MathGroup Archive 2007

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

Search the Archive

Re: How to do quickest

Daniel Lichtblau wrote:
> Artur wrote:
>> Probably these procedure isn't possible to do much quicker because 
>> limit  is time of single PrimeQ checking but mayby somebody is able do 
>> some  quickest (these procedure looking for prime numbers of the form  
>> 1+4+4^2+4^3+...4^x (mayby number 5 is only one such number ???):
>> a = {}; k = 0; Timing[Do[k = k + 4^x; If[
>>    PrimeQ[k], Print[k]; AppendTo[a, k]], {x, 0, 10000}]; a]
>> PrimeQ is relatively quick but working only up to upper limit, later 
>> is  necessary uses NumberTheory packagae and much more slowest 
>> procedures.
> First, you don't need NumberTheory packages, except possibly for minor 
> post-processing. It is not known whether PrimeQ will ever give a false 
> positive, but it cannot give a false negative. So if it claims your 
> number is composite then it is composite. Worst case, you find 
> contenders other than 5 and you have to prove primality. Worry about it 
> when you get one.
> Second, there are various classes of values that can be skipped. We work 
> with (changing your notation ever so slightly) 1+4+4^2+...+4^n, or 
> Sum[4^j, {j,0,n}]. If n is odd then the total is divisible by 5 (either 
> note the terms pair off as +1 and -1 mod 5, or else observe 1+x+...+x^n 
> is divisible by 1+x for n odd). If n is a multiple of 3 then 3 divides 
> the sum, because each summand is equal to 1 mod 3. Also easy to show 7 
> divides everyone in this class.
> Perhaps there is an obvious way to rule out all other contenders. Some 
> seem to factor as (a+1)*(3*a+1). Offhand I don't know if there is an 
> underlying pattern to this.
> Daniel Lichtblau
> Wolfram Research

Probably I am still missing a beat here, but what I wrote can be made 
considerably more efficient. The numbers are just strings of consecutive 
1's expressed base 4. So if the string length is not prime then it is 
easy to factor. Say the length is p*q. Then the number is

(1 + 4 + 4^2 + ... + 4^(p-1)) * (1 + 4^p + ... + 4^(p*(q-1)))

(or something like that, but correctly minding ones p's and q's).

Conclusion: you only need test cases where you sum to a prime length.

In[1]:= k = PrimePi[10000];

In[2]:= Timing[Select[Table[Sum[4^j,{j,0,Prime[n]-1}],
   {n,1,k}], PrimeQ]]

Out[2]= {3134.84, {5}}

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Re: Apart question
  • Next by Date: Re: Confused about correlations in sequence of Random[] numbers
  • Previous by thread: Re: How to do quickest
  • Next by thread: Remote Kernel does nothing