The Search For First Proth Prime (SNoB Problem)

Why SNoB?

In April 2020, "JeppeSN" suggested on PrimeGrid forum to extend Sierpiński problem to true Proth primes.

Although we often call any number in form k*b^n+1 a Proth number, strict definition of Proth numbers requires 2^n > k. For classic Sierpiński problem, it does not matter. For example, prime number 12743*2^9+1 is OK to eliminate k=12743 from any of Sierpiński conjectures. But this is not a Proth prime because condition 2^n > k is not met (512 < 12743).

After initial removal of small (up to n=100K) and known primes, we had... exactly 17 k’s left to test! The same number as in original Sierpiński "Seventeen-or-Bust" ("SoB") project. Eventually we started to call our project as "Seventeen New or Bust", or, in short form, "A SNoB project". Probably it was a joke first, but name was accepted by community and became official project name.

The project has three phases, two of them corresponds to existing Sierpiński projects. Their state and findings are posted below. All found primes also were tested for Fermat divisors (currently no divisors were found).

Pure SNoB

This phase corresponds to original Seventeen-Or-Bust project, testing all k < 78557. Having 17 candidates at start, 10 candidates were quickly eliminated by manual testing.

K	Prime	Digits	Tested depth (N)
22249	22249*2^408602+1	123006	Up to prime Found by gd_barnes in 2010, see Note 1
23873	23873*2^136733+1	41166	Up to prime
28831	28831*2^204580+1	61590	Up to prime
35461	35461*2^129820+1	39085	Up to prime
39527	39527*2^143055+1	43069	Up to prime
44243	44243*2^440969+1	132750	Up to prime
54953	54953*2^622065+1	187265	Up to prime
57377	57377*2^447439+1	134698	Up to prime
68221	68221*2^200944+1	60496	Up to prime
77297	77297*2^118499+1	35677	Up to prime

Note 1: this prime was reported by gd_barnes in September 2010, but he used an alternative notation 88996*2^408600+1, so the prime was left unnoticed and was discovered again in this project.

7 remaning candidates were tested on this server using LLR2, which led to discovery of two new primes. The search was stopped at 10M because tasks length started to grow significantly. Interesting that there is a big gap - last prime was found near 2.7M, and there are no primes between 2.7M and 10M.

K	Prime	Digits	Tested depth (N)
23971	-		10M
45323	-		10M
50777	-		10M
50873	-		10M
68633	68633*2^2715609+1 (T5K link)	817485	Up to prime
71657	71657*2^1146175+1	345038	Up to prime
76877	-		10M

Extra SNoB

Extra SNoB (or SNoB-Extended) is similar to Extended Sierpinski Problem. It includes all K between first and second Sierpinski numbers (from 78557 to 271129). After removal of known T5K primes and quick testing up to 100K, 19 sequences left. They were tested manually using LLR2 up to N = 1M, removing 13 sequences.

K	Prime	Digits	Tested depth (N)
90227	90227*2^138543+1	41711	Up to prime
97159	97159*2^523526+1	157603	Up to prime
130819	130819*2^114806+1	34566	Up to prime
145459	145459*2^272314+1	81980	420238 (second prime, Note 2)
160817	160817*2^756599+1	227765	Up to prime
165049	165049*2^111914+1	33695	Up to prime
165541	165541*2^627460+1	188890	Up to prime
171499	171499*2^200746+1	60436	Up to prime
179147	179147*2^132227+1	39810	Up to prime
192023	192023*2^507229+1	152697	Up to prime
201031	201031*2^170260+1	51259	Up to prime
221989	221989*2^351586+1	105844	Up to prime
248131	248131*2^204924+1	61694	Up to prime

Note 2: These tests were run by few people in parallel using same K but different ranges, so two primes were found for K = 145459; second one is 145459*2^420238+1.

No further testing took place yet for 6 remaining sequences:

K	Prime	Tested depth (N)
83599	-	2M
96407	-	1.5M
97667	-	2M
129769	-	2M
149693	-	2M
225803	-	1.5M

MEGA SNoB

MEGA SNoB project includes all K up to 1M. Since definition of Proth prime is 2^n > k, it makes sense to test everything not exactly up to 1000000, but up to 2²⁰ = 1048576.

There were 290 sequences after removal of known T5K primes and quick testing up to 100K. Manual testing up to 500K removed 75 sequences (215 remains). Below is a list of found primes (testing depth for these k was up to prime).

K	Prime	Digits	K	Prime	Digits	K	Prime	Digits
301607	301607*2^229647+1	69137	517651	517651*2^204528+1	61575	828287	828287*2^483751+1	145630
308423	308423*2^395337+1	119014	525173	525173*2^159553+1	48036	836543	836543*2^290465+1	87445
319531	319531*2^212252+1	63900	548869	548869*2^304442+1	91652	845899	845899*2^338386+1	101871
331247	331247*2^374775+1	112825	554573	554573*2^305373+1	91933	846857	846857*2^453343+1	136476
333227	333227*2^214471+1	64568	558991	558991*2^188204+1	56661	868523	868523*2^109737+1	33041
346223	346223*2^373085+1	112316	575539	575539*2^431950+1	130036	872177	872177*2^214575+1	64600
351199	351199*2^149618+1	45046	584971	584971*2^266656+1	80278	882077	882077*2^478755+1	144126
353477	353477*2^237219+1	71416	588083	588083*2^244477+1	73601	888499	888499*2^460922+1	138758
357017	357017*2^332367+1	100058	590329	590329*2^155334+1	46766	892249	892249*2^141518+1	42608
371791	371791*2^144840+1	43607	656063	656063*2^133969+1	40335	907043	907043*2^305293+1	91909
374149	374149*2^256202+1	77131	693467	693467*2^112027+1	33730	911123	911123*2^479981+1	144495
375121	375121*2^132268+1	39823	704507	704507*2^321379+1	96751	924683	924683*2^421877+1	127004
383717	383717*2^325171+1	97892	710153	710153*2^342801+1	103200	944011	944011*2^372216+1	112055
393497	393497*2^255283+1	76854	714229	714229*2^111318+1	33516	960301	960301*2^430616+1	129635
396203	396203*2^480729+1	144720	722207	722207*2^111831+1	33671	1003441	1003441*2^191044+1	57516
397309	397309*2^296070+1	89132	722419	722419*2^150414+1	45285	1013183	1013183*2^136521+1	41103
399617	399617*2^340955+1	102644	752303	752303*2^146405+1	44079	1015727	1015727*2^193231+1	58175
412501	412501*2^279708+1	84207	759653	759653*2^154085+1	46391	1024609	1024609*2^123754+1	37260
416659	416659*2^412866+1	124291	759947	759947*2^108487+1	32664	1028513	1028513*2^164921+1	49653
429931	429931*2^382776+1	115233	762769	762769*2^188586+1	56776	1034281	1034281*2^180464+1	54332
459263	459263*2^137237+1	41319	768773	768773*2^302509+1	91071	1034599	1034599*2^233258+1	70224
467417	467417*2^130927+1	39419	773447	773447*2^115035+1	34635	1037753	1037753*2^365805+1	110125
479657	479657*2^296367+1	89222	774977	774977*2^261235+1	78646	1042193	1042193*2^164893+1	49644
488341	488341*2^466940+1	140569	802231	802231*2^101528+1	30569	1043237	1043237*2^371971+1	111981
495979	495979*2^480286+1	144587	812117	812117*2^141051+1	42467	1047661	1047661*2^382784+1	115236

Remaining 215 sequences were tested up to 1M. This work was finished in March 2022, finding 40 primes.

K	Prime	Digits	K	Prime	Digits	K	Prime	Digits
285473	285473*2^530921+1	159829	619013	619013*2^849281+1	255665	899449	899449*2^981210+1	295380
344363	344363*2^603009+1	181530	624511	624511*2^962636+1	289789	923177	923177*2^611483+1	184081
392479	392479*2^958886+1	288660	653063	653063*2^899301+1	270723	923359	923359*2^541446+1	162998
420113	420113*2^524009+1	157749	665423	665423*2^566441+1	170522	984173	984173*2^872129+1	262543
428657	428657*2^720223+1	216815	670309	670309*2^520410+1	156665	989147	989147*2^635919+1	191437
441923	441923*2^774725+1	233222	680851	680851*2^741248+1	223144	992731	992731*2^731740+1	220282
481727	481727*2^883059+1	265833	701357	701357*2^532979+1	160449	1010693	1010693*2^560473+1	168726
498781	498781*2^557856+1	167938	724351	724351*2^675612+1	203386	1013657	1013657*2^922163+1	277605
499729	499729*2^725234+1	218323	735679	735679*2^885398+1	266538	1016693	1016693*2^963829+1	290148
504769	504769*2^839566+1	252741	743357	743357*2^860491+1	259040	1028431	1028431*2^556356+1	167486
506749	506749*2^574746+1	173022	749971	749971*2^843268+1	253855	1045187	1045187*2^508967+1	153221
510893	510893*2^556521+1	167536	750083	750083*2^684961+1	206200	1048099	1048099*2^605090+1	182157
609769	609769*2^879034+1	264622	761749	761749*2^716354+1	215650
615151	615151*2^800316+1	240925	851963	851963*2^558637+1	168173

No organized testing took place yet for 175 remaining sequences. Some sequences were tested further manually:

Between July 2023 and September 2023, testing up to 1.5M found 23 primes.

If not specified, current tested depth N = 1.5M.

K	Prime	Digits	Depth	K	Prime	Digits	Depth	K	Prime	Digits	Depth
272341	-		2.0M	536839	-			769343	769343*2^1230661+1	370472	Up to prime
273679	273679*2^1052058+1	316707	Up to prime	538943	-		2.0M	772411	-		2.0M
274699	-		2.0M	545401	-		2.0M	777559	-		2.0M
279361	279361*2^1613712+1	485782	Up to prime	545971	545971*2^1082956+1	326008	1.103M	785153	-		2.0M
279767	-		2.0M	548033	-		2.0M	794867	794867*2^1702787+1	512596	Up to prime
285601	-		2.0M	553159	-		2.0M	795983	-		2.0M
286037	-		2.0M	559789	559789*2^1030634+1	310258	Up to prime	802613	-
287393	-		2.0M	561769	-			818327	-		2.0M
289171	-			566569	-			819437	-		2.0M
294181	-		2.0M	571471	-		2.0M	823969	-		2.0M
305063	-			580831	-			826201	-		2.0M
305147	305147*2^1030527+1	310226	Up to prime	583189	-		2.0M	829643	-		2.0M
310339	-		2.0M	588317	-		2.0M	836687	-		2.0M
311573	-		2.0M	589021	-		2.0M	843079	-		2.0M
312121	312121*2^1109856+1	334106	Up to prime	590033	-		2.0M	844457	-
340441	-		2.0M	599003	599003*2^1828141+1	550332	Up to prime	846347	-		2.0M
340759	-			599011	-		2.0M	852019	852019*2^1763242+1	530795	Up to prime
351167	-		2.0M	599513	599513*2^1282453+1	386063	Up to prime	856043	-		2.0M
356359	-		2.0M	603767	-			858079	-		2.0M
357271	357271*2^1370332+1	412517	Up to prime	606199	-		2.0M	860117	-		2.0M
359933	-		2.0M	609227	-		2.0M	867151	867151*2^1952104+1 (T5K link)	587648	Up to prime
360331	-		2.0M	609737	-			867271	-
362881	-		2.0M	616909	616909*2^1899194+1 (T5K link)	571721	Up to prime	868339	-		2.0M
363917	363917*2^1655731+1	498431	Up to prime	626303	-		2.0M	870061	-		2.0M
365221	365221*2^1767932+1	532207	Up to prime	630121	-		2.0M	872119	-		2.0M
365867	-			632659	-			878029	-		2.0M
366953	-		2.0M	632663	-		2.0M	879049	879049*2^1174370+1	353527	Up to prime
368299	-			633481	-		2.0M	879497	-		2.0M
381799	-		2.0M	641327	-		2.0M	881537	-
382247	-		2.0M	648751	-		2.0M	884723	-		2.0M
392033	-		2.0M	651857	-			887153	-		2.0M
393287	-		2.0M	654499	-			894409	-
400613	-		2.0M	656123	-		2.0M	894827	-
412591	-		2.0M	656753	-		2.0M	895579	-		2.0M
418591	-		2.0M	664639	-			901067	-
433457	-		2.0M	666409	666409*2^1083222+1	326089	Up to prime	902191	902191*2^1138968+1	342870	Up to prime
447061	447061*2^1206128+1	363087	Up to prime	667861	-		2.0M	902453	902453*2^1050893+1	316357	Up to prime
451351	-		2.0M	674477	-		2.0M	904489	-		2.0M
452119	-		2.0M	678173	-		2.0M	925907	-		2.0M
452191	-			681413	-		2.0M	926371	-		2.0M
452567	-		2.0M	684617	684617*2^1098123+1	330574	Up to prime	935723	-
457217	-		2.0M	694973	-		2.0M	946879	-
462829	-		2.0M	702707	702707*2^1165279+1	350790	Up to prime	957977	-		2.0M
473543	-		2.0M	703643	-			961099	-		2.0M
473567	-		2.0M	705983	-			964673	-		2.0M
474323	-			711833	-		2.0M	968491	-		2.0M
479783	-		2.0M	714563	-			971389	-
484763	-		2.0M	718849	-		2.0M	972739	-
491147	-		2.0M	721141	-			979039	-		2.0M
499337	-		2.0M	721397	-		2.0M	983027	-		2.0M
499561	499561*2^1759204+1	529579	Up to prime	734147	734147*2^1047447+1	315319	Up to prime	1000313	-		2.0M
501107	501107*2^1058835+1	318747	Up to prime	734177	734177*2^1180107+1	355254	Up to prime	1001419	1001419*2^1675042+1	504244	Up to prime
502613	-		2.0M	736249	-		2.0M	1004987	-
504061	504061*2^1714720+1	516188	Up to prime	749447	749447*2^1036639+1	312066	Up to prime	1013689	-		2.0M
515357	-		2.0M	751999	751999*2^1589870+1	478605	Up to prime	1034809	1034809*2^1077230+1	324285	Up to prime
517913	-		2.0M	757343	-		2.0M	1039127	1039127*2^1193367+1	359246	Up to prime
518671	518671*2^1157008+1	348300	Up to prime	760583	760583*2^1433845+1	431637	Up to prime	1040297	-		2.0M
520471	-			766531	-		2.0M
532703	-		2.0M	766801	-