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]

Advertisements

14 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)
    
    # start with 0 and discard it later
    solve([0], 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[0] not in tr: continue
            s2=L[0]+L[1]
            s3=s2+L[2]
            s4=s3+L[3]
            s5=s4+L[4]
            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:
           print("Answer:",L)
           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'
    def add_nbr(nbrs, lnths, totals, 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)
    
    add_nbr([], [], [], set())
    
  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[0] not in tr: continue
            s2=L[0]+L[1]
            s3=s2+L[2]
            s4=s3+L[3]
            s5=s4+L[4]
            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:
           print("Answer:",L)
           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[0]))]
      elif ln == 2:
        yield r + [int(str(s[0]) + str(s[1]))]
        yield r + [int(str(s[1]) + str(s[0]))]
      else:
        for i in range(1, len(s)):
          yield from split(s[1:i] + s[i+1:], r + [int(str(s[0]) + str(s[i]))])
          yield from split(s[1:i] + s[i+1:], r + [int(str(s[i]) + str(s[0]))])
    
    # 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]>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[10]={0,0,0,0,0,0,0,0,0,0};
    	
    	
    	
    		
    	if (!(digitonce(added,digits)))
    		return false;
    	
    	for (i=0;i<counter;i++){
    		
    		
    		num=*(numbers+i);
    		
    		if (!digitonce(num,digits))
    			return false;
    		
    		if (num>10)
    		{
    			if (gcd(added,num)!=1)	
    				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[34],number=0;
    	Triangles(Tnum);
    	int numbers[5]={0,0,0,0,0};
    	for (int i=0;i<33;i++)
    	{
    		number=Tnum[i];
    		numbers[0]=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

  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
          %
          

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: