Re: exponential diophantine equations
- To: mathgroup at smc.vnet.net
- Subject: [mg62968] Re: [mg62922] exponential diophantine equations
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Fri, 9 Dec 2005 05:10:46 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
*This message was transferred with a trial version of CommuniGate(tm) Pro*
I have experimented a little more with this on the train home (thanks
to my faithful PowerBook) and have a few remarks.
The method I sketched below where I used the first 200 primes p to
test if f[k] is a square mod p is an overkill. In fact, it is much
better to use only a few primes at first (perhaps just one) and then
run the function again over the set of primes that get selected,
using different primes, of course. Here is what I did on the train.
First, I redefined the function g as follows:
g[k_:1, l_] := Function[x, Evaluate[And @@ Prepend[
Table[test[x, Prime[i]], {i, k, l}], test25[x]]]]
Now g takes two arguments, with the first one being optional and by
default 1. So g[200] will still test the first 200 primes, but g
[200,200] will just test the 20th prime. The test for divisibility of
f[k] by 25 is always included.
Now this is what I did:
ls=Select[Range[2000000],g[5000,5000]];//Timing
{205.797 Second,Null}
In other words, I first used the 5000 prime (which is 48611) to test
the first 2000000 integers as candidates for k, and collected them in
the list ls. It turned out that ls is pretty large, with around
60,000 numbers (I tested this with Length[ls] but forgot to record
the exact number i got and do not wish to run this again). After that
I run the program again on ls, but with different list of primes:
In[23]:=
ls=Select[ls,g[20]];//Timing
Out[23]=
{109.097 Second,Null}
This time it turned out that:
In[24]:=
Length[ls]
Out[24]=
1
Not surprisingly:
In[25]:=
ls
Out[25]=
{6}
So there seems to be no k under 2000000. We can certainly do much
better than that; the program has so far taken only about 5 and a
half minute to run. But it is already clear that if another solution
exists it will have to be pretty large.
Andrzej Kozlowski
PS. I extended the checked range to 1<=k <=3000000. I think I'll stop
here, as I have very little belief left that anything will be found.
On 9 Dec 2005, at 12:40, Andrzej Kozlowski wrote:
> Here is one approach. We will need the package:
>
> << NumberTheory`NumberTheoryFunctions`
>
> Let's start with a primitive approach and then improve it to run
> much faster. The primitive approach would be like this. First we
> write your equation as
>
> 2^k*3*(k + 5)^2 + 131*k + 7 == (5*x)^2
>
> Let us define a function f[k] as follows:
>
> f[k_Integer] := 2^k*3*(k + 5)^2 + 131*k + 7
>
> What we are looking for is values of k for which the the following
> are true:
>
> 1. f[k] is 0 mod 25.
> 2. f[k] is a perfect square.
>
> It is easy to write a slow function that looks for such k. First of
> all, we need a function f[k_,n_] which efficiently computes Mod[f
> [k],n]. Here is this function:
>
> f[k_Integer, p_Integer] :=
> Mod[PowerMod[2, k, p]*Mod[3, p]*PowerMod[k + 5, 2, p] + Mod
> [131*k + 7,
> p], p]
>
> The test for divisibility of f[k] by 25 takes the form
>
> test25[k_Integer] := f[k, 25] == 0
>
> We also need a test to check if a number is a perfect square. Here
> is the obvious one:
>
>
> test1[x_Integer] := IntegerQ[Sqrt[f[x]]]
>
> Now let's define a function that combines both tests:
>
> h = Function[x, Evaluate[And @@ Prepend[{test1[x]}, test25[x]]]];
>
>
> Let's check that this will work well on the one solution we know:
>
>
> h[6]
>
> True
>
> On the other hand:
>
>
> h[7]
>
> False
>
> OK, using this function we can now try to find any solutions for k
> between 1 and 10000:
>
>
> Select[Range[10000],h]//Timing
>
>
> {36.1681 Second,{6}}
>
>
> This is rather slow so we try something more sophisticated. Instead
> of checking is f[k] is a square root we will check if it is a
> square root modulo a prime p. We will use a large number of primes
> and this will still be faster than doing an integer check. Here is
> the test function:
>
> test[k_Integer, p_Integer] := ReleaseHold[Block[ {$Messages = {}},
> Check[SqrtMod[f[k, p], p]; True, False]
> ]]
>
> I do not have the time at this moment to explain exactly what this
> does. The key function is SqrtMod from the NumberTheoryFunctions
> package. it computes square roots modulo a prime. Here is now a
> function that will check if f[k] of a number is a square module the
> first n -primes (it also checks if f[k] is divisible by 25)
>
> g[k_] := Function[
> x, Evaluate[And @@ Prepend[Table[test[x, Prime[i]], {i, 1, k}],
> test25[x]]]]
>
> I am going to use g[200] which checks the first 200 primes.
>
> let7s try the above computation with g[200]:
>
>
> Select[Range[10000],g[200]]//Timing
>
>
> {3.41956 Second,{6}}
>
> Note that we still correctly identified the solution 6, but we got
> it a lot faster. So we can try looking at larger ranges. If we find
> a some possible solutions we still have to run the primitive test
> on them to check if they are real solutions and not just solutions
> modulo the first 200 primes.
>
> In[21]:=
> Select[Range[20000],g[200]]//Timing
>
> Out[21]=
> {6.82253 Second,{6}}
>
> Still no luck, but performance seems to scale quite well. I have no
> time now to try looking for more solutions (as my lecture will
> begin in half an hour) but we know that for k between 1 and 20000
> there is only one solution, which is the one you already knew.
>
> Andrzej Kozlowski
>
>
>
>
>
>
>
> On 9 Dec 2005, at 02:02, Andrea wrote:
>
>> Dear Andrzej,
>>
>> Oh those signs! I typed +7. Mistake. It should be -7.
>>
>> Andrea
>>
>> At 01:38 AM 12/8/2005, Andrzej Kozlowski wrote:
>>
>>> On 8 Dec 2005, at 17:27, Andrea wrote:
>>>
>>>>
>>>> I'm trying to find out how to use Mathematica to find solutions to
>>>> exponential diophantine equations like the following:
>>>>
>>>> (5x)^2 - 2^k * 3 * (5+k)^2 - 131 * k + 7 = 0. I want to
>>>> obtain
>>>> solutions for x and k. (One solution is x = 31, k = 6, but I didn't
>>>> find
>>>> this using Mathematica!)
>>>
>>> Are you sure you have found a solution? I get:
>>>
>>> In[30]:=
>>> (5x)^2 - 2^k * 3 * (5+k)^2 - 131 * k + 7 /.{x->31,k->6}
>>>
>>> Out[30]=
>>> 14
>>>
>>>
>>> One can certianly try some "educated searches" but before
>>> starting it
>>> woudl be better to be sure that this is really the equation you want
>>> to solve!
>>>
>>> Andrzej Kozlowski
>>>
>>
>