-
Notifications
You must be signed in to change notification settings - Fork 0
/
A101766.py
118 lines (106 loc) · 11.1 KB
/
A101766.py
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
#! /usr/bin/env python3
# A101765: Iccanobif semiprime indices: Indices of semiprime numbers in A014260.
from labmath import * # Available via pip (https://pypi.org/project/labmath/)
from multiprocessing import Process, Queue as mpQueue
print("The left column consists of candidates for A101766.")
print("The right column is A014260(k), where k is the value in the left column.")
print("The middle column is the number of digits in the right column.")
print("If a number takes too long to factor, then we automatically move on to the next.")
print()
# To aid verification of the sequence, the following list contains prime factors from the harder-to-factor terms in A014260.
factors = [2784709783, 424687589, 607993329733, 241194637, 1341049193909, 89201750527, 170266367, 256088873, 12850909, 43979371,
177707527, 234558411011, 529341241393, 956326272563, 569421751, 159980957, 873170329, 1936974889, 96852131, 23517281,
20777465359129, 21589349, 17340839, 404776583, 685801037, 37219729, 5539088831, 598293233, 1970934409, 632545829,
370043749, 50351479, 24226907, 110565383, 11481451, 2919264851, 405232123, 2527003883, 123075817, 27147173,
742285162550359039, 1655000230515124721, 2469146710118399, 3515180215620497923, 2458813714667, 23933305011316511,
103005881880982696139, 1508578352219, 10045648939262356243, 114116017243, 35595689388400877, 70819565227,
3336864859751, 888681746231, 44976907193, 1113955101463, 734548469, 149766944757103, 98292548871499, 3582379845853,
16093094723, 339445966667474731, 86871995117499391, 167082301904879267, 40601578825894529, 1846968743666803,
107919514475357118070466839448321, 3809874474908057372540508865742173, 8473390695382164254074263127979,
21342967205326918581106439616879478183643291069, 70813953416442701393, 1170752338713812690979925961,
25216658599536010125556993, 20340336299108061406853, 13031988861418162096668879455059, 5086454320458148244823064487,
521891479763894321744687, 1415976115793851204280341, 7562739555248345458943520761]
for p in factors: assert isprime(p)
# We will use multiprocessing to put a timout on each factoring operation.
def extract_prime_factor(x, factors, output):
# Finds a single prime factor of x, which is returned by putting it into the queue output.
# Trial divides with each of the elements of factors before passing to primefac.
for p in factors:
if x % p == 0:
output.put(p)
return
p = next(primefac(x))
output.put(p)
a, b = 1, 2
q = mpQueue()
for n in count(3):
a, b = b, mpz(b) + mpz(''.join(reversed(str(a))))
if n in (769, 1394, 1795, 1983, 2093, 2178):
print('\b'*100 + "%d %d hard %d " % (n, len(str(a)), a))
continue
print('\b'*100, n, len(str(a)), end=' ', flush=True)
try:
proc = Process(target=extract_prime_factor, args=(a, factors, q))
proc.start()
proc.join(1)
if proc.is_alive():
proc.terminate()
proc.join()
if not q.empty():
p = q.get()
assert isprime(p)
assert a % p == 0
else:
print('\b'*1000 + "%d %d timeout %d " % (n, len(str(a)), a))
continue
except KeyboardInterrupt:
raise
ap = a // p
if isprime(ap): print('\b'*1000 + "%d %d %d " % (n, len(str(a)), a))
"""
8 2 21
16 4 1563
18 5 12115
21 6 104645
26 7 1427797
38 11 15760098899
42 13 1084084619941
44 13 2609486483433
49 14 19257844151359
54 15 613632773448665
55 15 939743591886238
57 16 2339276164470493
61 17 83143570569221663
67 19 1584453602511035987
77 22 2261806959537771725147
78 22 8649184296900353284718
115 34 1307862466766223503761486963024421
123 36 219614651280272551281377915419146758
134 40 1569103135261552255620952800874514943449
145 43 1320957576031725345448789244377822669794553
151 44 19775723348296729360340574449461574333600011
154 44 97808715323843668600504341529942542350828659
202 61 3082256980708225451108032362793546225981433291659764026198383
218 65 68544087579135974583020430919965831912237243994231205970627743323
249 73 1871951489533834452402968820374840830446582222487396039934921944351740259
286 84 288025474706382791308724629303677377130027933969312057463710902998321831054201997549
349 103 1047475725153405362652495626620469936245917739649986260626969502753471104703931430060835751306184391347
403 120 122003912420634945720057339910777867211139374438689870937005842397167458996917879899782232552286638630203151971474420711
498 148 1468582481815340484222726174629475097258744789722024623629845627523122388190880356171292150098989869814477363249036429074068709591148136887084512709
539 162 120235940798880559124528460080806997523831644880257394812282390540308430372618041134732104453834796861203152433148928921895933746430457358055924364741170570522771
647 193 9352735093250398975464990836732214594586867462623920679500437099146623136681211674543069258734038891638778097227725513869919526044267814187071684846886540054321510099288837829530561279687863867
769 232 hard 1065324012278520488918301940747079850464760626272891133509789861138931700892066709644010098981857301846620846771906733664754817126185394932276519965243220048213845463652226594421294268877291079280300996616095509017143846355481497791
790 236 96734820568910034090261053922919488028159093152175005590575775854895073077908546246981007798997224646362209714707967479753382521874358861379632290557197676723212115056329328499442228056700354344776949962510215237769853162230130902872697
1161 346 1151028393202203575932482841904372275377064320857504601725974290750474361510418812236246799598126180959970934273489339331850664933704159564390761981440182920295269180692947434397602050867223783718489393519340623016363771732996296602183890098097418031615702291851803093379999947684130747587851561199317343692675982602700125483120662296039404100619
1347 401 24756404746891540892888361470669157585866595928037417073334364881575750744468727262480629454103020727952987119376777617419782964232862776523858566330672108935301213791397834879604658107454577027711894802874224477351947096128405443463163935859280055714279961447708877237739996724637366054040167790976196654200874975020036511756095496382085217829071709582321634976539914178497213145205070476533048573437
1394 415 hard 1372353517504534231276195952823338116312280896925567906967852298641678463725230894494990876915013287411748367264969600488717920639851576481002496347911932297099777493457685385119613640066675509803732510894889765150542915467567356478376661412357787462312102425988866878671352496851539973856655760936703503494773718060340675971937632723736067353887405935688870048084875001319415476495323898321820812556021036035750269
1418 421 8305469275261536132928879682918087744391314442069014949278214928780893872489581478253275868052945586543877357551198818579368136366739020008033702947449750198476214046178786234461760205125090355237678061809602073999120173349309868724468373033015968637036299071935671370115442681968099641273159133090516960338893458955148290025095074912473179475871145984104320155161550569915870859559781116848136346984674515925904018077663
1595 471 328335188715366342931904764865855591067303551525414078046095026320990215811004796469742333462608175288680528919645849519277502463553997786336489174758945066443784189857357283560214559601675099242726655502318673002224236504179097165925624527293539938024768427953045943709903475081425781364638865107578733442668286887819503465144159740473250392838844754666068460756092899300591491867873644775306397541386580197526294362810596671448228403832092532886345066666528367985540861
1761 518 23509715310030795537750661522281593951109181212209213625309163238509496733476738531436583275243368804028857567436421459424649499921157435748636789920123908655048791600728918100453567878031102130002669807986123356851541472592559011202379187093939847476141638315369458912682579392922217723108635922863752043516227130169651207633155146493104673972634726385243108169408349656575607394625944955885549029604390011641009171467413353682948232963805311417309009577876081189628585859798256026962350215596049571994901074416166123
1795 526 hard 8638041901328010979346169950672314885196113843850680872309286555588391358826987360045561280611640327664410153990892887971016364796443607179705302111176364958800115846097671504851935424097273316983448878047383469083619613352135987278962339383430902299866526783422264395178282759115623866795132714252592640148793059078846152268133909461367344320896437434738715436357849705812401050495192614363755597060344082817261616950832560474996260607956015200581435100837769413424429350443254298884200472178841525919576933956791448767151297
1983 581 hard 13928555950367822200725219428833045791237475235228675289861993029578487325720460352173121731159017110271322816072905187720785314582944980474598280905341816403242234232006421475473994661281157913520827887154949979983135300282217864735402594099654358332828208408563477603478390103109937725494886433036614433027827253941432591631703767441757123364986949743028402603988235274369931902124675685856493706450084458042301291664375158591366213594025904272446373063776106707619232245357015409969954794604982280584804736028003541760661807062097942670582697087011769861261482027724409999970331
2018 591 231720469874848842064548960575881383900205215817610895133302700876180954820572168673186443872507100914523764000147388116058464875024498141907623577437667070000694338414515610982945444868849260169675337893947824550173405929984802689619292188040370534014789853672765423566847673751184270662262424511716751104900441752854901474099985035101955842045543316110857274379130392500755859994627929877737029483392173371595665398747026344141244769016494307708966772284408877843290492683777915360632253819318286398633185883566831905396443100668298630535945281449940090011211658885991325682363114036693029
2093 614 hard 15600923942348227325683929880301298974155250143426927999257838085885925505752121838611158426594956020954157727727443652085312820025916255840223532271147742496632875223134827413007262634571508368381325197295457716418228955169334187239979610654190059849192803220954785198212157641358455360511549919469577548413832139900121495285548182645271839627758684874156105784722032317787326809527199736665691178066517550922659770118573178121555830112928371398818256833415921053047588704493613723774475197474894468426215647336334984165878205203807485096977945128279149042321097852715624214345673886799499844213442480585909084319
2178 638 hard 89292112580546211854100877053591193214318312595842879675582389288409897070998741618175350538231799025314000433216359500601599251690421357897152946729281142043550571372377548847837963389559425706425382547915272471261593918338977106847092959330163244750245997660918165483669804834892976669641070081884216686148285776172285185194373087966895359197498684014174554121745122163162340088217461150886776093578122205522043297606666113525069469897737830108484652383254706251447096817035474235415832398952517817382817672756884206876205325824958058832801561296234144112726240694852399891236251062423727216565547501339831088982540694593306645886414687
"""
# yafu "factor()" -one -pretest 40 -aprcl_p 6021 -aprcl_d 1