A Sobering Problem

Anything goes, but keep it seemly...

Re: A Sobering Problem

Postby Leren » Thu Oct 03, 2013 8:06 am

Smythe Dakota wrote:Let's do it with numbers. Somebody come up with two 5-digit prime numbers, and ask for a path between them, changing one digit at a time, such that every intermediate 5-digit number is prime.

Bill Smythe

As far as I can tell there are 8363 five digit prime numbers ranging from 10007 - 99991. Any two such primes can be connected via a minimum path of at most 10 steps (from the first prime). There is only 1 pair of five digit primes, 88259 and 99721 where a 10 step connection path is required, one such path being:

Code: Select all
   88259
 1 78259
 2 79259
 3 79159
 4 79151
 5 79181
 6 39181
 7 39161
 8 39761
 9 99761
10 99721

A minimum connection path between the lowest and highest 5 digit primes (10007 and 99991) requires only 5 steps, one such path being:

Code: Select all
   10007
 1 90007
 2 90001
 3 90901
 4 99901
 5 99991

What else would you like to know ?

Leren

<Edit> Corrected error in first path and improved presentation to be more consistent with previous discussions on word ladders.

Leren
Last edited by Leren on Thu Oct 03, 2013 9:29 pm, edited 1 time in total.
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby JPF » Thu Oct 03, 2013 9:53 am

Leren wrote: This is only required for 1 set of five digit primes, 88259 and 99761

What do you mean?

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: A Sobering Problem

Postby Leren » Thu Oct 03, 2013 11:04 am

JPF wrote:
Leren wrote: This is only required for 1 set of five digit primes, 88259 and 99761

What do you mean?

JPF

What I mean is that my results indicate that if you pick any other pair of 5 digit primes then it is possible to construct a prime number ladder between then with less than 10 numbers
(or 9 steps from the first number in word ladder speak). The other example I gave was 10007 <-> 99991 for which a minimum ladder would have 6 numbers (5 steps from the first number).

Leren
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby JPF » Thu Oct 03, 2013 12:23 pm

How do you go from 10111 to 65563 ?

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: A Sobering Problem

Postby Leren » Thu Oct 03, 2013 9:43 pm

JPF wrote:How do you go from 10111 to 65563 ?

JPF

A minimum connection path from 10111 to 65563 is as follows:

Code: Select all
   10111
 1 10211
 2 12211
 3 12251
 4 32251
 5 32261
 6 32561
 7 32563
 8 62563
 9 65563

I've corrected an error in the longest minimum path which now goes from 88259 <--> 99721. I've edited my original post to reflect this and make the presentation consistent with the style we've been using for word ladders.

Leren
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby Leren » Thu Oct 03, 2013 10:54 pm

My results for connection ladders for 5 digit primes indicate that every prime is connected to every other prime via a minimum sized ladder of at most 10 steps (from the given prime).

The following table shows the number of primes with a given minimum ladder size.

Code: Select all
Ladder Size        No of Primes

     7                  3
     8               7650
     9                708
    10                  2
                    -----
                     8363

This shows that every 5 digit prime can be connected to every other 5 digit prime. This is not the case with word ladders - there are lots of words that can't be turned into other words by changing one letter.

So you can obviously produce a ladder that includes all 5 digit primes by changing one digit at each step. What's not obvious is whether you have to repeat a number in the ladder. So the question arises:

Code: Select all
What is the longest ladder of 5 digit primes that can be made by changing one digit at each step without repeating a number ?

At the moment I can't answer this question (my code is designed to find shortest paths, not longest paths). I'll give it some thought but in the meantime if anyone can answer this question please fee free to post the answer.

Leren
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby David P Bird » Fri Oct 04, 2013 9:59 am

Leren, I have little idea about how your code works, but if you are looping through possible exchange digits it's possible to reduce the candidates to test using the following:

All prime numbers must be either 1 or 2 mod 3
So for example for a 1 mod 3 prime, any 1, 4, or 7 can't be replaced by 0, 3, 6, or 9.
This reduces 9 possible exchanges to 5 or 6
As the options are tested it should therefore be worthwhile to monitor the modulus of the current prime and loop through the candidates in a look-up table to avoid testing non-starters.
Of course for the final digit, the choice is even more restricted.

The only other thought of any merit that I've had is:

Using letters, this family of words provides a very versatile method of extending a ladder
Pat
Pet
Pit
Pot
Put
If any of the words is needed elsewhere it can easily be taken out with no ill effects, and there are also multiple opportunities for managing detours between any two of them.
For the prime ladders it may therefore be worth specifically looking for these and noting the most promising ones.

When checking for a repeated prime a sorted list of those already used may be the way to go. This could include a tag system showing if the prime is necessary or an optional family member.

David
David P Bird
2010 Supporter
 
Posts: 940
Joined: 16 September 2008
Location: Middle England

Re: A Sobering Problem

Postby Leren » Fri Oct 04, 2013 12:13 pm

Here's my first attempt, a ladder sequence of 3624 5 digit primes - no doubt good bed time reading.

Hidden Text: Show
25801 95801 95401 15401 12401 12301 18301 19301 10301 10331 10333 10313 30313 36313 36013 33013 43013 42013 42073
22073 12073 12973 15973 15073 15013 15083 95083 35083 32083 32003 32503 32533 32563 32569 32069 32089 32189 37189
67189 67489 17489 17789 10789 10739 10139 10939 10039 70039 70079 78079 78979 18979 18919 18913 18713 38713 30713
30703 30803 30809 30859 10859 10159 10259 15259 15289 10289 12289 12889 15889 10889 16889 16829 12829 12821 14821
14851 14551 14251 12251 12253 10253 30253 30203 32203 32303 32603 32803 32833 32233 32633 62633 62683 62383 92383
92387 97387 97187 97787 57787 58787 48787 42787 42797 42697 40697 40627 80627 10627 10657 10457 12457 12497 62497
69497 69493 69463 19463 19423 19427 19477 17477 13477 13177 11177 10177 80177 20177 20107 20147 20143 20123 40123
49123 29123 29023 29423 29473 29873 29833 29333 49333 49633 29633 25633 25603 25673 25643 25943 27943 27743 27773
23773 23873 23893 26893 26293 86293 36293 36493 30493 30497 36497 36097 36697 36607 31607 31307 31327 31397 91397
99397 99377 92377 93377 63377 63397 63337 63331 63311 33311 33911 93911 90911 90971 30971 30671 80671 80071 81071
81001 81701 21701 21001 21011 21017 21317 21517 21617 21611 41611 41681 41381 41281 41221 41621 41627 41647 41641
41651 41051 41057 41017 47017 27017 27917 27947 27967 27961 27061 27011 87011 87911 87211 67211 67231 67931 67933
67943 66943 76943 76243 76249 56249 56269 56209 56509 56599 56099 46099 46091 46051 46451 16451 13451 43451 43151
33151 31151 31159 31153 91153 91453 91493 91463 61463 61483 64483 34483 34583 34513 34313 34319 34919 24919 24917
24977 24077 24071 23071 23011 23017 23027 23627 23629 23669 22669 22639 25639 25339 25439 24439 24419 54419 54449
14449 84449 80449 80849 20849 20749 20549 20149 60149 60169 30169 30139 39139 39119 32119 12119 12619 12611 12641
12041 12541 22541 22571 28571 28541 28549 28579 28279 28219 28229 28729 38729 31729 31721 31727 21727 21737 21767
21757 21787 21487 51487 51437 51439 51839 51829 51859 51899 51199 51193 51593 50593 50093 40093 40193 40993 40493
40499 40429 40129 40529 30529 33529 33629 53629 59629 59929 59921 59021 59023 99023 99823 90823 40823 40853 45853
45823 45863 41863 41843 41543 31543 31547 37547 37507 37307 37397 37997 37957 37967 67967 67927 62927 65927 61927
64927 68927 98927 98327 94327 14327 13327 13397 13597 11597 11497 11197 51197 53197 53117 53617 63617 60617 65617
65657 61657 61687 41687 44687 44087 44017 74017 74717 74797 74597 74527 74521 74561 74531 74551 77551 17551 15551
15541 75541 78541 78041 18041 18049 18149 15149 15649 15619 75619 75679 73679 73609 23609 43609 47609 47659 47699
37699 37649 87649 81649 81647 81047 81017 81019 21019 31019 31069 31039 71039 73039 73079 76079 75079 75479 71479
71471 71411 41411 41413 41813 41213 41203 41243 41143 41141 41131 45131 15131 15731 15737 15787 15287 15217 55217
55817 55819 55219 55229 55829 57829 57859 57809 47809 47807 47207 49207 59207 59209 59009 19009 13009 13003 13063
13093 13033 13037 10037 10937 10957 17957 17959 17939 17539 17509 27509 27409 27407 27107 17107 15107 12107 12101
15101 15161 15661 15061 16061 16067 16087 16487 13487 93487 43487 43787 43789 13789 13759 13159 11159 11959 15959
12959 12953 12553 18553 18593 11593 71593 71563 21563 21569 21169 21163 21143 21193 21191 21101 21121 21821 26821
26921 56921 56923 56993 16993 16903 13903 13913 13613 12613 12713 14713 14717 14747 14447 16447 16417 13417 13457
19457 19417 59417 59497 59407 51407 21407 20407 20807 20809 20879 23879 28879 28979 28909 28409 28309 25309 25303
25307 45307 75307 75707 72707 72797 75797 78797 78707 78307 78317 77317 74317 84317 84347 14347 54347 54377 53377
53077 50077 50177 40177 40127 40427 10427 15427 16427 16477 56477 56467 56267 56263 96263 96269 86269 86369 16369
16361 15361 15461 15761 15767 15667 10667 10867 10067 10069 10099 10009 10709 10729 13729 13721 13421 12421 12451
12491 17491 47491 42491 48491 45491 45497 48497 48487 42487 42467 42457 42437 42433 12433 18433 18443 11443 11483
19483 19433 10433 10133 10163 12163 12143 12043 42043 42083 42023 42223 72223 72227 72277 22277 22279 22271 22871
21871 21851 24851 24151 94151 54151 54101 54121 84121 84421 84221 87221 87223 81223 81283 51283 51287 50287 50207
56207 56237 56239 53239 53269 23269 23209 23201 29201 79201 79801 49801 19801 19841 19541 39541 39341 30341 30841
30871 30271 30071 90071 90001 90011 90017 90917 90907 90107 80107 80147 50147 55147 25147 25247 25447 65447 68447
68443 68449 38449 38749 38747 34747 34847 39847 37847 31847 36847 36877 36677 30677 80677 80657 80651 80621 85621
55621 55631 55633 55333 55331 15331 13331 13337 10337 60337 60637 60737 60037 40037 40039 40639 40939 49939 49139
99139 79139 79133 79333 71333 71353 71453 71413 71419 71719 74719 74419 14419 14411 13411 16411 11411 11471 11971
51971 51941 51341 41341 41351 44351 44381 47381 47351 46351 46751 46757 46457 96457 96857 96557 92557 92957 52957
52967 52567 52067 52057 52051 50051 59051 59951 50951 70951 70901 72901 52901 52501 52511 52561 82561 86561 89561
89563 81563 81553 81559 87559 84559 84509 86509 86209 36209 36229 36529 36929 86929 86629 80629 80929 50929 50923
50023 50123 70123 70823 79823 79843 49843 49823 48823 48523 48533 44533 45533 35533 35537 35527 35327 35323 32323
32321 38321 38327 34327 32327 62327 62323 12323 12373 15373 15313 15413 15913 19913 19973 19979 79979 79379 79399
79699 79697 79693 79193 49193 49103 39103 30103 30113 33113 33613 33713 36713 26713 26717 22717 22727 52727 42727
42737 47737 47717 47711 47741 47743 47543 44543 14543 14143 14149 14159 34159 35159 32159 32059 32009 82009 82003
83003 23003 22003 92003 62003 67003 67073 57073 57773 50773 20773 20173 20183 26183 26683 26693 26993 22993 22943
42943 42443 42463 42473 62473 62483 62983 32983 32183 31183 31181 30181 70181 70121 70111 10111 50111 50411 58411
58711 98711 28711 28751 27751 27791 27793 25793 25733 25933 25903 85903 85933 35933 35923 35963 35993 38993 38953
38653 38603 34603 34613 34213 34217 54217 54917 54919 54949 54979 24979 24179 44179 44189 47189 47119 44119 44129
44159 44959 44953 41953 41957 41257 11257 11057 11087 11887 11827 11867 71867 79867 79367 75367 75167 78167 78367
58367 54367 54667 55667 52667 52627 50627 70627 70607 76607 73607 63607 63697 63997 13997 13697 12697 22697 27697
28697 28627 28687 26687 23687 23087 23057 23059 23029 20029 20021 20011 20611 29611 27611 27691 22691 22391 12391
10391 10091 10891 10831 10631 30631 60631 60601 63601 64601 67601 67631 61631 51631 51131 51031 61031 21031 22031
22051 82051 32051 32057 37057 47057 47051 43051 43651 43691 43391 43591 43597 43577 13577 63577 67577 67579 37579
37571 37511 37517 31517 31511 31513 31013 21013 21613 21673 51673 51973 57973 52973 72973 72673 72073 72043 72643
42643 42743 12743 12763 13763 13963 16963 19963 19163 13163 13103 16103 16183 16187 16987 11987 17987 17981 16981
16931 16831 11831 14831 14731 14737 14797 15797 15497 17497 17417 47417 47917 47317 87317 89317 99317 98317 95317
95717 65717 25717 25747 20747 20347 21347 71347 71387 71887 74887 74897 14897 14827 14627 14629 14621 14321 11321
11821 11801 11807 11897 41897 41893 21893 51893 56893 56093 53093 53693 53593 53597 53591 53891 53897 56897 55897
55837 65837 85837 85817 88817 88813 88811 87811 87511 87517 87557 87587 87547 67547 67447 67427 27427 57427 57527
27527 29527 29537 29531 19531 19031 19001 19501 29501 22501 62501 62701 42701 42709 42409 42403 42407 42307 22307
82307 72307 72907 72937 70937 30937 30637 30697 90697 90647 90847 90947 90997 93997 93497 96497 96997 91997 91967
91957 95957 95257 65257 65557 65357 25357 20357 20359 20759 20789 80789 80749 80149 80141 70141 70241 70201 70001
70009 70099 70999 70949 70849 40849 40829 30829 30839 35839 35869 35809 35801 35201 35251 32251 92251 92951 52951
56951 53951 43951 43961 43963 43933 43913 43613 43633 23633 13633 16633 16693 16691 13691 10691 10601 15601 15641
45641 42641 92641 92647 72647 77647 77047 57047 57077 17077 17977 87977 57977 57947 57347 51347 51647 21647 71647
71147 71167 71161 71761 71861 74861 74821 74831 74731 74771 44771 44171 44071 14071 14051 14057 14657 11657 17657
17659 17159 17189 17389 17383 17783 77783 77713 77743 77747 77347 77447 77417 77017 75017 75617 77617 77687 70687
10687 10487 40487 40483 40423 40433 40933 47933 47939 47639 49639 49669 29669 28669 28663 29663 29863 29063 23063
22063 22013 82013 81013 81043 81049 81041 87041 17041 77041 77641 87641 87643 87443 87943 57943 57143 57149 53149
33149 33119 30119 38119 18119 11119 11117 11617 41617 44617 44657 44651 44621 44221 44201 43201 43291 43991 49991
69991 69491 69191 39191 33191 33791 33391 31391 21391 21397 27397 27367 27767 27737 27739 27799 21799 21599 23599
20599 20399 23399 13399 13799 13709 19709 39709 39779 39719 39019 34019 34519 34549 34543 94543 94547 94847 94849
97849 97841 94841 34841 34849 34649 31649 30649 60649 60659 60259 60289 60089 30089 35089 95089 95989 45989 45589
42589 12589 10589 10559 10459 10429 70429 70489 70289 70249 70549 70529 90529 90527 90127 60127 60427 60497 60493
63493 63499 64499 54499 24499 84499 34499 34439 34469 30469 30869 32869 32369 92369 52369 22369 20369 10369 10169
18169 18869 18859 13859 13259 19259 19759 19753 10753 10853 12853 42853 42859 22859 21859 21059 21559 21529 21521
51521 51511 51517 81517 81547 81527 11527 11927 11923 11903 10903 10909 10979 70979 70379 70879 40879 44879 44279
44273 44263 41263 71263 71233 71237 31237 31247 31277 21277 21577 21587 11587 11287 71287 71987 61987 61981 41981
41081 31081 31051 35051 35053 35353 32353 32363 37363 37369 77369 77269 77569 17569 17579 17519 11519 11719 11789
11489 14489 19489 19289 18289 18229 16229 16249 13249 13049 13099 23099 23899 23819 25819 85819 89819 89809 89009
49009 49109 99109 99809 98809 98807 98867 98897 88897 88867 28867 28817 21817 22817 27817 27847 25847 85847 85247
85243 85223 84223 82223 82723 82721 52721 52021 55021 85021 89021 29021 23021 26021 26029 24029 24023 20023 21023
81023 81083 11083 14083 14033 64033 64633 14633 14533 14503 12503 11503 51503 53503 54503 56503 56501 56591 50591
50599 50539 60539 65539 62539 68539 68239 38239 38839 39839 39829 69829 69809 69709 63709 63703 63773 53773 54773
54673 55673 55603 55609 53609 53639 53633 53623 53923 33923 33023 33029 33829 33329 33349 33347 63347 63317 63367
63667 63647 63649 63629 65629 65029 65129 65929 62929 62939 62639 68639 68699 68899 98899 98869 98669 38669 38699
38693 37693 37493 67493 67499 69499 49499 46499 42499 42299 42293 44293 44203 44207 44507 47507 47407 47497 47797
47777 41777 41177 41179 48179 48679 48479 98479 96479 96179 96779 96979 96959 26959 26953 26153 22153 52153 52183
52189 22189 22109 24109 24107 24407 84407 83407 83477 83417 83117 23117 23917 23417 26417 26017 29017 29027 29927
49927 49627 49697 69697 19697 19597 89597 83597 73597 71597 41597 40597 49597 49537 49531 49031 69031 79031 76031
76091 16091 16001 16007 13007 13907 13901 16901 16301 16381 86381 86351 86311 86111 26111 26113 26813 56813 56713
56711 56731 56131 56171 26171 26161 26861 26261 26561 76561 73561 23561 23563 93563 93523 99523 99529 93529 93629
93229 13229 13219 19219 19919 12919 12911 12211 12241 12841 12941 32941 32341 32141 62141 62171 65171 68171 68111
28111 25111 25121 45121 45161 45181 46181 46171 86171 86131 84131 44131 42131 42139 42179 92179 92479 92419 95419
95413 95213 95233 92233 99233 99133 99833 89833 80833 50833 50333 59333 59233 59263 59063 59069 59669 59659 59359
59399 59699 53699 53899 53299 56299 36299 36269 36469 33469 33569 33589 37589 67589 60589 60889 60689 63689 23689
23189 43189 41189 31189 31139 37139 37339 37337 31337 31357 31387 41387 41357 40357 40351 40751 48751 48757 49757
49787 49727 19727 15727 15227 15277 15377 75377 75337 45337 42337 42397 42197 42157 49157 49177 49877 39877 39827
69827 69427 69467 62467 72467 72167 72367 72767 42767 92767 92467 92461 92861 92801 92401 96401 96431 96731 95731
75731 75931 85931 85331 85361 85661 88661 18661 16661 16631 16651 10651 10151 13151 13121 13127 13187 13687 13627
17627 17327 17387 17317 17377 12377 12379 12979 12479 12473 12413 18413 18313 18311 18211 18217 18917 18911 98911
95911 95111 95101 95131 95531 35531 35831 35851 33851 33857 23857 23557 23357 23327 23827 23227 23297 26297 28297
28097 28597 28517 28537 23537 23531 22531 82531 82031 82037 82237 32237 32297 32497 32491 32441 32401 35401 35407
35447 85447 85427 85027 85037 25037 22037 12037 12437 14437 84437 83437 83737 81737 84737 84731 84431 84401 14401
18401 18451 15451 85451 85751 87751 87251 57251 57259 55259 55249 55849 55889 52889 72889 72869 72169 72161 72101
78101 78301 78341 18341 18541 48541 45541 25541 55541 52541 52571 82571 82591 83591 89591 89891 19891 14891 17891
17791 57791 47791 47591 37591 37561 37501 47501 47581 27581 27481 27431 27031 28031 28051 20051 20071 20771 28771
68771 68371 38371 38671 39671 59671 59611 59621 59221 50221 50021 50321 50341 50441 59441 59443 29443 29483 29383
29387 19387 19087 14087 14887 15887 15187 15137 15139 15739 15733 55733 55933 55931 55901 55921 55721 54721 54421
54401 54403 54413 51413 51419 51479 56479 26479 36479 36779 32779 32719 32713 32717 32797 32707 32507 92507 92567
82567 89567 29567 23567 13567 13267 13967 13367 18367 18397 18797 18787 78787 78487 78437 75437 75937 75997 79997
79999 71999 71399 71329 71389 41389 44389 47389 45389 45289 75289 75689 75629 15629 15329 15319 15349 15359 15859
15559 19559 19553 16553 66553 66853 67853 87853 81853 81353 81373 81973 81971 81671 89671 89071 83071 83077 80077
81077 81677 81667 31667 31657 31687 31627 61627 61637 61667 64667 64067 63067 63467 63463 13463 93463 93493 96493
16493 16433 16333 19333 19373 19273 10273 10223 30223 37223 37253 31253 91253 91283 93283 93083 33083 36083 36383
36343 36353 36373 36973 36923 86923 80923 80963 80263 80233 80231 20231 29231 79231 19231 89231 82231 82261 82267
82207 82007 12007 10007 10607 15607 15307 15907 15901 15971 15671 12671 12601 82601 82609 83609 83009 73009 73309
79309 19309 19379 18379 18371 48371 44371 24371 24671 24691 24091 22091 27091 27191 77191 17191 17291 17299 17239
77239 77249 77549 37549 37529 57529 57559 57059 47059 44059 44029 44021 44027 44927 41927 41947 41941 71941 71341
21341 21841 21881 21481 21401 21491 21991 21961 61961 61261 61231 61331 61333 61343 61543 61643 61843 67843 67043
67033 67733 27733 27763 25763 25703 75703 75793 85793 82793 88793 28793 24793 24799 24709 24809 24859 28859 28759
29759 29753 20753 20743 20543 20593 20393 20333 20323 20353 60353 60343 66343 66383 56383 56333 56393 58393 38393
31393 35393 35593 35597 35507 35107 36107 36137 86137 83137 83177 83777 43777 43177 43117 43717 53717 53719 51719
51713 57713 54713 74713 71713 71711 77711 77611 77681 17681 19681 19181 39181 79181 73181 33181 33161 36161 36191
36791 66791 62791 12791 15791 15391 19391 19381 19081 14081 14011 12011 12511 22511 22111 22171 25171 35171 35111
65111 65119 62119 62189 82189 92189 92119 99119 59119 89119 69119 69109 66109 66103 76103 46103 46183 46187 36187
36587 96587 96787 96737 96757 96797 96097 16097 12097 12197 14197 14107 14177 74177 74167 74161 74101 44101 44701
84701 83701 83761 63761 69761 69763 60763 60773 60793 60703 90703 90803 95803 95003 97003 97001 93001 93901 90901
90401 90407 90007 94007 94009 91009 92009 52009 55009 56009 56809 36809 33809 63809 65809 65899 35899 35099 32099
32029 30029 30059 30559 30259 31259 31249 71249 71849 71899 71699 77699 67699 67679 57679 54679 54779 54709 94709
99709 99409 39409 39209 89209 89203 83203 23203 23603 23663 20663 20063 20563 20533 24533 84533 86533 86539 86239
80239 80209 80809 80909 89909 89959 89659 89669 89689 89989 99989 99089 90089 90289 96289 96989 56989 56929 51929
51329 51349 51343 51383 11383 11393 11399 10399 10799 10499 13499 43499 43399 46399 26399 29399 89399 89899 89839
89939 83939 83933 13933 11933 11939 11839 18839 17839 57839 57139 57119 57179 57173 57193 57793 87793 87293 81293
81233 41233 41231 40231 50231 53231 58231 58211 28211 27211 27281 27283 21283 61283 61223 31223 31123 31121 91121
91151 61151 64151 64153 64453 64403 61403 61493 21493 28493 18493 18793 18743 18043 18047 11047 51047 50047 53047
53087 50087 50387 40387 47387 47087 40087 40787 90787 93787 93887 93287 93281 93251 93151 97151 97159 97459 92459
98459 98419 93419 53419 53411 43411 49411 46411 46441 46471 76471 76481 70481 70487 70457 70657 70667 70867 40867
46867 46807 46307 46301 46381 46681 47681 47981 47911 17911 17921 17923 12923 14923 14323 14723 14753 14783 14683
17683 17183 17483 37483 37489 77489 77479 77471 73471 74471 74411 79411 29411 28411 98411 98011 98017 96017 36017
86017 89017 84017 84011 84811 94811 91811 91813 11813 19813 19213 89213 89513 89113 39113 39313 39317 35317 33317
33617 33619 13619 13649 13669 13679 13879 13877 73877 73867 77867 77167 77267 77261 67261 67961 97961 91961 99961
99971 59971 39971 39371 99371 99571 97571 97561 94561 95561 95461 96461 96451 36451 36457 36467 36067 36007 36037
36637 33637 33647 33547 33587 33487 33457 33757 33751 13751 13781 13681 11681 11981 31981 31991 31091 30091 30011
30013 37013 37313 87313 85313 55313 55813 95813 95713 98713 68713 68711 68311 78311 48311 48313 58313 58363 52363
52163 82163 82463 82963 52963 56963 58963 58967 58907 58901 58909 58109 58129 50129 20129 20929 20921 22921 28921
28901 22901 22961 22963 22973 22573 32573 31573 91573 98573 98473 48473 48073 48079 48049 48649 46649 16649 16619
16319 16519 14519 14549 44549 41549 41149 11149 12149 12109 12809 12899 92899 92893 92693 32693 32993 32933 38933
38903 38803 35803 35603 95603 95203 92203 92503 93503 93553 93053 96053 90053 50053 59053 59093 59393 79393 79397
79337 79357 59357 59377 50377 50777 80777 80747 80347 80387 80687 80681 80611 60611 60661 60161 60761 62761 62861
62801 62401 69401 69403 69473 63473 68473 68477 67477 77477 77977 72977 72997 70997 70991 70921 70321 10321 17321
17021 17027 11027 61027 61057 61051 61091 61001 51001 55001 55051 55061 55661 55691 45691 45697 45667 85667 85627
89627 79627 79687 74687 74587 74507 70507 40507 46507 76507 76597 56597 26597 26497 26437 56437 56431 51431 51421
51481 51581 51551 11551 11251 18251 18253 18257 98257 98227 92227 42227 42221 48221 48281 44281 42281 42283 40283
40883 40813 40013 45013 45053 45953 45959 41959 41659 41609 41809 48809 48889 46889 46819 44819 40819 47819 47869
47569 47563 44563 48563 98563 98543 58543 50543 40543 43543 43943 43973 48973 18973 10973 10993 10093 17093 17293
47293 45293 45233 45433 45413 65413 65213 67213 67219 68219 62219 62213 68213 68813 68819 88819 88919 84919 64919
66919 66949 66947 26947 26347 26317 26357 26387 26987 26981 26681 26881 26801 26501 26701 66701 66601 96601 93601
93607 93407 53407 53401 53101 53201 55201 52201 52301 52361 52321 52391 42391 49391 49891 43891 43801 41801 41201
49201 49211 49811 46811 46817 45817 45317 45377 45677 35677 35671 36671 36871 37871 34871 34877 64877 64879 64871
64171 34171 37171 37181 87181 84181 24181 24121 94121 94621 91621 95621 25621 25601 25609 65609 64609 64679 60679
90679 90379 90373 60373 60383 50383 57383 87383 87583 87523 87623 87629 84629 54629 56629 36629 38629 38639 38039
34039 34939 14939 44939 44839 44809 84809 84869 14869 14867 14767 54767 56767 36767 38767 38567 37567 37537 32537
32531 32561 38561 38261 34261 34361 34381 34781 36781 36721 33721 73721 73121 73421 72421 72221 72229 70229 70223
60223 60923 60913 60917 60017 60317 60217 60257 60457 69457 69857 69877 99877 99577 19577 12577 12547 12647 12347
92347 92317 92357 92353 72353 75353 75553 75583 75983 35983 39983 39383 39323 39343 39043 39023 35023 35027 35227
75227 75527 75521 75511 55511 55411 55711 55717 55787 51787 54787 54287 57287 57487 57467 59467 59447 19447 11447
11467 15467 17467 17167 17117 17137 17737 57737 57731 57751 67751 61751 61651 61681 61381 65381 65581 65981 62981
62987 32987 37987 97987 67987 67957 65957 65951 65851 65881 65831 65731 35731 35771 31771 31751 21751 22751 22721
12721 12781 10781 10181 10141 19141 19441 19421 16421 16921 16927 26927 26627 20627 20327 29327 29347 29147 29137
29131 99131 99191 95191 45191 45197 45127 45137 45737 45767 75767 75787 75781 75721 78721 78121 18121 15121 19121
49121 48121 48821 38821 38861 37861 37061 34061 34961 33961 33931 30931 30911 32911 32971 32371 32377 38377 98377
98387 91387 91381 92381 92581 99581 29581 39581 59581 54581 54181 52181 42181 42101 42901 42961 42461 72461 72431
72031 72931 72911 72211 72251 72253 72953 42953 42923 72923 72823 12823 16823 96823 96821 66821 36821 39821 39841
39241 30241 30941 30949 34949 94949 94349 94049 54049 55049 58049 58043 58013 18013 19013 19073 16073 16063 16763
66763 64763 64793 63793 63799 63199 33199 39199 39799 39769 39569 35569 35069 35059 35759 34759 34729 34129 34123
34183 38183 38153 35153 25153 29153 29173 23173 23473 24473 24443 20443 60443 60449 30449 35449 35149 38149 38189
58189 58199 58193 78193 48193 42193 82193 82183 82153 92153 92143 32143 32443 32413 32423 37423 35423 25423 25453
29453 59453 52453 52457 52757 58757 18757 18457 18427 58427 78427 78467 78497 72497 72493 76493 76403 76003 26003
26083 26783 56783 56773 56473 56453 58453 98453 98443 95443 15443 15473 15173 15773 95773 95873 91873 98873 98893
98993 88993 88493 88463 28463 28163 25163 25183 25189 25889 25849 25841 24841 24821 24421 94421 94321 98321 98621
28621 28661 58661 58631 54631 24631 24611 74611 75611 75011 75013 75083 75883 75853 78853 78823 78893 78593 38593
30593 30293 30893 30853 30851 38851 38351 34351 34301 34303 34403 33403 33703 33503 33563 39563 39163 39133 39233
39239 69239 59239 51239 81239 81299 81199 91199 91129 91139 91159 91459 91499 21499 28499 28439 78439 78479 78179
78139 70139 60139 67139 67129 47129 47123 47143 27143 27103 27109 27179 21179 21149 21139 21839 81839 81869 86869
86969 86959 86939 82939 82039 22039 22739 12739 19739 69739 69439 39439 39419 39499

Leren
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby JPF » Fri Oct 04, 2013 7:02 pm

Here is a list of 6500 five digit primes.

Some issues to resolve to get the full list.

JPF
Attachments
WL6500.txt
(44.43 KiB) Downloaded 55 times
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: A Sobering Problem

Postby Leren » Fri Oct 04, 2013 10:18 pm

It appears that there are 5 five digit primes that are "connected" to only one other five digit prime (by a single digit difference). These are the primes in the first column
of the following table. The primes in the second column are the only ones to which they are "connected".

Code: Select all
46769   96769
97039   37039
97919   27919
98519   98419
99721   99761

All of the primes in the second column appear in JPF's 6500 prime list and none of the primes in the first column appear in it.

I think this means that, unfortunately, the holy grail of a ladder list of all 8363 five digit primes is impossible - the best you can do would be something like:

46769 96769 .... [ ladder of 8356 primes ... ] .... 99721 99761 - a total ladder of 8360 primes. I have no idea if even this is possible.

Still, it would be nice to find a maximal ladder and demonstrate in some way that it is maximal. Another really cool objective would be to find a maximal cyclic ladder
ie where the last prime in the ladder is 1 digit different from the first prime - so you could start the list from any point along it.

Leren
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby JPF » Sat Oct 05, 2013 10:28 am

Leren wrote:I think this means that, unfortunately, the holy grail of a ladder list of all 8363 five digit primes is impossible - the best you can do would be something like:
46769 96769 .... [ ladder of 8356 primes ... ] .... 99721 99761 - a total ladder of 8360 primes.
..................

That's a good point.

JPF
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

Re: A Sobering Problem

Postby Leren » Sat Oct 05, 2013 12:19 pm

I've found that JPF's 6500 prime ladder starts with 87491 and has 17491 at position 6409.

That would make a cyclic ladder of length 6409. There will certainly be other cyclic ladders in that list but it will take a while to check all possibilities to see whether one exceeds a length of 6409.

Leren

<Edit> Now had a chance to check for longer cyclic ladders. 69691 is in position 5 and 79691 is in position 6493 for a longest cyclic ladder length of 6489.

Leren
Last edited by Leren on Sat Oct 05, 2013 9:22 pm, edited 1 time in total.
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby Smythe Dakota » Sat Oct 05, 2013 1:06 pm

Leren wrote: .... [ a whole bunch of stuff ] ....
In response, JPF and David P Bird wrote: .... [ a lot of other stuff ] ....

I can't believe you guys actually took me up on this. Your next task, should you decide to accept it, is to do the same thing in hexadecimal. Of course, there are m-a-n-y more hexadecimal 5-digit primes than decimal 5-digit primes.

Bill Smythe
Smythe Dakota
 
Posts: 525
Joined: 11 February 2006

Re: A Sobering Problem

Postby Leren » Sun Oct 06, 2013 2:55 am

Here is a 5 digit prime ladder with 7021 numbers starting from the lowest 5 digit prime.

<Edit> Added new file with a 7536 prime number ladder from the same start prime.

Leren
Attachments
Primes 5 Digit Ladder 7536 Numbers.txt
(88.31 KiB) Downloaded 54 times
Primes 5 Digit Ladder 7021 Numbers.txt
(82.28 KiB) Downloaded 50 times
Leren
 
Posts: 2734
Joined: 03 June 2012

Re: A Sobering Problem

Postby JPF » Sun Oct 06, 2013 5:02 pm

Waiting for 8000 ;)

edit:
here is a 8154 primes.
There is a cycle 23599 ->33599 with 8139 elements.


JPF
Attachments
WL8154.txt
(55.74 KiB) Downloaded 55 times
WL7616.txt
(52.06 KiB) Downloaded 55 times
JPF
2017 Supporter
 
Posts: 3751
Joined: 06 December 2005
Location: Paris, France

PreviousNext

Return to Coffee bar