Problems & Puzzles: Puzzles

Puzzle 966. Update Puzzle 353.

Here we ask for the unsolved cases for the Puzzle 353 posed time ago by Anurag Sahay.

"Arrange the first n2 primes in a n by n matrix such that every two adjacent primes should not have any digit in common."

From the contributions to Puzzle 353, this is the status for 3<=n<=22

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, ...

Solved in blue: 3, 4, 5, 10, 11 & 14
Impossible in
red: 6, 7, 8, 15-22
Unsolved in black: 9, 12 & 13

Q. Send your solutions for these unsolved cases (n = 9, 12 & 13) or show that these solutions are impossible.

n= 3 and n=5 by Anurag

 23 19 3 11 5 17 7 13 2

and

 97 43 67 3 41 31 7 89 17 53 47 61 73 2 79 59 23 19 5 13 37 11 83 71 29

n=4 by Fred Schneider

 3 41 37 11 7 23 19 53 13 5 43 2 47 31 29 17

n=10, 11 and 14 , by Jon Wharf

 173 449 31 457 139 487 313 67 499 151 59 317 229 13 467 193 227 509 271 349 137 409 311 257 331 277 53 17 439 157 269 113 479 103 79 5 281 43 71 239 131 89 163 97 463 179 433 101 293 167 29 431 7 23 197 283 61 383 107 359 47 2 83 19 223 41 353 241 389 127 191 73 149 367 11 263 401 397 251 443 523 419 337 109 373 181 233 541 379 521 491 307 199 347 211 503 461 37 421 3

and

 317 659 173 409 17 283 179 23 61 379 641 269 137 89 71 263 197 223 571 389 461 397 431 229 113 499 107 233 167 349 617 239 41 509 313 449 127 443 157 439 281 593 11 523 31 577 331 599 601 383 271 359 67 29 181 557 631 487 661 479 5 433 607 293 541 2 613 277 103 47 251 463 97 43 151 73 569 457 163 547 619 347 199 643 79 3 59 337 13 257 131 587 191 653 19 563 211 373 521 467 139 227 109 83 419 53 421 503 149 37 193 647 311 7 101 367 491 307 241 353 401

and

 137 659 317 509 617 239 761 359 107 653 701 863 271 983 829 173 269 13 809 167 293 1117 593 1087 643 127 389 157 113 859 313 569 17 349 1171 953 1187 563 71 883 571 839 929 131 47 1123 409 281 439 881 463 811 263 1051 233 751 1013 967 103 67 211 503 821 433 181 599 101 887 1151 443 769 1031 947 31 677 241 353 1181 59 2 499 251 397 151 1033 797 1103 997 421 683 401 29 7 449 1021 739 521 937 79 613 977 431 757 41 277 461 229 5 89 61 379 601 1063 97 631 907 11 283 641 877 541 727 661 347 1061 743 479 163 709 331 857 199 577 1129 37 941 827 619 733 1069 1163 547 311 607 19 823 491 373 419 307 691 557 919 383 487 1193 647 1153 467 109 367 149 673 191 83 911 3 1097 193 457 139 787 1109 853 1009 773 1049 223 719 53 179 43 227 1093 257 1039 587 1091 73 1019 337 991 523 971 23 197

Contributions came from Dmitry Kamenetsky, Michael Hürter, Paul Cleary and Oscar Volpatti

***

Dmitry wrote on Aug 17, 2019:

N=12 and N=13 exist! I don't think N=9 exists, but I cannot prove it. Here they are:

N=12
41 257 139 677 389 71 683 571 439 107 823 719
653 19 587 131 277 349 751 293 761 53 179 233
149 83 61 727 419 787 239 157 433 127 353 167
367 401 73 601 383 2 617 443 271 503 197 283
449 523 199 773 569 173 89 701 593 241 3 461
31 409 263 509 181 269 347 599 821 373 421 379
607 113 47 311 467 313 5 317 659 11 397 101
359 7 23 769 331 67 431 59 103 229 151 739
211 643 557 13 227 491 577 631 827 613 79 521
37 811 43 97 661 733 109 457 619 547 163 479
499 673 29 541 337 191 647 193 757 281 797 563
137 809 641 307 691 743 251 487 223 709 463 17

N=13
401 653 179 463 859 613 829 631 227 19 283 971 383
569 811 53 229 431 827 433 887 419 37 619 83 421
173 499 787 43 709 313 257 491 773 2 73 521 967
269 337 641 599 13 727 691 373 659 317 5 797 113
857 991 587 163 977 181 233 449 131 809 761 23 769
439 67 149 757 101 937 881 367 409 137 929 577 311
271 359 277 331 79 211 347 109 733 29 487 103 947
953 167 389 647 251 673 199 563 919 47 31 997 883
17 503 241 89 743 1009 353 719 853 601 479 263 71
509 661 379 41 59 443 197 523 61 547 281 457 983
821 397 541 907 863 571 643 911 307 11 557 193 677
739 461 7 3 701 349 157 823 941 877 139 607 239
151 97 683 127 593 107 839 751 223 191 467 293 617

***

Michael wrote on Aug 18, 2019:

I found the following solutions:
For n = 12:

541 739 41 359 71 389 701 659 401 673 811 349
73 61 23 17 439 127 563 211 367 191 337 251
461 233 179 463 271 683 149 773 419 257 619 733
239 571 43 109 643 719 523 199 3 19 307 11
751 293 617 823 197 83 647 383 151 347 521 379
263 487 509 467 283 677 353 491 37 821 397 181
587 193 7 139 557 113 607 5 29 373 281 547
601 757 101 47 613 599 331 479 131 499 67 223
227 431 827 631 97 241 769 31 409 317 89 641
691 277 313 709 421 79 433 59 311 809 167 593
727 653 797 163 577 13 229 743 269 157 443 107
503 787 103 457 661 449 173 569 137 2 761 53

For n = 13:

29 751 499 113 569 223 59 337 149 887 613 509 137
587 929 173 5 347 19 373 919 257 311 229 317 599
941 883 449 37 1009 773 691 877 631 479 13 859 463
233 197 853 419 827 619 227 193 727 131 659 23 557
191 433 199 307 461 733 911 547 331 757 41 97 103
563 719 43 991 283 101 73 269 457 163 857 3 79
809 523 179 53 409 577 641 7 109 787 431 977 503
643 971 2 491 653 241 379 881 277 139 67 31 487
157 823 907 263 47 593 661 743 811 467 251 947 313
839 617 443 107 953 607 353 601 397 181 709 151 769
761 239 701 983 271 389 647 359 281 367 541 739 211
89 17 349 571 383 167 829 11 967 521 937 821 997
127 83 61 293 677 439 71 863 421 673 401 797 683

***

Paul wrote on Aug 19, 2019:

For n=12 and 13 here are my solutions.

 599 673 811 379 601 757 199 43 661 449 613 89 773 151 739 251 349 211 373 821 743 181 727 631 641 293 41 389 71 53 419 367 109 677 503 787 397 61 223 751 643 197 523 19 487 139 47 13 421 359 617 83 127 563 11 457 193 827 103 479 509 761 593 271 3 241 587 313 557 163 797 311 263 409 7 383 691 733 491 577 331 709 653 79 541 2 443 5 337 149 277 431 769 823 179 283 683 17 269 317 659 37 191 67 433 719 23 157 401 569 137 499 173 59 467 113 607 353 701 439 257 31 809 167 229 73 281 647 131 97 463 571 619 227 461 29 307 521 347 101 547 233 107 239

And

 379 641 397 421 733 659 137 829 743 991 283 157 439 461 983 521 937 811 773 449 53 1009 587 41 83 727 389 127 43 181 67 109 353 691 337 919 233 107 593 71 563 997 523 149 277 619 307 541 367 599 443 167 383 971 23 941 673 881 347 191 827 401 227 101 839 11 823 17 223 199 757 911 73 419 557 311 257 61 883 761 5 179 503 229 467 281 607 193 677 139 877 751 433 7 643 719 653 19 37 59 787 359 647 293 263 79 103 977 463 197 863 491 887 953 617 509 47 947 251 97 241 797 853 701 683 409 211 349 271 569 31 907 151 769 13 269 3 709 821 739 601 859 317 487 331 967 431 809 571 29 631 577 661 457 613 2 239 857 131 89 373 499 113 547 163 479 313 929 173

***

Oscar wrote on August 23, 2019

I solved the cases n = 12 and n = 13; the case n = 9 is impossible.

Solution for n = 12:

107  349  127  463  227  139  257  313    2  179  263  479
439  157  643  751  443  277  163  557  149  653  197  563
271  449  571   43  709   13  457  193  577  419  683  719
499  701  433   29   31  727  331  487  613  587  491   23
821    3  109   37   59  113  757  631  547   19  607  191
367  541  733  101   73   89  131  787   61  307  199   53
521  673  241  379  151  337  229  311  827   11   83  619
773  811  397  401  739  181  373  509  661  223  691  353
809  347  251  769  421   67  211  677  599   17  503   41
431  269   47  281   79  103    7  233   71  593  167  293
569  173  659  743  601   97  283  467  523  617  359  461
317  409  137    5  797  383  647  823  761  389  641  239

Solution for n = 13:

107  349  127  463  227  139  257   61  503  179  653  479  263
439  157  643  907  313  277  163  557  149  523  197  563  947
271  449  571   43  709   13  457  193  577  419  863  719  683
499  701  433   29   31  727  661  487  613  587  491  823  971
751    3  109   37   59  113  757  631  547  991  827  941   23
443 1009  733  101   73   89  131  787  691  887   19  307  191
601  773  241  379  151  337  229  311  877  331  607  199   53
5  811  397  401  739  181  373  509   11  857  911   83  619
809  367  251  769  421  797  211    7  883  919  223   47  353
317  829  673  281  937  541  967  821  977  853   17  839   41
269  347  859  677  521   79  881  997  233   71  593  167  293
173  569  743  929   67  103   97  283  467  953  617  359  461
409  137  659  431  599    2  383  647  983  761  389  641  239

I built the 12x12 solution by manual arrangement.

I noticed that exactly 50% of the first 144 primes contain at least one rare digit from the set D2 = {0,2,5,8}, and I decided to place such primes on even positions only.
Therefore, I only needed to consider the frequent digits from the sets D0 = {3,6,9} and D1 = {1,4,7}.

I filled the matrix as follows:
top left corner: even {1,7}, odd {4,d0',d0"} or {4,d0};
top right corner: even {3,6}, odd {9,d1',d1"} or {d1',d1"};
bottom left corner: even {6,9}, odd {3,d1',d1"} or {d1',d1"};

bottom right corner: even {3,9}, odd {6,d1',d1"}, or {d1',d1"};

completing main diagonal: even {9};
above main diagonal: even {7} or {4,7}, odd {1,d0',d0"}, or {1,d0};
below main diagonal: even {1} or {1,4}, odd {7,d0',d0"}, or {7,d0};
finally, the remaining positions.
I built the 13x13 solution in the same way, just placing the primes 2 and 5 in odd positions.

Impossibility proof for n = 9.

In order to detect the bottleneck, consider the following simpler problem:
on a 9x9 board, place 14 pawns in non-adjacent squares in order to minimize the number x of empty squares adjacent to at least one pawn.

Solution: x>= 18, and the following configuration is an elegant optimal example (among many others):

1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

Going back to the original problem, place the 14 primes containing both 1 and 3 (necessarily, in non-adjacent positions).
The positions adjacent to such primes must be filled by primes not containing neither 1 nor 3.
But there are at least 18 such posiions, and only 16 such primes.

***

 Records   |  Conjectures  |  Problems  |  Puzzles