Puzzle 844. Primes inside Sudoku solutions

Problems & Puzzles: Puzzles

Puzzle 844. Primes inside Sudoku solutions

G. L. Honaker, Jr. sent the following nice puzzle.
Send a Sudoku solution with the most quantity of distinct primes inside. You can read entirely or in fragments only the 9 rows, the 9 columns and the two main diagonals, in any of the two directions for each.
Example: The following Sudoku solution sent by G.L. contains 134 distinct prime numbers inside.

Here are the primes inside, computed by me:
3 2 7 19 5 491 9187 23 487 59 59621 13 31 269 43 67 83 29 8643527 643 3527 35279 5279 2791 79 197 97 7253 53 751 519683 683 423 869 23869 238691 691 9157 157 293 317 17 8564713 5647 564713 647 47 71 139 9456371 563 37 281 173 73 6825439 825439 2543 25439 439 8419 41 419 419567 659 823 458729 587 5872913 381659 165947 947 2749 61 27941 279413 941 9413 86531 653 53149 531497 149 7523 75239 523 52391 239 4861 48619 486193 619 193 93257 3257 257 89 945673 4567 45673 673 7321 1237 163 284759 4759 82361 541 54163 41637829 1637 637 829 7829 829 179 85297 5297 2971 971 6148297 8297 84163 6893641 8936413 89364137 936413 641 137 14639 463 4639 518261 51826157 518261573 8261573
Q. Send your best solution.

Contributions came from Dmitry Kamenetsky, Jeff Heleen and Claudio Meller.

***

Dmitry wrote:

If we permute the 9 numbers then we obtain another valid Sudoku. I took Honaker's solution and checked all 9! permutations. This gave me a Sudoku with 191 primes:

145387629

283961574

976524831

812495367

397618452

564732198

629143785

731859246

458276913

primes 2 3 5 7 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 127 137 149 157 167 179 239 263 269 271 281 283 347 359 367 389 397 419 421 431 439 457 467 487 491 541 563 587 593 641 647 653 659 691 719 743 751 761 769 823 827 839 859 941 947 953 967 971 983 1237 1249 1453 1489 1693 2749 3457 3541 3659 4127 4397 4721 4751 4831 4871 5179 5387 5417 5431 5647 5813 5827 5879 6359 6473 6793 6917 7321 7691 8167 8563 8629 8641 8719 9421 9623 12743 12983 13457 24953 25679 26783 27143 27691 28541 29581 31859 34721 38921 39761 41729 45823 45827 47653 53269 54319 56473 58271 65827 75169 75431 76913 78517 83417 86291 87629 89123 89563 91237 95467 95813 96157 145823 176459 283961 291437 341729 362749 396157 429581 458239 473219 475169 524831 532691 538921 583417 587341 627491 629143 647321 715879 764593 765389 862913 873419 913457 947263 954671 1458239 2913457 3971587 4582769 5647321 5827691 5873419 6291437 6524831 7652483 8176459 8425679 9715879 28396157 54816793 58276913 62913457 76359421 76538921

***

Jeff wrote:

For puzzle 844 the best I have found so far has 161 distinct primes. -Jeff Heleen

725483169

143269578

869517234

497826351

216345897

358791642

634178925

571932486

982654713

161 primes

Row primes

7, 2, 5, 3, 83, 31, 5483, 4831, 3169, 254831

43, 269,

17, 23, 1723, 86951,

97, 263, 8263, 826351

89, 163, 5897, 34589

79, 587, 5879, 35879

41, 1789

71, 19, 571, 719, 193, 7193, 57193

47, 13, 547, 6547, 5471, 54713, 265471, 9826547

Reverse row primes

61, 613, 9613

59, 9623, 2341, 759623, 962341

271, 4327, 3271, 7159, 43271, 4327159

53, 6287, 2879, 536287, 1536287

8543, 98543, 54361

461, 619, 197, 853, 6197, 7853

29, 9871, 529871, 987143, 2987143

239, 8423, 3917, 84239, 42391, 23917, 684239

317, 7456289

Column primes

659, 3659, 718423, 18423659

37, 691, 4691, 24691, 469153

397, 6841

3719, 83719, 425837, 2583719

73, 1249, 4973, 12497, 612497, 8612497

97651

523, 947, 1523, 6947, 23869

67, 673, 359, 281, 594281

563

Reverse column primes

4817

7351

6793, 14867, 48679, 214867

173, 6917, 9173

379, 421, 9421

1567, 15679

683, 251, 3251, 683251

953, 24953, 49537, 8249537

1489, 36527, 271489

Diagonal primes

419, 983, 8419, 98419, 41983, 49841983

46279

Reverse diagonal primes

389, 48947

647, 479, 2647, 72647, 64747, 72647479, 972647479

***

Claudio wrote:

Encontré uno con 161, no sé si es mucho porque mucho no busqué.

647382591
293615478
518479632
879536124
162794853
354128967
431967285
786251349
925843716

***

On Aug 29, 2016 Carlos Rivera wrote:

Following the permutation idea of Dmitry I set a code in Ubasic in order to input Sudoku solutions (available in the web) to get the best permutation of all these 9! from each Sudoku solution. After around 20 attempts I came un with this 193 distinct primes inside.

Primes = 193

264718935
713592648
598364172
829173456
351426897
647985213
985631724
136247589
647859361

Primes from rows
2 2647 647 647189 6471893 47 47189 471893 7 71 89 3 5 53 9817 17
71359 13 359 59 84629 8462953 462953 29 2953 29531 953 95317 31 317
983 9836417 83 83641 641 41 271 271463 27146389 7146389 146389 463
6389 389 829 8291 2917 29173 9173 173 73 65437 654371 5437 54371
43 37 3719 719 19 5142689 42689 2689 97 79 7986241 8624153 241 4153
479 798521 985213 8521 85213 521 312589 12589 125897 5897 98563 985631
8563 563 631 6317 4271 2713 136247 6247 7589 9857 98574263 857
5742631 263 647859361 78593 859 859361 593 61 163 9587 587

Primes from columns
27583 7583 58369 8369 3691 691 619 63857 61925483 5483 4384529 3845291 43891
38917 67 6571 65719 571 71983 53149 149 8269 269 269413 941 9413 41357
967 7283 283 543827 43827691 382769 827 27691 769 7691 8243 2436517
24365179 43651 365179 65179 5179 179 971 971563 71563 9614827 614827
14827 482753 2753 347 34759 347591 4759 47591 7591 68219 821 8219
195743 5743 743 82673491 2673491 673 67349 7349 349 3491 491 9437

Primes from diagonals
181 8125781 257 8752181 52181
541 5413 132953 6359 635923 6359231 35923 359231 5923 23

BTW, Dmitry and I have been reasoning by email what could be an upper limit for the quantity of distinct primes in a sudoku solution. We came up with this idea and value: 218.

The average of the quantity of distinct primes of all the 9! zerloess pandigitals read in both directions is 14.7289. A Sudoku solution is composed by 20 zerloess pandigitals. For the purpose of counting primes inside we may assume that these 20 pandigitals are practically at random. But the primes 2, 3 5 y 7 are repeated in the last 19 zerloess pandigitals after the first one, so, the upper limit could be around 20*14.7289-4*19 = 218, nevertheless I must say that Dmitry thinks that this is a pessimistic upper bound...

***

On Aug 30 Emmanuel Vantieghem wrote:

This is a sudoku grid with 192 primes inside :

3 8 4 1 6 5 7 2 9

1 5 2 8 7 9 3 6 4

9 6 7 4 3 2 1 8 5

8 3 1 7 5 4 6 9 2

4 2 5 3 9 6 8 7 1

6 7 9 2 8 1 4 5 3

5 4 3 6 2 7 9 1 8

7 9 8 5 1 3 2 4 6

2 1 6 9 4 8 5 3 7

The primes :

2 3 5 7 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 137 149 157 173 197 239 251 263 271 281 293 317 347 359 397 457 461 463 491 521 541 563 571 577 593 613 617 659 673 683 743 751 769 821 829 839 853 919 941 947 953 967 977 1289 1453 1483 1579 1657 1847 2347 2539 2549 2659 2689 2749 2791 2879 3541 4157 4231 4253 4271 4639 4657 4723 4861 4919 5623 5779 5849 5897 6173 6397 6871 7159 7481 7561 7753 7919 8123 8297 8317 8513 8537 8563 8693 9239 9281 9851 12347 14923 15287 28793 32749 32941 34157 41579 43627 52879 56237 56489 57791 61483 62791 64231 64891 65729 71593 76831 84961 86137 92461 94169 94723 96149 96457 149239 152879 178693 194723 197753 231589 234769 246173 294169 327491 396871 436279 491977 539687 577919 645713 674321 749197 812347 924617 932941 956237 964571 1234769 1289537 2315897 2964571 3294169 3716429 3841657 4165729 5213867 5924617 6327491 7316849 7561483 7564891 8975143 9197753 9281453 9486137 9614923 9674321 21694853 25396871 29645713 42539687 52948613 57791947 75648913 83716429 93294169

A few hours later Emmanuel wrote:

Here is my latest result : 202 primes.

1 6 5 4 7 9 2 8 3

9 7 3 2 5 8 6 1 4

4 8 2 6 1 3 5 9 7

8 5 6 3 4 2 1 7 9

2 3 9 1 6 7 8 4 5

7 4 1 9 8 5 3 6 2

6 1 7 5 3 4 9 2 8

5 9 8 7 2 1 4 3 6

3 2 4 8 9 6 7 5 1

I think 218 is too big because the columns are not independent of the rows.

A little bit later he got 207 primes... and explains his approach...

Still better :

4 5 9 1 6 7 3 2 8

3 1 2 5 8 9 6 7 4

8 6 7 2 3 4 1 5 9

9 7 4 6 5 3 2 8 1

5 8 3 9 1 2 4 6 7

6 2 1 4 7 8 5 9 3

1 3 6 7 9 5 8 4 2

7 4 5 8 2 1 9 3 6

2 9 8 3 4 6 7 1 5

With 207 primes :

{2, 3, 5, 7, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 131, 163, 167, 173, 179, 193, 251, 269, 271, 281, 317, 347, 349, 367, 389, 421, 431, 467, 479, 491, 521, 547, 587, 593, 613, 617, 619, 631, 641, 643, 647, 653, 659, 673, 683, 719, 743, 761, 769, 821, 823, 839, 857, 859, 881, 883, 947, 967, 971, 983, 1367, 1823, 2341, 2371, 2467, 2851, 2971, 3467, 3517, 3719, 3761, 3881, 4159, 4219, 4297, 4327, 4591, 4729, 4783, 5167, 5179, 5623, 5647, 5821, 5839, 5869, 5897, 6421, 6857, 6947, 7643, 7823, 8167, 8219, 8237, 8521, 8597, 8713, 8741, 8761, 9173, 9431, 9587, 12589, 13679, 14327, 15269, 15823, 23497, 23719, 23761, 24859, 26947, 27431, 28547, 34159, 34729, 37619, 38749, 41761, 42193, 45821, 53281, 53881, 56237, 56479, 58391, 58741, 58967, 59167, 65983, 68351, 69431, 72341, 74653, 75869, 76421, 78593, 81671, 82193, 82349, 85213, 89561, 91673, 95143, 95617, 96857, 147859, 165983, 237619, 245897, 248597, 258967, 312589, 356479, 389561, 458219, 459167, 464131, 561347, 591673, 623719, 641317, 653281, 672341, 694783, 698521, 834671, 912467, 927431, 974653, 985213, 1258967, 1478593, 1761883, 3881671, 4653281, 5167823, 5823497, 6124589, 6985213, 7234159, 7698521, 8561347, 9514327, 36124589, 43895617, 48597631, 61582349, 76985213, 82356479, 83912467, 98542163}

My guess : 207 could be the upper limit.

I took as first row a pandigital with a maximum number of primes.

Among all the pandigitals rows that can be the 2nd row of a sudoku, I take one that gives me a maximum of primes (the partial diagonals a11,a22 and a19,a28 are counted with). In this way I can reach a sudoku with many primes. Of course, it will be impossible to prove that a number (like 207) is the exact upper bound. There are too much sudoku grids ...

Finally, on Set 02 he got a 211 primes sudoku.

I tried once more to beat the record. I found the grid

4 5 9 1 6 7 3 2 8

3 1 2 5 8 9 6 7 4

8 6 7 2 3 4 1 5 9

9 7 4 6 5 3 2 8 1

5 8 3 9 1 2 4 6 7

6 2 1 7 4 8 9 3 5

1 9 5 8 2 6 7 4 3

2 3 8 4 7 1 5 9 6

7 4 6 3 9 5 8 1 2

With 211 primes :

{2, 3, 5, 7, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 127, 131, 163, 167, 193, 241, 251, 263, 269, 281, 293, 317, 347, 349, 389, 421, 431, 439, 463, 467, 479, 487, 491, 521, 571, 593, 619, 647, 653, 659, 673, 683, 719, 743, 761, 769, 823, 829, 839, 857, 859, 863, 967, 983, 1249, 1427, 1753, 1823, 1879, 2341, 2467, 2861, 3491, 3571, 3761, 3847, 4153, 4159, 4219, 4327, 4591, 4639, 4729, 5167, 5647, 5839, 6217, 6421, 6823, 6857, 7159, 7489, 7537, 7829, 8167, 8237, 8293, 8513, 8521, 8713, 8761, 9421, 9781, 12497, 12589, 14327, 15269, 16823, 17483, 17489, 18593, 21859, 23497, 23761, 26357, 27431, 28591, 34159, 34729, 36857, 37619, 39581, 39847, 41761, 42193, 51347, 51427, 52697, 53281, 56479, 57131, 58391, 58967, 59167, 61879, 65983, 67829, 68351, 71317, 72341, 73571, 74653, 76421, 78167, 81671, 82349, 85213, 89561, 91673, 91753, 95143, 97241, 97843, 165983, 174893, 217489, 237619, 238471, 258967, 312589, 351427, 356479, 357131, 389561, 398471, 459167, 586349, 591673, 593647, 612497, 628591, 653281, 672341, 698521, 724153, 761879, 863491, 912467, 927431, 942163, 974653, 985213, 1258967, 3514279, 3847159, 4176187, 4653281, 4762859, 5134729, 6851347, 6985213, 7234159, 7628591, 7698521, 7942163, 8491753, 9514327, 9517483, 16823497, 43928761, 51682349, 57942163, 73571317, 76985213, 82356479, 83912467, 95826743}

I think the upper limit might indeed be 218

***

BTW, Emmanuel also asked for minimal solutions for this puzzle. See Puzzle 846 for this issue.

***

On set 16, 2016, Michael Hürter wrote:

For prime puzzle 844 I found the following solution with
221 distinct primes:

746231859
312589674
589764312
478923561
123856947
965147283
251498736
837612495
694375128

221 distinct primes:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 113, 149, 157, 167, 173, 199, 251, 257, 283, 293, 311, 337, 349, 359, 367, 379, 389, 419, 421, 431, 461, 463, 467, 491, 521, 541, 563, 569, 571, 577, 599, 617, 631, 641, 643, 647, 653, 673, 683, 719, 733, 751, 761, 769, 821, 827, 829, 839, 859, 863, 941, 947, 953, 967, 977, 983, 991, 1153, 1249, 1453, 2549, 2579, 2647, 2683, 2741, 2953, 3467, 3491, 3511, 3517, 3541, 3761, 4217, 4679, 4729, 4789, 4987, 5113, 5147, 5419, 5779, 5813, 5897, 5927, 6311, 6359, 6829, 6947, 7283, 7349, 7643, 7759, 8291, 8461, 8521, 8563, 8923, 8941, 9421, 9437, 9733, 12589, 14537, 21673, 23561, 26539, 31153, 31859, 32647, 32987, 34679, 35419, 38461, 38569, 41897, 54917, 57349, 58321, 58967, 62549, 62983, 64189, 65147, 71249, 72953, 73351, 74623, 75991, 78941, 81463, 83761, 85213, 91453, 95813, 99577, 115337, 132647, 147283, 149873, 153379, 157349, 164839, 213467, 231859, 257981, 258967, 311533, 312589, 335113, 371249, 378941, 496583, 528763, 562781, 592741, 631153, 641897, 658321, 698521, 716483, 733511, 735419, 741569, 746231, 761249, 821573, 876349, 923561, 942167, 943751, 965147, 985213, 1258967, 1472953, 3562781, 3862549, 5716483, 6231859, 6254917, 6298351, 6371249, 6532987, 6943751, 6985213, 7698521, 8635927, 8976431, 9421673, 9452683, 23856947, 57981463, 63115337, 63592741, 76985213, 78923561, 97335113

***

Records | Conjectures | Problems | Puzzles