-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathbenchmark.sagews
254 lines (199 loc) · 53.6 KB
/
benchmark.sagews
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
︠513b474e-3b15-490f-8cdc-919d79e0d2a2︠
%md
# Benchmark
Here are the values used to benchmark the factorization functions
︡22802245-47c6-4c58-b697-2f275b7d035d︡{"done":true,"md":"# Benchmark\nHere are the values used to benchmark the factorization functions"}
︠037831ee-c983-41bf-a32a-637f8adb3794si︠
# This cell needs to be executed
iterations = 10
smallPrimes = ("small primes", [(2, [(481, [1, 13, 37])]), (3, [(31093, [1, 31, 17, 59])]), (4, [(1213045, [1, 37, 5, 83, 79])]), (5, [(15001613, [1, 31, 37, 29, 11, 41])]), (6, [(3429238769, [1, 47, 97, 59, 11, 19, 61])]), (7, [(206397809105, [1, 37, 79, 5, 53, 41, 67, 97])]), (8, [(7311461300687, [1, 41, 23, 73, 41, 59, 83, 23, 23])]), (9, [(472213574958521, [1, 41, 53, 37, 47, 61, 11, 71, 61, 43])]), (10, [(3443187949695, [1, 29, 43, 83, 5, 73, 41, 13, 3, 19, 3])]), (11, [(309773094336642695, [1, 5, 97, 11, 31, 83, 97, 31, 89, 43, 53, 37])]), (12, [(62263002262083735, [1, 47, 83, 17, 41, 59, 59, 43, 3, 7, 47, 31, 5])]), (13, [(666536544405580303, [1, 31, 23, 7, 47, 23, 67, 37, 37, 19, 13, 41, 19, 7])]), (14, [(56142059257389353853, [1, 3, 37, 11, 37, 19, 97, 11, 31, 53, 31, 67, 11, 71, 23])]), (15, [(3173389011480824657829, [1, 3, 79, 59, 53, 31, 7, 23, 43, 73, 11, 71, 3, 71, 31, 53])]), (16, [(15863359163742166197825, [1, 37, 3, 19, 61, 5, 11, 79, 79, 67, 3, 71, 5, 71, 97, 43, 17])]), (17, [(3839358256056932827602345, [1, 67, 17, 29, 19, 53, 41, 19, 19, 37, 73, 89, 13, 5, 53, 3, 73, 43])]), (18, [(18710317739887802052740556555, [1, 97, 89, 89, 83, 59, 5, 79, 59, 73, 13, 11, 31, 31, 29, 3, 89, 67, 41])]), (19, [(155903632515187552359018988575, [1, 97, 43, 47, 89, 97, 11, 73, 73, 61, 3, 37, 29, 61, 73, 5, 5, 67, 29, 37])]), (20, [(53620794966136160429097776631, [1, 23, 3, 79, 23, 43, 89, 61, 59, 3, 23, 71, 41, 97, 13, 11, 17, 37, 29, 47, 13])])])
mediumPrimes = ("medium primes", [(2, [(9505247, [1, 1427, 6661])]), (3, [(112377214483, [1, 4451, 7607, 3319])]), (4, [(113332156404307, [1, 4007, 3539, 2903, 2753])]), (5, [(4298836929253947781, [1, 8429, 7417, 5039, 1867, 7309])]), (6, [(11038759956959519253043, [1, 4909, 7307, 1597, 3733, 7243, 7127])]), (7, [(353271001154438218427229539, [1, 8167, 2687, 5483, 7253, 5807, 7127, 9781])]), (8, [(858069121139663326922589137543, [1, 9137, 9463, 3967, 8737, 4349, 5003, 2243, 5867])]), (9, [(131563435713374902721110800493303, [1, 5923, 6907, 8317, 1151, 1787, 5479, 9929, 2287, 1511])]), (10, [(2528123531806453766378415166939107671, [1, 9749, 2069, 5879, 8377, 2683, 2267, 4919, 3637, 4703, 4973])]), (11, [(98861961050577963648512453904444483679, [1, 1283, 2203, 9533, 1303, 2239, 1523, 5009, 1429, 4253, 2791, 9719])]), (12, [(3699719069641057612942949836474926656811572189, [1, 9133, 9967, 5879, 6547, 8929, 2351, 8681, 6857, 9719, 7583, 3461, 3313])]), (13, [(9297901936182093694009454599759344878967851169253, [1, 3947, 8599, 3109, 4999, 5581, 8629, 5953, 8069, 6829, 9677, 5197, 8059, 2753])]), (14, [(2987283285112052856777637490953875990300408162464831, [1, 1523, 7043, 1889, 7507, 6133, 3253, 3797, 1877, 3463, 7253, 9281, 7243, 8837, 9257])]), (15, [(14046255291904838561381033780082793879910682609073503319, [1, 2003, 9479, 8677, 4733, 1279, 3947, 5431, 9421, 9059, 9377, 4817, 1663, 3221, 8111, 3923])]), (16, [(1672833210619559517657260567204379601678267615743624567961, [1, 9883, 6067, 1559, 1009, 7069, 2213, 8713, 1601, 9491, 7369, 1327, 6701, 3359, 6871, 2039, 2777])]), (17, [(212010140415468603762770884867770164189873990478028538128651543, [1, 7757, 1721, 9343, 2521, 6793, 8017, 8117, 2879, 6491, 3637, 3319, 3677, 5711, 7681, 3433, 2087, 5851])]), (18, [(29763544558056708909351290167863189328280637881745015028766377567, [1, 3793, 3323, 7841, 9949, 1181, 6659, 5171, 2011, 1861, 3547, 2887, 2131, 4801, 2243, 2141, 5843, 9349, 7237])]), (19, [(183733102700898942618853672482178977569632673473846394890208044869833, [1, 1861, 6997, 1459, 7103, 8191, 6883, 1499, 1123, 2069, 8563, 4091, 7699, 4027, 5813, 2099, 8803, 5821, 2753, 3709])]), (20, [(4315581732420458239176904986420389625324862838223258879737740116751534309, [1, 4933, 9473, 2753, 7949, 1223, 1213, 1447, 9689, 2647, 7177, 4421, 7883, 7883, 4673, 7253, 4787, 2713, 8929, 2693, 3673])])])
largePrimes = ("large primes", [(2, [(4063375517, [1, 78439, 51803])]), (3, [(522742080565357, [1, 71167, 82051, 89521])]), (4, [(52187387971275982093, [1, 89753, 95717, 64693, 93901])]), (5, [(1162300682477934084344741, [1, 65183, 73883, 57397, 78803, 53359])]), (6, [(188904463700616439184603915519, [1, 77339, 67523, 99577, 59333, 64577, 94811])]), (7, [(10382597739368109104150090934175379, [1, 88321, 75787, 62417, 55117, 56179, 83399, 96233])]), (8, [(2236854499510418655753593501324101562419, [1, 91433, 96221, 73477, 94543, 80489, 73063, 67619, 92041])]), (9, [(35042439864356271632594896096225381140303727, [1, 93077, 63391, 71261, 50909, 67979, 75307, 54403, 61007, 96353])]), (10, [(9938019912957784649301000808068798240941672975269, [1, 94793, 50909, 88667, 75377, 74231, 75553, 99571, 86509, 89959, 70901])]), (11, [(187109892613625880027947942540002116725379107367853319, [1, 53611, 60659, 85313, 88609, 71089, 75133, 53267, 66851, 99041, 80603, 50129])]), (12, [(49161767109869991125387613590249904971687586373477597553749, [1, 88211, 97073, 79111, 80777, 51859, 99767, 84869, 80963, 75937, 91369, 52027, 70009])]), (13, [(986007145146192555084662271727905179607731398501077146686982027, [1, 88241, 72559, 86239, 92459, 57097, 63647, 96167, 54541, 67219, 70439, 50123, 66083, 64609])]), (14, [(122656733660163473018814025422928703405374994772383697825517039916327, [1, 68389, 86539, 63493, 56377, 61001, 60217, 85361, 58393, 65701, 99251, 94049, 70289, 77711, 94397])]), (15, [(7842053712205825701754260824788620754149912403029793155702700015604989373, [1, 81101, 82387, 92399, 88903, 67567, 60037, 96797, 60161, 58229, 58243, 76333, 84181, 67927, 58403, 69959])]), (16, [(414983958423876613281406476811736161578168944722930828312908133102632845752703, [1, 92083, 56477, 94573, 67187, 83177, 88471, 52951, 55579, 71597, 66179, 59671, 59729, 69481, 97583, 54623, 92717])]), (17, [(53002745697331794043197162487408577583597259117156412795445234494802005531541655757, [1, 51949, 81689, 71089, 81737, 60659, 93179, 70489, 90547, 62189, 92647, 64123, 75239, 90841, 88129, 74653, 57119, 62791])]), (18, [(2774325281122485998802780772219788618613994707680106838689326624193111749855341451994853, [1, 62081, 94229, 70313, 50513, 69247, 67531, 74903, 84827, 75037, 57697, 58789, 78779, 50909, 88819, 99923, 90353, 59627, 92077])]), (19, [(81814093803623318906242340014181655977264794640309240515571248892045623493330471152004211349, [1, 63629, 76597, 60761, 85223, 63611, 82039, 75431, 52501, 77351, 54547, 60139, 80387, 51721, 59093, 65537, 66587, 81817, 91961, 76631])]), (20, [(4759420676774002917027080074804196749925026162216764903500438803531064867662815998548224047575111, [1, 51193, 63617, 74827, 77239, 65761, 71011, 82613, 77719, 99709, 85213, 95959, 54787, 56503, 53503, 61553, 60689, 67033, 64513, 58831, 65713])])])
largerPrimes = ('Larger primes', [(2, [(187186702751, [1, 590377, 317063])]), (3, [(227610837550458559, [1, 345461, 887483, 742393])]), (4, [(70258793277571237647233, [1, 899981, 280607, 312353, 890683])]), (5, [(28721678110719749295143472251, [1, 252323, 322589, 562259, 826169, 759623])]), (6, [(16584959865789562307773297581668989, [1, 526199, 772097, 347519, 284857, 826759, 498779])]), (7, [(40135231725177170651266451927317370040017, [1, 689917, 363037, 462571, 805559, 561367, 823201, 930571])]), (8, [(13543477157075511779696540916677807232136281983, [1, 369841, 369079, 898481, 593171, 673613, 333197, 874127, 948901])]), (9, [(21868276789400720715203792286586485297210926281696241, [1, 508867, 666031, 911839, 521657, 319981, 592597, 776357, 947389, 972611])]), (10, [(3398638008982066688531884463264580936942051180990210108323, [1, 655243, 756373, 805219, 655859, 563197, 592087, 467101, 333331, 364031, 687023])]), (11, [(9136943238414668122038298815310911346194279867410940342650742671, [1, 741457, 386333, 423887, 741869, 752281, 938323, 933847, 548567, 636953, 986351, 446477])]), (12, [(38071366054007302601960554011850986602984984747338895665946437878377453, [1, 779189, 507691, 750961, 875417, 967427, 371251, 857737, 943073, 943363, 895087, 761861, 783283])]), (13, [(368625134734142995123626326808047577046599110832420111833822347712566666853, [1, 409063, 634079, 260263, 620887, 744407, 440183, 971171, 755737, 654679, 556093, 968593, 293483, 353359])]), (14, [(350789352401366415305072032960473921257900088976055701075698491956756257404655481, [1, 746483, 585587, 530851, 555349, 751259, 378949, 404843, 937823, 447683, 444817, 511289, 644291, 603731, 635879])]), (15, [(431463623920866689805584050956253221308032437458060677109830929906624804391812275410793, [1, 533747, 682333, 828067, 484751, 446261, 578687, 977147, 283831, 564979, 690163, 836863, 327017, 693403, 794153, 701257])]), (16, [(3090895415152262211627476518158103729565126064320269607944002601270807904266490336040532453091, [1, 729761, 596009, 627481, 812963, 576757, 711679, 825983, 955613, 911593, 587959, 700759, 767623, 268979, 651821, 858763, 990523])]), (17, [(1881182900515253077657544850252234921978522056443095815660055032303071363462608086772712619979929, [1, 765283, 360959, 399181, 468653, 287849, 481297, 382351, 711727, 261917, 846983, 754463, 346711, 346217, 541201, 990377, 338027, 265261])]), (18, [(23169284855147410245104557782459930672656640958302012768111347982308836202807150642723443947428384991983, [1, 428899, 979543, 314243, 947819, 441121, 954277, 304709, 620717, 427877, 399689, 415343, 289181, 985063, 883429, 840979, 488011, 665153, 476587])]), (19, [(14148962297868150427488880128423453856260378948237916062898523907220089968114112210934057887773724022523805637, [1, 289249, 679417, 535481, 947539, 832757, 934537, 424829, 280451, 990893, 300319, 404321, 384547, 424223, 340387, 624097, 839207, 793999, 901717, 610837])]), (20, [(729883933457870363432152113700293245237626872643614401017049987282050216103044544786654875010234935256140803954547, [1, 704321, 342799, 581447, 842249, 257837, 938219, 255349, 266009, 265709, 725341, 452033, 692717, 464923, 648007, 795307, 476659, 314399, 367687, 518579, 909203])])])
largestPrimes = ("largest primes", [(2, [(156522823147269816284598631312951810612882615746935161032701, [1, 272431619873581157551105550911, 574539854147262640021933661891])]), (3, [(33874806091130475009235697120079470280226688813077808889362612187330734249556669208421939, [1, 155903459436988767034958394683, 785575136929393571457349360969, 276588001275352182296868615457])])])
print "Stored number suite - re run if needed"
︡aeb767af-8c05-4f4f-ba2a-3e2dd53bc072︡{"stdout":"Stored number suite - re run if needed\n"}︡{"done":true}︡
︠18531ca3-d578-4c3c-91c6-d6573a15ee4csi︠
smallClosePrimes = ('Small close primes', [(2, [(187, [1, 11, 17]), (221, [1, 13, 17])]), (3, [(1463, [1, 11, 19, 7]), (1183, [1, 13, 13, 7])]), (4, [(23023, [1, 11, 23, 7, 13]), (18515, [1, 5, 23, 7, 23])]), (5, [(161733, [1, 11, 13, 13, 29, 3]), (252655, [1, 5, 23, 13, 13, 13])]), (6, [(1154725, [1, 5, 13, 5, 17, 11, 19]), (955695, [1, 5, 29, 13, 13, 3, 13])]), (7, [(7743087, [1, 3, 31, 11, 29, 3, 29, 3]), (40602639, [1, 11, 29, 11, 19, 7, 29, 3])]), (8, [(107279613, [1, 3, 23, 3, 23, 7, 37, 3, 29]), (283487325, [1, 3, 17, 11, 41, 5, 17, 5, 29])]), (9, [(935717625, [1, 5, 43, 5, 29, 3, 23, 3, 29, 5]), (878332455, [1, 7, 17, 5, 31, 11, 13, 3, 37, 3])]), (10, [(24451456575, [1, 3, 17, 7, 13, 5, 43, 13, 29, 5, 13]), (1748802168425, [1, 13, 41, 5, 47, 13, 41, 5, 31, 13, 13])]), (11, [(6148592793, [1, 3, 19, 3, 31, 3, 19, 7, 19, 3, 17, 3]), (433954018575, [1, 3, 29, 5, 23, 11, 47, 5, 47, 7, 17, 3])]), (12, [(2336441234985, [1, 13, 37, 5, 19, 11, 13, 3, 41, 3, 19, 3, 17]), (6169110180975, [1, 3, 41, 3, 29, 7, 31, 5, 19, 7, 47, 5, 17])]), (13, [(19600594410375, [1, 5, 29, 3, 37, 11, 29, 5, 19, 3, 47, 5, 19, 3]), (27464992644375, [1, 3, 13, 11, 47, 5, 13, 5, 29, 3, 47, 5, 41, 5])]), (14, [(979848317369025, [1, 5, 23, 3, 59, 5, 17, 13, 59, 3, 23, 3, 29, 3, 41]), (16313742837926625, [1, 5, 23, 13, 61, 5, 53, 3, 31, 5, 43, 7, 53, 7, 13])]), (15, [(276612138433767825, [1, 3, 41, 13, 67, 3, 67, 5, 41, 3, 53, 13, 43, 5, 47, 3]), (480388899282435, [1, 11, 29, 3, 29, 3, 31, 5, 13, 3, 29, 3, 23, 3, 53, 3])]), (16, [(13042072935932625, [1, 3, 31, 5, 23, 3, 31, 3, 19, 3, 31, 3, 13, 5, 43, 5, 59]), (382555146521019375, [1, 3, 29, 5, 61, 3, 71, 3, 23, 5, 61, 5, 19, 3, 37, 5, 61])]), (17, [(3312499880682759375, [1, 5, 19, 3, 47, 5, 47, 5, 29, 7, 79, 3, 73, 3, 47, 5, 17, 5]), (1706485929231344625, [1, 13, 67, 5, 43, 5, 53, 3, 19, 3, 47, 3, 17, 3, 17, 7, 47, 5])]), (18, [(1174450948827771103125, [1, 5, 31, 3, 23, 5, 13, 5, 23, 7, 79, 5, 59, 5, 19, 13, 71, 13, 79]), (201675564824001357375, [1, 5, 31, 13, 19, 3, 67, 5, 37, 5, 61, 3, 23, 3, 71, 13, 13, 11, 17])]), (19, [(2896784440836584878125, [1, 5, 73, 5, 67, 5, 53, 5, 23, 13, 41, 7, 73, 5, 17, 3, 41, 7, 13, 3]), (1890142883084170567125, [1, 3, 67, 3, 13, 5, 29, 3, 79, 3, 47, 3, 79, 13, 61, 7, 17, 5, 89, 5])]), (20, [(65022163146983219653125, [1, 5, 43, 5, 59, 3, 61, 3, 97, 5, 59, 13, 31, 3, 83, 3, 29, 5, 23, 5, 13]), (32369441131223583393825, [1, 5, 29, 3, 97, 13, 19, 3, 41, 3, 71, 3, 53, 3, 37, 7, 17, 3, 53, 5, 71])]), (2, [(961, [1, 31, 31]), (1147, [1, 31, 37])]), (3, [(33263, [1, 29, 37, 31]), (27869, [1, 31, 31, 29])]), (4, [(494209, [1, 19, 37, 19, 37]), (847757, [1, 29, 41, 23, 31])]), (5, [(14253769, [1, 17, 43, 17, 37, 31]), (21859867, [1, 31, 31, 23, 43, 23])]), (6, [(272897651, [1, 13, 47, 17, 47, 13, 43]), (424808137, [1, 19, 43, 13, 37, 23, 47])]), (7, [(7642399589, [1, 11, 43, 23, 43, 17, 31, 31]), (8418710641, [1, 31, 47, 11, 53, 11, 53, 17])]), (8, [(705261876527, [1, 19, 47, 13, 61, 23, 43, 19, 53]), (343508150821, [1, 19, 43, 11, 61, 29, 41, 17, 31])]), (9, [(5001316620355, [1, 5, 61, 17, 53, 11, 53, 31, 53, 19]), (298235183875, [1, 5, 59, 19, 41, 5, 37, 5, 61, 23])]), (10, [(10840457019117, [1, 11, 37, 3, 31, 11, 37, 17, 53, 11, 71]), (32246166582465, [1, 11, 67, 3, 41, 5, 53, 19, 43, 31, 53])]), (11, [(131104352392575, [1, 17, 47, 29, 73, 17, 53, 3, 31, 5, 37, 5]), (318821990728325, [1, 31, 53, 19, 37, 5, 31, 5, 41, 7, 73, 17])]), (12, [(8917467228811725, [1, 29, 41, 5, 79, 3, 41, 23, 31, 5, 43, 19, 53]), (2047407165326187, [1, 23, 31, 7, 53, 3, 41, 19, 71, 3, 71, 3, 73])]), (13, [(6224134475718818659, [1, 13, 47, 11, 71, 23, 83, 23, 37, 17, 67, 19, 53, 7]), (51245303801837145, [1, 17, 53, 7, 83, 7, 73, 11, 43, 13, 31, 5, 67, 3])]), (14, [(108043090363342428225, [1, 5, 73, 29, 59, 19, 71, 31, 61, 3, 83, 5, 47, 19, 61]), (3926065196602313399917, [1, 17, 47, 23, 83, 19, 61, 23, 31, 17, 71, 29, 53, 23, 73])]), (15, [(22027411283540928125, [1, 23, 83, 5, 31, 23, 47, 5, 89, 5, 71, 7, 47, 5, 53, 5]), (177118086912132284625, [1, 3, 59, 7, 89, 23, 89, 5, 71, 29, 53, 23, 61, 5, 41, 5])]), (16, [(23707258426609810843125, [1, 5, 101, 23, 83, 17, 89, 5, 67, 5, 71, 29, 97, 5, 79, 3, 41]), (2031893035845148045125, [1, 3, 47, 3, 41, 5, 73, 5, 67, 23, 71, 19, 73, 19, 73, 5, 61])]), (17, [(36236921442400155709375, [1, 5, 71, 5, 101, 19, 67, 5, 41, 23, 43, 11, 79, 13, 47, 5, 59, 5]), (95484403968664676886375, [1, 31, 31, 5, 89, 3, 47, 5, 83, 13, 67, 29, 53, 5, 37, 31, 71, 7])]), (18, [(68449749435915415117875, [1, 13, 101, 23, 59, 3, 43, 5, 41, 3, 31, 13, 43, 3, 67, 5, 83, 5, 67]), (19589478089411820609060525, [1, 5, 107, 3, 97, 23, 47, 29, 31, 5, 89, 19, 103, 3, 31, 17, 83, 11, 103])]), (19, [(17459425383139545183002625, [1, 5, 53, 3, 61, 5, 101, 13, 73, 19, 59, 7, 103, 11, 101, 5, 41, 11, 53, 7]), (253868269728472313813110875, [1, 5, 59, 3, 67, 5, 67, 29, 41, 13, 109, 19, 47, 13, 73, 31, 43, 5, 79, 17])]), (20, [(10019176560312034400567595, [1, 3, 47, 3, 83, 5, 47, 19, 103, 29, 41, 3, 31, 3, 61, 3, 43, 3, 79, 17, 59]), (215947535722966231822673332275, [1, 5, 109, 17, 43, 23, 47, 23, 79, 11, 83, 17, 113, 17, 61, 17, 83, 3, 107, 5, 67])])])
mediumClosePrimes = ("Medium close primes", [(2, [(316933, [1, 557, 569]), (313591, [1, 557, 563])]), (3, [(171534277, [1, 557, 563, 547]), (173971709, [1, 557, 571, 547])]), (4, [(94758693241, [1, 541, 569, 541, 569]), (100381676093, [1, 557, 571, 547, 577])]), (5, [(56670957560149, [1, 563, 587, 563, 563, 541]), (55737645509339, [1, 563, 563, 547, 571, 563])]), (6, [(33960079475671199, [1, 557, 563, 547, 593, 563, 593]), (28590087506703829, [1, 541, 593, 521, 569, 521, 577])]), (7, [(16668687877305357367, [1, 547, 593, 547, 593, 547, 569, 509]), (14895421562352162947, [1, 523, 563, 523, 587, 541, 563, 541])]), (8, [(8825598186724532340139, [1, 503, 577, 563, 601, 503, 593, 503, 599]), (8056030357210311798593, [1, 509, 571, 541, 563, 509, 587, 541, 563])]), (9, [(5176371113800439756757811, [1, 523, 569, 503, 593, 547, 587, 547, 607, 547]), (4307414133054528902898431, [1, 547, 577, 503, 569, 547, 569, 503, 563, 541])]), (10, [(2472832340955827717218826729, [1, 499, 571, 541, 599, 491, 577, 563, 569, 491, 601]), (2584284171184513506455410453, [1, 503, 613, 509, 599, 563, 569, 499, 607, 491, 577])]), (11, [(1910856948409986584271742351543, [1, 521, 577, 547, 563, 563, 577, 541, 617, 563, 607, 557]), (1332882535090650712169308963739, [1, 487, 613, 547, 613, 503, 563, 487, 617, 557, 563, 499])]), (12, [(852196735493924940848986241767987, [1, 541, 613, 487, 617, 491, 587, 523, 613, 523, 563, 523, 601]), (752546528211330815497003845481997, [1, 479, 593, 503, 587, 491, 587, 503, 607, 541, 587, 547, 587])]), (13, [(413424284293138931542565906706071669, [1, 491, 587, 487, 617, 541, 607, 487, 587, 557, 617, 479, 571, 541]), (422612439674921629650938136476012611, [1, 523, 569, 541, 577, 541, 571, 523, 613, 487, 569, 563, 563, 523])]), (14, [(457153207646831573744181522153370927673, [1, 547, 619, 547, 641, 563, 607, 547, 593, 563, 631, 509, 619, 503, 617]), (259918970541028265619885810519171604529, [1, 557, 631, 541, 593, 487, 563, 503, 619, 503, 617, 467, 631, 503, 587])]), (15, [(109868336528703352227207124944087831704269, [1, 463, 599, 509, 631, 467, 617, 487, 643, 563, 563, 487, 607, 541, 563, 479]), (142219206797328060675174570040656920579167, [1, 479, 613, 547, 587, 557, 601, 479, 587, 499, 571, 479, 643, 563, 593, 547])]), (16, [(76820202531067992349805610678707511043871803, [1, 547, 587, 509, 569, 491, 613, 491, 607, 547, 601, 487, 643, 487, 617, 463, 643]), (84353082637098915851350715686631411152617919, [1, 499, 593, 541, 613, 523, 601, 557, 593, 491, 587, 521, 587, 491, 599, 521, 613])]), (17, [(29867711038615093175665393861938141536525529539, [1, 541, 607, 479, 577, 557, 599, 467, 647, 463, 577, 461, 607, 499, 617, 457, 617, 503]), (32160416498806182862863819430142025959220975101, [1, 449, 613, 509, 631, 461, 613, 499, 601, 541, 599, 461, 617, 487, 631, 503, 599, 503])]), (18, [(19956848495929281188644811212469947126676084328359, [1, 449, 601, 563, 659, 467, 587, 461, 577, 509, 659, 467, 577, 479, 641, 499, 653, 503, 601]), (21117036798239547259422495410311750799350659014713, [1, 487, 593, 541, 571, 449, 601, 487, 643, 521, 617, 463, 619, 457, 659, 503, 563, 541, 659])]), (19, [(13264396535897727373516274848984084788966136163607509, [1, 503, 613, 461, 659, 461, 659, 563, 569, 461, 647, 521, 653, 523, 607, 449, 631, 541, 631, 467]), (12747441328106451238259995492136682019426946134615741, [1, 461, 593, 503, 619, 479, 653, 521, 659, 563, 641, 541, 617, 457, 571, 499, 607, 439, 599, 557])]), (20, [(5156986434929461169796816182749562003267982133556328449, [1, 463, 571, 439, 661, 433, 607, 457, 617, 509, 641, 467, 659, 457, 661, 557, 661, 499, 619, 439, 599]), (4889610655414411472658135732868818020771788946718976949, [1, 503, 673, 487, 569, 479, 617, 491, 653, 457, 613, 461, 563, 479, 673, 509, 569, 433, 571, 487, 673])]), (2, [(1142761, [1, 1069, 1069]), (1136347, [1, 1063, 1069])]), (3, [(1228276303, [1, 1063, 1087, 1063]), (1235209189, [1, 1063, 1087, 1069])]), (4, [(1334677393237, [1, 1063, 1093, 1051, 1093]), (1332235165619, [1, 1063, 1091, 1051, 1093])]), (5, [(1402629106625399, [1, 1063, 1091, 1049, 1097, 1051]), (1418937909399427, [1, 1069, 1093, 1051, 1087, 1063])]), (6, [(1597798805102350891, [1, 1069, 1093, 1063, 1097, 1069, 1097]), (1520005874460943489, [1, 1069, 1069, 1061, 1087, 1061, 1087])]), (7, [(1603168127794699290541, [1, 1063, 1103, 1051, 1109, 1033, 1093, 1039]), (1612842382725010293011, [1, 1033, 1097, 1069, 1091, 1049, 1109, 1049])]), (8, [(1718598263073818570384887, [1, 1031, 1097, 1069, 1091, 1063, 1093, 1049, 1069]), (1757529589061923699888087, [1, 1049, 1097, 1063, 1087, 1039, 1093, 1061, 1097])]), (9, [(1824913317720944628804183853, [1, 1051, 1109, 1033, 1097, 1063, 1091, 1051, 1091, 1039]), (1766115859678499030090922409, [1, 1061, 1091, 1063, 1069, 1033, 1091, 1039, 1091, 1051])]), (10, [(2044146205511432560530644353003, [1, 1061, 1123, 1019, 1093, 1069, 1087, 1039, 1109, 1019, 1129]), (2023343565385497662573424982849, [1, 1049, 1069, 1049, 1129, 1051, 1117, 1039, 1093, 1069, 1069])]), (11, [(2138146560514888959638653203727999, [1, 1033, 1093, 1033, 1117, 1049, 1093, 1061, 1129, 1069, 1097, 1019]), (2047088725942481982714204169717471, [1, 1061, 1123, 1031, 1123, 1019, 1069, 1051, 1069, 1061, 1069, 1069])]), (12, [(2353583186144653289501714282050393409, [1, 1049, 1087, 1021, 1153, 1049, 1103, 1051, 1093, 1051, 1091, 1019, 1129]), (2275159985769061830987258016478931859, [1, 1063, 1097, 1031, 1103, 1063, 1103, 1021, 1091, 1051, 1109, 1009, 1117])]), (13, [(2492097436003839540838892538978283235653, [1, 1039, 1103, 1039, 1117, 1039, 1123, 1051, 1093, 1019, 1069, 1069, 1123, 1069]), (2083445330217309788943292916425765482277, [1, 1039, 1091, 1013, 1123, 1031, 1097, 1033, 1093, 1019, 1123, 1021, 1069, 1013])]), (14, [(3026567709449547952359333008027322113358461, [1, 1061, 1117, 1033, 1109, 1061, 1153, 1013, 1117, 1051, 1087, 1013, 1153, 1069, 1129]), (2882599589709110224249733588127180959062163, [1, 1013, 1097, 1033, 1109, 1063, 1123, 1063, 1087, 1063, 1151, 1061, 1109, 1049, 1087])]), (15, [(2784085616184428897659292570343329087575063793, [1, 1039, 1163, 997, 1087, 1009, 1109, 1009, 1151, 997, 1093, 1031, 1181, 1039, 1151, 1031]), (2623289042257046506415381707180861391182863277, [1, 991, 1091, 997, 1129, 1069, 1163, 1049, 1093, 1021, 1093, 1019, 1091, 1051, 1091, 1063])]), (16, [(3309498666165362973713994449803606500505059524969, [1, 1051, 1103, 1049, 1151, 1021, 1129, 1063, 1109, 1063, 1103, 1009, 1151, 983, 1091, 1061, 1123]), (3007559565989492190685682333633142659992222889983, [1, 991, 1153, 1013, 1103, 1069, 1109, 1039, 1151, 983, 1153, 1051, 1123, 983, 1109, 1033, 1103])]), (17, [(3337430374387820187766404846559737967472421425519377, [1, 1061, 1193, 1009, 1171, 1069, 1097, 971, 1093, 1061, 1091, 1019, 1187, 1033, 1109, 983, 1103, 1031]), (3009463694645099549214603933901886663401681206188531, [1, 1031, 1091, 1039, 1163, 1019, 1151, 1061, 1129, 1069, 1123, 1013, 1069, 977, 1109, 1019, 1117, 983])]), (18, [(3205474017206716910525999363197509384671530933913244179, [1, 1069, 1093, 991, 1163, 991, 1103, 971, 1087, 1061, 1069, 1039, 1087, 1063, 1091, 1019, 1087, 1051, 1193]), (3838143684519378674624606833998765033603759339155011169, [1, 1049, 1097, 991, 1193, 1021, 1151, 1069, 1093, 1021, 1181, 977, 1103, 1069, 1093, 1061, 1201, 977, 1087])]), (19, [(3630505250586537380826457274577452415857434807088548791649, [1, 1021, 1109, 1009, 1153, 967, 1163, 1009, 1123, 953, 1201, 1021, 1093, 997, 1171, 1033, 1109, 1019, 1171, 1061]), (3328634472598003887835597528525093350883513224862826212061, [1, 971, 1091, 1039, 1201, 1031, 1213, 1061, 1153, 997, 1103, 953, 1153, 977, 1091, 997, 1097, 1039, 1151, 977])]), (20, [(3055878534232886887533008275157224451264024556815840381056001, [1, 977, 1117, 977, 1117, 983, 1187, 971, 1093, 971, 1087, 1069, 1109, 953, 1097, 1051, 1093, 1069, 1193, 991, 1091]), (4003992205233808349893596129588063075763059241015453817988877, [1, 1033, 1069, 1031, 1163, 997, 1187, 953, 1087, 1039, 1129, 1049, 1069, 1031, 1213, 1013, 1109, 1039, 1181, 997, 1091])])])
largeClosePrimes = ("Large close primes", [(2, [(865712929, [1, 29423, 29423]), (865712929, [1, 29423, 29423])]), (3, [(25454551017407, [1, 29411, 29437, 29401]), (25454551017407, [1, 29401, 29437, 29411])]), (4, [(748949254585166161, [1, 29411, 29437, 29401, 29423]), (749815315379647091, [1, 29423, 29429, 29411, 29443])]), (5, [(22042301982094473596467, [1, 29389, 29437, 29401, 29453, 29423]), (22037819908204262231501, [1, 29411, 29453, 29399, 29423, 29411])]), (6, [(647625188777536523967038123, [1, 29389, 29437, 29387, 29429, 29399, 29443]), (648727214546027169234119857, [1, 29411, 29443, 29401, 29443, 29399, 29437])]), (7, [(19047305219120345130931560910901, [1, 29401, 29437, 29399, 29437, 29401, 29437, 29383]), (19122506962371043582760416155121, [1, 29423, 29473, 29399, 29483, 29399, 29423, 29411])]), (8, [(562143099156355627345058252853193301, [1, 29423, 29443, 29363, 29483, 29411, 29429, 29383, 29473]), (562829942618851054761838008402259709, [1, 29363, 29483, 29401, 29501, 29401, 29443, 29399, 29453])]), (9, [(16549917550139176331089539530499288572021, [1, 29389, 29437, 29423, 29501, 29347, 29443, 29383, 29527, 29399]), (16494942489066181415143190513104903497931, [1, 29387, 29443, 29387, 29501, 29383, 29473, 29347, 29443, 29387])]), (10, [(483818446645921223916066574454799803265926869, [1, 29399, 29443, 29383, 29423, 29411, 29423, 29347, 29443, 29387, 29423]), (490367376997778494257114997680532736329945909, [1, 29387, 29483, 29401, 29501, 29423, 29531, 29389, 29501, 29389, 29473])]), (11, [(14298066897873419916925610084596585019684404299577, [1, 29363, 29437, 29339, 29443, 29333, 29531, 29411, 29537, 29347, 29483, 29411]), (14320484452966964226830269428065419115967575823307, [1, 29399, 29527, 29389, 29537, 29399, 29501, 29383, 29423, 29347, 29443, 29333])]), (12, [(422988549701602021708072490756282881304545627458255859, [1, 29363, 29453, 29401, 29453, 29389, 29567, 29423, 29531, 29363, 29429, 29423, 29423]), (423761271786225112222217862150288564714519017380395689, [1, 29411, 29537, 29401, 29483, 29383, 29537, 29339, 29473, 29411, 29527, 29333, 29437])]), (13, [(12293239381581520625704123339024990495993226167931711051791, [1, 29363, 29443, 29347, 29537, 29401, 29423, 29347, 29531, 29311, 29423, 29311, 29443, 29399]), (12451198379061059764624491385115885732898863931874087138687, [1, 29363, 29569, 29347, 29429, 29339, 29567, 29423, 29483, 29363, 29527, 29423, 29483, 29339])]), (14, [(366249931054054855918254086215217231707917666117006778977380909, [1, 29347, 29569, 29423, 29443, 29333, 29527, 29387, 29567, 29399, 29429, 29327, 29527, 29339, 29453]), (367896370789011152412608731303715436991394396657947014758999489, [1, 29303, 29501, 29399, 29537, 29387, 29567, 29389, 29473, 29311, 29527, 29399, 29483, 29399, 29527])]), (15, [(10644894953985381764687625074094294366413635557060109122838940666171, [1, 29297, 29443, 29333, 29453, 29311, 29527, 29311, 29527, 29387, 29527, 29303, 29567, 29383, 29453, 29311]), (10685620363611581349723712362560065711947054666446884334157352103099, [1, 29399, 29453, 29399, 29531, 29399, 29443, 29311, 29453, 29297, 29531, 29297, 29573, 29389, 29473, 29297])]), (16, [(318513253747377908211654512553364042173627257881988069391587768229583691, [1, 29423, 29501, 29423, 29537, 29401, 29573, 29399, 29501, 29311, 29429, 29363, 29483, 29303, 29423, 29411, 29569]), (318010433938975531069970467031819358831170737214531625647265186479508697, [1, 29347, 29573, 29327, 29423, 29333, 29501, 29327, 29443, 29387, 29581, 29423, 29573, 29399, 29537, 29347, 29483])]), (17, [(9274924513456323558811589191670119099925691334742148666185537727889128732529, [1, 29423, 29599, 29269, 29531, 29339, 29483, 29333, 29443, 29333, 29537, 29387, 29443, 29399, 29453, 29311, 29599, 29287]), (9306534270861220085725248728885553486460012328605762858906957840590239358497, [1, 29389, 29567, 29363, 29423, 29269, 29483, 29423, 29437, 29363, 29567, 29333, 29581, 29399, 29527, 29339, 29537, 29269])]), (18, [(273447555319424943187398893784654666306360710336455357136751751809036563020145951, [1, 29389, 29473, 29387, 29501, 29327, 29611, 29327, 29537, 29339, 29537, 29251, 29423, 29423, 29473, 29251, 29527, 29303, 29573]), (273777364729800462429940443288730515555346668606062214085557317040304257088157639, [1, 29423, 29429, 29287, 29611, 29311, 29531, 29347, 29581, 29303, 29429, 29333, 29531, 29287, 29501, 29327, 29587, 29303, 29567])]), (19, [(8092813032034752870137381401915653543865243380513951917556601612686501897877155480529, [1, 29383, 29611, 29389, 29581, 29287, 29531, 29401, 29501, 29297, 29453, 29327, 29611, 29411, 29453, 29383, 29453, 29387, 29537, 29251]), (8101465846655008560733288209269117691483784364549949754676618472732876797621084547241, [1, 29399, 29573, 29339, 29567, 29251, 29423, 29347, 29443, 29389, 29573, 29333, 29567, 29347, 29573, 29327, 29501, 29401, 29629, 29297])]), (20, [(234378162774272083465819585268149691307105050863628353375341774554968068447199162285443833, [1, 29287, 29483, 29251, 29453, 29389, 29483, 29339, 29501, 29333, 29537, 29269, 29437, 29339, 29501, 29297, 29453, 29401, 29537, 29383, 29531]), (234135764547596304524147681265747540452786682840147054666671262723031988066482413301913669, [1, 29339, 29531, 29297, 29567, 29231, 29567, 29297, 29423, 29339, 29443, 29231, 29587, 29311, 29567, 29311, 29599, 29399, 29453, 29231, 29453])]), (2, [(1621270081, [1, 40253, 40277]), (1621270081, [1, 40253, 40277])]), (3, [(65260984570493, [1, 40253, 40277, 40253]), (65241529329521, [1, 40253, 40277, 40241])]), (4, [(2628907540960158751, [1, 40253, 40283, 40241, 40289]), (2628515975157071569, [1, 40241, 40289, 40253, 40277])]), (5, [(105663786523994505249787, [1, 40237, 40283, 40231, 40277, 40231]), (105747846551901297102991, [1, 40253, 40277, 40241, 40283, 40237])]), (6, [(4276777994168845795685084369, [1, 40213, 40357, 40253, 40357, 40277, 40277]), (4261730664682637298515573083, [1, 40237, 40277, 40231, 40277, 40213, 40357])]), (7, [(171675339450528779010130577717441, [1, 40231, 40351, 40237, 40289, 40277, 40277, 40213]), (171725964673339015282431048008621, [1, 40237, 40343, 40213, 40361, 40231, 40289, 40213])]), (8, [(6940328532425640161878617107022831931, [1, 40241, 40387, 40277, 40351, 40213, 40277, 40213, 40343]), (6937928030201461327568435740563312701, [1, 40213, 40357, 40241, 40361, 40253, 40343, 40231, 40289])]), (9, [(278783934216210794061753445528460285077843, [1, 40237, 40283, 40177, 40423, 40237, 40289, 40213, 40423, 40189]), (280201693317557732699734499983537650751331, [1, 40277, 40361, 40277, 40423, 40213, 40361, 40237, 40289, 40237])]), (10, [(11266035858555712572848498785608957810155199769, [1, 40277, 40361, 40241, 40277, 40169, 40427, 40231, 40343, 40213, 40343]), (11248748165423422014156975262092465859284398131, [1, 40277, 40361, 40193, 40289, 40189, 40343, 40213, 40361, 40237, 40357])]), (11, [(452365647933365700184455164174376023053860917287901, [1, 40177, 40387, 40277, 40283, 40189, 40357, 40231, 40343, 40163, 40387, 40241]), (449701911482155772128565847368365973030290463048771, [1, 40189, 40351, 40253, 40289, 40189, 40283, 40193, 40343, 40193, 40351, 40163])]), (12, [(18313458677768241029361126067868713086248286672636815087, [1, 40237, 40429, 40277, 40357, 40241, 40351, 40253, 40283, 40231, 40289, 40213, 40357]), (18250572437229924758295006051459000197191942489816056329, [1, 40213, 40361, 40231, 40283, 40231, 40361, 40177, 40277, 40153, 40433, 40237, 40423])]), (13, [(738365424372328155516200875596859028033712185143813239636697, [1, 40241, 40427, 40189, 40343, 40253, 40427, 40237, 40357, 40189, 40433, 40213, 40351, 40177]), (735286352707701561586078679475095075815643479401450265856257, [1, 40153, 40459, 40241, 40459, 40193, 40289, 40237, 40289, 40153, 40387, 40169, 40387, 40253])]), (14, [(29373297580035069399879971437182275084191326425505542159180637071, [1, 40213, 40289, 40129, 40283, 40129, 40387, 40241, 40361, 40153, 40429, 40129, 40277, 40169, 40427]), (29909068422978136679310036940712188458368142913407434306408958727, [1, 40177, 40433, 40189, 40429, 40193, 40423, 40277, 40429, 40241, 40343, 40237, 40427, 40189, 40357])]), (15, [(1190308734806001452624428419210166831878447638583765709998701699322677, [1, 40163, 40471, 40153, 40429, 40241, 40283, 40277, 40289, 40151, 40459, 40241, 40343, 40127, 40343, 40169]), (1191197716982639111892135143689621152800042059925150289986504827047163, [1, 40189, 40289, 40129, 40283, 40241, 40289, 40213, 40427, 40151, 40483, 40277, 40459, 40129, 40357, 40253])]), (16, [(48142145059544319190375895840285035420345008460652389028989842839589161101, [1, 40151, 40283, 40213, 40423, 40277, 40423, 40241, 40459, 40169, 40433, 40151, 40343, 40163, 40427, 40151, 40277]), (48304323928051683956152914371144110851492525150491340507493386931312814789, [1, 40241, 40433, 40123, 40459, 40153, 40283, 40241, 40429, 40151, 40483, 40169, 40357, 40193, 40429, 40189, 40387])]), (17, [(1947163081288901745447679864902656801561849466655905426788125701187223499442883, [1, 40253, 40483, 40127, 40387, 40111, 40277, 40213, 40493, 40129, 40433, 40253, 40459, 40277, 40487, 40231, 40289, 40129]), (1950193563503571247994675503760211420163920048052169513812618570297657545722893, [1, 40231, 40427, 40111, 40427, 40127, 40487, 40231, 40459, 40237, 40351, 40129, 40427, 40231, 40277, 40277, 40423, 40241])]), (18, [(78936951915049847226243400827108784756556544200163394380642260866249453916058775541, [1, 40253, 40471, 40099, 40343, 40129, 40433, 40231, 40471, 40237, 40361, 40213, 40471, 40213, 40471, 40237, 40351, 40099, 40487]), (78951094094132040233040058707045915482428704964122655414198932241792706059352696417, [1, 40123, 40429, 40127, 40423, 40153, 40483, 40151, 40427, 40193, 40487, 40189, 40357, 40123, 40471, 40231, 40499, 40253, 40459])]), (19, [(3128927636109278291345269400034681971656783052672880042429271967052894323478553387411493, [1, 40123, 40471, 40253, 40277, 40111, 40289, 40177, 40387, 40093, 40283, 40177, 40429, 40193, 40387, 40231, 40471, 40099, 40499, 40253]), (3146520128824371716207725209907584052952049742107680993674409723280717068075495166986423, [1, 40213, 40289, 40189, 40483, 40127, 40277, 40163, 40429, 40163, 40487, 40193, 40433, 40129, 40289, 40277, 40483, 40093, 40459, 40253])]), (20, [(128852600609349526097437512679089470899860629063921966904451544951666329006154974515208595849, [1, 40099, 40471, 40241, 40357, 40237, 40361, 40277, 40423, 40087, 40519, 40241, 40429, 40087, 40499, 40169, 40499, 40189, 40507, 40213, 40471]), (126062316213731487422916572994986948260691672311530813690188127109530700932036759345668642767, [1, 40189, 40433, 40277, 40343, 40153, 40387, 40169, 40357, 40093, 40499, 40127, 40387, 40087, 40499, 40087, 40493, 40111, 40283, 40087, 40433])])])
print "stored close number suite - re run if needed"
︡dbb844ef-c68d-4189-87d9-58a25bd1e5ec︡{"stdout":"stored close number suite - re run if needed\n"}︡{"done":true}︡
︠2ed4a7a5-cc2b-443a-a34d-61655c461753si︠
growingPrimes = ('Growing primes', [(1, [(9, [1, 3, 3])]), (2, [(49, [1, 7, 7])]), (3, [(143, [1, 11, 13])]), (4, [(551, [1, 29, 19])]), (5, [(3233, [1, 53, 61])]), (6, [(11663, [1, 107, 109])]), (7, [(50621, [1, 227, 223])]), (8, [(101617, [1, 331, 307])]), (9, [(615649, [1, 809, 761])]), (10, [(1854169, [1, 1303, 1423])]), (11, [(4954907, [1, 2213, 2239])]), (12, [(52140629, [1, 6389, 8161])]), (13, [(124433833, [1, 12647, 9839])]), (14, [(544651097, [1, 21991, 24767])]), (15, [(2370909979, [1, 49463, 47933])]), (16, [(14909151463, [1, 123209, 121007])]), (17, [(23492108273, [1, 164627, 142699])]), (18, [(139979437033, [1, 483503, 289511])]), (19, [(861780924353, [1, 870049, 990497])]), (20, [(1836467832607, [1, 1260167, 1457321])]), (21, [(6145242063227, [1, 2420167, 2539181])]), (22, [(35263383196049, [1, 8358397, 4218917])]), (23, [(211603722946933, [1, 15191249, 13929317])]), (24, [(690555681318599, [1, 22120183, 31218353])]), (25, [(2354768115270931, [1, 40387381, 58304551])]), (26, [(10524515709815509, [1, 105228511, 100015819])]), (27, [(35469271347158863, [1, 191062199, 185642537])]), (28, [(204116666094827663, [1, 487529767, 418675289])]), (29, [(422075674112500879, [1, 755800559, 558448481])]), (30, [(2117642963694787031, [1, 1895687023, 1117084697])]), (31, [(7302712871707479631, [1, 2560325633, 2852259407])]), (32, [(67646721787702298573, [1, 8220802739, 8228724607])]), (33, [(194967239383263797069, [1, 12949787761, 15055632029])]), (34, [(377916248951391898151, [1, 19144893389, 19739793859])]), (35, [(3152116907082197651323, [1, 48464174743, 65040144061])]), (36, [(5690735740278543294359, [1, 69273050309, 82149345451])]), (37, [(37348669355338730754557, [1, 192937964503, 193578643019])]), (38, [(182379465040006296703469, [1, 366780205313, 497244568813])]), (39, [(740035675021576430752279, [1, 832139107673, 889317264623])]), (40, [(1621467767655984856828349, [1, 1196156295463, 1355565132923])]), (41, [(5519572522682415067561399, [1, 2481611063383, 2224189198753])]), (42, [(46332129644074366155279907, [1, 6919101704399, 6696263709293])]), (43, [(140505798989565858871072807, [1, 9962837674843, 14102989888549])]), (44, [(739183508214265801484442949, [1, 22366391621261, 33048849395609])]), (45, [(1634079085510008367171987151, [1, 37337028415619, 43765643781829])]), (46, [(12593630947792621856215490773, [1, 105007431995513, 119930853545021])]), (47, [(58508070557320015547197140151, [1, 248525894898427, 235420419997813])]), (48, [(202739680938946359595878036913, [1, 509219106218003, 398138401452971])]), (49, [(689574790076973667294480257281, [1, 942281391942967, 731814080139143])]), (50, [(1949907766443191753963055660461, [1, 1570361150046071, 1241693839908091])]), (51, [(8489347585915818242829281843339, [1, 2516251199875337, 3373807665282547])]), (52, [(41187443491111694438447039647847, [1, 4887714224420297, 8426729059839151])]), (53, [(156459358642545737735512275734353, [1, 10496899304135149, 14905292897390197])]), (54, [(605087173965195078628199214146389, [1, 31467627177146113, 19228878318624853])]), (55, [(3859457453763851973223323911571301, [1, 59558844968537527, 64800743798887363])]), (56, [(7248187272527260607223951331592729, [1, 74877794598982747, 96800223769220507])]), (57, [(45105672648389253325310422267569571, [1, 203318050008452497, 221847851907462643])]), (58, [(161405370219590218800049142558598881, [1, 536101115446072597, 301072625236546973])]), (59, [(461405812545633164103290110362119653, [1, 795516191436818143, 580008072132720571])]), (60, [(3787113430887652026126242676547419979, [1, 1850855849976765139, 2046141751630843561])])])
print "Stored growing primes number suite - re run if needed"
︡1da714dd-cf71-4f6d-b7aa-449fc03337d0︡{"stdout":"Stored growing primes number suite - re run if needed\n"}︡{"done":true}︡
︠fc11521b-f6e7-4eac-acd9-d5c658748d99i︠
# This cell needs to be executed
def plotMinMaxAverage(benchmark):
dataMin = []
dataMax = []
dataAverage = []
for numberOfFactors, min, max, average in benchmarks:
dataMin.append([numberOfFactors, min.totalTime["default"]])
dataMax.append([numberOfFactors, max.totalTime["default"]])
dataAverage.append([numberOfFactors, average.totalTime["default"]])
#print "for %d factors:"%numberOfFactors
#print "min", min
#print "max", max
#print "average", average
minPlot = scatter_plot(dataMin, markersize = 5, scale = "linear", xmin = 2, ymin=0, facecolor="green", edgecolor="green")
maxPlot = scatter_plot(dataMax, markersize = 5, scale = "linear", xmin = 2, ymin=0, facecolor="red", edgecolor="red")
averagePlot = scatter_plot(dataAverage, markersize =5, scale = "linear", xmin = 2, ymin=0, facecolor="blue", edgecolor="blue")
html("<font color='green'>minimum</font><br/><font color='red'>maximum</font><br/><font color='blue'>average</font>")
return (minPlot, maxPlot, averagePlot)
print "defined plot function - re run if needed"
︡54cee9e2-f58c-497a-9116-05611f711f8e︡{"stdout":"defined plot function - re run if needed\n"}︡{"done":true}︡
︠9347994e-8446-486d-b055-7cf13e70d84ei︠
%md
## Trial Division
︡3815f2d8-a8d9-482c-bb07-a496fd690c20︡{"done":true,"md":"## Trial Division"}
︠219255df-7a33-4c28-b7e4-824e637a013csi︠
from trial_division import *
benchmarks = TrialDivision.benchmark(mediumClosePrimes, iterations)
examplePlot = '''
minPlot, maxPlot, averagePlot = plotMinMaxAverage(benchmarks)
print "Regular trial division, small primes"
minPlot + maxPlot + averagePlot
benchmarks = TrialDivision.benchmark(smallPrimes, iterations, {"modified": True})
minPlot, maxPlot, averagePlot = plotMinMaxAverage(benchmarks)
print "Primes only trial division, small primes\n"
minPlot + maxPlot + averagePlot
'''
︡9ffa237a-aa96-4e16-b034-8a452b0f7381︡{"done":true}︡
︠8381e20e-774f-40b9-9bc1-74866114a09ei︠
from trial_division import *
benchmarks = TrialDivision.benchmark(smallClosePrimes, iterations)
print "small primes"
benchmarks = TrialDivision.benchmark(smallClosePrimes, iterations, {"modified": True})
print "small primes"
︡ad9c120e-44cf-480e-b199-ae279624e98d︡{"stdout":"small primes\n"}︡{"stdout":"small primes\n"}︡{"done":true}︡
︠e920037c-25fd-4ba3-a296-a37ca0f5dadf︠
%md
Observationer trial division:
I och med att Trial Division hittar den minsta faktorn först så vet den att ingen annan faktor är mindre, därför kan den börja räkna från den hittade faktorn nästa gång istället för 0
Klarar inte att hitta 32 bits på > 2 timmar
︡76c8f62f-0006-427b-ad9e-9ce4a85afd6c︡
︠7da2602d-d0e3-4eef-afb3-f45a2db598dbi︠
%md
## Fermat's Factorization
︡1d70e3aa-f9c3-45dd-b19d-014107894b1a︡{"done":true,"md":"## Fermat's Factorization"}
︠c81e81ef-e521-429d-8fc0-b96231f59970io︠
from fermats_factorization import *
# Klarade ej att slutföra 5 factors medium primes under > 11 timmar!
# Klarade ej att slutföra 6 factors medium primes under > 3 timmar!
# Klarade ej att slutföra 12 factors medium close primes under > 9 timmar!
benchmarks = FermatsFactorization.benchmark(smallPrimes, iterations)
print "small primes"
benchmarks = FermatsFactorization.benchmark(mediumPrimes, iterations)
print "medium primes"
benchmarks = FermatsFactorization.benchmark(largePrimes, iterations)
print "large primes"
benchmarks = FermatsFactorization.benchmark(largerPrimes, iterations)
print "larger primes"
benchmarks = FermatsFactorization.benchmark(smallClosePrimes, iterations)
print "close small primes"
benchmarks = FermatsFactorization.benchmark(mediumClosePrimes, iterations)
print "close medium primes"
benchmarks = FermatsFactorization.benchmark(largeClosePrimes, iterations)
print "close large primes"
︡3694617b-b2dc-4b4f-a793-830e2d985f3a︡{"stderr":"Error in lines 2-2\n"}︡{"stderr":"Traceback (most recent call last):\n File \"/usr/local/sage/local/lib/python2.7/site-packages/smc_sagews/sage_server.py\", line 995, in execute\n exec compile(block+'\\n', '', 'single') in namespace, locals\n File \"\", line 1, in <module>\n File \"factorization_function.py\", line 95, in benchmark\n resultingFactors, b = self.factorize(n, true, **optionalArgs)\n File \"fermats_factorization.py\", line 74, in factorize\n possibleFactors = self.getOneFactor(a, benchmark)\n File \"fermats_factorization.py\", line 32, in getOneFactor\n benchmark.start(\"square\")\n File \"benchmark.py\", line 67, in start\n if \":\" in name or \",\" in name or \"-\" in name:\n File \"src/cysignals/signals.pyx\", line 251, in cysignals.signals.python_check_interrupt (build/src/cysignals/signals.c:2721)\n File \"src/cysignals/signals.pyx\", line 94, in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1328)\nKeyboardInterrupt\n"}︡{"stderr":"*** WARNING: Code contains non-ascii characters ***\n"}︡{"done":true}︡
︠efb9d8f0-3810-47b0-b4a4-a6fb911107cci︠
%md
observationer fermats:
av någon anledning verkar small primes 9 och 15 faktorer ta extra lång tid. Varför?
En optimering av fermats hade varit att börja räkna ifrån n:te roten ur det sammansatta talet. där n är antalet faktorer.
Udda antal faktorer går jävligt mycket långsammare. för att för fyra faktorer -- -- | -- -- och för 5 faktorer -- -- -|- -- -- Så man måste gå en halv extra. När det kommer upp till medium och stora faktorer är spannet i vår testdata större, exempelvis kan det skilja några 100 000 på mediumstora. Detta kan resultera i att sannolikeheten att fermats sqrt(n) hamnar mellan två faktorer blir lägre. För ännu större tal verkar det knappt fungera alls. För små tal är sannolikheten stor att den hamnar mellan två tal och då fungerar det fläckfritt.
43-bitars tal tar över 5 timmar.
︡28e19006-6988-47db-b2ce-ee6f5e9056c1︡{"done":true,"md":"observationer fermats:\n\nav någon anledning verkar small primes 9 och 15 faktorer ta extra lång tid. Varför?\n\nEn optimering av fermats hade varit att börja räkna ifrån n:te roten ur det sammansatta talet. där n är antalet faktorer.\n\nUdda antal faktorer går jävligt mycket långsammare. för att för fyra faktorer -- -- | -- -- och för 5 faktorer -- -- -|- -- -- Så man måste gå en halv extra. När det kommer upp till medium och stora faktorer är spannet i vår testdata större, exempelvis kan det skilja några 100 000 på mediumstora. Detta kan resultera i att sannolikeheten att fermats sqrt(n) hamnar mellan två faktorer blir lägre. För ännu större tal verkar det knappt fungera alls. För små tal är sannolikheten stor att den hamnar mellan två tal och då fungerar det fläckfritt.\n\n43-bitars tal tar över 5 timmar."}
︠7edfd4e3-f582-4de3-ad74-3c5eb8a645b0i︠
%md
## Pollards Rho Algorithm
︡0face64e-e61d-41ba-87ea-0adbdc8622dc︡{"done":true,"md":"## Pollards Rho Algorithm"}
︠98c7831e-5b96-4b53-9863-268d7f6bcfabi︠
from pollards_rho_algorithm import *
def default(x):
return x**2 + 1
def higher(x):
return x**3 + 1
def odd(x):
return x**2 + 3
def trial(x):
return x + 1
#PollardsRhoAlgorithm.benchmark(growingPrimes, 10, start=51, mode="bits", optionalArgs={"lambdas": [default]})
#PollardsRhoAlgorithm.benchmark(growingPrimes, 10, start=3, mode="bits", end=25, optionalArgs={"lambdas": [higher]})
#PollardsRhoAlgorithm.benchmark(growingPrimes, 10, mode="bits", start=3, end=25, optionalArgs={"lambdas": [odd]})
#PollardsRhoAlgorithm.benchmark(growingPrimes, 10, mode="bits", start=24, end=25, optionalArgs={"lambdas": [trial]})
#PollardsRhoAlgorithm.benchmark(growingPrimes, 10, mode="bits", end=25, optionalArgs={"start": 100})
benchmarks = PollardsRhoAlgorithm.benchmark(smallClosePrimes, iterations)
print "close small primes"
benchmarks = PollardsRhoAlgorithm.benchmark(smallPrimes, iterations)
print "small primes"
︡6173a321-27f2-4a12-94cf-117789c2a963︡{"stdout":"close small primes\n"}︡{"stdout":"small primes\n"}︡{"done":true}︡
︠46d752e1-5631-49a7-92d1-374ae28aa947i︠
%md
Enbart default fungerar ej på första
︡8c8a6eed-3146-49e6-9403-57df73dc9d19︡
︠0d28dcbf-ac0a-454c-94d6-8924ccd1ece1︠
︡8216fdce-0a19-408b-a966-4889e530491d︡
︠9ad8fdc4-7071-4568-9a12-75fb30a060a7i︠
%md
## Lenstras
︡f7a3a515-e036-4c55-8537-e4f7e4771b59︡{"done":true,"md":"## Lenstras"}
︠829afeb3-5ad8-402c-a540-98e48f3e0afci︠
from lenstras_elliptic_curve_factorization import *
#benchmarks = LenstrasEllipticCurveFactorization.benchmark(smallPrimes, iterations, {"maximumIterations": -1})
#values = map(lambda x: x[3].totalTime["default"], benchmarks)
#print sum(values)/len(values)
benchmarks = LenstrasEllipticCurveFactorization.benchmark(largerPrimes, iterations, {"maximumIterations": -1})
values = map(lambda x: x[3].totalTime["default"], benchmarks)
print sum(values)/len(values)
x = """
for i in [1, 2, 5, 10, 50, 100, 1000, -1]:
print i,
benchmarks = LenstrasEllipticCurveFactorization.benchmark(smallPrimes, iterations, {"maximumIterations": i})
values = map(lambda x: x[3].totalTime["default"], benchmarks)
print sum(values)/len(values)
"""
︡657c4faa-6e98-4c6b-8439-497ee33d218d︡{"stdout":"39.1989332011\n"}︡{"done":true}︡
︠07d27bb1-10a6-4fb9-94c7-f03b34d285cdi︠
%md
Över 8 timmar för 32 bitar...
︡a9351fe1-7c76-4dff-bcc3-ef840b557d02︡{"done":true,"md":"Över 8 timmar för 32 bitar..."}
︠5b5b66aa-9e88-4122-960b-9c8f94934739i︠
%md
Lenstras observationer:
att sänka maximum iterations innebär att fler iterationer körs (totalt, inte per "omgång") - detta innebär att fler primtester körs.
Det skulle gå att använda ett såll (marcus lägger till om GitHub-lösningen). Istället för att gå till alla punkter kan man ta primtal.
Teori:
Att 5 är bättre än 1 och 2 iterationer kan ha att göra med att det är först då det börjar löna sig med primtalstester. Det är generellt bättra att ha få iterationer och försöka forcera faktorer, men primtestet håller då tillbaka prestandan. Att exempelvis lägga till en flagga första gången ett tal är primtestat skulle kunna resultera i att tal inte behöver primtestas mer än en gång, men ändå kunna testa enbart en iteration av algoritmen.
Literatur har tytt på att algoritmen kan vara snabbare om man avbryter efter n försök (sqrt(n)) och kör om igen för att få nya slumpvariabler. Vid imperisk studie hittade vi.... Vi såg dock att sqrt(n) presterade klart sämst. Detta visade sig ha med jämförelse av int och cocalcs integer med decimaler som blir vid sqrt(n). int(i) < int(ceil(sqrt(n))) är alltså snabbare (med en faktor av ≈60!!!) än int(i) < sqrt(n) trots att sqrt(n) enbart beräknas en enda gång!
︡1133b299-83ef-4277-9476-37e48b139d1c︡{"done":true,"md":"Lenstras observationer:\natt sänka maximum iterations innebär att fler iterationer körs (totalt, inte per \"omgång\") - detta innebär att fler primtester körs.\n\nDet skulle gå att använda ett såll (marcus lägger till om GitHub-lösningen). Istället för att gå till alla punkter kan man ta primtal.\n\nTeori:\nAtt 5 är bättre än 1 och 2 iterationer kan ha att göra med att det är först då det börjar löna sig med primtalstester. Det är generellt bättra att ha få iterationer och försöka forcera faktorer, men primtestet håller då tillbaka prestandan. Att exempelvis lägga till en flagga första gången ett tal är primtestat skulle kunna resultera i att tal inte behöver primtestas mer än en gång, men ändå kunna testa enbart en iteration av algoritmen.\n\nLiteratur har tytt på att algoritmen kan vara snabbare om man avbryter efter n försök (sqrt(n)) och kör om igen för att få nya slumpvariabler. Vid imperisk studie hittade vi.... Vi såg dock att sqrt(n) presterade klart sämst. Detta visade sig ha med jämförelse av int och cocalcs integer med decimaler som blir vid sqrt(n). int(i) < int(ceil(sqrt(n))) är alltså snabbare (med en faktor av ≈60!!!) än int(i) < sqrt(n) trots att sqrt(n) enbart beräknas en enda gång!"}
︠b47cf34e-1b83-47d3-8523-5c051fa7a3c8i︠
%md
## Run all
︡3a9702e3-d07a-45ba-888d-df39d0b35d7a︡{"done":true,"md":"## Run all"}
︠9deb2d03-0f89-4087-88d8-942cece20f9bs︠
from trial_division import *
from lenstras_elliptic_curve_factorization import *
from pollards_rho_algorithm import *
from fermats_factorization import *
#
benchmarks = LenstrasEllipticCurveFactorization.benchmark(growingPrimes, 1, mode="bits", optionalArgs={"maximumIterations": 1})
#benchmarks = PollardsRhoAlgorithm.benchmark(growingPrimes, 1, mode="bits", start=25, end=50)
#benchmarks = TrialDivision.benchmark(growingPrimes, 1, mode="bits", start=33, optionalArgs={"modified": True})
#benchmarks = FermatsFactorization.benchmark(growingPrimes, 1, start=35, mode="bits")
#benchmarks = TrialDivision.benchmark(growingPrimes, 1, start=32, mode="bits")
︡52a3fcea-b40a-49bd-93be-b2022ebbbd84︡{"stderr":"Error in lines 5-5\n"}︡{"stderr":"Traceback (most recent call last):\n File \"/usr/local/sage/local/lib/python2.7/site-packages/smc_sagews/sage_server.py\", line 995, in execute\n exec compile(block+'\\n', '', 'single') in namespace, locals\n File \"\", line 1, in <module>\n File \"factorization_function.py\", line 97, in benchmark\n resultingFactors, b = self.factorize(n, true, **optionalArgs)\n File \"lenstras_elliptic_curve_factorization.py\", line 87, in factorize\n benchmark.stop(\"primalityTest\")\n File \"benchmark.py\", line 79, in stop\n def stop(self, name = \"default\"):\n File \"src/cysignals/signals.pyx\", line 251, in cysignals.signals.python_check_interrupt (build/src/cysignals/signals.c:2721)\n File \"src/cysignals/signals.pyx\", line 94, in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1328)\nKeyboardInterrupt\n"}︡{"done":true}︡
︠85bd0330-3aeb-4c2c-950b-5fc18cb19418s︠
def tableFromSuite(suite):
table = "count\tnumber\tfactors\n"
for count, numbers in suite[1]:
for number, factors in numbers:
table += "%d\t\seqsplit{%d}\t%s\n"%(count, number, ", ".join(map(str, factors)))
return table
︡987a3814-d91d-4384-8a59-efaaf6da3f89︡{"done":true}︡
︠52cebdae-3450-44be-8a1d-6f50fb4a3761so︠
print tableFromSuite(smallPrimes)
︡e95f5184-877d-4fb1-a106-f58eb4d8fe05︡{"stdout":"count\tnumber\tfactors\n2\t\\seqsplit{481}\t1, 13, 37\n3\t\\seqsplit{31093}\t1, 31, 17, 59\n4\t\\seqsplit{1213045}\t1, 37, 5, 83, 79\n5\t\\seqsplit{15001613}\t1, 31, 37, 29, 11, 41\n6\t\\seqsplit{3429238769}\t1, 47, 97, 59, 11, 19, 61\n7\t\\seqsplit{206397809105}\t1, 37, 79, 5, 53, 41, 67, 97\n8\t\\seqsplit{7311461300687}\t1, 41, 23, 73, 41, 59, 83, 23, 23\n9\t\\seqsplit{472213574958521}\t1, 41, 53, 37, 47, 61, 11, 71, 61, 43\n10\t\\seqsplit{3443187949695}\t1, 29, 43, 83, 5, 73, 41, 13, 3, 19, 3\n11\t\\seqsplit{309773094336642695}\t1, 5, 97, 11, 31, 83, 97, 31, 89, 43, 53, 37\n12\t\\seqsplit{62263002262083735}\t1, 47, 83, 17, 41, 59, 59, 43, 3, 7, 47, 31, 5\n13\t\\seqsplit{666536544405580303}\t1, 31, 23, 7, 47, 23, 67, 37, 37, 19, 13, 41, 19, 7\n14\t\\seqsplit{56142059257389353853}\t1, 3, 37, 11, 37, 19, 97, 11, 31, 53, 31, 67, 11, 71, 23\n15\t\\seqsplit{3173389011480824657829}\t1, 3, 79, 59, 53, 31, 7, 23, 43, 73, 11, 71, 3, 71, 31, 53\n16\t\\seqsplit{15863359163742166197825}\t1, 37, 3, 19, 61, 5, 11, 79, 79, 67, 3, 71, 5, 71, 97, 43, 17\n17\t\\seqsplit{3839358256056932827602345}\t1, 67, 17, 29, 19, 53, 41, 19, 19, 37, 73, 89, 13, 5, 53, 3, 73, 43\n18\t\\seqsplit{18710317739887802052740556555}\t1, 97, 89, 89, 83, 59, 5, 79, 59, 73, 13, 11, 31, 31, 29, 3, 89, 67, 41\n19\t\\seqsplit{155903632515187552359018988575}\t1, 97, 43, 47, 89, 97, 11, 73, 73, 61, 3, 37, 29, 61, 73, 5, 5, 67, 29, 37\n20\t\\seqsplit{53620794966136160429097776631}\t1, 23, 3, 79, 23, 43, 89, 61, 59, 3, 23, 71, 41, 97, 13, 11, 17, 37, 29, 47, 13\n\n"}︡{"done":true}︡
︠f4fcb521-1bfc-4e78-8faa-74fd1818e972︠