-
Notifications
You must be signed in to change notification settings - Fork 0
/
A101765.py
129 lines (117 loc) · 16.1 KB
/
A101765.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
121
122
123
124
125
126
127
128
#! /usr/bin/env python3
# A101765: Iccanobif semiprime indices: Indices of semiprime numbers in A014259.
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 A101765.")
print("The right column is A014259(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 A014259.
factors = [2465409832820948177, 61760730938862307327419757, 138208543626421, 13408523555526426167, 2642427361754889313424377,
126517954175813348810607859379, 3482957631081031, 2301092841269278596981137, 17532805657040801, 137106806128603177,
10872345235267020199046112144778543, 4021026661959716421086542451, 13538482368826351, 783567383821, 19836587839603,
21224760250905798887603961568973, 236139242942139638459097275462357, 34976544957914479, 4021026661959716421086542451,
1629325989012904876998323389061897, 2745163234558551149234814443694289930836334931, 171577174206951937709547357047,
704442602516897, 142915970947, 400277337437, 291668858197, 585396793, 925317641, 1002152939, 3784892957, 721971017,
1242586039, 2468952119221387031986722259351, 2782536667, 106678151, 232115502107, 122797513037, 1611005309, 42920897,
609680837, 177954781, 277526437, 64988801, 547274543, 20984006547805672954777, 3895086411132850585103, 34768395997,
635528246407, 122797513037, 1527415190201034633439, 10087445989, 521510501, 67900414343, 176359335277047446873,
10665429643829, 3402576649, 260950333997, 692135387, 431456383, 212993631973, 13549871197, 41781269, 30516001,
1087998970003853186552259031, 89707882485082192188293, 7277474936761332331178767, 914128982361687372227503, 25177267,
983641138107446872986029, 431657347491836216362009, 32654599, 16910251, 26389483, 6667909, 130893493,
27651754627277684504924018955925097]
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(a) + mpz(''.join(reversed(str(b))))
if n in (622, 630, 647, 817, 1247, 1402, 1422, 1477, 1649, 1781, 1818, 1867, 1874, 2115):
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 39
9 3 106
15 3 799
16 4 1941
18 4 2863
22 5 79199
32 8 66724797
37 9 908003573
46 12 821055378131
53 15 213376105160429
61 17 78428354544942119
62 18 143790460030897523
64 18 208721366514519927
79 22 7382112208472781089149
82 23 22442397678083530192123
106 30 827399885318087118997775388733
121 35 20508730434547333258078141563979855
129 37 5615564543039796708088251102738649291
149 43 2740242068784913933004733984902439194701133
153 45 104512830233692262087370443001638132930730379
229 68 11554090751787001369597437111938948823613707195042605587633917921341
241 71 15545323491523546576198272822905887185045112667639712800257181288021233
266 79 3266161070338327946961077368507424472287862784696188820395136906919460542852149
301 89 74749991317695408135475344671716264406530065935135933448476500115851633127626068029147357
381 114 383092152033550069632406544954588773359678708902401448353705826188413066001168317455861963393562185696641567477817
411 122 14581933886886146746815129869328500547763257198532872576839182109567714843135610828651593838048405582419583708260804455229
502 150 637871905841429068734257920904771605403730863351000621290313431432759208702926786519801728682607424836515209883803039306815131301666992671377315103977
622 185 hard 37901007985151122836637250102760662436239427777031500119038405218739137680691076046396287397306612776416143819229322421091531141505000383685380734873058161111946045432512796694941512723
630 187 hard 8055857905533737581764128027371579282830287757367635729292513977821127171069345373554043342326741133626348254471237828069310021633122878521670135028797195526200877066610887136873376496351
647 192 hard 892181701199792548938043827307588764986657803509819846218549062481687926158170256546458842001592740277359007126173678707877961791339143524286762022420205098178415374844544245352824706442280843
742 221 71916000678282592778814124349422929531475283008929944646052050707954166455551558682254393637581249434002323737535774931966438433803373624475975435960883064005124022370861141931216894915338424686203333191129848476951688963
817 244 hard 1372820083855439323462469068222609654239665597866690090121744944445044664745973886180588664504115221089063828412927882457380470612478219866866451060472130717426679847146633666239042510329910876271555860362800925931725539401262177126933212935361
987 295 5426643576548188892992336118577368489364212197281708258490224228101543295432595697750845662237595146859616824857033055357690156097479594868172242027897120364848590542457534566528520328912123458280528315704609011047971482948992501691094919490112258202310002353143431882993976413090477680032131303
1147 343 7116963384794156506810002238135210057369942234373062239112092428895579003856096279913834011848345397006253246606520963345208870171550024076472809869981104016697333702267027733525255685495198505831993732412512938538619734483708666155724421073957487529655466384387695608300746309328799571950980966185206248848656852337915590051073999224183929121
1246 373 1561722979323749163663244297497421696749155220212341095712265302713614016098349295110169418784275193837966540526206109128949946144315059217043149150303430667081938462632289281163775523311594781361834850136375848509140740957510478127934547684384472928834464492073020442449683294238528130144330247839953782164801835051941361865852187678199415192249995102516390039705103986033
1247 373 hard 4131293164900284746545300544384546260769868032240022128021218707962768174216573184360871788127778882177429539553239818452406043017473331945742876495684732151689455068441736397118335153975212550334881592263504901879441844543922252728798040376496746374561944066006300019648101788204710364651150183324735104186205851269230603054066963087733507252261927303599677923567909072817
1337 400 5616664902919371398142757289726650920747125426112190127676034175758899186598569678473533582932365288988986576364077661604153511460889903119450780500118594798488254895222979378706537765875542482799400123883303384872752802930691326152774968274308858173272992274212789001642987269042531203168065508337717280892951642331874437145639604164181728665715299121864484701019450932320587390523532386722712642249
1373 412 1684790067657334202979991561947898898045751363521924007183815418513016064612457495715679795075789588219496631583106299192424951514004595449004385579577912051869711825828135799702149061890980173845264060666046895556611262907132334474360855525998260355835504700789075683102365424897140709507701900386423893303954186479779181252836568859814554764707479219782774757738754881913055932457535683087160374911654625700491
1402 421 hard 4591646257644720808252096617132990611219146429037677861771447922902152402489660784983811449283886318413137988858630344662888578970657242954674638479438019971103098363145632335324677730379045868263270489574848816414890784391860698796093830143465780593955614848686346103588521894866586563021182349368079539641716049272741218092322447874473833048711317820227456975291005499509150764632739997368830084204096901440727193191781
1422 427 hard 4183464876313838054229901969183248947429846876379376503409414426552668814741763268683093024384162803274665862484220787984323168815887593474443165090607678728981228608456644163147233382772415910541721079736869942353473610087475623243632863865182122602749603656309751860549351522347015700589455438568311693385429790031900449467544653720170624083234419780929252666696061894815186912678925772208382108979616265790107433986885039117
1454 438 614029181161159707378543349893196819466158919932025204645274783331673217798076685465344502697736122775000400469689222493964952057670455588023679426492115727195994944560884430973444026954586994204290364809230909595296426612622741078866752315137322106869948810183127927366669985068671210496072418306139673450036994034156092168440039086139651051192253685646618524966605098055418195289836984810050168841120362119687546203994471653167372045787
1477 445 hard 8695548496248257821665427342127623453800535180853536652430043063270033750843848633311179638485721382107432920009855003755339230198087718059273211523047972546639596584532480267122131754876628653932937683562365622834349445916309552208554644320503946312066103880277481705457777080118937864292141266731160482598173983445373703868350760749182979793629548806264570542088353719729959544954560348440621472306127063900050921140301526777911741513077231637
1493 451 1102827360796542788186805526720383223951161176360774544714915168572584306292958445391138554939508600773580668400612934330111834649150615169529669275596977415235445114299410513929004213036413293926329644076808682581106562638534396577404870450200183852663250388149714369384695764378244482560337177904126102367990870719062011973872886226283607593390569808391893119951904187170941432329667374676317135143747266568159490919242711222532291940760970577749199
1537 464 36131352431142725944241937567198871886226036462167796820440827272769684261658896465925980102332108880552077046629586354432142323580402816486050994408435048977371986648620661789772260985112856099667418833784723463518337255546454173701235514843842091992029359293721746144246738839597154194351027973728881240739122040579272051515059664328279001014830716211023222900795146986119055173888063122438874107261324647736903229385146694971572405377233180933255792214061509931
1649 497 hard 14199545434378407850173296293967428650340809199969145089057620262825693482058115689433766307235922247952317896673316253892979304777036274402114170884915294764844687614470870714891993864510775203401506598028441429442395249596838242197287385844021980308370798860112591201341910923864598456420118156269333026765314552705074237205642445123601954313699201616995054414699709386973067657288841904676797077049433399340922613174845892068430009305006674323730915314209586887046270821649201328948214628668517
1781 536 hard 85621996981421204559514583971177558059821295726718964672479452026900802595736430601209996654244544524481777952079096958206278681730001860407766214747114572646612274227249805793295369210574940003385139360769524173595825597563873377517152925229201499037179113869677307789930499361144530040914329157670671163747775286484937958295808451517485308140163933836269410389807720709129992935168310124984825729984457768845248029774262589359949980678600739374292143963270586260855949343191827039039132510957691470793530720483336902016043246284811129
1818 547 hard 1069615662370679848220268218058143303769627228035511688427447052897006301397748824098684797492326289984776743416263479510896606366598791167379235777773655209088440128741986018520455019510772692240369743020019024642255665973010799884435845204448980665164726468903568267557247768159803786887241351637767889220004486681748780481759369496647199549619833539598862614028168858397299337448806773764006572607966371945107338410452875898108944946971264882996073510346452892099521466886208239064750723877043301423018801140276454195805509709982382898115377129
1835 553 1661131139634208033225744181113267168838194848212523765907221597669850061216775728715255790955945603195798682173664476282414920901461871024399555337548853912982751600905292418233553600057757529454584309685308777792773010109419971244086584985988604405308499982016631915802273747902672661710378010993706325862926651848397371100086063021995287005445653909255860336870449074737022568845297525658976854238153566646191817234712555142166246084191318058673449230459943391128539070706636743770957285132615169233299896487084641071781806181613639229940295851988801
1867 564 hard 135187794857434394998961354496352673002594227205515909010883511170296589433394725298925006704552582495540022829823477144234687717134058399021188058655220252014043967874105210234627756165334107554904157836086847323616018679075184183568672972868380960102723714823784118645863213191945355995440381467302085278574135207496048529973693661741134166358033290592035868963427022729699645599730246965553083271022436288152000579755518046311665947573231920571828986414367751231747837655929483838177793761320615883935434813386789185109462959777486048790862149309084890979688861
1874 565 hard 7385744586909680196790783604783033517791047777948631252144439960016526227138567950894811082312420462692675306035989439887537760951503160944600620941329183402191732512303105322688127280840520527066641250790179093781861883970633087355278569187060880285373942502960627821317029402524486298974695856310923420499373907972006066722162880739709994326775000760948735504803938190818079050553963734042332977934433586914463859316288608211287244219166006748050063138348947328638905203436886555717719284092804130237810013472361872108924748450150308033908819530027797790375547933
1967 594 658054813541367823321844313661689015505051424195044223603076795934199083542599515005603394620519051100625656925812694014254836897278326137930311214661772731229432783519228526859036126055634277362536926385471105280876881529481602473934949300931739170002506605061064222617184807563238259387105303728954483470008069135952966062483375094897953712035994983591988338818576842624243306870726793529854813562011544914849180994144207367588267518947919137686845323691343513404402278361867183097447158357528692750292867550807276654714037841230364631024870308106375367430965855621898605175484711158554673999
2115 637 hard 9540960846726488353740590463663530453772522725301322585989950354610440542897911498350644586761960050708453609151414355107760543842484082611895003968698807346236475501582424825070600636438983440482884287530671577368167740369603386139137575853508470406072046165454414823227929508512852634257049773018105867568147855303992204993551354112816111935172886062863864086640428708225206482483603629627708860930116848831068104298475412801202293611934304162679955386857127089818337760435796165428464723858401429947725222784818974098681743463195619023773790461681052697318941703751803869789945732572617198461355572064816379130663816186142079489522693
2265 683 14577520867172097737018099533828173084914345991501307150777525289707464757881872802727207366086087154958758900878348012591880714124676190348241668983373860182286776893739049518120740585301506666411368121584814373612059676019670583804925850243187894432297319862510873778674255063944812188078602942379524370484816016522669000471807462225580425717061489345529984693514368298233237374261183835300780283489777927906877509040586202989941146569275077340679446826437257171379143738726698975716683880178508007257485004279915775999261340725600394277944631199042838299750709057878869748483067010640329902270078434688779032244985075871039587412676786552576368487987811846815903802083598797527487
"""
# yafu "factor()" -one -pretest 40 -aprcl_p 6021 -aprcl_d 1