Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2007

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

Search the Archive

Re: How to do quickest

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.
> 
> BEST WISHES
> ARTUR

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
  • Prev by Date: Re: Numerical quantifier elimination
  • Next by Date: Re: Apart question
  • Previous by thread: How to do quickest
  • Next by thread: Re: How to do quickest