Design a site like this with WordPress.com
Get started

Tagged: by: Andrew Skidmore Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 4:02 pm on 27 January 2023 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3149: Cube route 

    From The Sunday Times, 29th January 2023 [link]

    I have a set of ten cards, each of which has a different digit written on it. All the cards have been used to make a set of prime numbers. After discarding the smallest prime, and without changing the order of any cards, I have placed the remaining primes in order of decreasing size to give a large number. It is possible, without changing the order of any cards, to break this number into a set composed entirely of cubes. Neither set contains a number with more than four digits.

    List, in order of decreasing size, my set of prime numbers.

    [teaser3149]

     
    • Jim Randell 4:31 pm on 27 January 2023 Permalink | Reply

      This Python program uses the [[ mcover() ]] (exact multiset cover) routine from the enigma.py library, that I implemented for Enigma 1712 (and also used in Teaser 2690).

      It runs in 239ms.

      Run: [ @replit ]

      from enigma import (
        primes, powers, inf, is_duplicate, group, item,
        multiset, mcover, trim, join, printf
      )
      
      # select numbers (as strings) with up to <k> digits and no repeated digits
      def select(seq, k=4):
        for n in seq:
          s = str(n)
          if len(s) > k: break
          if is_duplicate(s): continue
          yield s
      
      # cubes and primes up to 4-digits (as strings)
      cbs = group(select(powers(0, inf, 3)), by=item(0))  # grouped by first digit
      prs = dict((s, multiset.from_seq(s)) for s in select(primes))  # mapped to digit content
      
      # chop string <t> into segments from <ss>
      def chop(t, ss, rs=[]):
        # are we done?
        if not t:
          yield rs
        else:
          for s in ss.get(t[0], []):
            if t.startswith(s):
              yield from chop(trim(t, head=len(s)), ss, rs + [s])
      
      # find primes that cover each digit exactly once
      for ps in mcover(prs, multiset.from_seq("0123456789")):
        # put them in order
        ps.sort(key=(lambda n: (len(n), n)), reverse=1)
        # make the large number, by discarding the smallest prime
        n = join(trim(ps, tail=1))
        # chop the large number into cubes
        for ss in chop(n, cbs):
          printf("{ps} -> {n} -> {ss}", ps=join(ps, sep=":"), ss=join(ss, sep=":"))
      

      Solution: [To Be Revealed]

      Like

  • Jim Randell 9:04 am on 22 November 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2688: Mother’s Day 

    From The Sunday Times, 30th March 2014 [link]

    Today we are having a family get-together to celebrate Mother’s Day. My maternal grandmother, my mother and I have each written down our date of birth in the form “ddmmyy”. This gives us three six-figure numbers and, surprisingly, both of the ladies’ numbers are multiples of mine. Furthermore, all of the digits from 0 to 9 occur somewhere in the three six-figure numbers.

    What is my mother’s six-figure date of birth?

    [teaser2688]

     
    • Jim Randell 9:05 am on 22 November 2022 Permalink | Reply

      At first I found many possible solutions to this puzzle.

      But if we require that the 6-digit numbers formed from the date cannot have a leading zero, then this narrows down the solution space considerably (and essentially restricts the three dates to the form 10xxxx, 20yyyy, 30zzzz, and the multiples being 1, 2, 3).

      This Python program runs in 129ms.

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (
        fdiv, inc, repeat, nconcat, nsplit, catch,
        subsets, append, tuples, union, join, printf
      )
      
      # extract date as a 6-digit number
      def number(d):
        if d.day < 10: return None
        return nconcat(d.day, d.month, d.year % 100, base=100)
      
      # check viable generation gap, a -> b
      def gap(a, b):
        y = fdiv((b - a).days, 365.2422)
        return not (y < 16 or y > 50)
      
      # consider dates for the setters birthdate
      for d in repeat(inc(timedelta(days=-1)), date(2014, 3, 30)):
        if d.year < 1922: break
        # construct the number "ddmmyy"
        n = number(d)
        if n is None: continue
        # look for proper multiples that also give a valid date
        mn = n
        ds = list()
        while True:
          mn += n
          if mn > 311299: break
          (dd, mm, yy) = nsplit(mn, base=100)
          for y in (1900 + yy, 1800 + yy):
            if y < 1892: continue
            md = catch(date, y, mm, dd)
            if md is None or number(d) is None: continue
            ds.append(md)
      
        # look for a set of 3 plausible ages
        for ss in subsets(sorted(ds), size=2):
          ss = append(ss, d)
          if not all(gap(a, b) for (a, b) in tuples(ss, 2)): continue
          # check all digits are used
          if len(union(nsplit(number(d)) for d in ss)) < 10: continue
          # output dates
          printf("{ss}", ss=join(ss, sep=" -> "))
      

      The program works backwards from 2014 to 1922 looking for sets of 3 dates that make a plausible set of birthdates for the three generations.

      It finds 2 possible situations, as below (ages shown are on the date the puzzle was published (2014-03-30)):

      Grandmother = 1919-08-30 (age = 94.6y)
      Mother = 1946-05-20 (age = 67.9y)
      Setter = 1973-02-10 (age = 41.1y)
      gap = 26.7y
      100273 × 2 = 200546
      100273 × 3 = 300819

      Grandmother = 1892-07-30 (age = 121.7y)
      Mother = 1928-05-20 (age = 85.9y)
      Setter = 1964-02-10 (age = 50.1y)
      gap = 35.7y
      100264 × 2 = 200528
      100264 × 3 = 300792

      The second of these is only just plausible, so presumably the first provides the required answer. (I would have preferred the puzzle eliminated one of these solutions by an explicit condition).

      Solution: The mother’s date of birth is: 200546 (i.e. 20th May 1946).

      To see solutions where the 6-digit number formed from the date is permitted to have a leading zero, the check at line 9 can be removed. In this case the program finds 115 solutions.

      Like

  • Jim Randell 4:22 pm on 18 November 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3139: Checkmate 

    From The Sunday Times, 20th November 2022 [link] [link]

    Our chess club is divided into sections, with each section having the same number of players. The two oldest members will soon be retiring from playing and we will change the number of sections. The number of sections will change by one and so will the number of players in each section, but all the sections will still have the same number of players. This will result in there being a grand total of 63 fewer matches per year if each member plays all the other members of their section once per year.

    How many players are in each section at the moment?

    [teaser3139]

     
    • Jim Randell 4:56 pm on 18 November 2022 Permalink | Reply

      If the players are split into k sections, each consisting of n players, then the number of matches in each section is C(n, 2), and the total number of matches is m = k.C(n, 2).

      We can use some analysis to simplify the puzzle to two cases, one of which has no solution for positive integers, and the other that gives us the required solution.

      However, here is a constructive Python program that considers the total numbers of players t (up to 2000), and generates the possible (n, k, m) values for each candidate t value. It then looks for two t values that differ by 2, and give n and k values that differ by 1, and m values that differ by 63.

      This Python program runs in 85ms.

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, tri, cproduct, tuples, printf)
      
      # generate (k, n, m) values for t players
      def generate(t):
        # divide them into k sections of n players each
        for (k, n) in divisors_pairs(t, every=1):
          if n < 2: continue
          # calculate the total number of matches
          m = k * tri(n - 1)
          yield (t, k, n, m)
      
      # solve for numbers of players that differ by 2
      def solve(N):
        for (zs, ys, xs) in tuples((list(generate(t)) for t in irange(1, N)), 3):
          for ((t, k, n, m), (t_, k_, n_, m_)) in cproduct([xs, zs]):
            # check the differences in the corresponding k, n, m values
            if abs(k - k_) == 1 and abs(n - n_) == 1 and m - m_ == 63:
              # output solution
              printf("{k} sections of {n} players (= {m} matches) -> {k_} sections of {n_} players (= {m_} matches)")
      
      # solve the puzzle (up to 2000 players)
      solve(2000)
      

      Solution: There are 10 players in each section.

      The club starts with 110 players, formed into 11 sections of 10 players each. There are 45 matches among the players in each section, and 495 matches in total.

      When 2 players leave there are 108 players remaining. These are formed into 12 sections of 9 players each. There are 36 matches among the players in each section, and 432 matches in total. This is 63 fewer matches.


      Manually from:

      (n ± 1)(k ± 1) = nk − 2

      we can see that (for n + k > 3) there are 2 cases:

      [Case 1] (n, k)(n + 1, k − 1)k = n − 1.

      k C(n, 2) − (k − 1) C(n + 1, 2) = 63
      n[(n − 1)(n − 1) − (n − 2)(n + 1)] = 126
      n(3 − n) = 126
      n² − 3n + 126 = 0

      Which has no solution in positive integers.

      [Case 2] (n, k)(n − 1, k + 1)k = n + 1.

      k C(n, 2) − (k + 1) C(n − 1, 2) = 63
      (n − 1)[(n + 1)n − (n + 2)(n − 2)] = 126
      (n − 1)(n + 4) = 126
      n² + 3n − 130 = 0
      (n − 10)(n + 13) = 0
      n = 10
      k = 11

      And so there are 11 sections, each with 10 players.

      Like

    • GeoffR 3:49 pm on 19 November 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Assumed No. of persons in each section before and after retirement
      var 2..25:persB; var 1..23:persA;
      
      % Assumed No. of sections before and after retirement
      var 2..25:sectB; var 1..25:sectA;
      
      % No of matches before and after retirement
      % UB = 25 * (25 * 24//2)
      var 1..7500: matchesB; var 1..7500: matchesA;
      
      % Change in number of sections is one due to two people retiring
      constraint abs(sectA - sectB) == 1;
      
      % Change in total number of persons is two
      constraint sectB * persB - 2 == sectA * persA
      /\ abs (persB - persA) == 1;
      
      % Find total number of matches before and after two people retire
      constraint 2 * matchesB = sectB * persB * (persB - 1);
      constraint 2 * matchesA = sectA * persA * (persA - 1);
      
      % Change in number of total matches is given as 63
      constraint matchesB - matchesA == 63;
      
      solve satisfy;
      
      output ["Persons per section before two retire = " ++ show(persB)
      ++ "\n" ++ "Number of sections before two retire = " ++ show(sectB)
      ++ "\n" ++ "Persons per section after two retire = " ++ show(persA)
      ++ "\n" ++ "Number of sections after two retire = " ++ show(sectA) ];
      
      
      

      Like

    • GeoffR 6:21 pm on 19 November 2022 Permalink | Reply

      
      # Assumed max no players and sections is 24 for both groups
      # Suffix 'B' for before matches and 'A' for after matches
      for playersB in range(1, 25):
        for sectionsB in range(1, 25):
          before_matches = sectionsB * (playersB * (playersB - 1) // 2)
          for playersA in range(1, 25):
            # The number of players will change by one 
            if abs(playersA - playersB) != 1:
              continue
            for sectionsA in range(1, 25):
              # The number of sections will change by one 
              if abs(sectionsA - sectionsB) != 1:
                continue
              # two players retire
              if sectionsB * playersB - 2 != sectionsA * playersA:
                continue
              after_matches = sectionsA * (playersA * (playersA - 1) // 2)
              
              # Differences in total number of matches
              if before_matches - after_matches != 63:
                continue
              # output player and sections data
              print(f"Players before two retire = {playersB} No.")
              print(f"Sections  before two retire = {sectionsB} No.")
              print(f"Players after two retire = {playersA} No.") 
              print(f"Sections  after two retire = {sectionsA} No.")
      
      

      Like

  • Jim Randell 8:40 am on 18 October 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2538: Octahedra 

    From The Sunday Times, 15th May 2011 [link]

    Fabulé’s latest jewellery creation consists of a set of identically sized regular octahedra made of solid silver. On each octahedron, Fabulé has gold-plated four of its eight equilateral triangle faces. No two octahedra are the same, but if Fabulé had to make another, then it would be necessary to repeat one of the existing designs.

    How many octahedra are there in the set?

    [teaser2538]

     
    • Jim Randell 8:40 am on 18 October 2022 Permalink | Reply

      The octahedron is the dual of the cube, so colouring the faces of an octahedron is equivalent to colouring the vertices of a cube.

      I already have some code that deals with the rotations of the faces of the cube (see: Teaser 2835), so I used that to generate the rotations of an octahedron.

      We then consider all possible octahedra with 4 faces coloured gold and 4 coloured silver, and then remove those that are equivalent by rotation.

      The following Python program runs in 53ms. (Internal run time is 2.0ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, arg, printf)
      from cube import Cube
      
      # make a cube with faces labelled in powers of 2
      fs = list(1 << i for i in irange(0, 5))
      cube = Cube(faces=fs)
      
      # extract the vertices from a cube
      def vertices(cube):
        (U, D, F, B, L, R) = cube.faces
        return (
          U + F + L, U + F + R, U + B + R, U + B + L,
          D + F + L, D + F + R, D + B + R, D + B + L,
        )
      
      # map vertex values to indices
      m = dict((v, k) for (k, v) in enumerate(vertices(cube)))
      
      # construct the rotations of the faces of an octahedron
      rot8s = list()
      for x in cube.rotations():
        rot8s.append(list(m[v] for v in vertices(x)))
      
      # now on with the puzzle ...
      
      # canonical form of a colouring of the faces of the octahedron
      def canonical(fs):
        return min(tuple(fs[r[i]] for (i, _) in enumerate(fs)) for r in rot8s)
      
      # colour k of the faces
      k = arg(4, 0, int)
      # initial colouring
      fs = list(int(i < k) for i in irange(0, 7))
      # collect all possible permutations of the faces
      rs = set(canonical(s) for s in subsets(fs, size=len, select="mP"))
      
      printf("{k} faces -> {n} different octahedra", n=len(rs))
      

      Solution: There are 7 different octahedra.

      Like

    • Hugh Casement 12:50 pm on 18 October 2022 Permalink | Reply

      I was thinking of the octahedron as two pyramids stuck together base to base, but treating its dual may be easier to visualize.

      The seven variants are then, for example:
      1. All four upper vertices.
      2 to 5. Three upper vertices and each in turn of the lower ones.
      6. Two adjacent upper vertices and their diametric opposites.
      7. Two opposite upper vertices and their diametric opposites.
      Any further patterns turn out to be repeats, rotated or reflected in one way or another (a cube has many axes of symmetry).

      If we allow ourselves any number of gold faces, from 0 to 8, then I think there are 23 variants in all.

      Like

      • Jim Randell 11:17 am on 19 October 2022 Permalink | Reply

        Yes. I’ve updated my program to allow you to specify the number of faces to be coloured:

        0 (or 8) → 1 octahedron
        1 (or 7) → 1 octahedron
        2 (or 6) → 3 octahedra
        3 (or 5) → 3 octahedra
        4 → 7 octahedra

        Which gives the 23 essentially different colourings.

        Like

    • Jim Olson 6:05 pm on 18 October 2022 Permalink | Reply

      I looked at this teaser the same as Hugh and came up with 23.

      Like

  • Jim Randell 5:01 pm on 16 September 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3130: Making squares 

    From The Sunday Times, 18th September 2022 [link] [link]

    Liam has nine identical dice. Each die has the usual numbers of spots from 1 to 6 on the faces, with the numbers of spots on opposite faces adding to 7. He sits at a table and places the dice in a 3×3 square block arrangement.

    As I walk round the table I see that (converting numbers of spots to digits) each vertical face forms a different three-figure square number without a repeating digit.

    As Liam looks down he sees six three-digit numbers (reading left to right and top to bottom) formed by the top face of the block, three of which are squares. The total of the six numbers is less than 2000.

    What is that total?

    [teaser3130]

     
    • Jim Randell 5:29 pm on 16 September 2022 Permalink | Reply

      At first I found multiple solutions. But you can find a unique answer to the puzzle if you ensure the dice really are identical.

      This Python program runs in 261ms.

      Run: [ @replit ]

      from enigma import (powers, nsplit, subsets, seq_all_same_r, nconcat, irange, printf)
      
      # some useful routines for checking dice ...
      
      # value on opposite face
      #      0  1  2  3  4  5  6
      opp = [0, 6, 5, 4, 3, 2, 1]
      
      # valid edge?
      edge = lambda x, y: x != y and x != opp[y]
      
      # construct (x, y) -> z corner maps for a right handed die
      def corners(x, y, z):
        d = dict()
        for (a, b, c) in [(x, y, z), (x, z, opp[y]), (x, opp[y], opp[z]), (x, opp[z], y)]:
          for (p, q, r) in [(a, b, c), (b, c, a), (c, a, b)]:
            d[(p, q)] = r
            d[(opp[p], opp[r])] = opp[q]
        return d
      
      # valid corner?
      # -> 0 if invalid; 1 if right-handed; -1 if left-handed
      def corner(x, y, z, d=corners(1, 2, 3)):
        r = d.get((x, y), 0)
        if r == z: return 1
        if r == opp[z]: return -1
        return 0
      
      # now on with the puzzle ...
      
      # possible 3-digit squares (as numbers) / vertical squares (as digits)
      (sqs, sqvs) = (set(), set())
      for n in powers(10, 31, 2):
        ds = nsplit(n)
        if min(ds) < 1 or max(ds) > 6: continue
        sqs.add(n)
        if len(set(ds)) == 3: sqvs.add(ds)
      
      # consider the layout:
      #
      #     W V U
      #    +-----+
      #  K |A B C| T
      #  L |D E F| S
      #  M |G H I| R
      #    +-----+
      #     N P Q
      
      # choose the squares around the edges (all different)
      for ((K, L, M), (N, P, Q), (R, S, T), (U, V, W)) in subsets(sqvs, size=4, select="P"):
      
        # choose the top faces for the corner dice
        for (A, C, G, I) in subsets(irange(1, 6), size=4, select="M"):
          corners = [(A, W, K), (G, M, N), (I, Q, R), (C, T, U)]
          r = seq_all_same_r(corner(*vs) for vs in corners)
          if not (r.same and r.value != 0): continue
      
          # choose the remaining top faces
          for (B, D, E, F, H) in subsets(irange(1, 6), size=5, select="M"):
            edges = [(D, L), (H, P), (F, S), (B, V)]
            if not all(edge(*vs) for vs in edges): continue
      
            # construct the 6 top numbers
            numbers = [(A, B, C), (D, E, F), (G, H, I), (A, D, G), (B, E, H), (C, F, I)]
            ns = list(nconcat(*vs) for vs in numbers)
            # the sum is less than 2000
            t = sum(ns)
            if not (t < 2000): continue
            # three of them are squares
            if sum(n in sqs for n in ns) != 3: continue
      
            # output solution
            printf("{t} <- {hs} {vs}; [{K}{L}{M}, {N}{P}{Q}, {R}{S}{T}, {U}{V}{W}]", hs=ns[:3], vs=ns[3:])
      

      (or a faster variation on [@replit]).

      Solution: The total is 1804.

      The dice are laid out as follows:

      So the total is: (115 + 441 + 445) + (144 + 144 + 515) = 1804.

      Of the six numbers read off from the top of the arrangement the square numbers are: 441 (= 21²) and 144 (twice; = 12²).

      Note that each of the corner dice is left-handed (i.e. a mirror image of a “standard” die), and so, as the dice are all identical, they must all be left-handed.

      If we are allowed to mix left- and right-handed dice, then there are many possible layouts (and many possible answers to the puzzle).

      Like

      • Frits 9:50 pm on 16 September 2022 Permalink | Reply

        Thanks to Jim, hopefully with the correct solution.

           
        from itertools import permutations, product
        from functools import reduce
        
        # convert digits to number
        d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)
        
        # 3-digit squares using digits 1-6
        sqs = [s for x in range(10, 27) 
               if not any(y in (s := str(x * x)) for y in "7890")]
        
        # 3-digit squares with different digits       
        side_sqs = [int(s) for s in sqs if len(set(s)) == 3]
        sqs = set(int(s) for s in sqs)
        
        #    +-------+   so bottom = 4, left = 5, back = 6
        #   /   3   /.    
        #  /       /2
        # +-------+ .
        # |   1   | 
        # |       |.
        # +-------+ 
        
        # we have nine identical dice 
        # so with two clockwise adjacent faces, say (2, 3),
        # the upper face is fixed (I have set it to 6)
        d = dict()
        # set the number facing up for clockwise pair (a, b)
        d[(1, 2)] = 4
        d[(1, 3)] = 2
        d[(2, 3)] = 6
        d[(2, 6)] = 4
        d[(3, 5)] = 6
        d[(3, 6)] = 2
        d[(4, 5)] = 1
        d[(4, 6)] = 5
        d[(5, 6)] = 3
        
        # add decreasing pairs
        for k, v in d.copy().items():
          d[k[::-1]] = 7 - v
          
        for p in permutations(side_sqs, 4):
         
          edges = []
          corners = []
          # calculate candidate numbers facing up for each corner and each edge
          for x, y in zip(p, p[1:] + (p[0], )):
            # connect squares x and y
            corner_sides = (x % 10, y // 100)
            
            if corner_sides not in d: break
            corners.append([d[corner_sides]])
            edges.append([i for i in range(1, 7) 
                          if i not in {(x % 100) // 10, 7 - ((x % 100) // 10)}])
          
          # each corner should have only one candidate
          if len(corners) != 4: continue
          
          edges = edges[1:] + [edges[0]]
          
          # 3x3 block of dice
          block = [corners[2], edges[1], corners[1],
                   edges[2], range(1, 7), edges[0],  
                   corners[3], edges[3], corners[0]]
         
          for p2 in product(*block):
           # six three-digit numbers on top face
           F = [d2n([p2[3 * i + j] for j in range(3)]) for i in range(3)] + \
               [d2n([p2[3 * j + i] for j in range(3)]) for i in range(3)]
           # the total of the six numbers is less than 2000 ...
           if sum(F) >= 2000: continue
           # ... three of which are squares .
           if sum([f in sqs for f in F]) != 3: continue
             
           print("    ", str(p[2])[::-1])
           print(str(p[3])[0], p2[:3], str(p[1])[2])
           print(str(p[3])[1], p2[3:6], str(p[1])[1])
           print(str(p[3])[2], p2[6:], str(p[1])[0])
           print("    ", p[0])
           print()
           print("total:", sum(F))
        

        Like

        • Frits 10:03 pm on 16 September 2022 Permalink | Reply

          The side squares should be seen when walking anti-clockwise around the table (so the top and right squares are printed reversed).

          Like

    • Hugh Casement 7:17 am on 17 September 2022 Permalink | Reply

      Are they left-handed dice? I can’t find any solution with standard dice (such as Frits shows).
      Or perhaps you have to walk round the table with your head upside down.

      Like

      • Jim Randell 7:25 am on 17 September 2022 Permalink | Reply

        @Hugh: Yes. There is only a solution if left-handed dice are used (at least in the corners of the layout – and as the dice are identical then the rest must be left-handed too).

        Like

      • Frits 9:40 am on 17 September 2022 Permalink | Reply

        I set up my dice right-handed (I didn’t even know the term right-handed) based on numbers facing up when going clock wise. However, the corner arrangements in the block have to be read anti-clockwise so I should have used the 7-complement of my hardcoded values.

        My solution is the same as Jim’s and is left-handed. I will post a new version checking both left-handed and right-handed dice (using Brian Gladman’s function for determining the hardcoded values).

        Like

    • Frits 1:52 pm on 17 September 2022 Permalink | Reply

      Supporting right-hand and left-hand dice and with a recursive version of Brian Gladman’s function for third face values.

         
      from itertools import permutations, product
      from functools import reduce
       
      # find the third face anti-clockwise around a dice vertex
      # given two faces in anti-clockwise order
      def f3(fi, se, rh=True):
        # invalid first/second combination
        if fi == se or fi + se == 7: return 0
         
        # only calculate for 3 low increasing pairs 
        if (fi, se) in {(1, 2), (1, 3), (2, 3)}:
          c = 0 if rh else 7  # complement related
          return abs(c - (fi * (2 * se - 1)) % 9)            # artificial formula
         
        # as of now work towards low increasing pairs
        if se < fi: return 7 - f3(se, fi, rh)
        elif fi > 3 and se > 3: return f3(7 - fi, 7 - se, rh) # double complement
        elif fi > 3: return 7 - f3(7 - fi, se, rh)
        elif se > 3: return 7 - f3(fi, 7 - se, rh)
          
      # convert digits to number
      d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)
       
      # 3-digit squares using digits 1-6
      sqs = [s for x in range(10, 27) 
             if not any(y in (s := str(x * x)) for y in "7890")]
       
      # 3-digit squares with different digits       
      side_sqs = [int(s) for s in sqs if len(set(s)) == 3]
      sqs = set(int(s) for s in sqs)
         
      for p in permutations(side_sqs, 4):
        
        # check both right-handed and left-handed dice
        for rh in [1, 0]:
          edges = []
          corners = []
          # calculate candidate numbers facing up for each corner and each edge
          for x, y in zip(p, p[1:] + (p[0], )):
            # connect squares x and y and calculate top face
            top = f3(x % 10, y // 100, rh)
            if not top: break
            corners.append([top])
            edges.append([i for i in range(1, 7) 
                          if i not in {(x % 100) // 10, 7 - ((x % 100) // 10)}])
          else:    
            edges = edges[1:] + [edges[0]]    # rearrange 
       
            # 3x3 block of dice
            block = [corners[2], edges[1], corners[1],
                     edges[2], range(1, 7), edges[0],  
                     corners[3], edges[3], corners[0]]
       
            for p2 in product(*block):
             # six three-digit numbers on top face
             F = [d2n([p2[3 * i + j] for j in range(3)]) for i in range(3)] + \
                 [d2n([p2[3 * j + i] for j in range(3)]) for i in range(3)]
             # the total of the six numbers is less than 2000 ...
             if sum(F) >= 2000: continue
             # ... three of which are squares 
             if sum([f in sqs for f in F]) != 3: continue
       
             print("    ", str(p[2])[::-1])
             print(str(p[3])[0], p2[:3], str(p[1])[2])
             print(str(p[3])[1], p2[3:6], str(p[1])[1])
             print(str(p[3])[2], p2[6:], str(p[1])[0])
             print("    ", p[0], "\n")
             print("total:", sum(F), 
                   "(right-handed" if rh else "(left-handed", "dice)")
      

      Like

    • Frits 11:39 pm on 17 September 2022 Permalink | Reply

      Based on Jim’s first posted program. This program runs in 90ms.

         
      from enigma import SubstitutedExpression
       
      # consider the layout:
      #
      #     W V U
      #    +-----+
      #  K |A B C| T
      #  L |D E F| S
      #  M |G H I| R
      #    +-----+
      #     N P Q
      
      # corners for a right-handed die
      die = {(1, 2, 3), (1, 3, 5), (1, 5, 4), (1, 4, 2), 
             (6, 4, 5), (6, 5, 3), (6, 3, 2), (6, 2, 4)}
       
      # check faces anti-clockwise around a corner (= x, y, z)
      # 1 = right-handed, -1 = left-handed
      def corner(x, y, z):
        ss = {x, y, z}
        return (1 if die.intersection({(x, y, z), (y, z, x), (z, x, y)}) else -1)
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
         "W != 7 - K",
         "is_square(KLM)",
         "U != 7 - T",
         "is_square(UVW)",
         "R != 7 - Q",
         "is_square(RST)",
         "N != 7 - M",
         "is_square(NPQ)",
         
         "seq_all_different([KLM, NPQ, RST, UVW])",
         # corner checks
         "A not in {7 - W, K, 7 - K}",
         "C not in {7 - U, T, 7 - T}",
         "I not in {7 - R, Q, 7 - Q}",
         "G not in {7 - M, N, 7 - N}",
         # edge checks
         "D != 7 - L", 
         "B != 7 - V", 
         "F != 7 - S", 
         "H != 7 - P", 
         
         "seq_all_same(corner(*vs) for vs in [(A, W, K), (G, M, N), \
                                              (I, Q, R), (C, T, U)])",
         
         "sum([ABC, DEF, GHI, ADG, BEH, CFI]) < 2000",
                                           
         "sum([1 for x in [ABC, DEF, GHI, ADG, BEH, CFI] if is_square(x)]) == 3",
        ],
        answer="(ABC, DEF, GHI), (KLM, NPQ, RST, UVW), \
                sum([ABC, DEF, GHI, ADG, BEH, CFI])",
        
        distinct=("KLM","NPQ","RST","WVU","AWK","UCT","IRQ","MGN", \
                  "DL","BV","FL","HP"),
        env=dict(corner=corner),
        digits=range(1, 7),
        reorder=0,
        denest=32,    # [CPython] work around statically nested block limit
        verbose=0,    # use 256 to see the generated code
      )
      
      # print answers
      for (_, ans) in p.solve():
        print(" ", str(ans[1][3])[::-1])
        print(f"{str(ans[1][0])[0]} {ans[0][0]} {str(ans[1][2])[2]}")
        print(f"{str(ans[1][0])[1]} {ans[0][1]} {str(ans[1][2])[1]}")
        print(f"{str(ans[1][0])[2]} {ans[0][2]} {str(ans[1][2])[0]}")
        print(" ", ans[1][1], "  sum", ans[2], "\n")
      

      Like

    • Frits 11:02 pm on 22 September 2022 Permalink | Reply

      More efficient version.

         
      from itertools import permutations, product
      from functools import reduce
      from collections import defaultdict
      
      # find the third face anti-clockwise around a dice vertex
      # given two faces in anti-clockwise order
      def f3(fi, se, rh=True):
        # invalid first/second combination
        if fi == se or fi + se == 7: return 0
        
        # only hardcode for 3 low increasing pairs 
        match (fi, se):
          case (1, 2): return 3 if rh else 4
          case (1, 3): return 5 if rh else 2
          case (2, 3): return 1 if rh else 6
          case _:
            # work towards low increasing pairs
            if se < fi: return 7 - f3(se, fi, rh)
            elif fi > 3 and se > 3: return f3(7 - fi, 7 - se, rh)
            elif fi > 3: return 7 - f3(7 - fi, se, rh)
            elif se > 3: return 7 - f3(fi, 7 - se, rh)
      
      # convert digits to number
      d2n = lambda s: reduce(lambda x,  y: 10 * x + y, s)
      
      # 3-digit squares using digits 1-6
      sqs = [s for x in range(10, 27) 
             if not any(y in (s := str(x * x)) for y in "7890")]
       
      # map hundreds and units digits to tens digits in squares
      hu2ts = defaultdict(set)
      for s in sqs:
        h, t, u = (int(d) for d in s)
        hu2ts[h, u].add(t)
       
      # 3-digit squares with different digits       
      side_sqs = [int(s) for s in sqs if len(set(s)) == 3]
      sqs = set(int(s) for s in sqs)
        
      for p in permutations(side_sqs, 4):
        # check both right-handed and left-handed dice
        for rh in [1, 0]:
          edges = []
          corners = []
          # calculate candidate numbers facing up for each corner and each edge
          for x, y in zip(p, p[1:] + (p[0], )):
            # connect squares x and y and calculate top face
            top = f3(x % 10, y // 100, rh)
            if not top: break
            corners.append(top)
            edges.append([i for i in range(1, 7) 
                          if i not in {(x % 100) // 10, 7 - ((x % 100) // 10)}])
          else:    
            edges = edges[1:] + [edges[0]]    # rearrange 
            
            # c[2] e[1] c[1]   
            # e[2]  .   e[0]
            # c[3] e[3] c[0]
            
            # skip if sum of the four top numbers that don't use the center
            # is already too high
            if 100 * (2 * corners[2] + corners[1] + corners[3]) + 4 * 10 + \
               corners[3] + 2 + corners[0] + corners[1] + 222 > 1999:
              continue
            
            # which of these four top numbers can make a square number
            ts = []
            for i, (a, b) in enumerate([(1, 0), (2, 1), (2, 3), (3, 0)]):
              # can we form a square with 2 corners?
              if len(hu2ts[corners[a], corners[b]]):
                # which edge candidates result in a square
                cands = hu2ts[corners[a], corners[b]] & set(edges[i])
                if cands:
                  ts.append((i, cands))
            
            if not ts: continue    # we can't make a square
            elif len(ts) == 1:
              # only one top number can make a square, reduce the edge candidates
              edges[ts[0][0]] = list(ts[0][1])
           
            for e4 in product(*edges):
              # four three-digit numbers on top face (without the center)
              T4 = [d2n([corners[1], e4[0], corners[0]]),
                    d2n([corners[2], e4[1], corners[1]]),
                    d2n([corners[2], e4[2], corners[3]]),
                    d2n([corners[3], e4[3], corners[0]])]
              
              if sum(T4) + 222 > 1999: continue
              
              # center die
              for c in range(1, 7):
                # add two missing top numbers
                T6 = T4 + [d2n([e4[1], c, e4[3]]), d2n([e4[2], c, e4[0]])]
                
                # the total of the six numbers is less than 2000 ...
                if sum(T6) >= 2000: continue
                # ... three of which are squares 
                if sum([t in sqs for t in T6]) != 3: continue
               
                print(" ", str(p[2])[::-1])
                print(str(p[3])[0], T6[1], str(p[1])[2])
                print(str(p[3])[1], T6[3], str(p[1])[1])
                print(str(p[3])[2], T6[5], str(p[1])[0])
                print(" ", p[0], end="      ")
                print("total:", sum(T6), 
                      "(right-handed" if rh else "(left-handed", "dice)")
      

      Like

  • Jim Randell 10:16 am on 19 May 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2854: Power surge 

    From The Sunday Times, 4th June 2017 [link]

    I recently checked my energy bills. I noticed that the account numbers for my electricity and gas are two different six-figure numbers, and that one is a multiple of the other. The electricity account number is a perfect cube and the sum of its digits is a perfect square. The gas account number is a perfect square (and, as it happens, the sum of its digits is a perfect cube!).

    What is the gas account number?

    [teaser2854]

     
    • Jim Randell 10:17 am on 19 May 2022 Permalink | Reply

      I am assuming that leading zeros are not allowed in the 6-figure account numbers.

      The following Python program runs in 58ms. (Internal run time is 442µs).

      Run: [ @replit ]

      from enigma import (irange, dsum, is_cube, is_square, chain, div, printf)
      
      # generate possible other values for G
      def generate(E, fn):
        for d in irange(2, 9):
          G = fn(E, d)
          if G is None: continue
          # G has 6 digits
          if G < 100000: break
          if G > 999999: break
          # G is a perfect square
          if not is_square(G): continue
          # the sum of G's digits is a perfect cube
          if not is_cube(dsum(G)): continue
          # viable value
          yield (G, d)
      
      # E is a 6 digit cube
      for i in irange(47, 99):
        E = pow(i, 3)
        # and the sum of its digits is a perfect square
        if not is_square(dsum(E)): continue
      
        # look for another 6-digit multiple that is a multiple or divisor of E
        mul = lambda E, d: E * d
        for (G, d) in chain(generate(E, mul), generate(E, div)):
          # output solution
          printf("E={E} G={G} [d={d}]")
      

      Solution: The gas account number is 147456.

      And the electricity account number is 884736 (= 6 × 147456).

      Like

    • Frits 7:39 pm on 19 May 2022 Permalink | Reply

         
      from enigma import SubstitutedExpression, dsum
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
          # The electricity account number is a perfect cube and 
          # the sum of its digits is a perfect square
          "is_square(dsum(EL ** 3))",
          # six-figure number
          "99999 < EL ** 3 < 1000000",
          
          # one is a multiple of the other
          "(GAS ** 2) % (EL ** 3) == 0 or (EL ** 3) % (GAS ** 2) == 0",
          
          # two different six-figure numbers
          "EL ** 3 != GAS ** 2",
          
          # The gas account number is a perfect square and
          # the sum of its digits is a perfect cube
          "is_cube(dsum(GAS ** 2))",
          # six-figure number
          "99999 < GAS ** 2 < 1000000",
        ],
        answer="GAS ** 2",
        d2i=dict([(k, "EG") for k in range(0, 3)] + [(3, "E")]),
        distinct="",
        verbose=0,
      )
      
      # print answers
      for (_, ans) in p.solve():
        print(f"{ans}")
      

      Like

    • GeoffR 4:31 pm on 20 May 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Elec Account - six digits
      var 1..9:E; var 0..9:F; var 0..9:G; var 0..9:H;
      var 0..9:I; var 0..9:J; 
      
      % Gas Account - six digits
      var 1..9:g; var 0..9:h; var 0..9:i; var 0..9:j;
      var 0..9:k; var 0..9:l;
      
      var 100000..999999:Elec == 100000*E + 10000*F + 1000*G + 100*H + 10*I + J;
       
      var 100000..999999:Gas == 100000*g + 10000*h + 1000*i + 100*j + 10*k + l;
      
      % Two different six-figure account numbers
      constraint Elec != Gas;
      
      % One account number is a multiple of the other
      constraint Elec mod Gas == 0 \/ Gas mod Elec == 0;
      
      % 6-digit squares and cubes
      set of int: sq6 = {n * n | n in 317..999};
      set of int: cb6 = {n * n * n | n in 47..99};
      
      % 2-digit squares and cubes < 54 (i.e. < 6 * 9)
      set of int: cb2 = {n * n * n | n in 2..3};
      set of int: sq2 = {n * n | n in 2..7};
      
      % Square/Cube constraints for both accounts
      constraint Elec in cb6 /\ (E + F + G + H + I + J) in sq2;
      constraint Gas in sq6 /\ (g + h + i + j + k + l) in cb2;
      
      solve satisfy;
      
      output[ "Gas Acc No. = " ++ show(Gas) 
      ++ "\n" ++ "Elec Acc No. = " ++ show(Elec)];
      
      % Gas Acc No. = 147456
      % Elec Acc No. = 884736
      % ----------
      % ==========
      
      
      

      Like

  • Jim Randell 4:36 pm on 13 May 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3112: PIN 

    From The Sunday Times, 15th May 2022 [link] [link]

    Callum has opened a new current account and has been given a telephone PIN that is composed of non-zero digits (fewer than six). He has written down the five possible rearrangements of his PIN. None of these five numbers are prime; they can all be expressed as the product of a certain number of different primes.

    The PIN itself is not prime; it can also be expressed as the product of different primes but the number of primes is different in this case. The sum of the digits of his PIN is a square.

    What is the PIN?

    [teaser3112]

     
    • Jim Randell 5:19 pm on 13 May 2022 Permalink | Reply

      We need to find a collection of digits from which the PIN and exactly 5 other rearrangements can be made. So we need there to be 6 different arrangements in total.

      Selections of digits with the same pattern (e.g. “three different digits”, “two pairs of digits”, which we might write as (1, 1, 1) and (2, 2)) will have the same number of arrangements of the digits. So in the following program, if a pattern produces a number of arrangements that is not 6, we abandon testing that pattern. (Another way to check a pattern would be to check that its multinomial coefficient is 6, see [@replit]).

      This Python program runs in 58ms. (Internal run time is 4.18ms).

      Run: [ @replit ]

      from enigma import (
        defaultdict, irange, nconcat, subsets, decompose, multiset, factor,
        seq_all_different as all_different, is_square_p, singleton, map2str, printf
      )
      
      # group numbers by the number of prime factors, subject to:
      # - a number cannot be prime
      # - a number cannot have a repeated prime factor
      def group(ns):
        d = defaultdict(list)
        for n in ns:
          fs = factor(n)
          # none of the numbers are prime
          if len(fs) == 1: return
          # none of the numbers has a repeated prime factor
          if not all_different(fs): return
          # record this number
          d[len(fs)].append(n)
        return d
      
      # n = number of digits in the PIN
      # k = number of different digits in the PIN
      for (k, n) in subsets(irange(1, 5), size=2, select="R"):
        # calculate repetitions of digits
        for rs in decompose(n, k, increasing=0, sep=0, min_v=1):
          # choose digits
          for ds in subsets(irange(1, 9), size=k):
            # allocate the digits
            m = multiset.from_pairs(zip(ds, rs))
            # the sum of the digits is a square number
            if not is_square_p(m.sum()): continue
            # calculate the number of arrangements
            ns = list(nconcat(*x) for x in subsets(m, size=n, select="mP"))
            # we need 6 arrangements
            if len(ns) != 6: break
            # group the numbers by the number of prime factors
            d = group(ns)
            if d is None: continue
            # check there are only two different numbers of factors
            if len(d.keys()) != 2: continue
            # and one of these corresponds to only one number
            pk = singleton(k for (k, vs) in d.items() if len(vs) == 1)
            if pk is None: continue
            # output solution
            PIN = singleton(d[pk])
            printf("PIN={PIN} {d}", d=map2str(d, arr="->", enc="[]"))
      

      Solution: The PIN is 1771.


      The PIN has a factorisation into 3 different primes: 1771 = 7 × 11 × 13.

      And the other 5 rearrangements of the digits all have factorisations into 2 different primes:

      1177 = 11 × 107
      1717 = 17 × 101
      7117 = 11 × 647
      7171 = 71 × 101
      7711 = 11 × 701

      Like

    • GeoffR 3:09 pm on 15 May 2022 Permalink | Reply

      It looks as though the PIN number has to be three, four or five digits long.

      I thought a 3-digit pin would not give enough rearrangements and a 5-digit pin would give more than five rearrangements.

      I assumed only a four digit number, compose of two different digits, would give the requisite five rearrangements, as shown at the start of the code.

      # Assume only  a four-digit number made of two different
      # digits (A,B) can give five possible total rearrangements
      # of the PIN number
      # e.g. AABB, ABAB, ABBA, BAAB, BABA, BBAA
      
      from itertools import permutations
      from enigma import factor, is_square, is_prime
      
      # choose two non-zero digits for the four digit PIN
      for p1 in permutations('123456789', 2):
        a, b = p1
        # check sum of digits is a square
        if not is_square(2 * int(a) + 2 * int(b)):
           continue
        # form six numbers from two different digits
        n1 = int(a + a + b + b)
        n2 = int(a + b + a + b)
        n3 = int(a + b + b + a)
        n4 = int(b + a + a + b)
        n5 = int(b + a + b + a)
        n6 = int(b + b + a + a)
        # check all six numbers are not prime
        if all(not is_prime(x) for x in (n1, n2, n3, n4, n5, n6)):
          # find number of prime factors of the six numbers
          f1 = len(factor(n1))
          f2 = len(factor(n2))
          f3 = len(factor(n3))
          f4 = len(factor(n4))
          f5 = len(factor(n5))
          f6 = len(factor(n6))
          # check there are only two different numbers
          # of factors for the six numbers
          if len(set((f1, f2, f3, f4, f5, f5, f6))) == 2:
            # find the unique number of factors
            # to give the PIN number
            if f1 not in (f2, f3, f4, f5, f6):
              print(f"PIN = {n1}")
            elif f2 not in (f1, f3, f4, f5, f6):
              print(f"PIN = {n2}")
            elif f3 not in (f1, f2, f4, f5, f6):
              print(f"PIN = {n3}")
            elif f4 not in (f1, f2, f3, f5, f6):
              print(f"PIN = {n4}")
            elif f5 not in (f1, f2, f3, f4, f6):
              print(f"PIN = {n5}")
            elif f6 not in (f1, f2, f3, f4, f5):
              print(f"PIN = {n6}")
      
      
      
      

      Like

      • Jim Randell 3:32 pm on 15 May 2022 Permalink | Reply

        @GeoffR: Actually a 3-digit PIN consisting of 3 different digits will have the required 6 arrangements.

        Like

    • GeoffR 3:34 pm on 15 May 2022 Permalink | Reply

      @Jim: Yes, I overlooked that when thinking of repeated digits

      Like

    • Frits 1:12 pm on 17 May 2022 Permalink | Reply

      Based on GeoffR’s method.

        
      # assume only a four-digit number made of two different
      # digits (A,B) can give five other rearrangements of the PIN number
      # e.g. AABB, ABAB, ABBA, BAAB, BABA, BBAA
      #
      # or 
      #
      # the PIN number has 3 digits which are all different
      # resulting in 6 arrangements
      # e.g. ABC, ACB, BAC, BCA, CAB, CBA
       
      from itertools import permutations, combinations
      from enigma import factor, is_square
      
      # loop over three-digit and four-digit numbers
      for nd in [3, 4]:
        # choose non-zero digits for the nd-digit PIN
        for comb in combinations('123456789', 6 - nd):
          dgts = list(comb) if nd == 3 else list(comb * 2)
           
          # check sum of digits is a square
          if not is_square(sum(int(x) for x in dgts)):
            continue
            
          nums = [int(''.join(x)) for x in set(permutations(dgts))]  
          fs   = [factor(x) for x in nums]
       
          # none are prime and none have repeated prime factors
          if any(len(x) == 1 or len(x) != len(set(x)) for x in fs): continue
          
          n_fs  = [len(x) for x in fs]
          
          # check for exactly two different numbers of factors
          if len(set(n_fs)) == 2:
            # find the unique number of factors
            uniq = [i for i, x in enumerate(n_fs) if n_fs.count(x) == 1]
      
            if uniq:
              print(f"PIN = {nums[uniq[0]]}")
      

      Like

  • Jim Randell 9:19 am on 14 April 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2847: Easter parade 

    From The Sunday Times, 16th April 2017 [link]

    Following the success of last year’s Easter parade our village is going to make it an annual event. To celebrate today’s parade I have taken three numbers and I have consistently replaced digits by letters to give:

    ANNUAL
    EASTER
    PARADE

    In fact the third number is the sum of the other two.

    What is the number PARADE?

    [teaser2847]

     
    • Jim Randell 9:20 am on 14 April 2022 Permalink | Reply

      This puzzle can be solved using the [[ SubstitutedSum ]] solver from the enigma.py library.

      The following command executes in 85ms.

      Run: [ @replit ]

      % python3 -m enigma SubstitutedSum "ANNUAL + EASTER = PARADE"
      (ANNUAL + EASTER = PARADE)
      (300632 + 138719 = 439351) / A=3 D=5 E=1 L=2 N=0 P=4 R=9 S=8 T=7 U=6
      (300732 + 138619 = 439351) / A=3 D=5 E=1 L=2 N=0 P=4 R=9 S=8 T=6 U=7
      

      Solution: PARADE = 439351.

      T and U are interchangeable, taking on the values 6 and 7.

      Like

    • GeoffR 11:24 am on 14 April 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:A;  var 0..9:D;  var 1..9:E;  var 0..9:L; var 0..9:N;  
      var 1..9:P;  var 0..9:R;  var 0..9:S;  var 0..9:T; var 0..9:U;
      
      constraint all_different([A, D, E, L, N, P, R, S, T, U]);
      
      function var int: num6 (var int: u, var int: v, var int: w, var int: x, 
      var int: y, var int: z) = 100000*u + 10000*v + 1000*w + 100*x + 10*y + z;
      
      var 100000..999999: ANNUAL = num6(A,N,N,U,A,L);
      var 100000..999999: EASTER = num6(E,A,S,T,E,R);
      var 100000..999999: PARADE = num6(P,A,R,A,D,E);
      
      constraint ANNUAL + EASTER == PARADE;
      
      solve satisfy;
      output ["PARADE" ++ " = " ++ show(PARADE) ];
      
      % PARADE = 439351
      % ----------
      % ==========
      
      
      

      Like

  • Jim Randell 11:44 am on 22 March 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2734: Interlocking squares 

    From The Sunday Times, 15th February 2015 [link] [link]

    Place all of the digits 0 to 9 in the grid so that, reading across or down in crossword fashion, one can see a two-figure square, a three-figure square, and two four-figure squares.

    What (in increasing order) are the four squares?

    [teaser2734]

     
    • Jim Randell 11:45 am on 22 March 2022 Permalink | Reply

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 114ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      #  # A # #
      #  B C D E
      #  # F # G
      #  H J # K
      
      SubstitutedExpression
      
      # across
      "is_square(BCDE)"
      "is_square(HJ)"
      
      # down
      "is_square(ACFJ)"
      "is_square(EGK)"
      
      # answer
      --answer="ordered(BCDE, HJ, ACFJ, EGK)"
      

      Solution: The squares are: 49, 576, 1089, 3025.

      (49, 576, 1089, 3025) = (7², 24², 33², 55²).

      Like

    • GeoffR 2:33 pm on 22 March 2022 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      %    # A # #
      %    B C D E
      %    # F # G
      %    H J # K
      
      var 1..9:A; var 1..9:B; var 0..9:C; var 0..9:D;
      var 1..9:E; var 0..9:F; var 0..9:G; var 1..9:H;
      var 0..9:J; var 0..9:K;
      
      constraint all_different([A,B,C,D,E,F,G,H,J,K]);
      
      % sets of 2,3 and 4-digit squares
      set of int: sq2 = {n*n | n in 4..9};
      set of int: sq3 = {n*n | n in 10..31};  
      set of int: sq4 = {n*n | n in 32..99};  
      
      constraint (10*H + J) in sq2;
      constraint (100*E +10*G + K) in sq3;
      constraint (1000*A + 100*C + 10*F + J) in sq4 
      /\ (1000*B + 100*C + 10*D + E) in sq4;
      
      solve satisfy;
      
      output [ "[A,B,C,D,E,F,G,H,J,K] = " ++ show([A,B,C,D,E,F,G,H,J,K])];
      % [1, 3, 0, 2, 5, 8, 7, 4, 9, 6]
      % [A, B, C, D, E, F, G, H, J, K]
      % ----------
      % ==========
      % Squares : HJ = 49, EGK = 576, ACFJ = 1089, BCDE = 3025
      
      
      

      Like

    • GeoffR 8:10 am on 23 March 2022 Permalink | Reply

      A three stage permutation solution.

      from itertools import permutations
      from enigma import is_square
      
      digits = set('1234567890')
      
      # two digit square HJ
      for p1 in permutations(digits, 2):
        h, j = p1
        if h == '0':continue
        hj = int(h + j)   
        if not is_square(hj):continue
        q1 = digits.difference({h, j})
          
        # three digit square EGK
        for p2 in permutations(q1, 3):
          e, g, k = p2
          if e == '0':continue
          egk = int(e + g + k)
          if not is_square(egk):continue
              
          # two four digit squares BCDE and ACFJ
          q2 = q1.difference({e, g, k})
          for p3 in permutations(q2):
            a, b, c, d, f = p3
            if '0' in (a, b): continue
            bcde = int(b + c + d + e)
            if is_square(bcde):
              acfj = int(a + c + f + j)
              if is_square(acfj):
                print(f"HJ={hj}, EGK={egk}, ACFJ={acfj}, BCDE={bcde}")
                        
      # HJ=49, EGK=576, ACFJ=1089, BCDE=3025
      
      
      

      Like

  • Jim Randell 3:07 pm on 11 February 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3099: Recurring theme 

    From The Sunday Times, 13th February 2022 [link] [link]

    Liam is learning about fractions and decimals. He has been shown that some fractions give rise to decimals with a recurring pattern eg 4/11 = 0.3636… . Each pupil in his class has been given four numbers. The largest (two-figure) number is to be used as the denominator and the others as numerators, to create three fractions that are to be expressed as decimals. Liam found that each decimal was of the form 0.abcabc…, with the same digits but in different orders.

    Liam’s largest number contained the digit 7 and if I told you how many of his four numbers were divisible by ten you should be able to work out the numbers.

    What, in increasing order, are the four numbers?

    [teaser3099]

     
    • Jim Randell 3:42 pm on 11 February 2022 Permalink | Reply

      We can use some handy routines from the enigma.py library to help in solving this puzzle. [[ recurring() ]] finds the recurring part of the decimal representation of a fraction, and [[ filter_unique() ]] can be used to find sets that are unique by the count of multiples of 10 involved.

      The following Python program runs in 91ms.

      Run: [ @replit ]

      from collections import defaultdict
      from enigma import irange, union, recurring, join, subsets, filter_unique, printf
      
      # generate sets of possible numbers
      def generate():
        # choose the denominator (2-digits, one of them a 7)
        for d in union([irange(17, 97, step=10), irange(70, 79)]):
      
          # consider the smaller numbers, n/d = 0.(xyz)...
          # and record them by the digits that make up the repetend
          r = defaultdict(list)
          for n in irange(1, d - 1):
            (_, nr, rr) = recurring(n, d)
            if not(nr) and len(rr) == 3:
              r[join(sorted(rr))].append(n)
      
          # find sets of 3 numerators
          for ns in r.values():
            for ss in subsets(ns, size=3, fn=list):
              yield tuple(ss + [d])
      
      # find sets unique by the count of multiples of 10 involved
      fn = lambda ns: sum(n % 10 == 0 for n in ns)
      for ns in filter_unique(generate(), fn).unique:
        printf("{ns}")
      

      Solution: Liam’s numbers are: 4, 30, 40, 74.

      So we have:

      4/74 = 0.(054)…
      30/74 = 0.(405)…
      40/74 = 0.(540)…

      And this the only set of 4 numbers where 2 of them are divisible by 10.

      In all there are 30 possible sets of 4 numbers. 12 sets use a denominator of 37, and the numbers in these sets can be multiplied by 2 to give 12 further sets (that give the same fractions) using a denominator of 74. The remaining 6 sets have a denominator of 27.

      Of these there are 19 sets with none of the 4 numbers divisible by 10, and 10 sets with one of the 4 numbers divisible by 10. The remaining set has two of the numbers divisible by 10, and so gives the answer.

      Like

    • GeoffR 3:09 pm on 15 February 2022 Permalink | Reply

      Not very elegant code, but it finds the answer, and runs in less than 100ms.
      I used two Python dictionaries in this solution.

      from enigma import recurring, join
      from collections import defaultdict
      
      # for potential number lists
      Nums = defaultdict(list)
      
      # for counting values in Nums divisible by 10
      D10 = defaultdict(list) 
      
      # using list of possible denominators including digit 7
      # .. to search for repeating decimal patterns
      for n in (17,27,37,47,57,67,70,71,72,73,74,75,76,77,78,79,87,97):
        (_, nr, rr) = recurring(1, n)
        if not(nr) and len(rr) == 3:
          print(f"Number = {n}, reciprocal = {1/n}")
      
      # only 27 and 37 were found as denominators with repeating patterns
      # ... add multiples 54 and 74 as extra 2-digit numbers
      # ...in search for all 3-digit repeating patterns
      for n in range(1, 80):
        for d in (27, 37, 54, 74):
          if n < d:
            (_, nr, rr) = recurring(n, d)
            if not(nr) and len(rr) == 3:
              Nums[join(sorted(rr)) + " " + str(d)].append(n)
      
      # add denominator (from the key) to values            
      for k, v in Nums.items():  
        v = v + [int(k[4:6])]
      
      # form a new dictionary D10, based on the Nums dict values
      # ... which are divisible by 10
      for k, v in Nums.items():
        tot10 = 0
        # count numbers divisible by 10
        for x in v:
          q, r = divmod(int(x), 10)
          if q and r == 0:
            tot10 += 1
          # add denominator to D10 values
          D10[tot10].append(v + [int(k[4:6])] )
      
      # look for a unique set of four numbers
      # ... based on the number of values divisible by 10
      for k, v in D10.items():
        if len(v) == 1:
          print(f"Four numbers are {v}")
      
      
      

      Like

    • A.T.Surherland 9:40 am on 16 February 2022 Permalink | Reply

      I have obtained an interesting answer :-
      The sum of the 3 lowest numbers = the greatest number.
      ie the sum of the fractions = 1.
      Is there a reason for this condition?.

      Like

      • Jim Randell 12:01 pm on 16 February 2022 Permalink | Reply

        There are 12 sets of numbers that work with a denominator of 37. Of these 6 have the fractions sum to 1, and 6 have the fractions sum to 2. And we can obviously multiply all the numbers up by a factor of 2 to get another 12 sets that behave the same.

        The remaining 6 sets of numbers (with denominator 27) give fractions that don’t sum to a whole number (but are all multiples of 1/9).

        This is presumably due to the 3 different digits in the repetends lining up, so that the repetend of the sum is a single digit, and in the case of .(9)… this gives a whole number.

        Like

      • Brian Gladman 12:29 pm on 16 February 2022 Permalink | Reply

        If we add 0.abc… + 0.bca… + 0.cab… we will get 0.111… x (a + b + c) = (a + b + c) / 9, so sum(numerators) / denominator = (a + b + c) / 9. So this happens when a + b + c == 9, which it does in our case. The sum can be 2 when a + b + c equals 18 but it is not necessarily an integer.

        Like

    • GeoffR 11:07 am on 16 February 2022 Permalink | Reply

      Yes, This is my understanding of the reason.

      A repeating fraction of the format 0.abcabcabc.. can be expressed exactly as a rational fraction abc/999 – see number theory elsewhere.

      Each of the three numerators in the answer divided by the denominator, gives a 3-digit repeating pattern.

      Without displaying the answer publicly, as this is a current Sunday Times Teaser,
      the three repeating fractions for this teaser can be expressed as:

      0.abcabcabc   0.cabcabcab   0.bcabcabca – since the three fractions use the same digits as a stated teaser condition.

      The rational fractions for this teaser are then abc/999, cab/999 and bca/999.

      Also, abc + cab + bca = 999.

      It can be seen that abc/999 + cab/999 + bca/999 = 1.

      Like

  • Jim Randell 10:45 am on 3 February 2022 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2861: Fond memories 

    From The Sunday Times, 23rd July 2017 [link]

    One of my memories of my grandparents’ house is of an ornament consisting of three monkeys with the caption “See no evil, hear no evil, speak no evil”.

    I have written down four odd numbers, one of them being the sum of the other three. Then I have consistently replaced digits with letters, using different letters for different digits. In this way the four numbers have become:

    SPEAK
    HEAR
    SEE
    EVIL

    What number is represented by SPEAK?

    [teaser2861]

     
    • Jim Randell 10:47 am on 3 February 2022 Permalink | Reply

      E, K, L, R must be odd digits, and SPEAK must be the result of the sum.

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve the puzzle.

      The following run file executes in 128ms.

      Run: [ @replit ]

      #!/usr/bin/env python3 -m enigma -r
      
      SubstitutedExpression
      
      # the alphametic sum
      "SEE + HEAR + EVIL = SPEAK"
      
      # the numbers are all odd, so E, K, L, R are odd digits
      "E % 2 = 1"
      "R % 2 = 1"
      "L % 2 = 1"
      "K % 2 = 1"
      
      --answer="SPEAK"
      

      Solution: SPEAK = 12507.

      There are 2 ways to arrive at the solution:

      155 + 6503 + 5849 = 12507
      155 + 6509 + 5843 = 12507

      The values of L and R can be swapped. They are 3 and 9 (in some order).

      Like

    • GeoffR 8:35 pm on 3 February 2022 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..9:S; var 0..9:P; var 1..9:E;  var 0..9:A;  var 0..9:K;
      var 1..9:H; var 0..9:R; var 0..9:V;  var 0..9:I;  var 0..9:L;
      
      constraint all_different ([S,P,E,A,K,H,R,V,I,L]);
      
      var 10000..99999: SPEAK == 10000*S + 1000*P + 100*E + 10*A + K;
      var 1000..9999: HEAR == 1000*H + 100*E + 10*A + R;
      var 1000..9999: EVIL == 1000*E + 100*V + 10*I + L;
      var 100..999: SEE == 100*S + 11*E;
      
      constraint SPEAK == HEAR + SEE + EVIL;
      
      % Confirm four numbers are odd
      constraint SPEAK mod 2 == 1 /\ HEAR mod 2 == 1
      /\ SEE mod 2 == 1 /\ EVIL mod 2 == 1;
      
      solve satisfy;
      
      output ["HEAR = " ++ show(HEAR) ++ ", SEE = " ++ show(SEE) ++ 
      ", EVIL = " ++ show(EVIL) ++ ", SPEAK = " ++ show(SPEAK)];
      
      % HEAR = 6509, SEE = 155, EVIL = 5843, SPEAK = 12507
      % ----------
      % HEAR = 6503, SEE = 155, EVIL = 5849, SPEAK = 12507
      % ----------
      % ==========
      
      

      Like

  • Jim Randell 1:17 pm on 10 December 2021 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3090: Main line 

    From The Sunday Times, 12th December 2021 [link] [link]

    Anton and Boris live next to a railway line. One morning a goods train passed Anton’s house travelling south just as a slower train passed Boris’s house travelling north. The goods train passed Boris’s house at the same time as a passenger train, heading north at a speed that was half as fast again as the goods train. Similarly, as the slower train passed Anton’s house it passed a passenger train; this was heading south at a speed that was three times as great as that of the slower train.

    The passenger trains then passed each other at a point 25 kilometres from Anton’s house before simultaneously passing the two houses.

    All four trains travelled along the same route and kept to their own constant speeds.

    How far apart do Anton and Boris live?

    [teaser3090]

     
    • Jim Randell 1:38 pm on 10 December 2021 Permalink | Reply

      This is an exercise is generating and solving simultaneous equations. No programming necessary.

      If we suppose B lives a distance d from A.

      Initially (at time 0) if the goods train passes A travelling south at speed 2v, then it reaches B at a time of (d / 2v).

      At this time, the passenger train, with a speed of 3v passes B, heading north.

      And the slow train, travelling at speed 2fv (i.e. some fraction of v), reaches A at a time of (d / 2fv).

      And at this time a train travelling at 6fv passes A heading south.

      These trains pass at time t1 at a point 25 km south of A:

      t1 = (d / 2fv) + (25 / 6fv) = (3d + 25) / 6fv
      t1 = (d / 2v) + ((d − 25) / 3v) = (5d − 50) / 6v
      ⇒ f = (3d + 25) / (5d − 50)

      And then at time (t1 + t2) the two trains pass A and B:

      t2 = 25 / 3v
      t2 = (d − 25) / 6fv
      ⇒ f = (d − 25) / 50

      Equating these:

      (3d + 25) / (5d − 50) = (d − 25) / 50
      10(3d + 25) = (d − 25)(d − 10)
      30d + 250 = d² − 35d + 250
      d² − 65d = 0
      ⇒ d = 65

      So A and B are 65 km apart, and f = 4/5.

      We are not given any times, so we cannot determine the actual speeds of the trains.

      Solution: Anton and Boris live 65 km apart.

      Like

  • Jim Randell 11:27 am on 9 December 2021 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2843: Child’s play 

    From The Sunday Times, 19th March 2017 [link]

    Liam has a set of cards numbered from one to twelve. He can lay some or all of these in a row to form various numbers. For example the four cards:

    6, 8, 11, 2

    give the five-figure number 68112. Also, that particular number is exactly divisible by the number on each of the cards used.

    In this way Liam used his set of cards to find another much larger number that was divisible by each of the numbers on the cards used — in fact he found the largest such possible number.

    What was that number?

    [teaser2843]

     
    • Jim Randell 11:29 am on 9 December 2021 Permalink | Reply

      To reduce the search space we can use some shortcuts.

      Considering the cards that are included in the number, if the “10” card is included, then it would have to appear at the end, and would preclude the use of cards “4”, “8”, “12”.

      Similarly if “5” is included, and any even card, then the number must end in “10” and the cards “4”, “8”, “12” are excluded.

      If any of the cards “3”, “6”, “9”, “12” are included then the overall digit sum must be a multiple of 3.

      Similarly if “9” is included, then the overall digit sum must be a multiple of 9.

      If any of the even cards (“2”, “4”, “6”, “8”, “10”) are used, the resulting number must also be even.

      This Python program uses a number of shortcuts. It considers the total number of digits in the number, as once a number is found we don’t need to consider any number with fewer digits. It runs in 263ms.

      Run: [ @replit ]

      from enigma import (enigma, irange, group, subsets, Accumulator, join, printf)
      
      # the cards
      cards = list(irange(1, 12))
      
      # map cards to their digit sum, and number of digits
      dsum = dict((x, enigma.dsum(x)) for x in cards)
      ndigits = dict((x, enigma.ndigits(x)) for x in cards)
      
      # find maximum arrangement of cards in ss
      def find_max(ss):
        # look for impossible combinations
        if (10 in ss) and (4 in ss or 8 in ss or 12 in ss): return
        even = any(x % 2 == 0 for x in ss)
        if (5 in ss and even) and (4 in ss or 8 in ss or 12 in ss): return
        # calculate the sum of the digits
        ds = sum(dsum[x] for x in ss)
        # check for divisibility by 9
        if (9 in ss) and ds % 9 != 0: return
        # check for divisibility by 3
        if (3 in ss or 6 in ss or 12 in ss) and ds % 3 != 0: return
        # look for max rearrangement
        r = Accumulator(fn=max)
        fn = (lambda x: (lambda x: (-len(x), x))(str(x)))
        for s in subsets(sorted(ss, key=fn, reverse=1), size=len, select="P"):
          if even and s[-1] % 2 != 0: continue
          # done, if leading digits are less than current max
          if r.value and s[0] != r.data[0] and str(s[0]) < str(r.value): break
          # form the number
          n = int(join(s))
          if all(n % x == 0 for x in ss): r.accumulate_data(n, s)
        return (r.value, r.data)
      
      # sort subsets of cards into the total number of digits
      d = group(subsets(cards, min_size=1), by=(lambda ss: sum(ndigits[x] for x in ss)))
      
      r = Accumulator(fn=max)
      for k in sorted(d.keys(), reverse=1):
        printf("[considering {k} digits ...]")
      
        for ss in d[k]:
          rs = find_max(ss)
          if rs is None: continue
          r.accumulate_data(*rs)
      
        if r.value: break
      
      printf("max = {r.value} [{s}]", s=join(r.data, sep=","))
      

      Solution: The number is 987362411112.

      The cards are: (1, 2, 3, 4, 6, 7, 8, 9, 11, 12).

      Like

      • Frits 6:52 pm on 9 December 2021 Permalink | Reply

        If “5” is included then the number must end in “10” or “5” and the cards “4”, “8”, “12” are excluded (not relying on an even card). I got this from Brian’s solution on his puzzle site.

        Like

        • Jim Randell 10:04 am on 10 December 2021 Permalink | Reply

          @Frits: Good point.

          So if “5” or “10” are used, none of “4”, “8”, “12” can be used. And vice versa, if “4”, “8” or “12” are used, none of “5” or “10” can be used. So at least 3 digits must be absent, and we can start the search from 12 digits.

          Here’s a neater version of my code:

          from enigma import (enigma, irange, group, subsets, mlcm, Accumulator, join, printf)
          
          # the cards
          cards = list(irange(1, 12))
          
          # map cards to their digit sum, and number of digits
          dsum = dict((x, enigma.dsum(x)) for x in cards)
          ndigits = dict((x, enigma.ndigits(x)) for x in cards)
          
          # find maximum arrangement of cards in ss
          def find_max(ss):
            d = mlcm(*ss)
            even = any(x % 2 == 0 for x in ss)
            # look for max rearrangement
            r = Accumulator(fn=max)
            fn = (lambda x: (lambda x: (-len(x), x))(str(x)))
            for s in subsets(sorted(ss, key=fn, reverse=1), size=len, select="P"):
              if even and s[-1] % 2 != 0: continue
              # done, if leading digits are less than current max
              if r.value and s[0] != r.data[0] and str(s[0]) < str(r.value): break
              # form the number
              n = int(join(s))
              if n % d == 0: r.accumulate_data(n, s)
            return (r.value, r.data)
          
          # reject impossible subsets
          def check(ss):
            # look for impossible combinations
            if (5 in ss or 10 in ss) and (4 in ss or 8 in ss or 12 in ss): return False
            # calculate the sum of the digits
            ds = sum(dsum[x] for x in ss)
            # check for divisibility by 9
            if (9 in ss) and ds % 9 != 0: return False
            # check for divisibility by 3
            if (3 in ss or 6 in ss or 12 in ss) and ds % 3 != 0: return False
            # looks OK
            return True
          
          # sort subsets of cards into the total number of digits
          d = group(subsets(cards, min_size=1), st=check, by=(lambda ss: sum(ndigits[x] for x in ss)))
          
          r = Accumulator(fn=max)
          for k in sorted(d.keys(), reverse=1):
            printf("[considering {k} digits ...]")
          
            for ss in d[k]:
              rs = find_max(ss)
              if rs is None: continue
              r.accumulate_data(*rs)
          
            if r.value: break
          
          printf("max = {r.value} [{s}]", s=join(r.data, sep=","))
          

          Like

    • GeoffR 2:30 pm on 10 December 2021 Permalink | Reply

      In this first solution, I assumed it was reasonable for the largest number to start with the digits 9,8,7 to minimise a solution run-time. It also found the seven possible solutions for Liam’s numbers from which the maximum can be found.

      from enigma import Timer
      timer = Timer('ST2843', timer='E')
      timer.start()
      
      from itertools import permutations
      
      # assume number from cards is ABCDEFGHIJ, with A = 9, B = 8 and C = 7
      # Also no digit in A..J is 5 or 10 - see previous postings
      cards = set((1, 2, 3, 4, 6, 7, 8, 9, 11, 12))
      
      # Assume first three digits must be 9, 8 and 7 to maximise Liam's number
      A, B, C = 9, 8, 7
      a, b, c = str(A), str(B), str(C)
      
      cards2 = cards.difference([A, B, C])
      
      Liam_nums = []
      
      # permute remainder of cards
      for p1 in permutations(cards2, 7):
        D, E, F, G, H, I, J = p1
        d, e, f, g = str(D), str(E), str(F), str(G)
        h, i, j = str(H), str(I), str(J)
        num = int(a + b + c + d + e + f + g + h + i + j)
        if all(num % d == 0 for d in (A, B, C, D, E, F, G, H, I, J)):
          if num not in Liam_nums:
            Liam_nums.append(num)
      
      # find largest number in the list
      print (f"Largest possible number = { max(Liam_nums)}")
      timer.stop()      
      timer.report()
      
      # Largest possible number = 987362411112
      #[ST2843] total time: 0.0151168s (15.12ms)
      
      print(Liam_nums)
      # There are only seven possible numbers in Liam's list:
      # [987162411312, 987111312264, 987241136112, 987211614312,
      #  987341621112, 987362411112, 987113624112]
      
      
      

      In the second solution, I did a full permutation solution for the 12 cards, which had an expected longer run-time, as there were over 6,300 potential numbers in the list.

      
      from enigma import Timer
      timer = Timer('ST2843', timer='E')
      timer.start()
      
      from itertools import permutations
      
      # Assume digits 5 & 10 not included (previous postings)
      # Assume 10-digit number is ABCDEFGHIJ
      cards = set((1, 2, 3, 4, 6, 7, 8, 9, 11, 12))
      
      Liam_nums = []
      
      for p1 in permutations(cards):
        A, B, C, D, E, F, G, H, I, J = p1
        a, b, c = str(A), str(B), str(C)
        d, e, f, g = str(D), str(E), str(F), str(G)
        h, i, j = str(H), str(I), str(J)
        num = int(a + b + c + d + e + f + g + h + i + j)
        if all(num % d == 0 for d in (A, B, C, D, E, F, G, H, I, J)):
          if num not in Liam_nums:
            Liam_nums.append(num)
      
      # find largest number in the list
      print (f"Largest possible number = { max(Liam_nums)}")
      timer.stop()      
      timer.report()
      
      #Largest possible number = 987362411112
      #[ST2843] total time: 9.1977548s (9.20s)
      
      

      Like

  • Jim Randell 4:15 pm on 1 October 2021 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3080: One of a kind 

    From The Sunday Times, 3rd October 2021 [link]

    The raffle tickets at the Mathematical Society Dinner were numbered from 1 to 1000. There were four winning tickets and together they used each of the digits from 0 to 9 once only. The winning numbers could be classified uniquely as one square, one cube, one prime and one triangular number. For example, 36 is a triangular number as 1+2+3+4+5+6+7+8 = 36, but it cannot be a winner as 36 is also a square. The tickets were all sold in strips of five, and two of the winning numbers were from consecutive strips. The first prize was won by the holder of the smallest-numbered winning ticket, which was not a cube.

    List the four winning numbers in ascending order.

    [teaser3080]

     
    • Jim Randell 4:34 pm on 1 October 2021 Permalink | Reply

      The following Python program runs in 64ms.

      Run: [ @replit ]

      from enigma import irange, singleton, is_cube, is_square, is_triangular, is_prime, empty, tuples, printf
      
      # collect numbers with no repeated digits as strings
      def collect(fns, a=1, b=1000):
        rs = list(list() for _ in fns)
        for n in irange(a, b):
          # remove numbers with repeated digits
          s = str(n)
          if len(s) != len(set(s)): continue
          # does the number satisfy a single condition
          j = singleton(i for (i, fn) in enumerate(fns) if fn(n))
          if j is not None: rs[j].append(s)
        return rs
      
      # collect each category
      cats = collect([is_cube, is_square, is_triangular, is_prime])
      
      # find members of each set, such that each digit is used exactly once
      def solve(ss, ns=[], ds=empty):
        # are we done?
        if not(ss):
          if len(ds) == 10:
            yield ns
        else:
          # choose an element from the next set
          for n in ss[0]:
            if not(ds.intersection(n)):
              yield from solve(ss[1:], ns + [n], ds.union(n))
      
      # allocate tickets to strips
      strip = lambda n: (n + 4) // 5
      
      # find candidate winning tickets
      for ns in solve(cats):
        # smallest number is not a cube
        ns = sorted(int(n) for n in ns)
        if is_cube(ns[0]): continue
        # find numbers on consecutive strips
        if any(b == a + 1 for (a, b) in tuples(map(strip, ns), 2)):
          printf("{ns}")
      

      Solution: The winning numbers are: 49, 53, 216, 780.

      Like

    • GeoffR 12:05 pm on 4 October 2021 Permalink | Reply

      For the 10 unique digits used in this teaser, I found only two arrangements to partition the 10 different digits to give four numbers, so that no number was greater than 1000.

      These two 10-digit arrangements were 1:3:3:3 and 2:2:3:3.

      The first 10-digit arrangement i.e. 1:3:3:3 did not produce a solution, using a similar MiniZinc programme for the second 10-digit arrangement i.e. 2:2:3:3, shown below.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      var 1..9:A; var 0..9:B; var 1..9:C; var 1..9:D; var 1..9:E; 
      var 0..9:F; var 0..9:G; var 1..9:H; var 0..9:I; var 0..9:J; 
      
      % four winning tickets used each of the digits from 0 to 9 once only
      constraint all_different([A, B, C, D, E, F, G, H, I, J]);
      
      predicate is_sq(var int: y) =
        exists(z in 1..ceil(sqrt(int2float(ub(y))))) (
              z*z = y );
              
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
      
      predicate is_tri( var int: n) =
        exists ( x in 1..n div 2)
             ( x * (x+1) div 2 = n);
      
      predicate is_cube(var int: c) =
         let {
            var 0..ceil(pow(int2float(ub(c)),(1/3))): z
         } in z*z*z = c;
         
      % Assume number digit splits are 2:2:3:3 to use the ten different digits
      var 10..99:AB = 10*A + B;
      var 10..99:CD = 10*C + D;
      var 100..999:EFG = 100*E + 10*F + G;
      var 100..999:HIJ = 100*H + 10*I + J;
      
      % Reducing 24 no.possible permutations, for 4 items, 
      % to say 9 permutations for two repeated groups of digit patterns,
      % omitting AB as a cube for the first 2-digit number, as specified,
      % proved sufficient to find the unique answer for the four numbers.
      constraint 
         (is_sq(AB) /\ is_prime(CD) /\ is_cube(EFG) /\ is_tri(HIJ)  )
      \/ (is_sq(AB) /\ is_cube(CD) /\ is_prime(EFG) /\ is_tri(HIJ)  )
      \/ (is_sq(AB) /\ is_tri(CD) /\ is_prime(EFG) /\ is_cube(HIJ)  )
      
      \/ (is_prime(AB) /\ is_sq(CD) /\ is_cube(EFG) /\ is_tri(HIJ)  )
      \/ (is_prime(AB) /\ is_cube(CD) /\ is_sq(EFG) /\ is_tri(HIJ)  )
      \/ (is_prime(AB) /\ is_tri(CD) /\ is_sq(EFG) /\ is_cube(HIJ)  )
      
      \/ (is_tri(AB) /\ is_sq(CD) /\ is_prime(EFG) /\ is_cube(HIJ)  )
      \/ (is_tri(AB)/\ is_prime(CD) /\ is_sq(EFG)  /\ is_cube(HIJ)  )
      \/ (is_tri(AB) /\ is_cube(CD) /\ is_sq(EFG) /\ is_prime(HIJ)  );
      
      % put four numbers in increasing order
      constraint increasing ( [ AB, CD, EFG, HIJ]);
      
      % two of the winning numbers were from consecutive strips of 5 tickets
      constraint ((CD + 4) div 5 - (AB + 4) div 5 == 1)
      \/ ((EFG + 4) div 5 - (CD + 4) div 5 == 1)
      \/ ((HIJ + 4) div 5 - (EFG + 4) div 5 == 1) ;
      
      output [ "Four numbers are " ++ show([AB, CD, EFG, HIJ]) ];
      

      Like

    • Frits 3:29 pm on 4 October 2021 Permalink | Reply

      from enigma import SubstitutedExpression
      from itertools import permutations as perm
      
      checknum = lambda n: n in td
      gettype = lambda n: td[n]
      
      # two ticket numbers must be in adjacent strips
      def consecutive(li):
       strips = [(x - 1) // 5 for x in li]
       if any(strips[i + 1] == x + 1 for i, x in enumerate(strips[:-1])):
         return True
       return False
      
      # perfect squares and perfect cubes between 1000 and 9999
      squares = set(i ** 2 for i in range(1, 32))
      # as smallest ticket may not be a cube start with 27
      cubes = set(i ** 3 for i in range(3, 11))
      tris = set((i * (i + 1)) // 2 for i in range(1, 45))
      
      # set of prime numbers up to 997
      P = {2, 3, 5, 7}
      P |= {x for x in range(11, 33, 2) if all(x % p for p in P)}
      P |= {x for x in range(33, 1000, 2) if all(x % p for p in P)}
      
      td = dict()  # dictionary of tickets
      # build dictionary of "classified uniquely" ticket numbers
      for n in range(1, 1000):
       # skip numbers with duplicate digits
       if len(set(str(n))) != len(str(n)): continue
       cnt = 0
       for i, y in enumerate([squares, cubes, tris, P]):
         if n in y:
           cnt += 1
           i1 = i
       # classified uniquely?
       if cnt == 1:
         td[n] = i1
      
      # determine digits that occur in all cubes
      cubes = [k for k, v in td.items() if v == 1]
      mand_dgts = set(str(cubes[0]))
      for c in cubes[1:]:
       mand_dgts &= set(str(c))
      
      # remove non-cube entries which use digits that occur in all cubes
      if mand_dgts:
       td = dict((k, v) for k, v in td.items()
                 if v == 1 or all(c not in str(k) for c in mand_dgts))
      
      # the alphametic puzzle (numbers AB, CDE, FGH and IJK are increasing)
      p = SubstitutedExpression(
       [
        "A == 0 or C == 0",   # AB and CDE must have total length of 4
        "A + C = X",          # X is non-zero and represents A or C
      
        # check AB
        "checknum(AB)",
        "gettype(AB) != 1",   # not a cube
      
        # check CDE
        "AB < CDE and checknum(CDE)",
        "gettype(CDE) not in {gettype(AB)}",
        "consecutive([AB, CDE]) = Y",
      
        # check FGH
        "C < F",
        "checknum(FGH)",
        "gettype(FGH) not in {gettype(AB), gettype(CDE)}",
        "Y or (G == 9 and F < 8) or consecutive([CDE, FGH])",
        #"consecutive([CDE, FGH]) = Z",
        #"Y or Z or (G == 9 and F < 8)",
      
        # check IJK
        "F < I",
        "checknum(IJK)",
        "gettype(IJK) not in {gettype(AB), gettype(CDE), gettype(FGH)}",
      
        # two ticket numbers must be in adjacent strips
        #"consecutive([AB, CDE, FGH, IJK])",
        "Y or consecutive([CDE, FGH, IJK])",
        #"Y or Z or consecutive([FGH, IJK])",
       ],
      
       answer="AB, CDE, FGH, IJK",
       verbose=0,
       d2i=dict([(0, "FI")] +
                [(1, "I")] +
                [(8, "C")] +
                [(9, "CF")]),
       distinct="BDEFGHIJKX",
       env=dict(consecutive=consecutive, checknum=checknum, gettype=gettype),
       reorder=0,
      )
      
      # print answer
      for (_, ans) in p.solve():
       print(f"{ans}")
      

      Like

    • GeoffR 4:47 pm on 4 October 2021 Permalink | Reply

      This Python programme lists all 3-digit primes, squares, cubes and triangular numbers, without repeating digits, with reference to a 1:3:3:3 digits split solution.

      from enigma import is_prime
      
      L1, L2, L3, L4 = [], [], [], []
      
      #1. 3-digit squares without repeating digits
      print('3-digit squares')
      L1 = [ x * x for x in range(10, 32) if len(set(str(x*x))) == len(str(x*x)) ]
      print(L1)
      
      #2. set of 3-digit tri numbers, without repeating digits
      print('3-digit triangular numbers')
      for n in range(14,45):
          tri = n * (n + 1)//2
          if len(set(str(tri))) == len(str(tri)):
              L2.append(tri)
      
      print(L2); print(len(L2))
      
      #3. 3-digit cubes. without repeating digits
      print('3-digit cubes')
      
      L3 = [ x*x*x for x in range(5,10) if len(set(str(x*x*x))) == len(str(x*x*x)) ]
      print(L3)
      
      #4. 3-digit primes, without repeating digits
      print('3-digit primes')
      for n in range(100,1000):
          if is_prime(n) and len(set(str(n))) == len(str(n)):
              L4.append(n)
      
      print(L4); print(len(L4))
      
      # 3-digit squares, non repeating digits
      # [169, 196, 256, 289, 324, 361, 529, 576, 625, 729, 784, 841, 961] 13 no.
      
      # 3-digit triangular numbers, non repeating digits
      # 105, 120, 136, 153, 190, 210, 231, 253, 276, 325, 351, 378,
      # 406, 435, 465, 496, 528, 561, 630, 703, 741, 780, 820, 861,
      # 903, 946] 26 no.
      
      # 3-digit cubes, non repeating digits
      # [125, 216, 512, 729] 4 no.
      
      # 3-digit primes, non repeating digits
      # 103, 107, 109, 127, 137, 139, 149, 157, 163, 167, 173, 179,
      # 193, 197, 239, 241, 251, 257, 263, 269, 271, 281, 283, 293,
      # 307, 317, 347, 349, 359, 367, 379, 389, 397, 401, 409, 419,
      # 421, 431, 439, 457, 461, 463, 467, 479, 487, 491, 503, 509,
      # 521, 523, 541, 547, 563, 569, 571, 587, 593, 601, 607, 613,
      # 617, 619, 631, 641, 643, 647, 653, 659, 673, 683, 691, 701,
      # 709, 719, 739, 743, 751, 761, 769, 809, 821, 823, 827, 829,
      # 839, 853, 857, 859, 863, 907, 937, 941, 947, 953, 967, 971,
      # 983] 97 no.
      
      
      
      

      Manual Analysis – why a 1:3:3:3 digits split is not viable
      ———————————————————-

      Considering a 1:3:3:3 digits split, the single digit can be a square (1,4,9), a prime (2,3,5), a triangular number (1,3,6) but not a cube(1,8) as per teaser conditions.

      For any combination of the three remaining 3-digit numbers, I found there was usually a duplicate hundreds digit (1-9), after choosing the first 3-digit number. The 400 series for 3-digit squares, as 400, 441 etc was excluded due to repeating digits.

      Obviously, this prevents finding four separate numbers with ten different digits.

      I also checked for any possibility of consecutive numbers in two strips of five tickets at the end of one hundred series e.g. end of 190’s and the start of a new hundred series e.g. start of 200’s.

      One instance of a 3-digit triangular number(496) and a consecutive 3-digit prime(503) was found, leaving the digits (1,2,7,9) to form a 3-digit cube and a single digit square, or a single digit cube and a 3-digit square. This was not found to be possible. The only 3-digit numbers found were either not in any of the four number categories, or duplicate primes to 503.

      The over-riding reasons why three 3-digit suitable numbers could not be found was the duplication of the hundreds digit and the teaser requirement to obtain two numbers in two consecutive strips of five tickets.

      Like

  • Jim Randell 10:37 am on 7 September 2021 Permalink | Reply
    Tags: by: Andrew Skidmore,   

    Teaser 2820: Three ages 

    From The Sunday Times, 9th October 2016 [link] [link]

    Today is Alan’s, Brian’s and Colin’s birthday. If I write down their ages in a row in that order then I get a six-figure number. If I write down their ages in a row in the reverse order (i.e., Colin’s followed by Brian’s followed by Alan’s) then I get a lower six-figure number. When I divide the difference between these two six-figure numbers by the total of their three ages the answer is Alan’s age multiplied by Colin’s.

    What are Alan’s, Brian’s and Colin’s ages?

    As published there are 2 possible solutions to this puzzle.

    This puzzle was not included in the published collection of puzzles The Sunday Times Brainteasers Book 1 (2019).

    [teaser2820]

     
    • Jim Randell 10:38 am on 7 September 2021 Permalink | Reply

      If we assume the ages have 2 digits each (something not mentioned in the puzzle text), then we can quickly use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this problem.

      The following run file executes in 187ms.

      #! python3 -m enigma -r
      
      # A = UV
      # B = WX
      # C = YZ
      
      SubstitutedExpression
      
      --distinct=""
      
      "(UV * YZ) * (UV + WX + YZ) + YZWXUV = UVWXYZ"
      

      And this finds two viable solutions.

      However it is not a great deal of work to write a program that considers ages that include 1-digit and 3-digit ages (with a suitable upper limit).

      The following Python program runs in 179ms, and finds the same two solutions.

      Run: [ @replit ]

      from enigma import (irange, printf)
      
      # permissible ages
      ages = irange(1, 120)
      
      for A in ages:
        for B in ages:
          AB = str(A) + str(B)
          if len(AB) > 5: break
          for C in ages:
            ABC = AB + str(C)
            if len(ABC) > 6: break
            if len(ABC) < 6: continue
            d = int(ABC) - int(str(C) + str(B) + str(A))
            if A * C * (A + B + C) == d:
              printf("A={A} B={B} C={C} [A:B:C={A}{B}{C} C:B:A={C}{B}{A}; d={d}]")
      

      Solution: The are two possible answers: Alan = 22, Brian = 61, Colin = 18; Alan = 99, Brian = 70, Colin = 33.

      These could be reduced to a single solution by adding one of the following conditions:

      (a) “None of the ages include the digit 0” → (22, 61, 18)
      (b) “Alan is older than Brian, who is older than Colin” → (99, 70, 33)

      We can run the Python program above to consider ages up to 9999, and we find that without constraining the values of A, B, C there are 5 possible solutions:

      (22, 61, 18)
      (37, 326, 3)
      (51, 830, 3)
      (78, 252, 6)
      (99, 70, 33)

      Like

    • GeoffR 12:13 pm on 7 September 2021 Permalink | Reply

      # Using 2-digit ages: Alan = ab, Brian = cd, Colin = ef
      for ab in range(10, 100):
        for cd in range (10, 100):
          for ef in range(10, 100):
            abcdef = 10000*ab + 100*cd + ef  # ages in order
            efcdab = 10000*ef + 100*cd + ab  # ages in reverse order
            if abcdef < efcdab:continue
            diff = abcdef - efcdab
            if diff == (ab * ef) * (ab + cd + ef):
              print(f"Alan = {ab}, Brian = {cd}, Colin = {ef}")
              
      # Alan = 22, Brian = 61, Colin = 18
      # Alan = 99, Brian = 70, Colin = 33
      
      
      

      Like

      • Frits 2:46 pm on 7 September 2021 Permalink | Reply

          
        # Using 2-digit ages: Alan = A, Brian = B, Colin = C
        # difference <d> does not depend on B
        for A in range(10, 100):
          sA = str(A)
          for C in range(10, A):
            # use dummy "10" for the value of B
            d = int(sA + "10" + str(C)) - int(str(C) + "10" + sA)
            (sumABC, r) = divmod(d, A * C)
            if r != 0: continue
            B = sumABC - A - C
            if not (9 < B < 100): continue
            print(f"Alan = {A}, Brian = {B}, Colin = {C}")
        

        Like

        • Jim Randell 4:11 pm on 7 September 2021 Permalink | Reply

          Or (still assuming 2-digit ages):

          from enigma import (irange, subsets, div, printf)
          
          # assuming 2 digit ages
          for (C, A) in subsets(irange(10, 99), size=2):
            B = div(9999 * (A - C), A * C)
            if B is None: continue
            B -= A + C
            if B < 10 or B > 99: continue
            printf("A={A} B={B} C={C}")
          

          or:

          #! python3 -m enigma -r
          SubstitutedExpression
          
          --distinct=""
          
          "div(9999 * (UV - YZ), UV * YZ) - UV - YZ = WX"
          

          Like

      • Frits 6:18 pm on 7 September 2021 Permalink | Reply

         
        # Using 2-digit ages: Alan = A, Brian = B, Colin = C
        #
        #  d = 9999 * (A - C) = (A * C) * (A + B + C)
        #    9999 = 3 * 3 * 11 * 101
        #
        # as A * C cannot be a multiple of 101 the sum A + B + C must be 101 or 202
        # this means that A * C must be a multiple of 99
        #            and (A * C) / (A - C) is 49.5 or 99
        
        for A in [x for x in range(11, 100) if x % 3 == 0 or x % 11 == 0]:
         for i, y in enumerate([A + 99, 2 * A + 99]):
            (C, r) = divmod(99 * A, y)
            if r > 0 or not (9 < C < 99): continue
            
            B = 101 - A - C if i == 0 else 202 - A - C
            if not (9 < B < 100): continue     # probably not needed
            
            print(f"Alan = {A}, Brian = {B}, Colin = {C}") 
        

        Like

      • Frits 9:22 pm on 7 September 2021 Permalink | Reply

        Allowing for ages up to 999, again we don’t need to loop over B.

          
        # allow for high 3-digit ages
        for A in range(10, 1000):
          sA = str(A)
          
          if A < 100:
            # see previous posting
            rangeC = list(range(1, 10)) + \
                     [int((99 * A) / (A + 99)), int((99 * A) / (2 * A + 99))] 
          else:
            rangeC = range(1 , A  % 100)
          
          for C in rangeC:
            sC = str(C)
            if sC[0] > sA[0]: continue
            AC = sA + sC
            if len(sA + sC) > 5: break
            
            prodAC = A * C
            
            # allow Brian to be born on 9th October 2016
            minB = 10**(5 - len(AC)) if len(AC) != 5 else 0
            
            # how much does d decrement due to one increment of B? 
            if len(sA) > len(sC):
              difB = int((len(sA) - len(sC)) * "9" + "0")
            else:
              difB = 0
            
            # calculate difference for first B entry
            d = int(sA + str(minB) + sC) - int(sC + str(minB) + sA)  
            
            # rule: (A * C) * (A + minB + C) + n * (A * C) = d - n * difB 
            (n, r) = divmod(d - prodAC * (A + minB + C), prodAC + difB)
            
            if r > 0 or n < 0: 
              continue
            
            B = minB + n
            sB = str(B)
            
            ABC = sA + sB + sC
            if len(ABC) != 6: continue
            d = int(ABC) - int(sC + sB + sA)
            if prodAC * (A + B + C) == d:
              print(f"A={A} B={B} C={C} [A:B:C={A}{B}{C} C:B:A={C}{B}{A}; d={d}]")
        

        Like

        • Jim Randell 10:20 pm on 7 September 2021 Permalink | Reply

          Here’s my take on isolating B from the equation, by adjusting the definition of [[ ages() ]] you can allow whatever range of ages you want (including up to 9999).

          from itertools import product
          from enigma import irange, div, printf
          
          # decompose t into n numbers, min m
          def decompose(t, n, m=1, s=[]):
            if n == 1:
              if not(t < m):
                yield s + [t]
            else:
              for x in irange(m, t - n + 1):
                yield from decompose(t - x, n - 1, m, s + [x])
          
          # acceptable k digit ages
          def ages(k):
            if k == 3:
              return irange(100, 120)
            if k < 3:
              return irange(10 ** (k - 1), (10 ** k) - 1)
          
          # consider number of digits a, b, c; a + b + c = 6
          for (a, b, c) in decompose(6, 3):
            # age ranges
            (rA, rB, rC) = (ages(k) for k in (a, b, c))
            if not(rA and rB and rC): continue
            # multipliers
            mA = 10 ** (b + c) - 1
            mB = (10 ** c) - (10 ** a)
            mC = 10 ** (a + b) - 1
            # consider values for A and C
            for (A, C) in product(rA, rC):
              AC = A * C
              B = div(A * mA - C * mC - AC * (A + C), AC - mB)
              if B is not None and B in rB:
                printf("A={A} B={B} C={C}")
          

          Like

          • Frits 10:53 pm on 7 September 2021 Permalink | Reply

            @Jim, very concise.

            Almost twice as fast with PyPy (for ages up to 999) although having 4 times as many (innermost) loops (187920 and 44649).

            Like

          • Frits 12:16 pm on 8 September 2021 Permalink | Reply

            @Jim,

            While trying decompose(11, 3) I got into memory problems (5,6 GB memory used).

            Although itertools product is supposed to be a generator the problem disappeared when using separate loops for A and C (25 MB memory used).

            Like

            • Jim Randell 12:41 pm on 8 September 2021 Permalink | Reply

              I suspect internally [[ product() ]] is remembering all the values of the inner loops, because it doesn’t know that range objects are restartable iterators. Which will end up using a lot of memory if the ranges are large.

              So in the general case it would be better to use two for loops. (Which was how it was originally before I decided to save a line and a level of nesting).

              Like

          • Jim Randell 4:00 pm on 9 September 2021 Permalink | Reply

            Since I end up writing [[ decompose() ]] functions a lot in puzzles, I’ve added a helper function to enigma.py to generate them for you (see [[ Decompose() ]] and [[ decompose() ]]).

            For example, this program becomes:

            from enigma import (decompose, irange, div, printf)
            
            # acceptable <k> digit ages
            def ages(k):
              if k == 3:
                return irange(100, 120)
              if k < 3:
                return irange(10 ** (k - 1), (10 ** k) - 1)
            
            # consider number of digits (a, b, c), a + b + c = 6
            for (a, b, c) in decompose(6, 3, increasing=0, sep=0, min_v=1):
              # age ranges
              (rA, rB, rC) = (ages(k) for k in (a, b, c))
              if not(rA and rB and rC): continue
              # multipliers
              mA = 10 ** (b + c) - 1
              mB = (10 ** c) - (10 ** a)
              mC = 10 ** (a + b) - 1
              # consider values for A and C
              for A in rA:
                for C in rC:
                  AC = A * C
                  B = div(A * mA - C * mC - AC * (A + C), AC - mB)
                  if B is not None and B in rB:
                    printf("A={A} B={B} C={C}")
            

            Like

    • Frits 5:52 pm on 9 September 2021 Permalink | Reply

      @Jim, Thanks, I will look into it.

      Calculating rC after A is known is faster:

        
      rC = range(10 ** (c - 1), (int(str(A)[0]) + 1) * 10 ** (c - 1))
      

      Like

    • Frits 2:07 pm on 10 September 2021 Permalink | Reply

      Finding a galactic object for “Brian” 9.5 billion years old.
      This program runs in 8 seconds with PyPy.

       
      from enigma import decompose
      from math import ceil
      
      # acceptable k digit ages
      def ages(k):
        if k == 11:
          # universe is approx. 13.8 billion years old
          return range(10 ** (k - 1), 138 * 10 ** (k - 3))
        else:  
          return range(10 ** (k - 1), (10 ** k))
        
      L = 13  # number of digits concatenated A, B and C
      
      print("number of digits =", L)
      cnt = 0 
      cntsols = 0
      
      # consider number of digits a, b, c; a + b + c = L
      for (a, b, c) in decompose(L, 3, increasing=0, sep=0, min_v=1):
        # skip if A * C * (A + B + C) will have too many digits
        if 2 * a + c - 2 > L or 2 * c + a - 2 > L: 
          continue
        
        # group A range by first digit
        rA = [range(i * 10**(a - 1),  i * 10**(a - 1) + 10**(a - 1)) 
              for i in range(1, 10)]
        rB = ages(b)
        
        # multipliers
        mA = 10 ** (b + c) - 1
        mB = (10 ** c) - (10 ** a)
        mC = 10 ** (a + b) - 1
        
        # consider values for A and C
        for i, grp in enumerate(rA, 1):
          rC = range(10 ** (c - 1), (i + 1) * 10 ** (c - 1))
          
          # check first entry in C loop (see below)
          A = i * 10**(a - 1)  
          C = rC[0]
          if A * C == mB: 
            C = rC[1]     # next entry, we don't want to divide by zero
          
          numeratorB = A * mA - C * mC - A * C * (A + C)
          denominatorB = A * C - mB
          
          # numeratorB decreases and denominatorB increases as C becomes higher
          (B, r) = divmod(numeratorB, denominatorB)
          
          d1 = A * mA + B * mB - C * mC
          if d1 <= 0:    
            # we need a positive distance
            if numeratorB > 0: 
              # check when numeratorB becomes negative
              # (mC + A**2 + A * C) * C - A * mA = 0
              # quadratic equation: A * C**2 + (mC + A**2) * C - A * mA = 0
              newC1 = (-1 * (mC + A**2) + ((mC + A**2)**2 + 4 * A**2 * mA)**.5) 
              newC1 /= (2 * A)
              newC2 = mB / A      # when will denominatorB become positive again?
              newCs = sorted([newC1, newC2])
              low = ceil(newCs[0])
              hgh = int(newCs[1])
              rC = range(low, hgh + 1)
         
          for A in grp:
            for C in rC:
              cnt += 1
              AC = A * C
              
              # difference rule: A * mA + B * mB - C * mC = A * C * (A + B + C)
              if AC == mB: continue  # don't divide by zero
              
              (B, r) = divmod(A * mA - C * mC - AC * (A + C), AC - mB)
              
              if B < 0: break  
              
              if r == 0 and B in rB:
                d1 = int(str(A) + str(B) + str(C)) - int(str(C) + str(B) + str(A))
                d2 = AC * (A + B + C)
                
                print(f"A={A} B={B} C={C}, AC={AC} diff1={d1} diff2={d2}")
                cntsols += 1
            
      print("number of solutions", cntsols, "loop count =", cnt) 
      

      Like

    • GeoffR 1:49 pm on 12 September 2021 Permalink | Reply

      
      ' A Solution in Visual Basic 2019
      Module Module1
        Public Sub Main()
          Dim A, B, C As Integer ' for Alan, Brian and Colin
          Dim AGES, Rev_AGES, DIFF_AGES As Integer
          For A = 10 To 99
            For B = 10 To 99
              If B = A Then
                Continue For
              End If
              For C = 10 To 99
                If C = B Or C = A Then
                  Continue For
                End If
                AGES = 10000 * A + 100 * B + C
                Rev_AGES = 10000 * C + 100 * B + A
                If AGES > Rev_AGES Then
                  DIFF_AGES = AGES - Rev_AGES
                  If DIFF_AGES = (A + B + C) * (A * C) Then
                    Console.WriteLine("Alan = {0}, Brian = {1}, Colin = {2}", A, B, C)
                  End If
                End If
              Next   'C
            Next   'B
          Next   'A
          Console.ReadKey()   'Freeze console screen
        End Sub
      End Module
      
      'Alan = 22, Brian = 61, Colin = 18
      'Alan = 99, Brian = 70, Colin = 33
      
      
      
      

      Like

  • Jim Randell 4:46 pm on 21 May 2021 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3061: Ratio 

    From The Sunday Times, 23rd May 2021 [link]

    Liam has split a standard pack of 52 cards into three piles; black cards predominate only in the second pile. In the first pile the ratio of red to black cards is 3 to 1. He transfers a black card from this pile to the second pile; the ratio of black to red cards in the second pile is now 2 to 1. He transfers a red card from the first pile to the third pile; the ratio of red to black cards in this pile is now a whole number to one.

    Liam told me how many cards (a prime number) were initially in one of the piles; if I told you which pile you should be able to solve this teaser.

    How many cards were initially in the third pile?

    [teaser3061]

     
    • Jim Randell 5:27 pm on 21 May 2021 Permalink | Reply

      I assume that Liam told the setter a specific pile number, and the total number of cards that was initially in that pile and this number of cards was a prime number.

      So knowing the number of the pile, and the fact that the total number of cards in that pile was prime (but not knowing the number itself), is sufficient for us to determine the number of cards that were in the third pile.

      This Python program runs in 48ms.

      Run: [ @replit ]

      from enigma import (irange, div, is_prime, printf)
      
      # generate possible piles
      # return (piles = ((red, black), ...), {indices of prime piles})
      def piles():
        # choose the number of red cards in pile 1 (a multiple of 3)
        for r1 in irange(3, 26, step=3):
          # there are 3 times as many reds as blacks
          b1 = div(r1, 3)
      
          # choose the number of black cards in pile 2 (+1 = a multiple of 2)
          for b2 in irange(3, 26 - b1, step=2):
            # with 1 extra black there are twice as many blacks as reds
            r2 = div(b2 + 1, 2)
            if r1 + r2 > 26: break
      
            # pile 3 has the remaining cards
            r3 = 26 - r1 - r2
            b3 = 26 - b1 - b2
            if b3 > r3: continue
            # with 1 extra red there are k times as many reds as blacks
            k = div(r3 + 1, b3)
            if k is None: continue
      
            printf("[{r1}R+{b1}B; {r2}R+{b2}B; {r3}R+{b3}B; k={k}]")
            ps = ((r1, b1), (r2, b2), (r3, b3))
            pr = set(i for (i, (r, b)) in enumerate(ps) if is_prime(r + b))
            yield (ps, pr)
      
      # collect piles, that have a prime number of cards in one of the piles
      ss = list((ps, pr) for (ps, pr) in piles() if pr)
      
      # look for unique solutions, identified by pile i being prime
      for i in (0, 1, 2):
        rs = list(ps for (ps, pr) in ss if i in pr)
        if len(rs) == 1:
          ((r1, b1), (r2, b2), (r3, b3)) = rs[0]
          printf("{r1}R+{b1}B; {r2}R+{b2}B; {r3}R+{b3}B [pile {i} is prime]", i=i + 1)
      

      Solution: There were initially 11 cards in the third pile.

      There are only 4 ways to construct the piles as described:

      [1] 3R+1B; 12R+23B; 11R+3B (4 + 35 + 13)
      [2] 6R+2B; 12R+23B; 8R+1B (8 + 35 + 9)
      [3] 9R+3B; 10R+19B; 7R+4B (12 + 29 + 11)
      [4] 12R+4B; 11R+21B; 3R+1B (16 + 32 + 4)

      The only collections with a prime number of cards in at least one pile are [1] (pile 3) and [3] (pile 2, pile 3).

      So Liam must have revealed there were 29 cards in pile 2, which means he has constructed collection [3] (as that is the only collection with a prime number of cards in pile 2).

      Although if Liam had revealed just the prime numbers of cards in the pile (without giving the pile number); 11, 13, or 29, that would have been sufficient to determine which collection he had constructed.

      So the second paragraph could be:

      “Liam told me the total number of cards that was initially in one of the piles (but not the number of the pile). This was a prime number, and that enabled me to work out the composition (number of red and black cards) of each of the piles. If I now told you the number of the pile whose total Liam had revealed to me, you could also work out the composition of each of the piles.”

      Like

      • Frits 9:02 pm on 22 May 2021 Permalink | Reply

        from enigma import SubstitutedExpression, is_prime, div
        
        # the alphametic puzzle
        p = SubstitutedExpression(
          [
          # (r1   , b1), (r2, b2), (r3, b3) = 
          # (3 * C, C),  (EF, GH), (IJ, KL)
          
          # both pile 1 and pile 3 contain at least 1 black card
          # black cards predominate only in the second pile
          "0 < EF < 13",
          
          "2 * EF - 1 = GH",
            
          # black cards predominate only in the second pile
          # "3 * C + EF <= C + GH",
          # "3 * C + EF <= C + 2 * EF - 1",
          "2 * C <= EF - 1",                #  EF < 13 --> C < 6 
          
          # with 1 extra red there are k times as many reds as blacks
          "div(27 - 3 * C - EF, 26 - C - GH)",
          
          # Liam told me how many cards (a prime number) were initially 
          # in one of the piles
          "any(is_prime(x) for x in [EF + GH, 52 - 3 * C - EF - C - GH])",
        
          ],
          answer="(3 * C, C), (EF, GH), (26 - 3 * C - EF, 26 - C - GH)",
          d2i=dict([(0, "C")] + 
                   [(k, "E") for k in range(2, 6)] + 
                   [(k, "CE") for k in range(6, 10)] 
                  ),
          distinct="",
          reorder=0,
          verbose=256)
        
        answs = [y for _, y in p.solve()]
        
        for p in range(3):  
          ps = [a for a in answs if is_prime(sum(a[p]))]
          if len(ps) == 1:  # unique
             print(f"third pile has {sum(ps[0][2])} cards")
        

        Based on the generated code and some more analysis (we can conclude r2 is even and b1 is less than 5) only 12 (r2, b1) combinations are considered:

        from enigma import is_prime
        
        answs = []
        # r2 must be even as last pile can't have only 2 cards
        # (so we deal with odd primes only)
        for r2 in range(4, 13, 2):
          b2 = 2 * r2 - 1
          p2 = is_prime(r2 + b2)
          for b1 in range(1, min(r2 // 2, 26 - b2)):
            # 26 - b1 - b2 > 0 --> b1 < 26 - b2 
            
            # with 1 extra red there are <k> times as many reds as blacks
            (d, r) = divmod(27 - 3 * b1 - r2, 26 - b1 - b2)
            if r > 0: continue
            # a prime number of cards were initially in one of the piles
            if p2 or is_prime(52 - 4 * b1 - r2 - b2): 
              answs.append([(3 * b1, b1), (r2, b2), (26 - 3 * b1 - r2, 26 - b1 - b2)])
        
        for p in range(3):  
          ps = [a for a in answs if is_prime(sum(a[p]))]
          if len(ps) == 1:  # unique
             print(f"third pile has {sum(ps[0][2])} cards") 
        

        Like

      • Tony Brooke-Taylor 6:31 pm on 25 May 2021 Permalink | Reply

        I wanted to visualise this problem as points on the line where two surfaces intersect. Because of the simple relationships between the red count and black count in each pile, we can easily define planes on the same 3 axes such that one plane represents the black values and the others represent the set of reds corresponding to a given value of N, where N is the ratio of reds to blacks in the third pile, after the swaps. I followed the maths through and arrived at a set of constraints such that I had to test 11 combinations of (b1,b2) to get the 4 possible results. I expect my analysis is much the same as Frits’, but the route depends on which parameters we choose to loop. My code for the solution is not very interesting, but I thought I’d share my graphical representation. The code below is based on an approach set out by banderlog013 on stackoverflow. If you draw the plot for the appropriate value of N, and run your mouse down the line of intersection, you will see that only one point has integer values for x,y,z that sum to 26.

        
        
        import numpy as np
        import plotly.graph_objects as go
        from plotly.subplots import make_subplots
        from typing import Tuple, Iterable
        
        def plotPlane(fig: go.Figure,
                      normal: Tuple[int, int, int],
                      d: int,
                      values: Iterable,
                      colorScaleName: str) -> None:
        
            # x, y, z
            x, y = np.meshgrid(values, values)
            z = (-normal[0] * x - normal[1] * y - d) * 1. / normal[2]
        
            # draw plane
            surface = go.Surface(x=x, y=y, z=z, colorscale=colorScaleName, showscale=False)
            fig.add_trace(surface, row=1, col=1)
        
        N=1#Not correct but if you have solved the puzzle you will know what is
        
        point1  = -26
        normal1 = (1,1,1)
        
        point2  = -26.5
        normal2 = (3,1/2,N)
        
        # create figure
        fig = make_subplots(rows=1, cols=1, specs=[[{'type': 'surface'}]])
        # plot two intersectioned surfaces
        values = range(1, 26)
        plotPlane(fig, normal1, point1, values, "Hot")
        plotPlane(fig, normal2, point2, values, "Greys")
        fig.show()
        
        

        Like

    • Robert Brown 9:19 am on 22 May 2021 Permalink | Reply

      Following the steps in your program, I find a different answer from the one posted by Brian.

      My values are
      b1 = 1, r1 = 3: (r1 = 3*b1): total not prime
      b2 = 23, r2 = 12: (b2+1/r2 = 2): total not prime
      b3 = 2, r3 = 11: (r3+1/b3 = 6): total (13) is prime

      Am I doing something silly?

      Like

      • Jim Randell 9:49 am on 22 May 2021 Permalink | Reply

        @Robert: There are actually four collections of piles that can be constructed following the rules of the first paragraph of the puzzle text.

        But the second paragraph allows you to identify which one of those four provides the answer to the puzzle.

        Like

        • Robert Brown 7:53 am on 23 May 2021 Permalink | Reply

          Yes, Brian’s solution has prime totals for piles 2 & 3, my alternative just for pile 3. The other two have no prime totals. So if Liam had quoted the total for pile 3, we would have a choice of 2 solutions. It follows that he quoted the total for pile 2, leading to Brian’s solution.

          Like

          • Jim Randell 11:33 am on 23 May 2021 Permalink | Reply

            @Robert: That’s correct.

            Interestingly if Liam had revealed just the initial total number of cards in one of the piles (without revealing the number of the pile), and that number was prime, it would be enough for the setter to work out the composition of each of the piles.

            The setter can then tell us the number of the pile that Liam was referring to, and the fact that the total number of cards in that pile was prime, and this is enough for us to also work out the composition of each of the piles.

            Like

    • Hugh Casement 1:13 pm on 30 May 2021 Permalink | Reply

      More troublesome logic.
      As far as I can see, the constraints are:
      red1 = 3 × black1
      black2 + 1 = 2 × red2
      (red3 + 1) mod black3 = 0
      and the total is 52 (with no variables being 0).

      I found well over 100 sets that satisfy those conditions!
      Prime numbers abound, so I don’t see how any conclusions can be drawn.
      How is it that others found only four possible sets?

      Like

    • Hugh Casement 6:14 pm on 30 May 2021 Permalink | Reply

      Thanks for that, Jim. You can tell it’s a long time since I had a pack of cards in my hands!

      Like

  • Jim Randell 5:04 pm on 16 April 2021 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3056: Rose garden 

    From The Sunday Times, 18th April 2021 [link]

    The six rose bushes in my garden lie on a circle. When they were very small, I measured the six internal angles of the hexagon that the bushes form. These were three-digit whole numbers of degrees. In a list of them, of the ten digits from 0 to 9, only one digit is used more than once and only one digit is not used at all. Further examination of the list reveals that it contains a perfect power and two prime numbers.

    In degrees, what were the smallest and largest angles?

    [teaser3056]

     
    • Jim Randell 5:51 pm on 16 April 2021 Permalink | Reply

      (See also: Teaser 1885).

      The internal angles of a hexagon must sum to 720°, and as they are all 3-digit whole numbers of degrees we see that they are all in the range 100° to 179°. So the repeated digit must be 1. (And with a little bit of analysis we can reduce the range of the angles further).

      Additionally the alternating angles of a cyclic hexagon, must sum to 360°, so the angles must be able to be formed into 2 groups of 3, each group summing to 360°. (In general for cyclic 2n-gon the alternating angles must have the same sum).

      These constraints, along with the other conditions give two possible sets of angles, but they have the same largest and smallest values.

      I assumed the angles were all different (although 111° could potentially be repeated, but there are no solutions where it is).

      This Python 3 program runs in 122ms.

      Run: [ @replit ]

      from enigma import irange, mgcd, unpack, prime_factor, subsets, multiset, nsplit, printf
      
      # check digits have no repeats (other than 1)
      def digits(ns, ds=None):
        ds = (multiset() if ds is None else ds.copy())
        for n in ns:
          ds.update_from_seq(nsplit(n))
        # check the digits
        if all(v == 1 or k == 1 for (k, v) in ds.items()): return ds
      
      # determine if a number is a prime or an exact power from its prime factorisation
      is_prime = lambda fs: len(fs) == 1 and fs[0][1] == 1
      is_power = lambda fs, gcd=unpack(mgcd): gcd(e for (p, e) in fs) > 1
      
      # collect candidate primes, powers and others
      (primes, powers, others) = (list(), list(), set())
      for n in irange(100, 179):
        if not digits([n]): continue
        fs = list(prime_factor(n))
        if is_prime(fs):
          primes.append(n)
        elif is_power(fs):
          powers.append(n)
        else:
          others.add(n)
      
      # decompose <t> into <k> numbers in range [m, M]
      # that are not in primes or powers
      def decompose(t, k, m=100, M=179, ns=[]):
        # are we done?
        if k == 1:
          if not(t < m or t > M) and t in others:
            yield ns + [t]
        else:
          # choose the next number
          k_ = k - 1
          for n in irange(m, min(M, t - k_ * m)):
            if n in others:
              yield from decompose(t - n, k_, n + 1, M, ns + [n])
      
      # choose the two primes
      for (b, c) in subsets(primes, size=2):
        ds1 = digits([b, c])
        if ds1 is None: continue
      
        # choose the power
        for a in powers:
          ds2 = digits([a], ds1)
          if ds2 is None: continue
      
          # find the remaining angles
          for xs in decompose(720 - (a + b + c), 3):
            ds3 = digits(xs, ds2)
            if ds3 is None: continue
            # only one of the 10 digits is missing
            if len(ds3.keys()) != 9: continue
      
            # and the sum of alternate angles must be 360 degrees
            ns = sorted([a, b, c] + xs)
            if any(sum(ss) == 360 for ss in subsets(ns, size=3)):
              printf("min={ns[0]} max={ns[-1]} {ns}")
      

      Solution: The smallest angle is 101°. The largest angle is 146°.


      Measuring angles in degrees. The 6 angles are all integers between 101 and 179 (100 is ruled out because of the repeated 0 digit).

      And they must form two groups of 3 that add up to 360, so the largest possible angle is 360 − 101 − 111 = 148.

      This limits the possible powers to: 121, 125, 128.

      So, whichever power is chosen the digit 2 will be used.

      The primes are therefore limited to: 101, 103, 107, 109, 113, 131, 137, 139.

      So, whichever primes are chosen one will contain the digit 0 and one will contain the digit 3 (so 103 cannot be chosen).

      Which means the remaining three angles cannot contain the digits 0, 2, or 3.

      The remaining angles are therefore limited to: 111, 114, 115, 116, 117, 118, 119, 141, 145, 146, 147, 148.

      There are no pairs from the permissible remaining angles that pair with 121 to give 360, so the power is either 125 or 128.

      For a power of 125, there are two sets of angles that can make 360, but only one of them leaves another set of angles that can make 360 according to the constraints:

      (125, 117, 118) + (101, 113, 146)

      For a power of 128, there are four sets of angles that can make 360, but only one of them leaves another set of angles that can make 360 according to the constraints (and it is the same set of additional angles as the previous solution):

      (128, 115, 117) + (101, 113, 146)

      And in both cases the unused digit is 9 and the minimum and maximum values both lie in the set without the power.


      There are many ways to produce a cyclic hexagon from a set of angles, but here are two diagrams corresponding to the two solutions. For each diagram I have maximised the smallest distance between vertices:

      Like

      • Jim Randell 12:30 pm on 19 April 2021 Permalink | Reply

        Here is a faster version. It builds up sets of 3 angles that sum to 360° and don’t share non-1 digits, and then looks for two of these sets that don’t share non-1 digits, and checks that together they have exactly 1 power and 2 primes.

        It also allows for a 111° angle to appear multiple times (although this doesn’t give any further solutions).

        It runs in 51ms.

        Run: [ @replit ]

        from enigma import irange, mgcd, unpack, prime_factor, subsets, nsplit, union, printf
        
        # check digits have no repeats (other than 1), return set of digits used
        def digits(ns):
          ds = set()
          for n in ns:
            for d in nsplit(n):
              if d == 1: continue
              if d in ds: return
              ds.add(d)
          return ds
        
        # determine if a number is a prime or an exact power from its prime factorisation
        is_prime = lambda fs: len(fs) == 1 and fs[0][1] == 1
        is_power = lambda fs, gcd=unpack(mgcd): gcd(e for (p, e) in fs) > 1
        
        # max and min possible angles
        (m, M) = (101, 148)
        
        # collect candidate primes, powers and others
        (primes, powers, others) = (set(), set(), set())
        for n in irange(m, M):
          if not digits([n]): continue
          fs = list(prime_factor(n))
          if is_prime(fs):
            primes.add(n)
          elif is_power(fs):
            powers.add(n)
          else:
            others.add(n)
        
        # decompose <t> into <k> numbers in range [m, M] chosen from <ns>
        def decompose(t, k, ns, m=m, M=M, xs=[]):
          # are we done?
          if k == 1:
            if not(t < m or t > M) and t in ns:
              yield xs + [t]
          else:
            # choose the next number
            k_ = k - 1
            for n in irange(m, min(M, t - k_ * m)):
              if n in ns:
                yield from decompose(t - n, k_, ns, n + 1, M, xs + [n])
        
        # find sets of numbers that give 360
        ss = list()
        for ns in decompose(360, 3, union([primes, powers, others])):
          # find digits used
          ds = digits(ns)
          if ds:
            ss.append((ns, ds))
        
        # also allow a repeat of 111
        ns = [111, 111, 138]
        ds = digits(ns)
        if ds:
          ss.append((ns, ds))
        
        # choose two sets with no shared digits (other than 1)
        for ((ns1, ds1), (ns2, ds2)) in subsets(ss, size=2):
          if ds1.intersection(ds2): continue
          ns = sorted(ns1 + ns2)
          # check there is 1 power and 2 primes
          if not(len(powers.intersection(ns)) == 1 and len(primes.intersection(ns)) == 2): continue
          # output solution
          printf("min={ns[0]} max={ns[-1]} {ns1} + {ns2}")
        

        Like

    • Frits 10:10 pm on 16 April 2021 Permalink | Reply

      Checks for prime numbers and powers are done a limited number of times so it was not worth to calculate prime numbers and powers (for 101-159) in advance.

      from enigma import SubstitutedExpression, is_prime, unpack, mgcd, prime_factor
      
      # check a number is _not_ an exact power  (see Brain-Teaser 683)
      is_no_power = lambda n, gcd=unpack(mgcd): gcd(e for (p, e) in prime_factor(n)) == 1
      
      # main checks for sequence <s>
      def check(s):
        # only one digit is missing so we have four 1's and eight others
        s1 = "".join(str(x).zfill(2) for x in s)
        if len(set(s1)) != 9 or s1.count("1") != 4 :
          return False 
       
        # list contains two prime numbers 
        if len([x for x in s if is_prime(100 + x)] ) != 2:
          return False
       
        # list contains one power
        if len([x for x in s if is_no_power(100 + x)]) != 5:
          return False
       
        return True
      
      p = SubstitutedExpression(
        [
         # 1AB + 1CD + 1?? = 360   ?? = 60 - AB - CD
         "AB < CD",
         "CD < 60 - AB - CD",
        
         # 1GH + 1IJ + 1?? = 360   ?? = 60 - GH - IJ
         "GH < IJ",
         "IJ < 60 - GH - IJ",
        
         # limit duplicate solutions
         "AB <= GH",
        
         # main check
         "check([AB, CD, 60 - AB - CD, GH, IJ, 60 - GH - IJ])",
        ],
        answer="(100 + AB, 100 + CD, 160 - AB - CD, \
                 100 + GH, 100 + IJ, 160 - GH - IJ)",
        d2i=dict([(0, "CG")] +
                 [(2, "AG")] +
                 [(k, "ACGI") for k in range(3, 10)]),
        env=dict(check=check),
        distinct="",
      verbose=0,
      )
      
      # print answer
      for (_, ans) in p.solve():
        print(f"min={min(ans)} max={max(ans)} {ans}")
      

      Like

    • Frits 12:30 pm on 17 April 2021 Permalink | Reply

      Built for speed (hardcoded values).

      # check if sequence <s> contains different digits (except 1)
      def diffdgts(s, no1s=0):
        s1 = "".join(str(x).zfill(2) for x in s)
        s2 = s1.replace("1", "")
        if len(set(s2)) != len(s2):
          return False  
        else:
          if no1s and s1.count("1") != no1s:
              return False
          
          # F needs to contain 2 or 3 so don't allow both in A, B, C    
          if len(s) == 3 and "2" in s2 and "3" in s2: 
            return False
            
          return True
      
      # form angles into 2 groups of 3, each group summing to 360  
      for A in range(1, 18):
        # F needs to contain 2 or 3 so limit B to 19
        for B in range(max(11, A + 1), 20):
          C = 60 - A - B
          if not diffdgts([A, B, C]): continue
          
          # second group 
          for D in range(max(11, A + 1), 19): 
            for E in range(D + 1, 20):
              F = 60 - D - E
              
              s = [A, B, C, D, E, F]
              if not diffdgts(s, 4): continue
              
              # either 100 + C or 100 + F has to be a power as A, B, C and D < 20
              if len([x for x in [C, F] if x in {21, 25, 28}]) != 1: continue
              
              # list contains two prime numbers (prime numbers < 149)  
              if len([x for x in s if x in {1, 3, 7, 9, 13, 27, 31, 37, 39}] ) != 2:
                continue
           
              ans = [100 + x for x in s]
              print(f"min={min(ans)} max={max(ans)} {ans}")
      

      Like

    • Frits 1:10 am on 20 April 2021 Permalink | Reply

      Starting with 3 angles which sum to 360 and include a power.
      This list is limited and allows us to derive digits which may not be used in the other list of 3 angles.

      # (prime numbers < 149 and excluding numbers with digit 2)  
      primes = {101, 103, 107, 109, 113, 131, 137, 139}
      
      # create a list of 3 angles which sum to 360 and includes a power
      pwrs = []
      # power 121 is not allowed as it forces 119, 120, 121
      for A in [125, 128]:
        # set ranges so that C > B
        for B in range((241 - A), 100 + (161 - A) // 2):
          C = 360 - A - B
      
          # check for different digits (except 1)
          dABC = [x for n in [A, B, C] for x in [n // 10 - 10, n % 10] if x != 1]
          # the 9 digits must have exact 5 ones as B = 111 is not allowed
          if len(dABC) != 4 or len(set(dABC)) != 4: continue
      
          pwrs.append([[A, B, C], dABC])
      
      
      # if digits 3/4, 8 and 9 are used in ABC we can't make 360 with remaining
      # digits as you will have to make 10 with 0, 1, 5, 6, 7 (3/4 is for tens)
      pwrs = [[p, d] for p, d in pwrs if not ((3 in d or 4 in d) 
                                         and 8 in d and 9 in d)]
      
      # check which digits occur in all power entries
      common_dgts = [i for i in range(2, 10) if all(i in d for p, d in pwrs)]
      
      # second group without power
      for D in range(101, 115): 
        if (D % 10) in common_dgts: continue
        for E in range(max(111, D + 1), min(231 - D, 120)):
          if (E % 10) in common_dgts: continue
          F = 360 - D - E
          if (F % 10) in common_dgts: continue
      
          # check for different digits (except 1)
          dDEF = [x for n in [D, E, F] for x in [n // 10 - 10, n % 10] if x != 1]
          if len(dDEF) != 4 or len(set(dDEF)) != 4: continue
      
          # check if D, E, F complements pwrs (A, B, C)
          for p, d in pwrs:
            # skip if they have digits in common
            if any(x in d for x in dDEF): continue
      
            s = [D, E, F] + p
      
            # list contains two prime numbers 
            if len([x for x in s if x in primes]) == 2:
               print(f"{min(s)}, {max(s)} [{s}]")
      

      Like

  • Jim Randell 5:03 pm on 26 February 2021 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3049: Plantation 

    From The Sunday Times, 28th February 2021 [link]

    Jed farms a large, flat, square area of land. He has planted trees at the corners of the plot and all the way round the perimeter; they are an equal whole number of yards apart.

    The number of trees is in fact equal to the total number of acres (1 acre is 4840 square yards). If I told you an even digit in the number of trees you should be able to work out how far apart the trees are.

    How many yards are there between adjacent trees?

    It is now 60 years since the first numbered Teaser puzzle was published — Brain-Teaser 1: Tall story — on 26th February 1961.

    Congratulations to The Sunday Times!

    [teaser3049]

     
    • Jim Randell 5:22 pm on 26 February 2021 Permalink | Reply

      Here is a constructive solution.

      This Python program runs in 56ms.

      Run: [ @repl.it ]

      from collections import defaultdict
      from enigma import irange, inf, is_square, nsplit, peek, printf
      
      # generate (number-of-trees, total-area, size-of-square, distance-between-trees)
      def generate():
        # consider total number of trees (t = 4n)
        for t in irange(4, inf, step=4):
          # this is the same as the total number of acres
          # calculate the area in square yards
          a = 4840 * t
          # but the area is a square
          # and the side is a whole number of yards
          s = is_square(a)
          if s is None: continue
          # so the distance between trees is...
          (d, r) = divmod(4 * s, t)
          if d < 1: break
          if r == 0:
            printf("[t={t} a={a} s={s} d={d}]")
            yield (t, a, s, d)
      
      # collect candidate solutions by the even digits of the number of trees
      digits = {0, 2, 4, 6, 8}
      r = defaultdict(set)
      for (t, a, s, d) in generate():
        for x in digits.intersection(nsplit(t)):
          r[x].add(d)
      
      # look for digits that give a unique distance
      for (x, ds) in r.items():
        if len(ds) == 1:
          printf("digit {x} -> distance {ds} yards", ds=peek(ds))
      

      Solution: The distance between trees is 4 yards.


      Manually:

      If there are t = 4n trees around the perimeter, then we can calculate the distance d between them as:

      d = 88 √(5 / 2n)

      So:

      n⋅d² = 19360 = (2^5)(5)(11^2)

      Which gives the following (d, n) values:

      (d=1, n=19360) → t=77440
      (d=2, n=4840) → t=19360
      (d=4, n=1210) → t=4840
      (d=11, n=160) → t=640
      (d=22, n=40) → t=160
      (d=44, n=10) → t=40

      Looking at the t values we see that, of the even digits, only 8 gives a unique solution.

      Here is a Python program that uses the same approach:

      from collections import defaultdict
      from enigma import divisors_pairs, is_square, irange, nsplit, peek, printf
      
      # generate (number-of-trees, distance-between-trees)
      def generate():
        # n.d^2 = 19360
        for (n, d2) in divisors_pairs(19360, every=1):
          d = is_square(d2)
          if d is None: continue
          # return (t, d)
          t = 4 * n
          printf("[d={d} n={n} -> t={t}]")
          yield (t, d)
      
      # group candidate solutions by the even digits of the number of trees
      digits = set(irange(0, 9, step=2))
      r = defaultdict(set)
      for (t, d) in generate():
        for x in digits.intersection(nsplit(t)):
          r[x].add(d)
      
      # look for digits with a single distance
      for (x, ds) in r.items():
        if len(ds) == 1:
          printf("digit {x} -> distance {ds} yards", ds=peek(ds))
      

      Like

      • Tony Brooke-Taylor 12:57 pm on 27 February 2021 Permalink | Reply

        My solution replicates my manual approach. It is an order or magnitude quicker than yours – I think because I am being much more selective about the cases I try. Ironically it took me about ten times as long to code as it took me to solve the problem manually!

        #let the number of trees on a side be n, and the distance between trees be x yards, so the length of a side is n.x 
        
        #we are told that the total number of trees is equal to the area in acres, so
        #4n=((n.x)**2)/4840 
        
        #For integer values of n, valid values of x**2 must be made up of factors of 4*4840
        
        def factors(n):    
            j = 2
            while n > 1:
                for i in range(j, int(n**(1/2)) + 1):
                    if n % i == 0:
                        n /= i ; j = i
                        yield i
                        break
                else:
                    if n > 1:
                        yield int(n); break
        
        facs=list(factors(4*4840))
        
        #furthermore, if x is an integer, x**2 can only be made up of products of squares, meaning that we can only combine factors in multiples of two
        
        cofac=1
        mults=[]
        for fac in set(facs):
          if facs.count(fac)%2==1: cofac *= fac
          if facs.count(fac)//2>0:mults.append([fac**i for i in range(facs.count(fac)//2+1)])
        
        #mults contains the possible multiples of each valid prime factor; cofac is the product of factors that do not form part of a pair
        
        #use mults to generate all possible values for x
        x_vals=[1]
        for vec in mults:
          x_vals = [(i*j) for i in x_vals for j in vec]
        
        #each value of x generates a possible value for 4n  
        n_vals=list(zip(x_vals,[4*(x**2)*cofac for x in x_vals]))
        
        #we are now looking for the value for 4n which contains a unique instance of a given even number, so let's collect all digits in all our possible 4n's
        
        digits=[]
        for n in n_vals:
          digits=digits+([dig for dig in str(n[1])])
        
        #then find the value of 4n which contains the even digit that appears in only one value of 4n
        for ev in range(2,9,2):
          if digits.count(str(ev)) == 1:
            result_n = [n for n in n_vals if str(ev) in str(n[1])][0]
        
        print("The distance between adjacent trees is",(result_n[0]),"yards.")
        

        Like

        • Jim Randell 4:40 pm on 27 February 2021 Permalink | Reply

          @Tony: I also did some analysis which gives a fairly short manual solution (or a short program). I’ve put the code up on repl.it [link], and I’ll post the analysis later.

          Like

        • Frits 5:26 pm on 27 February 2021 Permalink | Reply

          @Tony,

          I have taken a similar approach like you (number of trees on a side is n) but I reach a different answer.

          At the Notes section of the Enigmatic Code (link in the About section) site Jim has described how you can include Python code so that it is displayed with colors.

          Like

          • Tony Brooke-Taylor 9:48 am on 28 February 2021 Permalink | Reply

            Brian has spotted my error. Thanks for the tip re: posting. Hopefully any posts I make in future will be more legible.

            Like

        • Brian Gladman 9:31 am on 28 February 2021 Permalink | Reply

          Line 38 should be:

          n_vals = list(zip(x_vals, [16 * 4840 // (x ** 2) for x in x_vals]))
          

          Like

          • Tony Brooke-Taylor 9:46 am on 28 February 2021 Permalink | Reply

            So it should, thanks.

            Like

    • Frits 4:53 pm on 27 February 2021 Permalink | Reply

      from enigma import divisors_pairs
      from math import isqrt
      
      #          n trees  
      #     x . . . . . . . x
      #  n  .               . n     T = 4 * (n - 1),  total number of trees
      #     .               .             
      #  t  .    Jed's      . t     A = (n - 1)^2 * D^2,  A = area, D = distance
      #  r  .               . r 
      #  e  .    land       . e     no acres A / 4840 = T
      #  e  .               . e   
      #  s  .               . s     so (n - 1) * D^2 = 4 * 4840 = 19360
      #     x . . . . . . . x
      #          n trees  
        
      # make a list of possible <T> and <D> values
      TD = [(4 * b, sa) if sa * sa == a else (4 * a, sb) 
            for (a, b) in divisors_pairs(19360) 
            if (sa := isqrt(a)) ** 2 == a or (sb := isqrt(b)) ** 2 == b]
      
      # check if a certain even digit occurs in only one of the <T> values
      for dgt in '02468':
        if len(q := [x[1] for x in TD if dgt in str(x[0])]) == 1:
          print(f"answer = {q[0]} yards")
      

      Like

  • Jim Randell 8:10 am on 19 January 2021 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 2771: All Saints Day 

    From The Sunday Times, 1st November 2015 [link] [link]

    I have written down three even numbers and then consistently replaced digits by letters with different letters used for different digits. In this way I get:

    ALL
    THE
    SAINTS

    In fact multiplying together the first two of these numbers gives the third.

    What number is my SAINT?

    [teaser2771]

     
    • Jim Randell 8:11 am on 19 January 2021 Permalink | Reply

      We can solve this puzzle using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in

      Run: [ @repl.it ]

      #!/usr/bin/env python -m enigma -r
      
      SubstitutedExpression
      
      # all numbers are even
      --invalid="1|3|5|7|9,LES"
      
      "ALL * THE = SAINTS"
      
      --answer="SAINT"
      

      Solution: SAINT = 69357.

      Like

    • GeoffR 10:40 am on 19 January 2021 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 0..9:A; var 0..9:L; var 0..9:T; var 0..9:H; 
      var 0..9:E; var 0..9:S; var 0..9:I; var 0..9:N; 
        
      constraint A != 0 /\ T != 0 /\ S != 0;
      constraint all_different ([A,L,T,H,E,S,I,N]);
      
      var 100..999: ALL = 100*A + 11*L;
      var 100..999: THE = 100*T + 10*H + E;
      var 100000..999999: SAINTS = 100001*S + 10000*A + 1000*I + 100*N + 10*T;
      var 10000..99999: SAINT == 10000*S + 1000*A + 100*I + 10*N + T;
      
      constraint ALL mod 2 == 0 /\ THE mod 2 == 0 /\ SAINTS mod 2 == 0;
      constraint ALL * THE == SAINTS;
      
      solve satisfy;
      
      output ["SAINT = " ++ show(SAINT)
      ++"\nSum is " ++ show(ALL) ++ " x " ++ show(THE) ++ " = " ++ show(SAINTS)];
      
      % SAINT = 69357
      % ----------
      % Sum is 988 x 702 = 693576
      % ==========
      
      
      

      Like

  • Jim Randell 10:31 pm on 23 December 2020 Permalink | Reply
    Tags: by: Andrew Skidmore   

    Teaser 3040: Moving digit 

    From The Sunday Times, 27th December 2020 [link]

    Jonny has opened a new bank account and has set up a telephone PIN. His sort code is comprised of the set of three two-figure numbers with the smallest sum which give his PIN as their product. He was surprised to find that the PIN was also the result of dividing his eight-figure account number by one of the three two-figure numbers in the sort code.

    The PIN has an unusual feature which Jonny describes as a moving digit. If the number is divided by its first digit then the number which results has the same digits in the same order except that first digit is now at the end.

    The account number does not contain the digit which moved.

    What is the account number?

    [teaser3040]

     
    • Jim Randell 10:54 pm on 23 December 2020 Permalink | Reply

      Using a similar analysis to Teaser 3031 we get:

      If the PIN is represented by leading digit a and remaining digits r (a k digit number), then:

      r = a(10^k − a) / (10a − 1)

      The PIN is an 8-digit number divided by a 2-digit number, so it must have 6 or 7 digits. But it is also the product of three 2-digit numbers, so it has at most 6 digits.

      This gives only a few candidates for the PIN (and only one “proper” candidate), which can then be checked against the remaining conditions.

      This Python 3 program runs in 43ms.

      Run: [ @repl.it ]

      from enigma import irange, div, divisors_pairs, catch, ndigits, nsplit, printf
      
      # decompose n into k 2-digit divisors
      def decompose(n, k, m=10, ds=[]):
        if k == 1:
          if 9 < n < 100 and not(n < m):
            yield ds + [n]
        else:
          for (d, r) in divisors_pairs(n):
            if d < m: continue
            if d > 99: break
            yield from decompose(r, k - 1, d, ds + [d])
      
      # consider k digit numbers for r
      k = 5
      m = 10 ** k
      # consider possible leading digits
      for a in irange(1, 9):
        r = div(a * (m - a), 10 * a - 1)
        if r is None: continue
        PIN = a * m + r
        # find the numbers in the sort code
        sc = catch(min, decompose(PIN, 3), key=sum)
        if sc is None: continue
        # find possible account numbers
        ac = list(n for n in (x * PIN for x in set(sc)) if ndigits(n) == 8 and a not in nsplit(n))
        if ac:
          # output solutions
          printf("PIN = {PIN}; sort-code = {sc}; account-number = {ac}")
      

      Solution: The account number is 31589712.

      The 2-digit numbers in the sort code are: 72, 74, 77, so the PIN is 410256.

      And we have:

      31589712 / 77 = 410256
      410256 / 4 = 102564


      If the “two-figure” numbers in the sort code, and the “eight-figure” account number are allowed to have leading zeros, then there are further solutions:

      PIN = 111; sort-code = (01, 03, 37); account-number = 00000333
      PIN = 111111; sort-code = (37, 39, 77); account-number = 08555547
      PIN = 111111; sort-code = (37, 39, 77); account-number = 04333329

      The PIN cannot have a leading zero, as we want to divide by the leading digit.

      Like

      • Frits 1:41 pm on 24 December 2020 Permalink | Reply

        @Jim, Very concise.
        I think you can limit k to 3,4,5 as PIN cannot be a 7 digit number.

        Like

        • Jim Randell 2:50 pm on 24 December 2020 Permalink | Reply

          @Frits: Yes. I’d forgotten PIN is (k + 1) digits.

          And in fact we can see that PIN can only have 6 digits (so k = 5).

          Like

    • Frits 9:58 pm on 24 December 2020 Permalink | Reply

      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [
        # smallest 8-digit number divided by biggest 2-digit number:
        # 10,000,000 // 99 = 101,010 so PIN is a 6-digit number
        #
        # PIN = AB * CD * EF = GHIJKL
        # 
        # HIJKL = G * (10^5 - G) / (10G - 1) 
        
        "AB <= CD",
        "CD <= EF",
        
        # PIN is product of three 2-digit numbers
        "AB * CD * EF = GHIJKL",
        
        # moving digit formula
        "G * (100000 - G) == HIJKL * (10 * G - 1)", 
        ],
        answer="(GHIJKL, AB + CD + EF, [GHIJKL * AB, GHIJKL * CD, GHIJKL * EF])",
        distinct="",
        d2i={0: "ACEG"},
        reorder=0,
        verbose=0)   
      
      answs = sorted([y for _, y in p.solve()])
      
      prev = ""
      for ans in answs:  
        if ans[0] != prev:      # only do once for minimal sum
          accounts = [x for x in ans[2] if str(ans[0])[0] not in str(x) 
                      and len(str(x)) == 8]
          if len(accounts) != 1: continue
          print(f"account number {accounts[0]}")
        prev = ans[0]
      

      Like

    • Frits 11:58 am on 25 December 2020 Permalink | Reply

      Framework has been taken from the generated code of the previous program.
      It can’t be run with PyPy yet (due to the walrus operator).

      # product of three 2-digit numbers can't be a 7-digit number
      #
      # smallest 8-digit number divided by biggest 2-digit number:
      # 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number
      #
      # moving digit formula (pin1 = first digit, pin2_6 = the remaining digits):
      #
      # pin1.(100000 - pin1) / (10.pin1 - 1) = pin2_6
      
      sol = []
      
      # increasing sort codes AB, CD and EF 
      for AB in range(10, 100):
        for CD in range(AB, 100):
          mi = max(CD, round(100000 / (AB * CD) + 0.5))
          for EF in range(mi, 100):
            pin = AB * CD * EF
            pin1 = pin // 100000
            pin2_6 = pin % 100000
            # moving digit formula  
            if pin1 * (100000 - pin1) == pin2_6 * (10 * pin1 - 1):
              sol.append([pin, AB + CD + EF, AB, CD, EF])
      
      prev = -1
      for s in sorted(sol):  
        if s[0] != prev:      # only do once for a minimal sum
          # account number has eight digits, none equal to the PIN's first digit
          accounts = [a for x in s[2:] if str(s[0])[0] not in (a := str(x * s[0])) 
                      and len(a) == 8]
                      
          if len(accounts) > 0:
            print(f"account number(s): {', '.join(str(x) for x in accounts)}")
        prev = s[0]
      

      Like

      • Frits 12:15 pm on 25 December 2020 Permalink | Reply

        AB could also have 11 as minimum.

        CD could also have as minimum:

        mi = max(AB, round(round(100000 / 99 + 0.5) / AB + 0.5))
        

        Like

    • GeoffR 2:10 pm on 26 December 2020 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % 6-digit PIN number
      var 100000..999999: PIN;
      
      % 8-digit Account number 
      % Search range reduced to one million to limit run-time
      var 31000000..32000000: ACCNO;
      
      var 1..9:p; var 0..9:q; var 0..9:r;  var 0..9:s; 
      var 0..9:t; var 0..9:u; var 0..9:v;  var 0..9:w; 
      
      constraint ACCNO = 10000000*p + 1000000*q + 100000*r
      + 10000*s + 1000*t + 100*u + 10*v + w;
      
      % Using others similar analysis for the moving digit
      % d = initial digit, n = remaining number and N = power
      var 1..9: d;
      var 3..6: N;
      var 10000..99999:n;
      
      constraint d * pow(10,N) + n == d * (10*n + d);
      constraint PIN = d * pow(10,N) + n;
      
      % Three two digit numbers multiplied to give the PIN
      var 47..99: N1; var 47..99: N2; var 47..99: N3;  
      constraint N1 * N2 * N3 == PIN;
      
      % Find Account Number
      constraint  ACCNO == PIN * N1 \/ ACCNO == PIN * N2 
      \/ ACCNO == PIN * N3;
      
      constraint N3 > N2 /\ N2 > N1;
      
      % Smallest sum of three 2-digit numbers
      solve minimize(N1 + N2 + N3);
      
      % The moved digit 'dig1' is not in the account number
      var 1..9: dig1;
      constraint dig1 == PIN div 100000;
      
      % Set of digits for the account number
      var set of int: s1 = {p, q, r, s, t, u, v, w};
      constraint card(s1 intersect {dig1} ) == 0;
      
      output ["PIN = " ++ show(PIN)
      ++ "\n" ++ "ACC No. = " ++ show(ACCNO)
      ++ "\nThree 2-digit numbers are  " ++ show(N1) ++ 
      ", " ++ show(N2) ++ ", " ++ show(N3) ];
      
      
      

      Like

      • Frits 1:57 pm on 27 December 2020 Permalink | Reply

        Based on GeoffR’s program. I didn’t reduce the account range to limit run-time, runs in half a second.

        Removing lines 56-58 gives the same result but is probably not a good idea in combination with the minimize function.

        % A Solution in MiniZinc
        include "globals.mzn";
        
        % Product of three 2-digit numbers can't be a 7-digit number
        %
        % Smallest 8-digit number divided by biggest 2-digit number:
        % 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number  
        var 101011..922082: PIN;                 % 97*97*98
        
        % Array of sort codes
        array[1..3] of var int: N;  
        
        % Array of possible accounts
        array[1..3, 1..8] of var int: t;  
        
        predicate toNum(array[int] of var int: a, var int: n,  int: base) =
                  let { int: len = length(a) }
                  in
                  n = sum(i in 1..len) (
                    ceil(pow(int2float(base), int2float(len-i))) * a[i]
                  )
                  /\ forall(i in 1..len) (a[i] >= 0 /\ a[i] < base)
        ; 
        
        predicate toNum10(array[int] of var 0..9: a, var int: n) = toNum(a, n, 10);
        
        % Using others similar analysis for the moving digit
        % d = initial digit, n = remaining number and N = power
        var 1..9: d;
        var 10000..99999:n;
        
        constraint d * 100000 + n == d * (10*n + d);
        constraint PIN = d * 100000 + n;
         
        % Three two digit numbers multiplied to give the PIN
        % N[1] <= 97 as 98^3 > 900,000 and 98^4 > 90,000,000, both containing a 9
        % N[2] >= 32 as 31*31*99 < 100,000
        % N[3] >= 47 as 46^3 < 100,000
        constraint N[1] > 10 /\ N[1] < 98;
        constraint N[2] > 31 /\ N[2] < 100;
        constraint N[3] > 46 /\ N[3] < 100;
         
        % Increasing 
        constraint N[3] > N[2] /\ N[2] > N[1];
        
        constraint N[1] * N[2] * N[3] == PIN;
        
        % Smallest sum of three 2-digit numbers
        solve minimize(sum(N));
         
        % The moved digit 'd' is not in the account number
        constraint toNum10(row(t, 1), PIN * N[1]) /\ PIN * N[1] > 9999999;
        constraint toNum10(row(t, 2), PIN * N[2]) /\ PIN * N[2] > 9999999;
        constraint toNum10(row(t, 3), PIN * N[3]) /\ PIN * N[3] > 9999999;
        
        constraint forall( [row(t, 1)[i] != d | i in 1..8] ) \/ 
                   forall( [row(t, 2)[i] != d | i in 1..8] ) \/ 
                   forall( [row(t, 3)[i] != d | i in 1..8] ); 
                   
        output ["PIN = " ++ show(PIN)];
        output ["\nACC No. = " ++ show(N[j] * PIN) ++ " " | j in 1..3 where fix(forall( [row(t, j)[i] != d | i in 1..8]))];
        output ["\nThree 2-digit numbers are  " ++ show(N)];
        output["\nSum = " ++ show(sum(N))];
        

        Like

        • Frits 3:10 pm on 27 December 2020 Permalink | Reply

          A bit easier with div and mod.

          % A Solution in MiniZinc
          include "globals.mzn";
          
          % Product of three 2-digit numbers can't be a 7-digit number
          %
          % Smallest 8-digit number divided by biggest 2-digit number:
          % 10,000,000 // 99 = 101,010 so PIN has to be a 6-digit number  
          var 100000..999999: PIN;             
               
          % Array of sort codes
          array[1..3] of var int: N;  
          
          % Array of possible accounts
          array[1..3, 1..8] of var int: t;  
          
          % Using others similar analysis for the moving digit
          % d = initial digit, n = remaining number and N = power
          var 1..9: d;
          var 10000..99999:n;
          
          constraint d * 100000 + n == d * (10*n + d);
          constraint PIN = d * 100000 + n;
           
          % Three two digit numbers multiplied to give the PIN
          % N[1] <= 97 as 98^3 > 900,000 and 98^4 > 90,000,000, both containing a 9
          % N[2] >= 32 as 31*31*99 < 100,000
          % N[3] >= 47 as 46^3 < 100,000
          constraint N[1] > 10 /\ N[1] < 98;
          constraint N[2] > 31 /\ N[2] < 100;
          constraint N[3] > 46 /\ N[3] < 100;
           
          % Increasing 
          constraint N[3] > N[2] /\ N[2] > N[1];
          
          constraint N[1] * N[2] * N[3] == PIN;
          
          % Smallest sum of three 2-digit numbers
          solve minimize(sum(N));
           
          % The moved digit 'd' is not in the account number
          constraint forall( [(PIN * N[1] div pow(10,i-1) mod 10) != d | i in 1..8] ) \/ 
                     forall( [(PIN * N[2] div pow(10,i-1) mod 10) != d | i in 1..8] ) \/ 
                     forall( [(PIN * N[3] div pow(10,i-1) mod 10) != d | i in 1..8] ); 
          
          % Account consists of 8 digits          
          constraint forall( [PIN * N[i] > 9999999 | i in 1..3] );          
                     
          output ["PIN = " ++ show(PIN)];
          output ["\nACC No. = " ++ show(N[j] * PIN) ++ " " | j in 1..3 
                  where fix(forall( [(PIN * N[j] div pow(10,i-1) mod 10) != d 
                  | i in 1..8]))];
          output ["\nThree 2-digit numbers are  " ++ show(N)];
          output["\nSum = " ++ show(sum(N))];
          

          Like

    • GeoffR 7:35 pm on 27 December 2020 Permalink | Reply

      @Frits:
      On running your latest two MiniZinc postings, I found that they both give three solutions as output.

      From my own experience in MinZinc, I also know this is possible and the correct solution can easily be found as one of the output solutions. However, for this teaser, my code produced a single solution. Maybe, with some minor amendment, this also might be possible for your code, but I am not sure why our outputs vary.

      I also try to generally try to make most of my code visible in the available posting space. However, I have not found any guidance/ recommendations on this matter and opinions vary. I did achieve this aim for my MiniZinc posting, but it gets increasingly difficult to achieve when page widths for posting decrease with replies to postings.

      I noticed there was quite a lot of your output code hidden from the available posting window on your first posting after my posting. I reformatted this last section of code to show that some simple adjustments to code can keep code readable in the window – please don’t mind me doing this as I am just making a comment.

      % Frits part teaser code only - formatting comment
        
      % The moved digit 'd' is not in the account number
      constraint toNum10(row(t, 1), PIN * N[1])
      /\ PIN * N[1] > 9999999;
      
      constraint toNum10(row(t, 2), PIN * N[2]) 
      /\ PIN * N[2] > 9999999;
      
      constraint toNum10(row(t, 3), PIN * N[3]) 
      /\ PIN * N[3] > 9999999;
       
      constraint forall( [row(t, 1)[i] != d | i in 1..8] ) 
      \/ forall( [row(t, 2)[i] != d | i in 1..8] ) 
      \/ forall( [row(t, 3)[i] != d | i in 1..8] ); 
                  
      output ["PIN = " ++ show(PIN)];
      output ["\nACC No. = " ++ show(N[j] * PIN) 
      ++ " " | j in 1..3 
      where fix(forall( [row(t, j)[i] != d | i in 1..8]))];
      output ["\nThree 2-digit numbers are  " ++ show(N)];
      output["\nSum = " ++ show(sum(N))];
      
      
      

      @Jim: Any comments about maximising available windows for posting code?

      Like

      • Jim Randell 7:24 pm on 31 December 2020 Permalink | Reply

        When running MiniZinc on a model with a maximise()/minimise() target you only expect to get one answer, but I think some solvers will output “best so far” solutions as they work if the “all solutions” parameter is selected.

        Replies on the site are indented, so there is less horizontal space. I like replies, rather than making new comment threads, but this is an issue for code. Unfortunately there doesn’t seem to be a documented option to allow code blocks to wrap long lines. (Although there is a [[ collapse="true" ]] option which means you have to click on it to view the code, which might be useful for long programs).

        Personally I’m not bothered that much by horizontal scrolling (I prefer it to lots of wrapped lines). If I really want to look at (or run) a program I will copy it into an editor.

        Like

    • GeoffR 8:22 am on 28 December 2020 Permalink | Reply

      @Frits:
      Looking at the three solutions in the output, the first two solutions are not the minimum sum of the three two-digit numbers (224 and 225). The third solution is the answer and has a minimum sum of 223. Should have seen that earlier!

      Like

      • Frits 10:36 am on 28 December 2020 Permalink | Reply

        @GeoffR, Yes, per default Minizinc will print intermediate solutions. In the configuration editor you have to use “user-defined behavior”.

        I normally try to keep code within lines of 80 bytes. I will not correct for indentations within WordPress itself.

        In your program “d” and “dig1” always seem to be the same as you have fixed PIN to 6 digits. Also N always have to be 5 in that case.

        Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
%d bloggers like this: