Problems & Puzzles:
Puzzles
Puzzle 120. Primal Squares
A Primal Square
(*) is an nxn arrangement of numbers such that every two adjacent 
horizontal & vertical, but not diagonal  numbers sum up to a prime
number.
Example:
It's easy to verify that there is no solution for n=3 with consecutive
numbers.
Question 1. Can you explain why ?
Otherwise, for every n>3 it appears (this is my conjecture) that
always exists at
least one solution using the first n^{2} natural numbers. A 4x4
example sent by JeanCharles Meyrignac is:
1 
4 
7 
6 
2 
9 
10 
13 
11 
8 
3 
16 
12 
5 
14 
15 
Question 2. Can you
develop an algorithm to find at least one of these kind of solutions for
any n>3?
Question 3. Using your
own algorithm can you produce the solution for n = 10, 20 & 30
Question 3. Jean
Charles Meyrignac asks
if an (even) Magic
Square can be also a Primal
Square. In such
a case can you produce & send the first example?
A Primal Square
is said to satisfy the 'full torus condition'
if is prime the sum of every two symmetric (not necessarily adjacent)
cells out of the main diagonals. The mentioned symmetry is respect both
the horizontal and the vertical symmetry axis of the square. Obviously the
full torus condition can not be
satisfied by odd nxn squares.
The 4x4 example sent by JeanCharles
is a Primal Square but does not
satisfy the full torus
condition because none of the following: 4+5, 7+14, 2+13, 11+16
is prime (of course, is enough only one failure to spoil the full
torus condition).
Question 4. Can you find
a Primal Square that
satisfy the full torus
condition for n =
4, 6, 8 & 10?
_______
Note: According to JeanCharles Meyrignac,
these squares were first studied by Fred Schuh and made popular by
the well known French puzzler reporter Pierre Berloquin.
Solution
Jud McCranie has solved the question
1 (23/12/2000):
"...for any 9 consecutive numbers to fill into a 3x3, you
must have 5 even numbers and 4 odd ones, or
4 even numbers and 5 odd numbers. They must alternate odd/even in the
square. The center cell plus each of the four cells touching it sum to
four consecutive odd numbers, but one of those must be divisible by 3,
so it can't be prime, unless it is 3. But if one of them is 3, those
four numbers must be 3, 5, 7, and 9, and 9 isn't prime."
He has also sent a solution for the case 10x10:
1 
2 
3 
4 
7 
6 
5 
8 
9 
10 
12 
11 
20 
27 
16 
13 
18 
23 
14 
33 
17 
26 
21 
32 
15 
28 
19 
24 
29 
38 
30 
41 
62 
35 
44 
39 
22 
37 
42 
59 
31 
48 
65 
36 
53 
50 
51 
46 
25 
54 
40 
61 
66 
43 
60 
47 
56 
57 
82 
49 
63 
76 
73 
58 
91 
90 
83 
74 
75 
88 
86 
81 
100 
79 
72 
77 
80 
99 
52 
85 
93 
70 
97 
34 
67 
96 
71 
68 
45 
64 
98 
69 
94 
55 
84 
95 
78 
89 
92 
87 
His method "...is a brute force one  start
filling in the first row, fill in a number that forms a prime when summed
to the number to the left of it and the number above it (if they exist),
and proceed. If you get to a location that you can't fill, back up and try
another number.". His largest primal square sent is now 13x13.
***
I (C.R.) have gotten a solution to the 20x20 case with a
method that (I think) should be easily improved in order to get solutions for
any n value.
This is the method:
1. Use the value n^2 in the cell
northeast.
2. Assign all the other values to each
cell as the largest primalvalid & nonused number, proceeding by rows
from up to down, and by columns from left to right.
3. If the complete assignation to the
whole matrix is not possible then  while possible  decrease by one the
value for the northeast cell and go to step 2; or halt when there are no
more valid values for this cell.
Using the above procedure I got this solution for n=20:
225

394

393

380

389

398

399

388

385

384

377

396

391

382

387

400

397

390

383

386

392

267

376

381

362

371

320

363

298

355

306

347

336

337

364

369

322

379

378

365

395

374

285

358

315

368

341

290

309

304

313

330

323

354

319

340

361

372

305

326

366

353

356

303

344

375

302

357

352

349

370

331

360

373

328

333

286

367

342

335

343

348

251

350

297

334

339

274

325

294

307

346

301

318

289

310

321

292

277

324

316

283

258

359

272

327

314

345

268

253

270

271

300

299

288

259

250

351

280

223

291

208

241

282

275

332

329

248

273

226

217

232

247

210

311

198

211

256

243

244

308

279

262

295

312

287

284

293

230

261

202

255

184

199

180

281

276

265

214

235

269

338

171

196

187

234

257

264

227

296

207

254

249

190

229

228

233

168

205

252

278

263

260

201

172

175

246

245

222

167

242

237

212

231

118

193

216

215

204

317

221

240

239

218

165

142

151

186

197

266

191

206

177

170

219

238

181

132

185

224

236

203

194

179

188

195

112

145

192

155

182

131

176

213

220

163

150

161

152

159

183

164

189

200

209

158

111

166

115

162

149

120

173

140

153

154

157

156

125

104

148

129

178

93

98

135

146

147

136

121

108

143

174

137

86

87

124

127

144

119

169

100

139

130

141

128

123

160

133

106

91

138

103

126

113

110

117

64

85

114

102

97

94

99

92

105

134

63

46

67

90

101

96

71

80

83

116

75

88

109

95

84

79

58

81

76

33

74

57

82

49

78

61

66

47

56

107

122

69

70

72

65

48

55

28

73

40

39

50

21

52

31

42

41

62

51

32

77

20

27

59

44

53

54

43

36

7

34

9

38

45

22

37

60

89

8

35

26

17

14

68

29

30

13

24

23

6

25

4

15

16

1

10

19

18

11

12

5

2

3

This simple & mechanical procedure is
successful without any other refinement for n = 7(39), 8(62), 13(111), 16(238), 17(165), 19(65),
20(226), 21(237), ...
In parentheses is the northeast
cell value (the largest or first in descending order) for the corresponding nxn square.
I guess that with a light refinement this
strategy may work out solutions for all n values.
***
One day after (25/12/2000)I got the following solutions: 30(492),
40 (1336) . In order to get these examples
my code used 37 minutes & 1hr.37minutes, respectively, running in a 400
Mhz PC.
***
Paul Jobling produced (29/12/2000) his
own code and has sent solutions for the 45x45, 50x50, 100x100 & 150x150
primal square cases. If anybody wants the solutions I can send them on
request. Regarding his method, he wrote:
My program works as follows. The order is
to go across a line, then down a column. For example, for a 6x6 it would
do them in the following order:
1 2 3 4 5
6
7 12 13 14 15 16
8 17 21 22 23 24
9 18 25 28 29 30
10 19 26 31 33 34
11 20 27 32 35 36
Note that this does not matter so much for
simple squares, but when searching for one which has the full torus
property, this allows you to check the torus conditions sooner.
I work from n^2 downwards, and place the
largest unused value in each cell in turn (in the order outlined above). I
then check that the number is valid by checking the sum with the number on
the left and the number above. If either of these sums is not prime I
decrement the number and test again. If I get to 0, I backtrack to the
previously filled in square and decrement its value (in fact, rather than
decrementing I subtract two, as the following paragraph will make clear).
The program only works for even values of
n. To speed up the search I impose the following conditions: that the top
left contains an even number, so the top row is even, odd, even, etc; the
second row is odd, even, odd, etc; etc. Due to the symmetries I also
constrain that the cell to the right of the top left must contain a higher
value than the cell underneath the top left  this halves the search
time.
My program can generate about 1 million
partial valid positions per second on this 500 MHz PIII (where 'partial
valid' means that all of the numbers that have been placed in the cells so
far match the primality criteria with their neighbours). The inner loop,
which find partial valid positions, is written in assembler. Outside this
inner loop is just some code which writes out the current position to the
screen every 2^20 iterations, and sees if a solution has been found
and writes it out to a file if it has.
The main speed up is obtained by using preinitialised
arrays wherever possible  for example, the primality check is just a
lookup into an array. This makes the assembly inner search loop just 35
instructions long.
***
He also says that no magical & primal
square 4x4 was found.
***
Regarding the "full torus condition"
definition he did it the following way, on my request:
"Each number in a cell is a distance y
from an edge. The sum of this number with the number at the distance y
in from the opposite edge must also be prime. Note that these are all four
edges. For example, in the 8x8 square
a+b must be prime, as must a+c, b+d, and c+d."
***
This is an example of an 8x8 primal square that
I (C.R.) have produced with a very primitive code mainly &
just to illustrate the full torus condition, but
it is not a real solution because it uses
numbers greater than 64 & nonconsecutive.
28

99

158

155

156

125

152

129

151

142

135

44

137

146

87

22

132

109

148

93

140

123

154

79

61

120

121

136

57

106

73

150

138

103

76

147

134

117

124

133

145

88

63

104

89

122

75

118

82

69

128

153

74

105

92

159

111

130

21

86

107

32

141

110

Hopefully soon Paul will provide a real
solution of this kind of primal squares. He is working right now in the 6x6
case. By his way Jean Charles Meyrignac will attempt to make an
exhaustive search for the magic 6x6 primal square.
***
The 3/1/2001 Paul Jobling announces "I
have completed the search and found no 6x6 with the full torus property".
***
