MathGroup Archive 2007

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

Search the Archive

Re: How to do quickest

Dear Daniel,
Thank you for comments. Are also another cases divisable by 5 other than n  
is odd then the total is divisible by 5. When n is even and last decimal  
digit of n is 8

Dnia 30-01-2007 o 15:56:46 Daniel Lichtblau <danl at> napisa³(a):

> 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
> __________ NOD32 Informacje 2019 (20070130) __________
> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> lub

  • Prev by Date: Re: Apart question
  • Next by Date: Re: fundamental Integrate question
  • Previous by thread: Re: How to do quickest
  • Next by thread: Re: How to do quickest