how to solve the integer equation Abs[3^x-2^y]=1
a boy
(x,y)= (0,1),
(1,1),
(1,2),
(2,3)
can anyone give any else solution?
when the two integers x and y become bigger and bigger, is there a
pair integer (x,y) to give a small value for |3^x-2^y|? Or else,how
to prove the equation |3^x-2^y|=1having only 4 groups of integer
solution?
Andrzej Kozlowski
Here is the solution to one half of your problem, showing that the
only integer solutions of the equation 2^y-3^x == 1 are (0,1) and
(1,2). The other half of the problem is to show that the only
solutions of 3^x-2^y==1 are (1,1) and (2,3). The proof should be
similar "in spirit", but it seems harder so I will leave it to you.
So, consider the equation 2^y-3^x == 1. For x==0, we must have y==1.
Clearly, we can't have y==0. Suppose both x and y >= 1. Since 2^y ==
(3-1)^y == (-1)^y mod 3 and 3^x + 1 == 1 mod 3, y must be even. Let y
= 2a. Then 2^(2a)-1 == 3^x, hence (2^a-1)(2^a+1)==3^x. This is only
possible if both factors are powers of 3, i.e. 2a-1==3^u and 2a+1==3^v
(where u,v>=0). Hence 3^v-3^u == 2. If both u and v >=1 then the left
hand side is divisible by 3, a contradiction. Therefore v==1 and u==0.
Since u+v == x, x must be 1, a==1, so y =2. So the only solutions are
(0,1) and (1,2).
Andrzej Kozlowski
a boy
the only solutions of 3^x-2^y==1 are (1,1) and (2,3).
(-1)^x==1+2^y ( mod 4),
when x=2a+1, it must be y<2; when x=2a, y>1 and (3^a+1)(3^a-1)=2^y,so
only x=2.
Proved!
And more,I wonder that
does it exist two infinite and increasing integer sequence {Xi} and
{Yi} to satisfy {|3^Xi-2^Yi|} progressively decreasing?
Could you give me Yes or NO? and why?
a boy
And more,I wonder that
does it exist two infinite and increasing integer sequence {Xi}
and {Yi} to
satisfy {|3^Xi-2^Yi|} progressively decreasing?
Could you give me Yes or NO? and why?
Oh, the answer to this is to be No, for 1 is the last element of {|
3^Xi-2^Yi|} .
Now my question is changed to :
To construct an increasing integer pair sequence {(Xi,Yi)} satisfy
that
1) {Xi} is progressively increasing
2) {|3^Xi-2^Yi|} progressively decreasing
What is L=the maximum length of constructed sequence?
I think it's hard to me, can you give me a good solution?
Bill Rowe
>Does the equation |3^x-2^y|=1 give only 4 groups of solution? (x,y)=
>(0,1),
>(1,1), (1,2), (2,3)
>can anyone give any else solution? when the two integers x and y
>become bigger and bigger, is there a pair integer (x,y) to give a
>small value for |3^x-2^y|? Or else,how to prove the equation
>|3^x-2^y|=1having only 4 groups of integer solution?
It is easy to show there are more than the 4 pairs you give
above. Specifically,
In[3]:= FindInstance[
Abs[3 x^2 - 2 y^2] == 1 && x > 2, {x, y}, Integers]
Out[3]= {{x->9,y->11}}
Andrzej Kozlowski
4, which is not a prime. As Bill Rowe pointed out FindInstance shows
that the result is not true for 3x^2-2^y==1 (but it is true for
2^y-3x^2 == 1 as shown by my proof).
I am not even sure if if it is true that 3x^2-2^y==1 has only a
finite number of integer solutions. Gelfond has shown that a^x
+b^y==c^z has only a finite number of solutions, when a,b,c are all
non zero and none of them is a power of 2. However, since you do has a
power of 2 in your equation this result does not apply. It would be
interesting to find a proof one way or another.
A
On 4 Sep 2009, at 06:09, a boy wrote:
>
>
> On Fri, Sep 4, 2009 at 11:49 AM, a boy <a.doz...@gmail.com> wrote:
> As your prove is so superb and clear , now, I can easly prove that
> the only solutions of 3^x-2^y==1 are (1,1) and (2,3).
> for 3^x==(4-1)^x==1+2^y,
> (-1)^x==1+2^y ( mod 4),
> when x=2a+1, it must be y<2; when x=2a, y>1 and (3^a+1)
> (3^a-1)=2^y,so only x=2.
> Proved!
>
> And more,I wonder that
> does it exist two infinite and increasing integer sequence {Xi} and
> {Yi} to
> satisfy {|3^Xi-2^Yi|} progressively decreasing?
> Could you give me Yes or NO? and why?
> Oh, the answer to this is to be No, for 1 is the last element of {|
> 3^Xi-2^Yi|} .
> Now my question is changed to :
> To construct an increasing integer pair sequence {(Xi,Yi)} satisfy
> that
> 1) {Xi} is progressively increasing
> 2) {|3^Xi-2^Yi|} progressively decreasing
> What is L=the maximum length of constructed sequence?
>
> I think it's hard to me,can you give me a good solution?
>
>
> On Fri, Sep 4, 2009 at 2:01 AM, Andrzej Kozlowski
> <ak...@mimuw.edu.pl> wrote:
>
> On 3 Sep 2009, at 13:10, a boy wrote:
>
> Does the equation |3^x-2^y|=1 give only 4 groups of solution?
> (x,y)= (0,1),
> (1,1),
> (1,2),
> (2,3)
>
> can anyone give any else solution?
> when the two integers x and y become bigger and bigger, is there a
> pair integer (x,y) to give a small value for |3^x-2^y|? Or else,how
> to prove the equation |3^x-2^y|=1having only 4 groups of integer
> solution?
>
>
>
Daniel Lichtblau
> Does the equation |3^x-2^y|=1 give only 4 groups of solution?
> (x,y)= (0,1),
> (1,1),
> (1,2),
> (2,3)
>
> can anyone give any else solution?
> when the two integers x and y become bigger and bigger, is there a
> pair integer (x,y) to give a small value for |3^x-2^y|? Or else,how
> to prove the equation |3^x-2^y|=1having only 4 groups of integer
> solution?
You now have a proof, at least for one of the two cases. I'll show a
method to find solutions to related problems, or show that there are no
solutions in certain size ranges.
The general problem: find solutions to
j^m - k^n = s
where j<k are given integers, m and n are unknown nonnegative integer
exponents, and s is a small integer (small being dependent on various
sizes that show up; this is a bit of hand-waving).
We thus have j^m approximately equal to k^n in the sense that their
ratio is close to 1 (this is one place where "s small" enters). That is
m*log(j) - n*log(k) is approximately zero.
In a bit more detail, suppose the equation has a solution. Take logs on
both sides of
k^n = j^m - s
we obtain
n*log(k) = m*log(j) + log(1-s/j^m)
Now observe we can approximate the right hand side, to first order, as
m*log(j) - s/j^m
Suppose we wish to find solutions in the range u<m<2*u, and also suppose
u is not "tiny" (say, u>=10; we can handle smaller cases by brute
force). We set up an integer lattice as follows.
round(j^u*log(j)) 1 0
round(j^u*log(k)) 0 1
Then there is an element in this lattice of the form {x,m,n} where x is
"small". Indeed, it is in the ballpark of j^u*s/j^m, and this is no
larger than s by assumption on u<m. Thus we have a lattice element no
larger than roughly 3*u (since clearly n<m<2*u).
We can use LatticeReduce to find such a lattice element. For two rows it
is guaranteed (from basic literature on the topic) to produce a row no
larger than twice the smallest element in the lattice.
Case 1: If the second and third elements of the smallest row
significantly exceeds twice the above value, then clearly there is no
solution in the desired range. (Significant, in this case, depends on
various estimates, size of s, etc. In practice the adverb can be removed
provided s is small). Notice that a sufficiently large "small" vector
implies nonexistence of solutions in a range perhaps larger than 2*u.
Case 2: If the second and third elements of the smallest row are in the
desired size range, then we check to see if it gives a solution {m,n}.
Note (see example below): the solution we obtain might have j<=u.
Case 2 b: If not, then our test is inconclusive. I believe there are
planar lattice reduction refinements that might be used to show there
are no other sufficiently small lattice elements to satisfy the
equation, but this would take more work than I'm willing to do.
Here is an example. We look for m, n so that 3^m - 13^n is small (I use
these because I know there is such a pair). I'll look for a solution
with m in the range 5 to 10.
mult = 3^5;
a = 3;
b = 13;
lat = Round[{{mult*Log[3],1,0}, {mult*Log[13],0,1}}]
Out[35]= {{267, 1, 0}, {623, 0, 1}}
In[36]:= redlat = LatticeReduce[lat]
Out[36]= {{0, 7, -3}, {89, -2, 1}}
Our small solution has m=7, n=3. We see what this gives.
In[37]:= {3^7,13^3}
Out[37]= {2187, 2197}
So they differ by 10.
If I use a multiplier of 3^10 I get the same solution (this time the
small vector is {-270,7,-3}). While we (again) obtain a solution for
which u<10, there is nothing above to claim this cannot happen.
If I go to 3^20, that is, try for u<20<40, our smallest row is
{77044, -21365, 9151}. This is the "greatly exceeds" case, so we have no
solutions with 10<m<20.
I apologize for a bit of sloppiness in the statements and exposition.
I'm sure it could be made more precise, but not without more time and
effort than I'm willing to give, and more length than most anyone would
be willing to read.
Daniel Lichtblau
Wolfram Research
a boy
On Sep 5, 5:36 pm, Daniel Lichtblau <d...@wolfram.com> wrote:
>
> You now have a proof, at least for one of the two cases. I'll show a
> method to find solutions to related problems, or show that there are no
> solutions in certain size ranges.
>
> The general problem: find solutions to
>
> j^m - k^n = s
>
> Daniel Lichtblau
> Wolfram Research
what a brilliant exposition!
For any integer k and 3^k, suppose 2^j is the closest to 3^k, Gap[k]=|
3^k-2^j| is the subtraction .
Gap = Function[k, x = k*Log[2, 3]; Min[3^k - 2^Floor[x], 2^Ceiling
[x] - 3^k]];
Table[{i, Gap[i]}, {i, 1, 100}]
Out[24]:={{1, 1}, {2, 1}, {3, 5}, {4, 17}, {5, 13}, {6, 217}, {7,
139}, {8,
1631}, {9, 3299}, {10, 6487}, {11, 46075}, {12, 7153},.....
I find {Gap[i]} is not a increasing sequence. Suppose D is a strict
decreasing sub sequence of {Gap[i]} .
Q1: is the length of D always less than 3?
-------------
I have another question.
Table[Abs[s2 * 2^m + s3 *3^n], {s2, {-1, 1}}, {s3, {-1, 1}}, {m, 0,
100}, {n, 0, 100}];
Tally[Sort[Flatten[%]]]
The result shows that 21 != 2^i+3^j or |2^i-3^j| and 53 can not be
expressed as these form also.
But 53= 2 * 3^3 - 1
My another question is:
Q2: Is any odd prime number p can be expressed as one of these forms:
1. 2^i + 3^j
2. 2^i - 3^j or 3^i - 2^j
3. 2^i * 3^j +1
4. 2^i * 3^j -1
The answer to Q2 is true of false? How to prove or disprove it?
Daniel Lichtblau
> [...]
> For any integer k and 3^k, suppose 2^j is the closest to 3^k, Gap[k]=|
> 3^k-2^j| is the subtraction .
>
> Gap = Function[k, x = k*Log[2, 3]; Min[3^k - 2^Floor[x], 2^Ceiling
> [x] - 3^k]];
> Table[{i, Gap[i]}, {i, 1, 100}]
>
> Out[24]:={{1, 1}, {2, 1}, {3, 5}, {4, 17}, {5, 13}, {6, 217}, {7,
> 139}, {8,
> 1631}, {9, 3299}, {10, 6487}, {11, 46075}, {12, 7153},.....
> I find {Gap[i]} is not a increasing sequence. Suppose D is a strict
> decreasing sub sequence of {Gap[i]} .
> Q1: is the length of D always less than 3?
I suspect it is straightforward to show that you cannot have three
consecutive decreases.
As for getting any such subsequence, let's first define, for given
nonnegative integers mj and nj, the real value tj by
| mj*log(2) / (nj*log(3)) | = 1 + tj
The idea being, we want to find pairs {mj,nj} with corresponding tj very
small. In this setting, we have
2^mj - 3^nj = 3^nj * (3^(tj*nj)-1)
So what we require is an increasing set m1, m2, m3 and corresponding n1,
n2, n3 such that the sequence 3^nj * (3^(tj*nj)-1) decreases. To first
order approximation, this value is tj*nj*3^nj.
Can we have such trios? Perhaps naively, I think this would depend on
having "large" convergents somewhere in the continued fraction
representation of log(2)/log(3). But regardless, the answer is yes, we
do have such trios. Here is one such.
In[48]:= {Gap[666], Gap[661], Gap[660]} // N
317 314
Out[48]= {1.930005508972960 10 , 6.328896257794369 10 ,
313
> 4.037250828437273 10 }
I found this using the code below.
Gap[k_] := With[{x=k*Log[2, 3]}, Min[3^k-2^Floor[x], 2^Ceiling[x]-3^k]]
orderedlogs = Ordering[Table[Log[N[Gap[k]]], {k, 1, 5000}]]
orderdiffs = ListConvolve[{1,-1}, orderedlogs]
Now just look for two consecutive negative signs:
In[61]:= conseqs = Position[Partition[orderdiffs,2,1],
{a_,b_} /; a<0&&b<0]
Out[61]= {{659}, {1324}, {1989}, {2654}}
It is reasonable to conjecture that there is an upper bound on these
decreasing subsequence lengths. If I up the size from 5000 to 10000
elements, I do not get further trios, which indicates it might be
reasonable to conjecture that the maximum length of decreasing gap
subsequences is in fact 3. But when I increas again to 20000, I get a
sizeably larger set:
Out[67]= {{659}, {1324}, {1989}, {2654}, {12935}, {13600}, {14265},
{14930}, {16925}, {17590}, {18255}, {18920}}
Does this mean we might expect decreasing subsequences of length 4 or
larger? I do not know. One sign that would make me suspect a negative
answer is that the pattern near such trios is always the same.
In[78]:= Map[orderdiffs[[#[[1]]-2;;#[[1]]+3]]&, conseqs]
Out[78]= {
{1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1},
{1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1},
{1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1},
{1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1}, {1, 7, -5, -1, 2, 1}}
So we have recurring gap undulations, in a manner of speaking.
> -------------
> I have another question.
>
> Table[Abs[s2 * 2^m + s3 *3^n], {s2, {-1, 1}}, {s3, {-1, 1}}, {m, 0,
> 100}, {n, 0, 100}];
> Tally[Sort[Flatten[%]]]
>
> The result shows that 21 != 2^i+3^j or |2^i-3^j| and 53 can not be
> expressed as these form also.
> But 53= 2 * 3^3 - 1
> My another question is:
> Q2: Is any odd prime number p can be expressed as one of these forms:
> 1. 2^i + 3^j
> 2. 2^i - 3^j or 3^i - 2^j
> 3. 2^i * 3^j +1
> 4. 2^i * 3^j -1
>
> The answer to Q2 is true of false? How to prove or disprove it?
Again I do not know the answer but my guess is it is false. Call the
values you cannot attain in your table (extended to infinity...)
non-gaps. I would expect the density of such nongaps to be far too large
to recover them all as numbers in the form 3 or 4 above.
Again, this might be tied to behavior of the continued fraction of
log(2)/log(3).
Daniel Lichtblau
Wolfram Research
a boy
~~~~~~~~~~~~~~~~~~~~
666>661>660
317>314>313
In[48] do not show a trio which we need. Up to now, I have not find a trio
(i,j,k) that
i<j<k and Gap[i]>Gap[j]>Gap[k]
a boy
> I'm soooorry!
>
orderedlogs = Ordering[Table[Log[N[Gap[k]]], {k, 1, 5000}]] shows a trio.
It is 659,660,665! not 660,661,666.
Gap[665]< Gap[660]< Gap[659]
a boy
Gap = Function[k, x = k*Log[2, 3];
Min[3^k - 2^Floor[x], 2^Ceiling[x] - 3^k]];
orderedlogs = Ordering[Table[Log[N[Gap[n]]], {n, 1, 50000}]];
With[{sublists = Split[orderedlogs, #1 >= #2 &]},
With[{m = Max[Length /@ sublists]},
Select[sublists, Length[#] == m &]]]
I have found these trios:
{{665, 660, 659}, {1330, 1325, 1324}, {1995, 1990, 1989}, {2660, 2655,
2654}, {12941, 12936, 12935}, {13606, 13601, 13600}, {14271, 14266,
14265}, {14936, 14931, 14930}, {16931, 16926, 16925}, {17596,
17591, 17590}, {18261, 18256, 18255}, {18926, 18921, 18920}, {29207,
29202, 29201}, {29872, 29867, 29866}, {30537, 30532,
30531}, {31202, 31197, 31196}, {32532, 32527, 32526}, {33197, 33192,
33191}, {33862, 33857, 33856}, {34527, 34522, 34521}, {44808,
44803, 44802}, {45473, 45468, 45467}, {46138, 46133, 46132}, {46803,
46798, 46797}, {48133, 48128, 48127}, {48798, 48793,
48792}, {49463, 49458, 49457}}