-
Notifications
You must be signed in to change notification settings - Fork 0
/
A101763.py
120 lines (109 loc) · 12.6 KB
/
A101763.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
118
119
120
#! /usr/bin/env python3
# A101765: Iccanobif semiprime indices: Indices of semiprime numbers in A001129.
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 A101763.")
print("The right column is A001129(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 A001129.
factors = [3246525723631, 508926885527371, 2277974807, 891894168391, 891894168391, 1315593107, 15330252793, 8264192186826923,
21589326122354323211, 5713626987475999133, 3446400317, 300440741, 243706465871787733, 957073226861572390243,
172909367415915407, 2522841859, 109475648800034381, 1168633379, 39345653779, 62861405443, 59932452247, 157780149217,
25423424473409, 1084505123310073, 849550399, 849550399, 982311067069, 424653133, 7567854929109113560543, 2672417287,
573948369390367, 8340890615252743, 263697380959, 753876934731621817, 19342983631, 1657273637, 57919259, 6750207791,
747549310178159, 17143287258036000253, 16719491093202823, 416142945408197382941, 561734224453, 239993174476673,
890940526170799894443191428585026611921698279199, 12765913574958384583474872573859, 1280105378276339198520819437,
3708977477723720206441338113, 4968415083457690784370392159, 176908699226351402056197533557918076612179, 40706886947,
172630908216221913140513, 19772350295589499842137997305677, 123232294791145091, 177775186156979430271664228987,
348280651263869227381, 236188192672787413, 200088953446061654041, 336013114172699, 8027807048299, 328426269629,
982774544589264528242848553109379, 1237441669514557171871, 4300771489064312456621107, 17795660106046204667064286853,
24441271933360698031447430510250131796553638931, 605930248412381002353048560752801499164181, 1260141569, 123935921,
23621531, 90084857, 120758761622471008531237003, 7206949, 189893037387458632145649881389124903]
for p in factors: assert isprime(p)
# We will use multiprocessing to put a timout on each factoring operation.
# Those numbers that hit the timeout were then given special attention by yafu, GMP-ECM, or CADO-NFS.
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(''.join(reversed(str(a)))) + mpz(''.join(reversed(str(b))))
if n in (838, 849, 1073, 1667, 1741, 1870, 2155, 2478):
print('\b'*100 + "%d %d hard %d " % (n, len(str(a)), a))
continue
print('\b'*100, n, len(str(a)), end=' ', flush=True)
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
ap = a // p
if isprime(ap): print('\b'*1000 + "%d %d %d " % (n, len(str(a)), a))
"""
8 2 39
10 3 514
15 5 61135
17 6 792517
35 9 522619163
37 10 1148964371
47 12 108347089519
53 15 109799986317899
62 18 443750792427191609
66 20 82476194306552245747
74 24 106279288487219195996077
79 25 8017843312816648158380899
110 34 1484156683177311102265795907844017
127 39 504174577393204378401199240003107009505
146 46 1733895155434408674203305300488907561439193397
214 67 5925695014208246549953552367223606830993853437759678156657573154617
231 73 8092022532062794355153764983301701361322827375071548000887086836551060459
241 76 7135676014128172681952480223286942455361932855427885973467672585504531819987
242 77 12745305432613431656978115308315310478605367860248143100000391328259917084981
245 78 468928763284410213621724581327962516132696902619834165240253711855360077333963
250 79 1228992434504736860145162852704186240365113020074767544080594123579576288770314
277 87 619648096479083553324954963570809307842305459961415742031548431441061795598723784922907
293 91 4120241722269580870374488105744621623170799643308381928808912214164161744807195001066151193
302 92 38632762036390587138644744572847732221313822501669531939596614235135355586127661242420337927
343 103 8901805536000585389597534243943418206087099403199685757723821055496390602351357072191240689893148299123
485 148 1383412911418890641134658162018058916256454358991361069186656016577764738995416563200363444956886967138814203765602965004276061971653870688874562787
525 156 103988879304385928597113671071102308839947544329126203786269553723584741406050321899164495832365001767351687025176106364314959668638318145803764630023592553
550 166 1071278261554943442572538205526224345874222926950042775751027062950625078459000533611856344984142814676026606458221087381746493077685382402023940737915222255138298077
599 181 9867039513348714632847765879725176343357539332401931593002927347590368885676458910443746432735620745274951934671168716380988778811351376077189695710295188599795219853306719117512969
638 193 7504461213179469670982913268908792049146450972065609520274530108395352120694183676017337523670076133351900066104647817763908099192487190626860088315017190951093991639841291177063068426002471686
687 207 573058417948569851409940622954714584300112285524392093468430303430375540775559781542829416178469639391527411640951896183698104510942524581657071256665358826781175193304673407797595688686741128558418026324289
733 221 46418755136569269605790176655656601804707322650782496187269164688805341005667484919931088236899578470166575332806043872784111627255587174372276798623806652680783891925343456627052135722314563589990450506349127630656624954
805 243 945578516044748091735336461359683791943968732624913910076689481102178607830679267408882511537011576528065512908415693708295540060210009443967033811528481394397450632252385359517265700519362695996935582122475949032451568645813144368547487951773
814 245 93749513646284002488184608889006947065024937224502662355781014828217692852975367341670204894718897753420646035125833270739890952815590968007690545040910950302748616211519461478894921046478514182053387028020884169268265428546631978347507466373963
838 248 hard 97568038442426748823075161541139292532803666655397738012361079889864122312244202887249974072634111105897508813856744605749397369829461645481520994154845062940454403148570758202857658678419017730027201021652293232908366654938930435141714622943650831
849 251 hard 98028690235826810872305786551975809960045299469808011449872942730177995080240727301027461539894415296537378785550663419004779558125074278502006867935253323281679696018824237647900722658006829964563029603116429056384470872817110170051855071567352156509
881 261 100131148176372051471080763361274166388958276777270784173798546516305592264861583271406560562747837859191718761645327586002444470245418361296884759571937180088165696041611678339188974531230430816594702440539643519732384413795054951789768044072450610370751598979
946 281 75206952393117825530772107083236534328780727566473751994934778632251164237694360748803838111196022284869438895757086120538531121226032393663292873212824540499893998797007649984477706615390310143236902376690948104552119916031462194692077246949034349088589187155521901142907071769082
954 284 96357587705225748209128283670617089595850884510203948521947570704630620724345155340157400730277389681466001617510466348241907066242825039133322640813333379294239768421063839906547058562074754517882923972168178611478088122894671265853970022203529957921323428477053305730633522970219718
1073 318 hard 107872729973383632349757216736309920285538247551316836040785274870522032231235550023015148755609639083787846575072556625877851691861494185877445366700904659084555231035497180833363948076699670181394163069502879552331045704127059401271046715592389431140646223432654068186219020844833827051590545447453990822891157893117
1086 321 127307614424520797289479924071573167383256667869223974787547219278943682213271721504167487198947538112385274453312248433526647815951926602371932001267958649454590089400806743041632913635773858602322670578487640596821664617992533843975123956407842291257380169086404415453201745284711772768328878315519184055296721406753931
1667 490 hard 1043427631505484413113144234000893975749018892783301842337496081426257072976450572349818239067171412760452272789077865208336610571035148001651296633907963539843969900515986035394893656958595543566984857260201799981690709049683205515255248881541025131998548325009032835326897355415905742316296782855160690773743332968642700554105305056728585818106791855297797660136433625902980829250852032427598913109385364477404388462683087131865923675177064193834253539782369904798880763657257395824028609
1741 507 hard 121985259356058373671686264034835542801443114347198949719551129089631256185555242756030658668522872931461856112858054645002594655521424049748794704640501656433375818524720894489538467242260511263780358071913041982832793052427686313922405102880497020529916186301319159637770741677340511818385976133656245958744806015792338487372430111336757356561768085214747188675680895920456945005342131282980189719611843281015206973175264241976406368427482117698854956769128897606251346118440801484327867540473550267688247
1753 508 1649452632457867267973054154084965254787748565330097803785990543831382391584776079301296137305933628866487950412195359488186158531747156080801116991072359766145131909309504274167405592518353524819842438605806621323282806030823482765292075155189783870172850477851769576923647309571652962969157249587714423680967912843988813001086902807190530879156661128866596494578295807500679324522895877888320343623434881329827110708020317649550765423713679572309312681100523906455452617549271181783800855075149893829062369
1771 513 131004760360474280568269389788268896098919629447677235289226215660037315305173386065662469571917372406442644844286815026982443286990022619769986698503818699945700402260115955324174041104647797819350906760243971530311313875668724776990303861473588596722854375685473242035895568052849602562847319823324107904182455745601791648498321069430649876101290987748543133256324715859692165975704486532552311616524799880443405819238009047367041471815266599528505510871971943386201363531687855055019742819403948905050085624831
1870 543 hard 101412659494618568288573643932426633223913596805956447472371217300362161859229206493821182527173417139087538184514633177725752617854437927123232923045110915581559334097132436263514597893110970999220422865733373796610698128475451007605083949913133381602633496388924268980556406818418997170741599704942124254251080555885171027979014073991443935192405317410790398783577364724676451827181564371826411300948997496356109201368655232093634079385438594116645422193126484381048349462366772462544437994987711244395677101391883514670235947361728860301273
2155 622 hard 9957982345973752036432745013303175834594056121389502692724009360564464297618426845587907526287327685606706410990405490103473153336470745503367655399127568472445323702777800600702773306374071880269215970690930329248947181784033926463285834604590606985840274416820874391242127962216321244303145805833250254175822483792382933913389959333312793135345597072384033513047638331383250630676508999195747724077904695903633396342756285107745913391729665174229392643089680251893314736936360650952921925880761166114544238046844870454970282993784100811210152558174618024147543996397234704467384968116875363799728091474713636382721375549
2478 708 hard 142222062587196890207686809086920894599025543718127591491909150672481522235358800289684522513866585625772922736503775942608141501135191847667797662986591310398661649401245628740961292699534064504467627392265324380439020193853557049175270570376584882681070678472813613147302465066644369496422215958172888804472427391533974652245348266784473928018510803333096978897021107540823291254188997634651385247210822784727574864543185353348179019095992663118116781812909037076703346122335043675507111712575268793830007374804897153165763222863765636964653244928800503779070210493418250150554824677370274459466020081882823797912051587288605461291444290918744808902138719397117183771850264092475198321877147101377508553007
"""
# yafu "factor()" -one -pretest 40 -aprcl_p 6021 -aprcl_d 1