Enigmatic Code

Programming Enigma Puzzles

Enigma 1497: Divide both ways

From New Scientist #2659, 7th June 2008

Using each of the digits 1 to 9, find a 3-digit positive integer divisible by 7 whose reverse is an integer also divisible by 7, a 3-digit positive integer divisible by 9 whose reverse is an integer also divisible by 9, and a 3-digit positive integer divisible by 11 whose reverse is an integer also divisible by 11.

What are the smallest and the largest of your six integers?

[enigma1497]

Advertisements

2 responses to “Enigma 1497: Divide both ways

  1. Jim Randell 4 November 2012 at 12:24 am

    The following Python code runs in 35ms.

    from itertools import combinations
    from enigma import irange, nconcat, printf
    
    # abc is divisible by 9 when a + b + c is divisible by 9
    # so: 9 | abc => 9 | cba
    
    # also abc is divisible by 11 when a - b + c is divisible by 11
    # so: 11 | abc => 11 | cba
    
    # so we don't need to test the divisibility criteria for r9 or r11
    
    # generate 3-digit numbers, divisible by n
    # yield <sequence of digits>, <integer>, <reverse integer>
    # (each <integer>, <reverse integer> pair is only returned once)
    def generate(ds, n):
      for (a, b, c) in combinations(ds, 3):
        for s in ((a, b, c), (a, c, b), (b, a, c)):
          i = nconcat(s)
          if i % n > 0: continue
          yield (s, i, nconcat(s[::-1]))
    
    # digits we start with
    ds = set(irange(1, 9))
    # choose a number divisible by 7
    for (s7, n7, r7) in generate(ds, 7):
      # need to check r7 is divisible by 7
      if r7 % 7 > 0: continue
    
      # from the remaining digits chose a number divisible by 9
      ds1 = ds.difference(s7)
      for (s9, n9, r9) in generate(ds1, 9):
    
        # and from the remaining digits chose a number divisible by 11
        ds2 = ds1.difference(s9)
        for (s11, n11, r11) in generate(ds2, 11):
    
          # compute min and max
          mn = min(n7, r7, n9, r9, n11, r11)
          mx = max(n7, r7, n9, r9, n11, r11)
          printf("min={mn} max={mx} [n7={n7} r7={r7} n9={n9} r9={r9} n11={n11} r11={r11}]")
    

    Solution: The smallest integer is 168. The largest integer is 957.

    • geoffrounce 2 April 2017 at 4:41 pm
      % A Solution in MiniZinc
      include "globals.mzn";
       
      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]);
       
      % Form three 3-digit integers 
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: DEF = 100*D + 10*E + F;
      var 100..999: GHI = 100*G + 10*H + I;
      
      % and their reverse numbers
      var 100..999: CBA = 100*C + 10*B + A;
      var 100..999: FED = 100*F + 10*E + D;
      var 100..999: IHG = 100*I + 10*H + G;
      
      % Divisibility constraints
      constraint ABC mod 7 == 0 /\ CBA mod 7 == 0;
      constraint DEF mod 9 == 0 /\ FED mod 9 == 0;
      constraint GHI mod 11 == 0 /\ IHG mod 11 == 0;
      
      solve satisfy;
      
      output [ "Minimum of six integers = " ++ show(min ([ABC, DEF, GHI, CBA, FED, IHG]))
      ++ "\n" ++ "Maximum of six integers = " ++ show(max ([ABC, DEF, GHI, CBA, FED, IHG])) 
      ++ "\n" ++ "Six integers are: " ++ show ([ABC, DEF, GHI, CBA, FED, IHG])];
      
      % Minimum of six integers = 168
      % Maximum of six integers = 957
      % Six integers are: [168, 423, 957, 861, 324, 759]
      % ----------
      % Finished in 79msec
      

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: