Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: exponential diophantine equations

  • To: mathgroup at smc.vnet.net
  • Subject: [mg62998] Re: exponential diophantine equations
  • From: Peter Pein <petsie at dordos.net>
  • Date: Sat, 10 Dec 2005 06:03:13 -0500 (EST)
  • References: <dnbndq$5ua$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski schrieb:

> 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 200th 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}
> 
...

A slightly faster approach checks only k in
Flatten[Table[{6, 26, 46, 47, 66, 86, 99} + 100*n, {n, 0, kmax/100}]].

Experiments show, that this list takes its strongest reduction with the 
test g[p1,p2], where p1 and p2 are near EulerGamma*PrimePi[kmax] (most 
probably by accident(?)):

First[Timing[
  kmax = 10^7;
  ls = Select[
   Flatten[Table[{6, 26, 46, 47, 66, 86, 99} + 100*n, {n, 0, kmax/100}]],
   g @@ (Floor[PrimePi[kmax]*EulerGamma] + {-2, 2})];
]]
--> 146.641*Second
Length[ls]
--> 21876

Timing[Select[ls, g[20]]]
--> {6.047*Second, {6, 3706947}}

unfortunately no new solution; just too weak tests:
g[21, 21][3706947]
--> False

Peter


  • Prev by Date: Re: Using The Random Function to predict Things
  • Next by Date: Re: Evaluate[] not needed in With[]
  • Previous by thread: Re: exponential diophantine equations
  • Next by thread: Re: Notebook for Borel-Tanner Distribution