# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1766: Triangular sums

From New Scientist #2934, 14th September 2013 [link]

I have listed in random order five positive integers, four of two digits and one of one digit. They use each of the digits 1 to 9. None of the two-digit integers has any factor greater than 1 in common with any other of the two-digit integers. The first of the integers in my list is a triangular number. The sum of the first two, the sum of the first three, the sum of the first four and the sum of all five are also triangular numbers.

What are my integers in the order in which I have listed them?

[enigma1766]

### 15 responses to “Enigma 1766: Triangular sums”

1. Jim Randell 11 September 2013 at 6:49 pm

I’m glad to see the puzzles are becoming a little more challenging. The difficulty here is keeping track of all the conditions. This recursive Python program runs in 39ms.

```from itertools import count
from enigma import T, irange, gcd, printf

# s - sequence of solution numbers
# i - index of previous triangular number
# f - flag set when a single digit number is used
# ds - digits used
def solve(s, i, f, ds):
# are we done?
if len(s) == 6:
# if we've used a 1-digit number we're done
if f: print(s[1:])
else:
# try to extend the sequence by finding the next tri
for j in count(i + 1):
# the solution number is the difference from the previous tri
n = T(j) - T(i)
# it must be 1- or 2-digit
if n > 99: break
# and if it's 1-digit it should be the only one
if f and n < 10: continue
# and it shouldn't use any digits we've already seen (or 0)
d = str(n)
ds2 = ds.union(d)
if len(ds2) != len(ds) + len(d): continue
# and it should have no divisors in common with other 2-digit numbers
if any(gcd(n, x) > 1 for x in s[1:] if x > 9): continue
solve(s + [n], j, f | (n < 10), ds2)

solve(, 0, False, set('0'))
```

Solution: The list of integers is: 6, 49, 23, 58, 17.

2. Naim Uygun 11 September 2013 at 8:30 pm
```import fractions
from itertools import permutations
tr=[n*(n+1)//2 for n in range(1,34)]
for a1,a2,b1,b2,c1,c2,d1,d2,e in permutations(range(1,10),9):
a=10*a1+a2
b=10*b1+b2
c=10*c1+c2
d=10*d1+d2
l=[a,b,c,d,e]
flag=0
for L in permutations(l,5):
if L not in tr: continue
s2=L+L
s3=s2+L
s4=s3+L
s5=s4+L
if fractions.gcd(a, b) != 1 : continue
if fractions.gcd(a, c) != 1 : continue
if fractions.gcd(a, d) != 1 : continue
if fractions.gcd(b, c) != 1 : continue
if fractions.gcd(b, d) != 1 : continue
if fractions.gcd(c, d) != 1 : continue
if s2 not in tr: continue
if s3 not in tr: continue
if s4  not in tr: continue
if s5 not in tr: continue
flag=1
break
if flag==1:
break

```
3. Brian Gladman 11 September 2013 at 9:56 pm

Pretty similar to Jims version.

```from itertools import combinations

# the greatest common divisor of two numbers
def gcd(x, y):
while y > 0:
x, y = y, x % y
return x

# triangular numbers less than 406
tr = [x * (x + 1) // 2 for x in range(1, 29)]

# add a number to 'nbrs' with their lengths in  'lnths', their
# cumulative sum in 'totals' and the digits used in 'digits'
ln = len(nbrs)

# if we have 5 numbers
if ln == 5:
# with only one of length one and using the digits 1 to 9
if lnths.count(1) == 1 and len(digits) == 9:
print(nbrs, totals)

else:
# numbers other than the first are the difference between
# two triangular numbers with a difference less than 100;
# the first is triangular
for t in tr:
n = t - (totals[-1] if totals else 0)
if 0 < n < 100:
s, z = str(n), set(str(n))
# we don't want a zero digit in n, nor two lengths equal to one,
# nor shared digits, nor two digit numbers with GCD's > 1
if ('0' not in s and lnths.count(1) < 2 and not (digits & z)
and (n < 10 or all(gcd(n, x) == 1 for x in nbrs if x > 9))):
add_nbr(nbrs + [n], lnths + [len(s)], totals + [t], digits | z)

```
4. Naim Uygun 12 September 2013 at 6:00 am

Execution time is better than its previous version.

```
# Enigma 1766 Triangular Sums
# Answer: (6, 49, 23, 58, 17)
from fractions import gcd
from itertools import permutations
tr=[n*(n+1)//2 for n in range(1,34)]
for a1,a2,b1,b2,c1,c2,d1,d2,e in permutations(range(1,10),9):
a=10*a1+a2
b=10*b1+b2
c=10*c1+c2
d=10*d1+d2
if gcd(a, b) != 1 : continue
if gcd(a, c) != 1 : continue
if gcd(a, d) != 1 : continue
if gcd(b, c) != 1 : continue
if gcd(b, d) != 1 : continue
if gcd(c, d) != 1 : continue
l=[a,b,c,d,e]
flag=0
for L in permutations(l,5):
if L not in tr: continue
s2=L+L
s3=s2+L
s4=s3+L
s5=s4+L
if s2 not in tr: continue
if s3 not in tr: continue
if s4  not in tr: continue
if s5 not in tr: continue
flag=1
break
if flag==1:
break
```
5. Brian Gladman 12 September 2013 at 9:06 am

This non-recursive version is a lot slower than the recursive solutions.

```from itertools import combinations, permutations

# split a string of characters into four two-digit
# numbers and one one-digit number
def split(s, r = []):
ln = len(s)
if ln == 1:
yield r + [int(str(s))]
elif ln == 2:
yield r + [int(str(s) + str(s))]
yield r + [int(str(s) + str(s))]
else:
for i in range(1, len(s)):
yield from split(s[1:i] + s[i+1:], r + [int(str(s) + str(s[i]))])
yield from split(s[1:i] + s[i+1:], r + [int(str(s[i]) + str(s))])

# check for coprime two digit numbers
def test_gcds(x):
for a, b in combinations((i for i in x if i > 9), 2):
while b > 0:
a, b = b, a % b
if a > 1:
return False
return True

# triangular numbers less than 406
tr = set(x * (x + 1) // 2 for x in range(1, 29))

# check for triangular cumulative sums
def test_csums(x):
t = 0
for i in x:
t += i
if t not in tr:
return False
return True

# split the digits into four two-digit and one one-digit number
for nbrs in split(list('123456789')):
# permute the five numbers
for p in permutations(nbrs):
# check that the cumulative sums are triangular
# and that the two digit values are coprime
if test_csums(p) and test_gcds(p):
print(p)
```
6. saracogluahmet 12 September 2013 at 2:48 pm

if speed or time does matter too much, I did write this in C++,

```#include <iostream>
void Triangles(int *tri){
int i;
for (i=1;i<34;i++){
*(tri+i-1)=i*(i+1)/2;
}

}

int gcd ( int a, int b )
{
if ( a==0 ) return b;
return gcd ( b%a, a );
}

bool digitonce(int number,int *digits){

while (number>0){
digits[number%10]+=1;
number/=10;
}

if (digits>0)
return false;

for (int j=1;j<10;j++){
if (digits[j]>1)
return false;
}
return true;
}

bool CheckRule(int added,int trcandi,int *tri,int *numbers,int counter){

int i,j,num,tnum=0;
int digits={0,0,0,0,0,0,0,0,0,0};

return false;

for (i=0;i<counter;i++){

num=*(numbers+i);

if (!digitonce(num,digits))
return false;

if (num>10)
{
return false;
}

}

for ( i=0;i<34;i++){
if (trcandi==*(tri+i))
return true;

}
return false;
}

void search(int *tri,int Number,int counter,int *numbers){
int number;

if (counter==5)
return;

for (int j=10;j<100;j++){

Number=Number+j;

if (CheckRule(j,Number,tri,numbers,counter)){
numbers[counter]=j;
if (counter==4){
std::cout<<	"FOUND"<<"\n\n";
for (int i=0;i<=counter;i++){
std::cout<<numbers[i]<<"\n\n";
}
}
search(tri,Number,counter+1,numbers);

}

Number=Number-j;

}

}

int main(int argc, char** argv) {
int Tnum,number=0;
Triangles(Tnum);
int numbers={0,0,0,0,0};
for (int i=0;i<33;i++)
{
number=Tnum[i];
numbers=number;
search(Tnum,number,1,numbers);

}
return 0;
}
```
• Jim Randell 13 September 2013 at 3:28 pm

No particular point here, just some musings on the timing of code…

Compiling this C++ code and running the same timing procedure that I run on my Python programs on the resulting program reports that it takes 8ms to run (about 5 times faster than my Python program). However I expect the vast majority of this time is taken up with the housekeeping that the operating system does to run the process, rather than the time taken to actually solve the problem.

But, you could argue that Python program is being unfairly disadvantaged by this comparison, as we’re measuring the execution time of a piece of compiled native code, not the program as it was originally written. If I measure the time taken to compile the C++ program to native code (using the default compiler settings), that comes to 193ms, giving an overall time of 201ms. So we could equally say that the Python code is 5 times faster than the C++ code, if the time taken to compile the code is taken into account.

• saracogluahmet 13 September 2013 at 4:15 pm

What I am trying to say this, if the speed is important to us, the execution speed sure, I am talking about that, then no need to use C++

The code is not so optimum, it can be speeded up assembly routines inline, and or cpu registers

I have not written that to be compared with Python, I guess no need to make a comparison

I agree that Python is easy to use, whereas programming in C++ requires more knowledge I guess

• saracogluahmet 13 September 2013 at 4:43 pm

No need use Python, I was going to say instead no need to use C++, sorry

7. Satish Ramakrishna 19 October 2013 at 2:34 pm

I just saw this and I think it might be useful to clarify that an exhaustive computer search is probably as time consuming to construct as a solution as below (I did use Excel to make the first table). I have on the x- and y-axes, the triangular numbers up to 496 – I stopped when the differences became mostly 3 -digit numbers. The body of the matrix is the difference between the top row of the matrix (the triangular numbers) and the left side column (the triangular numbers again). I don’t need to consider more than the top right triangle of the matrix, not interested in 0 or negative numbers for differences
I can’t paste the table here, but here is how it looks for a few rows and columns

```	1	3	6	10	15	21	28	36	45
1		2	5	9	14	20	27	35	44
3			3	7			25	33
6				4	9		22	30
10					5	11	18	26	35
15						6	13	21	30
21							7	15	24
28								8	17
36									9
45
```

etc
Now from the body of the matrix, eliminate differences with
– repeated digits
– anything with 0 in it
– anything where the left side is a single digit number and the difference is also a single digit number (since there is only one single digit number)

Now, we would have the first number be a two digit number and the second could be one digit. Or the first number could be one digit and the second could be two digit. A moment’s inspection reveals that you can’t have a situation where the third or higher number is one digit – it doesn’t work.

In the first case, the choices are

Number 1=> 10 15 21 28 36
Number 2=> 5 6 7 8 9
The pair 1(10,5) doesn’t work – 10 has a zero in it.
The pairs (15,6), (21,7), (36,9) are not co-prime
The pair (28,8) has 8 repeated

So, the first number has to be a single digit number.
There are 18 possibilities.
10 are eliminated either because digits repeat (you have to have 1,..9, no repeats) or they are not co-prime
The only one that survives is 6,49,23,58,17

8. Satish Ramakrishna 19 October 2013 at 2:35 pm

It looks like the tabs just vanished in the table after I saved the comment down… Hmm. Let me know if the argument is not clear.

• Jim Randell 24 October 2013 at 6:25 pm

The whitespace was retained, so I was able to surround the table with `<pre> ... </pre>` tags to bring back the formatting.

• Satish Ramakrishna 26 October 2013 at 12:32 pm

ah, thanks! I looked at the change on my iPhone when I noticed your message – It didn’t look good on my iPhone, though why anyone would want to look at a coding-based web page on an iPhone, I don’t know!

• geoffrounce 16 March 2016 at 4:17 pm

I found a solution in MiniZinc with the first permutation I tried of the five integers.
However, this is not a rigorous solution, as it does not check all the permutations of the five integers – this enigma was a bit tricky in MiniZinc.

```% A solution in MiniZinc
include "globals.mzn";
solve satisfy;

var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D; var 1..9:E;
var 1..9:F; var 1..9:G; var 1..9:H; var 1..9:I;

constraint alldifferent([A,B,C,D,E,F,G,H,I]);

% function ex Hakan Kjellerstrand
function var int: gcd(var int: x, var int: y) =
let {
int: p = min(ub(x),ub(y));
var 1..p: g;
constraint
exists(i in 1..p) (
x mod i = 0 /\ y mod i = 0
/\
forall(j in i+1..p) (
not(x mod j = 0 /\ y mod j = 0)
) /\ g = i);
} in g;

% Four two digit numbers
var 10..99: AB; var 10..99: CD; var 10..99: EF; var 10..99: GH;

constraint AB = 10*A + B /\ CD = 10*C + D /\ EF = 10*E + F /\ GH = 10*G + H
/\ alldifferent ([AB,CD,EF,GH]);

set of int: tri_nums = {1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,
171,190,210,231,253,276,300,325,351,378,406,435,465,496,528,561,595,630,666,
703,741,780,820,861,903,946,990};

% None of the two-digit integers has any factor greater than 1 in
% common with any other of the two-digit integers
constraint 1 == gcd(AB,CD) /\ 1 == gcd(AB,EF) /\ 1 == gcd(AB,GH)
/\ 1 == gcd(CD,EF) /\ 1 == gcd(CD,GH) /\ 1 == gcd(EF,GH);

% The first number is triangular, the sum of the first two, the sum of the first three,
% the sum of the first four and the sum of all five are also triangular numbers.
constraint I in tri_nums /\ (I + AB) in tri_nums /\ (I + AB + CD) in tri_nums /\
(I + AB + CD + EF) in tri_nums /\ (I + AB + CD + EF + GH) in tri_nums;

output["Listed order of 5 integers is : " ++show(I) ++ ", " ++ show(AB) ++ ", "
++ show(CD) ++ ", " ++ show(EF) ++ ", " ++ show(GH)];

% Listed order of 5 integers is : 6, 49, 23, 58, 17
% Finished in 104msec
%
```
9. Jim Randell 1 July 2018 at 10:18 am

Here’s a solution using the [[ `SubstitutedExpression()` ]] solver from the enigma.py library.

This run file executes in 120ms.

```#!/usr/bin/env python -m enigma -r

# suppose the numbers are:
#
#   AB  CD  EF  GH  IJ
#
# where one of A, C, E, G, I is 0

SubstitutedExpression

--invalid="0,BDFHJ"

# none of the 2-digit numbers has a factor in common with any of the
# other 2-digit numbers
"all(gcd(x, y) == 1 for (x, y) in itertools.combinations((n for n in (AB, CD, EF, GH, IJ) if n > 9), 2))"

# the first number is triangular
"is_triangular(AB)"

# the sum of the first two numbers is triangular
"is_triangular(AB + CD)"

# the sum of the first three numbers is triangular
"is_triangular(AB + CD + EF)"

# the sum of the first four numbers is triangular
"is_triangular(AB + CD + EF + GH)"

# the sum of all five numbers is triangular
"is_triangular(AB + CD + EF + GH + IJ)"
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.