[seqfan] Re: Subject: Need help computing a number

[Alex Meiburg]

You can quickly rule out lots of numbers using a sieve based on various
small primes. For instance, the following Mathematica code:

k=104917;
Do[
If[Not[PrimeQ[p]],Continue[]];
residues=Reap[Do[If[Mod[Mod[k,p]*PowerMod[2,m,p]-1,p]==0,Sow[m]],{m,0,p-2}]][[2]];
If[Length[residues]==0,Continue[]];
Print["M mod ",(p-1)," is not equal to ",residues[[1]]];
,{p,3,100}]

prints out:

m mod 2 is not equal to {0}
m mod 4 is not equal to {3}
m mod 6 is not equal to {0,3}
m mod 10 is not equal to {5}
m mod 12 is not equal to {1}
m mod 18 is not equal to {9}
m mod 28 is not equal to {20}
m mod 36 is not equal to {5}
m mod 40 is not equal to {9,29}
m mod 52 is not equal to {39}
m mod 58 is not equal to {2}
m mod 60 is not equal to {24}
m mod 66 is not equal to {18}
m mod 70 is not equal to {13,48}
m mod 72 is not equal to {5,14,23,32,41,50,59,68}
m mod 78 is not equal to {4,43}
m mod 82 is not equal to {55}

>From the first five lines, for instance, we can see that it must be of the
form 12k+5 and not a multiple of 5. This immediately trims down the number
of required primality tests by 93%.
If we add in the "mod 36", we see that it must be 36k+17, or 36+29 (so not
36k+5). That's another 1/3 of the tests we can skip.
And so on!
This is assuming that the bulk of the time is spent doing primality tests,
since "double and add 1" is a very quick operation.

-- Alexander Meiburg


On Tue, Jul 30, 2024 at 2:42 PM Robert Gerbicz <robert.gerbicz at gmail.com>
wrote:

> "If 104916 takes m steps, the prime reached will be 104917*2^m - 1,"
>
> From http://www.prothsearch.com/rieselprob.html
> the 104917*2^340181-1 is prime. Maybe 340181 is also the smallest exponent.
>
> Neil Sloane <njasloane at gmail.com> ezt írta (időpont: 2024. júl. 30., K,
> 20:06):
>
> > Dear Math Fun, Sequence Fans,
> >
> > Start with an integer k, 13 say, and repeatedly double it and add 1 until
> > reaching a prime:
> >
> > 13 -> 27 -> 55 -> 111 -> 223.
> >
> > This took 4 steps, so we set R(13) = 4. This is called Riesel's problem,
> > and if we never reach a prime we set R(k) = 0. The sequence R(k) is
> > A050412.
> > I think Riesel showed R(509203) = 0, and it seems it is believed that
> R(k)
> > != 0 for k<509203.
> >
> > For another sequence (A374965) that Harvey Dale and I have been studying,
> > we badly need the value of R(104916). Can someone help?  If 104916 takes
> m
> > steps, the prime reached will be 104917*2^m - 1,
> >
> > so we don't actually need to see the prime (just m).
> >
> > I ran a naive Mathematica program (from A050412) on my iMAC, but I killed
> > it after nearly 24 hours.
> >
> >  I have no idea how far it got.  The bottleneck is presumably the
> primality
> > testing, but I don't know who has the fastest program for that.
> > Best regards
> > Neil
> >
> > Neil J. A. Sloane, Chairman, OEIS Foundation.
> > Also Visiting Scientist, Math. Dept., Rutgers University,
> > Email: njasloane at gmail.com
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>