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>
- Re: NDSolve -- initial conditions