Design a site like this with WordPress.com
Get started

Tagged: by: Graham Smithers Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 10:42 am on 6 December 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2690: Leaving present 

    From The Sunday Times, 13th April 2014 [link]

    When maths teacher Adam Up reached the age of 65, he asked his colleagues for some spring bulbs as a leaving present. So they gave him some packs of bulbs with, appropriately enough, each pack containing 65 bulbs.

    Adam planted all the bulbs in clumps of different sizes, the number of bulbs in each clump being a prime number. Furthermore, these prime numbers overall used each of the ten digits exactly once. Had he been given any fewer packs this would have been impossible.

    How many bulbs were there in the smallest and largest clumps?

    [teaser2690]

     
    • Jim Randell 10:42 am on 6 December 2022 Permalink | Reply

      I implemented a multiset exact cover algorithm [[ mcover() ]] when I revisited Enigma 1712. And the same function can be used to solve this puzzle.

      As we are looking for the smallest number of packs we can start by considering primes up to 65, to see if the problem can be solved using a single pack, and if not we can then add primes between 66 and 130 into the mix, and so on until we find a number of packs that provides solutions.

      The following Python program runs in 56ms. (Internal run time is 3.7ms).

      Run: [ @replit ]

      from enigma import (irange, primes, inf, nsplit, multiset, mcover, printf)
      
      # incremental multiple
      N = 65
      
      # target digit contents (each digit once)
      tgt = multiset.from_seq(irange(0, 9), count=1)
      
      # start with 0 multiples
      k = 0
      m = dict()  # map primes to digit content
      for p in primes.irange(2, inf):
        # have we finished a chunk?
        k_ = p // N
        if k_ > k:
          k = k_
          kN = k * N
          # look for covers using this collection of primes
          n = 0
          for ss in mcover(m, tgt, (lambda ss: sum(ss) > kN)):
            # check for required sum
            if sum(ss) == kN:
              # output solution
              printf("{ss} -> {k} * {N}", ss=sorted(ss))
              n += 1
          # are we done?
          if n > 0:
            printf("[{n} solutions]")
            break
      
        # add primes that are subsets of the target into the list
        ds = multiset.from_seq(nsplit(p))
        if ds.issubset(tgt):
          m[p] = ds
      

      Solution: The smallest clump had 5 bulbs. The largest clump had 401 bulbs.

      There are 2 ways to achieve the solution with 9 packs of 65 bulbs (= 585 bulbs in total):

      5 + 29 + 67 + 83 + 401 = 585
      5 + 23 + 67 + 89 + 401 = 585

      Like

    • GeoffR 7:02 pm on 6 December 2022 Permalink | Reply

      The only way I could find a solution in MiniZinc was to assume the ten digit pattern of the primes i.e. 1,2,2,2,3. There has to be at least one 3-digit prime with zero as the middle digit.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % Using a 1,2,2,2,3 digit prime pattern
      
      var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D;
      var 1..9:E; var 1..9:F; var 1..9:G; var 1..9:H;
      var 0..9:I; var 1..9:J;
      
      var 10..99:BC = 10*B + C;
      var 10..99:DE = 10*D + E;
      var 10..99:FG = 10*F + G;
      var 100..999:HIJ = 100*H + 10*I + J;
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x)))))
      ((i < x) -> (x mod i > 0));
      
      constraint sum([is_prime(A), is_prime(BC), is_prime(DE), 
      is_prime(FG), is_prime(HIJ)]) == 5;
      
      constraint card( {A,B,C,D,E,F,G,H,I,J}) == 10;
      % There are 65 bulbs in each pack
      constraint (A + BC + DE + FG + HIJ) mod 65 == 0;
      
      constraint increasing([A,BC,DE,FG,HIJ]);
      
      solve satisfy;
      
      output ["Smallest clump = " ++ show(A) ++ 
      " , Largest clump = " ++ show(HIJ) ++
      "\n" ++ "[A,BC,DE,FG,HIJ] = " ++ show([A,BC,DE,FG,HIJ] )];
      
      % Smallest clump = 5 , Largest clump = 401
      % [A,BC,DE,FG,HIJ] = [5, 29, 67, 83, 401]
      % ----------
      % Smallest clump = 5 , Largest clump = 401
      % [A,BC,DE,FG,HIJ] = [5, 23, 67, 89, 401]
      % ----------
      % ==========
      
      
      

      Out of interest I then adapted the program to check a different prime digit pattern, which was 2,2,3,3 for the ten digits. All the answers used 18 packs of 65 bulbs, exactly double the original solution using 9 packs of 65 bulbs = 585

      % [AB,CD,EFG,HIJ] for different 10-digits pattern
      % [AB,CD,EFG,HIJ] = [43, 61, 257, 809]
      % [AB,CD,EFG,HIJ] = [53, 89, 421, 607]
      % [AB,CD,EFG,HIJ] = [59, 83, 421, 607]
      % [AB,CD,EFG,HIJ] = [53, 67, 241, 809]
      % [AB,CD,EFG,HIJ] = [43, 67, 251, 809]
      % [AB,CD,EFG,HIJ] = [29, 83, 457, 601]
      % [AB,CD,EFG,HIJ] = [23, 89, 457, 601]
      % [AB,CD,EFG,HIJ] = [29, 53, 487, 601]
      % [AB,CD,EFG,HIJ] = [23, 59, 487, 601]
      
      
      

      Like

  • Jim Randell 9:13 am on 25 October 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2698: Pond plants 

    From The Sunday Times, 8th June 2014 [link]

    John bought some packs of pond plants consisting of oxygenating plants in packs of eight, floating plants in packs of four and lilies in packs of two, with each pack having the same price. He ended up with the same number of plants of each type. Then he sold some of these packs for twenty-five per cent more than they cost him. He was left with just fifty plants (with fewer lilies than any other) and he had recouped his outlay exactly.

    How many of these fifty plants were lilies?

    [teaser2698]

     
    • Jim Randell 9:14 am on 25 October 2022 Permalink | Reply

      If John ends up with L packs of lilies, F packs of floating plants and X packs of oxygenating plants, then we have:

      2L + 4F + 8X = 50

      And if he started out by buying a total of N packs, and selling some (at 25% markup) to cover the cost of the initial purchase, then we have:

      (5/4)(N − (X + F + L)) = N
      N = 5(X + F + L)

      And if he initially purchased n plants of each type we have:

      N = n/8 + n/4 + n/2 = (7/8)n

      This Python program runs in 56ms. (Internal runtime is 210µs).

      Run: [ @replit ]

      from enigma import (express, div, printf)
      
      # consider the make up of the 50 remaining plants
      # L = lily packs, F = floating packs; X = oxygenating packs
      # 2L + 4F + 8X = 50
      for (L, F, X) in express(50, (2, 4, 8)):
        # there are fewer lilies than any other type of plant
        if not (2 * L < min(4 * F, 8 * X)): continue
        # calculate the initial number of packs bought
        N = 5 * (L + F + X)
        # calculate the initial number of plants of each type bought
        n = div(8 * N, 7)
        if n is None: continue
        # output solution (final number of lily plants)
        printf("{x} lily plants [L={L} F={F} X={X} -> N={N} n={n}]", x=2 * L)
      

      Solution: 14 of the remaining 50 plants were lilies.

      Initially John bought 80 of each type of plant (240 plants in total) = 10 packs of oxygenators + 20 packs of floating plants + 40 packs of lilies.

      Of these 70 packs he sold 8 packs of oxygenators + 15 packs of floating plants + 33 packs of lilies. Leaving him with 14 packs.

      The sale of these 56 packs at a 25% markup exactly met the initial cost of the 70 packs.

      Leaving John with 2 packs of oxygenators (= 16 plants) + 5 packs of floating plants (= 20 plants) + 7 packs of lilies (= 14 plants). A total of 50 plants.

      Like

  • Jim Randell 8:46 am on 11 October 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2676: New diary 

    From The Sunday Times, 5th January 2014 [link]

    My diary has this design on the cover:

    In this 2-by-3 grid there are 12 junctions (including the corners), some pairs of which are joined by a straight line in the grid. In fact there are 30 such pairs.

    The diary publisher has been using such grids of various sizes for years and the 1998 diary was special because its grid had precisely 1998 pairs of junctions joined by lines. Within the next 10 years they will once again be able to produce a special diary where the number of joined pairs equals the year.

    (a) What was the grid size on the 1998 diary?
    (b) What is the year of this next special diary?

    [teaser2676]

     
    • Jim Randell 8:47 am on 11 October 2022 Permalink | Reply

      In an x by y grid each horizontal line (of length x) has:

      1 pair that are distance x apart
      2 pairs that are distance (x − 1) apart
      3 pairs that are distance (x − 2) apart

      x pairs that are distance 1 apart

      Giving a total of tri(x) pairs on that line, and there are (y + 1) horizontal lines.

      So the total number of horizontal pairs is:

      h(x, y) = (y + 1) tri(x)

      Similarly the total number of vertical pairs is:

      v(x, y) = (x + 1) tri(y)

      And so the total number of pairs is:

      pairs(x, y) = h(x, y) + v(x, y)
      pairs(x, y) = (y + 1)x(x + 1)/2 + (x + 1)y(y + 1)
      pairs(x, y) = (x + 1)(y + 1)(x + y)/2

      This Python program runs in 54ms. (Internal runtime is 488µs).

      Run: [ @replit ]

      from enigma import (irange, inf, div, decompose, printf)
      
      # count pairs on an x by y grid
      pairs = lambda x, y: div((x + 1) * (y + 1) * (x + y), 2)
      
      # check the 3x2 grid gives 30 pairs
      assert pairs(3, 2) == 30
      
      # generate (x, y, pairs(x, y)) values
      def generate():
        # consider increasing x + y values
        for t in irange(2, inf):
          for (x, y) in decompose(t, 2, increasing=1, sep=0, min_v=1):
            yield (x, y, pairs(x, y))
      
      # find the answers
      a = b = 0
      for (x, y, n) in generate():
        # (a) look for grids with 1998 pairs
        if n == 1998:
          printf("(a) {x} x {y} -> {n}")
          a = 1
        # (b) looks for grid in the range [2015, 2024]
        if 2014 < n < 2025:
          printf("(b) {x} x {y} -> {n}")
          b = 1
        # are we done?
        if a and b: break
      

      Solution: (a) The 1998 diary had a 2 × 35 grid; (b) The next special diary is for 2016.

      We have:

      1998 = pairs(2, 35)
      2016 = pairs(5, 23) = pairs(11, 13)


      Alternatively we can start with the required number of pairs n and produce possible (x, y) grids, by considering the divisors of n.

      Which gives us a shorter program.

      This Python program runs in 56ms. (Internal runtime is 622µs).

      Run: [ @replit ]

      from enigma import (divisors_pairs, irange, printf)
      
      def solve(n):
        for (a, b) in divisors_pairs(2 * n):
          for (x, y) in divisors_pairs(b - a - 1):
            if x + y == a:
              yield (x, y)
      
      # years to investigate
      qs = {
        'a': [1998],
        'b': irange(2015, 2024),
      }
      
      # solve the puzzle
      for k in sorted(qs.keys()):
        for n in qs[k]:
          for (x, y) in solve(n):
            printf("({k}) {x} x {y} -> {n}")
      

      Like

    • Hugh Casement 3:18 pm on 11 October 2022 Permalink | Reply

      Of course 2016 is in the past for us, and the next will be 2025:
      1 × 44 or 4 × 26 or 8 × 17.

      However, I maintain that those are the sizes of the arrays of square cells;
      the grids (of lines) are 2 × 45, 5 × 27, and 9 × 18.

      Like

  • Jim Randell 7:56 am on 6 October 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2750: Granny’s birthdays 

    From The Sunday Times, 7th June 2015 [link] [link]

    At Granny’s birthday this year she was telling us some surprising things about some past birthdays. She told us that each year she writes down the date of her birthday (in the eight-digit form dd/mm/yyyy) and her age in years.

    On two occasions in her lifetime it has turned out that this has involved writing each of the digits 0 to 9 exactly once. The first of these occasions was in 1974.

    What is Granny’s date of birth (in the eight-digit form)?

    Note that in order to solve this puzzle it is important to be aware of the date it was originally set.

    All 200 puzzles included in the book The Sunday Times Brain Teasers Book 1 (2019) are now available on S2T2.

    [teaser2750]

     
    • Jim Randell 8:00 am on 6 October 2022 Permalink | Reply

      The puzzle was originally set on 7th June 2015, and mentions Granny’s birthday “this year” as having already happened. So her birthday must be earlier in the year than 7th June.

      This Python program considers dates in 1974 up to 6th June, if the date includes 8 different digits, then the remaining 2 digits indicate Granny’s age (in some order), and we can then look for other years.

      The program runs in 59ms. (Internal runtime is 4.3ms)

      Run: [ @replit ]

      from datetime import (date, timedelta)
      from enigma import (irange, repeat, nsplit, union, subsets, nconcat, printf)
      
      digits = set(irange(0, 9))
      
      # consider dates earlier than this
      end = date(1974, 6, 7)
      
      # consider dates in 1974
      inc = lambda x, i=timedelta(days=1): x + i
      for d in repeat(inc, date(1974, 1, 1)):
        if not (d < end): break
        # remaining digits
        ds4 = union([nsplit(d.month, 2), nsplit(d.day, 2)])
        ds = digits.difference(nsplit(d.year, 4), ds4)
        if len(ds) != 2: continue
        # construct possible ages
        for ss in subsets(ds, size=2, select='P'):
          age = nconcat(ss)
          year = 1974 - age
          # collect "special" years
          years = list()
          for bd in irange(10, 99):
            y = year + bd
            if y > 2015: break
            if not digits.difference(nsplit(y, 4), ds4, nsplit(bd, 2)):
              years.append(y)
          if len(years) == 2 and years[0] == 1974:
            # output solution
            printf("{d} -> {years}", d=date(year, d.month, d.day).strftime("%d/%m/%Y"))
      

      Solution: Granny’s date of birth is: 26/05/1936.

      So Granny is 38 in 1974 → (26/05/1974, 38).

      And she is 47 in 1983 → (26/05/1983, 47).

      In 2015 (when the puzzle was set) she was 79.

      If we consider all dates in 1974 then there is a further solution of: 25/06/1936.

      So, the puzzle only has a unique solution if posed between 27th May and 24th June. A fact that was not mentioned when the puzzle was included in the book The Sunday Times Brain Teasers 1 (2019).

      Like

  • Jim Randell 9:23 am on 1 September 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2732: Prime meat 

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

    Mark has recently converted from vegetarianism. John sent him a coded message consisting of a list of prime numbers. Mark found that by systematically replacing each digit by a letter the list became the message:

    EAT BEEF AT TIMES
    IT IS A PRIME MEAT

    What number became PRIME?

    [teaser2732]

     
    • Jim Randell 9:29 am on 1 September 2022 Permalink | Reply

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

      The following Python program executes in 58ms. (Internal runtime of the generated program is 1.8ms).

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, sprintf)
      
      words = "EAT BEEF AT TIMES IT IS A PRIME MEAT"
      
      SubstitutedExpression(
        list(sprintf("is_prime({w})") for w in words.split()),
        answer="PRIME",
        template=words,
      ).run()
      

      Solution: PRIME = 80429.

      Like

    • GeoffR 11:53 am on 1 September 2022 Permalink | Reply

      This solution gets the answer, but is a bit slow – approx 1.5 sec.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      var 0..9:E; var 0..9:A; var 0..9:T; var 0..9:B;
      var 0..9:F; var 0..9:I; var 0..9:M; var 0..9:S;
      var 0..9:P; var 0..9:R;
      
      constraint E > 0 /\ B > 0 /\I > 0 /\ P > 0
      /\ T > 0 /\ A > 0 /\ M > 0;
      
      constraint all_different ([E, A, T, B, F, I, M, S, P, R]);
      
      var 100..999:EAT = 100*E + 10*A + T;
      var 1000..9999:BEEF = 1000*B + 110*E + F;
      var 10..99:AT = 10*A + T;
      var 10..99:IS = 10*I + S;
      var 10..99:IT = 10*I + T;
      var 10000..99999:TIMES = 10000*T + 1000*I + 100*M + 10*E + S;
      var 10000..99999:PRIME = 10000*P + 1000*R + 100*I + 10*M + E;
      var 1000..9999:MEAT = 1000*M + 100*E + 10*A + T;
      
      constraint sum([is_prime(A), is_prime(EAT), is_prime(BEEF),
      is_prime(AT), is_prime(TIMES), is_prime(IT), is_prime(IS),
      is_prime(PRIME), is_prime(MEAT)]) == 9;
      
      solve satisfy;
      output ["PRIME = " ++ show(PRIME) ++
      "\n" ++ "[E, A, T, B, F, I, M, S, P, R] = " 
      ++ show( [E, A, T, B, F, I, M, S, P, R] ) ];
      
      % PRIME = 80429
      % ----------
      %  E, A, T, B, F, I, M, S, P, R] = 
      % [9, 5, 3, 6, 1, 4, 2, 7, 8, 0]
      % ==========
      

      Like

    • GeoffR 1:56 pm on 1 September 2022 Permalink | Reply

      from itertools import permutations
      from enigma import is_prime
      
      for p1 in permutations('1234567890', 5):
          A, E, I, T, S = p1
          if '0' in (A, E, I, T):continue
          if not(is_prime(int(A))):continue
          AT = int(A + T)
          if not (is_prime(AT)):continue
          IS = int(I + S)
          if not (is_prime(IS)):continue
          IT = int(I + T)
          if not (is_prime(IT)):continue
          EAT = int(E + A + T)
          if not (is_prime(EAT)):continue
          q = set('1234567890').difference([A, E, I, T, S])
          for p2 in permutations(q):
              B, F, M, P, R = p2
              if '0' in (B, M, P):continue
              BEEF = int(B + E + E + F)
              if not (is_prime(BEEF)):continue
              TIMES = int(T + I + M + E + S)
              if not (is_prime(TIMES)):continue
              MEAT = int(M + E + A + T)
              if not (is_prime(MEAT)):continue
              PRIME = int( P + R + I + M + E)
              if is_prime(PRIME):
                  print(f"PRIME = {PRIME}")
      
      # PRIME = 80429
      
      
      
      

      Like

  • Jim Randell 8:26 am on 4 August 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2725: Darts match 

    From The Sunday Times, 14th December 2014 [link] [link]

    Andrew, Alexander, Austin, Anthony, Benjamin, Charles, Christopher, Elijah, Jacob, Jayden, Jackson, James, Jason, Mason, Michael, Nathan, Newman, Robert, Samuel and William entered a darts competition, arranged into five teams of four players. It turned out that, for any pair of members of any team, there were just two letters of the alphabet that occurred (once or more) in both their names. The names in each team were arranged alphabetically, the first name being the captain and the last name the reserve. Then the teams were numbered 1 to 5 in alphabetical order of the captains.

    In the order 1 to 5, who were the reserves?

    [teaser2725]

     
    • Jim Randell 8:27 am on 4 August 2022 Permalink | Reply

      This puzzle is slightly different from the usual kind of grouping puzzle, but we can still use some of the [[ grouping ]] functions from the enigma.py library.

      This Python program runs in 57ms. (Internal runtime is 1.4ms).

      Run: [ @replit ]

      from enigma import (grouping, join, printf)
      
      # available players
      names = [
        'Andrew', 'Alexander', 'Austin', 'Anthony', 'Benjamin', 'Charles',
        'Christopher', 'Elijah', 'Jacob', 'Jayden', 'Jackson', 'James', 'Jason',
        'Mason', 'Michael', 'Nathan', 'Newman', 'Robert', 'Samuel', 'William',
      ]
      
      # grouping function
      fn = grouping.share_letters(2)
      
      # form the names <ns> into teams of size <k>
      def teams(ns, k, ts=[]):
        # are we done?
        if not ns:
          yield ts
        else:
          # find the next captain
          cap = min(ns)
          # and 3 team members
          for team in grouping.gang(k - 1, cap, ns.difference([cap]), fn):
            team = [cap] + sorted(team)
            # solve for the remaining names
            yield from teams(ns.difference(team), k, ts + [team])
      
      for ts in teams(set(names), 4):
        for (i, team) in enumerate(ts, start=1):
          printf("Team {i}: {team}", team=join(team, sep=", "))
        printf()
      

      Solution: The reserves are (Team 1-5): William, Samuel, Robert, Newman, Michael.

      The full teams are:

      Team 1: Alexander, Austin, James, William
      Team 2: Andrew, Christopher, Jason, Samuel
      Team 3: Anthony, Benjamin, Charles, Robert
      Team 4: Elijah, Jackson, Nathan, Newman
      Team 5: Jacob, Jayden, Mason, Michael

      Like

    • Frits 8:04 pm on 5 August 2022 Permalink | Reply

      A lot more work but already solved before recursion (ie parameter teams will have 5 teams) .

         
      from itertools import combinations
      
      # check that each string shares exactly <k> letters
      shr_lttrs = lambda s1, s2, k: len(set(s1.lower()) & set(s2.lower())) == k
      
      # form the names <ns> into teams of size <k>
      def form_teams(ns, k, ts=[]):
        # are we done?
        if not ns:
          yield ts
        else:
          # find the name with the least matches
          key = min({k: v for k, v in d.items() if k in ns}.items(), 
                     key=lambda x: len(x[1]))
          # and 3 team members
          for rest in combinations([x for x in key[1] if x in ns], 3):
            # these 3 names should have exactly 2 letters in common
            if any(not y in d[x] for x, y in zip(rest, rest[1:])): continue
            
            team = sorted((key[0], ) + rest)
            # solve for the remaining names
            yield from form_teams(ns.difference(team), k, ts + [team])
            
      
      # available players
      vs = [
        'Andrew', 'Alexander', 'Austin', 'Anthony', 'Benjamin', 'Charles',
        'Christopher', 'Elijah', 'Jacob', 'Jayden', 'Jackson', 'James', 'Jason',
        'Mason', 'Michael', 'Nathan', 'Newman', 'Robert', 'Samuel', 'William',
      ]
      
      vs = sorted(vs)
      
      # create dictionary: name --> matches
      d = {vs[i]: {x for j, x in enumerate(vs[:i] + vs[i + 1:]) 
                       if shr_lttrs(vs[i], x, 2)} for i in range(len(vs))}
      
      teams = []
      dsize = -1
      # process until no more changes to dictionary
      while dsize != sum(len(v) for v in d.values()):
        dsize = sum(len(v) for v in d.values())
        
        # if a match doesn't share exactly 2 letters with at least 2 other matches
        # it can be removed from the dictionary as we we need 4 members in a team
        d = {k: {x for x in v if sum(x != y and y in d[x] for y in v) > 1} 
                 for k, v in d.items()}
       
        # if only three matches left we have finalized a team 
        match3 = [x for k, v in list(d.items()) 
                  for x in [k] + list(v) if len(v) == 3]
        
        # add these persons to teams (removing duplicates while preserving order)
        teams += list(dict.fromkeys(match3))
       
        # maintain dictionary for persons in teams
        d = {k: [x for x in v if x not in teams] 
                 for k, v in d.items() if k not in teams}
               
      # reduce values for persons in teams
      vs = [x for x in vs if x not in teams]
      
      # solve for remaining people
      for ts in form_teams(set(vs), 4):
        i = 0
        for (i, team) in enumerate(ts, start=1):
          print(f"Team {i}: {', '.join(team)}")
        for j in range(len(teams) // 4):
          i += 1
          print(f"Team {i}: {', '.join(sorted(teams[j * 4:j * 4 + 4]))}")
        print()
      

      Like

  • Jim Randell 12:33 pm on 17 July 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2531 

    From The Sunday Times, 27th March 2011 [link] [link]

    A Harshad number (or H-number) is any number that is divisible by the sum of its digits. Using each non-zero digit just the once, I have written down a 9-figure H-number. Reading from left to right, it also consists of three 2-figure H-numbers followed by a 3-figure H-number. Again working from left to right through the 9-figure number, the last five digits form a 5-figure H-number. Reversing the order of the first five digits of the 9-figure number also gives a 5-figure H-number.

    What is the 9-figure number?

    [teaser2531]

     
    • Jim Randell 12:34 pm on 17 July 2022 Permalink | Reply

      See: [@wikipedia].

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

      The following run file executes in 72ms. The internal runtime of the generated program is 3.1ms).

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      --digits="1-9"
      
      # is <n> an H-number?
      --code="H = lambda n: n % dsum(n) == 0"
      
      # the 9-digit number is: abcdefghi
      "H({abcdefghi})"
      
      # three 2-digit H-numbers and a 3-digit H-number
      "H({ab})"
      "H({cd})"
      "H({ef})"
      "H({ghi})"
      
      # 5-digit H-numbers
      "H({efghi})"
      "H({edcba})"
      
      --answer="{abcdefghi}"
      

      Solution: The 9-digit number is: 273684915.

      Like

    • GeoffR 2:16 pm on 17 July 2022 Permalink | Reply

      
      % A Solution in MiniZinc 
      include "globals.mzn";
      
      var 1..9: a; var 1..9: b; var 1..9: c;
      var 1..9: d; var 1..9: e; var 1..9: f;
      var 1..9: g; var 1..9: h; var 1..9: i;
      
      constraint all_different([a,b,c,d,e,f,g,h,i]);
      
      % 2-digit Harshad numbers
      constraint (10*a + b) mod (a + b) == 0
      /\ (10*c + d) mod (c + d) == 0
      /\ (10*e + f) mod (e + f) == 0;
      
      % 3-digit Harshad number
      constraint (100*g + 10*h + i) mod (g + h + i) == 0;
      
      % 5-digit Harshad numbers
      constraint (10000*e + 1000*f + 100*g + 10*h + i) mod(e + f + g + h + i) == 0;
      constraint (10000*e + 1000*d + 100*c + 10*b + a) mod(e + d + c + b + a) == 0;
      
      % 9-digit Harshad number
      constraint (a * pow(10,8) + b * pow(10,7) + c * pow(10,6)
      + d * pow(10,5) + e * pow(10,4) + f * pow(10,3)
      + g * pow(10,2) + h * 10 + i) mod (a+b+c+d+e+f+g+h+i) == 0;
      
      solve satisfy;
      
      output ["9-figure number = " ++ " \(a)\(b)\(c)\(d)\(e)\(f)\(g)\(h)\(i)" ];
      
      % 9-figure number = 273684915
      % ----------
      % ==========
      
      

      Like

    • Frits 3:40 pm on 17 July 2022 Permalink | Reply

         
      from itertools import permutations
      from functools import reduce
      
      # convert digits sequence to number
      d2n = lambda s: reduce(lambda x, y: 10 * x + y, s)
      
      # calculate H-number
      H = lambda s: d2n(s) % sum(s) == 0
      
      i = 5  # as abcdefghi is divisible by 45
      
      # ghi:   sum(g,h) must be even as sum(g,h,i) must be odd
      # efghi: sum(e,f) must be even as sum(e,f,g,h,i) must be odd
      # ef:    e and f not both odd otherwise 10*d + e is not divisible by e + f
      #        so e and f are both even
      # ab:    a and b not both odd
      # cd:    c and d not both odd
      # g an h must be both odd otherwise a, b, c and d must all be odd
      
      # ....eeoo5
      # edcba : a must be even as sum(e,d,c,b,a) is even
      # e...eeoo5
      # as c and d are not both odd b must be odd
      # eo..eeoo5
      
      for (b, g, h) in permutations([1, 3, 7, 9], 3):
        if not H((g, h, i)): continue
        for (a, e, f) in permutations([2, 4, 6, 8], 3):
          if not H((a, b)): continue
          if not H((e, f)): continue
          if not H((e, f, g, h, i)): continue
          rest = set(range(1, 10)).difference({a, b, e, f, g, h, i})
          for (c, d) in permutations(rest):
            if not H((c, d)): continue
            if not H((e, d, c, b, a)): continue
            if not H((a, b, c, d, e, f, g, h, i)): continue
            print("the 9-figure number:", d2n((a, b, c, d, e, f, g, h, i)))
      

      Like

    • GeoffR 6:43 pm on 17 July 2022 Permalink | Reply

      I carried out some further analysis to see how the number of Harshad numbers reduced with different arrangements of numbers.

      1) For numbers ab, cd, ef, ghi and abcdefghi, this gave 96 possible 9-digit Harshad numbers.

      2) Adding abcde to (1) above, I found 16 possible Harshad numbers for abcdefghi:

       a b c d e f g h i    a b c d e f g h i    a b c d e f g h i
      ------------------------------------------------------------
       2 7 3 6 4 8 1 9 5,   2 7 3 6 8 4 9 1 5,   2 7 6 3 4 8 1 9 5,   
       2 7 6 3 8 4 9 1 5,   3 6 2 7 4 8 1 9 5,   3 6 2 7 8 4 9 1 5,   
       3 6 7 2 4 8 1 9 5,   3 6 7 2 8 4 9 1 5,   6 3 2 7 4 8 1 9 5,   
       6 3 2 7 8 4 9 1 5,   6 3 7 2 4 8 1 9 5,   6 3 7 2 8 4 9 1 5,   
       7 2 3 6 4 8 1 9 5,   7 2 3 6 8 4 9 1 5,   7 2 6 3 4 8 1 9 5,   
       7 2 6 3 8 4 9 1 5.
      

      3) Finally, adding number edcba to (2) above, this gave the single 9-digit answer of 273684915.
      (top row, middle value)

      Interesting to note how the 16 solutions illustrate aspects of analysis in Frits code.

      Like

  • Jim Randell 8:40 am on 31 March 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2867: Clumsy Meg 

    From The Sunday Times, 3rd September 2017 [link]

    I arranged cards labelled ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE and TEN equally-spaced around the perimeter of a circular table. The arrangement was such that any two adjacent cards had exactly one letter in common.

    That evening Meg entered the room and accidentally knocked two adjacent cards onto the floor. In her haste to put things right, she inadvertently put the two cards back the wrong way round. Surprisingly, the one-letter property still applied.

    What were the two numbers directly opposite the two that she knocked on the floor?

    [teaser2867]

     
    • Jim Randell 8:41 am on 31 March 2022 Permalink | Reply

      I took “exactly one letter in common” to mean that there was exactly one letter of the alphabet that appeared in both words, but the letter may be repeated in one (or both) of the words.

      The following Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import subsets, intersect, ordered, update, tuples, join, printf
      
      # available words
      words = ('ONE', 'TWO', 'THREE', 'FOUR', 'FIVE', 'SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN')
      
      # find words that share exactly one letter
      S1 = set(ordered(*ws) for ws in subsets(words, size=2) if len(intersect(ws)) == 1)
      
      # check two words share exactly one letter
      check = lambda *ws: ordered(*ws) in S1
      
      # generate a ring of words such that adjacent items share exactly one letter
      def generate(s, ws):
        sz = s[-1]
        # are we done?
        if not ws:
          # check closure and eliminate duplicates
          if check(sz, s[0]) and s[1] < sz:
            yield s
        else:
          # extend the ring
          for (i, w) in enumerate(ws):
            if check(sz, w):
              yield from generate(s + [w], ws[:i] + ws[i + 1:])
      
      # solve the puzzle starting with the first word
      for s in generate([words[0]], words[1:]):
        # find two adjacent words that can be swapped
        for (i, w) in enumerate(s):
          if i == len(s) - 1: break
          s2 = update(s, (i + 1, i), s[i:i + 2])
          if all(check(a, b) for (a, b) in tuples(s2, 2, circular=1)):
            # the numbers opposite the swapped pair
            r = (s2[(i + 5) % 10], s2[(i + 6) % 10])
            fmt = lambda x: join(x, sep=" ", enc="()")
            printf("{r}; {s} -> {s2}", r=fmt(r), s=fmt(s), s2=fmt(s2))
      

      Solution: The two numbers are: SEVEN and EIGHT.

      One scenario is that the cards were initially laid out:

      ONE (O) FOUR (F) FIVE (E) TEN (T) TWO (T) EIGHT (E) SEVEN (S) SIX (I) NINE (E) THREE (E) [ONE]

      And the ONE and FOUR cards were swapped over to give

      FOUR (O) ONE (E) FIVE (E) TEN (T) TWO (T) EIGHT (E) SEVEN (S) SIX (I) NINE (E) THREE (R) [FOUR]

      Or we started with the second set and swapped ONE and FOUR to get the first set.

      Like

  • Jim Randell 2:05 pm on 4 January 2022 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2875: Easy as ABC 

    From The Sunday Times, 29th October 2017 [link]

    I have ten cards and on each is one of the letters A, B, C, E, L, N, T, V, W and Y. On the back of each card is a different digit.

    The digits on T, E, N add to 10.

    The digits on T, W, E, L, V, E add to 12.

    The digits on T, W, E, N, T, Y add to 20.

    The digits on A, B, C add to …

    If I told you that last total, then you should be able to answer the following question:

    What are the digits on T, E and N respectively?

    [teaser2875]

     
    • Jim Randell 2:06 pm on 4 January 2022 Permalink | Reply

      Presumably we are to find the unique answer to the final question.

      The values of A, B, C are independent of the rest of the puzzle, and we are only interested in their sum, so we can place an ordering on them (and the remaining permutations would provide further solutions).

      I used the [[ SubstitutedExpression() ]] solver from the enigma.py library to find possible values of A + B + C and (T, E, N), and the used the [[ filter_unique() ]] function to find sums that give a unique value for (T, E, N).

      The following Python program runs in 60ms.

      Run: [ @replit ]

      from enigma import SubstitutedExpression, filter_unique, uniq, unpack, printf
      
      # find solutions to the given sums
      p = SubstitutedExpression(
        [
          "sum([T, E, N]) = 10",
          "sum([T, W, E, L, V, E]) = 12",
          "sum([T, W, E, N, T, Y]) = 20",
          "A < B < C", # to remove duplicate solutions
        ],
        answer="(A + B + C, (T, E, N))",
        verbose=0,
      )
      
      # find solutions where A + B + C uniquely identifies (T, E, N)
      ss = filter_unique(
        uniq(ans for (d, ans) in p.solve()),
        unpack(lambda ABC, TEN: ABC),
        unpack(lambda ABC, TEN: TEN),
      ).unique
      
      # output solutions
      for (ABC, TEN) in ss:
        printf("A + B + C = {ABC} -> (T, E, N) = {TEN}") 
      

      Solution: T = 3; E = 2; N = 5.

      The complete set of values:

      {A, B, C} = {7, 8, 9}
      {L, V} = {0, 4}
      E = 2
      N = 5
      T = 3
      W = 1
      Y = 6

      Like

    • GeoffR 6:38 pm on 4 January 2022 Permalink | Reply

      The only way I could find a unique solution for (T,E,N) in MiniZinc was to maximise the sum of (A+B+C). Other potential values of (T,E,N) were found, but they were not unique.

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 0..9:A; var 0..9:B; var 0..9:C; var 0..9:E;
      var 0..9:L; var 0..9:N; var 0..9:T; var 0..9:V;
      var 0..9:W; var 0..9:Y;
      
      constraint all_different([A, B, C, E, L, N, T, V, W, Y]);
      constraint T > 0;
      
      constraint T + E + N == 10;
      constraint T + W + E + L + V + E == 12;
      constraint T + W + E + N + T + Y == 20;
      
      solve maximize(A + B + C);
      
      output["[A + B + C] = " ++ show(A + B + C) ++ 
      ", [T,E,N] = " ++ show([T,E,N]) ];
      
      % [A + B + C] = 17, [T,E,N] = [1, 0, 9]
      % ----------
      % [A + B + C] = 18, [T,E,N] = [2, 0, 8]
      % ----------
      % [A + B + C] = 20, [T,E,N] = [2, 0, 8]
      % ----------
      % [A + B + C] = 22, [T,E,N] = [2, 0, 8]
      % ----------
      % [A + B + C] = 23, [T,E,N] = [1, 2, 7]
      % ----------
      % [A + B + C] = 24, [T,E,N] = [3, 2, 5] <<< Solution with unique values of  A, B and C.
      % ----------
      % ==========
      
      
      

      Like

  • Jim Randell 8:46 am on 9 November 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2834: Degrees of freedom 

    From The Sunday Times, 15th January 2017 [link]

    I bought an odd thermometer from an old curiosity shop. On its linear scale the freezing point and boiling point of water were higher than they are on the centigrade scale. In fact the freezing point was a prime number and, higher up the scale, the boiling point was a perfect square. There was only one number on the scale where it actually agreed with the corresponding centigrade temperature. That number was the negative of an odd prime (and not the same prime as the one mentioned earlier).

    On this new scale, what are the freezing and boiling points of water?

    There are now 2500 puzzles available between the Enigmatic Code and S2T2 sites. See [link].

    [teaser2834]

     
    • Jim Randell 8:46 am on 9 November 2021 Permalink | Reply

      A straightforward program finds the answer. The following Python program runs in 48ms.

      Run: [ @replit ]

      from enigma import Primes, irange, inf, div, printf
      
      def solve():
        primes = Primes()
      
        # consider possible squares (for the boiling point)
        for n in irange(11, inf):
          b = n * n
      
          # consider possible primes (for the freezing point)
          for f in primes.range(2, b - 100):
      
            # compute when the temperature scales coincide
            d = b - f - 100
            if not(d > 0): continue
            v = div(100 * f, d)
            if v is None or not(v > 2 and v != f and v in primes): continue
      
            yield (n, b, f, v)
      
      # find the first solution
      for (n, b, f, v) in solve():
        printf("n={n} b={b} f={f} v={v}")
        break
      

      Solution: The freezing point is at 41. The boiling point is at 961.

      The scales coincide at −5.

      To convert from Celsius you can use:

      y = (46/5)x + 41

      However, if the scales were allowed to coincide at −2, there would be further solutions:

      f = 31, b = 1681 (= 41²), y = (33/2)x + 31, coincide at −2
      f = 71, b = 3721 (= 61²), y = (73/2)x + 71, coincide at −2


      A bit of analysis gives a shorter program:

      The scales coincide at −v where:

      v = 100f / (b − f − 100)

      And v is an odd prime number different from f.

      The prime factorisation of the numerator is: 2⋅2⋅5⋅5⋅f.

      So we immediately see:

      v = 5
      b = 21f + 100

      And a short program provides the answer:

      from enigma import Primes, is_square, printf
       
      for f in Primes():
        b = 21 * f + 100
        if is_square(b):
          printf("f={f} b={b}")
          break
      

      Alternatively, we can further analyse the expression for b, which is a square, say n²:

      n² = 21f + 100
      n² − 100 = 21f
      (n − 10)(n + 10) = 3⋅7⋅f

      Considering the factor that does not contain f:

      n − 10 = 1 ⇒ n = 11, f = 1 [not prime]
      n + 10 = 1 ⇒ n = −9, f = −19/21 [non-integral]
      n − 10 = 3 ⇒ n = 13, f = 23/7 [non-integral]
      n + 10 = 3 ⇒ n = −7, f = −17/7 [non-integral]
      n − 10 = 7 ⇒ n = 17, f = 9 [not prime]
      n + 10 = 7 ⇒ n = −3, f = −13/3 [non-integral]
      n − 10 = 21 ⇒ n = 31, f = 41 [*** SOLUTION ***]
      n + 10 = 21 ⇒ n = 11, f = 1 [not prime]

      Like

  • Jim Randell 11:15 am on 4 November 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2832: A New Year reminiscence 

    From The Sunday Times, 1st January 2017 [link]

    Whilst filing away last year’s diary this morning I came across an old diary from my teenage years. In it I can see that in one particular month I went to four parties, three of them being on Saturdays and the other on a Sunday. I wrote down the four dates of the parties in words (in the format “January first” etc.) and found that each of the dates used a different prime number of letters.

    What were the four dates that I wrote down?

    [teaser2832]

     
    • Jim Randell 11:16 am on 4 November 2021 Permalink | Reply

      This Python program finds the first (most recent) year and month satisfying the conditions.

      It runs in 55ms.

      Run: [ @replit ]

      from datetime import date
      from enigma import (irange, int2words, catch, is_prime, subsets, join, sprintf as f, cached, printf)
      
      # map month numbers to English names
      months = dict(enumerate([
          'January', 'February', 'March', 'April', 'May', 'June',
          'July', 'August', 'September', 'October', 'November', 'December',
        ], start=1)
      )
      
      # ordinals that aren't cardinal + "th", or cardinal - "y" + "ieth"
      _ordinal = {
        1: 'first',
        2: 'second',
        3: 'third',
        5: 'fifth',
        8: 'eighth',
        9: 'ninth',
        12: 'twelfth',
      }
      
      # return the ordinal of a number (0 < n < 100)
      @cached
      def ordinal(n):
        if n in _ordinal:
          return _ordinal[n]
        if n < 20:
          return int2words(n) + 'th'
        (t, r) = divmod(n, 10)
        if r == 0:
          return int2words(n)[:-1] + 'ieth'
        else:
          return int2words(n - r) + ' ' + ordinal(r)
      
      # format dates
      fmt = lambda x: join((f('"{d}" {n}') for (d, n) in x), sep=", ", enc="[]")
      
      # find solutions (going back in time)
      def solve(month=12, year=2016):
      
        while year > 0:
          # find saturdays and sundays in the specified month
          sats = list()
          suns = list()
          for day in irange(1, 31):
            d = catch(date, year, month, day)
            if d is None: break
            wd = d.weekday()
            if not (wd == 5 or wd == 6): continue
            s = months[month] + " " + ordinal(day)
            n = sum(1 for x in s if x.isalpha())
            if is_prime(n):
              (sats if wd == 5 else suns).append((s, n))
      
          # choose three saturdays
          for sat in subsets(sats, size=3):
            ps = set(p for (s, p) in sat)
            if len(ps) != 3: continue
            sun = list((s, p) for (s, p) in suns if p not in ps)
            if sun:
              yield (month, year, sat, sun)
      
          # move back a month
          month -= 1
          if month == 0: (month, year) = (12, year - 1)
      
      # find the first solution
      for (month, year, sat, sun) in solve():
        printf("month={month}, year={year}, sat={sat}, sun={sun}", sat=fmt(sat), sun=fmt(sun))
        break
      

      Solution: The four dates are: August fifth, August twelfth, August twenty sixth, August twenty seventh.

      With 11, 13, 17, and 19 letters respectively.

      The first viable year (counting back from 2016) is 2006.

      If we suppose the setter was 16 when attending the parties that gives an age in 2016 of 26.

      But there are further solutions going back in time (but they all give the same answer to the puzzle):

      year = 2000; current age = 32
      year = 1995; current age = 37
      year = 1989; current age = 43
      year = 1978; current age = 54
      year = 1972; current age = 60
      year = 1967; current age = 65
      year = 1961; current age = 71
      year = 1950; current age = 82
      year = 1944; current age = 88
      year = 1939; current age = 93
      year = 1933; current age = 99
      year = 1922; current age = 110
      year = 1916; current age = 116
      year = 1911; current age = 121
      year = 1905; current age = 127

      I won’t speculate on the probable age of the setter.

      Like

    • Frits 2:31 pm on 4 November 2021 Permalink | Reply

      Some constants have been taken from Brian Gladman’s site.
      I didn’t bother to put in code for leap years (28/29 in February, the month always has to be August anyway).

        
      import datetime
      
      MONTHS = ( "January", "February", "March", "April", "May", 
                 "June", "July", "August", "September", "October", 
                 "November", "December" )
       
      DAYS = ( "first", "second", "third", "fourth", "fifth", "sixth", 
               "seventh", "eighth", "ninth", "tenth", "eleventh", "twelfth", 
               "thirteenth", "fouteenth", "fifteenth", "sixteenth", 
               "seventeenth", "eighteenth","nineteenth", "twentieth", 
               "twentyfirst", "twentysecond", "twentythird","twentyfourth",
               "twentyfifth", "twentysixth", "twentyseventh", "twentyeighth", 
               "twentyninth", "thirtieth", "thirtyfirst" )
               
      WEEKDAYS = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday", 
                  "Saturday", "Sunday"]
               
      P = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
       
      # days in month (29 for February)
      DIM = ( 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 )
      
      minm = min(len(m) for m in MONTHS)
      maxm = max(len(m) for m in MONTHS)
      
      mind = min(len(d) for d in DAYS)
      maxd = max(len(d) for d in DAYS)
      
      primes = [x for x in range(minm + mind, maxm + maxd + 1) if x in P]
      
      if len(primes) < 4: 
        print("no solution")
        exit()
      
      # skip months that are too short to make the 4th prime
      ms = [m for m in MONTHS if len(m) + maxd >= primes[3]]
      
      # skip months that are too long to make the 1st prime
      ms = [m for m in ms if len(m) + mind <= primes[-4]]
      
      # pick one value from each entry of a <k>-DIMensional list <ns>
      def pickOneFromEach(k, ns, s=[]):
        if k == 0:
           s = sorted(s)
           # first entry must be either a day later than the rest or same week day
           if tuple(sorted((s[0] - x) % 7 for x in s[1:])) in \
                   {(1, 1, 1), (0, 0, 6)}:
             yield s
        else:
          for n in ns[k-1]:
            # day numbers must be equal or one apart
            if not s or all((n - x) % 7 in {0, 1, 6} for x in s):
              yield from pickOneFromEach(k - 1, ns, s + [n])
      
      # process all viable months
      for m in ms:
        lenm = len(m)
        mno = MONTHS.index(m) + 1
        
        # make list of different month+day lengths
        lst = [[] for _ in range(4)]  
        for i, d in enumerate(DAYS[:DIM[mno] - 1], start=1):
          totlen = lenm + len(d)
          if totlen not in primes: continue
          lst[primes.index(totlen)].append(i)
        
        # check whether we can find a combination of <lst> entries with
        # three same week days and one on the following day
        cands = list(pickOneFromEach(4, lst))
        for c in cands:
          for y in range(2016, 1900, -1):    
            wdays = [WEEKDAYS[datetime.date(year=y, month=mno, day=d).weekday()] 
                     for d in c]
      
            if sorted(wdays) == ['Saturday', 'Saturday', 'Saturday', 'Sunday']:
              print(f"{y}, {m} {c}")
              break # stop at first solution
      

      Like

  • Jim Randell 9:31 am on 26 October 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2833: Celebrity dogs 

    From The Sunday Times, 8th January 2017 [link]

    Six celebrities appeared on television with their dogs. Each celebrity brought two dogs and between them they had twelve different breeds.

    The celebrities were Clooney, Hathaway, Jackman, Palermo, Rossum and Seyfried. The breeds of dog were Akita, Basenji, Basset, Bull Terrier, Chihuahua, Dalmation, Foxhound, Keeshond, Plott, Poodle, Rottweiler and Setter.

    For the name and breeds in each trio of celebrity plus their two dogs, if you look at any two out of the three then there are just two letters of the alphabet that occur (once or more) in both.

    In alphabetical order of the breeds, please list the initials of the owners (e.g. C, S, A, C, …)

    [teaser2833]

     
    • Jim Randell 9:32 am on 26 October 2021 Permalink | Reply

      I used the standard spelling of “Dalmatian”, but it doesn’t change the answer if you use the version given in the puzzle text.

      This is another puzzle that can be solved using the [[ grouping ]] functionality from the enigma.py library.

      The following Python program runs in 45ms.

      Run: [ @replit ]

      from enigma import (grouping, join, printf)
      
      # categories for this puzzle (using the normal spelling of "Dalmatian")
      names = ( 'Clooney', 'Hathaway', 'Jackman', 'Palermo', 'Rossum', 'Seyfried' )
      dogs = (
        'Akita', 'Basenji', 'Basset', 'Bull Terrier', 'Chihuahua', 'Dalmatian',
        'Foxhound', 'Keeshond', 'Plott', 'Poodle', 'Rottweiler', 'Setter'
      )
      
      # form the 2-gangs
      for gs in grouping.gangs(2, names, dogs, grouping.share_letters(2)):
        # output the gangs
        grouping.output_gangs(names, gs)
      
        # map breeds to their owners
        m = dict()
        for (n, ds) in zip(names, gs):
          m.update((d, n) for d in ds)
        # output owner initials by breed
        printf("-> {s}", s=join((m[d][0] for d in dogs), sep=" "))
      

      Solution: The initials of the owners are: J P H C J H S R C S R P.

      Ownership is as follows:

      Clooney: Bull Terrier, Plott
      Hathaway: Basset, Dalmatian
      Jackman: Akita, Chihuahua
      Palermo: Basenji, Setter
      Rossum: Keeshond, Rottweiler
      Seyfried: Foxhound, Poodle

      Like

  • Jim Randell 9:49 am on 28 September 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2827: Password 

    From The Sunday Times, 27th November 2016 [link] [link]

    My computer password consists of different digits written in decreasing order.

    I can rearrange the digits to form a perfect cube.

    A further rearrangement gives a perfect square.

    Another rearrangement gives a prime number.

    A further rearrangement gives a number that is divisible by the number of digits in the password.

    Yet another rearrangement gives a number that is divisible by all but one of its digits.

    What is my password?

    [teaser2827]

     
    • Jim Randell 9:50 am on 28 September 2021 Permalink | Reply

      This Python program runs in 245ms.

      Run: [ @replit ]

      from enigma import group, unpack, powers, inf, is_duplicate, ordered, nsplit, intersect, nconcat, subsets, is_prime, find, update, printf
      
      # collect numbers by digit content
      def numbers(s):
        def generate():
          for n in s:
            if n > 9876543210: break
            # only collect numbers with distinct digits
            if is_duplicate(n): continue
            yield (ordered(*nsplit(n), reverse=1), n)
        return group(generate(), by=unpack(lambda ds, n: ds), f=unpack(lambda ds, n: n))
      
      cubes = numbers(powers(0, inf, 3))
      squares = numbers(powers(0, inf, 2))
      
      divides = lambda n, ds: sum(d != 0 and n % d == 0 for d in ds)
      
      # select distinct elements from each set
      def select(ss, xs):
        i = find(xs, None)
        if i == -1:
          yield xs
        else:
          # choose an elements from ss[i]
          for x in ss[i]:
            if x not in xs:
              yield from select(ss, update(xs, [(i, x)]))
      
      # look for keys common to squares and cubes
      for ds in intersect(s.keys() for s in (squares, cubes)):
        k = len(ds)
      
        # find rearrangements (we need at least 6)...
        rs = set(nconcat(*s) for s in subsets(ds, size=k, select="P") if s[0] > 0)
        if len(rs) < 6: continue
      
        # ... divisible by k
        r1s = set(n for n in rs if n % k == 0)
        if not r1s: continue
      
        # ... divisible by all but one of the digits in ds
        r2s = set(n for n in rs if divides(n, ds) == k - 1)
        if not r2s: continue
      
        # ... primes
        r3s = set(n for n in rs if is_prime(n))
        if not r3s: continue
      
        # select distinct members for each set
        n = nconcat(*ds)
        for xs in select([[n], cubes[ds], squares[ds], r3s, r1s, r2s], [None] * 6):
          printf("password = {n}")
          printf("-> cubes = {rs}", rs=cubes[ds])
          printf("-> squares = {rs}", rs=squares[ds])
          printf("-> primes = {r3s}")
          printf("-> divisible by {k} = {r1s}")
          printf("-> divisible by all but one of {ds} = {r2s}")
          printf("-> selected = {xs}")
          break  # only need one example
      

      Solution: The password is 9721.

      The program ensures five different rearrangements of the password satisfying the conditions can be made, for example:

      9721 = password
      2197 = cube
      7921 = square
      2179 = prime
      7912 = divisible by 4 (length of password)
      1792 = divisibly by 7, 2, 1 (but not 9)

      In fact there are 50 different sets of rearrangements that we could choose for this particular password.


      We can do some analysis to reduce the number of passwords considered by looking at digital roots (which are unchanged by rearrangement):

      the digital root of a square is 1, 4, 7, 9
      the digital root of a cube is 1, 8, 9
      the digital root of prime (except 3) is 1, 2, 4, 5, 7, 8

      So we need only consider passwords with a digital root of 1. (At this point considering cubes leads to 12 candidate passwords).

      Also, there must be at least 6 different rearrangements, so we need at least 3 digits, but it cannot have exactly 3 digits, as then the requirement for a rearrangement divisible by the number of digits would require a rearrangement that is divisible by 3, which would also have a digital root that was divisible by 3. (At this point considering cubes leads to 10 candidate passwords).

      Similarly, the number cannot have 9 digits, as it would have to have a rearrangement with a digital root of 9. Nor 10 digits, as again, the digital root would have to be 9.

      And if the password had length 6, it would have to have a rearrangement divisible by 6, which would require the rearrangement to be divisible by 3, and so its digital root would also be divisible by 3.

      So the password has 4, 5, 7, or 8 digits, and a digital root of 1. (At this point considering cubes leads to 6 candidate passwords).

      Additionally the password is not divisible only one of its digits, and it cannot be divisible by 0, 3, 6, 9, so no more than one of those four digits can occur in it.

      This is enough to narrow the password down to a single candidate, which gives the answer to the puzzle. (Although for completeness we should check that the appropriate rearrangements can be made).

      Like

    • Hugh Casement 1:36 pm on 28 September 2021 Permalink | Reply

      All six rearrangements ending in 2 are integer multiples of 4 (and of course of 1 and 2).
      1279, 1297, 2179, 2719, 2791, 2917, 2971, 7129, 7219, 9127, 9721 are all prime.
      I have certainly known more satisfying Teasers.

      Like

    • Frits 12:02 pm on 4 October 2021 Permalink | Reply

      The singles and lst2 logic is not really needed as Jim’s select function is sufficient.
      The program runs in 15ms.

       
      from enigma import is_cube, is_square, is_prime, find, update
      from itertools import permutations as perm
      
      # select distinct elements from each row
      def select(ss, xs):
        i = find(xs, None)
        if i == -1:
          yield xs
        else:
          # choose an elements from ss[i]
          for x in ss[i]:
            if x not in xs:
              yield from select(ss, update(xs, [(i, x)]))
      
      def check(n):
        # we need 6 arrangements
        
        # 0: I can rearrange the digits to form a perfect cube.
        # 1: A further rearrangement gives a perfect square.
        # 2: Another rearrangement gives a prime number.
        # 3: A rearrangement that is divisible by the number of digits.
        # 4: A rearrangement that is divisible by all but one of its digits.
        # 5: original number
      
        s = str(n)
        ndigits = len(s)
        lst = [[] for _ in range(5)]
        
        # check all permutations of original number
        for p in perm(s):
          m = int("".join(p)) 
          
          if m == n: continue
        
          if is_cube(m): 
            lst[0] += [m]
          if is_square(m): 
            lst[1] = lst[1] + [m]
          if is_prime(m): 
            lst[2] += [m]
          if m % ndigits == 0: 
            lst[3] += [m]
          if sum(x != '0' and m % int(x) == 0 for x in p) == ndigits - 1: 
            lst[4] += [m]
            
        # if any row is empty return False
        if any(not x for x in lst): return False
        
        # add 6th arrangement (original number)
        lst += [[n]]
        
        singles = [x[0] for x in lst if len(x) == 1]
        
        # build list of non-singles with numbers not occurring in singles
        lst2 = [[y for y in x if y not in singles] for x in lst if len(x) > 1]  
        lngth = len(lst2)
        
        # if each remaining row contains enough items return True
        if all(len(x) >= lngth for x in lst2):
          return True
        
        # select distinct members for each row
        for x in select(lst, [None] * 6):
          return True
        
        return False
      
      # add digit to each number in the list so that order remains decreasing
      def addLastDigit(li=range(1, 10)):
        lngth = len(str(li[0])) if li else 0
        return [10 * n + i for n in li for i in range(10 - lngth) if i < (n % 10)]
            
            
      # list of 3-digit numbers with different digits written in decreasing order
      nums = addLastDigit(addLastDigit())
      
      while True:
        for n in nums:
          if check(n):
            print("password:", n)
            break  # only need one example
        else:  # no break
          if len(str(nums[0])) > 9: break
          # add another digit
          nums = addLastDigit(nums)
          continue
          
        break    # break if nested break occurred 
      

      Like

  • Jim Randell 1:45 pm on 17 August 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2811: Making arrangements 

    From The Sunday Times, 7th August 2016 [link] [link]

    Beth wrote down a three-figure number and she also listed the five other three-figure numbers that could be made using those same three digits. Then she added up the six numbers: it gave a total whose digits were all different, and none of those digits appeared in her original number.

    If you knew whether her original number was prime or not, and you knew whether the sum of the three digits of her original number was prime or not, then it would be possible to work out her number.

    What was it?

    [teaser2811]

     
    • Jim Randell 1:47 pm on 17 August 2021 Permalink | Reply

      If the number is ABC, then in order for the different orderings of (A, B, C) to make 6 different numbers A, B, C must all be distinct and non-zero. Then we have:

      ABC + ACB + BAC + BCA + CAB + CBA = PQRS
      ⇒ 222 × (A + B + C) = PQRS

      We can use two of the routines from the enigma.py library to solve this puzzle. [[ SubstitutedExpression() ]] to solve the alphametic problem, and [[ filter_unique() ]] to find the required unique solutions.

      The following Python program runs in 53ms.

      Run: [ @replit ]

      from enigma import SubstitutedExpression, filter_unique, unpack, printf
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        ["222 * (A + B + C) = PQRS"],
        d2i={ 0: 'ABCP' },
        answer="(ABC, is_prime(ABC), is_prime(A + B + C))",
      )
      
      # if you knew (f1, f2) you could deduce n
      rs = filter_unique(
        (ans for (_, ans) in p.solve(verbose=0)),
        unpack(lambda n, f1, f2: (f1, f2)),
        unpack(lambda n, f1, f2: n),
      )
      
      # output solution
      for (n, f1, f2) in rs.unique:
        printf("number = {n} (prime = {f1}; dsum prime = {f2})")
      

      Solution: Beth’s number was 257.

      The only values for (A, B, C) that work are (2, 5, 7) and (3, 7, 9). These can be assembled in any order to give an original number that works.

      Of these 257 is the only arrangement that gives a prime number, with a digit sum that is not prime.

      Like

    • GeoffR 9:39 am on 18 August 2021 Permalink | Reply

      I used four lists for the two primality tests for each potential 3-digit answer. The list with a single entry was Beth’s number.

      from itertools import product
      from enigma import is_prime
      
      # Four lists for primality tests
      TT, FT, FF, TF = [], [], [], []
      
      # Form six 3-digit numbers - Beth's number was abc
      for a,b,c in product(range(1,10), repeat=3):
        abc, acb = 100*a + 10*b + c, 100*a + 10*c + b
        bac, bca = 100*b + 10*a + c, 100*b + 10*c + a
        cab, cba = 100*c + 10*a + b, 100*c + 10*b + a
        pqrs = abc + acb + bac + bca + cab + cba
        # find four digits of the sum of six numbers
        p, q = pqrs//1000, pqrs//100 % 10
        r, s = pqrs//10 % 10, pqrs % 10
        
        # all seven digits are different
        if len(set((a, b, c, p, q, r, s))) == 7:
          
          # check the primality of number abc
          # and primality of the sum of its digits
          if is_prime(abc) and is_prime(a+b+c):
            TT.append(abc)  # true/true
            
          if not(is_prime(abc)) and is_prime(a+b+c):
            FT.append(abc)  # false/true
            
          if not(is_prime(abc)) and not(is_prime(a+b+c)):
            FF.append(abc)  # false/false
            
          if is_prime(abc) and not(is_prime(a+b+c)):
            TF.append(abc)  # true/false
      
      # find a single number in the four lists
      for L in (TT, FT, FF, TF):
        if len(L) == 1:
          print(f"Beth's number was {L[0]}.")
          
      print("True/True numbers = ", TT)
      print("False/True numbers = ", FT)
      print("False/False numbers = ", FF)
      print("True/False numbers = ", TF)
          
      # Beth's number was 257.
      # True/True numbers =  [379, 397, 739, 937]
      # False/True numbers =  [793, 973]
      # False/False numbers =  [275, 527, 572, 725, 752]
      # True/False numbers =  [257]
      
      

      Like

    • Frits 3:02 pm on 18 August 2021 Permalink | Reply

        
      from itertools import permutations as perm
      from functools import reduce
      from enigma import is_prime
      
      # convert digits sequence to number
      d2n = lambda s: reduce(lambda x, y: 10 * x + y, s)
      
      # decompose number <t> into <k> increasing numbers from <ns>
      # so that sum(<k> numbers) equals <t>
      def decompose(t, k, ns, s=[]):
        if k == 1:
          if t in ns and t > s[-1]:
            yield s + [t]
        else:
          for n in ns:
            if s and n <= s[-1]: continue
            yield from decompose(t - n, k - 1, ns, s + [n])
      
      # 5 < a + b + c < 25
      for sumabc in range(6, 25):
        # pqrs = abc + acb + bac + bca + cab + cba
        pqrs = str(222 * sumabc)   
        
        # skip if duplicate digits
        if len(set(pqrs)) != len(pqrs): continue
        
        # determine minimum and maximum for a, b, c
        mi = max(1, sumabc - 9 - 8)
        ma = min(9, sumabc - 1 - 2)
        
        # determine digits not used in sum (must be valid for a, b, c)
        missing = [x for x in range(1, 10) if str(x) not in pqrs and mi <= x <= ma]
        if len(missing) < 3: continue
        
        # check if 3 digits of missing sum to <sumabc>
        for d in decompose(sumabc, 3, missing):
          if not is_prime(sumabc): 
            # check which permutatons of a, b, c are prime
            primes = [n for p in perm(d) if is_prime(n := d2n(p))]
            if len(primes) == 1:
              print("answer:", primes[0])
          else:     # sumabc is prime    
            # check which permutatons of a, b, c are non-prime
            nprimes = [n for p in perm(d) if not is_prime(n := d2n(p))]
            if len(nprimes) == 1:
              print("answer:", nprimes[0]) 
      

      Like

    • GeoffR 3:08 pm on 19 August 2021 Permalink | Reply

      An easy solution with standard MiniZinc, although the answer needs to be interpreted from multiple output configuration.

      % A Solution in MiniZinc 
      include "globals.mzn";
      
      var 1..9: A; var 1..9: B; var 1..9: C; 
      var 1..9: P; var 0..9: Q; var 0..9: R; var 0..9: S; 
      
      constraint all_different([A, B, C, P, Q, R, S]);
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
      ((i < x) -> (x mod i > 0));
      
      var 100..999: ABC = 100*A + 10*B + C;
      var 100..999: ACB = 100*A + 10*C + B;
      var 100..999: BAC = 100*B + 10*A + C;
      var 100..999: BCA = 100*B + 10*C + A;
      var 100..999: CAB = 100*C + 10*A + B;
      var 100..999: CBA = 100*C + 10*B + A;
      var 1000..9999: PQRS = 1000*P + 100*Q + 10*R + S;
      
      var 6..24: sum_ABC = A + B + C;
      
      constraint ABC + ACB + BAC + BCA + CAB + CBA == PQRS;
      
      solve satisfy;
      
      output [ "[ABC, sum_ABC] = " ++ 
      show([ABC, is_prime(ABC), sum_ABC, is_prime(sum_ABC) ]) ];
      
      % key: 0 = not prime, 1 = prime
      
      % [ABC, sum_ABC] = [752, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [572, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [973, 0, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [793, 0, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [725, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [275, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [527, 0, 14, 0]
      % ----------
      % [ABC, sum_ABC] = [937, 1, 19, 1]
      % ----------
      % *** unique prime/non-prime test for ABC ***
      % [ABC, sum_ABC] = [257, 1, 14, 0] <<<
      % ----------
      % [ABC, sum_ABC] = [397, 1, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [739, 1, 19, 1]
      % ----------
      % [ABC, sum_ABC] = [379, 1, 19, 1]
      % ----------
      % ==========
      
      
      

      Like

  • Jim Randell 9:09 am on 8 July 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2800: Promoting rugby 

    From The Sunday Times, 22nd May 2016 [link] [link]

    Six male rugby players and six female rugby players are helping to promote the game. The men are Eastmond, Morgan, Twelvetrees, Webber, Yarde and Youngs. The women are Allen, Clarke, Croker, McGilchrist, McLean and Thompson. The men have paired off with the women and one pair has gone to each of the counties East Sussex, Hampshire, Isle of Wight, Norfolk, Suffolk and Surrey. For each pair, if you look at the name of the man, the name of the woman and the name of their county, then for any two of the three names just two different letters of the alphabet occur in both (possibly more than once).

    The men above are listed in alphabetical order: in that order, who are their female partners?

    [teaser2800]

     
    • Jim Randell 9:10 am on 8 July 2021 Permalink | Reply

      This is another puzzle by Graham Smithers that can be solved using the [[ grouping ]] functionality in the enigma.py library.

      This Python program runs in 52ms.

      Run: [ @replit ]

      from enigma import grouping
      
      male = ('Eastmond', 'Morgan', 'Twelvetrees', 'Webber', 'Yarde', 'Youngs')
      female = ('Allen', 'Clarke', 'Croker', 'McGilchrist', 'McLean', 'Thompson')
      county = ('East Sussex', 'Hampshire', 'Isle of Wight', 'Norfolk', 'Suffolk', 'Surrey')
      
      grouping.solve([male, female, county], grouping.share_letters(2))
      

      Solution: The female partners are: Clarke, Allen, Thompson, Croker, McLean, McGilchrist.

      Like

  • Jim Randell 8:00 am on 10 June 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2794: D-day 

    From The Sunday Times, 10th April 2016 [link] [link]

    I have a particular digit in mind and I shall call it D. I have written down a number consisting of D digits in which the penultimate digit is D itself. If I move that penultimate digit to the left so that it becomes the first digit, then I get a new D-digit number that turns out to be D times the number I started with.

    What is the D-digit number I started with?

    [teaser2794]

     
    • Jim Randell 8:00 am on 10 June 2021 Permalink | Reply

      Using : for concatenation, we have:

      D:abc:z = D × abc:D:z
      ⇒ 10^(D − 1) D + 10 abc + z = D (100 abc + 10 D + z)
      ⇒ abc = (10 D (10^(D − 2) − D) − (D − 1) z) / (100 D − 10)

      where abc represents a (D − 2) digit number).

      This Python program runs in 50ms.

      Run: [ @replit ]

      from enigma import irange, div, ndigits, printf
      
      # choose D
      for D in irange(3, 9):
        x = 10 * D * (10 ** (D - 2) - D)
        y = 100 * D - 10
        # possible final digits
        for z in irange(0, 9):
          # note: D * z = z [mod 10]
          r = (D - 1) * z
          if not(r % 10 == 0): continue
          # calculate abc...
          abc = div(x - r, y)
          if abc is None or ndigits(abc) != D - 2: continue
          # output solution
          printf("number={abc}{D}{z} [D={D}]")
      

      Solution: The number you started with is 101123595.

      So, D = 9, and: 9 × 101123595 = 910112355.

      Like

      • Frits 12:15 pm on 10 June 2021 Permalink | Reply

        @Jim, you also could have used (regarding the r % 10 == 0) :

        for z in [0, 2, 4, 5, 6, 8]:
        

        Like

      • Jim Randell 2:57 pm on 10 June 2021 Permalink | Reply

        If we construct numbers by taking successive digits of the larger number (D:abc:z), and divide these by D, then we get the corresponding digits of the number we started with, which can then be used in the next division to determine the following digit:

        D / D = a (so: a = 1)
        Da / D = ab (so: b = 0)
        Dab / D = abc

        So, for a given value of D, we can compute successive digits of abc. And after the (D − 2) digits are calculated, z is chosen to complete the division, and then we check that it is a viable digit:

        from enigma import irange, div, printf
        
        # choose D
        for D in irange(3, 9):
          n = D
          x = 0
          # perform (D - 2) divisions
          for _ in irange(1, D - 2):
            d = (n // D) % 10
            n = 10 * n + d
            x = 10 * x + d
        
          # the final digit is z
          n = 10 * n
          x = 100 * x + 10 * D
          z = div(n - x * D, D - 1)
          if z is None or z < 0 or z > 10: continue
        
          # output solution
          n += z
          x += z
          printf("[D={D}] {x} * {D} = {n}")
        

        This appears to be slightly faster than my original code (internal runtime is reduced from 60μs to 42μs).

        Like

    • Frits 11:57 am on 10 June 2021 Permalink | Reply

      We can also continue the analysis, so C must be 1, etc …

      from enigma import SubstitutedExpression
      
      # the alphametic puzzle
      p = SubstitutedExpression(
        [# consider number ABCDEFGHI
         
         # (9 * H + carry digit) modulo 10 must be equal to G
         "(81 + 0.8 * I) % 10 = G",
      
         # we have established H must be 9   
         "HABCDEFGI == 9 * ABCDEFGHI",
         ],
      
        answer="ABCDEFGHI",
        verbose=0,
        # (9 * I) % 10 = I so I is 0 or 5
        # Consider 9 * FGHI = HFGI (F > 0), this can only happen when H is 9
        # so H is 9, A must be 1 and B must be 0
        # G is 1 or 5 (see G formula)
        d2i=dict([(0, "AH")] + [(1, "BHI")] + [(2, "ABHI")] + [(5, "ABH")] + 
                 [(k, "ABHI") for k in [3, 4, 6, 7, 8, 9]] +
                 [(9, "ABI")]),
        distinct="",   # allow variables with same values
        reorder=0,
      )
      
      # Print answer
      for (_, ans) in p.solve():
        print(f"{ans}")
      

      Like

    • GeoffR 1:53 pm on 10 June 2021 Permalink | Reply

      A simple solution in MiniZinc, using Frits analysis i.e. D-digit number = 9

      
      % A Solution in MiniZinc
      
      var 0..9: A; var 0..9: B; var 0..9: C; var 0..9: D; var 0..9: E;
      var 0..9: F; var 0..9: G; var 0..9: H; var 0..9: I;
      
      constraint H > 0 /\ A > 0;
      
      var 100000000..999999999: ABCDEFGHI = I + 10*H + 100*G + 1000*F + 10000*E
      + 100000*D + 1000000*C + 10000000*B + 100000000*A;
      
      var 100000000..999999999: HABCDEFGI = I + 10*G + 100*F + 1000*E + 10000*D
      + 100000*C + 1000000*B + 10000000*A + 100000000*H;
      
      constraint HABCDEFGI == 9 * ABCDEFGHI;
      
      solve satisfy;
      
      output["The number you started with was " ++ show(ABCDEFGHI) ];
      
      % The number you started with was 101123595
      % time elapsed: 0.20 s
      % ----------
      % ==========
      
      

      Like

      • Frits 7:20 pm on 10 June 2021 Permalink | Reply

        Unfortunately my analysis was incorrect (I mixed things up).
        Following program works well with Geocode but gives no answer with the Chuffed solver.

        Using “var 0..9: A;” gives an out of range error.

        % A Solution in MiniZinc
         
        var 0..1: A; var 0..9: B; var 0..9: C; var 0..9: D; var 0..9: E;
        var 0..9: F; var 0..9: G; var 0..9: H; var 0..9: I;
        
         % moving the penultimate digit to the left so that it becomes
         % the first digit
        constraint H > 2;
         
        var 100000000..999999999: ABCDEFGHI = I + 10*H + 100*G + 1000*F
        + 10000*E + 100000*D + 1000000*C + 10000000*B + 100000000*A;
         
        var 10000000..99999999: ABCDEFGI = I + 10*G + 100*F + 1000*E
        + 10000*D + 100000*C + 1000000*B + 10000000*A;
         
        constraint H * pow(10, H - 1) + ABCDEFGI == H * ABCDEFGHI;
         
        solve satisfy;
         
        output["The number you started with was " ++ show(ABCDEFGHI)];
        

        Like

  • Jim Randell 11:36 am on 24 May 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2527 

    From The Sunday Times, 27th February 2011 [link]

    Without repeating a digit I wrote down two five-figure numbers. For the first of these, its first two digits form a number divisible by two, its first three digits form a number divisible by three, and likewise for four and five. For the second number, looking again at the numbers formed by the first few digits, those of prime length are prime and the one of length four is a square. Furthermore the sum of the digits of the difference between the two numbers is itself a digit. Without doing much division you should now be able to answer the question:

    What are the two five-figure numbers?

    [teaser2527]

     
    • Jim Randell 11:37 am on 24 May 2021 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      The following run file executes in 122ms.

      Run: [ @replit ]

      #!/usr/bin/env python3 -m enigma -r
      
      # suppose the numbers are: ABCDE and FGHIJ
      
      SubstitutedExpression
      
      # first 2, 3, 4, 5 digits of ABCDE are divisible by 2, 3, 4, 5
      "AB % 2 = 0"  # or: "B % 2 = 0"
      "ABC % 3 = 0"
      "ABCD % 4 = 0"  # or: "CD % 4 = 0"
      "ABCDE % 5 = 0"  # or: "E % 5 = 0"
      
      # first 2, 3, 5 digits of FGHIJ are prime
      "is_prime(FG)"
      "is_prime(FGH)"
      "is_prime(FGHIJ)"
      
      # FGHI is a perfect square
      "is_square(FGHI)"
      
      # the sum of the digits of the difference is a single digit
      "dsum(ABCDE - FGHIJ) < 10"
      
      --answer="(ABCDE, FGHIJ)"
      

      Solution: The numbers are: 52840 and 73961.

      Like

    • Frits 12:07 pm on 26 May 2021 Permalink | Reply

      from itertools import compress
      from math import isqrt
      
      # return true if an integer <n> is a perfect square
      def is_square(n):
        if n % 144 not in {0, 1, 4, 9, 16, 25, 36, 49, 52,
                           64, 73, 81, 97, 100, 112, 121}:
          return False
        return isqrt(n) ** 2 == n
      
      def primesbelow(n):
        # rwh_primes1v2(n):
        """ Returns a list of primes < n for n > 2 """
        sieve = bytearray([True]) * (n // 2 + 1)
        for i in range(1, int(n ** 0.5) // 2 + 1):
          if sieve[i]:
            sieve[2*i*(i+1)::2*i+1] = \
            bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1)
        return [2, *compress(range(3, n, 2), sieve[1:])]
        
      digits = "0123456789"
      P = primesbelow(100000)
      odds = ["1", "3", "5", "7", "9"]
      
      second = []
      # determine second number FGHIJ
      for FG in [str(x) for x in P if 11 < x < 100]:
        (F, G) = (FG[0], FG[1])
        for H in [x for x in odds if x not in {F, G}]:
          if int(FG + H) not in P: continue
          for I in [x for x in digits if x not in {F, G, H}]:
            if not is_square(int(FG + H + I)): continue
            for J in [x for x in odds if x not in {F, G, H, I}]:
              if int(FG + H + I + J) not in P: continue
              second.append(FG + H + I + J)
      
      for FGHIJ in second:
        remaining = "".join(x for x in digits if x not in FGHIJ)
       
        # determine first number ABCDE
        for E in [x for x in remaining if x in "05"]:
          for B in [x for x in remaining if x not in {E} and x in "02468"]:
            for A in [x for x in remaining if x not in {B, E} and x != "0"]:
              for C in [x for x in remaining if x not in {A, B, E}]:
                if int(A + B + C) % 3: continue
                for D in [x for x in remaining if x not in {A, B, C, E}]:
                  if int(C + D) % 4: continue
                  
                  ABCDE = int(A + B + C + D + E)
                  # the sum of the digits of the difference between the two numbers
                  # is itself a digit
                  if sum(int(x) for x in str(abs(int(FGHIJ) - ABCDE))) > 9: continue
                  print(f"the two five-figure numbers are: {ABCDE} and {FGHIJ}")
      

      Like

    • GeoffR 4:20 pm on 26 May 2021 Permalink | Reply

      
      from itertools import permutations
      from enigma import is_prime
      
      sq4 = [x ** 2 for x in range(32, 100)]
      
      # Find digits for first 5-digit number
      for P1 in permutations('1234567890', 5):
          A, B, C, D, E = P1
          if A == '0':
              continue
      
          # two,three, four and five digit numbers
          # are divisible by two, three, four and five
          AB = int(A + B)
          if AB % 2 != 0:
              continue
          ABC = int(A + B + C)
          if ABC % 3 != 0:
              continue
          ABCD = int(A + B + C + D)
          if ABCD % 4 != 0:
              continue
          ABCDE = int(A + B + C + D + E)
          if ABCDE % 5 != 0:
              continue
      
          # Find digits for second 5-digit number
          Q1 = set('1234567890').difference([A, B, C, D, E])
          for P2 in permutations(Q1):
              F, G, H, I, J = P2
              if F == '0':
                  continue
      
              # two, three and five digit numbers are prime
              FG = int(F + G)
              if not is_prime(FG):
                  continue
              FGH = int(F + G + H)
              if not is_prime(FGH):
                  continue
              # four digit number is square
              FGHI = int(F + G + H + I)
              if FGHI not in sq4:
                  continue
              FGHIJ = int(F + G + H + I + J)
              if not is_prime(FGHIJ):
                  continue
              
              # the sum of the digits in the difference between
              # the two numbers is a digit
              dd = sum(int(x) for x in str(abs(ABCDE - FGHIJ)))
              if not dd < 10:
                  continue
              print(f"Two five-figure numbers are {ABCDE} and {FGHIJ}.")
      
      # Two five-figure numbers are 52840 and 73961.
      
      

      Like

    • John Crabtree 6:46 pm on 26 May 2021 Permalink | Reply

      As the 3rd digit of N2 is odd, the 4th digit is 6.
      (10a + 4)^2 = 100a(a + 1) – 20a + 16, with 2nd digit odd for 0 < a < 6
      (10a + 6)^2 = 100a(a + 1) + 20a + 36, with 2nd digit odd for 3 < a N2 but the sum of the digits of the difference (SDD) cannot be 2
      86^2 = 7396, N2 = 73961, N2 > N1, SDD = 7, N1 = 52840 (not 42850)

      Using a prime factor calculator, 739 and 73961 are all prime.

      Like

  • Jim Randell 9:13 am on 20 April 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2787: Crime-writers convention 

    From The Sunday Times, 21st February 2016 [link] [link]

    A group of twelve crime writers attended a convention. They were Bonfiglioli, Durrenmatt, Fyfield, Hiaasen, Highsmith, Hill, Innes, James, Knox, Le Carre, Rendell and Sayers, They sat in one long row on the stage, with Hiaasen further to the left than Hill. It turned out that, for any two sitting next to each other, there was just one letter of the alphabet that occurred (perhaps more than once) in both their surnames.

    List the initial of each author from left to right along the row.

    [teaser2787]

     
    • Jim Randell 9:16 am on 20 April 2021 Permalink | Reply

      This Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import join, printf
      
      names = [
        'bonfiglioli', 'durrenmatt', 'fyfield', 'hiaasen', 'highsmith',
        'hill', 'innes', 'james', 'knox', 'le carre', 'rendell', 'sayers',
      ]
      
      # add names in rs to ns, so that adjacent names share exactly 1 letter
      # ns - names assigned so far
      # rs - remaining names
      def solve(ns, rs):
        # are we done?
        if not rs:
          yield ns
        else:
          # consider one of the remaining names
          for (i, n) in enumerate(rs):
            # check adjacent names share exactly 1 letter
            if not(ns) or len(set(n).intersection(ns[-1])) == 1:
              # solve for the remaining names
              yield from solve(ns + [n], rs[:i] + rs[i + 1:])
      
      # find lists of names
      for ns in solve([], names):
        # check 'hiaasen' is further left than 'hill'
        if not(ns.index('hiaasen') < ns.index('hill')): continue
        # output the names and the initals
        s = list(n[0].upper() for n in ns)
        printf("{s}\n  -> {ns}", s=join(s, sep=' '), ns=join(ns, sep=', '))
      

      Solution: The initial letters of the surnames are: H K D B L I H R J F H S.

      The order is (left to right):

      Hiaasen
      Knox
      Durrenmatt
      Bonfiglioli
      Le Carre
      Innes
      Hill
      Rendell
      James
      Fyfield
      Highsmith
      Sayers

      Like

  • Jim Randell 10:02 am on 1 April 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2782: Spiders 

    From The Sunday Times, 17th January 2016 [link] [link]

    Spiders Beth and Sam wake up in the bottom corner of a cuboidal barn (all of whose sides are whole numbers of metres). They want to reach the opposite bottom corner without actually walking across the floor. Beth decides to walk on one of five possible shortest routes, two of them being around the edge of the floor and the other three being over the walls and ceiling. Sam decides instead to spin a web directly to the point on the ceiling diagonally opposite the starting point and then to drop down into the corner. The total length of his journey is within five centimetres of a whole number of metres.

    How high is the barn?

    [teaser2782]

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

      Suppose the cuboid barn has dimensions width = x, length = y, height = z (all of which are positive integer values).

      The spiders wish to traverse from one corner of the floor to the diagonally opposite corner, but without crossing the floor.

      Beth walks along one of the 5 shortest routes (which presumably means that there are 5 shortest routes that have the same distance travelled).

      Two of these routes (p1, p2) are along the edges of the floor:

      To see the other routes we can “unfold” the barn (imagine it is a cardboard box), and the shortest paths will appear as straight lines.

      We get a route that crosses the front, ceiling and left wall (p3):

      And routes that cross the right wall, ceiling, back wall (p4), and right wall, ceiling, left wall (p5).

      So the following expressions all give the square of the minimal path length:

      [p1, p2] (x + y)² = x² + y² + 2xy
      [p5] (x + 2z)² + y² = x² + y² + 4z² + 4xz
      [p3, p4] (x + z)² + (y + z)² = x² + y² + 2z² + 2xz + 2yz

      So, given values for x and y, we can calculate z, and then look for diagonals of the cube (= hypot(x, y, z)) that are within 5cm of a whole number of metres, to give Sam’s path.

      This Python program runs in 47ms.

      Run: [ @replit ]

      from enigma import irange, inf, quadratic, hypot, first, arg, printf
      
      # generate solutions
      def solve(verbose=1):
      
        # consider increasing lengths
        for y in irange(2, inf):
          # and widths
          for x in irange(1, y - 1):
            # compute corresponding z (using p1,p2 & p5)
            for z in quadratic(4, 4 * x, -2 * x * y, domain="Z"):
              if not(z > 0): continue
      
              # check against p3,p4
              if not((x + y) ** 2 == (y + z) ** 2 + (x + z) ** 2): continue
      
              # calculate the length of diagonal through the cuboid
              h = hypot(x, y, z)
              d = abs(h - int(h + 0.5)) 
              # check it is within 5cm of a whole number of metres
              if d > 0.05: continue
      
              # lengths of paths for Beth and Sam
              (b, s) = (x + y, h + z)
              if verbose:
                printf("z={z} [x={x} y={y}; h={h:.3f} d={d:.3f}, beth={b} sam={s:.3f}]")
      
              yield (x, y, z)
      
      # find the first n solutions
      n = arg(1, 0, int)
      first(solve(), n)
      

      Solution: The barn in 4 metres high.

      In fact there is a family of solutions, the program stops after the first (smallest) solution, which is the only reasonable one, where the barn is less 25m high (and the spiders journeys are each less than 100m).


      Analytically:

      Equating the sum of the first two of the expressions with twice the third, we get:

      2x² + 2y² + 4z² + 2xy + 4xz = 2x² + 2y² + 4z² + 4xz + 4yz
      2xy = 4yz
      x = 2z

      Then, substituting for x in the first 2 expressions, and equating them:

      4z² + y² + 4yz = 16z² + y²
      4yz = 12z²
      y = 3z

      Hence the barn has dimensions (2z, 3z, z), and the shortest paths have length 5z.

      The diagonal across the barn is: √(x² + y² + z²) = √(14z²) = (√14)z.

      And we want to know when this is within 5cm if a whole number of metres.

      Here is a shorter and faster program to generate solutions:

      from enigma import irange, inf, sqrt, first, arg, printf
      
      def solve():
        r14 = sqrt(14)
      
        for z in irange(1, inf):
          h = z * r14
          d = abs(h - int(h + 0.5))
          if d > 0.05: continue
      
          (x, y) = (2 * z, 3 * z)
          (b, s) = (x + y, h + z)
          printf("z={z} [x={x} y={y}; h={h:.3f} d={d:.3f}; beth={b} sam={s:.3f}]")
      
          yield (x, y, z)
      
      # find the first n solutions
      n = arg(1, 0, int)
      first(solve(), n)
      

      Like

  • Jim Randell 9:48 am on 18 February 2021 Permalink | Reply
    Tags: by: Graham Smithers   

    Teaser 2776: Winning months 

    From The Sunday Times, 6th December 2015 [link] [link]

    I have won three Premium Bond prizes and noted the number of non-winning months between my first and second wins, and also the number between my second and third wins. Looking at the letters in the spelling of the months, I have also noted the difference between the numbers of letters in the months of my first and second wins, and also the difference between those of the months of my second and third wins. All four numbers noted were the same, and if you knew that number then it would be possible to work out the months of my wins.

    What (in order of the wins) were those three months?

    [teaser2776]

     
    • Jim Randell 9:48 am on 18 February 2021 Permalink | Reply

      The largest difference in number of letters is 6 (“May” to “September”), so we don’t need to worry about time spans longer than this.

      This Python program runs in 52ms.

      Run: [ @repl.it ]

      from enigma import filter_unique, unpack, irange, join, printf
      
      # month names (in English)
      months = (
        'January', 'February', 'March', 'April', 'May', 'June',
        'July', 'August', 'September', 'October', 'November', 'December',
      )
      
      # month lengths
      ls = set(len(x) for x in months)
      M = max(ls) - min(ls)
      
      # map (<n>, <month1>) -> <month2>
      # where month1 and month2 are separated by n months
      # and month2 length is different from month1 by n
      d = dict()
      for (m1, name) in enumerate(months):
        l1 = len(name)
        for n in irange(0, M):
          m2 = (m1 + n + 1) % 12
          if abs(l1 - len(months[m2])) == n:
            d[(n, m1)] = m2
      
      # now look for elements (n, m1) -> m2 where (n, m2) -> m3
      rs = list()
      for ((n, m1), m2) in d.items():
        m3 = d.get((n, m2), None)
        if m3 is not None:
          ms = tuple(months[i] for i in (m1, m2, m3))
          rs.append((n, ms))
          printf("[n={n}: {ms}]", ms=join(ms, sep=' -> '))
      
      # find unambiguous solutions by n
      rs = filter_unique(rs, unpack(lambda n, ms: n)).unique
      
      # output solutions
      for (n, ms) in rs:
        printf("SOLUTION: n={n}, {ms}", ms=join(ms, sep=' -> '))
      

      Solution: The winning months are: February, July, December.

      This is the only set of months such that each adjacent pair has 4 months between them, and also differ by 4 letters.

      There are ambiguous solutions for values 1 and 5:

      1: August → October → December
      1: September → November → January

      5: May → November → May
      5: November → May → November

      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: