## Re: [PrimeNumbers] primes close to 2^(2^n) for n = 11..14

Expand Messages
• ... I don t know any list which goes up to such high powers of 2. Heheh, 2^(2^9) I could give you a vast number of examples for. You could generate PRPs using
Message 1 of 17 , Jan 3, 2003
--- Carl Devore <devore@...> wrote:
>
>
> I am doing some timing tests in Maple in order to hunt down some bugs in
> its large-integer computation. It would be useful if I had primes close
> to 2^(2^n) for n = 11..14. This is beyond the range that can be found
> with Maple, but is too small to be on lists of the largest known primes.
> Can someone direct me to a list?

I don't know any list which goes up to such high powers of 2. Heheh, 2^(2^9)
I could give you a vast number of examples for.

You could generate PRPs using primeform. You can do any number of PRP tests,
and a Lucas test too. Ones for n=11 and 12 you can easily ECPP prove (but
n=13 looks like it owuld take a bit of time).

A simple ABC2 file like
<<<
ABC2 2^(2^11)+\$a
a: from 1 to 99999 step 2
>>>
should do the trick

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• ... I found a list for the largest n-bit prime for n up to 400. It should be feasible, and useful I believe, to extend this up n ~ 2^14. Even a list of any
Message 2 of 17 , Jan 3, 2003
On Fri, 3 Jan 2003, Phil Carmody wrote:
> I don't know any list which goes up to such high powers of 2. Heheh, 2^(2^9)
> I could give you a vast number of examples for.

I found a list for the largest n-bit prime for n up to 400. It should be
feasible, and useful I believe, to extend this up n ~ 2^14. Even a list
of any n-bit prime for each n would be useful.
• ... This is a job for script-mode PFGW. Anyone care to write a script that will generate 10 PRPs above and below each exponent? (You only need script mode to
Message 3 of 17 , Jan 4, 2003
--- Carl Devore <devore@...> wrote:
>
> On Fri, 3 Jan 2003, Phil Carmody wrote:
> > I don't know any list which goes up to such high powers of 2. Heheh, 2^(2^9)
> > I could give you a vast number of examples for.
>
> I found a list for the largest n-bit prime for n up to 400. It should be
> feasible, and useful I believe, to extend this up n ~ 2^14. Even a list
> of any n-bit prime for each n would be useful.

This is a job for script-mode PFGW. Anyone care to write a script that will
generate 10 PRPs above and below each exponent?
(You only need script mode to get it to stop after finding 10, you could
simply get it to to a fixed size band using ordinary ABC2 mode.)

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• ... That is a pretty slow way to do it. Might I suggest using CPAPSieve to presieve. It operates as fast (or nearly as fast) as NewPGen. Once the sieved file
Message 4 of 17 , Jan 4, 2003
--- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@y...>
wrote:
> --- Carl Devore <devore@m...> wrote:
>>
>> On Fri, 3 Jan 2003, Phil Carmody wrote:
>>>I don't know any list which goes up to such high powers of 2.
>>>Heheh, 2^(2^9) I could give you a vast number of examples for.
>>
>>I found a list for the largest n-bit prime for n up to 400. It
>>should be feasible, and useful I believe, to extend this up
>>n~2^14. Even a list of any n-bit prime for each n would be useful.
>
>This is a job for script-mode PFGW. Anyone care to write a script
>that will generate 10 PRPs above and below each exponent?
>(You only need script mode to get it to stop after finding 10, you
>could> simply get it to to a fixed size band using ordinary ABC2
>mode.)

That is a pretty slow way to do it. Might I suggest using CPAPSieve
to presieve. It operates as fast (or nearly as fast) as NewPGen.
Once the sieved file is generated (in ABC or ABCD format, not ABC2)
Then, once the well factored data is built, use PFGW to process the
file. Stop (manually) when 10 (or more) primes have been found.

This method should allow a much faster search than using the ABC2
format and using PFGW to trial factor each candidate individually.

If anyone wants to do this, I have a newer version of CPAPSieve that
can do b^n-K as well as b^n+K factoring (and a program called reverse
that reverses the -maxK to -minK file so that the number closer to
k==0 are tested first).

If anyone wants to do this, contact me off list. I might be hard to
get ahold of this weekend (will be out hunting), but I can get you
a newer version of CPAPSieve (the version on-line will work for the
b^n+K testing), and a version of reverse.exe (simple text file line
reversing program).

Jim.

PS, here are some results (these are ONLY prp-3 tested):

2^2048+981
2^2048+1617
2^2048+3063
2^2048+3211
2^2048+4143
2^2048+7405
2^2048+9843
2^2048+10665
2^2048+10725
2^2048+11097
2^2048+11467

2^2048-1557
2^2048-2543
2^2048-7437
2^2048-8507
2^2048-9443
2^2048-9509
2^2048-11339
2^2048-11837
2^2048-12459
2^2048-12855
2^2048-13407
2^2048-14505
2^2048-15155
2^2048-16773
2^2048-18819
2^2048-19575

2^4096-2549
2^4096-8067
2^4096-8627
2^4096-8799
2^4096-9443
2^4096-14477
2^4096-16859
2^4096-17555
2^4096-18365
2^4096-20655

2^4096+1761
2^4096+7227
2^4096+7423
2^4096+10093
2^4096+10473
2^4096+13965
2^4096+17335
2^4096+17355
2^4096+19891
2^4096+22803

2^8192+897
2^8192+9543
2^8192+10813
2^8192+13371
2^8192+14931
2^8192+14985
2^8192+15505
2^8192+15763
2^8192+16305
2^8192+19423

2^8192-2439
2^8192-5619
2^8192-9345
2^8192-9515
2^8192-19085
2^8192-19733
2^8192-21713
Tested up to 2^8192-43073, but I am out of time and have to go.

Options for CPAPSieve would be:

cpapsieve -b=2 -n=16384 -K=-1 -k=-250000 -O=14m -L
cpapsieve -b=2 -n=16384 -k=1 -K=250000 -O=14p -L

then do reverse 14m.in to get the minuses into n-1 to n-250000 order

then use WinPFGW to test 14p.in and 14m.in files until enough PRPs
are found. A range of 250000 should be enough for 2^(2^14)+-k range.
This size would need increased as the size of the numbers increased
(or if searching for more PRP's)
• ... Original problem - powers of two. ... new problem - arbitrary n, from 400-4000. ... You want to do that 3600 times? It s the manually part that would
Message 5 of 17 , Jan 4, 2003
--- "jim_fougeron <jfoug@...>" <jfoug@...> wrote:
> --- In primenumbers@yahoogroups.com, Phil Carmody <thefatphil@y...>
> wrote:
> > --- Carl Devore <devore@m...> wrote:
> >>
> >> On Fri, 3 Jan 2003, Phil Carmody wrote:
> >>>I don't know any list which goes up to such high powers of 2.

Original problem - powers of two.

> >>>Heheh, 2^(2^9) I could give you a vast number of examples for.
> >>
> >>I found a list for the largest n-bit prime for n up to 400. It
> >>should be feasible, and useful I believe, to extend this up
> >>n~2^14. Even a list of any n-bit prime for each n would be useful.

new problem - arbitrary n, from 400-4000.

> >This is a job for script-mode PFGW. Anyone care to write a script
> >that will generate 10 PRPs above and below each exponent?
> >(You only need script mode to get it to stop after finding 10, you
> >could> simply get it to to a fixed size band using ordinary ABC2
> >mode.)
>
> That is a pretty slow way to do it. Might I suggest using CPAPSieve
> to presieve. It operates as fast (or nearly as fast) as NewPGen.
> Once the sieved file is generated (in ABC or ABCD format, not ABC2)
> Then, once the well factored data is built, use PFGW to process the
> file. Stop (manually) when 10 (or more) primes have been found.

You want to do that >3600 times? It's the 'manually' part that would
disincline me, personally. I still think it's a job for PFGW which can

However, for small powers, even calc does the job (and I assume pari's not
far behind).

for(p=400;p<600;++p){printf("2^%d+ :",p);v=2^p;for(n=0;n<10;++n){v=nextcand(v);printf("
%d",v-2^p);}print("");}

2^400+ : 181 435 1021 1161 1327 1431 2443 2605 3097 3877
2^401+ : 807 989 1119 1379 1689 1841 2651 3737 4031 4689
2^402+ : 505 793 849 1443 2389 2875 2979 3027 3099 3267
2^403+ : 293 683 701 713 989 1271 1425 1581 1901 2033
2^404+ : 55 63 265 753 837 1833 2025 2203 2881 2973
2^405+ : 539 731 789 887 1265 1517 2039 2489 3119 3209
2^406+ : 129 169 405 583 777 1005 1183 1387 1743 1813
2^407+ : 309 453 641 659 761 905 921 993 1043 1265
2^408+ : 37 231 247 267 325 385 915 927 1137 1645
2^409+ : 29 125 381 399 587 977 1071 1211 1329 1355
2^410+ : 33 375 643 765 817 909 1015 1183 1189 1357
2^411+ : 63 333 345 1493 1839 2793 3245 3491 3621 3789
2^412+ : 67 115 385 463 961 1087 1387 1585 2407 2775
2^413+ : 221 317 411 435 1121 1167 1439 2661 3021 3599
2^414+ : 315 507 537 1957 2047 2359 2529 2593 2695 2737
2^415+ : 323 659 669 1095 1313 1403 1649 1661 1715 1799
2^416+ : 235 921 961 987 1131 1177 1261 1653 1723 1797
2^417+ : 245 495 605 651 929 1025 1145 1619 2181 2199
2^418+ : 163 739 937 1443 1465 1659 1857 1995 2103 2113
2^419+ : 299 431 905 1271 1575 1625 1649 1653 2963 3441
2^420+ : 45 543 705 1005 1255 1381 1443 1485 1503 1801
2^421+ : 105 261 837 969 1421 1635 1655 1667 2061 2765
2^422+ : 163 273 537 805 1507 1645 1875 2199 2437 2475
2^423+ : 309 459 593 701 821 1089 1571 2055 2415 2465
2^424+ : 163 423 451 637 703 823 967 1077 1285 1893
2^425+ : 57 329 387 497 671 869 1295 1509 1535 2129
2^425+ : 57 329 387 497 671 869 1295 1509 1535 2129
2^426+ : 423 439 855 1599 1725 2017 2203 2377 2515 3007
2^427+ : 69 183 489 659 669 863 1191 1359 1509 1751
2^428+ : 345 651 837 897 1365 1693 1741 2233 2535 2601
2^429+ : 131 611 921 1905 2937 3029 3321 3369 4085 4635
2^430+ : 73 1105 2173 2535 2647 2869 3075 3907 3913 4053
2^431+ : 173 485 545 681 791 813 1383 1653 1661 1869
2^432+ : 1093 1387 2167 2331 2517 3007 3187 3553 5187 5241
2^433+ : 335 629 1229 2051 2249 2355 2835 3357 3629 4035
2^434+ : 103 495 553 805 807 1147 1273 1783 1945 1989
2^435+ : 561 653 821 873 1023 1061 1491 1725 1991 2229
2^436+ : 295 303 337 567 625 951 975 1467 1885 1917
2^437+ : 117 249 425 1031 1301 1415 2189 2265 2277 2715
2^438+ : 25 213 553 1183 1303 1507 1909 1923 2517 2773
2^439+ : 101 543 1173 1815 2753 3443 3489 3801 4215 4623
2^440+ : 187 853 897 1677 1873 1995 2605 2811 3385 3655
2^441+ : 227 257 509 767 1127 1361 1599 1779 1869 2039
2^442+ : 189 559 609 723 1137 1189 1609 1837 2353 2685
2^443+ : 53 533 743 785 863 1145 1229 1805 1955 2781
2^444+ : 267 631 913 1081 1347 1405 1411 2091 2095 2187
2^445+ : 41 95 227 269 585 1151 1491 1511 1829 2561
2^446+ : 33 435 825 1105 1467 1713 1849 1929 2203 2527
2^447+ : 99 575 711 1341 1485 1619 1659 1743 1859 2223
2^448+ : 211 597 703 721 1731 1803 2367 2443 2473 2487
2^449+ : 459 869 909 965 1271 1289 1587 1629 2147 3171
2^450+ : 213 225 289 487 585 1107 1137 1195 1365 1479
2^451+ : 23 165 563 1491 1751 1941 2375 2619 3065 3231

at about 1 second per row on a heavily loaded <1GHz machine.

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• ... Judging from the conjectured density of primes in this region you were quite lucky! One useful measure of good luck in a Poisson distribution is the
Message 6 of 17 , Jan 4, 2003
<paulunderwood@m...>" <paulunderwood@m...> wrote:

> 2^(2^14)+2775 is 2-PRP! (1.480000 seconds)
> 2^(2^13)+897 is 2-PRP! (0.280000 seconds)
> 2^(2^12)+1761 is 2-PRP! (0.110000 seconds)
> 2^(2^11)+981 is 2-PRP! (0.000000 seconds)

Judging from the conjectured density of primes in this region you
were quite lucky!
One useful measure of good luck in a Poisson distribution is the
proportion of the expected time that the first event happens before
the expected time. This has the pleasing properties of scale
independence, an upper bound on good luck of 1, no lower bound and an
average of zero.
For instance, the density of primes near 2^(2^11) is 2^11 * ln 2 =
1419.6 so in finding 2^(2^11)+981 Paul's good luck was (1419.6-
981)/1419.6 = 0.309

2^(2^14)+2775 Luck= 0.756
2^(2^13)+897 Luck= 0.842
2^(2^12)+1761 Luck= 0.380
2^(2^11)+981 Luck= 0.309
Total=2.286

Whereas for me

2^(2^14)-13797 Luck= -0.215
2^(2^13)-2439 Luck= 0.570
2^(2^12)-2549 Luck= 0.102
2^(2^11)-1557 Luck= -0.097
Total=0.361

I guess I would get the most bad luck on the 2^(2^14) search, as it's
the most expensive!

Richard Heylen
• ... Nothing more than PNT and Poisson, with a touch of Irish blood. You can strengthen these numbers by running / pfgw -tc PRPfile this will test for Fermat
Message 7 of 17 , Jan 4, 2003
--- richard_heylen wrote:
> Judging from the conjectured density of primes in this region you
> were quite lucky!

Nothing more than PNT and Poisson, with a touch of Irish blood.

You can strengthen these numbers by running
/>pfgw -tc PRPfile

this will test for "Fermat and Lucas PRP".

I don't know of any composites that pass this. Does anyone else know?

If you wanted to be even more sure you could use "Perrin
pseudoprimality test" or one simmilar, but these are not part of PFGW.

Paul
• ... 25 It s a 7-PSP and a LPSP(1,-1) If you re using the LPSP definition to include GCD(n,D)==1, as C&P do, then 377 is a 12-PSP and a LPSP(1,-1) ... Simply
Message 8 of 17 , Jan 5, 2003
--- "paulunderwooduk <paulunderwood@...>" <paulunderwood@...> wrote:
> --- richard_heylen wrote:
> > Judging from the conjectured density of primes in this region you
> > were quite lucky!
>
> Nothing more than PNT and Poisson, with a touch of Irish blood.
>
> You can strengthen these numbers by running
> />pfgw -tc PRPfile
>
> this will test for "Fermat and Lucas PRP".
>
> I don't know of any composites that pass this. Does anyone else know?

25

It's a 7-PSP and a LPSP(1,-1)

If you're using the LPSP definition to include GCD(n,D)==1, as C&P do, then

377 is a 12-PSP and a LPSP(1,-1)

> If you wanted to be even more sure you could use "Perrin
> pseudoprimality test" or one simmilar, but these are not part of PFGW.

Simply using the strong version (the 1 must be preceded by a -1) of each PRP
test you'll get rid of 95% of these jokers. There's very rarely a reason for
running a weak test rather than a strong one.

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• ... Indeed. Moreover http://groups.yahoo.com/group/primenumbers/files/pseudo/ contains *many* reasons for _not_ doing a weak Fermat + weak Lucas combination.
Message 9 of 17 , Jan 5, 2003
Phil:
> There's very rarely a reason for running
> a weak test rather than a strong one.
Indeed. Moreover
contains *many* reasons for _not_ doing a
weak Fermat + weak Lucas
combination.
David
• To be more precise http://groups.yahoo.com/group/primenumbers/files/pseudo/ contains *many* reasons for _not_ doing a strong Fermat + weak Lucas combination
Message 10 of 17 , Jan 5, 2003
To be more precise
contains *many* reasons for _not_ doing a
strong Fermat + weak Lucas
combination
with bases 2 and golden_mean
respectively.
• ... How many of them (randomness predicts 1/4) remain if a SLPRP test test is done rather than a LPRP? (and yes, I know, randomness is utterly irrelevant). Can
Message 11 of 17 , Jan 5, 2003
> To be more precise
> contains *many* reasons for _not_ doing a
> strong Fermat + weak Lucas
> combination
> with bases 2 and golden_mean
> respectively.

How many of them (randomness predicts 1/4) remain if a SLPRP test test is
done rather than a LPRP? (and yes, I know, randomness is utterly irrelevant).

Can these SLPRP's generate square roots of -1? I know that you can get square
rots from lucas sequences, but whether the particular setup for a SLPRP test
permits it I don't know. (I'm sure David, Jason, Marcel, et al. know facts
likethis off the top of their heads, I'm so ashamed!). If so, then the "sqrt
test" might drop the 1/4 to 1/8. Probably.

Phil

=====
The answer to life's mystery is simple and direct:
Sex and death. -- Ian 'Lemmy' Kilminster

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• ... Weak is it? I wonder why PFGW did not implement Baillie-PSW. Paul
Message 12 of 17 , Jan 5, 2003
> To be more precise
> contains *many* reasons for _not_ doing a
> strong Fermat + weak Lucas
> combination
> with bases 2 and golden_mean
> respectively.

Weak is it? I wonder why PFGW did not implement Baillie-PSW.

Paul
• ... I guess because then the fast PrP test would be 3 times slower. And the -tc test is stronger than B-PSW, I believe. If you have a fair pecentage of N^2-1
Message 13 of 17 , Jan 5, 2003
Paul:

> I wonder why PFGW did not implement Baillie-PSW.

I guess because then the fast PrP test would be 3 times slower.

And the -tc test is stronger than B-PSW, I believe.
If you have a fair pecentage of N^2-1 it's *very* strong.
If you have enough for BLS it's a proof.

Why should one want something intermediate between
a fast PrP and a slower-and-better-than-B-PSW test?

After all, only a fraction=O(log(sieve_depth)/log(N))
get through the fast test, so it doesn't matter that
the slow one is even better (and hence slower) than B-PSW.
[Except to Chris, who is suffering right now.]

Maybe you do not see it this way, because your log(N)
is so small. But PFGW is for finding large primes,
not small pseudoprimes.

Or have I missed something?

David
• ... No I didn t mean using B-PSW as the main PRP test! Rather I meant: why does PFGW report Fermat and Lucas PRP rather than B-PSW? Is something to do with the
Message 14 of 17 , Jan 5, 2003
> Paul:
>
> > I wonder why PFGW did not implement Baillie-PSW.
>
> I guess because then the fast PrP test would be 3 times slower.
>

No I didn't mean using B-PSW as the main PRP test! Rather I meant:
why does PFGW report Fermat and Lucas PRP rather than B-PSW? Is
something to do with the calculation of N^2-1?

> And the -tc test is stronger than B-PSW, I believe.
> If you have a fair pecentage of N^2-1 it's *very* strong.

Can someone construct such a N^2-1 factored composite number?

Paul
• ... We can t make even a B-PSW pseudoprime to order, though with huge processing power there is an explicit construction which has a very high probability of
Message 15 of 17 , Jan 5, 2003
> Can someone construct such a N^2-1 factored composite number?
We can't make even a B-PSW pseudoprime to order,
though with huge processing power there is an explicit
construction which has a very high probability of suceeding:
http://www.d.umn.edu/~jgreene/baillie/Baillie-PSW.html
which must be the hardest way to win \$640 ever devised.
These animals are simply "out there"; caging one is very hard.
Your message has been successfully submitted and would be delivered to recipients shortly.