Updates from October, 2023 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:04 am on 24 October 2023 Permalink | Reply
    Tags:   

    Teaser 2664: Time ‘n’ again 

    From The Sunday Times, 13th October 2013 [link] [link]

    Time and again at school we would be given the exercise of changing a fraction into a decimal.

    This time the given fraction is in its simplest form and it equals a recurring decimal. In some places the digits have been consistently replaced by letters, with different letters used for different digits, but in four places the digits have merely been replaced by asterisks:

    TIME / **N** = .AGAINAGAIN…

    Numerically, what is the TIME?

    [teaser2664]

     
    • Jim Randell's avatar

      Jim Randell 9:06 am on 24 October 2023 Permalink | Reply

      The fraction:

      TIME / **N**

      is in its lowest form, but may also be written:

      AGAIN / 99999

      So it follows that the numerator and denominator of the first fraction can be scaled up by an integer value (k) to give the numerator and denominator of second fraction.

      And k must be a 1-digit divisor of 99999.

      The only possible values are k=3 or k=9, meaning

      **N** = 33333
      **N** = 11111

      The following run file executes in 74ms. (Internal runtime of the generated program is 1.8ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

--invalid="0,NT"
--invalid="2|4|5|6|7|8|9,N"  # N is 1 or 3

# TIME / NNNNN is in lowest terms
"gcd(TIME, NNNNN) = 1"

# TIME scales up to give AGAIN
"div(N * AGAIN, 9) = TIME"

--answer="TIME"

      Solution: TIME = 5269.

      And we have:

      TIME / **N** = .(AGAIN)… → 5269 / 11111 = 0.(47421)…

      Like

      • Hugo's avatar

        Hugo 1:36 pm on 24 October 2023 Permalink | Reply

        99999 = 3² × 41 × 271. 11111 = 41 × 271.
        41 is the smallest value of n such that multiples and submultiples of 1/n recur with period five.

        5269 = 11 × 479, and AGAIN = 47421 is 9 times as much.

        Like

  • Unknown's avatar

    Jim Randell 9:21 am on 19 October 2023 Permalink | Reply
    Tags:   

    Teaser 2643: Pack points 

    From The Sunday Times, 19th May 2013 [link] [link]

    Five cubs were awarded points for effort. Enid’s son and Master Smith had 17 points between them, Masters Jones and Robinson had a total of 16, Ivan and Master Robinson together had 14, and the two youngest of the cubs had a total of 13. John and Master Brown had a total of 12 points, Brenda’s son and Mike had 11 points between them, Ken and his best friend had a total of 10, Ann’s son and Debbie’s son together had 9, Christine’s son and Nigel had a total of 8, and Master Perkins and Debbie’s son together had 6.

    In alphabetical order of their mothers’ Christian names, what were the names of the five cubs (Christian name and surname)?

    [teaser2643]

     
    • Jim Randell's avatar

      Jim Randell 9:21 am on 19 October 2023 Permalink | Reply

      If we use variables A, B, C, D, E to correspond to the points allocated (according to mothers name), then we can allocate the first names and surnames of the cubs to the same set of variables to give us a set of simultaneous linear equations, which we can attempt to solve to give the points values.

      I used the [[ Matrix.linear() ]] solver from the enigma.py library to find assignments that give non-negative points values. (Although there are no further solutions if negative values are permitted).

      I also ensure that the pairings mentioned in the text all consist of distinct cubs. (Although, again, there are no further solutions if a pairing can refer to the same cub twice).

      The following Python program runs in 375ms.

      Run: [ @replit ]

      from enigma import (Matrix, subsets, catch, printf)

# suppose the points are: A, B, C, D, E (according to mothers name)
# then we can map the first and surnames to these values

# variables
vs = "ABCDE"

# a function to construct equations
def eq(vs, k, fn=Matrix.equation(vs)):
  r = fn(vs, k)
  assert {0, 1}.issuperset(r[0])  # reject coefficients that aren't 0 or 1
  return r

# validate point values
def valid(x):
  assert not x < 0
  return x

# for firstnames I, J, K, M, N
for (I, J, K, M, N) in subsets(vs, size=len, select='P'):

  # for surnames P, R, S, T (= Brown), U = (Jones)
  for (P, R, S, T, U) in subsets(vs, size=len, select='P'):

    # try to solve the equations
    r = None
    try:
      # construct equations
      eqs = [
        eq(['E', S], 17),  # Enid + Smith = 17
        eq([U, R], 16),  # Jones + Robinson = 16
        eq([I, R], 14),  # Ivan + Robinson = 14
        eq([J, T], 12),  # John + Brown = 12
        eq(['B', M], 11),  # Brenda + Mike = 11
        eq(['A', 'D'], 9),  # Ann + Debbie = 9
        eq(['C', N], 8),  # Christine + Nigel = 8
        eq([P, 'D'], 6),  # Perkins + Debbie = 6
      ]

      # solve the equations
      r = Matrix.linear(eqs, valid=valid)
    except (ValueError, AssertionError):
      pass
    if r is None: continue

    # check there is a pair = 13 (two youngest), and a pair = 10 (Ken + friend)
    v = dict(zip(vs, r))
    if not any(v[x] + v[K] == 10 for x in vs if x != K): continue
    if not any(v[x] + v[y] == 13 for (x, y) in subsets(vs, size=2)): continue

    # output solution
    mn = { 'A': 'Anne', 'B': 'Brenda', 'C': 'Christine', 'D': 'Debbie', 'E': 'Enid' }
    fn = { I: 'Ivan', J: 'John', K: 'Ken', M: 'Mike', N: 'Nigel' }
    sn = { P: 'Perkins', R: 'Robinson', S: 'Smith', T: 'Brown', U: 'Jones' }
    for k in vs:
      printf("{fn} {sn} = {v} points [{mn}]", mn=mn[k], fn=fn[k], sn=sn[k], v=v[k])
    printf()

      Solution: The names of the cubs are:

      Mike Smith = 7 points [Anne]
      Ivan Perkins = 4 points [Brenda]
      Ken Jones = 6 points [Christine]
      Nigel Brown = 2 points [Debbie]
      John Robinson = 10 points [Enid]

      So the youngest two are Mike and Ken (= 13 points in total), and Ivan must be Ken’s best friend (= 10 points in total).

      Like

  • Unknown's avatar

    Jim Randell 7:46 am on 15 October 2023 Permalink | Reply
    Tags:   

    Teaser 2644: Route canal 

    From The Sunday Times, 26th May 2013 [link] [link]

    Stephen is planning a 70-mile canal trip from the lock at Aytown to the lock at Beeswick, stopping at a pub at a lock over half way along the route. He has listed the number of miles from each lock to the next, the largest being the stretch from the pub to the next lock. He has also noted the distances from Aytown to the pub and from the pub to Beeswick. All the numbers that he has written down are different primes.

    Stephen can use his figures to work out the number of miles from any lock to any other. He’s found that, whenever that number of miles between locks is odd, then it is also a prime.

    What (in order) are the numbers of miles between consecutive locks?

    [teaser2644]

     
    • Jim Randell's avatar

      Jim Randell 7:46 am on 15 October 2023 Permalink | Reply

      This Python program runs in 55ms. (Internal runtime is 806µs).

      Run: [ @replit ]

      from enigma import (irange, primes, express, diff, cproduct, subsets, flatten, printf)

# decompose total <t> into different values from <ns>
def decompose(t, ns):
  if not ns: return
  for qs in express(t, ns, qs=(0, 1)):
    yield list(n for (n, q) in zip(ns, qs) if q > 0)

# check all odd distances are prime
def check(ds):
  for (i, j) in subsets(irange(len(ds)), size=2):
    d = sum(ds[i:j + 1])
    if d % 2 == 1 and d not in primes: return False
  return True

# consider possible distances from P to B (prime, < 35)
for d2 in primes.between(2, 34):
  # distance from A to P (prime, > 35)
  d1 = 70 - d2
  if d1 not in primes: continue

  # decompose the distances into individual sections
  for d2s in decompose(d2, list(primes.between(2, d2 - 1))):
    max_d = d2s[-1]
    for d1s in decompose(d1, list(diff(primes.between(2, max_d - 1), d2s))):

      # construct possible ordered sequences
      for (s1, s2) in cproduct(subsets(s, size=len, select='P') for s in (d1s, d2s[:-1])):
        ds = flatten([s1, [max_d], s2])
        if check(ds):
          # output solution
          printf("{ds}")

      Solution: The distances between consecutive locks (from A to B) are (in miles): 17, 13, 11, 19, 7, 3.

      Like

  • Unknown's avatar

    Jim Randell 12:31 pm on 12 October 2023 Permalink | Reply
    Tags:   

    Teaser 2656: Wrong adding 

    From The Sunday Times, 18th August 2013 [link] [link]

    Here is an addition sum in which digits have consistently been replaced by letters, with different letters used for different digits. The six-figure total is even:

    Unfortunately, once again I have made a mistake. In just one place in the display I have written an incorrect letter.

    What is the correct numerical value of the six-figure total?

    [teaser2656]

     
    • Jim Randell's avatar

      Jim Randell 12:31 pm on 12 October 2023 Permalink | Reply

      I’ve added the [[ bungled_sum() ]] solver (from Puzzle 56 etc.) to the enigma.py library as a class method on [[ SubstitutedSum ]], and also allowed it to be called from the command line.

      Using this solver we find there are two possibilities for as single letter mistake in the translation.

      The following command line executes in 270ms.

      Run: [ @replit ]

      % python3 -m enigma -r SubstitutedSum.bungled_sum "AGAIN + WRONG = ADDING"

            G
AGAIN + WRONI = ADDING / @[1,4] G -> I
14195 + 86759 = 100954 / A=1 D=0 G=4 I=9 N=5 O=7 R=6 W=8

                     G
AGAIN + WRONG = ADDINA / @[2,5] G -> A
16195 + 84756 = 100951 / A=1 D=0 G=6 I=9 N=5 O=7 R=4 W=8

      But we are told that in the original numerical sum the result is even, so we are looking at the first possibility.

      Solution: The result of the sum is 100954.

      The original sum was: 14195 + 86759 = 100954.

      And it should have been encoded as: AGAIN + WRONI = ADDING.

      Like

  • Unknown's avatar

    Jim Randell 9:48 am on 28 September 2023 Permalink | Reply
    Tags:   

    Teaser 2641: Exchange rate 

    From The Sunday Times, 5th May 2013 [link] [link]

    I am going on holiday to Tezarland. So at our local Bureau de Change I exchanged a three-figure number of pounds for Tezar dollars. From the pounds I paid a £12 fee and received a whole number of Tezar dollars for each remaining pound.

    This was an unremarkable transaction except that it was an exchange in more ways than one: the number of Tezar dollars I received was like the number of pounds that I started with but with the digits in the reverse order.

    How many Tezar dollars did I receive?

    [teaser2641]

     
    • Jim Randell's avatar

      Jim Randell 9:49 am on 28 September 2023 Permalink | Reply

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

      The following run files executes in 68ms. (Internal runtime of the generated program is 703µs).

      Run: [ @replit ]

      #! python3 -m enigma -rr

# (ABC - 12) * rate = CBA

SubstitutedExpression

--distinct=""

# rate is a whole number
"div(CBA, ABC - 12) > 0"

# answer is the number of dollars received
--answer="CBA"

      Solution: You received 612 Tezar dollars.

      Like

  • Unknown's avatar

    Jim Randell 12:12 pm on 26 September 2023 Permalink | Reply
    Tags: ,   

    Teaser 2653: Tough guys 

    From The Sunday Times, 28th July 2013 [link] [link]

    The SS Thomas More has two identical vertical masts mounted on the centre line of the deck, the masts being a whole number of feet tall and seven feet apart. Two straight guy ropes secure the top of each mast to a single anchor point on the centre line of the deck some distance forward of the masts. The total length of the two ropes is a whole number of feet, with one rope being two feet longer than the other.

    What is the height of the masts?

    [teaser2653]

     
    • Jim Randell's avatar

      Jim Randell 12:13 pm on 26 September 2023 Permalink | Reply

      If the ropes are length x and (x + 2), then the total length (= 2x + 2) is a whole number of feet, so x is a whole number of semi-feet (i.e. units of 6 inches).

      So let’s do everything in semi-feet.

      From the 2 right-angled triangles we have:

      r² = d² + h²
      (r + 4)² = (d + 14)² + h²
      ⇒
      r = (7d + 45) / 2

      And as r is an integer, d must be an odd integer.

      This Python program looks for the smallest viable solution:

      It runs in 58ms. (Internal runtime is 200µs)

      Run: [ @replit ]

      from enigma import (irange, inf, div, ircs, printf)

# generate candidate solutions
def generate():
  # consider d values
  for d in irange(1, inf, step=2):
    r = div(7 * d + 45, 2)
    h = ircs(r, -d)
    x = div(h, 2)
    if h is None or x is None: continue
    # return solution
    yield (d, r, h, x)

# find the first solution
for (d, r, h, x) in generate():
  printf("height = {x} ft [d={d} r={r} -> h={h}]")
  break

      Solution: The masts are 30 ft tall.

      The ropes are 30.5 ft and 32.5 ft long (giving a total rope length of 63 ft), and they are anchored 5.5 ft away from the nearest mast.

      The next solution is found when the masts are 540 ft tall, which seems a bit impractical.

      Analytically we are looking for integer solutions to the equation:

      h² = [(7d + 45) / 2]² − d²

      where h is an even integer, say h = 2z (so z is the mast height in feet):

      (2z)² = (45/4)(d + 7)² − 45
      16z² − 45(d + 7)² = −180

      writing X = 4z (= 2h), Y = d + 7 we get a form of Pell’s equation:

      X² − 45 Y² = −180

      And we can use the pells.py module (from the py-enigma-plus repository – see: Teaser 2994) to quickly find larger solutions to the original equation:

      from enigma import (div, arg, ifirst, printf)
import pells

# generate (h, d, r, height) values
def solve():
  # find solutions to: 16z^2 - 45(d + 7)^2 = -180
  for (z, d) in pells.diop_quad(16, -45, -180):
    d -= 7
    r = div(7 * d + 45, 2)
    if r and r > 0 and d > 0 and z > 0:
      yield (2 * z, d, r, z)

# find the first N solutions
N = arg(8, 0, int)
for (i, (h, d, r, height)) in enumerate(ifirst(solve(), N), start=1):
  printf("[{i}] h={h} d={d} r={r} -> height = {height} ft")

      % time python3 teaser2653pells.py 8
[1] h=60 d=11 r=61 -> height = 30 ft
[2] h=1080 d=315 r=1125 -> height = 540 ft
[3] h=19380 d=5771 r=20221 -> height = 9690 ft
[4] h=347760 d=103675 r=362885 -> height = 173880 ft
[5] h=6240300 d=1860491 r=6511741 -> height = 3120150 ft
[6] h=111977640 d=33385275 r=116848485 -> height = 55988820 ft
[7] h=2009357220 d=599074571 r=2096761021 -> height = 1004678610 ft
[8] h=36056452320 d=10749957115 r=37624849925 -> height = 18028226160 ft
python3 teaser2653pells.py 8  0.06s user 0.03s system 89% cpu 0.098 total

      Like

    • Frits's avatar

      Frits 7:49 pm on 26 September 2023 Permalink | Reply 

       
# 16z^2 - 45(d + 7)^2 = -180 
# with X = 4z (= 2h), Y = d + 7 we get a form of Pell's equation:
# X^2 - 45 Y^2 = -180 
# the first soltion being the trivial one, X=0, Y=2 

# Using Brian's method: https://brg.me.uk/?page_id=1468
#
# These solutions can also be generated recursively using:
# x(n+1) = 9 x(n) + 60 y(n)
# y(n+1) = 4/3 x(n) + 9 y(n)

x, y = 0, 2
for n in range(8):
  x, y = 9 * x + 60 * y, (4 * x) // 3 + 9 * y
  print(f"[{n + 1}] h={x // 2} d={y - 7} r={(7 * (y - 7) + 45 ) // 2} "
        f"-> height = {x // 4} ft")

      Like

  • Unknown's avatar

    Jim Randell 12:33 pm on 19 September 2023 Permalink | Reply
    Tags: ,   

    Teaser 2642: New world order 

    From The Sunday Times, 12th May 2013 [link] [link]

    In maths class Pat has been learning about progressions from his “New World” text book. The book has three sections, namely “Arithmetic”, “Algebra” and “Geometry” which overall run from page 1 to page 500 inclusive — with each section starting on a new page. The geometry section is over twice as long as the arithmetic section.

    As an exercise Pat calculated the sum of the page numbers in each section and he was surprised to find that the sum of the page numbers in “Algebra” was double that of the sum of the page numbers in “Geometry”.

    How many pages are there in the “Arithmetic” section?

    [teaser2642]

     
    • Jim Randell's avatar

      Jim Randell 12:34 pm on 19 September 2023 Permalink | Reply

      The total sum of all the page numbers = T = tri(500).

      If the Arithmetic section is pages 1 .. x, the Algebra section pages (x + 1) .. y, and the Geometry section pages (y + 1) .. 500, then the sums of the page numbers in each section are:

      Ar = tri(x)
      Al = tri(y) − tri(x)
      Ge = T − tri(y)
      ⇒
      tri(y) = T − Ge

      and:

      Al = 2 Ge
      ⇒
      Ge = (T − Ar) / 3

      So, by choosing a value for x, we can calculate the values of Ar, Al, Ge and hence y.

      This Python program runs in 55ms. (Internal runtime is 267µs).

      Run: [ @replit ]

      from enigma import (irange, tri, div, is_triangular, printf)

# Ar: sum(1 .. x) = tri(x)
# Al: sum(x + 1 .. y) = tri(y) - tri(x)
# Ge: sum(y + 1 .. 500) = tri(500) - tri(y)
#
# Al = 2 * Ge

# total sum of all pages
T = tri(500)

# consider the end page for arithmetic = x
for x in irange(2, 165):
  Ar = tri(x)
  Ge = div(T - Ar, 3)
  if Ge is None: continue
  # calculate y
  y = is_triangular(T - Ge)
  if y is None or not x < y < 500: continue
  if not (500 - y > 2 * x): continue
  # output solution
  printf("Ar = 1..{x}; Al = {x1}..{y}; Ge = {y1}..500", x1=x + 1, y1=y + 1)

      Solution: There are 45 pages in the Arithmetic section.

      So the sections are:

      Arithmetic: pages 1 – 45 (= 45 pages); sum = 1035
      Algebra: pages 46 – 409 (= 364 pages); sum = 82810 (= Geometry × 2)
      Geometry: pages 410 – 500 (= 91 pages); sum = 41405

      Like

  • Unknown's avatar

    Jim Randell 10:12 am on 12 September 2023 Permalink | Reply
    Tags:   

    Teaser 2651: Parsnip Farm 

    From The Sunday Times, 14th July 2013 [link] [link]

    On Parsnip Farm there was a triangular field with one of its boundaries running north to south. From that boundary’s southernmost point Farmer Giles built a fence in an easterly direction, thus partitioning the field into two smaller triangular fields, with the area of the northern field being forty per cent of the area of the southern field. Each side of each field was a whole number of furlongs in length, one of the sides of the southern field being twenty-five furlongs in length.

    What are the lengths of the other two sides of the southern field?

    [teaser2651]

     
    • Jim Randell's avatar

      Jim Randell 10:12 am on 12 September 2023 Permalink | Reply

      If the area of the original field is A, then it is split such that the northern field has an area N = (2/7)A and the southern field S = (5/7)A.

      The boundaries of N are all integers and so form a Pythagorean triple (x, y, z).

      And we can expand the northern field by a factor of f until its hypotenuse exactly covers the boundary of the original field, and we get this:

      The we can then write the area of the original field in two ways:

      A = (7/2)N = 7xy / 4
      A = fxy / 2
      ⇒
      f = 7/2

      And we can calculate the unknown sides of S:

      z′ = (f − 1)z = 5z/2
      y′ = hypot(7x/2, 5y/2) = hypot(7x, 5y) / 2

      This Python program runs in 58ms. (Internal runtime is 334µs).

      Run: [ @replit ]

      from enigma import (pythagorean_triples, div, ihypot, ordered, printf)

for (a, b, z) in pythagorean_triples(100):
  z_ = div(5 * z, 2)
  if z_ is None: continue
  N = ordered(a, b, z)
  for (x, y) in [(a, b), (b, a)]:
    y_ = div(ihypot(7 * x, 5 * y), 2)
    if y_ is None: continue
    S = ordered(x, z_, y_)
    if 25 in S:
      # output solution
      printf("N = {N}; S = {S}")

      Solution: The other two sides of the southern field are 6 and 29 furlongs.

      N is a (6, 8, 10) triangle, (area = 24 square furlongs ≈ 0.97 sq km).

      S is a (6, 25, 29) triangle, (area = 60 square furlongs ≈ 2.43 sq km).

      So the original field was a (8, 29, 35) triangle, (area = 84 square furlongs ≈ 3.40 sq km).

      Like

    • Frits's avatar

      Frits 5:44 pm on 12 September 2023 Permalink | Reply

      Avoiding imports.

       
is_square = lambda n: int(rt := n**.5) == rt

# generate Pythagoren triples for a fixed hypothenuse
def triples(h):
  sqs = {i * i for i in range(1, h)}
  return [(int(s1**.5), int(s2**.5)) for s1 in sqs 
           if (s2 := h**2 - s1) >= s1 and s2 in sqs]
  
side = 25

# can x be 25?  
# then f.x = 87.5, y' can never be a whole number  (f = 3.5)
# if other side (2.5y) is k.0 or k.5, so x != 25

# can y' be 25?
for c, d in triples(side): 
   # are these lenghts multiples of 2.5 and 3.5?
  x, y = -1, -1
  if (c % 2.5 == 0 and d % 3.5 == 0):
    y, x = c // 2.5, d // 3.5    
  if ((c % 3.5 == 0 and d % 2.5 == 0)):
    x, y = c // 3.5, d // 2.5    
  if x == -1: continue
  
  # y' can be 25
  if is_square(z2 := x**2 + y**2):
    z = int(z2**.5)
    if z % 2 == 0:
      print(f"answer {int(x)} and {int(2.5 * z)} furlongs")
  
# can z' be 25?
if side % 5: exit(0)
z = int(side * 2 / 5)

ts = triples(z)
# determine z'
for x, y in ts + [x[::-1] for x in ts]:
  if is_square(y1 := 3.5**2 * x**2 + 2.5**2 * y**2):
    print(f"answer {int(x)} and {int(y1**.5)} furlongs")

      Like

  • Unknown's avatar

    Jim Randell 9:28 am on 7 September 2023 Permalink | Reply
    Tags: ,   

    Teaser 2645: One square 

    From The Sunday Times, 2nd June 2013 [link] [link]

    I have consistently replaced digits by letters, using different letters for different digits, and in this way I have found that:

    (FIVE − FOUR)² = ONE

    Now, if I were to tell you whether or not THREE is divisible by 3, and whether or not FOUR is divisible by 4, then you could work out FIVE.

    What number is FIVE?

    Note: As originally published this puzzle has no solution (and was reproduced in this flawed form in the book The Sunday Times Brain Teasers Book 2 (2020)).

    However the additional information that “FIVE is greater than FOUR” allows the published answer to be found.

    [teaser2645]

     
    • Jim Randell's avatar

      Jim Randell 9:29 am on 7 September 2023 Permalink | Reply

      With the extra condition that “FIVE is greater than FOUR” we find the published answer.

      So maybe the setter intended to say: “… I have found that FIVE − FOUR is a positive number, whose square is ONE” (or: “the square root of ONE is equal to FIVE – FOUR“).

      This Python program runs in 147ms.

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, group, unpack, item, peek, seq2str, printf)

# the alphametic problem (with an additional condition)
p = SubstitutedExpression(
  ["sq(FIVE - FOUR) = ONE", "FIVE > FOUR"],
  answer="(THREE, FOUR, FIVE)",
)

# collect the answers, and record values of FIVE (= item(2))
# by (THREE divisible by 3, FOUR divisible by 4).
fn = unpack(lambda n3, n4, n5: (int(n3 % 3 == 0), int(n4 % 4 == 0)))
d = group(p.answers(verbose=0), by=fn, f=item(2), fn=set)

# output the collections, and find the solution
for (k, vs) in d.items():
  if len(vs) == 1:
    printf("(d3, d4) = {k} -> FIVE = {v} [*** SOLUTION ***]", v=peek(vs))
  else:
    printf("(d3, d4) = {k} -> FIVE = {vs}", vs=seq2str(vs, sort=1, enc="{}"))

      Solution: FIVE = 5901.

      If we are told THREE is not divisible by 3, and FOUR is divisible by 4, then the only possible assignments are:

      FIVE = 5901, FOUR = 5872, ONE = 841, THREE = 36211
      FIVE = 5901, FOUR = 5872, ONE = 841, THREE = 63211

      Any of the other of the divisibility possibilities lead to multiple candidate values for FIVE, so this gives the answer.

      However if we do not require FIVE > FOUR, then we find many further possible solutions to the alphametic problem:

      FIVE = 1496, FOUR = 1520, ONE = 576, THREE = 38066
      FIVE = 1496, FOUR = 1520, ONE = 576, THREE = 83066

      FIVE = 3791, FOUR = 3820, ONE = 841, THREE = 56011
      FIVE = 3791, FOUR = 3820, ONE = 841, THREE = 65011

      FIVE = 5791, FOUR = 5820, ONE = 841, THREE = 36011
      FIVE = 5791, FOUR = 5820, ONE = 841, THREE = 63011

      FIVE = 6791, FOUR = 6820, ONE = 841, THREE = 35011
      FIVE = 6791, FOUR = 6820, ONE = 841, THREE = 53011

      FIVE = 8496, FOUR = 8520, ONE = 576, THREE = 13066
      FIVE = 8496, FOUR = 8520, ONE = 576, THREE = 31066

      And so we cannot work out the value of FIVE.

      We can see these candidates by removing the [[ "FIVE > FOUR" ]] on line 5 of the program.

      Like

      • Frits's avatar

        Frits 12:32 pm on 8 September 2023 Permalink | Reply

        The reported run time 147ms was probably with PyPy (I get 423ms with CPython).

        With this program CPython performs better than PyPY.

        from enigma import (SubstitutedExpression, group, unpack, item, peek, seq2str, printf)

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  if d == 0: vs.update('OFT')
  # if E is odd then R is even and if E is even then R is even as well
  if d % 2: vs.update('R')
  # a number that ends in 2, 3, 7 or 8 is not a perfect square
  if d in {2, 3, 7, 8}: vs.update('E')
  d2i[d] = vs
 
# the alphametic problem (with an additional condition)
p = SubstitutedExpression(
  [ # FIVE > FOUR
    "I > O", 
    "sq(IVE - OUR) = ONE",],
  answer="(FOUR, FIVE, THREE)",
  #answer="(FOUR, FIVE, \
  #         R + 2*E + sum(i for i in range(10) if i not in {F,I,V,E,O,U,R,N}))",
  d2i=d2i,
  verbose=0
)
 
# collect the answers, and record values of FIVE (= item(1))
# by (THREE divisible by 3, FOUR divisible by 4).
fn = unpack(lambda n4, n5, n3: (int(n3 % 3 == 0), int(n4 % 4 == 0)))
d = group(p.answers(), by=fn, f=item(1), fn=set)
 
# output the collections, and find the solution
for (k, vs) in d.items():
  if len(vs) == 1:
    printf("(d3, d4) = {k} -> FIVE = {v} [*** SOLUTION ***]", v=peek(vs))
  else:
    printf("(d3, d4) = {k} -> FIVE = {vs}", vs=seq2str(vs, sort=1, enc="{}"))

        Like

        • Jim Randell's avatar

          Jim Randell 12:13 pm on 9 September 2023 Permalink | Reply

          @Frits: Yes, 147ms was with PyPy 7.3.12. With CPython 3.12 I get an overall runtime of 255ms.

          Although, if you are solving the rescued problem you can use the expression [[ "is_square(ONE) + FOUR = FIVE" ]] which is a bit faster, and it is even faster to use [[ "is_square(ONE) + OUR = IVE" ]] (93ms with CPython 3.12).

          Like

  • Unknown's avatar

    Jim Randell 9:09 am on 5 September 2023 Permalink | Reply
    Tags:   

    Teaser 2637: Powerful team 

    From The Sunday Times, 7th April 2013 [link] [link]

    George and Martha support the local football team. The squad is numbered from 1 to 22, with 11 playing at any one time and the remaining 11 sitting on the bench. At the start of this week’s match Martha commented that among their 11 players on the pitch there were no three consecutive numbers, and that the same was true of the 11 sitting on the bench. She also commented that the sum of the 11 players’ numbers on the pitch was a perfect square. At half-time one substitution was made and in the second half George noted that all that Martha had said was still true, but now the perfect square was higher.

    What (in increasing order) were the numbers of the 11 players in the first half?

    [teaser2637]

     
    • Jim Randell's avatar

      Jim Randell 9:10 am on 5 September 2023 Permalink | Reply

      This Python program runs in 349ms. (Internal runtime is 279ms).

      Run: [ @replit ]

      from enigma import (irange, subsets, tuples, is_square, diff, cproduct, update, printf)

# available players
players = list(irange(1, 22))

# check for <k> consecutive numbers in sorted list <ns>
is_consecutive = lambda ns, k: any(t[0] + k == t[-1] + 1 for t in tuples(ns, k))

# choose 11 of the players to form the team
for ps in subsets(players, size=11):
  # the sum is a perfect square
  s = sum(ps)
  if not is_square(s): continue
  # no 3 consecutive numbers are used
  if is_consecutive(ps, 3): continue

  # and the unused players
  xs = diff(players, ps)
  # no 3 consecutive numbers
  if is_consecutive(xs, 3): continue

  # substitute a player from ps with one from xs
  for ((i, p), (j, x)) in cproduct([enumerate(ps), enumerate(xs)]):
    s_ = s - p + x
    if not (s_ > s and is_square(s_)): continue
    # perform the substitution
    ps_ = sorted(update(ps, [(i, x)]))
    if is_consecutive(ps_, 3): continue
    xs_ = sorted(update(xs, [(j, p)]))
    if is_consecutive(xs_, 3): continue

    # output solution
    printf("{ps} = {s} -> {ps_} = {s_}")

      Solution: The players in the first half were: 1, 2, 4, 5, 7, 8, 10, 12, 14, 17, 20.

      The sum of the numbers in the first half is 100 (= 10²).

      In the second half player 1 was substituted by player 22, causing the sum to increase to 121 (= 11²).

      We can easily see that the smallest possible square is 100, and the largest possible square is 144.

      The difference in the squares is also the difference in the numbers of the substituting and substituted players.

      So the only possible difference is 21, going from 100 → 121.

      And the substitution must be that player 1 was substituted by player 22.

      Like

  • Unknown's avatar

    Jim Randell 8:53 am on 29 August 2023 Permalink | Reply
    Tags:   

    Teaser 2638: Digilist 

    From The Sunday Times, 14th April 2013 [link] [link]

    I have written down a list of positive whole numbers in ascending order. Overall they use each of the digits 0 to 9 exactly once. There is more than one even number in the list, and the majority of the numbers are primes. The final number in the list is a perfect square and it is the sum of all the other numbers in the list.

    What is my list of numbers?

    [teaser2638]

     
    • Jim Randell's avatar

      Jim Randell 8:56 am on 29 August 2023 Permalink | Reply

      There is more than 1 even number on the list (i.e. at least 2), and the majority of numbers on the list are primes.

      There is only one even prime, so there must be at least 2 primes on the list, so the list must have at least 3 numbers.

      If the final square had 5 digits there would only be 5 digits remaining to form at least 2 numbers that sum to a 5 digit number, and this is not possible.

      So we only need to consider results that are 2, 3, or 4 digits.

      My first program was straightforward, but a bit slow (execution time was 1.9s).

      This Python program constructs an alphametic problem by allocating 2, 3 or 4 digits to the result of the sum, and then chops the remaining digits into numbers that make up the terms. It constructs a corresponding alphametic puzzle, and then uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve that.

      It runs in 128ms.

      Run: [ @replit ]

      from enigma import (
  SubstitutedExpression, irange, express, str_upper, tuples,
  sprintf as f, join, printf
)

# construct appropriate alphametic words
def words(qs, ds, k, syms=str_upper):
  for (q, d) in zip(qs, ds):
    # return <q> <d>-length words
    for _ in irange(1, q):
      yield syms[:d]
      syms = syms[d:]
  # and a <k>-length result
  yield syms[:k]

# the result is a <k> digit square
for k in [2, 3, 4]:
  # form numbers from the remaining digits
  ds = list(irange(1, k))
  for qs in express(10 - k, ds):
    if qs[-2:] == [0, 0]: continue
    # make appropriate length alphametic words for the numbers
    ss = list(words(qs, ds, k))

    # the alphametic puzzle sum
    sq = ss.pop(-1)
    expr = f("{ss} = {sq}", ss=join(ss, sep=" + "))
    # additional constraints
    exprs = [
      f("is_square({sq})"),  # result is a square
    ]
    # remove duplicates (same length symbols are ordered)
    for (x, y) in tuples(ss, 2):
      if len(x) == len(y):
        exprs.append(f("{x} < {y}", x=x[0], y=y[0]))
    # now add in expressions over the entire list
    ss.append(sq)
    ns = join(ss, sep=", ", enc="[]")
    exprs.extend([
      # more than 1 of the numbers is even
      f("sum(n % 2 == 0 for n in {ns}) > 1 "),
      # the majority of the numbers are prime
      f("sum(is_prime(n) for n in {ns}) > {t}", t=len(ss) // 2),
    ])

    # make a solver for the puzzle
    p = SubstitutedExpression.split_sum(
      expr, extra=exprs,
      d2i={ 0: list(s[0] for s in ss) }, # all numbers are positive
      template=expr,
    ).solver()

    # solve the puzzle
    for s in p.solve(verbose=0):
      # output the sum
      printf("{s}", s=p.substitute(s, expr))

      Solution: The numbers are: 2, 3, 80, 491, 576.

      And:

      2 + 3 + 80 + 491 = 576

      There is more than one even number (2, 80, 576), and 3 of the 5 numbers are prime (2, 3, 491).

      The wording of the puzzle excludes 0 from being on the list, but if it were allowed we would have an alternative solution of:

      0 + 2 + 83 + 491 = 576

      Which has the same square total.

      There are also two further solutions that have the same square total (although a different one to above) but have fewer than 2 even numbers on the list:

      3 + 5 + 41 + 680 = 729
      3 + 5 + 80 + 641 = 729

      Like

  • Unknown's avatar

    Jim Randell 8:46 am on 22 August 2023 Permalink | Reply
    Tags:   

    Teaser 2635: Three sisters 

    From The Sunday Times, 24th March 2013 [link] [link]

    In Shakespeare’s less well-known prequel, King Lear shared all of his estate amongst his three daughters, each daughter getting a fraction of the estate. The three fractions, each in their simplest form, had numerators less than 100 and had the same denominators. Cordelia got the least, with Regan getting more, and Goneril the most (but her share was less than three times Cordelia’s). Each of the three fractions gave a decimal which recurred after three places (as in 0.abcabc…) and each digit from 1 to 9 occurred in one of the three decimals.

    What were the three fractions?

    [teaser2635]

     
    • Jim Randell's avatar

      Jim Randell 8:46 am on 22 August 2023 Permalink | Reply

      The recurring decimal 0.(abc)… is a representation of the fraction abc/999.

      But the three fractions we are dealing with can all be reduced to fractions with a 2-digit numerator, and a common denominator.

      So the common denominator must be a divisor of 999.

      This Python program runs in 54ms. (Internal runtime is 2ms)

      Run: [ @replit ]

      from enigma import (divisors, decompose, gcd, recurring, join, printf)

# return viable repetends
def repetend(n, d):
  r = recurring(n, d)
  return (None if r.nr else r.rr)

# consider possible denominator values 3 < d < 100
for d in divisors(999):
  if d < 4: continue
  if d > 297: break

  # calculate ascending splits of the denominator
  for (C, R, G) in decompose(d, 3, increasing=1, sep=1, min_v=1, max_v=99):
    # G's share is less than 3 times C's
    if not (G < 3 * C): continue
    # check fractions are in lowest terms
    if any(gcd(n, d) != 1 for n in (C, R, G)): continue

    # find the repetends
    reps = list(repetend(n, d) for n in (C, R, G))
    if None in reps: continue
    # check the digits used
    ds = join(reps)
    if '0' in ds or len(set(ds)) < 9: continue

    # output solution
    (rC, rR, rG) = reps
    printf("C = {C}/{d} = 0.({rC})...; R = {R}/{d} = 0.({rR})...; G = {G}/{d} = 0.({rG})...")

      Solution: The fractions are: Cordelia = 6/37, Reagan = 14/37, Goneril = 17/37.

      As decimals:

      C = 0.(162)…
      R = 0.(378)…
      G = 0.(459)…

      Like

  • Unknown's avatar

    Jim Randell 8:33 am on 17 August 2023 Permalink | Reply
    Tags: ,   

    Teaser 2634: Good company 

    From The Sunday Times, 17th March 2013 [link] [link]

    Each year at this time Pat’s company gives its staff a bonus to help them “drown their shamrocks” on the Irish national holiday. A total of £500 is shared out amongst all six employees (five men and the manager Kate) whose numbers of years of service consist of six consecutive numbers. Each man gets the same whole number of pounds for each year of his service and Kate gets a higher whole number of pounds for each year of her service. This means that, although Pat does not get the lowest bonus, he does get £20 less than Kate — even though he has served the company for a year longer than her.

    How much does Pat get?

    [teaser2634]

     
    • Jim Randell's avatar

      Jim Randell 8:33 am on 17 August 2023 Permalink | Reply

      This Python program runs in 51ms. (Internal runtime is 421µs).

      Run: [ @replit ]

      from enigma import (irange, tuples, update, printf)

# consider possible consecutive years of service (up to 50)
for ys in tuples(irange(1, 50), 6):
  # total years service
  t = sum(ys)
  # choose a basic bonus amount
  for b in irange(1, 23):
    # remaining bonus
    r = 500 - t * b
    if not r > 0: break
    # make the list of basic bonuses
    bs = list(y * b for y in ys)
    # kate (not first or last) gets the remaining bonus
    for i in (1, 2, 3, 4):
      y = ys[i]
      if r % y != 0: continue
      # kate's bonus is 20 more than pat's
      (k, p) = (bs[i] + r, bs[i + 1])
      if k == p + 20:
        # output solution
        printf("pat = {p}, kate = {k} [years = {ys}, bonus = {bs}]", bs=update(bs, [(i, k)]))

      Solution: Pat’s bonus was £ 108.

      The six employees have worked at the company for 4, 5, 6, 7, 8, 9 years. With Kate having worked 8 years and Pat 9 years.

      Each of the non-managers receives a £12/year bonus:

      4 → £48
      5 → £60
      6 → £72
      7 → £84
      9 → £108 (Pat)

      Kate receives a £16/year bonus:

      8 → £128

      Like

    • Frits's avatar

      Frits 1:08 pm on 17 August 2023 Permalink | Reply 

      # basic bonus amount: B,          we have B < 500 / (6 + 15)
for B in range(1, 24):
  # years of service Y, ..., Y+5, we have (6 * Y + 15) * B < 500
  for Y in range(1, int((500 / B - 15) / 6) + 1):
    # index Kate in Y, ..., Y+5: I   (if I = 0 then Pat gets the lowest bonus)
    for I in range(1, 5):
      # Pat does get 20 pounds less than Kate,  K.(Y + I) - B.(Y + I + 1) = 20
      K, r = divmod(20 + B * (Y + I + 1), Y + I)
      if r: continue
      # a total of 500 pounds is shared out amongst all six employees
      if sum(B * (Y + i) if i != I else K * (Y + I) for i in range(6)) != 500:
        continue
      print(f"answer: {(Y + I + 1) * B} pounds")

      or

      # basic bonus amount: B,          we have B < 500 / (6 + 15)
for B in range(1, 24):
  # years of service Y, ..., Y+5, we have (6 * Y + 15) * B < 500
  for Y in range(1, int((500 / B - 15) / 6) + 1):
    # index Kate in Y, ..., Y+5: I   (if I = 0 then Pat gets the lowest bonus)
    sofar = sum(B * (Y + i) for i in range(6))
   
    # (Y + I).(K - B) = 500 - sofar,  I = index Kate in list years of service 
    for K, I in [(B + d[0], i) for i in range(1, 5) 
                 if not (d := divmod(500 - sofar, Y + i))[1]]:
      # Pat does get 20 pounds less than Kate
      if K * (Y + I) - B * (Y + I + 1) != 20: continue
      print(f"answer: {(Y + I + 1) * B} pounds")

      Like

  • Unknown's avatar

    Jim Randell 8:05 am on 8 August 2023 Permalink | Reply
    Tags:   

    Teaser 2639: Prime number 

    From The Sunday Times, 21st April 2013 [link] [link]

    I have given each letter of the alphabet a different whole-number value between 1 and 99 so that each letter represents one or two digits. In this way, for example, a three- letter word can represent a number of three, four, five or six digits. With my values it turns out that:

    PRIME = NUMBER.

    Furthermore, rather fortuitously, each letter used in that display has a value equal to an odd prime number.

    What is the number PRIME?

    [teaser2639]

     
    • Jim Randell's avatar

      Jim Randell 8:06 am on 8 August 2023 Permalink | Reply

      We have encountered a puzzle similar to this before (see: Teaser 2628), and I wrote some generic code to solve that puzzle, which can also be used to solve this puzzle.

      The following Python 3 program runs in 64ms. (Internal runtime is 8.8ms).

      Run: [ @replit ]

      from enigma import (primes, subsets, filter2, group, item, update, remove, translate, join, printf)

# solve() routine copied from teaser2628r.py:

# replace letters in <X>, <Y> with values from <ns>, so the strings formed are equal
# <ns> groups values by their final digit
# return the map: letter -> value
def _solve(X, Y, ns, d):
  # are we done?
  if X == Y:
    yield d
  elif X and Y:
    # remove any common suffix
    while X and Y and X[-1] == Y[-1]: (X, Y) = (X[:-1], Y[:-1])
    if not (X and Y): return
    # split the final characters into numeric / non-numeric
    (nums, nons) = filter2((lambda x: x.isdigit()), [X[-1], Y[-1]])
    # different final numerics = failure
    if len(nums) > 1: return
    # choose values with the same final digit
    # if there is a numeric value use that, otherwise use the groups
    for k in (nums or ns.keys()):
      ss = ns.get(k, [])
      for vs in subsets(ss, size=len(nons), select='P'):
        # update the strings
        d_ = update(d, nons, vs)
        (X_, Y_) = (translate(x, d_, embed=0) for x in (X, Y))
        ns_ = update(ns, [(k, remove(ss, *vs))])
        # and solve for the translated strings
        yield from _solve(X_, Y_, ns_, d_)

# replace letters in <X>, <Y>
def solve(X, Y, ns):
  # group values by their final digit
  ns = group(map(str, ns), by=item(-1), fn=set)
  # and call the solver
  return _solve(X, Y, ns, dict())

# now solve the puzzle:

# possible numeric values
ns = list(primes.irange(3, 99))

# word values we are interested in
(w1, w2) = ("PRIME", "NUMBER")

# turn a word into a string
fmt = lambda w, sep=':': join((d.get(x, x) for x in w), sep=sep)

# solve the puzzle
for d in solve(w1, w2, ns):
  # output solution
  printf("{w1}={f1} {w2}={f2}", f1=fmt(w1), f2=fmt(w2))

      Solution: PRIME = 531713717.

      We have:

      PRIME = 53:17:13:71:7
      NUMBER = 5:31:71:3:7:17

      Like

      • Frits's avatar

        Frits 7:54 pm on 8 August 2023 Permalink | Reply

        One performance improvement could be to add:

        vars2 = len(nons) == 2

        and

        if vars2 and len(vs[0] + vs[1]) != 3: continue

        I have more performance optimisations but this seems to be the one with the most impact.

        Like

        • Jim Randell's avatar

          Jim Randell 8:42 am on 9 August 2023 Permalink | Reply

          @Frits: To keep things generic we could just skip selections of 2 values where they have the same length. That is a simple change.

          More complicated would be to store candidate values by the final digit and the number of values required and populate it only with different length pairs, and that would avoid the recalculation at each step.

          Like

    • Frits's avatar

      Frits 12:59 pm on 8 August 2023 Permalink | Reply

      Without much analysis (except that both PRIME and NUMBER must have the same trailing digit F).

       
from enigma import SubstitutedExpression, join

# build string of valid numbers
P = [3, 5, 7]
P += [x for x in range(11, 100, 2) if all(x % p for p in P)]
P = "{" + join(P, ",") + "}" 

# check for same leading digits
leading = lambda s1, s2: all(x == y for x, y in zip(join(s1), join(s2)))
# check for same trailing digits
trailing = lambda s1, s2: all(x == y for x, y in zip(join(s1)[::-1], join(s2)[::-1]))
 
# the alphametic puzzle
p = SubstitutedExpression(
  [
    #      PRIME             NUMBER  
    # PQ RF IJ MA EF == NO UV MA BC EF RF"
    
    # first check from the back
    "EF in @primes",
    "RF in @primes and len(s2 := {EF, RF}) == 2",
    "trailing([EF], [RF])",
    
    "MA in @primes and len(s3 := s2 | set([MA])) == 3",
    "trailing([MA, EF], [EF, RF])",
    
    # now check from the front
    "PQ in @primes and len(s4 := s3 | set([PQ])) == 4",
    "NO in @primes and len(s5 := s4 | set([NO])) == 5",
    "leading([PQ, RF], [NO])",

    "UV in @primes and len(s6 := s5 | set([UV])) == 6",
    "leading([PQ, RF], [NO, UV, MA])",
    
    "IJ in @primes and len(s7 := s6 | set([IJ])) == 7",
    "leading([PQ, RF, IJ], [NO, UV, MA])",
    
    "BC in @primes and BC not in s7",
    
    # check all digits
    "join(@prime) == join(@number)",
  ],
  answer="join(@prime)",
  d2i=dict([(k, "QFJAOVC") for k in [0, 2, 4, 6, 8]]),
  macro=dict([("primes", P)] + [("prime", "[PQ, RF, IJ, MA, EF]")] + \
             [("number", "[NO, UV, MA, BC, EF, RF]")]
  ),
  distinct="",
  env=dict(leading=leading, trailing=trailing),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for ans in p.answers():
  print(f"answer: {ans}")

      Like

    • Jim Randell's avatar

      Jim Randell 4:46 pm on 8 August 2023 Permalink | Reply

      Here is a run file for this puzzle.

      It would be fairly straightforward to write a program that used this format for a generic solution.

      #! python3 -m enigma -rr

SubstitutedExpression

--base=100

# digits = primes.between(3, 99)
--digits="3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97"

# check the concatenations match (working from the end)
--code="check = lambda xs, ys, **kw: zip_eq(join(xs), join(ys), reverse=1, **kw)"

# check the full strings
"check([P, R, I, M, E], [N, U, M, B, E, R], strict=1)"

# for performance check the partial strings
"check([E], [R])"
"check([M, E], [E, R])"
"check([I, M, E], [B, E, R])"
"check([R, I, M, E], [M, B, E, R])"
"check([P, R, I, M, E], [U, M, B, E, R])"

--template=""
--answer="((P, R, I, M, E), (N, U, M, B, E, R))"

# zip_eq(..., strict=1) only works in Python 3.10+
--code="require('sys.version', '3.10')"

      Like

  • Unknown's avatar

    Jim Randell 9:28 am on 3 August 2023 Permalink | Reply
    Tags:   

    Teaser 2640: Megan’s number 

    From The Sunday Times, 28th April 2013 [link] [link]

    I had ten cards and each was labelled with a different digit. Megan chose three of these cards and arranged them to give a number. Beth then chose some of the remaining cards and also arranged them as a number. Finally Jan took some, or all, of the remaining cards and produced her number.

    If Megan multiplied her number by its last digit, she would get Beth’s number, and if Megan multiplied her number by its first digit she would get Jan’s number.

    Who has the biggest number and what is it?

    [teaser2640]

     
    • Jim Randell's avatar

      Jim Randell 9:29 am on 3 August 2023 Permalink | Reply

      It is straightforward to just consider possible 3-digit numbers for Megan. (Although we could reduce the number of candidates with some analysis).

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

      Run: [ @replit ]

      from enigma import (irange, is_duplicate, printf)

# Megan's number has 3 different digits
for M in irange(100, 999):
  # Beth's number
  B = M * (M % 10)
  # J's number
  J = M * (M // 100)
  # all digits are distinct
  if is_duplicate(M, B, J): continue

  # who has the maximum number?
  d = { M: 'M', B: 'B', J: 'J' }
  m = max(d.keys())
  printf("max = {x} = {m} [M={M} B={B} J={J}]", x=d[m])

      Solution: Beth’s number is the largest. It is 819.

      The numbers are:

      M = 273
      B = 273 × 3 = 819
      J = 273 × 2 = 546

      Like

  • Unknown's avatar

    Jim Randell 9:30 am on 27 July 2023 Permalink | Reply
    Tags:   

    Teaser 2632: Times table 

    From The Sunday Times, 3rd March 2013 [link] [link]

    I have placed the numbers 1 to 16 (in no particular order) in a four-by-four table. As you go across each row of the table (from left to right) the four numbers are increasing, and as you go down each column the four numbers are increasing. If you read the top row as one long number, it is a four-figure number which equals the product of the four numbers in the second row.

    What are the four numbers in the second row?

    [teaser2632]

     
    • Jim Randell's avatar

      Jim Randell 9:31 am on 27 July 2023 Permalink | Reply

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

      The following run file executes in 152ms. (Internal runtime for the generated code is 76ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

#  A B C D
#  E F G H
#  I J K L
#  M N P Q

--base=17
--digits="1-16"

# rows are increasing
"A < B" "B < C" "C < D"
"E < F" "F < G" "G < H"
"I < J" "J < K" "K < L"
"M < N" "N < P" "P < Q"

# columns are increasing
"A < E" "E < I" "I < M"
"B < F" "F < J" "J < N"
"C < G" "G < K" "K < P"
"D < H" "H < L" "L < Q"

# the top row gives a 4-digit product of the numbers in the second row
"D < 10"
"nconcat(A, B, C, D, base=10) == E * F * G * H"

--answer="(E, F, G, H)"

--template="(A B C D) (E F G H) (I J K L) (M N P Q)"

      Solution: The numbers in the second row are: 2, 7, 8, 13.

      The first two rows are:

      (1, 4, 5, 6)
      (2, 7, 8, 13)

      And we have:

      2 × 7 × 8 × 13 = 1456

      The bottom two rows are:

      (3, 9|10, 10|11|12, 14|15)
      (9|10|11, 11|12, 14|15, 16)

      So there are 10 ways that the grid can be filled out.

      Like

      • Frits's avatar

        Frits 3:25 pm on 27 July 2023 Permalink | Reply

        @Jim,

        Which tags do you use for text in the grey commentary boxes ?
        I can see blockquotes are used in the final html.

        Like

    • Frits's avatar

      Frits 3:06 pm on 27 July 2023 Permalink | Reply

      Same concept but with calculating upper and lower bounds.

      from enigma import SubstitutedExpression

symbols = "ABCDEFGHIJKLMNPQ"

# (row i, col j) has i * j - 1 lower values  (rows and cols 1-4)
# (row i, col j) has (5 - i) * (5 - j) - 1 higher values   
# position <p> in symbols has rowno p // 4 + 1 and colno p % 4 + 1

# for each symbol determine lower and higher values
lh = [(symbols[p], (p // 4 + 1) * (p % 4 + 1) - 1, 
                   (4 - p // 4 ) * (4 - p % 4) - 1) for p in range(16)]

# invalid digit / symbol assignments
d2i, s2d = dict(), dict()
for d in range(1, 17):
  vs = set()
  if d > 9: vs.update('ABCD')
  
  for s, lw, hi in lh:
    if d <= lw: vs.update(s)
    if d > 16 - hi: vs.update(s)
    
  d2i[d] = vs
  
if 1:
  print("Allowed values:")
  for s in symbols:
    print(s, ":", end=" ")
    c, v = 0, 0
    for k, vs in d2i.items():
      if s not in vs:
        print(k, end=" ")
        c += 1
        v = k
    print()
    if c == 1:
      s2d[s] = v

distinct = ''.join([x for x in symbols if x not in s2d])

#  A B C D
#  E F G H
#  I J K L
#  M N P Q


# the alphametic puzzle
p = SubstitutedExpression(
  [
   "A < B",
   "B < F",
   "A < E",
   "E < F",
   "B < C",
   "C < G",
   "F < G",
   "C < D",
   "D < H",
   "G < H",
   
   # the top row gives a 4-digit product of the numbers in the second row
   "nconcat(A, B, C, D, base=10) == E * F * G * H",
   
   "E < I",
   "F < J",
   "I < J",
   "G < K",
   "J < K",
   "H < L",
   "K < L",
   "I < M",
   "J < N",
   "M < N",
   "K < P",
   "N < P",
   "L < Q",
   "P < Q",
  ],
  answer="((A, B, C, D), (E, F, G, H), (I, J, K, L), (M, N, P, Q))",
  base=17,
  d2i=d2i,
  s2d=s2d,
  distinct=distinct,
  digits=range(1, 17),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for ans in p.answers():
  print(f"{ans}")   

        
Allowed values:
A : 1
B : 2 3 4 5
C : 3 4 5 6 7 8 9
D : 4 5 6 7 8 9
E : 2 3 4 5
F : 4 5 6 7 8
G : 6 7 8 9 10 11
H : 8 9 10 11 12 13 14
I : 3 4 5 6 7 8 9
J : 6 7 8 9 10 11
K : 9 10 11 12 13
L : 12 13 14 15
M : 4 5 6 7 8 9 10 11 12 13
N : 8 9 10 11 12 13 14
P : 12 13 14 15
Q : 16

      Like

    • GeoffR's avatar

      GeoffR 7:17 pm on 27 July 2023 Permalink | Reply 

      % A Solution in MiniZinc
include "globals.mzn";

% ABCD
% EFGH
% IJKL
% MNPQ

% Numbers in the table
var 1..16:A; var 1..16:B; var 1..16:C; var 1..16:D;
var 1..16:E; var 1..16:F; var 1..16:G; var 1..16:H;
var 1..16:I; var 1..16:J; var 1..16:K; var 1..16:L;
var 1..16:M; var 1..16:N; var 1..16:P; var 1..16:Q;
% Read the top row as one long number
var 1000..9999:ABCD == 1000*A + 100*B + 10*C + D;

constraint all_different([A,B,C,D,E,F,G,H,I,J,K,L,M,N,P,Q]);

% The four numbers are increasing in each row
constraint A < B /\ B < C /\ C < D;
constraint E < F /\ F < G /\ G < H;
constraint I < J /\ J < K /\ K < L;
constraint M < N /\ N < P /\ P < Q;

% The four numbers are increasing in each column
constraint A < E /\ E < I /\ I < M;
constraint B < F /\ F < J /\ J < N;
constraint C < G /\ G < K /\ K < P;
constraint D < H /\ H < L /\ L < Q;

% If you read the top row as one long number,  
% it is a four-figure number which equals the product 
% of the four numbers in the second row.
constraint ABCD == E * F * G * H;

solve satisfy;
output [" Four numbers in second row  are " ++ show([E, F, G, H])];

% Four numbers in second row  are [2, 7, 8, 13]
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 11:12 am on 25 July 2023 Permalink | Reply
    Tags:   

    Teaser 2631: Family progression 

    From The Sunday Times, 24th February 2013 [link] [link]

    I have five grandchildren: from oldest to youngest they are Imogen, Madeline, Alex, Matthew and Laurence. They were all born in different years and no two have a birthday in the same month. They were all born before noon and for each grandchild I have noted their time and date of birth as five numbers [in the following order]:

    minute, hour, DD, MM, YY

    (none of the numbers is zero, but they may have a leading zero).

    Surprisingly, for each grandchild the five numbers form an arithmetic progression (i.e. increasing or decreasing by a fixed amount), and also in each case the sum of two of the five numbers equals the sum of the other three.

    With the children in the order given above, list the months in which they were born.

    [teaser2631]

     
    • Jim Randell's avatar

      Jim Randell 11:13 am on 25 July 2023 Permalink | Reply

      If (mm, hh, DD, MM, YY) forms an arithmetic progression, then so does its reverse (YY, MM, DD, hh, mm) which is perhaps a more sensible order for date and time.

      This Python program considers possible birth date/times that form appropriate sequences (from that start of the year 2000 up to the date of publication of the puzzle). And then collects sequences from 5 different years that occur in 5 different months.

      It runs in 66ms. (Internal runtime is 539µs).

      Run: [ @replit ]

      from datetime import datetime
from enigma import (irange, cproduct, div, catch, subsets, group, attr, join, printf)

# (abbreviated) month names to use
month = "??? Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec".split()

# only consider dates before this (= publication date of puzzle)
M = datetime(2013, 2, 24)

# generate possible birth dates
def generate():
  # hh is 01-11, MM is 1-12
  # choose values for hh and MM
  for (hh, MM) in cproduct([irange(1, 11), irange(1, 12)]):
    # calculate the common difference
    d = div(MM - hh, 2)
    if not d: continue
    # fill in the remaining values
    (mm, DD, YY) = (hh - d, hh + d, MM + d)
    # does it form a valid date?
    if mm < 1 or YY < 1: continue
    t = catch(datetime, 2000 + YY, MM, DD, hh, mm)
    if t is None or not t < M: continue
    # calculate the sum of the progression
    s = 5 * mm + 10 * d
    # is the sum of 2 of the numbers equal to the sum of the other 3
    if s % 2 == 1: continue
    ns = (mm, hh, DD, MM, YY)
    if not any(2 * sum(ss) == s for ss in subsets(ns, size=2)): continue
    # viable date
    printf("[{t} = {ns}, d={d}, s={s}]")
    yield t

# collect dates by year
g = group(generate(), attr('year'))

# select 5 birth years, oldest to youngest
for ks in subsets(sorted(g.keys()), size=5):
  # select birthdates
  for ds in cproduct(g[k] for k in ks):
    # collect the months
    ms = list(d.month for d in ds)
    # there must be 5 different months
    if len(set(ms)) != 5: continue
    # output solution
    for (i, d) in enumerate(ds, start=1):
      printf("{i} -> {d}")
    printf("months = {ms}", ms=join((month[m] for m in ms), sep=", "))
    printf()

      Solution: The months are: March, June, May, July, October.

      And the birth date/times are:

      Imogen = 2002-03-04 05:06, seq = (06, 05, 04, 03, 02)
      Madeline = 2004-06-08 10:12, seq = (12, 10, 08, 06, 04)
      Alex = 2006-05-04 03:02, seq = (02, 03, 04, 05, 06)
      Matthew = 2008-07-06 05:04, seq = (04, 05, 06, 07, 08)
      Laurence = 2012-10-08 06:04, seq = (04, 06, 08, 10, 12)

      Like

    • Frits's avatar

      Frits 3:24 pm on 25 July 2023 Permalink | Reply

      Using the new “decl” setting to remember assignment variables when denesting is requested.

      from enigma import SubstitutedExpression

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  if d > 1: vs.update('ACEGISTUVW')
  # as half the sum (2.5a + 5k) is an integer the year must be even
  if d % 2: vs.update('BDFHJ')
  # maximum difference between elements is three
  if not (0 < d < 4): vs.update('KLMNO')

  d2i[d] = vs
  
# YY, MM, DD, hh, mm 
# arithmetic progression: 
# AB, AB + -1**S * K, AB + 2 * -1**S * K, .. , AB + 4 * -1**S * K

# year, positive difference and sign
vars = [("AB", "K", "S"), ("CD", "L", "T"), ("EF", "M", "U"), 
        ("GH", "N", "V"), ("IJ", "O", "W")]

exprs, ms = [], ""
# build expressions        
for i, (a, k, s) in enumerate(vars):
  # decreasing ages
  exprs.append(("0" if not i else vars[i - 1][0]) + " < " + a + " <= " + str(8 + i))
  inc = "(-1)**" + s + " * " + k
  ms += a + " + " + inc + ", "

  exprs.append("0 < " + a + " + " +  inc + " <= 12")        # month
  exprs.append("0 < " + a + " + 3 * " + inc + " <= 11")     # hours
  exprs.append("0 < " + a + " + 4 * " + inc + " <= 59")     # minutes
  
  # make half the sum with highest and 1st or 2nd highest number
  y = "(" + s + " and 2.5 * " + a + " + 5 * " + inc 
  y += " in {2 * " + a + " + " + inc + ", 2 * " + a + " + 2 * " + inc + "}) or "
  y += "(not " + s + " and 2.5 * " + a + " + 5 * " + inc 
  y += " in {2 * " + a + " + 6 * " + inc + ", 2 * " + a + " + 7 * " + inc + "})"
  exprs.append(y)
  
# born on 5 different months
exprs.append("len(set(ms := [" + ms[:-1] +"])) == 5")

# the alphametic puzzle
p = SubstitutedExpression(
  exprs=exprs,
  answer="ms, \
          (AB, AB + (-1)**S * K, AB + 2 * (-1)**S * K, AB + 3 * (-1)**S * K, AB + 4 * (-1)**S * K), \
          (CD, CD + (-1)**T * L, CD + 2 * (-1)**T * L, CD + 3 * (-1)**T * L, CD + 4 * (-1)**T * L), \
          (EF, EF + (-1)**U * M, EF + 2 * (-1)**U * M, EF + 3 * (-1)**U * M, EF + 4 * (-1)**U * M), \
          (GH, GH + (-1)**V * N, GH + 2 * (-1)**V * N, GH + 3 * (-1)**V * N, GH + 4 * (-1)**V * N), \
          (IJ, IJ + (-1)**W * O, IJ + 2 * (-1)**W * O, IJ + 3 * (-1)**W * O, IJ + 4 * (-1)**W * O)",
          
  d2i=d2i,
  distinct="",
  decl="global ms",     # new feature for remembering assignment variables
  denest=1,
  verbose=0,            # use 256 to see the generated code
)

# print answers
for ans in p.answers():
  print(f"{ans[0]}")

      Like

  • Unknown's avatar

    Jim Randell 8:51 am on 20 July 2023 Permalink | Reply
    Tags:   

    Teaser 2633: Magic mushrooms 

    From The Sunday Times, 10th March 2013 [link] [link]

    Enid and her famous five (Anne, Dick, George, Julian and Timmy) were joined by Pixie in a mushroom hunt. They each picked two varieties, the fourteen overall being:

    Bird’s Nest, Beef Steak, Blue Toothed, Cannon Ball, Death Cap, Devil’s Um, Inky Cap, Old Man of the Woods, Parasol, Poison Pie, Stinkhorn, Slippery Jack, Tree Ears and The Gypsy.

    For each of these hunters, if you wrote down their name and the two varieties of mushroom they picked, then for any two from the three you would find that there were just two letters of the alphabet that occurred in both.

    What mushrooms were picked by: (a) Pixie and (b) Enid?

    It seems likely that “Devil’s Um” is a typo for “Devil’s Urn” (which is a type of mushroom), however the answer to the puzzle is the same whichever you use, so I have stuck with the spelling used in the original puzzle and in the 2020 book.

    Also, in Enid Blyton’s Famous Five, Timmy is a dog.

    [teaser2633]

     
    • Jim Randell's avatar

      Jim Randell 8:52 am on 20 July 2023 Permalink | Reply

      The [[ grouping ]] functionality in the enigma.py library was specifically written for puzzles like these.

      The following Python program runs in 61ms. (Internal runtime is 909µs).

      Run: [ @replit ]

      from enigma import grouping

names = ["Enid", "Anne", "Dick", "George", "Julian", "Timmy", "Pixie"]

picks = [
  "Bird's Nest", "Beef Steak", "Blue Toothed", "Cannon Ball", "Death Cap",
  "Devil's Um", "Inky Cap", "Old Man of the Woods", "Parasol",
  "Poison Pie", "Stinkhorn", "Slippery Jack", "Tree Ears", "The Gypsy"
]

# form 2-gangs
for gs in grouping.gangs(2, names, picks, grouping.share_letters(2)):
  # output the groups
  grouping.output_gangs(names, gs)

      Solution: (a) Pixie picked Devil’s Um/Urn and The Gypsy. (b) Enid picked Blue Toothed and Slippery Jack.

      The full solution is:

      Enid: Blue Toothed, Slippery Jack [de, ei, el]
      Anne: Beef Steak, Cannon Ball [ae, an, ab]
      Dick: Death Cap, Stinkhorn [cd, ik, ht]
      George: Poison Pie, Tree Ears [eo, er, es]
      Julian: Bird’s Nest, Parasol [in, al, rs]
      Timmy: Inky Cap, Old Man of the Woods [iy, mt, an]
      Pixie: Devil’s Um/Urn, The Gypsy [ei, ep, es]

      (Common letters are listed as: [name ∩ pick1, name ∩ pick2, pick1 ∩ pick2]).

      Like

  • Unknown's avatar

    Jim Randell 9:01 am on 11 July 2023 Permalink | Reply
    Tags:   

    Teaser 2629: Random road 

    From The Sunday Times, 10th February 2013 [link] [link]

    George and Martha moved into Random Road, which has 99 houses along just one side. But instead of being numbered 1 to 99 in the usual way, the man given the job of numbering them gave the first house a number equal to his age and then kept adding his age again for each subsequent house, ignoring the hundreds digits and above. (So, had he been 37 then the numbers would have been 37, 74, 11, 48, 85, 22, etc). Luckily each house got a different number. George’s house number was “correct” so he did not immediately notice. He only saw that something was amiss when Martha pointed out that a house next door had a number with the same two digits as theirs, but in reverse order.

    What is George’s and Martha’s house number? And how old was the numberer?

    [teaser2629]

     
    • Jim Randell's avatar

      Jim Randell 9:01 am on 11 July 2023 Permalink | Reply

      The house numbers in positions k = 1 .. 99 are defined as:

      a[1] = n
      a[k + 1] = (a[k] + n) mod 100

      or:

      a[k] = (k.n) mod 100

      So numberers with the same age mod 100 will give the same sequence. We can suppose that the numberers age lies in the range 16 – 115, so we can identify the ages by the residue mod 100.

      We are looking for a 2-digit house number XY that appears in the “correct” position, i.e.:

      a[XY] = XY

      And has a neighbouring house whose number is YX:

      a[XY ± 1] = YX

      I am assuming that 1-digit numbers are represented with a single digit.

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

      Run: [ @replit ]

      from enigma import (irange, nreverse, printf)

# find solutions for age <n>
def solve(n):
  # map: position -> house number
  (d, seen) = (dict(), set())
  (p, k) = (1, n)
  while p < 100:
    if k == 0 or k in seen: break
    d[p] = k
    seen.add(k)
    k = (k + n) % 100
    p += 1
  # did we allocate all the houses?
  if p == 100:
    # look for a house with a 2-digit number the same as position
    for (p, k) in d.items():
      if not (k > 9 and k == p): continue
      # look for neighbouring houses with the reverse of the number
      r = nreverse(k)
      if not (r > 9): continue
      if d.get(p - 1, 0) == r: yield (n, (p, k), (p - 1, r))
      if d.get(p + 1, 0) == r: yield (n, (p, k), (p + 1, r))

# consider possible ages (mod 100)
for n in irange(0, 99):
  for (n, (p0, k0), (p1, k1)) in solve(n):
    printf("age = {n} -> pos {p0} = {k0}, pos {p1} = {k1}")

      Solution: George and Martha’s house number is 25. The numberer’s age was 73.

      We have:

      a[25] = (25×73) mod 100 = 1825 mod 100 = 25
      a[24] = (24×73) mod 100 = 1752 mod 100 = 52

      The complete mapping is:

      (0 → 0), 1 → 73, 2 → 46, 3 → 19, 4 → 92, 5 → 65, 6 → 38, 7 → 11, 8 → 84, 9 → 57, 10 → 30,
      11 → 3, 12 → 76, 13 → 49, 14 → 22, 15 → 95, 16 → 68, 17 → 41, 18 → 14, 19 → 87, 20 → 60,
      21 → 33, 22 → 6, 23 → 79, 24 → 52, 25 → 25, 26 → 98, 27 → 71, 28 → 44, 29 → 17, 30 → 90,
      31 → 63, 32 → 36, 33 → 9, 34 → 82, 35 → 55, 36 → 28, 37 → 1, 38 → 74, 39 → 47, 40 → 20,
      41 → 93, 42 → 66, 43 → 39, 44 → 12, 45 → 85, 46 → 58, 47 → 31, 48 → 4, 49 → 77, 50 → 50,
      51 → 23, 52 → 96, 53 → 69, 54 → 42, 55 → 15, 56 → 88, 57 → 61, 58 → 34, 59 → 7, 60 → 80,
      61 → 53, 62 → 26, 63 → 99, 64 → 72, 65 → 45, 66 → 18, 67 → 91, 68 → 64, 69 → 37, 70 → 10,
      71 → 83, 72 → 56, 73 → 29, 74 → 2, 75 → 75, 76 → 48, 77 → 21, 78 → 94, 79 → 67, 80 → 40,
      81 → 13, 82 → 86, 83 → 59, 84 → 32, 85 → 5, 86 → 78, 87 → 51, 88 → 24, 89 → 97, 90 → 70,
      91 → 43, 92 → 16, 93 → 89, 94 → 62, 95 → 35, 96 → 8, 97 → 81, 98 → 54, 99 → 27

      So 25 is in the correct position, and 24 has the number that is the reverse of 25.

      50 and 75 are also in the correct position, but are not neighbours of 5 or 57 (respectively).

      62 is given the number 26, the reverse of its position.

      Like

    • Jim Randell's avatar

      Jim Randell 10:22 am on 11 July 2023 Permalink | Reply

      Without checking that each house is assigned a different number there is only one candidate solution (but we can provide an additional check to ensure the answer is viable).

      This run file executes in 62ms. (Internal runtime of the generated program is 1.3ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

# AB = age of the numberer
# XY = George and Martha's house number

SubstitutedExpression

--distinct="XY"
--code="num = lambda n, k: (n * k) % 100"

# G&M's house number is the same as its position
"num(AB, XY) == XY"

# a neighbouring house is numbered YX
"YX in { num(AB, XY - 1), num(AB, XY + 1) }"

# answer is: G&M's number, numberers age
--answer="(XY, AB)"

# check each house is assigned different number
--reorder=0
"seq_all_different(num(AB, k) for k in irange(1, 99))"

      Like

  • Unknown's avatar

    Jim Randell 10:43 am on 4 July 2023 Permalink | Reply
    Tags:   

    Teaser 2625: Mind the gap 

    From The Sunday Times, 13th January 2013 [link] [link]

    If you list in increasing order all ten-figure numbers with no repeat digit, then the first is 1023456789 and the last is 9876543210. The differences between consecutive numbers in the list vary wildly but no difference is ever equal to the average of all the differences between the consecutive numbers.

    What difference between consecutive numbers comes closest to the average?

    [teaser2625]

     
    • Jim Randell's avatar

      Jim Randell 10:44 am on 4 July 2023 Permalink | Reply

      The way [[ subsets(..., select='P') ]] works the numbers will be produced in numerical order, so we don’t need to order them.

      The distances between consecutive numbers are recorded in a [[ multiset() ]], so we don’t have to bother processing duplicate values.

      But there are a lot of numbers to process, so the program is quite slow.

      This Python program runs in 871ms.

      Run: [ @replit ]

      from enigma import (irange, subsets, nconcat, multiset, tuples, rdiv, Accumulator, printf)

# construct pandigitals in numerical order
def generate():
  for ds in subsets(irange(0, 9), size=10, select='P'):
    if ds[0] != 0:
      yield nconcat(ds)

# record the collection of differences between consecutive pandigitals
ds = multiset.from_seq(b - a for (a, b) in tuples(generate(), 2))
# calculate the mean difference
m = ds.avg(div=rdiv)
printf("mean difference = {m}", m=float(m))

# find the closest difference
r = Accumulator(fn=min, collect=1)
for d in ds.keys():
  r.accumulate_data(abs(m - d), d)
# output solution(s)
for d in r.data:
  printf("closest difference = {d} [{n} times]", n=ds[d])

      Solution: The difference that comes closest to the mean is 2727.

      Which occurs 1872 times, for example in the following pairs:

      (1034679852, 1034682579)
      …
      (9865317420, 9865320147)

      There are 500 different difference values.

      The smallest difference is 9 (which happens 322560 times):

      (1023456789, 1023456798)
      …
      (9876543201, 9876543210)

      And the largest difference is 104691357 (which happens 2 times):

      (1098765432, 1203456789)
      (8796543210, 8901234567)

      With some analysis we can get a faster program.

      We can calculate the mean difference fairly easily:

      In an ordered sequence (a, b, c, …, x, y, z) the sequence of consecutive distances is:

      (b − a, c − b, …, y − x, z − y)

      and this has one fewer element than the original sequence.

      And the sum of this sequence is simply:

      sum = z − a

      i.e. the difference between the largest pandigital and the smallest pandigital.

      So, if we knew the number of pandigitals in the original sequence we can calculate the mean.

      There are factorial(10) possible digit sequences, but factorial(9) of them will have a leading zero, so are rejected.

      Hence, there are 3265920 pandigitals (and the number of distances is 1 less than this).

      And so the mean distance is:

      mean distance = (9876543210 − 1023456789) / 3265919 = 2710.7489…

      So we see that no individual difference is equal to the mean because the mean is not an integer and all individual differences are. (And in fact they all must be multiples of 9).

      Now, if we consider two consecutive pandigitals that are at a distance apart that is close to the mean, then they are going to look something like:

      abcde|vwxyz
      abcde|xzyvw

      Where there is some shared prefix, and then the remaining digits appear in a different arrangement for the two numbers. And when calculating the difference between them the common prefix disappears.

      So the difference for the numbers in the example is then:

      xzyvw − vwxyz

      And we can calculate the differences by just looking at sets of numbers that are not part of the common prefix, and calculating the closest difference using those set.

      We are looking for a difference close to 2711, so we can examine sets of digits that have 5 elements.

      This Python program runs in 123ms.

      Run: [ @replit ]

      from enigma import (
  factorial, rdiv, ndigits, Accumulator,
  irange, subsets, nconcat, tuples, printf
)

# calculate the mean distance
m = rdiv(9876543210 - 1023456789, 9 * factorial(9) - 1)
printf("mean difference = {m}", m=float(m))

# record the closest difference to the mean
r = Accumulator(fn=min)

# consider possible sets of digits
k = ndigits(int(m)) + 1
for ds in subsets(irange(0, 9), size=k):
  # find consecutive numbers using this set of digits
  ns = subsets(ds, size=len, select='P', fn=nconcat)
  # find differences between consecutive numbers closest to the mean
  for (a, b) in tuples(ns, 2):
    d = b - a
    r.accumulate_data(abs(m - d), d)

# output solution
printf("closest difference = {r.data}")

      Like

    • Frits's avatar

      Frits 5:22 pm on 4 July 2023 Permalink | Reply 

        
from enigma import factorial
from itertools import permutations, combinations

# calculate the mean distance
m = (9876543210 - 1023456789) / (factorial(10) - factorial(9) - 1)
print(f"mean difference = {m}")

mn, md = 9999999, 9999999

# abcde with c > d > e 
# choose last three descending digits
for c in combinations('9876543210', 3):
  # choose first 2 digits
  for p in permutations(set('0123456789').difference(c), 2):
    s = ''.join(p + c)

    # jump within same 10000:  like 32510 to 35012
    if s[1] < '7':
      # jump 3 higher for a difference of 2xxx
      s2 = str(int(s[1]) + 3)
      if s2 not in s[1:]: continue
      new = int(s[0] + s2 + ''.join(sorted(set(s[1:]).difference(s2))))
    else:  
      ints = [int(x) for x in s]
      # we must be able to jump to a higher 10000
      a1 = str(ints[0] + 1)
      if s[0] == '9' or a1 not in s: continue
      # digit 3 higher then 2nd digit must be present
      if str(ints[1] - 7) not in s: continue
      # digits higher than 2nd digit may not occur in last three positions
      if any(str(j) in s[2:] for j in range(ints[1] + 1, 10)): continue
      
      # jump to higher 10000:   like 17420 to 20147
      new = int(a1 + ''.join(sorted(set(s).difference(a1))))
  
    i = int(s)
    # check for closeness to target
    if abs(m - new + i) <= mn:
      mn, md = abs(m - new + i), new - i

print("answer:", md)

      Like

      • Frits's avatar

        Frits 1:27 pm on 5 July 2023 Permalink | Reply

        With the abcde|vwxyz method we might miss other combinations that can come relatively close to 2710.

        like 2345698710, 2345701689 with difference 2979

        Like

        • Jim Randell's avatar

          Jim Randell 1:37 pm on 5 July 2023 Permalink | Reply

          We can reduce the size of the prefix considered at line 14:

          k = ndigits(int(m)) + 2

          Although it turns out the common prefix is size 5 in all 1872 cases, so we are OK.

          Originally I allowed 1 digit more than the length of the mean for the suffix, but this does assume that the closest value is going to be reasonably close to the mean value.

          Like

← Older posts

Newer posts →

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
Design a site like this with WordPress.com
Get started