Re: how to solve the integer equation Abs[3^x-2^y]=1
- To: mathgroup at smc.vnet.net
- Subject: [mg103076] Re: how to solve the integer equation Abs[3^x-2^y]=1
- From: a boy <a.dozy.boy at gmail.com>
- Date: Mon, 7 Sep 2009 02:35:15 -0400 (EDT)
- References: <200909031110.HAA24198@smc.vnet.net> <h7tbeb$fs6$1@smc.vnet.net>
On Sep 5, 5:36 pm, Daniel Lichtblau <d... at wolfram.com> wrote:
> 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?
>
> 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
On Sep 5, 5:36 pm, Daniel Lichtblau <d... at 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?
- Follow-Ups:
- Re: Re: how to solve the integer equation Abs[3^x-2^y]=1
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: Re: how to solve the integer equation Abs[3^x-2^y]=1
- References:
- how to solve the integer equation Abs[3^x-2^y]=1
- From: a boy <a.dozy.boy@gmail.com>
- how to solve the integer equation Abs[3^x-2^y]=1