MPMP15 - Prime Pairs

prime-pairs.md

This is the fifteenth puzzle in Matt Parker's Matt Parker's Maths Puzzles puzzle series

Prime Pairs

Submittable Puzzle

Find a permutation of the numbers 1 to 9 such that the sum of any two adjacent numbers is prime.

e.g. The permutation 9 8 7 6 5 4 3 2 1 does not satisfy the condition because 8 and 7 are adjacent and 8 + 7 = 15 = 3 * 5 which is not prime.

Solution

This seems like a great candidate for backtracking. In much the same way we would solve a sudoku with backtracking, we start with an empty permutation and attempt to add values onto the end, such that the permutation so far satisfies the condition that sums of adjacent terms are prime.

Here is an example of such a backtracking algorithm:

def allPrimePairPermutations(n):
    """
    Returns all the permutations of 1 to n such that the sum of any pair of
    adjacent numbers is prime.
    """
    # Our resulting list of the valid permutations. This will be populated by
    # the backtracking algorithm.
    result = []

    # A set to let us know whether we have used a value yet.
    used = [False] * (n + 1)

    # The largest sum of two adjacent numbers is n + (n - 1), so we don't need
    # to know any primes larger than that.
    primes = set(primesLessThan(2 * n))

    # The permutation so far.
    perm = []

    # Our backtracking method.
    def findPermutations():
        if len(perm) == n:
            # we have a valid permutation; we should add it to the result.
            result.append(perm.copy())
            return
        # otherwise attempt to append an unused value to the current permutation
        for cand in range(1, n + 1):
            if used[cand]:
                # we shouldn't use any number more than once
                continue
            if len(perm) == 0 or perm[-1] + cand in primes:
                # If adding cand to our permutation preserves our condition, we
                # should append it to our current permutation and recurse.

                # The candidate number is now used.
                used[cand] = True
                perm.append(cand)

                # We now recurse down.
                findPermutations()

                # We finished checking the permutations, we can pop our
                # candidate from the permutation and continue the loop.
                perm.pop()
                used[cand] = False

    # Start backtracking.
    findPermutations()
    return result

It turns out there are quite a few valid answers:

All 140 valid permutations

1. 1, 2, 3, 4, 7, 6, 5, 8, 9
2. 1, 2, 3, 4, 9, 8, 5, 6, 7
3. 1, 2, 3, 8, 5, 6, 7, 4, 9
4. 1, 2, 3, 8, 9, 4, 7, 6, 5
5. 1, 2, 5, 6, 7, 4, 3, 8, 9
6. 1, 2, 5, 6, 7, 4, 9, 8, 3
7. 1, 2, 9, 4, 3, 8, 5, 6, 7
8. 1, 2, 9, 4, 7, 6, 5, 8, 3
9. 1, 2, 9, 8, 3, 4, 7, 6, 5
10. 1, 2, 9, 8, 5, 6, 7, 4, 3
11. 1, 4, 3, 2, 9, 8, 5, 6, 7
12. 1, 4, 3, 8, 9, 2, 5, 6, 7
13. 1, 4, 7, 6, 5, 2, 3, 8, 9
14. 1, 4, 7, 6, 5, 2, 9, 8, 3
15. 1, 4, 7, 6, 5, 8, 3, 2, 9
16. 1, 4, 7, 6, 5, 8, 9, 2, 3
17. 1, 4, 9, 2, 3, 8, 5, 6, 7
18. 1, 4, 9, 8, 3, 2, 5, 6, 7
19. 1, 6, 5, 2, 3, 8, 9, 4, 7
20. 1, 6, 5, 2, 9, 8, 3, 4, 7
21. 1, 6, 5, 8, 3, 2, 9, 4, 7
22. 1, 6, 5, 8, 9, 2, 3, 4, 7
23. 1, 6, 7, 4, 3, 2, 5, 8, 9
24. 1, 6, 7, 4, 3, 2, 9, 8, 5
25. 1, 6, 7, 4, 3, 8, 5, 2, 9
26. 1, 6, 7, 4, 3, 8, 9, 2, 5
27. 1, 6, 7, 4, 9, 2, 3, 8, 5
28. 1, 6, 7, 4, 9, 2, 5, 8, 3
29. 1, 6, 7, 4, 9, 8, 3, 2, 5
30. 1, 6, 7, 4, 9, 8, 5, 2, 3
31. 3, 2, 1, 4, 7, 6, 5, 8, 9
32. 3, 2, 1, 4, 9, 8, 5, 6, 7
33. 3, 2, 1, 6, 5, 8, 9, 4, 7
34. 3, 2, 1, 6, 7, 4, 9, 8, 5
35. 3, 2, 5, 8, 9, 4, 1, 6, 7
36. 3, 2, 5, 8, 9, 4, 7, 6, 1
37. 3, 2, 9, 8, 5, 6, 1, 4, 7
38. 3, 2, 9, 8, 5, 6, 7, 4, 1
39. 3, 4, 1, 2, 9, 8, 5, 6, 7
40. 3, 4, 7, 6, 1, 2, 5, 8, 9
41. 3, 4, 7, 6, 1, 2, 9, 8, 5
42. 3, 4, 7, 6, 5, 8, 9, 2, 1
43. 3, 4, 9, 8, 5, 2, 1, 6, 7
44. 3, 8, 5, 2, 1, 6, 7, 4, 9
45. 3, 8, 5, 2, 9, 4, 1, 6, 7
46. 3, 8, 5, 2, 9, 4, 7, 6, 1
47. 3, 8, 5, 6, 1, 2, 9, 4, 7
48. 3, 8, 5, 6, 7, 4, 1, 2, 9
49. 3, 8, 5, 6, 7, 4, 9, 2, 1
50. 3, 8, 9, 2, 1, 4, 7, 6, 5
51. 3, 8, 9, 2, 5, 6, 1, 4, 7
52. 3, 8, 9, 2, 5, 6, 7, 4, 1
53. 3, 8, 9, 4, 1, 2, 5, 6, 7
54. 3, 8, 9, 4, 7, 6, 1, 2, 5
55. 3, 8, 9, 4, 7, 6, 5, 2, 1
56. 5, 2, 1, 6, 7, 4, 3, 8, 9
57. 5, 2, 1, 6, 7, 4, 9, 8, 3
58. 5, 2, 3, 8, 9, 4, 1, 6, 7
59. 5, 2, 3, 8, 9, 4, 7, 6, 1
60. 5, 2, 9, 8, 3, 4, 1, 6, 7
61. 5, 2, 9, 8, 3, 4, 7, 6, 1
62. 5, 6, 1, 2, 3, 8, 9, 4, 7
63. 5, 6, 1, 2, 9, 8, 3, 4, 7
64. 5, 6, 7, 4, 1, 2, 3, 8, 9
65. 5, 6, 7, 4, 1, 2, 9, 8, 3
66. 5, 6, 7, 4, 3, 8, 9, 2, 1
67. 5, 6, 7, 4, 9, 8, 3, 2, 1
68. 5, 8, 3, 2, 1, 6, 7, 4, 9
69. 5, 8, 3, 2, 9, 4, 1, 6, 7
70. 5, 8, 3, 2, 9, 4, 7, 6, 1
71. 5, 8, 3, 4, 7, 6, 1, 2, 9
72. 5, 8, 3, 4, 9, 2, 1, 6, 7
73. 5, 8, 9, 2, 1, 6, 7, 4, 3
74. 5, 8, 9, 2, 3, 4, 1, 6, 7
75. 5, 8, 9, 2, 3, 4, 7, 6, 1
76. 5, 8, 9, 4, 3, 2, 1, 6, 7
77. 5, 8, 9, 4, 7, 6, 1, 2, 3
78. 7, 4, 1, 6, 5, 2, 3, 8, 9
79. 7, 4, 1, 6, 5, 2, 9, 8, 3
80. 7, 4, 1, 6, 5, 8, 3, 2, 9
81. 7, 4, 1, 6, 5, 8, 9, 2, 3
82. 7, 4, 3, 2, 1, 6, 5, 8, 9
83. 7, 4, 3, 2, 9, 8, 5, 6, 1
84. 7, 4, 3, 8, 5, 6, 1, 2, 9
85. 7, 4, 3, 8, 9, 2, 1, 6, 5
86. 7, 4, 3, 8, 9, 2, 5, 6, 1
87. 7, 4, 9, 2, 1, 6, 5, 8, 3
88. 7, 4, 9, 2, 3, 8, 5, 6, 1
89. 7, 4, 9, 8, 3, 2, 1, 6, 5
90. 7, 4, 9, 8, 3, 2, 5, 6, 1
91. 7, 4, 9, 8, 5, 6, 1, 2, 3
92. 7, 6, 1, 2, 3, 4, 9, 8, 5
93. 7, 6, 1, 2, 5, 8, 3, 4, 9
94. 7, 6, 1, 2, 5, 8, 9, 4, 3
95. 7, 6, 1, 2, 9, 4, 3, 8, 5
96. 7, 6, 1, 4, 3, 2, 5, 8, 9
97. 7, 6, 1, 4, 3, 2, 9, 8, 5
98. 7, 6, 1, 4, 3, 8, 5, 2, 9
99. 7, 6, 1, 4, 3, 8, 9, 2, 5
100. 7, 6, 1, 4, 9, 2, 3, 8, 5
101. 7, 6, 1, 4, 9, 2, 5, 8, 3
102. 7, 6, 1, 4, 9, 8, 3, 2, 5
103. 7, 6, 1, 4, 9, 8, 5, 2, 3
104. 7, 6, 5, 2, 1, 4, 3, 8, 9
105. 7, 6, 5, 2, 1, 4, 9, 8, 3
106. 7, 6, 5, 2, 3, 8, 9, 4, 1
107. 7, 6, 5, 2, 9, 8, 3, 4, 1
108. 7, 6, 5, 8, 3, 2, 1, 4, 9
109. 7, 6, 5, 8, 3, 2, 9, 4, 1
110. 7, 6, 5, 8, 3, 4, 1, 2, 9
111. 7, 6, 5, 8, 3, 4, 9, 2, 1
112. 7, 6, 5, 8, 9, 2, 1, 4, 3
113. 7, 6, 5, 8, 9, 2, 3, 4, 1
114. 7, 6, 5, 8, 9, 4, 1, 2, 3
115. 7, 6, 5, 8, 9, 4, 3, 2, 1
116. 9, 2, 1, 4, 3, 8, 5, 6, 7
117. 9, 2, 1, 4, 7, 6, 5, 8, 3
118. 9, 2, 1, 6, 5, 8, 3, 4, 7
119. 9, 2, 1, 6, 7, 4, 3, 8, 5
120. 9, 2, 3, 8, 5, 6, 1, 4, 7
121. 9, 2, 3, 8, 5, 6, 7, 4, 1
122. 9, 2, 5, 8, 3, 4, 1, 6, 7
123. 9, 2, 5, 8, 3, 4, 7, 6, 1
124. 9, 4, 1, 2, 3, 8, 5, 6, 7
125. 9, 4, 3, 8, 5, 2, 1, 6, 7
126. 9, 4, 7, 6, 1, 2, 3, 8, 5
127. 9, 4, 7, 6, 1, 2, 5, 8, 3
128. 9, 4, 7, 6, 5, 8, 3, 2, 1
129. 9, 8, 3, 2, 1, 4, 7, 6, 5
130. 9, 8, 3, 2, 5, 6, 1, 4, 7
131. 9, 8, 3, 2, 5, 6, 7, 4, 1
132. 9, 8, 3, 4, 1, 2, 5, 6, 7
133. 9, 8, 3, 4, 7, 6, 1, 2, 5
134. 9, 8, 3, 4, 7, 6, 5, 2, 1
135. 9, 8, 5, 2, 1, 6, 7, 4, 3
136. 9, 8, 5, 2, 3, 4, 1, 6, 7
137. 9, 8, 5, 2, 3, 4, 7, 6, 1
138. 9, 8, 5, 6, 1, 2, 3, 4, 7
139. 9, 8, 5, 6, 7, 4, 1, 2, 3
140. 9, 8, 5, 6, 7, 4, 3, 2, 1

As an aside, Matt said in the video "I think there are 2 solutions [for 12]", where in fact there are 17536 solutions.