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

Dnia 30-01-2007 o 15:56:46 Daniel Lichtblau <danl at wolfram.com> 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.
>>  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
>
>
> __________ NOD32 Informacje 2019 (20070130) __________
>
> Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> http://www.nod32.com lub http://www.nod32.pl

```

• 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