prime gaps are attractive upper bounds for Eratosthenes's prime sieve because you get a bit extra at the end without having to do another iteration. for example, using primes only up to 7 seems like it would be sufficient only for sieving to 49, but it actually works for sieving up to 120 because of the prime gap between 7 and 11.
below, we list record and tied-for-record prime gaps.
primes up to 120 is an easy exercise on graph paper. primes up to 16128 seems doable by hand. the output of the first could be used for the second, a neat coincidence.
q=prime(1); gap=0; forprime(p=3, +oo, if(p-q>=gap, gap=p-q; print("strictlynextprime("q")^2 - 1 = "p"^2 - 1 = ",p^2-1)); q=p)
strictlynextprime(7)^2 - 1 = 11^2 - 1 = 120
strictlynextprime(13)^2 - 1 = 17^2 - 1 = 288
strictlynextprime(19)^2 - 1 = 23^2 - 1 = 528
strictlynextprime(23)^2 - 1 = 29^2 - 1 = 840
strictlynextprime(31)^2 - 1 = 37^2 - 1 = 1368
strictlynextprime(47)^2 - 1 = 53^2 - 1 = 2808
strictlynextprime(53)^2 - 1 = 59^2 - 1 = 3480
strictlynextprime(61)^2 - 1 = 67^2 - 1 = 4488
strictlynextprime(73)^2 - 1 = 79^2 - 1 = 6240
strictlynextprime(83)^2 - 1 = 89^2 - 1 = 7920
strictlynextprime(89)^2 - 1 = 97^2 - 1 = 9408
strictlynextprime(113)^2 - 1 = 127^2 - 1 = 16128
strictlynextprime(293)^2 - 1 = 307^2 - 1 = 94248
strictlynextprime(317)^2 - 1 = 331^2 - 1 = 109560
strictlynextprime(523)^2 - 1 = 541^2 - 1 = 292680
strictlynextprime(887)^2 - 1 = 907^2 - 1 = 822648
strictlynextprime(1129)^2 - 1 = 1151^2 - 1 = 1324800
strictlynextprime(1327)^2 - 1 = 1361^2 - 1 = 1852320
strictlynextprime(8467)^2 - 1 = 8501^2 - 1 = 72267000
strictlynextprime(9551)^2 - 1 = 9587^2 - 1 = 91910568
strictlynextprime(12853)^2 - 1 = 12889^2 - 1 = 166126320
strictlynextprime(14107)^2 - 1 = 14143^2 - 1 = 200024448
strictlynextprime(15683)^2 - 1 = 15727^2 - 1 = 247338528
strictlynextprime(19609)^2 - 1 = 19661^2 - 1 = 386554920
strictlynextprime(25471)^2 - 1 = 25523^2 - 1 = 651423528
strictlynextprime(31397)^2 - 1 = 31469^2 - 1 = 990297960
strictlynextprime(155921)^2 - 1 = 156007^2 - 1 = 24338184048
strictlynextprime(338033)^2 - 1 = 338119^2 - 1 = 114324458160
strictlynextprime(360653)^2 - 1 = 360749^2 - 1 = 130139841000
strictlynextprime(370261)^2 - 1 = 370373^2 - 1 = 137176159128
strictlynextprime(492113)^2 - 1 = 492227^2 - 1 = 242287419528
strictlynextprime(1349533)^2 - 1 = 1349651^2 - 1 = 1821557821800
strictlynextprime(1357201)^2 - 1 = 1357333^2 - 1 = 1842352872888
strictlynextprime(1561919)^2 - 1 = 1562051^2 - 1 = 2440003326600
strictlynextprime(2010733)^2 - 1 = 2010881^2 - 1 = 4043642396160
strictlynextprime(4652353)^2 - 1 = 4652507^2 - 1 = 21645821385048
strictlynextprime(11113933)^2 - 1 = 11114087^2 - 1 = 123522929843568
strictlynextprime(15203977)^2 - 1 = 15204131^2 - 1 = 231165599465160
strictlynextprime(17051707)^2 - 1 = 17051887^2 - 1 = 290766850260768
strictlynextprime(20831323)^2 - 1 = 20831533^2 - 1 = 433952767130088
strictlynextprime(47326693)^2 - 1 = 47326913^2 - 1 = 2239836694109568
strictlynextprime(122164747)^2 - 1 = 122164969^2 - 1 = 14924279650770960
strictlynextprime(189695659)^2 - 1 = 189695893^2 - 1 = 35984531821067448
strictlynextprime(191912783)^2 - 1 = 191913031^2 - 1 = 36830611467606960
strictlynextprime(387096133)^2 - 1 = 387096383^2 - 1 = 149843609731682688
strictlynextprime(428045491)^2 - 1 = 428045741^2 - 1 = 183223156388239080
strictlynextprime(436273009)^2 - 1 = 436273291^2 - 1 = 190334384439970680
strictlynextprime(1294268491)^2 - 1 = 1294268779^2 - 1 = 1675131672294150840
strictlynextprime(1453168141)^2 - 1 = 1453168433^2 - 1 = 2111698494667675488
strictlynextprime(2300942549)^2 - 1 = 2300942869^2 - 1 = 5294338086401951160
strictlynextprime(3842610773)^2 - 1 = 3842611109^2 - 1 = 14765660135010209880
strictlynextprime(4275912661)^2 - 1 = 4275912997^2 - 1 = 18283431957913522008
strictlynextprime(4302407359)^2 - 1 = 4302407713^2 - 1 = 18510712128881890368
strictlynextprime(10726904659)^2 - 1 = 10726905041^2 - 1 = 115066491758631211680
strictlynextprime(20678048297)^2 - 1 = 20678048681^2 - 1 = 427581697253805839760
OEIS A134266
No comments:
Post a Comment