We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #49: Prime permutations
  4. Discussions

Project Euler #49: Prime permutations

Sort by

recency

|

23 Discussions

|

  • srikv
     + 1 comment

    100% python

    # Enter your code here. Read input from STDIN. Print output to STDOUT
from collections import OrderedDict

code_p = { 0:2, 1:3, 2:5, 3:7, 4:11, 5:13, 6:17, 7:19, 8:23, 9:29}

N, K = map(int, input().split())

n, N = N, N - 1 if N in [ 10**_ for _ in range(3, 7)] else N

primes = [ 0 for i in range(10**len(str(N))-1) ]

for i in range(2, len(primes)):
    for j in range(i*2, len(primes), i):
        if not primes[i] == 0:
            continue
        primes[j] = 1

def rootval(n):
    s = 1
    while n > 0:
        s *= code_p[n % 10]
        n //= 10
    return(s)

primes_d, k_vals = OrderedDict(), OrderedDict()
for j in ( i for i in range(2, len(primes)) if primes[i] == 0 and i >= 1487 ):
    if j < n:
        k_vals[j] = {}
    val = rootval(j)
    if not val in primes_d:
        primes_d[val] = [j]
    else:
        for k in primes_d[val]:
            if k in k_vals:
                for x in k_vals[k]:
                    if (j-k) % x == 0:
                        k_vals[k][x].append((j-k)//x)
                if not j-k in k_vals[k]:
                    k_vals[k][j-k] = [1]
        primes_d[val].append(j)

for i in k_vals:
    if len(k_vals[i]) < K-1:
        continue
    for j in sorted(set(k_vals[i])):
        try:
            if k_vals[i][j][K-2] == K - 1:
                print(*[ i+(x*j) for x in range(K)], sep='')
        except IndexError as e:
            pass

  • cyjackx
     + 0 comments

    itertools permutations, and groupby are very helpful things to learn for this one!

  • vidush_rk11
     + 0 comments

    Solution for n=1000000, k=3

    148748178147
296962999629
114831481318143
114974171971941
127131321713721
127391723921739
127571725721757
127991729921799
148214812181421
148313148148131
148974718979481
185035180385103
185935189385193
195433549151439
201612061121061
203532530330253
203592530930259
207472407727407
238872838732887
250875280780527
257935927392753
259133952153129
259815928192581
263173126736217
265975962792657
289332938329833
296696296996269
314893481938149
314893984148193
329696329993629
349613946143961
354074035745307
354913954143591
356715361771563
375615163765713
495475449759447
556035605356503
603736370367033
607576570770657
614876481768147
625976592769257
627736772372673
634996394964399
678296827968729
687137816387613
719477471977491
735897859383597
767177716777617
768198176986719
789418417989417
801918910198011
839878893793887
889379388798837
893879388798387
923819283193281
101603106103110603
101681106181110681
105251155201205151
105673306517507361
106243160423214603
110359510931911503
112643162143211643
113279117329121379
113497413719713941
113947143719173491
113947413719713491
114827121487128147
116027121067126107
117223122173127123
118549151849185149
118583151883185183
120277170227220177
120371123701127031
121367126317131267
122389122839123289
122599521929921259
122719172219221719
123259322591521923
123259522391921523
123863218363312863
125299192259259219
125597192557259517
126317131267136217
126359539261952163
126719172169217619
127157172157217157
127219172219217219
127643172643217643
127681172681217681
127717172717217717
127849172849217849
127859172859217859
128341234811341281
128473278143427813
129341134291139241
129497429719729941
129539521399913259
129671162971196271
129853529183928513
132059320591509123
132169162391192613
132383132833133283
133499133949134399
134593341953549313
134683483163831643
134909139409143909
135329533921932513
136753375163613573
137029203971270913
138641386411634181
138937139387139837
139547317459495371
139547437519735491
140167140617141067
140741144071147401
142907192407241907
142963192463241963
142969146299149629
143291192341241391
144593149543154493
146581415861685141
147283314827482371
147283487213827143
147293197243247193
147827214787281747
148171481171814171
148199481199814199
148469481469814469
148501481501814501
148531345181541831
148531481531814531
148633481633814633
149257195427241597
149731171439193147
149749471949794149
150209200159250109
151673163517175361
152081201581251081
153487345817538147
153749473951794153
153929539921925913
154871485171815471
154927214759274591
156041160541165041
157523355127552731
157543351457545371
158923238591318259
158927189257219587
159347457139754931
160231210631261031
160243210643261043
162011211061260111
162493239461316429
162593256931351269
162859215689268519
162947462719762491
163991391691619391
164023402613641203
165673351667537661
165877518767871657
166931391661616391
167159171659176159
169243246931324619
169859569189968519
170351350711531071
170641406171641701
170749174079177409
172021221071270121
172217221717271217
172439247193321947
172853352817532781
173699396719619739
173891178931183971
174061467101760141
174221224171274121
175783381757587731
175853515783855713
175963395671615379
178561517861857161
178933179383179833
180239230189280139
182339231839281339
182387281837381287
182389182839183289
182389281839381289
182593185923189253
183259582391981523
183587518387853187
184231234181284131
184523214853245183
184567514867845167
184999189949194899
185057518057851057
185131518131851131
185153518153851153
185327218357251387
185327518327851327
185363358613531863
185593358591531589
185693358691531689
185813518813851813
185831518831851831
185923189253192583
188933193883198833
189347193847198347
189377193877198377
189391193891198391
189851589181988511
190759570919951079
192043201493210943
192383192833193283
192383291833391283
192497492719792941
192961196291199621
193057351097509137
193247243197293147
193447471439749431
194087471089748091
194729471929749129
194749471949749149
194977497197799417
195343354391513439
196523256391316259
197203203971210739
197389197893198397
198323239831281339
198571578191957811
198647481769764891
200153205103210053
200587502807805027
201497204719207941
201947204719207491
203563253063302563
203771237071270371
204163412603621043
204371473201742031
205949250499295049
205991599021992051
207343274033340723
207367267037326707
207433240733274033
207469240769274069
209173291037372901
209359259309309259
213947473219732491
215497245719275941
215497247519279541
216493423961631429
216719217169217619
217367267317317267
217369239671261973
218453521483824513
218509521809825109
218531235181251831
218531521831825131
218579251879285179
218947248719278491
219547247519275491
220357225307230257
220373270323320273
223781273281322781
224591259421294251
225371275321325271
225931232591239251
225977259277292577
229343234293239243
229601262901296201
229637262937296237
230387280337330287
230389280339330289
231481234811238141
231589528391825193
232963236293239623
233489328439423389
234917239417243917
234931239431243931
234931329431423931
234961364291493621
234989239489243989
234989329489423989
235783387253538723
236909302969369029
237409304729372049
238093283093328093
238397283397328397
238519283519328519
238639283639328639
238727283277327827
238837283837328837
239417491273743129
239441294341349241
239641436291632941
239671276319312967
239843294383348923
240371243701247031
240551245501250451
243701473021702341
243707473027702347
244597594427944257
245083524803804523
245941594241942541
245963469253692543
245983594283942583
246599469529692459
246913429631612349
247193493217739241
250583528053805523
250741254071257401
250813528013805213
250841528041805241
253081302581352081
253937323597393257
253993593293932593
257893592873927853
258061560281862501
258319538921819523
258917528719798521
258949425899592849
259019592019925019
259121592121925121
259309309259359209
259387592387925387
259517592517925517
259577592577925577
259621592621925621
259643456293652943
260387283607306827
260753265703270653
261973617293972613
263111312161361211
263489324869386249
263491263941264391
263591395261526931
263983296833329683
265957596257926557
265961596261926561
270133321073372013
270587572807875027
271279271729272179
271351511237751123
271867276817281767
273149342971412793
273269322769372269
273271322771372271
273551512537751523
273827328277382727
273941493217712493
274139324179374219
275083527803780523
276113321617367121
277513327517377521
278269282769287269
279637327967376297
279649476299672949
279823289273298723
283133332183381233
283303332803382303
283501320851358201
285997589297892597
289543592483895423
289637628937968237
289643486293682943
293147342197391247
294341344291394241
294563624593954623
295861582691869521
296011629011962011
296243629243962243
296377329677362977
296473469723642973
296509629509962509
296683629683962683
296921629921962921
302171307121312071
302459352409402359
303187308137313087
303619603391903163
304537354037403537
305821328051350281
307121312071317021
307243340723374203
307409340709374009
307423324073340723
309461634901960341
312383321833331283
312709317209321709
312757317257321757
312779317279321779
313549453931594313
313849349381384913
314467364417414367
315389583391851393
316213321163326113
316219321169326119
316291639211962131
316697639167961637
317693639713961733
318559351859385159
319169619391919613
319547431759543971
319567357619395671
321851325181328511
321851352181382511
323383328333333283
323803328303332803
324397329347334297
324589428539532489
324619632941941263
324619642931961243
324791374291423791
325943342593359243
325943359243392543
325999359299392599
326479624973923467
327511521317715123
327517521377715237
328619628391928163
329347334297339247
329603362903396203
331549395431459313
334487384437434387
335149393541451933
337487387437437387
340169490631641093
342863384623426383
344909394409443909
345271431257517243
345601346051346501
345979549739753499
347057375407403757
347951371549395147
348629386249423869
348937349387349837
349007394007439007
349357394357439357
349409394409439409
349729394729439729
349759394759439759
349787394787439787
349967499673649379
349981394981439981
350789578093805397
356749475693594637
357047450377543707
357611516371675131
357619536791715963
357823358273358723
357989598973839957
358793597383835973
359267526397693527
360193631903903613
360497497603634709
361577517367673157
361763366713371663
361793639713917633
361967639167916367
363019633091903163
364079649073934067
364411414361464311
365471453617541763
366713367163367613
367127371627376127
368513615833863153
370169370619371069
370169673091976013
370241403721437201
370421420317470213
370483403783437083
370537537037703537
370571571037771503
371249394271417293
372149394721417293
372877377827382777
374219423179472139
374953459373543793
375967569773763579
376039639703903367
377827382777387727
378149398471418793
378151581731785311
378269382769387269
379649673499967349
380461408631436801
380641408361436081
380951385901390851
381569683591985613
381749439781497813
382061602831823601
382751582137781523
384317433817483317
384907407893430879
386039608339830639
386093608393830693
386401408631430861
389357393857398357
394619694391994163
395287589273783259
395677579637763597
395767579673763579
397549495973594397
398609690839983069
400753570403740053
401671406171410671
402371412037421703
403159459031514903
403181408131413081
403577574307745037
404557454507504457
405599455099504599
405917451709497501
407599574099740599
408131413081418031
408169604819801469
412591451921491251
412717417217421717
412739417239421739
415489448519481549
415651465151514651
415669465169514669
416393439163461933
416851451681486511
418351451831485311
418637641387864137
419477447197474917
422377427327432277
423869428369432869
424397429347434297
424597459427494257
426971694721962471
429467462947496427
429587489257548927
429631432961436291
429683462983496283
431581481531531481
431857435187438517
432589482539532489
432961463291493621
434909439409443909
435889485389534889
438169463891489613
438241443281448321
439759493579547399
439759597349754939
445937495437544937
446731461437476143
448169464819481469
449173471943494713
451183481513511843
451831485131518431
452671457621462571
453797495773537749
453799594379734959
453913493531533149
456061460561465061
456293459623462953
456293549623642953
458207480527502847
458501508451558401
458621642581826541
461957615749769541
462181641821821461
463219692431921643
463993699343934693
465187658417851647
467083607843748603
467183471683476183
467317614377761437
467431614437761443
467591514769561947
467591714569961547
468109641089814069
475289524789574289
479513497153514793
480167648107816047
480379487093493807
480761678401876041
480959485909490859
481157511487541817
481589514889548189
481633648133814633
481699648199814699
485063645803806543
485131513481541831
485603486053486503
486511651481816451
486721627481768241
489157519487549817
491537514739537941
491719719419947119
491783719483947183
491837714839937841
491977719947947917
493523542933592343
493567543967594367
495377734957974537
495617546179596741
497141719441941741
497411719441941471
503779537079570379
503791537091570391
504269562409620549
505823528053550283
506551556051605551
506593556093605593
507329705293903257
510793709153907513
512497542719572941
512671562711612751
512683682153851623
512767517267521767
516679566179615679
516721567121617521
516847584167651487
518767568177617587
521497724519927541
527941742591957241
529517752519975521
529673562973596273
530743534073537403
534571543157551743
535169565391595613
535609536059536509
536791597361657931
536801586301635801
536849586349635849
536867586367635867
538939539389539839
539677596737653797
540377543707547037
541483544813548143
541859545189548519
542599545929549259
545189548519551849
547951751549955147
552917575219597521
553607603557653507
556043605543655043
560297590627620957
560477605477650477
560543605543650543
560873605873650873
561373637513713653
561797679157796517
562591565921569251
562909596209629509
562931593261623591
562973759623956273
562979579629596279
566179615679665179
567101571601576101
567179571679576179
569671765619961567
572329752293932257
572387723857875327
572969576299579629
573161615137657113
573329752933932537
574631645137715643
576041670541765041
577627672577767527
578267582767587267
579263627593675923
579281715289851297
579521752519925517
580639630589680539
581369698531815693
585601586051586501
586301635801685301
586367635867685367
587927592877597827
588631638581688531
589273785923982573
592463625943659423
596009600959605909
596179756919917659
596243624593652943
596317613957631597
597901751909905917
598163639851681539
607471640771674071
607471674071740671
608743648073687403
610741614071617401
613169616391619613
613763663713713663
614881648181681481
617951791561965171
617959791569965179
617983739861861739
618509651809685109
618577651877685177
620777670727720677
621097671029720961
625397659327693257
629177712697796217
629467662947696427
629653662953696253
629747796247962747
631487634817638147
632473637423642373
637079670379703679
637787687737737687
637817687317736817
638063660833683603
645397649573653749
645397659473673549
645739794653943567
649801806941964081
650779705769760759
652381652831653281
654739794653934567
656291659621662951
658633663583668533
658639663589668539
662789667829672869
663713713663763613
667103671603676103
668719768169867619
670487708647746807
671003716003761003
671087716087761087
671161716161761161
671249716249761249
671477716477761477
671591716591761591
671633716633761633
673297732967792637
675179715679756179
678289682789687289
678833683783688733
679517719567759617
679829689279698729
680161680611681061
681731731681781631
685739789653893567
687107781607876107
687131781631876131
687389687893688397
687517781567875617
687721782671877621
688717788167887617
689321836291983261
689713813697937681
689713831697973681
695603696053696503
695749745699795649
697013701963706913
697019701969706919
701609706109710609
703499703949704399
703753737053770353
707857757807807757
708599759089809579
709823809273908723
710839801973893107
710863760813810763
711947714719717491
718259785219852179
718657785167851677
719801810791901781
721859752189782519
723169726391729613
723493732943742393
725929759229792529
725993759293792593
726487784627842767
733189783193833197
734887784837834787
734933739433743933
738401804371870341
738923789323839723
739861861739983617
740561745601750641
740891807491874091
741283784213827143
742817782147821477
744389789443834497
748183781483814783
748711781741814771
749171771941794711
749893798943847993
751277751727752177
751481754811758141
754981851749948517
757807807757857707
757829758279758729
759641764591769541
760169760619761069
761879816779871679
762917771269779621
766813816763866713
776719777169777619
778237827737877237
780163780613781063
782129827129872129
782231827231872231
782251827251872251
782429827429872429
782791827791872791
783283827833872383
783421812347841273
785921789251792581
786031831067876103
786211826711867211
788387837887887387
793843843793893743
796487846977897467
796711797161797611
798263862973927683
800159805109810059
800743804073807403
801949891049980149
804197809147814097
807193897103987013
807409840709874009
807427824077840727
809579895079980579
809581859081908581
809587895087980587
812969862919912869
814873848173881473
814937847139879341
816329839621862913
816859851689886519
819653869153918653
822971872129921287
823169826391829613
824399829349834299
825959859259892559
825997859297892597
826979876929926879
827969897629967289
829639832969836299
830989880939930889
832519892351952183
835979897359958739
835987859783883579
837149839471841793
838931839381839831
848933849383849833
849731871439893147
849973899473948973
855607856057856507
856043860543865043
859049908549958049
859223892523925823
859279875929892579
860971876019891067
863897868793873689
864901906481948061
865937869753873569
867121871621876121
867827868277868727
874091907481940871
876719877169877619
879031893107907183
879269928769978269
879287928787978287
891859895189898519
892643928463964283
892733932783972833
893881938881983881
895319913589931859
899429948929998429
907433940733974033
911269916219921169
912497942719972941
914873948173981473
916859951689986519
918529951829985129
919253925391931529
920743924073927403
929609962909996209
929671962971996271
929693962993996293
932471937421942371
934951939451943951
950161950611951061
971851975181978511
983987988937993887
990371991037991703
992963996293999623
993493993943994393

  • VeeJaeay
     + 0 comments

    If you are having timout issues, I recommend implementing sieve to get the relevant prime numbers, and using itertools permutations. The key is not to run itertools on every prime. As you go along, apply the same permutation list to all the primes in the list to optimize speed. I recommend splicing only the larger primes. Good luck!

  • VeeJaeay
     + 1 comment

    Leading zeros? Clarification would be nice