Re: How to do quickest

*To*: mathgroup at smc.vnet.net*Subject*: [mg73047] Re: [mg73035] How to do quickest*From*: Artur <grafix at csl.pl>*Date*: Wed, 31 Jan 2007 00:00:40 -0500 (EST)*References*: <epf93g$buf$1@smc.vnet.net> <200701290939.EAA12706@smc.vnet.net> <200701301200.HAA16288@smc.vnet.net> <45BF5CAE.6060602@wolfram.com>

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

**References**:**Re: NDSolve -- initial conditions***From:*Jens-Peer Kuska <kuska@informatik.uni-leipzig.de>

**How to do quickest***From:*Artur <grafix@csl.pl>