On a obtenu la bourse FARE ))

2010/01/26

Problem from Number Theory

Recently my friend asked me, whether I could solve an interesting problem. Since I am into the stuff like that(i.e. during the vacations I had fun with mathematical programming). And the statement of the problem was very simple so I just could not help not to try to solve it. So here is my solution. If there are any errors, or something is not clear, be my guest and comment.

Find all m and n that
2ⁿ - 3^m = 1, m,n∈N.

Solution.

The pairs (n,m) = (2,1); (1,0) obviously satisfy the relation.

Below I prove that there are no other solutions to this equation.
Let's consider n>4 and m > 2.
2ⁿ - 1 = 3^m ⇒ (2 - 1)(2^{n - 1} + 2^{n - 2} + … + 1) = 3^m ⇒ 2^{n - 1} + 2^{n - 2} + … + 1 = 3^m
For the equality to hold 2^{n - 1} + 2^{n - 2} + … + 1 ≡ 0 mod 3 ⇒ 2^{n - 1} + 2^{n - 2} + … + 1 = 2^{n - 2}(2 + 1) + … + (2 + 1).
We can construct these pairs because if not, we'll have the situation 2^{n - 1} + B = 3^m, where
B = 2^{n - 3}(2 + 1) + … + (2 + 1) divides by 3, but 2^{n - 1} does not divide by 3, so n (the number of terms in the left hand side of the obtained equation) is even, and it is possible to obtain the following equation:
2^{n - 2} + 2^{n - 4} + … + 2² + 1 = 3^{m - 1}
Let's consider the left hand side once more. We obtained n/2 terms in the left hand side of the equation. Which comprise the sum of terms with the powers n - 2, n - 4,…,0.
There are 2 possible situations:

• n/2 is even, then we can rewrite the equation in the following form:
  2^{n - 4}(2² + 1) + … + (2² + 1) = 3^{m - 1} ⇒ 5(2^{n - 4} + … + 1) = 3^{m - 1}, this equation does not have solutions since 3^{m - 1} does not divide by 5.
  


• n/2 is odd, then
  1 + 2² + 2⁴ ≡ 0 mod 3⇒1 + 2² + 2⁴ + 2⁶ does not divide by 3.
  1 + 2² + 2⁴ + 2⁶ + 2⁸ + 2¹⁰ = D ≡ 0 mod 3 ⇒ D - 2¹⁰ = 1 + 2² + 2⁴ + 2⁶ + 2⁸ does not divide by 3.
  From the previous 2 statements one can see that the left hand side sum divides by 3
  only if n/2 = 3k, and since n/2 is odd, k = 2p + 1,p = 0…∞.
  For this case we have
  (1 + 2² + 2⁴)(1 + 2⁶ + 2¹² + … + 2^{n - 6}) = 3^{m - 1} ⇒ 21(1 + 2⁶ + 2¹² + … + 2^{n - 6}) = 3^{m - 1} ⇒
  ⇒ 7(1 + 2⁶ + 2¹² + … + 2^{n - 6}) = 3^{m - 2}. Which is not possible, since 3^{m - 2} does not divide by 7.
  

So the final answer is: (n,m) = (2,1); (1,0).

How to save data to file in J

J is a very interesting, concise and efficient language that I often use for mathematical computaions.
In this post I will write the different ways of doing things in J.

I needed to generate a lot of primes in the range (1e8, 1e9), and then save them to file in order to play with them in Python. I tried to play with it in J but there it tries to create the matrix for this procedure which requires a lot of memory. Here is how I wrote the data to file in J:

primes =: p:i.6e7 .NB Generate primes from 2 to 1190494771
primes =: ((primes < 1e9)*.(primes > 1e8)) # primes .NB select primes with 9 digits only
primes =: ": primes .NB Convert the list of primes to the list of strings
(primes,LF) 1!:2 <'/home/san/primes.txt' .NB write the primes to the file

So this way I got a text file of the size 430 MB :)
And I processed this file using python in 687.204969883 seconds.

31 décembre 2009