Puzzle 576.- Triangular Magic Triangles

Problems & Puzzles: Puzzles

Puzzle 576.- Triangular Magic Triangles

Here I'm asking by triangular pointing down arrangements of the smallest consecutive positive integers , such that every three contiguous numbers in a triangular sub-shape pointing down, must add up to the same quantity.

Examples:

3 rows, 4 solutions

Sum = 9 = 6+2+1 = 2+4+3 = 1+3+5
6 2 4
1 3
5

Sum=10
2 3 6
5 1
4

Sum=11
1 4 5
6 2
3

Sum=12
1 5 3
6 4
2

4 rows, 2 solutions

Sum = 16 = 10+1+5 = 1+8+7 = 8+2+6 = 5+7+4 = 7+6+3 = 4+3+9

10 1 8 2
5 7 6
   4 3
    9

Sum=17
9 5 8 2
3 4 7
10 6
    1

Q1. Please send links to other pages dealing with these objects, other than: http://www.puzzles.com/puzzleplayground/MagicTriangle3X/MagicTriangle3X.htm

Q2. Are there more solutions for K>4 rows, using consecutive positive integers?

Q3. Send solutions for K>2, using consecutive primes, the minimal sum the better, for each K value.

Contributions came from: Torbjörn Alm, Seiji Tomita, Jan van Delden, Giovanny Resta, Hakan Summakoğlu, & W. Edwin Clark

***

Torbjörn Alm, Seiji Tomita, Jan van Delden, Giovanny Resta & Hakan Summakoğlu found the same solutions to Q3:

k=3, Sum = 35
7 11 19
17 5
13

k=4, sum=731
227 241 251 257
263 239 223
229 229
233

***

Jan Added:

K=4, Smallest solution with similar layout as the one with sum=16 starts with prime 1704931

K=4, Smallest solution with similar layout as the one with sum=17 starts with prime 3068903

If this puzzle has a solution using the numbers [1..T(n)], with n the number of rows (and T(n)=(1+n)n/2), then it also has solutions using any arithmetic series (using consecutive entries), because the triangle sums are invariant to addition with a constant or multiplication with a constant (for each number). More general if a set of numbers with consecutive differences d[i] (doesn’t) generates a solution then all derived sets of numbers with consecutives difference k.d[i] (don’t) generate a solution, with k a general constant (<>0).

I used a procedure, starting at the left point in the top row, move to the right 1 point (top row) finishing the first triangle (defining the triangle sum). Followed by the next point in the top row and checking the remaining triangles etc. (So n+1 choices). I could find some (‘sharp’) bounds on the triangle sums, given the numbers employed (will omit them here).

I didn’t find a solution for K>4, the maximum number of equal sums I did obtain was 9. My “instinct” tells me the prove that no such solution exists “is out there”.

If primes are used, the list of consecutive differences must be “admissible” in the sense that it may not contain a complete residue set mod q for all q<T(n). Maybe it’s easy to see that in order to have enough equal triangle sums we must have that all residues mod 3 are used and hence no solution for K>4 using consecutive primes.

Giovanni Resta added:

Q2, I searched for other larger solutions (K=5,...,9) with consecutive integers to no avail ...

Q3, I had more luck with consecutive set of primes. These are the minimal solutions
for sets of consecutive primes and K=3,4,5.

K=5 Primes from 12546207413 to 12546207607, common sum 37638622523.
-----------------
12546207551 12546207511 12546207521 12546207473 12546207469
12546207461 12546207491 12546207529 12546207581
12546207571 12546207503 12546207413
12546207449 12546207607
12546207467
-----------------

If the primes are not required to be consecutive, but just distinct,
it is much easier to find larger solutions. This, for example, is a minimal (in the sense of the largest prime used)
solution for K=9, with common sum equal to 1697.
---------------------------------------------
457 1061 137 673 857   11 1087 263 947
179 499 887 167 829 599 347 487
1019 311 643 701 269 751 863
367 743 353 727 677   83
587 601 617 293 937
509 479 787 467
709 431 443
557 823
317

***

On my request,

Can you please compute the minimal solution (Sum) to Puzzle 576 using 15
positive integers not necessarily consecutive?

Giovanni Resta wrote (Feb 21, 2011):

For K=5, the solution with minimal sum (sum=24) uses the numbers up to
19.
-------------------------
14 8 10 1 19
2 6 13 4
16 5 7
3 12
9
-------------------------

However, the solution with minimal maximal number (17) is:
--------------------------------
10 15 2 11 7
1 9 13 8
16 4 5
6 17
3
--------------------------------
with common sum equal to 26.

Below I report the minimal solutions (with respect
to sum and/or maximal number) for K=6,7,8,9,10.

minimal sum K=6 (n=27, s=33)
-----------------
27 1 14 12 4 26
5 18 7 17 3
10 8 9 13
15 16 11
2 6
25
-----------------

minimal max K=6 (n=24, s=36)
-----------------
3 10 17 6 22 2
23 9 13 8 12
4 14 15 16
18 7 5
11 24
1
-----------------

for K=7 the two minimal solutions coincide
n=34, sum=48.
-----------------
34 9 10 30 2 20 21
5 29 8 16 26 7
14 11 24 6 15
23 13 18 27
12 17 3
19 28
1
-----------------

minimal sum K=8 (n=52, s=60)
-----------------
27 11 28 6 38 12 5 52
22 21 26 16 10 43 3
17 13 18 34 7 14
30 29 8 19 39
1 23 33 2
36 4 25
20 31
9
----------------------

minimal max K=8 (n=45, s=67)
-----------------
31 2 33 28 3 45 14 10
34 32 6 36 19 8 43
1 29 25 12 40 16
37 13 30 15 11
17 24 22 41
26 21 4
20 42
5
--------------------

minimal sum K=9 (n=66, s=75)
-----------------
66 1 23 42 4 44 18 7 65
8 51 10 29 27 13 50 3
16 14 36 19 35 12 22
45 25 20 21 28 41
5 30 34 26 6
40 11 15 43
24 49 17
2 9
64
-----------------

minimal max K=9 (n=57, s=83)
-----------------
10 16 47 22 15 50 3 54 4
57 20 14 46 18 30 26 25
6 49 23 19 35 27 32
28 11 41 29 21 24
44 31 13 33 38
8 39 37 12
36 7 34
40 42
1
-----------------

minimal sum K=10 n= 82 S=101
-----------------
4 76 13 29 50 14 54 24 15 79
21 12 59 22 37 33 23 62 7
68 30 20 42 31 45 16 32
3 51 39 28 25 40 53
47 11 34 48 36 8
43 56 19 17 57
2 26 65 27
73 10 9
18 82
1
-----------------

minimal max K=10 N=77 S=117
-----------------
49 65 5 71 26 22 77 9 35 72
3 47 41 20 69 18 31 73 10
67 29 56 28 30 68 13 34
21 32 33 59 19 36 70
64 52 25 39 62 11
1 40 53 16 44
76 24 48 57
17 45 12
55 60
2
-----------------

To solve Puzzle 576 I used a very simple recursive program
written in C language.

I had slightly different versions of the program, but the basic
idea is straightforward:

I started from the bottom of the triangle, by selecting
the 3 numbers in the corner. To cut in half the possibilities
exploiting symmetry, I only considered cases in which the 2 number on the penultimate row were in ascending order.

Once the 3 numbers are selected (I simply considered all the
possibilities), I have the goal sum and using it as a guideline I
can fill the rest of the triangle recursively.

Each step of the recursion works in this way:
if I had to fill the beginning of a row (and thus
I only know the sum and the element in the row below the current position)
I try all the unused numbers (provided that the sum with
the element below does not already exceed the goal sum).

If instead I've to fill an inner element of the row,
then I have no choices, since given the sum, the neighbor on the
row and the neighbor on the row below, the current element is
completely determined, so I have only to check if it is still available.

To speed up things, when I searched for consecutive primes,
I did two things. First I subtracted from the set of tentative primes
the smallest one, then I used a binary vector to check easily
if a number is a prime or not and it is still available.
So, for example, given the set of consecutive primes
(11 13 17 19 23 31), I reduced them to (0 2 6 8 12 20), then
I used a vector of 21 positions which was set initially to 1 only for
elements 0, 2, 6, 8, 12, and 20. In this way, given a number,
I could check fast if it is valid and still available.

***

W. Edwin Clark wrote (Feb 25, 11)

CLAIM: There are no solutions in consecutive
integers for Puzzle 576 for 5,6 or 7 row.

METHOD OF PROOF. To prove that there are NO solutions to
puzzle 576 for the case of 5 rows with consecutive integers
it suffices to prove that the 10 equations:

A51+(A52+A41)= K,
A52+(A53+A42)= K,
A53+(A54+A43)= K,
A54+(A55+A44)= K,
A41+(A42+A31)= K,
A42+(A43+A32)= K,
A43+(A44+A33)= K,
A31+(A32+A21)= K,
A32+(A33+A22)= K,
A21+(A22+A11)= K,

have no distinct solutions for the 15 variables
A11,A21,A22,...,A55
in the ring of integers modulo 15 since a solution
for the variables in consecutive integers would give
distinct solutions modulo 15.

15! is too large to check by brute force but using the
"model builder" Mace4 (http://www.cs.unm.edu/~mccune/prover9/)
I was able to verify that no distinct solutions exist modulo 15.

Using a similar technique with Mace4 I also
was able to verify that no solutions exist for
6 or 7 rows. [This is consistent with the empirical results by Resta above] I didn't try 8 rows.

***

Records | Conjectures | Problems | Puzzles