Updates from June, 2023 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 10:37 am on 29 June 2023 Permalink | Reply
    Tags:   

    Brainteaser 1093: Bumper’s final ball 

    From The Sunday Times, 17th July 1983 [link]

    It is a lovely evening in August, and the final Test of the 1990 series has reached its climax. The rubber stands at two games each, the last ball of the last over of the match is now to come. Australia are batting and need six runs for victory. Whacker, their wicket-keeper, the last man in, has taken his stand. with his captain’s words ringing in his ears, “Six or bust!”.

    Bumper, the England bowler, has just taken the previous two wickets in succession, With a dim opinion of Whacker’s batting, he feels sure that a fast straight one will not only give England the Ashes, but will give him his hat-trick and his seventh wicket of the match.

    In a breathless hush he delivers a  fast straight one. Striding forward like a Titan, Whacker mows …

    The records of this match are scanty. The Australian total in two innings was 490. Except for one man run out in the first innings, their casualties fell to bowlers. The five England bowlers had averages of 14, 20, 25 (Bumper), 33, 43, each with a differing number of wickets.

    How many wickets did each take and who won the Ashes?

    This puzzle was originally published as Brain-Teaser 15 on 11th June 1961 (although when originally published it was credited to R. Skeffington Quinn), and was re-published as Brainteaser 1093 to celebrate Mr Skeffington Quin’s 100th birthday.

    [teaser1093]

     
    • Jim Randell's avatar

      Jim Randell 10:38 am on 29 June 2023 Permalink | Reply

      See my solution at Teaser 15.

      In the same issue an interview with Mr Skeffington Quin was published. [link]

      The article notes that Mr Skeffington Quin’s “very first” puzzle (Brain-Teaser 15, 11th June 1961) is being re-published (as Brainteaser 1093) in celebration of his 100th birthday.

      However in 1960, the year before Brain-Teaser became a weekly feature (and before the puzzles were numbered), he had contributed a puzzle on 31st July 1960 (Brain-Teaser: Silver collection), which was also included in the book Sunday Times Brain Teasers (1974).

      The article also mentions a puzzle set on 5th November 1972 as his most “impenetrable” puzzle, and that only two correct answers were received.

      However when I searched for this puzzle in The Sunday Times archive, I found a note saying that The Sunday Times was not published on that date due to industrial action. (However the accompanying magazine, which was prepared in advance, is present in the archive, but the puzzle does not appear in it).

      However there is a gap in the puzzle numbers at that point (the missing puzzle is Brain-Teaser 591), and a solution was given with Brain-Teaser 593, where it is noted that only 2 (out of 50) entrants got the correct answer, suggesting the puzzle was published.

      So it is indeed something of a puzzle.

      Like

    • GeoffR's avatar

      GeoffR 6:52 pm on 29 June 2023 Permalink | Reply 

      
% A Solution in MiniZinc
include "globals.mzn";
 
% Number of wickets taken by each bowler is different
var 1..9:w1; var 1..9:w2; var 1..9:w3;  
var 1..9:w4; var 1..9:w5; 
constraint all_different([w1, w2, w3, w4, w5]);

% Average runs per wicket for each bowler
int: a1 == 14;
int: a2 == 20;
int: a3 == 25;  % Bumper's average runs per wicket 
int: a4 == 33;
int: a5 == 43;

% total runs for each bowler ( say, UB half total runs scored)
var 1..245:t1; var 1..245:t2; var 1..245:t3; var 1..245:t4; var 1..245:t5;

% The Australian total in two innings was 490
constraint  t1 + t2 + t3 + t4 + t5 == 490;

constraint a1 * w1 == t1 /\ a2 * w2 == t2 /\ a3 * w3 == t3 /\ 
a4 * w4 == t4 /\ a5 * w5 == t5;

% Bumper (w3) takes 6 or 7 wickets (Jim's analysis)
% .. and total wickets are 18 or 19
constraint ((w1 + w2 + w3 + w4 + w5 == 18) /\ w3 == 6)
\/  ((w1 + w2 + w3 + w4 + w5 == 19) /\ w3 == 7);

solve satisfy; 

output [ "[w1, w2, w3, w4, w5 ] = " ++ show( [w1, w2, w3, w4, w5 ]) ++
"\n" ++ "[t1, t2, t3, t4, t5 ] = " ++ show( [t1, t2, t3, t4, t5 ]) ++
"\n" ++ "[a1, a2, a3, a4, a5 ] = " ++ show( [a1, a2, a3, a4, a5 ])];

% [w1, w2, w3, w4, w5 ] = [5, 2, 7, 1, 4]
% [t1, t2, t3, t4, t5 ] = [70, 40, 175, 33, 172]
% [a1, a2, a3, a4, a5 ] = [14, 20, 25, 33, 43]
% ----------
% ==========
% so Bumper takes 7 wickets and England wins the series.

% Not sure of relevance of condition below
% Bumper, the England bowler, has just taken the previous two wickets in succession,

      Like

    • Pete Good's avatar

      Pete Good 1:23 pm on 19 September 2023 Permalink | Reply

      Jim,

      I may be able to shed some light on the missing Skeffington-Quin teaser. I first started doing Brain Teasers when I was at school and one puzzle that I particularly remember was “Here Comes the Bride” by this author. I remember it because the Sunday Times printed a note in the magazine a few weeks later stating that there were only 2 correct entries out of 50. I kicked myself at the time for not having sent in a postcard because I had obtained the correct solution!

      I never kept copies of those early newspapers so I was delighted when I recently obtained a second-hand copy of Ronnie Postill’s 1974 book of Brain Teasers and had the pleasure of solving it again. I thought it was originally published in 1968 or 1969, not in 1972 as stated in the article you read. If you have access to the Sunday Times archives then you may find it in an earlier year.

      Regards

      Pete

      Like

      • Jim Randell's avatar

        Jim Randell 6:43 pm on 19 September 2023 Permalink | Reply

        @Pete: Thanks for the info.

        I also have a copy of the 1974 book, and I have gradually been adding puzzles from it to the site – [teaser-book-1974]. There are currently 44 (of 101) puzzles posted from that book, but I haven’t yet got to the one you mention, which is Teaser 429 (27th July 1969). When the answer was published (10th August 1969) it was noted that there were 21 correct entries.

        I searched the Sunday Times Digital Archive for puzzles involving Ara and Chne, and found these:

        Brain-Teaser 250: Spider’s Wedding March / 13th February 1966
        Brain-Teaser 346: Antics / 24th December 1967 (also in the 1974 book)
        Brain-Teaser 429: Here Comes the Bride / 27th July 1969 (also in the 1974 book)
        Brain-Teaser 843: Stratagem / 11th September 1977

        but it didn’t find the missing puzzle, Brain-Teaser 591 (5th November 1972), so the search continues.

        Like

  • Unknown's avatar

    Jim Randell 9:20 am on 27 June 2023 Permalink | Reply
    Tags: ,   

    Teaser 2530: [A day at the races] 

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

    At the St Patrick’s Day races, Pat backed losers in each of the first three. Starting with £100, he bet a whole-number percentage of his money in the first race and a whole-number percentage of the remainder (but not a whole number of pounds) in the second. In the third, he bet a whole-number percentage of what was left, leaving a whole-number percentage of his £100. This final percentage was the sum of the three percentages he had bet and lost.

    How much was lost on the third race?

    This puzzle was originally published with no title.

    [teaser2530]

     
    • Jim Randell's avatar

      Jim Randell 9:21 am on 27 June 2023 Permalink | Reply

      If the percentages bet are p1, p2, p3, and the remaining amounts after each bet it lost are r1, r2, r3, then:

      p1 + p2 + p3 = r3
      r1 = 100 − p1
      r2 = r1 − p2 . r1 / 100 = r1(100 − p2)/100 [and r2 is not a whole number]
      r3 = r2 − p3 . r2 / 100 = r2(100 − p3)/100

      So we can choose a value for r3, and split that into the three percentages (p1, p2, p3) and check the bets turn out as required.

      And this approach does find the answer in a reasonable time, but it is not hugely fast.

      This Python program runs in 347ms. (Internal runtime is 237ms).

      Run: [ @replit ]

      from enigma import (irange, decompose, printf)

# generate possible (p1, p2, p3) percentage values
def generate():
  # consider the number of pounds remaining after the 3 bets
  for r in irange(3, 98):
    # this is equal to p1 + p2 + p3
    yield from decompose(r, 3, increasing=0, sep=0, min_v=1)

# consider values for p1, p2, p3
for (p1, p2, p3) in generate():
  # bet 1, we lose p1 pounds
  r1 = 100 - p1
  # bet 2, we lose not a whole number of pounds
  b2 = r1 * p2  # = (bet 2) * 100
  if b2 % 100 == 0: continue
  r2 = 100 * r1 - b2  # = (remaining 2) * 100
  # bet 3, we are left with (p1 + p2 + p3) pounds
  b3 = r2 * p3  # = (bet 3) * 100^2
  r3 = 100 * r2 - b3  # = (remaining 3) * 100^2
  if r3 != (p1 + p2 + p3) * 10000: continue
  # output solution
  printf(
    "p1={p1}% p2={p2}% p3={p3}% -> b1={b1:.2f} b2={b2:.2f} b3={b3:.2f}; r1={r1:.2f} r2={r2:.2f} r3={r3:.2f}",
    b1=float(p1), b2=(b2 * 0.01), b3=(b3 * 0.0001), r1=float(r1), r2=(r2 * 0.01), r3=(r3 * 0.0001),
  )

      Solution: £2.25 was bet (and lost) on the third race.

      The scenario is:

      start = £100.00
      bet 1 = 25% of £100.00 = £25.00
      bet 1 lost, remaining = £75.00
      bet 2 = 25% of £75.00 = £18.75
      bet 2 lost, remaining = £56.25
      bet 3 = 4% of £56.25 = £2.25
      bet 3 lost, remaining = £54.00
      sum of percentage values = 25 + 25 + 4 = 54.

      For a faster program we can do a bit of analysis:

      We can write (r1, r2, r3) in terms of (p1, p2, p3) to get:

      r1 = 100 − p1
      r2 = (100 − p1)(100 − p2)/100
      r3 = (100 − p1)(100 − p2)(100 − p3)/10000
      r3 = p1 + p2 + p3
      ⇒
      10000(p1 + p2 + p3) = (100 − p1)(100 − p2)(100 − p3)

      Note that 5^4 divides the LHS, so it must divide the terms of the RHS, so one of them must be a multiple of 25 (i.e. 25, 50, 75), and another must also be a multiple of 5.

      And this gives us a faster way to generate possible (p1, p2, p3) values.

      This Python 3 program uses a different [[ generate() ]] function, and runs in 61ms. (Internal runtime is 89µs).

      Run: [ @replit ]

      from enigma import (irange, div, subsets, printf)

# generate possible percentage values
def generate():
  # one of the values is a multiple of 25
  for a in (25, 50, 75):
    # an another is a multiple of 5
    for b in irange(5, 95 - a, step=5):
      c_ = div(10000 * (a + b + 100), 10000 + (100 - a) * (100 - b))
      if c_ is None or not (c_ < 100): continue
      # return the values (in some order)
      yield from subsets((a, b, 100 - c_), size=len, select='mP')

# consider values for p1, p2, p3
for (p1, p2, p3) in generate():
  # bet 1, we lose p1 pounds
  r1 = 100 - p1
  # bet 2, we lose not a whole number of pounds
  b2 = r1 * p2  # = (bet 2) * 100
  if b2 % 100 == 0: continue
  r2 = 100 * r1 - b2  # = (remaining 2) * 100
  # bet 3, we are left with (p1 + p2 + p3) pounds
  b3 = r2 * p3  # = (bet 3) * 100^2
  r3 = 100 * r2 - b3  # = (remaining 3) * 100^2
  if r3 != (p1 + p2 + p3) * 10000: continue
  # output solution
  printf(
    "p1={p1}% p2={p2}% p3={p3}% -> b1={b1:.2f} b2={b2:.2f} b3={b3:.2f}; r1={r1:.2f} r2={r2:.2f} r3={r3:.2f}",
    b1=float(p1), b2=(b2 * 0.01), b3=(b3 * 0.0001), r1=float(r1), r2=(r2 * 0.01), r3=(r3 * 0.0001),
  )

      In fact only one set of values (25, 25, 4) satisfies the analysis. And only with the 4% value for the final bet is the condition that the second amount bet is not a whole number of pounds satisfied.

      Like

    • Frits's avatar

      Frits 7:08 pm on 27 June 2023 Permalink | Reply

      Manual solution:

      Let the percentages NOT bet at each stage be p1, p2 and p3 and
let the remainders after each stage be r1, r2 and r3 with the
initial amount r0. Then r1 = r0.p1 / 100, r2 = r1.p2 / 100 and
r3 = r2.p3 / 100 giving:

p1 = 100.r1/r0 = 10000.r2/p2.r0 = 1000000.r3/p2.p3.r0

   p1.p2.p3 = 10^6.r3/r0

Also:

  100.r3/r0 = (100 - p1) + (100 - p2) + (100 - p3)

Eliminating r3/r0 now allows p3 to be derived from p1 and p2:

  p3 = (300 - p1 - p2).10^4 / (10^4 + p1.p2)

  p1 * p2 * p3 - 10^4 * (300 - p1 - p2 - p3) = 0

  p1 * p2 * p3 = (300 - p1 - p2 - p3) * 16 * 5^4

if p1, p2 and p3 are all multiples of 5 then
(300 - p1 - p2 - p3) is also a multiple of 5 so
p1 * p2 * p3 must be a multiple of 5^5

so we can conclude at least 2 out (p1, p2, p3) must be equal to 75,
remaining percentage p* must be a multiple of 16
and (300 - p1 - p2 - p3) must be a multiple of 9 (3 * 3)
    (150 - p*) must be a multiple of 9
    so p* mod 9 = 6
the only multiple of 16 and mod 9 = 6 out of 64, 80 and 96 is 96
so (p1, p2, p3) = (75, 75, 96) in any order

p1 can't be 96 as 0.75 * 96 is a whole number
p2 can't be 96 as 75 * 0.96 is the same whole number
so (p1, p2, p3) = (75, 75, 96) in this order

on the third race was lost: (3/4)^2 * 100 * (100 - 96) / 100 = 2.25 pounds

      Like

  • Unknown's avatar

    Jim Randell 10:08 am on 25 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 346: Antics 

    From The Sunday Times, 24th December 1967 [link]

    All distances and dimensions are exact feet; all times, exact seconds; all the spiders run at 5 feet per second; and drop with a maximum fall of 30 feet.

    Ara and Chne sat hungry in the top north-west corner of the palace corridor (no flies).

    “Could be and ant or two in that bottom south-east corner by the garden door”, said Chne.

    “True”, said Ara. She dropped to the floor and headed straight for the prospective meal, while Chne (she never drops) instantly set off down the shortest route via the north wall and floor.

    Farther along the corridor, Taran and Tula sat hungry together at the top of the south wall.

    “Hey, look!”, cried Taran, as the ant-hunters approached.

    “Must be something in that corner”, said Tula, dropping to the floor and speeding straight toward it.

    Taran at the same moment ran direct for the corner. As she started, Ara, clocking 39 seconds, passed by.

    Tangle and wrangle! Dead heat all! No ants!

    How wide is the corridor?

    This puzzle is included in the book Sunday Times Brain Teasers (1974). The puzzle text is taken from the book.

    [teaser346]

     
    • Jim Randell's avatar

      Jim Randell 10:09 am on 25 June 2023 Permalink | Reply

      By folding the walls of the corridor flat we can turn all of the paths into straight lines in the same plane.

      Measuring all distances in feet, and times in “ticks” (= 1/5 second), then each spider travels 1 ft per tick.

      We don’t know how long it takes a spider to drop the height of the corridor, but this is calculated as part of the solution.

      The following Python program runs in 58ms. (Internal runtime is 859µs).

      Run: [ @replit ]

      from enigma import (pythagorean_triples, sum_of_squares, is_square, printf)

# consider the path Taran takes, it is the hypotenuse of a Pythagorean triple
for (a, b, t2) in pythagorean_triples(999):
  # but must be divisible by 5
  if t2 % 5 > 0: continue
  # and the height of the corridor must be no more than 30
  for (h, t1) in [(a, b), (b, a)]:
    # and Tula's path must also be a multiple of 5
    if h > 30 or t1 % 5 > 0: continue
    # and their times are equal, so we can calculate drop time (in 1/5 s)
    d = t2 - t1

    # total time for Ara and Chne is 195 ticks more than for t2
    t = t2 + 195
    # and this is Chne's distance, the hypotenuse of a (w + h, l, t) triangle
    for (x, y) in sum_of_squares(t * t, min_v=1):
      for (wh, l) in [(x, y), (y, x)]:
        w = wh - h
        if w < 0 or not (l > t1): continue
        # Ara's time is the same as Chne's
        z = is_square(w * w + l * l)
        if z is None or z + d != t: continue

        # output solution
        printf("h={h} t1={t1} t2={t2}; d={d} t={t}; w={w} l={l} z={z}")

      Solution: The corridor is 39 ft wide.

      And 25 ft high, and 252 ft long.

      Chne takes a direct route (across the N wall and floor) so travels hypot(39 + 25, 252) = 260 ft (in 52s).

      Ara drops to the floor (which takes 1s) and travels hypot(39, 252) = 255 ft (in 51s).

      At the 39s mark Taran and Tula set off on their journeys.

      Taran crosses the S wall diagonally for 13s, so travels a distance of 65 ft.

      Tula drops to the floor (1s) and travels for 12s a distance of 60 ft.

      And so they all arrive in the SE bottom corner at exactly the same time.

      Like

  • Unknown's avatar

    Jim Randell 4:34 pm on 23 June 2023 Permalink | Reply
    Tags:   

    Teaser 3170: Time to admire the adverts 

    From The Sunday Times, 25th June 2023 [link] [link]

    George and Martha use a local underground station, which has up and down escalators and an adjacent 168-step staircase. Martha always uses the escalator. George, being the fitness fanatic, always uses the stairs. In olden times, he could keep up with her while climbing or descending at seven steps per second. But now he can only ascend at N steps per second and descend at N + 1 steps per second, N being a whole number. They start together at the bottom and go up and down continually, losing negligible time in turning. Interestingly, at some point after they have both been all the way up and down, but before ten minutes have elapsed, Martha overtakes George precisely half-way up or half-way down.

    After how many seconds does this happen?

    [teaser3170]

     
    • Jim Randell's avatar

      Jim Randell 4:55 pm on 23 June 2023 Permalink | Reply

      Presumably N is between 1 and 6.

      This Python program considers possible values, generating the times for Martha and George at the halfway mark, and then looking for times when Martha is overtaking George.

      We use rational numbers to avoid loss of precision in floating point comparisons.

      It runs in 64ms. (Internal runtime is 140µs).

      Run: [ @replit ]

      from enigma import (Rational, irange, printf)

Q = Rational()

# generate times at halfway (less than T) -> t
def times(up, dn, H=84, T=600):
  # go halfway up
  t = Q(H, up)
  # go half up/dn (or half dn/up) to return to halfway
  inc = t + Q(H, dn)
  while t < T:
    yield t
    t += inc

# generate M's times
M = dict((t, m) for (m, t) in enumerate(times(7, 7)))

# consider possible N values
for N in irange(1, 6):
  # generate G's times
  for (g, t) in enumerate(times(N, N + 1)):
    # look for times when they meet
    if g < 2: continue
    m = M.get(t)
    if m is None: continue
    # we are interested in when they are going the same direction
    if m % 2 != g % 2: continue
    # output solution
    printf("N={N}: t={t}s [g={g} m={m}]")

      Solution: After 588 seconds.

      i.e. after 9 minutes, 48 seconds.

      George can only manage 1 step/s ascending and 2 steps/s descending.

      At that time George has been up the stairs 2.5 times (each ascent taking 168s) and down 2 times (each descent taking 84s, so the total time is 2.5×168 + 2×84 = 588s).

      Martha has been up the stairs 12.5 times and down 12 times (each ascent and descent takes 24s, so the total time is 12.5×24 + 12×24 = 588s).

      Manually:

      Martha travels at a constant 7 steps per second, so she is at halfway at the following times (in seconds):

      [12, 36, 60, 84, 108, …, 588]

      i.e. the odd multiples of 12, less than 600 (= 10 minutes).

      The first two elements are discarded (as M must have completed one full up and down).

      So she is going up on [60, 108, 156, …, 588] and down on [84, 132, 180, …, 564].

      As multiples of 12 these are:

      up = [5, 9, 13, …, 49]
      down = [7, 11, 15, …, 47]

      George takes N steps/s going up and (N + 1) steps/s going down so, he is halfway at:

      g[1] = 84/N
      g[k + 1] = g[k] + (84/N + 84/(N + 1))

      When N = 1, G’s halfway points are separated by 84 + 42 = 126:

      g = [84, 210, 336, 462, 588]

      And as multiples of 12 these are:

      g = [7, 17.5, 28, 38.5, 49]

      Only the first and fifth are odd multiples of 12, and the first two elements are discounted as G must have completed one full up and down.

      So only the fifth element for G is permissible, and as it is in an odd position, G is on his way up.

      And 49 also appears on M’s up list, so this gives an answer to the puzzle.

      And there are no further solutions for N = 2 .. 6.

      Like

    • Frits's avatar

      Frits 6:15 pm on 23 June 2023 Permalink | Reply 

         
NS = 168  # number of staircase steps

# one cycle: going up and down

# walk for less than 10 minutes and check halfway points for Martha
for t in range(12, 600, 24):
  # determine the direction Martha was going
  directionM = "u" if t % 48 == 12 else "d"
   
  for N in range(1, 7):
    # times for George to walk up and down
    u, d = NS / N, NS / (N + 1)
    
    r = t % (u + d)     # time left after cycles have been completed
    # George must have been halfway
    if r not in {u / 2, u + d / 2}: continue
    
    # determine the direction George was going
    directionG = "u" if r < u else "d"
    if directionG != directionM: continue
    
    print("answer: after", t, "seconds")

      Like

    • Frits's avatar

      Frits 2:25 pm on 26 June 2023 Permalink | Reply

      71 iterations.

       
# work with tenths of seconds to avoid fractional inaccuracies
# when dividing by 5

# T = time in tenths of seconds to walk all staircase steps 
#     if you take 1 step a second
T = 10 * 168

# possible answers, Martha must have gone up and down at least twice
answers = set(range(1080, 6000, 240))

# consider possible N values
for N in range(1, 7):
  # times in tenths of second for George to walk up and down
  u, d = T // N, T // (N + 1)
  ud, half_ud = u + d, (u + d) // 2
  
  up = 1       # toggle for up/down
  t = ud + u // 2
  # check George's times at halfway points
  while t < 6000:
    # for Martha to overtake George also check their directions
    if t in answers and ((t % 480) == 120) == up:
      print("answer: after", t // 10, "seconds")
    t += half_ud
    up = 1 - up

      Like

      • Jim Randell's avatar

        Jim Randell 10:10 am on 28 June 2023 Permalink | Reply

        @Frits: Yes, calculating G’s halfway times and then checking to see when one matches a halfway time for M only considers 71 cases (because when G is slow, he doesn’t reach halfway many times in the 10 minutes).

        And I think in general it is also a good idea not to rely on strict equality of floats.

        Like

  • Unknown's avatar

    Jim Randell 10:24 am on 22 June 2023 Permalink | Reply
    Tags: by: John Sharples   

    Teaser 2088: Black and white 

    From The Sunday Times, 22nd September 2002 [link]

    Throughout the following calculations, each digit has consistently been replaced by a letter, with different letters for different digits:

    Here the fractions are not necessarily in their simplest form — indeed, each of the three fractions in the above subtraction is in fact a whole number. Furthermore (though you might not need to know all these):

    What number is BLACK?

    [teaser2088]

     
    • Jim Randell's avatar

      Jim Randell 10:25 am on 22 June 2023 Permalink | Reply

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

      It runs in 78ms. (Internal runtime of the generated program is 9ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

# fraction() representation of 0
--code="zero = fraction()"

# "BL/WH - AC/IT = K/E" ...
"fraction(BL, WH, -AC, IT,  -K, E) == zero"

# ... but each fraction is a whole number
"BL % WH = 0" "AC % IT = 0" "K % E = 0"

# "IT/WB + CA/KL = H/E"
"fraction(IT, WB,  CA, KL,  -H, E) == zero"

# "WB/TI * KL/CA = E/H"
"fraction(WB * KL, TI * CA,  -E, H) == zero"

# "BT/IK / EL/WA = H/C"
"fraction(BT * WA, IK * EL,  -H, C) == zero"

--answer="BLACK"
--template="(BL/WH - AC/IT = K/E) (IT/WB + CA/KL = H/E) (WB/TI * KL/CA = E/H) (BT/IK / EL/WA = H/C)"
--solution=""

      Solution: BLACK = 80549.

      And the sums are:

      [BL/WH − AC/IT = K/E] (80/16 − 54/27 = 9/3) → (5 − 2 = 3)
      [IT/WB + CA/KL = H/E] (27/18 + 45/90 = 6/3) → (3/2 + 1/2 = 2)
      [WB/TI × KL/CA = E/H] (18/72 × 90/45 = 3/6) → (1/4 × 2 = 1/2)
      [BT/IK ÷ EL/WA = H/C] (87/29 ÷ 30/15 = 6/4) → (3 ÷ 2 = 3/2)

      Like

      • Frits's avatar

        Frits 3:31 pm on 22 June 2023 Permalink | Reply

        @Jim, I noticed the generated code allows zero for variable H (which is used as a denominator).

        A further optimisation of SubstitutedExpression() could be to detect that we have used the maximum of variables (10) and that only one (L) can have a specific value (zero) which then can be assigned.

        Like

        • Frits's avatar

          Frits 3:45 pm on 22 June 2023 Permalink | Reply

          I have done some sudoku solving lately.

          If variables are distinct and values p, q, r are the only values used by variables X, Y, Z then we can remove p,q,r from the candidates of other variables.

          Like

        • Jim Randell's avatar

          Jim Randell 10:30 am on 23 June 2023 Permalink | Reply

          @Frits: I think both these cases are currently handled reasonably by the [[ SubstitutedExpression ]] solver.

          The solver doesn’t know how you are going to use a symbol, so it can’t remove values that are inappropriate to use as a denominator of a fraction. But it does skip over values that cause a runtime exception (although in some cases this can also mask flaws in the supplied expressions). If you set the warn (or -W) flag these failures are reported as warnings. Invoking my code with this flag set shows that it does not actually try the H=0 assignments.

          Also symbols that are part of a distinct grouping have values that have already been used by other symbols in that group removed, so if there is only a single value remaining, that is what will be used. And if the solver is allowed to choose the order of the expressions it will start with those that have to fewest possible assignments.

          Like

    • GeoffR's avatar

      GeoffR 7:33 pm on 22 June 2023 Permalink | Reply 

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

var 1..9:B; var 0..9:L; var 1..9:W; var 0..9:H;
var 1..9:A; var 0..9:C; var 1..9:I; var 0..9:T;
var 1..9:K; var 1..9:E;

constraint all_different ([B, L, W, H, A, C, I, T, K, E]);

% Another form of first sum: BL/WH - AC/IT = K/E
constraint (10*B + L) * (10*I  + T) * E - (10*A + C) *(10*W +  H) * E
== K * (10*I  + T)* (10*W +  H);

% Each of the three fractions in the first sum gives an exact division
constraint (10*B + L) mod (10*W + H) == 0;
constraint (10*A + C) mod (10*I + T) == 0;
constraint K mod E == 0;

% The second equation ; IT/WB + CA/KL = H/E 
constraint E * ((10*I + T)* (10*K + L) + (10*C + A) * (10*W + B)) 
== H * (10*W +  B) * (10*K + L);

% 3rd equation: WB/TI X LL/CA = E/H
constraint H * (10*W + B) * (10*K + L) == E * (10*T + I) * (10*C + A);

% 4th equation: BT/IK / EL/WA =  H/C
constraint (10*B + T) * (10*W + A) * C == (10*E + L) *(10*I + K) * H;

solve satisfy;

output ["BLACK = " ++ "\(B)\(L)\(A)\(C)\(K)" ];

% BLACK = 80549
% ----------
% ==========

      I found using the 1st and 2nd sums, together with the the three exact divisions of the components of the 1st sum, was sufficient in practice to get a single answer for BLACK.

      Like

    • Frits's avatar

      Frits 2:42 pm on 23 June 2023 Permalink | Reply

      With a bit more analysis.

      from enigma import SubstitutedExpression

vars = "ABCEKLITWH"
distinct = set(vars)
# invalid digit / symbol assignments
d2i, s2d = dict(), dict()

for d in range(0, 10):
  vs = set()
  # starting digit of 2-digit numbers may not be zero
  if d == 0: vs.update('BWAICKTE')
  # IT/WB + CA/KL = H/E
  if d == 0: vs.update('H')
  # BL/WH >= 4 (sum of two true multiples) so WH < 25 and BL > 40
  if d > 2: vs.update('W')
  if d < 4: vs.update('B')
  
  d2i[d] = vs

# check if a value can only belong to one variable
for k, vs in d2i.items():
  if len(vs) == 9:
    s2d[c := set(vars).difference(vs).pop()] = k
    distinct = distinct.difference(c)

# more analysis, L = 0 and 
# BT * WA * C == H * IK * EL so either T, A, or C is equal to 5  
# WB * KL * H == E * TI * CA so either E, I, or A is equal to 5  
s2d["A"] = 5
d2i[5] = set(vars).difference("A")
distinct = distinct.difference("A")

# the alphametic puzzle
p = SubstitutedExpression(
  [
    # each fraction is a whole number
    "K % E = 0",
    "BL % WH = 0",
    # BL/WH - AC/IT = K/E
    "AC // (BL // WH - K // E) = IT",
    "AC % IT = 0",
    
    # maybe not all three equations are necessary
    
    # IT/WB + CA/KL = H/E 
    "E * (IT * KL + CA * WB) == H * WB * KL", 
    
    # WB/TI × KL/CA = E/H
    "WB * KL * H == E * TI * CA",
    
    # BT/IK ÷ EL/WA = H/C
    "BT * WA * C == H * IK * EL",
  ],
  answer="BLACK",
  d2i=d2i,
  s2d=s2d,
  distinct=str(distinct),
  #reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for (_, ans) in p.solve():
  print(f"BLACK={ans}")

      Like

  • Unknown's avatar

    Jim Randell 9:31 am on 20 June 2023 Permalink | Reply
    Tags:   

    Teaser 2156: Some cubes 

    From The Sunday Times, 11th January 2004 [link]

    In what follows, digits have consistently been replaced by letters, with different letters used for different digits:

    THREE
    CAN
    BE
    CUBES

    As stated, three of those numbers are cubes (and the other one is less than five away from a cube).

    What is the value of CUBE?

    [teaser2156]

     
    • Jim Randell's avatar

      Jim Randell 9:32 am on 20 June 2023 Permalink | Reply

      This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to find candidate values that are each individually within 5 of a cube number. We then check the answers for cases where three of the distances are 0.

      It runs in 68ms. (Internal runtime is 11ms).

      Run: [ @replit ]

      from enigma import (SubstitutedExpression, iroot, printf)

# distance to nearest kth root
def dist(n, k=3):
  x = iroot(n, k)
  return min(n - x**k, (x + 1)**k - n)

# make an alphametic puzzle
p = SubstitutedExpression(
  [
    # each must be less than 5 away from a cube
    "dist(THREE) < 5",
    "dist(CAN) < 5",
    "dist(BE) < 5",
    "dist(CUBES) < 5",
  ],
  answer="(THREE, CAN, BE, CUBES)",
  env=dict(dist=dist),
  verbose=0
)
# solve the puzzle
for ans in p.answers():
  # count the distances
  ds = list(dist(x) for x in ans)
  # three must have distance 0
  if ds.count(0) != 3: continue
  # output solution
  CUBE = ans[-1] // 10
  printf("CUBE = {CUBE} {ans}")

      Solution: CUBE = 1968.

      The numbers are:

      THREE = 74088 = 42³
      CAN = 125 = 5³
      BE = 68 = 4³ + 4
      CUBES = 19683 = 27³

      Like

    • Frits's avatar

      Frits 1:57 pm on 20 June 2023 Permalink | Reply

      More messy (the reorder=0 isn’t even necessary).

         
#!/usr/bin/env pypy -m enigma -r
 
SubstitutedExpression

# each must be a cube or less than 5 away from a cube
"(c1 := is_cube_p(BE)) or \
  BE - (r := int(BE**(1/3)))**3 < 5        or (r + 1)**3 - BE < 5"
"(c2 := is_cube_p(CUBES)) or (c1 and \
  (CUBES - (r := int(CUBES**(1/3)))**3 < 5 or (r + 1)**3 - CUBES < 5))"
"(c3 := is_cube_p(CAN)) or (c1 and c2 and \
  (CAN - (r := int(CAN**(1/3)))**3 < 5     or (r + 1)**3 - CAN < 5))"
"is_cube_p(THREE) or (c1 and c2 and c3 and \
  (THREE - (r := int(THREE**(1/3)))**3 < 5 or (r + 1)**3 - THREE < 5))"

--answer="(THREE, CAN, BE, CUBES)"

# [optional] less verbose output
--template=""

--reorder=0

      Like

      • Frits's avatar

        Frits 7:02 pm on 20 June 2023 Permalink | Reply

        The 2 missing ” and ” don’t cause a syntax error.

        Like

      • Jim Randell's avatar

        Jim Randell 8:26 am on 21 June 2023 Permalink | Reply

        @Frits: I think I see what this is doing. (I removed the extraneous trailing commas, and fixed up some missing and keywords).

        But I think it would allow the case where all four of the words were cubes.

        This is what my [[ SubstitutedExpression ]] run file looks like:

        Run: [ @replit ]

        #! python3 -m enigma -rr

SubstitutedExpression

# distance to nearest kth root
--code="def _dist(n, k=3): x = iroot(n, k); return min(n - x**k, (x + 1)**k - n)"
--code="dist = cache(_dist)"

# check cube distance is less than 5 (if flag) or 0
--code="def check(n, f): x = dist(n); return (0 < x < 5 if f else x == 0)"

# n = 1..4 denotes which statement is not a cube
--invalid="0|5|6|7|8|9,n"

# each is less than 5 away from a cube
"check({THREE}, {n} ==  1)"
"check({CAN}, {n} == 2)"
"check({BE}, {n} == 3)"
"check({CUBES}, {n} == 4)"

--distinct="ABCEHNRSTU"
--answer="CUBE"
--template="(THREE, CAN, BE, CUBES)"
--solution="n"

        Like

    • GeoffR's avatar

      GeoffR 5:43 pm on 20 June 2023 Permalink | Reply

      Using Frits method of solution i.e.each number must be a cube or less than 5 away from a cube.

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

var 1..9:T; var 0..9:H; var 0..9:R; var 0..9:E;
var 1..9:C; var 0..9:A; var 0..9:N; var 1..9:B;
var 0..9:U; var 0..9:S;

constraint all_different ([T, H, R, E, C, A, N, B, U, S]);

% Four numbers are BE, CAN, CUBES, THREE
var 10..99:BE == 10*B + E;
var 100..999:CAN == 100*C + 10*A + N;
var 10000..99999:CUBES == 10000*C + 1000*U + 100*B + 10*E + S;
var 10000..99999:THREE == 10000*T + 1000*H + 100*R + 11*E;

% Required answer is CUBE
var 1000..9999:CUBE == 1000*C + 100*U + 10*B + E; 

% Sets of cubes for 2-digit, 3-digit and 5-digit numbers
set of int: cb2 = {27, 64};
set of int: cb3 = {n * n * n | n in 5..9};
set of int: cb5 = {n * n * n | n in 22..46};

% Three of the numbers are cubes
constraint sum([THREE in cb5, CAN in cb3, BE in cb2, CUBES in cb5]) == 3;

% Allow for the fourth number to be less than five away from a cube
% Number BE
constraint BE in cb2 \/ (BE - 1) in cb2  \/ (BE - 2) in cb2 
\/ (BE - 3) in cb2   \/ (BE - 4) in cb2  \/ (BE + 1) in cb2 
\/ (BE + 2) in cb2   \/ (BE + 3) in cb2  \/ (BE + 4) in cb2; 
% Number CAN
constraint CAN in cb3 \/ (CAN - 1) in cb3 \/ (CAN - 2) in cb3
 \/ (CAN - 3) in cb3  \/ (CAN - 4) in cb3 \/ (CAN + 1) in cb3 
 \/ (CAN + 2) in cb3  \/ (CAN + 3) in cb3 \/ (CAN + 4) in cb3;
% Number THREE
constraint THREE in cb5 \/ (THREE - 1) in cb5  \/ (THREE - 2) in cb5
 \/ (THREE - 3) in cb5  \/ (THREE - 4) in cb5  \/ (THREE + 1) in cb5 
 \/ (THREE + 2) in cb5  \/ (THREE + 3) in cb5  \/ (THREE + 4) in cb5;
% Number CUBES
constraint CUBES in cb5 \/ (CUBES - 1) in cb5 \/ (CUBES - 2) in cb5
 \/ (CUBES - 3) in cb5  \/ (CUBES - 4) in cb5 \/ (CUBES + 1) in cb5 
 \/ (CUBES + 2) in cb5  \/ (CUBES + 3) in cb5 \/ (CUBES + 4) in cb5;
                                                                                  
solve satisfy;

output["CUBE = " ++ show(CUBE)  ++ "\n" ++   
"[THREE, CAN, BE, CUBES] = " ++ show ([THREE, CAN, BE, CUBES]) ];

% CUBE = 1968
% [THREE, CAN, BE, CUBES] = [74088, 125, 68, 19683]
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 2:38 pm on 18 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 433: Hymn numbers 

    From The Sunday Times, 24th August 1969 [link]

    The hymn-board in church was electrically operated and made provision for any four hymn numbers of up to three digits in each (from 0 to 9), but did not provide blanks so that Hymn No. 7 for example would appear on the board as 007, and No. 77 as 077.

    One Sunday a parishioner noticed with surprise that not only was each of the four hymn numbers for that service a perfect square, but moreover each of the three numbers produced in the vertical columns was a 4-digit perfect square.

    When, back home, he told his son Tom of this unique occurrence, the latter exclaimed: “I can’t believe it! What were the numbers then?”, to which the father replied: “You already know enough to work that out for yourself, but it will be of help to you to learn that I also noticed that the totals of the digits of each hymn number were perfect squares too, and that, coincidentally, one of these squares would result from dividing the final hymn number into the number formed by the middle column”.

    But Tom still couldn’t puzzle it out and demanded to be told at any rate one of the hymn numbers, to which the father responded, “All I can remember now is that the third hymn number ended in two noughts”.

    What was the opening hymn number?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser433]

     
    • Jim Randell's avatar

      Jim Randell 2:39 pm on 18 June 2023 Permalink | Reply

      I used the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 80ms. (Internal runtime of the generated code is 8ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

#  A B C
#  D E F
#  G H I
#  J K L

--distinct=""
--invalid="0,ABC" # columns form 4-digit squares

# hymns are different
"all_different(ABC, DEF, GHI, JKL)"

# rows form squares
"is_square(ABC)"
"is_square(DEF)"
"is_square(GHI)"
"is_square(JKL)"

# columns form squares
"is_square(ADGJ)"
"is_square(BEHK)"
"is_square(CFIL)"

# row sums form squares
"is_square(A + B + C)"
"is_square(D + E + F)"
"is_square(G + H + I)"
"is_square(J + K + L)"

# 3rd row is x00
--assign="H,0"
--assign="I,0"

# 4th row divides into middle column, to give one of the row sums
"div(BEHK, JKL) in {A + B + C, D + E + F, G + H + I, J + K + L}"

# [optional] just show the hymn numbers
--template="ABC DEF GHI JKL"
--solution=""

      Solution: The opening hymn number was: 529.

      The hymns are: 529, 36, 400, 144.

      We have:

      rows
      529 = 23²; 5 + 2 + 9 = 16 = 4²
      036 = 6²; 0 + 3 + 6 = 9 = 3²
      400 = 20²; 4 + 0 + 0 = 4 = 2²
      144 = 12² ; 1 + 4 + 4 = 9 = 3²

      columns
      5041 = 71²
      2304 = 48²
      9604 = 98²

      2304 / 144 = 16 = 4² = 5 + 2 + 9

      And we do indeed get a single solution if we just keep the requirements that the rows and columns form squares (lines 16 – 25).

      Like

  • Unknown's avatar

    Jim Randell 4:28 pm on 16 June 2023 Permalink | Reply
    Tags:   

    Teaser 3169: Cancel culture — amp it up! 

    From The Sunday Times, 18th June 2023 [link] [link]

    A heckled lecturer used her megaphone. The power reaching its amplifier’s input was multiplied by a two-figure whole number (the “intrinsic gain”). In each of three stages a fraction of the power was lost but, by good design, each of the three fractions was under one-twentieth. Curiously, each happened to have a different two-figure prime denominator. It turned out that the effective gain in the process (the ratio of the output power to the input power) was a whole number. In addition, the intrinsic gain and the effective gain both started with the same digit.

    In ascending order, what were the three fractions?

    [teaser3169]

     
    • Jim Randell's avatar

      Jim Randell 4:58 pm on 16 June 2023 Permalink | Reply

      If I understand this correctly the mechanics of it are:

      The input signal is initially multiplied by a 2-digit value (= I, the “intrinsic gain”), and then goes through 3 stages where it is reduced by fractions a/p, b/q, c/r, where each of the fractions is less than 1/20, and p, q and r are prime numbers. This gives the “effective gain” E, which is a whole number, and which has the same first digit as I.

      So:

      E = I × (1 − a/p) × (1 − b/q) × (1 − c/r)

      Here’s my initial stab at this.

      It runs in 137ms. (Internal runtime is 38ms).

      Run: [ @replit ]

      from enigma import (
  primes, irange, first, subsets, cproduct, div,
  nsplit, fdiv, unpack, seq2str, sprintf, printf
)

# map prime denominators to numerators that give fractions < 1/20
nums = lambda p: first(irange(1, p), count=(lambda n: 20 * n < p))
d = dict((p, nums(p)) for p in primes.between(20, 99))

# choose the prime denominators (p, q, r)
for (p, q, r) in subsets(d.keys(), size=3):
  Rd = p * q * r
  # and choose the numerators (a, b, c)
  for (a, b, c) in cproduct(d[k] for k in (p, q, r)):
    # calculate the ratio E/I (= Rn / Rd)
    Rn = (p - a) * (q - b) * (r - c)
    # choose a 2-digit number for I (= intrinsic gain)
    for I in irange(10, 99):
      # calculate E (= effective gain) (a whole number)
      E = div(I * Rn, Rd)
      if E is None: continue
      # check E and I have the same first digit
      if nsplit(E)[0] != nsplit(I)[0]: continue
      # order the fractions
      fs = sorted([(a, p), (b, q), (c, r)], key=unpack(fdiv))
      # output solution
      printf("{fs} [I={I} E={E}]", fs=seq2str(sprintf("{x}/{y}") for (x, y) in fs))

      Solution: The three fractions are: 1/41, 3/89, 2/43.

      The intrinsic gain (I) is 89, and so the effective gain (E) is:

      E = 89 × (1 − 1/41) × (1 − 3/89) × (1 − 2/43)
      E = (89 × 40 × 86 × 41) / (41 × 89 × 43)
      E = 80

      Without the requirement that the first digits of E and I are the same we find there are 5 potential solutions:

      88/97 = (46/47) × (94/97) × (22/23)
      66/73 = (71/73) × (69/71) × (22/23)
      56/61 = (58/59) × (59/61) × (28/29)
      80/89 = (40/41) × (86/89) × (41/43)
      78/89 = (86/89) × (41/43) × (39/41)

      Like

      • Hugo's avatar

        Hugo 6:03 pm on 16 June 2023 Permalink | Reply

        A more realistic way of looking at it is that each stage is designed to have a certain gain, the product of the three gains being I. In practice the circuitry is imperfect and each gain is reduced by a certain fraction, so that the overall gain E is somewhat lower. The overall effect is the same as in the situation described by Jim, but the losses occur during amplification, not after it.

        Like

      • Jim Randell's avatar

        Jim Randell 7:56 am on 17 June 2023 Permalink | Reply

        Here is a faster version. Once the ratio E:I is determined we can look for equivalent fractions with a 2-digit denominator to give values for E and I.

        It runs in 77ms. (Internal runtime is 17ms).

        Run: [ @replit ]

        from enigma import (
  primes, irange, divf, subsets, cproduct, fraction,
  nsplit, fdiv, unpack, seq2str, format_fraction, printf
)

# map denominators to numerators that give fractions < 1/20
nums = lambda n: irange(1, divf(n - 1, 20))

# choose the prime denominators (p, q, r)
for (p, q, r) in subsets(primes.between(20, 99), size=3):
  Rd = p * q * r
  # and choose the numerators (a, b, c)
  for (a, b, c) in cproduct(nums(k) for k in (p, q, r)):
    # calculate the ratio E/I (= Rn / Rd)
    Rn = (p - a) * (q - b) * (r - c)
    # consider fractions E/I = Rn/Rd where I is 2-digits
    (n, d) = fraction(Rn, Rd)
    for k in irange(1, divf(99, d)):
      (E, I) = (k * n, k * d)
      if I < 10: continue
      # check E and I have the same first digit
      if nsplit(E)[0] != nsplit(I)[0]: continue
      # order the fractions
      fs = sorted([(a, p), (b, q), (c, r)], key=unpack(fdiv))
      # output solution
      printf("{fs} [I={I} E={E}]", fs=seq2str(format_fraction(x, y) for (x, y) in fs))

        Like

    • GeoffR's avatar

      GeoffR 11:15 pm on 16 June 2023 Permalink | Reply

      A slow solution – about 8.5 sec.
      It finds the three fractions, but not in ascending order.

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

% Same variables as Jim's solution.
var 1..9:A; var 1..9:B; var 1..9:C;
var 10..99:P; var 10..99:Q; var 10..99:R;
var 10..99:E; var 10..99:I;

constraint I > E /\ E div 10 == I div 10;

predicate is_prime(var int: x) = 
 x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) 
 ((i < x) -> (x mod i > 0));   
 
% The three denominators of the fractions are all 2-digit primes
constraint is_prime(P) /\ P > 10  /\ P < 98;
constraint is_prime(Q) /\ Q > 10  /\ Q < 98;
constraint is_prime(R) /\ R > 10  /\ R < 98;

% The three fractions are all less than 1/20
constraint 20 * A < P /\ 20 * B < Q /\ 20 * C < R;

% Jim's equation simplifies to:
% E * P * Q * R  = I *(P - A) * (Q - B) * (R - C)
constraint E * P * Q * R == I * (P - A) * (Q - B) * (R - C);

solve satisfy;

output[ "Three fractions are " ++ show(A) ++ "/" ++ show(P) ++", "
++ show(B) ++ "/" ++ show(Q) ++" and "  
++ show(C) ++ "/" ++ show(R) ];

      Like

      • Jim Randell's avatar

        Jim Randell 11:31 pm on 16 June 2023 Permalink | Reply

        You can add the following to get the fractions in order:

        constraint A * Q < B * P /\ B * R < C * Q;

        Like

        • GeoffR's avatar

          GeoffR 11:08 am on 17 June 2023 Permalink | Reply

          @Jim:
          Yes, that extra line of code works well.
          it also reduces the run-time for me to just over 2sec.

          Like

    • Frits's avatar

      Frits 12:31 am on 17 June 2023 Permalink | Reply 

       
from enigma import SubstitutedExpression
from fractions import Fraction as rf

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  if d == 0: vs.update('ACEPXYZ')
  if d == 1: vs.update('ACE')
  if d > 4: vs.update('XYZ')
  if d % 2 == 0 or d == 5: vs.update('BDF')

  d2i[d] = vs

# remaining checks for prime   
check = lambda n: all(n % x for x in [3, 7])
  
# PQ intrinsic gain, PR = effective gain
# primes AB, CD and EF

# the alphametic puzzle
p = SubstitutedExpression(
  [
    "20 * (AB - X) > 19 * AB",
    # prime check
    "check(AB)",
    
    "CD > AB",
    # prime check
    "check(CD)",
    "20 * (CD - Y) > 19 * CD",
    
    "EF > CD",
    # prime check
    "check(EF)",
    
    # if (AB - X) * (CD - Y) is not divisible by either prime 
    # then (EF - Z) * PQ must be a multiple of AB * CD
    "any(((AB - X) * (CD - Y)) % x == 0 for x in [AB, CD]) or \
         ((AB - X) * (CD - Y)) % EF == 0",
    
    "20 * (EF - Z) > 19 * EF",
    
    "PQ * (AB - X) * (CD - Y) * (EF - Z) == PR * (AB * CD * EF)"
  ],
  answer="ordered(rf(X, AB), rf(Y, CD), rf(Z, EF))",
  d2i=d2i,
  env=dict(check=check, rf=rf),
  distinct="",
  verbose=0,    # use 256 to see the generated code
)

# print answers
for (_, ans) in p.solve():
  print(f"{ans[0]}, {ans[1]} and {ans[2]}")

      Like

    • GeoffR's avatar

      GeoffR 12:31 pm on 17 June 2023 Permalink | Reply 

      
from enigma import is_prime
from itertools import permutations

PR = [ x for x in range(11, 98) if is_prime(x)]

for A, B, C in permutations(range(1, 5), 3):
  for P in PR:
    if not(20 * A < P):continue
    for Q in PR:
      if Q == P:continue
      if not (20 * B < Q):continue
      if not(A * Q < B * P):continue
      for R in PR:
        if R in (P, Q):continue
        if not (20 * C < R):continue
        if not(B * R < C * Q):continue
        for E in range(10, 99):
          for I in range(10, 99):
            if E // 10 != I // 10:continue
            # Same equation as the MiniZinc solution
            if E * P * Q * R == I * (P - A) * (Q - B) * (R - C):
              print(f"Three fractions: {A}/{P}, {B}/{Q}, {C}/{R}.")

      Like

  • Unknown's avatar

    Jim Randell 9:33 am on 15 June 2023 Permalink | Reply
    Tags:   

    Teaser 2016: T for two 

    From The Sunday Times, 6th May 2001 [link]

    I have in mind a whole number less than 100. If I were to tell you the first letter in the spelling of that number, you would not be able to determine the number. But if I were to tell you both the first and last letters in the spelling of the number, then you would be able to determine it. Now, If I were to tell you just the last letter in the spelling of the number, you would be able to determine it.

    What is the number?

    [teaser2016]

     
    • Jim Randell's avatar

      Jim Randell 9:33 am on 15 June 2023 Permalink | Reply

      I supposed the numbers were from 1 to 99 (although you can also use 0 if you like).

      This Python program combines the [[ int2words() ]] and [[ filter_unique() ]] functions from the enigma.py library.

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

      Run: [ @replit ]

      from enigma import (irange, int2words, filter_unique, intersect, join, printf)

# numbers from 1 to 99 as words
ns = dict((n, int2words(n)) for n in irange(1, 99))

# return a function to select letters at indices <js> from the spelling of a number
select = lambda *js: (lambda k: join(ns[k][j] for j in js))

# the number is ambiguous by first letter
ss1 = filter_unique(ns.keys(), f=select(0)).non_unique

# but unique by first + last letter
ss2 = filter_unique(ns.keys(), f=select(0, -1)).unique

# from these it is unique by last letter
ss = filter_unique(intersect([ss1, ss2]), f=select(-1)).unique

# output solution
printf("{ss}", ss=join(ss, sep=", "))

      Solution: The number is 98.

      Like

    • Frits's avatar

      Frits 2:06 pm on 15 June 2023 Permalink | Reply

      Maintaining a dictionary.

         
from enigma import int2words

# lowercase letters
letters = ''.join(chr(ord('a') + i) for i in range(26))
 
# numbers from 1 to 99 as words
nums = [int2words(n) for n in range(1, 100)]

# the number is ambiguous by first letter
d = {l: [x for x in nums if x[0] == l] for l in letters}
d = {k: vs for k, vs in d.items() if len(vs) > 1}

# but unique by first + last letter
d = {l1 + l2: [x for x in nums if x[0] == l1 and x[-1] == l2 and x[0] in d] 
               for l1 in letters for l2 in letters}
d = {k: vs for k, vs in d.items() if len(vs) == 1}       

# from these it is unique by last letter
d = {k[-1]: [vs2 for k2, vs2 in d.items() if k[-1] == k2[-1]] for k in d}   
d = {k: vs for k, vs in d.items() if len(vs) == 1}

for k, v in d.items():
  print("answer:", *v[0])

      Like

  • Unknown's avatar

    Jim Randell 11:52 am on 13 June 2023 Permalink | Reply
    Tags:   

    Teaser 2177: Basic sum 

    From The Sunday Times, 6th June 2004 [link]

    You might look askance at the addition sum:

    But in fact each of the numbers is written in a different base. Just one of the four numbers is prime and just one is divisible by three. Also, when written in the normal decimal form, the last digits of the three numbers being added are all different, and the total is still a four-figure number.

    What is the total?

    [teaser2177]

     
    • Jim Randell's avatar

      Jim Randell 11:52 am on 13 June 2023 Permalink | Reply

      See also: Enigma 1358.

      This Python program collects numerical values of “1101” in various bases, such that the value is not more than 4 digits in decimal.

      It then looks for three of these values that sum to a fourth, and applies the remaining conditions.

      It runs in 56ms. (Internal runtime is 518µs).

      Run: [ @replit ]

      from enigma import (
  irange, inf, base2int, subsets, icount_exactly,
  is_prime, seq_all_different, join, printf
)

# is x divisible by 3?
div3 = lambda x: x % 3 == 0

# find values for <s> in various bases
d = dict()
for b in irange(2, inf):
  n = base2int('1101', base=b)
  if n > 9999: break
  d[n] = b

# look for 3 of the values that sum to a 4th
for ns in subsets(d.keys(), size=3, fn=list):
  t = sum(ns)
  if t < 1000 or t not in d: continue
  # the last digits of the summands (in base 10) are all different
  if not seq_all_different(n % 10 for n in ns): continue
  ns.append(t)
  # exactly one of the 4 numbers is divisible by 3
  if not icount_exactly(ns, div3, 1): continue
  # exactly one of the 4 numbers is prime
  if not icount_exactly(ns, is_prime, 1): continue
  # output solution
  bs = list(d[n] for n in ns)
  printf("{ns} = {t} [bases = {bs}]",
    ns=join(ns[:-1], sep=" + "),
    bs=join(bs, sep=", ", enc="()"),
  )

      Solution: The result of the sum is 7221 (in decimal).

      The sum is:

      1101 [base 6] = 253 [decimal] +
      1101 [base 9] = 811 [decimal] +
      1101 [base 18] = 6157 [decimal] =
      1101 [base 19] = 7221 [decimal]

      Like

      • Frits's avatar

        Frits 12:01 pm on 14 June 2023 Permalink | Reply

        @Jim, you don’t seem to have a proper check on “the total is still a four-figure number”.

        Like

    • GeoffR's avatar

      GeoffR 10:21 pm on 13 June 2023 Permalink | Reply 

      
from enigma import is_prime, all_different
from itertools import combinations

# max base for 4 digits is 21
# sum is n1 + n2 + n3 = n4
for b1, b2, b3, b4 in combinations(range(2, 22),4):
  n4 = int('1101', base = b4)
  # the total n4 is a four-figure number
  if n4 < 10000:
    n1 = int('1101', base = b1)
    n2 = int('1101', base = b2)
    n3 = int('1101', base = b3)
    # one of the four numbers is prime
    if sum  ((is_prime(n1), is_prime(n2), is_prime(n3),\
              is_prime(n4))) == 1:
      # last digits of the three summands are all different
      if all_different( str(n1)[:-1], str(n2)[:-1], \
                        str(n3)[:-1]):
        # one of the four numbers is divisible by three
        if sum((n1 % 3 == 0, n2 % 3 == 0, n3 % 3 == 0, \
                n4 % 3 == 0))== 1:
          # check total of sum is correct
          if n4 == n1 + n2 + n3:
            print(f"Sum is : {n1} + {n2} + {n3} = {n4}.")
            print(f"The bases are {b1}, {b2}, {b3} and {b4}.")

# Sum is : 253 + 811 + 6157 = 7221.
# The bases are 6, 9, 18 and 19.

      Like

    • GeoffR's avatar

      GeoffR 8:38 am on 14 June 2023 Permalink | Reply

      Quite slow in MiniZinc – nearly 3 sec with the Chuffed Solver.

      % 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));

% Four numbers with four different number bases
% min LB = 8 + 4 + 0 + 1 = 13
% max UB = 21**3 + 21**2 + 0 + 1 = 9703
var 13..9703:N1; var 13..9703:N2; var 13..9703:N3; var 13..9703:N4;
var 2..21:b1; var 2..21:b2; var 2..21:b3; var 2..21:b4;
 
% put bases in order
constraint b2 > b1 /\ b3 > b2 /\ b4 > b3;

% Form 4 numbers in 4 different bases in format 1101
constraint N1 == 1 * b1 * b1 * b1 + 1 * b1 * b1 + 0 + 1;
constraint N2 == 1 * b2 * b2 * b2 + 1 * b2 * b2 + 0 + 1;
constraint N3 == 1 * b3 * b3 * b3 + 1 * b3 * b3 + 0 + 1;
constraint N4 == 1 * b4 * b4 * b4 + 1 * b4 * b4 + 0 + 1;

% Main sum
constraint N1 + N2 + N3 == N4;

% One of the four numbers is prime
constraint sum([is_prime(N1), is_prime(N2), is_prime(N3), is_prime(N4)]) == 1;

% One of the four numbers is prime is exactly divisible by three
constraint sum([N1 mod 3 == 0, N2 mod 3 == 0, N3 mod 3 == 0, N4 mod 3 == 0]) == 1;

% the last digits of the three summands are different
constraint all_different([N1 mod 10, N2 mod 10, N3 mod 10]);

solve satisfy;

output["Total is " ++ show(N4) ++ "\n" 
++ "Sum is " ++ show(N1) ++ " + " ++ show(N2) ++ " + " ++ show(N3) ++ " = " ++ show(N4)
++ "\n" ++ "Bases are " ++ show([b1, b2, b3, b4])];

% Total is 7221
% Sum is 253 + 811 + 6157 = 7221
% Bases are [6, 9, 18, 19]
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 11:09 am on 11 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 276: Electing a Chairman 

    From The Sunday Times, 14th August 1966 [link]

    The ten directors of the Everlasting Mutual Trust Company, Chairman (C), Secretary (S), Treasurer (T), Directors 1, 2, 3, 4, 5, 6, and Vice-Chairman (V), sat in that order to elect a new chairman.

    They all got one vote. No director voted for himself, or for his neighbour, or for the man who voted for him. No officer voted for an officer. C voted for the man who voted for the man who voted for 2, i.e. C vote vote vote 2 for short; and T vote vote vote 4, and V vote vote vote 5, and S vote vote vote 6. Director 4 did not vote for an officer. Neither C nor S voted for 3. The man getting a vote from 6 did not vote for 3.

    For whom did C, S, T, 1, 2, 3, 4, 5, 6, V respectively vote?

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser276]

     
    • Jim Randell's avatar

      Jim Randell 11:09 am on 11 June 2023 Permalink | Reply

      Presumably each of them cast one vote, and received one vote.

      We can write “X vote vote vote Y” even more compactly as “X vote^3 Y”.

      This Python 3 program generates possible voting patterns, taking direct voting restrictions into account, and then checks the restrictions on voting chains.

      In Python 3.7+ dict() objects remember their insertion order, so the output should be in the required order.

      It runs in 111ms. (Internal runtime is 52ms).

      Run: [ @replit ]

      from enigma import (tuples, remove, update, map2str, printf)

# multiple lookups on dict <d>
def nget(d, k, n):
  while n > 0:
    k = d[k]
    n -= 1
  return k

# the voters
voters = "CST123456V"

# determine invalid votes:
invalid = dict((k, set()) for k in voters)
# no-one votes for themselves
for k in voters:
  invalid[k].add(k)
# no-one votes for their neighbours
for (x, y, z) in tuples(voters, 3, circular=1):
  invalid[y].update((x, z))
# officers (CSTV) don't vote for other officers
officers = "CSTV"
for k in officers:
  invalid[k].update(officers)

# generate possible votes
# return <m>, map of <voter> -> <vote>
def votes(ks, vs, m=dict()):
  # are we done?
  if not ks:
    yield m
  else:
    k = ks[0]
    xs = invalid[k]
    for v in vs:
      # reject invalid votes and reciprocal votes
      if v not in xs and (v not in m or m[v] != k):
        yield from votes(ks[1:], remove(vs, v), update(m, [(k, v)]))

# 4 did not vote for an officer
invalid['4'].update(officers)
# neither C nor S voted for 3
invalid['C'].add('3')
invalid['S'].add('3')

# who votes for who?
for v in votes(voters, set(voters)):
  # check vote chains:
  # the man getting a vote from 6 did not vote for 3
  if nget(v, '6', 2) == '3': continue
  # C vote^3 2
  if nget(v, 'C', 3) != '2': continue
  # T vote^3 4
  if nget(v, 'T', 3) != '4': continue
  # V vote^3 5
  if nget(v, 'V', 3) != '5': continue
  # S vote^3 6
  if nget(v, 'S', 3) != '6': continue
  # output solution
  printf("{v}", v=map2str(v, sort=0))

      Solution: The votes are: C→6, S→2, T→3, 1→5, 2→C, 3→V, 4→1, 5→T, 6→S, V→4.

      Or as cycles:

      C → 6 → S → 2 (→ C)
      T → 3 → V → 4 → 1 → 5 (→ T)

      Like

    • Frits's avatar

      Frits 4:35 pm on 11 June 2023 Permalink | Reply 

       
from enigma import SubstitutedExpression

# invalid digit / symbol assignments
d2i = dict()
for d in range(0, 10):
  vs = set()
  # no officer voted for an officer
  # director 4 did not vote for an officer 
  
  if d < 1 or d > 6: vs.update('NCSTV')
  else:  # 1 <= d <= 6
    # no director voted for himself or for his neighbour ..
    vs.update("KLMNOP"[max(0, d - 2):d + 1])
  
  if d == 0:
    vs.update("K")
  
  if d == 7:
    vs.update("P")
  
  # neither C nor S voted for 3
  if d == 3:
    vs.update("CS")   
  
  d2i[d] = vs

# return index of person in sequence {seq> who voted <n>
voted = lambda seq, n: seq.index(n)
# return the man who voted for the man who voted for <n>
vote3 = lambda seq, n: voted(seq, voted(seq, n))

# officers CSTV and directors KLMNOP
# VKLMNOPCST
# 0123456789

# the alphametic puzzle
p = SubstitutedExpression(
  [
   # choose assignment to T as C and S have fewer candidate values
   # T vote^3 4
   "vote3([V, K, L, M, N, O, P, C, S, -1], 4) = T",

   # the man getting a vote from 6 did not vote for 3
   "(r := [V, K, L, M, N, O, P, C, S, T])[P] != 3",
   
   # C vote^3 2 (C voted for the man who voted for the man who voted for 2)
   "vote3(r, 2) == C",
   # V vote^3 5
   "vote3(r, 5) == V",
   # S vote^3 6
   "vote3(r, 6) == S",
   
   # no director voted for the man who voted for him
   "all(x != voted(r, i) for i, x in enumerate([K, L, M, N, O, P], 1))",
  ],
  answer="[C, S, T, K, L, M, N, O, P, V]",
  d2i=d2i,
  env=dict(vote3=vote3, voted=voted),
  reorder=0,
  verbose=0,    # use 256 to see the generated code
)

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

      Like

  • Unknown's avatar

    Jim Randell 4:31 pm on 9 June 2023 Permalink | Reply
    Tags:   

    Teaser 3168: Number cruncher 

    From The Sunday Times, 11th June 2023 [link] [link]

    The gaslight glittered on the polished brass of the machine. “My Number Cruncher can calculate mechanically the result of a calculation on three positive whole numbers used once each, provided it is restricted to plus, times and brackets operations, declared the Engineer. He opened the delicate cover and made meticulous adjustments. “There, I have disposed it for one particular expression. Please put it to the test”.

    I chose three numbers, all greater than 1, and rotated the three dials to those positions. Then I cranked the handle until a delicate bell rang, and the result was indicated as 451. I made one more try, using the same three numbers although in a different order; this time the machine yielded 331.

    In ascending order, what were the three numbers I selected?

    [teaser3168]

     
    • Jim Randell's avatar

      Jim Randell 4:59 pm on 9 June 2023 Permalink | Reply

      Here is a generic solution:

      Each operation combines two numbers, so if we start with three numbers and end with one number there must be two operations involved.

      And if we get different results by reordering the numbers then the operations must be different.

      So we are looking at one of the following expressions:

      (a + b) × c
      (a × b) + c

      So we can start with the output number and try reversing one of the operations to give us two numbers, and then choose one of these numbers, reverse the other operation on it, and we end up with the three original numbers.

      We then need to find which of the expressions gives a sequence of input numbers that are common to both the output numbers.

      This Python program runs in 63ms. (Internal runtime is 4.7ms).

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, intersect, printf)

# destruct an addition
def destruct_add(n):
  for a in irange(2, n // 2):
    yield [a, n - a]

# destruct a multiplication
def destruct_mul(n):
  for (a, b) in divisors_pairs(n):
    if a > 1:
      yield [a, b]

# find sets that can give the result <n> using operations <ops>
def destruct(ns, ops):
  # are we done?
  if not ops:
    yield tuple(sorted(ns))
  else:
    op = ops[0]
    # choose one of the numbers to destruct
    for (i, x) in enumerate(ns):
      for xs in op(x):
        yield from destruct(ns[:i] + xs + ns[i + 1:], ops[1:])

# numbers to solve
ns = [451, 331]

# consider possible operation orders
exprs = {
  '(a * b) + c': (destruct_add, destruct_mul),
  '(a + b) * c': (destruct_mul, destruct_add),
}
for (k, ops) in exprs.items():
  # find input numbers in all sets
  for ss in intersect(destruct([n], ops) for n in ns):
    printf("{ns} -> {ss} [{k}]")

      Solution: The numbers are: 16, 19, 27.

      So the machine was set to calculate:

      (a × b) + c → result

      And the calculations were:

      a=16, b=27, c=19 → result = (16 × 27) + 19 = 451
      a=16, b=19, c=27 → result = (16 × 19) + 27 = 331

      Like

      • Jim Randell's avatar

        Jim Randell 10:47 pm on 9 June 2023 Permalink | Reply

        Or we can solve the specific problem from the puzzle text in a much faster way:

        (a × b) + c = x
        (a × c) + b = y
        ⇒
        (a + 1)(b + c) = x + y

        This Python program runs in 57ms. (Internal runtime is 98µs).

        Run: [ @replit ]

        from enigma import (irange, divisors_pairs, divf, divc, ordered, printf)

(x, y) = (451, 331)
for (p, q) in divisors_pairs(x + y, every=1):
  if p < 3: continue
  a = p - 1
  for c in irange(divc(y - q + 2, a), divf(y - 2, a)):
    b = q - c
    if a * b + c == x and a * c + b == y:
      printf("({x}, {y}) -> {ns}", ns=ordered(a, b, c))

        And this approach can be used to give a manual solution where there are only a few cases to consider.

        (But I still like the generic solution).

        Manually:

        331 is prime, so the expression cannot be of the form (a + b) × c, so we must be looking at (a × b) + c.

        So we need to find a, b, c such that:

        (a × b) + c = 451
        (a × c) + b = 331

        Adding these equations gives:

        (a + 1)(b + c) = 782

        And if we have:

        782 = p × q
        ⇒ a = p − 1; c = (331 − q) / (a − 1); b = q − c

        So we can examine the divisors of 782.

        There are only four possible decompositions: 1 × 782, 2 × 391, 17 × 46, 23 × 24.

        Hence a ∈ {16, 22, 33, 45}.

        And only a = 16 gives integer values for b and c.

        782 = 17 × 46 ⇒ a = 16; c = 19; b = 27

        Like

        • Frits's avatar

          Frits 11:06 pm on 9 June 2023 Permalink | Reply

          Nice, we already know that the first 2 divisors pairs can be ignored.

          Like

        • Frits's avatar

          Frits 11:05 pm on 10 June 2023 Permalink | Reply

          @Jim, I tried to understand the boundaries of your latest version and saw that the minimum for variable c wasn’t tight enough for the first value of a.

          We don’t have to loop over c as we can state:

          c = (y – q) / (a – 1)

          which has to be a whole number greater than 1

          Like

          • Jim Randell's avatar

            Jim Randell 11:36 pm on 10 June 2023 Permalink | Reply

            @Frits: That is cool. Makes things even simpler, and saves a few more µs.

            from enigma import (divisors_pairs, div, ordered, printf)

(x, y) = (451, 331)

for (p, q) in divisors_pairs(x + y, every=1):
  if p < 3: continue
  a = p - 1
  c = div(y - q, a - 1)
  if c is None or c < 2: continue
  b = q - c
  if b < 2: continue
  printf("({x}, {y}) -> {ns}", ns=ordered(a, b, c))

            Like

    • Frits's avatar

      Frits 6:37 pm on 9 June 2023 Permalink | Reply

      Less pythonic but more chance to optimise.

         
from enigma import divisor_pairs

# determine lowest number to minimize number of iterations
nums = sorted([451, 331])

# a + b + c and a * b * c are not possible (nothing changes)
# (a + b) * c is not possibe as 331 is a prime number

# check a + (b * c)
for a in range(2, nums[0] - 3):
  # ignore divisor_pair with 1
  for b, c in list(divisor_pairs(nums[0] - a))[1:]:
    # check 2 options
    if nums[1] in {b + (a * c), c + (b * a)}:
      pr("answer", sorted([a, b, c]))

      Like

      • Frits's avatar

        Frits 10:48 pm on 9 June 2023 Permalink | Reply

        More complex but a little different.

           
from enigma import is_square, div

# determine lowest number to minimise number of iterations
nums = sorted([451, 331])

# a + b + c and a * b * c are not possible (nothing changes)
# (a + b) * c is not possibe as 331 is a prime number


# check a + (b * c)

# I: a + b.c = 331, b + a.c = 451
#    a + b = 331 - 120 * b / (b - a)

for a in range(2, nums[0] - 3):
  for b in range(2, int((nums[0] - a) / 2) + 1):
    if b == a: continue
    if a + b != 331 - (120 * b) / (b - a): continue
    
    c, r = divmod(nums[1] - b, a)
    if r or c < 2: continue
    
    # double check 
    if a + b * c == nums[0]:
      pr("answer", sorted([a, b, c]))
    
# II: a + b.c = 331, c + a.b = 451
#     a.b^2 - 451b + 331 - a = 0
#     4a^2 - 1324a + 203401 must be square
for a in range(2, nums[0] - 3):
  D = 4 * a**2 - 1324 * a + 203401
  D = is_square(D) 
  if D is None: continue 
  
  for b in [d for i in (-1, 1) if (d := div(451 + i * D, 2 * a))]:
    c = nums[1] - a * b
    
    # double check 
    if c > 1 and a + b * c == nums[0]:
      pr("answer", sorted([a, b, c]))

        Like

  • Unknown's avatar

    Jim Randell 8:38 am on 8 June 2023 Permalink | Reply
    Tags:   

    Teaser 2052: Back to back 

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

    Your Teaser today is to take the 10 digits 0 to 9. Use three of them to make a three-figure prime number. Then write that number down backwards (i,e. with the digits in reverse order). Then take three of the remaining digits, use them to form a larger prime number, and write that number down backwards. Finally, use the remaining four digits to form a four-figure perfect square and then write that number down backwards. You should do all this in such a way that the sum of the two reversed primes equals the reversed square.

    What are the two primes?

    [teaser2052]

     
    • Jim Randell's avatar

      Jim Randell 8:39 am on 8 June 2023 Permalink | Reply

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

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

      Run: [ @replit ]

      #! python3 -m enigma -rr

#     C B A -> ABC is prime
#  +  F E D -> DEF is prime
#   -------
#   J I H G -> GHIJ is square
#   =======

SubstitutedExpression

"CBA + FED = JIHG"

"is_prime(ABC)"
"is_prime(DEF)"
"A < D"
"is_square(GHIJ)"

--answer="(ABC, DEF)"

      Solution: The two primes are: 467 and 523.

      And the sum is:

      764 + 325 = 1089

      Like

    • Frits's avatar

      Frits 1:19 pm on 8 June 2023 Permalink | Reply 

         
from enigma import is_square_p
from itertools import combinations

# prime numbers between 100 and 1000 with different digits
# without using digit 1
P = [3, 5, 7]
P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
P = [s for x in range(203, 1000, 2) if all(x % p for p in P) and 
     '1' not in (s := str(x)) and len(set(s)) == 3]

# pick two primes 
for p1, p2 in combinations(P, 2):
  # different digits
  if len(s := set(p1 + p2)) != 6: continue
  
  # sum of reversed primes should be a 4-digit number using different digits 
  sm = int(p1[::-1]) + int(p2[::-1])
  if sm < 1000 or s.difference(str(sm)) != s: continue
  # and a square
  if not is_square_p(sm): continue
  
  print(f"the two primes are {p1} and {p2}")

      Like

    • GeoffR's avatar

      GeoffR 7:46 am on 9 June 2023 Permalink | Reply 

      
from enigma import is_prime
from math import isqrt

def is_sq(x):
   return isqrt(x) ** 2 == x

digits = set('1234567890')

from itertools import permutations
for p1 in permutations(digits, 3):
    A, B, C = p1
    if '0' in (A, C):continue
    # 1st prime
    ABC = A + B + C
    if not is_prime(int(ABC)):continue
    q1 = digits.difference([A, B, C])
    
    # find 2nd prime
    for p2 in permutations(q1, 3):
        D, E, F = p2
        if D < A: continue  # 2nd prime > 1st prime
        if '0' in (D, F):continue
        DEF = D + E + F
        if not is_prime(int(DEF)):continue
        q2 = q1.difference(p2)
        for p3 in permutations(q2):
            G, H, I, J = p3
            if '0' in (G, J):continue
            GHIJ = G + H + I + J
            rGHIJ = GHIJ[::-1]
            
            # check sum of two reversed primes equals the reversed square
            if int(ABC[::-1]) + int(DEF[::-1]) == int(rGHIJ):
                if is_sq(int(rGHIJ)):
                    print(f"Two primes are {ABC} and {DEF}.")
                                            
# Two primes are 467 and 523.

      Like

  • Unknown's avatar

    Jim Randell 8:01 am on 6 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 973: Square-rigger 

    From The Sunday Times, 15th March 1981 [link]

    Young Mary, who is good at manipulating figures, was playing with her standard set of dominoes and seeing what numerical structures she could form with them, treating each half-domino as a digit according to its number of spots (“blank” being 0).

    Starting with double-6/double-5/double-4 laid end-to-end in a row, she built forwards and downwards from that beginning, placing dominoes across and apparently at  random, until she had completed a solid rectangle by slotting into the only remaining gaps, in its farther half, her last two dominoes which were 4-&-blank and 2-&-blank.

    Whereupon she called out to me: “Uncle, do come and look! I’ve managed to arrange all my dominoes in a rectangle so that the numbers formed by the four halves in each column are all dissimilar 4-digit squares”.

    “Are you quite sure about that?” I temporised.

    “Certain,” she replied. “And they’re pretty well in correct order of magnitude too!”.

    When I protested that this was quite impossible with dominoes, she said reproachfully: “But Uncle, I never said that ALL the squares appear in the right order, did I?  Actually there are just two of them — both among the seven smallest present — which do not; but every single square except those two is definitely just where it would be if all those appearing were strictly in order of magnitude”.

    She was perfectly correct. And you don’t need dominoes to figure out …

    Which four of Mary’s together formed columns 7 and 8 of her rectangle? (Use figures, e.g. 4-0 = four-&-blank).

    This was the final puzzle to use the title Brain-Teaser. The next puzzle was Brain teaser 974.

    [teaser973]

     
    • Jim Randell's avatar

      Jim Randell 8:04 am on 6 June 2023 Permalink | Reply

      A standard set of dominoes has 28 dominoes, each with 2 numbers on, so there are 56 numbers in total, consisting of 8 copies of each of the digits from 0 to 6.

      The program starts by constructing a list of square numbers that can be constructed using only the digits available on dominoes (i.e. the digits 0-6). It then constructs a viable sequence of squares that use the required 56 digits between them, and we consider swapping a pair of the numbers in the second half of the list to give Mary’s list of squares.

      We then turn the numbers into a 14×4 grid and use the [[ DominoGrid() ]] solver from the enigma.py library to find viable arrangements of dominoes.

      The program runs in 558ms. (Internal runtime is 412ms).

      Run: [ @replit ]

      from enigma import (
  DominoGrid, irange, subsets, multiset, flatten, unzip, union, group,
  update, seq_ordered as ordered, seq_get as get, join, printf
)

# available digits on dominoes
digits = set("0123456")

# find 4-digit squares that can be represented by dominoes
sqs = list()
for i in irange(32, 81):
  s = str(i * i)
  if not digits.issuperset(s): continue
  sqs.insert(0, s)

# construct viable sequences of squares (in descending order)
# - each of the digits 0-6 must be used exactly 8 times
# - the sequence must start: 6xxx, 6xxx, 5xxx, 5xxx, 4xxx, 4xxx
def squares(sqs, ds=None, ss=[]):
  # ds counts the digits remaining to be used
  if ds is None: ds = multiset.from_seq('0123456', count=8)
  # are we done?
  n = len(ss)
  if n == 14:
    yield ss
  elif not (n + len(sqs) < 14):
    # choose the next square to include
    for (i, sq) in enumerate(sqs):
      # 0, 1 must be 6xxx
      if n < 2:
        if sq[0] < '6': break
      # 2, 3 must be 5xxx
      elif n < 4:
        if sq[0] > '5': continue
        if sq[0] < '5': break
      # 4, 5 must be 4xxx
      elif n < 6:
        if sq[0] > '4': continue
        if sq[0] < '4': break
      # can we add sq to the sequence?
      if ds.issuperset(sq):
        # solve for the remaining squares in the list
        yield from squares(sqs[i + 1:], ds.difference(sq), ss + [sq])

# domino ordering
order = lambda xs: ordered(xs, reverse=1)

# find dominoes used in specified columns (1-indexed)
def dominoes(p, grid, cols):
  # indices of columns
  ks = union(irange(x - 1, 55, step=14) for x in cols)
  # find the dominoes at the specified indices
  g = group(ks, by=get(grid), f=get(p.grid))
  # extract dominoes that are entirely in selected columns
  for v in g.values():
    if len(v) == 2:
      yield order(v)

# collect solutions
rs = set()

# consider possible sequences of squares
for ss in squares(sqs):
  # choose two squares from index 7-13 to swap
  for (i, j) in subsets(irange(7, 13), size=2):
    ss_ = update(ss, [(i, ss[j]), (j, ss[i])])
    # construct the grid
    p = DominoGrid(14, 4, list(int(x) for x in flatten(unzip(ss_))))
    # and solve it
    for (grid, used) in p.solve(fixed=[(0, 1), (2, 3), (4, 5)]):
      # check that (4, 0) and (2, 0) occur in columns 8 - 14
      ds = set(dominoes(p, grid, irange(8, 14)))
      if not ((4, 0) in ds and (2, 0) in ds): continue

      # find the 4 dominoes in columns 7 and 8
      ds = order(dominoes(p, grid, [7, 8]))
      if len(ds) != 4: continue
      rs.add(ds)

      printf("squares = {ss_}", ss_=join(ss_, sep=" "))
      printf()
      p.output_solution((grid, used))
      printf("cols 7/8 = {ds}", ds=join(ds, sep=" "))
      printf("--")

# output solution
for ds in rs:
  printf("answer = {ds}", ds=join(ds, sep=" "))

      Solution: The dominoes making up columns 7 and 8 are: [6-0] [5-0] [3-3] [2-0].

      There is only one arrangement of square numbers that use each of the digits 0-6 exactly 8 times:

      6400, 6241, 5625, 5041, 4356, 4225, 3600, 3025, 3136, 3364, 2401, 2304, 1521, 1156

      And there are 2 (slightly) different ways the required grid can be constructed from a set of dominoes, here is one way:

      The [6-3] and [6-4] dominoes can be placed either horizontally or vertically to give the two layouts.

      If the indicated columns were swapped the squares would be in strict descending numerical order.

      The [2-0] and [4-0] dominoes (highlighted) were placed last in the right-hand half of the layout. If this condition is removed more arrangements are viable (16 in total), but the sequence of squares (and answer to the puzzle) remains the same.

      Like

  • Unknown's avatar

    Jim Randell 8:40 am on 4 June 2023 Permalink | Reply
    Tags:   

    Brain-Teaser 568: Batting averages 

    From The Sunday Times, 21st May 1972 [link]

    Allen and Biggin, stalwarts of our village cricket side, have an annual wager: whichever finishes the season with the lower batting average buys the other a dinner.

    Last season the result was in doubt until the last ball of the last match to which Allen, offering no stroke, was adjudged “out”, leg-before-wicket. Had he been given “not out” (which, incidentally, would have been the first “not out” innings either had played) his batting average — a whole number — would have beaten Biggin’s by exactly 0.5 of a run. In the event Biggin won by exactly 0.5 of a run.

    Both players comfortably passed a season’s total of 300 runs but neither reached 500. Biggin had three fewer innings than Allen.

    How many runs did Biggin score during the season?

    [Note for the non-cricketer: batting average is calculated by dividing a player’s total runs by his number of completed innings; i.e., times he was “out”].

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser568]

     
    • Jim Randell's avatar

      Jim Randell 8:41 am on 4 June 2023 Permalink | Reply

      If A’s average is A/a and B’s average is B/b, then we have:

      B/b − 1/2 = A/a
      B/b + 1/2 = A/(a − 1) = an integer
      a = b + 3
      300 < A, B < 500

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

      Run: [ @replit ]

      from enigma import (irange, divisors_pairs, div, printf)

# consider values for A's runs
for A in irange(301, 499):
  # A / (a - 1) is an integer
  for (a1, k) in divisors_pairs(A, every=1):
    a = a1 + 1
    b = a - 3
    if b < 1: continue

    # calculate B's runs (B/b - 1/2 = A/a)
    B = div((2 * A + a) * b, 2 * a)
    if B is None or not (300 < B < 500): continue
    # check (B/b + 1/2 = A/(a - 1))
    if not (a1 * (2 * B + b) == 2 * A * b): continue

    # output solution
    printf("A={A} B={B} a={a} b={b}")

      Solution: Biggin scores 369 runs.

      A is 420 for 21, an average of 20.

      B is 369 for 18, an average of 20.5.

      Had A been out only 20 times, his average would have been 21.

      Like

    • Frits's avatar

      Frits 7:47 pm on 4 June 2023 Permalink | Reply

      Two iterations.

       
from math import ceil

# A = a(a-1)

# A = a^2 - a > 300, (a - 1/2)^2 > 300.25, a - 1/2 > 17.328, a > 17.828
# A = a^2 - a < 500, (a - 1/2)^2 < 500.25, a - 1/2 < 22.367, a < 22.867

# make sure B is a whole number (a has to be odd)
mn = (a := int(300.25**.5 + 0.5)) + (2 if a % 2 else 1)
mx = ceil(500.25**.5 + 0.5)

# loop over odd a's
for a in range(mn, mx, 2):
  # B/b - 1/2 = A/a, B = (a - 1/2)b
  B = (a - 0.5) * (a - 3)
  if not (300 < B < 500): continue
  print(f"Biggin scored {int(B)} runs during the season")

      Like

    • GeoffR's avatar

      GeoffR 8:36 pm on 4 June 2023 Permalink | Reply 

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

var 301..499:A; % Allen's total runs in the season
var 301..499:B; % Biggin's total runs in the season

% 26 weeks looks a reasonable average time for a cricket season (Apr - Sept)
var 1..26: ai;  % Allen's total innings for the season
var 1..26: bi;  % Biggin's total innings for the season

% Allen's possible average scores are integers
constraint A mod ai == 0  /\ A mod (ai - 1) == 0 ;

% Biggin had three fewer innings than Allen
constraint ai == bi + 3;

% if Biggin wins by 1/2 point
% B / bi - 1 / 2 = A / ai
constraint 2 * (ai * B - bi * A) = ai * bi;

% if Allen wins by 1/2 point
% B / bi + 1 / 2 = A /(ai - 1)
constraint 2 * (A * bi - B *(ai -  1)) == (ai - 1) * bi;

solve satisfy;

output ["[A, ai, B, bi] = " ++ show( [A, ai, B, bi] )];

% [A, ai, B, bi] = [420, 21, 369, 18]
% ----------
% ==========

      Like

  • Unknown's avatar

    Jim Randell 3:59 pm on 2 June 2023 Permalink | Reply
    Tags:   

    Teaser 3167: Binary primes 

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

    Grace and Helen play a turn-based card game. Each player is given two cards with a 0 printed on them, and unlimited cards with a 1 printed on them. Before the game starts a 1 is placed on the table. Sitting on the same side of the table, a turn then involves placing a card to the left of the table cards, such that the value shown in binary remains prime or one (allowing leading zeros). The winner is the player who is last able to play a card, earning points equal to the value on the table at that time.

    Being expert logicians, they play the best possible cards to maximise their points or minimise their opponent’s points. Grace goes first.

    Who wins and with what cards on the table from left to right?

    [teaser3167]

     
    • Jim Randell's avatar

      Jim Randell 4:35 pm on 2 June 2023 Permalink | Reply

      This Python program plays the game with each player aiming to maximise their winnings (or minimise their losses) at each stage. So it performs a depth first traversal of the game tree.

      It runs in 56ms. (Internal runtime is 138µs).

      Run: [ @replit ]

      from enigma import (Accumulator, is_prime, int2base, compare, printf)

# explore the outcome of this move
def explore(n, k, a0, b0, rs):
  (rn, rk) = play(n, k, a0, b0)  # play the move
  rs.accumulate_data(-rn, rk)  # swap the result

# play the game with current value <n> from <k> cards
# player A to move, with <a0> zero cards
# player B has <b0> zero cards
# return (<pts>, <k>) [+ve for win, -ve for loss]
def play(n, k, a0, b0):
  # choose the best move (maximum points)
  rs = Accumulator(fn=max)
  # play 0
  if a0 > 0: explore(n, k + 1, b0, a0 - 1, rs)
  # play 1
  n_ = n + (1 << k)
  if is_prime(n_): explore(n_, k + 1, b0, a0, rs)
  # make the best available move
  if rs.count: return (rs.value, rs.data)
  # if there are no moves, current points go to opponent
  return (-n, k)

# play starting with value 1, on 1 card, and 2 zero cards for each player
(n, k) = play(1, 1, 2, 2)
# determine points won and the sequence of cards
pts = abs(n)
ss = int2base(pts, base=2, width=k)
# output solution
printf("{w} wins, {pts} pts, cards = {ss}", w=compare(n, 0, 'B?A'))

      Solution: Helen wins. The cards on the table are: (0 1 0 0 1 1 1 0 1).

      The game proceeds:

      start → (1) = 1
      G chooses 0 → (0 1) = 1
      H chooses 1 → (1 0 1) = 5
      G chooses 1 → (1 1 0 1) = 13
      H chooses 1 → (1 1 1 0 1) = 29
      G chooses 0 → (0 1 1 1 0 1) = 29
      H plays 0 → (0 0 1 1 1 0 1) = 29
      G plays 1 → (1 0 0 1 1 1 0 1) = 157
      H plays 0 → (0 1 0 0 1 1 1 0 1) = 157
      G cannot play; H wins 157 points

      The the final moves (0, 1, 0, out) are forced.

      There are 61 positions in the game tree, 17 of them are terminal positions, and only 2 of these are wins for the player who goes first.

      Like

      • Mark Valentine's avatar

        Mark Valentine 11:11 pm on 5 June 2023 Permalink | Reply

        What does run time vs zeros per person look like? How many zeroes can you reasonably solve for?

        Like

        • Jim Randell's avatar

          Jim Randell 10:43 am on 6 June 2023 Permalink | Reply

          Hi, Mark. Thanks for the puzzle!

          I ran my program for games with up to 28 zero cards per player. The number of positions grows at a reasonable rate, but things start to get a bit slow above z = 20.

          But we can switch to using the Miller-Rabin primality test [[ is_prime_mr() ]] for larger primes, which allows us to check up to z = 55 in under 1s (or [[ gmpy2.is_prime() ]] which is even faster).

           z    pos   winner       pts  runtime

 1     17    B            23
 2     61    B           157
 3    130    B            17
 4    237    B           769
 5    376    B          1223
 6    554    B          1223
 7    772    B         65543
 8   1036    B         65537
 9   1353    B         65537
10   1727    B       2097169
11   2141    B         65537
12   2631    B         65537
13   3158    B         65537
14   3770    B         65537
15   4455    B         65537
16   5220    B       2097169  [101ms]
17   6029    B         65537  [128ms]
18   6909    B         65537  [243ms]
19   7854    B         65537  [482ms]
20   8870    B         65537  [886ms]
21   9954    B         65537  [1.96s]
22  11130    B         65537  [5.34s]
23  12378    B     268435493  [10.7s]
24  13736    B         65537  [23.6s]
25  15160    B         65537  [38.6s]
26  16663    B  274877906957  [81.6s]
27  18234    B         65537  [ 161s]
28  19904    B         65537  [1279s] [107ms with is_prime_mr]
29  21668    B         65537          [127ms]
30  23532    B         65537          [156ms]
31  25463    B         65537          [181ms]
32  27475    B         65537          [213ms]
33  29559    B         65537          [225ms]
34  31731    B         65537          [253ms]
35  34001    B         65537          [265ms]
36  36384    B         65537          [292ms]
37  38847    B         65537          [305ms]
38  41407    B         65537          [336ms]
39  44048    B         65537          [346ms]

          z = 40 ends with a win for B with 302231454903657293676551 points.

          It doesn’t seem like going first is an advantage. In the z = 2 case only 2 of the 17 terminal positions are wins for A.

          Like

          • Mark Valentine's avatar

            Mark Valentine 3:37 pm on 6 June 2023 Permalink | Reply

            Impressive, it doesn’t blow up as much as I would have thought. I guess the primes becoming increasingly scarce helps.

            Like

    • Frits's avatar

      Frits 3:39 pm on 9 June 2023 Permalink | Reply

      @Jim, if you start with a list of prime numbers is there an upper limit for a prime number that you beforehand can determine?

      Like

      • Jim Randell's avatar

        Jim Randell 5:41 pm on 9 June 2023 Permalink | Reply

        @Frits: Do you mean can we determine what the largest possible value on the table can be without playing the game?

        Each position in the game must be a left-truncatable prime in binary (treating 1 as prime), and as there are a limited number of zeros, it is reasonable to suppose there are only a limited number of such primes. (See: Enigma 1075 for more on truncatable primes).

        With up to 4 zeros there are 28 left-truncatable binary primes, and the largest is:

        01100111101 = 829 [base 10]

        (Although determining this is pretty much the same as playing the game anyway).

        And 829 does indeed show up as the largest possible score for player B in the game tree.

        Like

    • Frits's avatar

      Frits 10:09 am on 11 June 2023 Permalink | Reply

      @Jim, thanks.

      On PuzzlingInPython (see below) I published a program where I start with a list of all prime numbers up to a certain limit where you keep pruning this list until you have all 17 games.

      I hoped to find by logic a limit on the number of consecutive 1’s but in some cases none of the new primes end on a 5 anymore (fi if the last used power of 2 ends on an 8 and your last prime ends on a 1 then your next primes will end on (7, 9, 3, 1, 7, 9, 3, 1, 7, ….) ).

      It was relative easy to generate the 17 games by recursion but picking the winner from this list I found difficult to program.

      Do you also plan to add some kind of binary tree implementation to enigma.py? I guess not that many puzzles you have published can be solved from a binary tree.

      [ https://brg.me.uk/?p=8290#comment-3820 ]

      Like

      • Jim Randell's avatar

        Jim Randell 3:33 pm on 12 June 2023 Permalink | Reply

        @Frits: In these game puzzles I usually find it is easiest to write a recursive function to do a depth first traversal of the game tree. From the current position you can examine all possible moves, and then choose the “best” one for the player, and this means we can determine what the outcome of a game is from the result of the initial position (presuming the players are aiming to maximise their metric at each position). (And in some games we don’t even need to explore the entire tree).

        I’ve done a couple of recent Tantalizer puzzles using this approach (see: Tantalizer 4, Tantalizer 7a), but there are other puzzles where the same approach works.

        This particular puzzle is relatively simple, in that there are at most two plays from any position (playing “0” or “1”), but in other games there may be many more plays available, so the game tree is not always binary.

        I didn’t really think about constructing the graph by starting from the all potential endpoints and then removing those that are not reachable. It seems that this might not be tractable on more complex games as the number of potential positions could be very large, and only a sparse subset of them would be reachable. I think it would be more efficient to build the tree going forward from the starting position.

        Like

  • Unknown's avatar

    Jim Randell 9:00 am on 1 June 2023 Permalink | Reply
    Tags:   

    Teaser 2108: Touch of magic 

    From The Sunday Times, 9th February 2003 [link]

    Place a single digit into each of the nine squares, such that:

    • There is no repeat in any row and no repeat in any column.
    • Each row, read in either direction, is a three-figure prime.
    • Each column, read up or down, is a three-figure prime.

    What is the sum of your nine digits?

    [teaser2108]

     
    • Jim Randell's avatar

      Jim Randell 9:01 am on 1 June 2023 Permalink | Reply

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

      The following run file executes in 79ms. (Internal runtime of the generated code is 11ms).

      Run: [ @replit ]

      #! python3 -m enigma -rr

SubstitutedExpression

#  A B C
#  D E F
#  G H I

# no repeats in rows/columns
--distinct="ABC,DEF,GHI,ADG,BEH,CFI"

# rows are 3-digit primes (in either direction)
"is_prime(ABC)" "is_prime(CBA)"
"is_prime(DEF)" "is_prime(FED)"
"is_prime(GHI)" "is_prime(IHG)"

# columns are 3-digit primes (in either direction)
"is_prime(ADG)" "is_prime(GDA)"
"is_prime(BEH)" "is_prime(HEB)"
"is_prime(CFI)" "is_prime(IFC)"

# answer is the sum of the digits
--answer="A + B + C + D + E + F + G + H + I"

--template="(ABC DEF GHI)"
--solution=""

      Solution: The sum of the digits is 50.

      One arrangement is:

      We also get a solution if we reverse the rows (left to right), or reverse the order of the rows (top to bottom), or both.

      Like

    • Frits's avatar

      Frits 5:19 pm on 2 June 2023 Permalink | Reply 

        
from itertools import permutations

# 143 prime numbers between 100 and 1000
P = [3, 5, 7]
P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
P = [str(x) for x in range(101, 1000, 2) if all(x % p for p in P)]

# a list of all valid prime numbers
p_both = [p for p in P if len(set(p)) == 3 and p[::-1] in P]
# a list of all valid prime numbers without it's reverse
p_single = [p for p in p_both if p[0] < p[2]]


#       2 ends  (also for middle layers)
#      /     \
#   +---+---+---+
#   |   |   |   |
#   +---+---+---+
#   |   |   |   | <-- edge
#   +---+---+---+
#   |   |   |   |
#   +---+---+---+
#      \  |  /
#     1 side

ends = set(y for x in p_single for y in (x[0], x[2]))
edges = set(x[1] for x in p_single if x[1] in ends)
middle_layers = [x[::k] for x in p_single if set([x[0], x[2]]) <= edges 
                 for k in (-1, 1)]

# a side of 3 cells must have an odd edge and it's edge must be an end
sides = [x[::k] for x in p_single if x[1] in "13579" and x[1] in ends 
         for k in (-1, 1)]

# pick 2 different sides for top and bottom horizontal layer
for p in permutations(sides, 2):
  s1, s2 = p
  # vertically digits may not match
  if any(s1[i] == s2[i] for i in range(3)): continue
  # pick a horizontal middel layer
  for m in middle_layers:
    # check column for prime numbers 
    if any(s1[i] + m[i] + s2[i] not in p_both for i in range(3)): continue
    sm = sum(int(s1[i]) + int(m[i]) + int(s2[i]) for i in range(3))
    print(f"{s1}\n{m}  with sum {sm}\n{s2}\n ")

      Like

    • GeoffR's avatar

      GeoffR 8:12 pm on 2 June 2023 Permalink | Reply 

      # reusing first part of Frits' code
P = [3, 5, 7]
P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
P = [str(x) for x in range(101, 1000, 2) if all(x % p for p in P)]

# a list of all valid reversed prime numbers - only 22 no.
p_both = [str(p) for p in P if len(set(p)) == 3 and p[::-1] in P]

# grid
# a b c = prime q1 
# d e f = prime q2 
# g h i = prime q3 

from enigma import all_different
from itertools import permutations

for p1 in permutations(p_both, 3):
    q1, q2, q3 = p1
    # find digits in L.H. column
    a, d, g =  q1[0],  q2[0],  q3[0]
    adg, gda = a + d + g, g + d + a
    if adg in p_both and gda in p_both:
        
       # find digits in middle column
       b, e, h =  q1[1], q2[1], q3[1]
       beh, heb = b + e + h, h + e + b
       if beh in p_both and heb in p_both:
           
           # find digits in R.H. column
           c, f, i = q1[2], q2[2], q3[2],
           cfi, ifc = c + f + i, i + f + c
           if cfi in p_both and ifc in p_both:
               # check all rows and columns are different
               if all_different(q1, q2, q3, adg, beh, cfi):
                   print(q1); print(q2); print(q3)
                   # find total of all digits in the grid
                   total = sum(int(i) for i in (a,b,c,d,e,f,g,h,i))
                   print('Total of all digits = ', total)
                   print()

# 937
# 743
# 179
# Total of all digits =  50

      Like

      • Frits's avatar

        Frits 1:39 pm on 3 June 2023 Permalink | Reply

        or

           
from itertools import permutations

# 143 prime numbers between 100 and 1000
P = [3, 5, 7]
P += [x for x in range(11, 33, 2) if all(x % p for p in P)]
P = [str(x) for x in range(101, 1000, 2) if all(x % p for p in P)]
 
# a list of all valid prime numbers
p_both = [p for p in P if len(set(p)) == 3 and p[::-1] in P]
 
for p in permutations(p_both, 3):
  # transpose the permutations to get the columns
  if any(''.join(col) not in p_both for col in zip(*p)): continue

  print('\n'.join(p))
  print("sum = ", sum(int(y) for x in p for y in x), "\n")

        Like

    • GeoffR's avatar

      GeoffR 2:56 pm on 3 June 2023 Permalink | Reply 

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

% a b c
% d e f 
% g h i 

% Reversible primes can only start or end  with 1,3,7 ot 9.
set of int: pr = {1,3,7,9}; 

var pr:a; var pr:b; var pr:c; 
var pr:d; var 0..9:e; var pr:f;
var pr:g; var pr:h; var pr:i; 

% Reversible primes, as  found in the Python solution
set of int: primes = {107, 149, 157, 167, 179, 347,
359, 389, 701, 709, 739, 743, 751, 761, 769, 907,
937, 941, 953, 967, 971, 983};

% Reversible prime rows and columns
constraint (100*a + 10*b + c) in primes;
constraint (100*c + 10*b + a) in primes;

constraint (100*d + 10*e + f) in primes;
constraint (100*f + 10*e + d) in primes;

constraint (100*g + 10*h + i) in primes;
constraint (100*i + 10*h + g) in primes;

constraint (100*a + 10*d + g) in primes;
constraint (100*g + 10*d + a) in primes;

constraint (100*b + 10*e + h) in primes;
constraint (100*h + 10*e + b) in primes;

constraint (100*c + 10*f + i) in primes;
constraint (100*i + 10*f + c) in primes;

% all rows and columns are different
constraint all_different([ (100*a + 10*b + c) ,
(100*d + 10*e + f), (100*g + 10*h + i), (100*a + 10*d + g),
(100*b + 10*e + h), (100*c + 10*f + i)]);

solve satisfy;

output[ show(a), show(b),show(c) ++
"\n" ++ show(d),show(e),show(f) ++
"\n" ++ show(g),show(h),show(i) ++
"\nDigit total = " ++ show(a+b+c+d+e+f+g+h+i)];

      Like

  • Unknown's avatar

    Jim Randell 7:40 am on 30 May 2023 Permalink | Reply
    Tags:   

    Teaser 2100: Uncle Hex 

    From The Sunday Times, 15th December 2002 [link]

    The standard hexadecimal notation used in some computations needs 16 “hex-digits”, so it uses 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E and F — e.g. the hex-number DEC15 represents the decimal number: 13×16⁴ + 14×16³ + 12×16² + 1×16 + 5 = 912405.

    Of course, only a few dates (like today’s) can look like a hex-number in that way (with some dates having a choice of hex-number, like DEC08/DEC8). My Uncle Hex and I have noticed we both have birthdays that look like hex-numbers. We have each worked out a decimal number that our birthday can represent and, comparing notes, we see that between them those two decimal numbers use each of the digits 0 to 9 at least once. Uncle Hex’s next birthday comes before mine.

    When is Uncle Hex’s birthday?

    Teaser 2100 – 2105 were originally published in The Sunday Times with the numbers 3000 – 3005.

    [teaser2100]

     
    • Jim Randell's avatar

      Jim Randell 7:41 am on 30 May 2023 Permalink | Reply

      This Python program generates all the dates in a leap year, and finds those that give viable “hex-dates” (obviously it would be more efficient to just consider months that consist entirely of hex digits).

      We then look for a pair of hex-dates that have values that between them use all 10 digits when represented in decimal form.

      It runs in 75ms. (Internal runtime is 12ms).

      Run: [ @replit ]

      from datetime import (date, timedelta)
from enigma import (repeat, inc, sprintf, base2int, catch, subsets, union, int2base, printf)

# generate possible "hex-dates"
def generate():
  # month names
  months = "? JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC".split()
  # consider dates in 2000 (a leap year)
  for d in repeat(inc(timedelta(days=1)), date(2000, 1, 1)):
    if d.year > 2000: break
    (m, d) = (months[d.month], d.day)
    for fmt in ["{m}{d}", "{m}{d:02d}"]:
      s = sprintf(fmt)
      v = catch(base2int, s, base=16)
      if v is not None:
        yield (s, v)

# collect "hex-dates"
d = dict(generate())

# find pairs that use 10 different digits when expressed in decimal
for ((k1, v1), (k2, v2)) in subsets(d.items(), size=2):
  ds = union(int2base(v, base=10) for v in (v1, v2))
  if len(ds) != 10: continue
  # output solution
  printf("{k1} -> {v1}; {k2} -> {v2}")

      Solution: Uncle Hex’s birthday is 4th February.

      The two dates are:

      FEB4 [base 16] = 65204 [base 10]
      DEC03 [base 16] = 912387 [base 10]

      The puzzle was set on 15th December, so the next of these dates to occur is 4th February.

      Like

      • Frits's avatar

        Frits 6:54 pm on 30 May 2023 Permalink | Reply

        @Jim, I don’t see the requirement that each “hex-date” has to use distinct digits.

        Like

        • Jim Randell's avatar

          Jim Randell 7:13 pm on 30 May 2023 Permalink | Reply

          I don’t know where that came from. The [[ is_duplicate() ]] test can be removed, and you still get the same answer.

          Like

      • Frits's avatar

        Frits 8:39 pm on 30 May 2023 Permalink | Reply

        Slow but more than three times faster with PyPy.

         
from enigma import SubstitutedExpression, int2base

months = "JAN FEB MAR APR MAY JUN JUL AUG SEP OCT NOV DEC"
days = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

# check for valid "hex-date"
def check(i):
  s = int2base(i, base=16)
  if not (3 < len(s) < 6): return 0
  f = months.find(s[:3])
  if f < 0: return 0
  
  d = s[3:]
  if not d.isnumeric(): return 0
  d = int(d)
  
  f //= 4            # so we have indices 0-11
  if not (0 < d <= days[f]): return 0
  
  return 100 * f + d
  
  
# the alphametic puzzle
p = SubstitutedExpression(
  [
    # uncle HEX: UVWXYZ     me: SOMERF
    
    "UVWXYZ > 43680", # start from AAA1
    
    "check(UVWXYZ)",
    "len(set([U, V, W, X, Y, Z])) >= 4",
    
    "SOMERF > 43681", # start from AAA2
    
    # those numbers use each of the digits 0 to 9 at least once
    "len(set([U, V, W, X, Y, Z, S, O, M, E, R, F])) == 10",
    
    # my number
    "check(SOMERF)",
    
    # uncle Hex's next birthday comes before mine
    "0 < check(UVWXYZ) < check(SOMERF)",
  ],
  answer="int2base(UVWXYZ, base=16)",
  d2i="",
  distinct="",
  env=dict(check=check),
  #reorder=0,
  verbose=0,    # use 256 to see the generated code
)

# print answers
for (_, ans) in p.solve():
  print(f"Uncle Hex's birthday: {ans}")

        Like

  • Unknown's avatar

    Jim Randell 4:29 pm on 26 May 2023 Permalink | Reply
    Tags: ,   

    Teaser 3166: All their marbles 

    From The Sunday Times, 28th May 2023 [link] [link]

    In their art class, Jack and Jill each had a box of spherical glass marbles. Each box contained marbles of at least three different sizes, and the radius of every marble was a whole number of cm.

    Jack placed three marbles of equal size from his box onto a desk, and placed each of the other [sizes] in turn on top so that all four marbles touched each other and formed a triangular pyramid. He worked out the height of each pyramid (from desk to top of top marble) and obtained a different whole number of cm each time.

    Jill was also able to do this with her marbles but they were all of different sizes to Jack’s.

    None of the pyramids was higher than 30cm.

    List all of the different marble radii in ascending order.

    [teaser3166]

     
    • Jim Randell's avatar

      Jim Randell 5:53 pm on 26 May 2023 Permalink | Reply

      Presumably “at least three” is “exactly three”, otherwise there would be multiple solutions.

      But I think this puzzle is flawed. We don’t find 2 possible sets of marbles that satisfy the specified conditions of the puzzle. Although by increasing the maximum allowable pyramid height we can find a solution to the puzzle as worded. But these involve quite sizeable marbles (using mm instead of cm would make the puzzle more reasonable).

      By calculating the height h of the the (not regular) tetrahedron formed by the centres of the spheres we can determine the height of a pyramidal configuration of spheres, and reject non-viable configurations. And we can then look for disjoint sets of three spheres (a base size and two viable top sizes) for Jack and Jill that give valid configurations.

      from enigma import (
  irange, subsets, sq, is_square, group, item, delete,
  cproduct, disjoint_union, arg, printf
)

MAX_H = arg(30, 0, int)  # max pyramid height
MAX_R = (MAX_H - 1) // 2  # max sphere radius

# calculate integer height of a pyramid configuration
# with base spheres radius <R> and top sphere radius <r>
def height(R, r):
  if R % 3 != 0: return
  # vertical height between centres of spheres = h
  h = is_square(sq(r) + 2 * R * r - sq(R) // 3)
  if h is None: return
  H = h + R + r
  # check it is a valid pyramid
  if not (H > 2 * R): return
  return H

# generate possible base/top radii
def generate():
  # consider possible radii
  for (R, r) in subsets(irange(1, MAX_R), size=2, select="P"):
    # calculate height of the pyramid = H
    H = height(R, r)
    # check it forms a pyramid with H not exceeding MAX_H
    if H is None or H > MAX_H: continue
    printf("[R={R} r={r} -> H={H}]")
    yield (R, r)

# group top radii by base radius
g = group(generate(), by=item(0), f=item(1))
# discard sets with fewer than 3 different sizes
g = delete(g, (k for (k, vs) in g.items() if len(vs) < 2))

# look for 2 disjoint sets of 3 radii
for ((k1, vs1), (k2, vs2)) in subsets(g.items(), size=2):
  for (ts1, ts2) in cproduct(subsets(vs, size=2) for vs in (vs1, vs2)):
    ss = disjoint_union([ts1, ts2, [k1, k2]])
    if ss is None: continue
    # output solution
    printf("radii = {ss} [base = {k1} + tops = {ts1}; base = {k2} + tops = {ts2}]", ss=sorted(ss))

      My interpretation of the puzzle text is that in order for the marbles to form a structure that could be described as a triangular pyramid, the uppermost point of the top marble in the arrangement must project above the uppermost points of the three marbles forming the base. So that three planar triangles, each supported by two of the base marbles and the top marble, would form the inclined faces of a triangular based pyramid that exactly encloses the marbles.

      However, with this interpretation, there is no solution to the puzzle with the restrictions given.

      If we increase the maximum allowed height of the arrangements (to between 72 and 95), we can find a unique solution using valid pyramids:

      set 1 = (7, 12, 14) [base = 12, top = 7 → height = 32; base = 12, top = 14 → height 48]
      set 2 = (13, 18, 21) [base = 18, top = 13 → height 54; base = 18, top = 21 → height 72]

      And this gives an answer of: (7, 12, 13, 14, 18, 21).

      The marbles are quite large though, so perhaps this would work better if the radii were specified in millimetres instead of centimetres.

      Another way to find a solution is to abandon the requirement for a “triangular pyramid” arrangement, and just place the three base marbles on the desk, touching each other in a triangular arrangement, and then place the fourth marble on top of these. And we measure the elevation of the uppermost point of the top marble above the desk. (We don’t care if this is below the level of the uppermost points of the base marbles, or at the same level).

      And using such arrangements we can get a unique solution within the height restriction given in the puzzle text:

      set 1 = (1, 6, 7) [base = 6, top = 1 → height 8; base = 6, top = 7 → height 24]
      set 2 = (2, 4, 12) [base = 12, top =2 → height 16; base = 12, top 4 → height 24]

      Which gives an answer of: (1, 2, 4, 6, 7, 12).

      And it seems likely this is the intended solution.

      And the published solution was: “1, 2, 4, 6, 7 and 12 cm”.

      Like

      • Frits's avatar

        Frits 9:52 pm on 26 May 2023 Permalink | Reply

        @Jim, using r = R in your height formula I don’t recognize the published height of a tetrahedron with 2 layers (2r(1 + sqrt(2/3)).

        No idea yet how to find the formula myself.

        Like

        • Jim Randell's avatar

          Jim Randell 10:01 pm on 26 May 2023 Permalink | Reply

          That is exactly what you get from my formula when R = r:

          H = 2r + √(r² +2r² − r²/3)
          H = 2r + √(8r²/3)
          H = 2r + 2r√(2/3)
          H = 2r(1 + √(2/3))

          The formula itself comes from a bit of trigonometry on a triangle whose hypotenuse connects the centres of the top sphere and one of the base spheres.

          Like

          • Frits's avatar

            Frits 10:38 pm on 26 May 2023 Permalink | Reply

            OK, I thought “h” was the height of the pyramid.

            Like

          • Frits's avatar

            Frits 11:01 pm on 26 May 2023 Permalink | Reply

            I verified your formula (using the formula for the distance between the centre of an equilateral triangle and any of its vertices)

            Like

      • Jim Randell's avatar

        Jim Randell 10:59 pm on 27 May 2023 Permalink | Reply

        If we ignore all the stuff about making “pyramids”, and just arrange 3 marbles of the same size in a triangular arrangement on the desk, with each marble touching the other two, and then place a different size fourth marble on top of these three marbles in the hollow between the lower three marbles. We can then measure the distance between the surface of the desk and the top of the fourth marble. And it is this distance we require to be an integer.

        With this wording the puzzle does have a unique solution, with distances not exceeding 30cm, and it is quite possible these are the sets the setter was intending us to find.

        My program (above) can be adapted for this scenario by removing the validity check at line 18.

        I’ve also made a more generic program that allows you to experiment with various criteria for valid configurations:

        from enigma import (
  irange, subsets, sq, is_square, group, item, delete,
  cproduct, disjoint_union, compare, sqrt, arg, printf
)

MAX_H = arg(30, 0, int)  # max pyramid height
MAX_R = MAX_H - 2  # max sphere radius

# if the r/R ratio is not less than this the bounding pyramid cannot be formed
MAX_Q = 1 + sqrt(1, 3)

# calculate integer height of a pyramid configuration
# with base spheres radius <R> and top sphere radius <r>
def height(R, r):
  if MAX_Q and not (r < R * MAX_Q): return
  if R % 3 != 0: return
  # vertical height between centres of spheres = h
  h = is_square(sq(r) + 2 * R * r - sq(R) // 3)
  if h is None: return
  H = h + R + r
  # return appropriate configurations:
  # H < 2 * R -> indented pyramid
  # H = 2 * R -> flat topped pyramid (frustum)
  # H > 2 * R -> normal pyramid
  c = compare(H, 2 * R)
  if c < 0: return H   # indented
  if c == 0: return H  # flat
  if c > 0: return H   # normal

# generate possible base/top radii
def generate():
  # consider possible radii
  for (R, r) in subsets(irange(1, MAX_R), size=2, select="P"):
    # calculate height of the pyramid = H
    H = height(R, r)
    # check it forms a pyramid with H not exceeding MAX_H
    if H is None or H > MAX_H: continue
    printf("[R={R} r={r} -> H={H}]")
    yield (R, r)

# group top radii by base radius
g = group(generate(), by=item(0), f=item(1))
# discard sets with fewer than 3 different sizes
g = delete(g, (k for (k, vs) in g.items() if len(vs) < 2))

# look for 2 disjoint sets of 3 radii
for ((k1, vs1), (k2, vs2)) in subsets(g.items(), size=2):
  for (ts1, ts2) in cproduct(subsets(vs, size=2) for vs in (vs1, vs2)):
    ss = disjoint_union([ts1, ts2, [k1, k2]])
    if ss is None: continue
    # output solution
    printf("radii = {ss} [base = {k1} + tops = {ts1}; base = {k2} + tops = {ts2}]", ss=sorted(ss))

        Like

  • Unknown's avatar

    Jim Randell 10:33 am on 25 May 2023 Permalink | Reply
    Tags:   

    Teaser 2183: The punishment fits the crime 

    From The Sunday Times, 18th July 2004 [link]

    Recently I was teaching the class about Pascal’s triangle, which starts:

    1
    1  1
    1  2  1
    1  3  3  1
    1  4  6  4  1

    Subsequent rows have a 1 at each end of each row, with any other number in the row obtained by adding the two numbers diagonally above it. Then a row gives, for example:

    (1 + x)⁴  = 1 + 4x + 6x² + 4x³ + x⁴

    Six pupils disrupted the lesson, and so I kept them in after school. I gave each of them a different prime number and told them to work out its 10th power without a calculator.

    “That’s too easy”, said Blaise, whose prime was 3. “I’ll work out the product of everyone else’s answers instead”. Then she read out the 41-digit answer and left!

    What was her 41-digit answer?

    [teaser2183]

     
    • Jim Randell's avatar

      Jim Randell 10:34 am on 25 May 2023 Permalink | Reply

      In order for the 10th power to be a 41 digit number the product of the 5 primes must be in the range:

      min = ceil(10^(40/10)) = ceil(10^4) = 10000
      max = floor(10^(41/10)) = floor(10^4.1) = 12589

      Excluding 3, the five smallest primes are (2, 5, 7, 11, 13) which have a product of 10010, which is in the range we require.

      And:

      10010^10 = 10100451202102522101200450100010000000000

      We can calculate this number using Pascal’s Triangle as follows:

      10010^10 = (10(1000 + 1))^10
      = (10^10)(1000 + 1)^10

      And row 10 (numbering from 0) of Pascal’s triangle is:

      10: (1  10  45  120  210  252  210  120  45  10  1)

      So we can calculate (1000 + 1)^10, using the polynomial derived from this row with x = 1000).

      The terms are separated by 1000, and each value in the row is 3 digits or less, so we can just write the result out by padding the values in the row to 3 digits:

      001 010 045 120 210 252 210 120 045 010 001

      Multiplying this by 10^10 just involves adding 10 zeros to the end, to give the 41 digit number:

      10100451202102522101200450100010000000000

      Or using Python.

      The following Python program runs in 57ms. (Internal runtime is 228µs).

      Run: [ @replit ]

      from enigma import (intc, intf, fdiv, primes, inf, subsets, diff, multiply, ndigits, printf)

def solve(n, k):
  # min and max products for an n digit number
  m = intc(pow(10, fdiv(n - 1, k)))
  M = intf(pow(10, fdiv(n, k)))
  printf("[n={n} -> [{m}, {M}]]")

  # consider the largest prime
  for p in primes.irange(2, inf):
    if p == 3: continue
    # choose 4 smaller primes (excluding 3)
    f = 0
    for ps in subsets(diff(primes.between(2, p - 1), [3]), size=4, fn=list):
      ps.append(p)
      x = multiply(ps)
      if x > M:
        if f == 0: return
        break
      if not (x < m or x > M):
        x10 = pow(x, 10)
        printf("{ps} -> {x} -> {x10} [{d} digits]", d=ndigits(x10))
      f = 1

# solve for 41 digit numbers
solve(41, 10)

      Like

    • GeoffR's avatar

      GeoffR 4:45 pm on 26 May 2023 Permalink | Reply 

      primes = (2, 5, 7, 11, 13, 17, 19)  # prime 3 excluded from description

# The highest product of primes to power of 10 in the tuple below
# .. i.e. (7,11,13,17,19) gives a 56 digit number
# .. so a more than an adequate range to find a 41 digit product.

from itertools import combinations

for P1 in combinations(primes, 5):
    # choose 5 primes from a tuple of 7 primes
    p1, p2, p3, p4, p5 = P1

    num = p1**10 * p2**10 * p3**10 * p4**10 * p5**10
    if len(str(num)) == 41:
       print(f"41 digit number is {num}")
       exit()  # only one answer needed

# 41 digit number is 10100451202102522101200450100010000000000

      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