by: Robin Nayler

Tagged: by: Robin Nayler Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:27 am on 8 April 2025 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2547: Multiple celebration
From The Sunday Times, 17th July 2011 [link] [link]

Today is my birthday and the birthday of my granddaughter Imogen. My age today is a whole-number multiple of hers, and this has been true on one third of our joint anniversaries.

If we both live until I am six times her current age, then my age will be a multiple of hers on two more birthdays.

How old are we today?

[teaser2547]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:27 am on 8 April 2025 Permalink | Reply
  This Python program runs in 63ms. (Internal runtime is 139µs).
```
from enigma import (irange, is_divisor, printf)

# find multiple anniversaries for [a, b] and [a+d, b+d]
def multiples(d, a, b):
  for x in irange(a, b):
    y = x + d
    if is_divisor(y, x):
      yield (x, y)

# consider possible ages for the granddaughter (must be a multiple of 3)
for g in irange(3, 20, step=3):
  # consider the setters age (a multiple of g, less than 6g)
  for k in [2, 3, 4, 5]:
    s = k * g

    # calculate earlier multiples
    d = s - g
    ms = list(multiples(d, 1, g))
    # exactly 1/3 of the joint anniversaries so far are multiples
    if not (len(ms) * 3 == g): continue

    # and in there future there will be 2 more multiple anniversaries
    ms_ = list(multiples(d, g + 1, 6 * g - d))
    if not (len(ms_) == 2): continue

    # output solution
    printf("g={g} s={s} [k={k} d={d}] -> {ms} {ms_}")
```
  Solution: The setter is 72. The granddaughter is 18.
  
  So the age difference is 54 years.
  
  The multiples in the past are:
  
  1 year old & 55 years old (multiple = 55)
  2 years old & 56 years old (multiple = 28)
  3 years old & 57 years old (multiple = 19)
  6 years old & 60 years old (multiple = 10)
  9 years old & 63 years old (multiple = 7)
  18 years old & 72 years old (multiple = 4)
  
  Which is 6 anniversaries out of 18, so one third of them are multiples.
  
  In the future (with the setters age up to 6 × 18 = 108) we can have the following multiples:
  
  27 years old & 81 years old (multiple = 3)
  54 years old & 108 years old (multiple = 2)
  
  LikeLike
Reply Cancel reply
Required fields are marked *

Name *

Email *

Website

Notify me of new comments via email.
Notify me of new posts via email.
Δ

This site uses Akismet to reduce spam. Learn how your comment data is processed.
Jim Randell 10:22 pm on 3 January 2025 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2589: A certain age
From The Sunday Times, 6th May 2012 [link] [link]

My cousin and I share a birthday. At the moment my age, in years, is the same as hers but with the order of the two digits reversed. On one of our past birthdays I was five times as old as her but, even if I live to a world record “ripe old age”, there is only one birthday in the future on which my age will be a multiple of hers.

How old am I?

[teaser2589]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Hugo and Jim Randell are discussing. Toggle Comments
- Jim Randell 10:22 pm on 3 January 2025 Permalink | Reply
  Suppose my age is XY and my cousin’s age is YX, then we have X > Y.
  
  This Python program runs in 63ms. (Internal runtime is 306µs).
```
from enigma import (irange, subsets, printf)

# ages are the reverse of each other
for (Y, X) in subsets(irange(1, 9), size=2):
  (XY, YX) = (10 * X + Y, 10 * Y + X)

  # look for an age in the past where I was five times the age of the cousin
  past = ((XY - n, YX - n) for n in irange(1, YX - 1))
  x1 = list((x, y) for (x, y) in past if x == 5 * y)
  if not x1: continue

  # look for ages in the future where my age is a multiple of hers
  future = ((XY + n, YX + n) for n in irange(1, 130 - XY))
  x2 = list((x, y) for (x, y) in future if x % y == 0)
  if len(x2) != 1: continue

  # output solution
  printf("XY={XY} YX={YX} [past={x1} future={x2}]")
```
  Solution: Your age is 62.
  
  And the cousin’s age is 26.
  
  17 years ago the ages were 45 and 9 (and 45 = 5 × 9).
  
  In 10 years time the ages will be 72 and 36 (and 72 = 2 × 36).
  
  LikeLike
- Hugo 7:23 am on 5 January 2025 Permalink | Reply
  
  The difference between the ages is 9(X – Y).
  That remains the same each year, and at one time it was 4 times the cousin’s age.
  So (X – Y) is either 4 or 8.
  The current ages could be 15, 51; 26, 62; 37, 73; 48, 84; or 59, 95.
  In all cases the difference is 36.
  Ages when one age is an integer multiple of the other are 1, 37; 2, 38; 4, 40; 9, 45; 18, 54; 36, 72.
  Only one of those is allowed to be in the future.
  
  Alternatively, the current ages could be 19, 91, with difference 72.
  Then the ‘multiple’ ages are 1, 73; 2, 74; 4, 76; 8, 80; 9, 81; 18, 90; 36, 108; 72, 144.
  But two of those are in the future.
  The only valid solution appears to be 26, 62.
  
  LikeLike
- Hugo 7:32 am on 6 January 2025 Permalink | Reply
  
  I forgot some pairs of ages where one is an integer multiple of the other.
  With a difference 36: 3, 39; 6, 42; 12, 48.
  Similarly with a difference 72, but we’ve eliminated that as a potential solution.
  
  LikeLike
Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2623: Latecomer
From The Sunday Times, 30th December 2012 [link] [link]

Imogen is having a New Year party tomorrow night and she has invited Madeline, hoping not to have a repeat of last year’s episode which completely spoilt the celebrations. Last New Year’s Eve Madeline had been due at a certain whole number of minutes past an hour but she was late, the number of minutes late being that same aforementioned “certain number of minutes” but with the digits in the reverse order. Madeline pointed out that at least the angle between the hands of the clock at the moment of her arrival was the same as it would have been when she was due.

At what time was she due to arrive?

[teaser2623]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
  Madeline was expected to arrive at a time of xy minutes past a specified hour, but she was late, and arrived yx minutes later than her expected time. So yx (and xy) cannot be 00 (as then she would not be late).
  
  This Python program finds both possible solutions to the puzzle.
  
  It runs in 74ms. (Internal runtime is 3.6ms).
  
  Run: [ @replit ]
```
from enigma import (Rational, irange, cproduct, nrev, printf)

Q = Rational()

# calculate angle between hands at time h:m
# angles are between 0 (coincident) and 1 (opposite)
def angle(h, m):
  (x, m) = divmod(m, 60)
  h = (h + x) % 12
  ah = Q(h + Q(m, 60), 6)
  am = Q(m, 30)
  a = abs(ah - am)
  return (2 - a if a > 1 else a)

# consider possible scheduled arrival times
for (h, m) in cproduct([irange(0, 11), irange(1, 59)]):
  a1 = angle(h, m)
  # calculate angle at actual arrival time
  a2 = angle(h, m + nrev(m, 2))
  # are angles the same?
  if a1 == a2:
    # output solution
    printf("expected arrival = {h:02d}:{m:02d} [angle = {a:.2f} min]", a=float(a1 * 30))
```
  There are two possible answers:
  
  Expected time = 11:43; Actual time = 11:43 + 34 minutes = 12:17
  Expected time = 5:43; Actual time = 5:43 + 34 minutes = 6:17
  
  Both of which are illustrated below, with the same shape indicating the identical angles between the hands:
  
  As the party in question is a New Years Eve party, presumably the setter intends us to choose the solution where Madeline was expected to arrive before midnight, but actually arrived after midnight (although this could easily have been specified in the problem text).
  
  Solution: Madeline was due to arrive at 11:43 pm.
  
  LikeLike

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply
Tags: by: Robin Nayler

Teaser 2578: The right money

From The Sunday Times, 19th February 2012 [link] [link]

In order to conserve his change, Andrew, our local shopkeeper, likes to be given the exact money. So today I went to Andrew’s shop with a collection of coins totalling a whole number of pounds in value. I could use these coins to pay exactly any amount from one penny up to the total value of the coins. Furthermore, the number of coins equalled the number of pounds that all the coins were worth; I had chosen the minimum number of coins to have this property.

(a) How many coins did I have?
(b) For which denominations did I have more than one coin of that value?

[teaser2578]

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply

I am assuming we are using “standard” UK coinage which was in circulation at the time of the publication of the puzzle. These are: 1p, 2p, 5p, 10p, 20p, 50p, £1 (= 100p), £2 (= 200p).

There are special commemorative 25p and £5 coins, but these are not commonly used in making purchases.

We can get a nice compact program without doing any particular analysis (like determining there must be at least one 1p coin), and it runs in just under 1s, so it not too bad. (I also tried a custom express() routine which makes an amount using an exact number of coins, but it was only a little bit faster).

We are going to need at least 10 coins to be able to make the required different amounts (with a set of 10 different coins there are 2^10 − 1 = 1023 subsets, which could potentially allow all values from 1p – 1000p to be made, but with fewer coins there will be insufficiently many subsets).

This Python program runs in 860ms (using PyPy).

Run: [ @replit ]

from enigma import (irange, inf, subsets, multiset, printf)

# coin denominations (in pence)
coins = (1, 2, 5, 10, 20, 50, 100, 200)

# consider number coins (= total value in pounds)
for n in irange(10, inf):
  done = 0
  # choose n coins ...
  for vs in subsets(coins, size=n, select='R', fn=multiset.from_seq):
    # ... with a total value of n pounds
    if vs.sum() != 100 * n: continue
    # can we make all values between 1 and 100n using these coins?
    if not all(any(vs.express(x)) for x in irange(1, 100 * n)): continue
    # output solution
    printf("{n} coins -> {vs}", vs=vs.map2str(arr='p x', sep='; '))
    done = 1
  if done: break

Solution: (a) There are 16 coins; (b) There is more than one of the 2p, 10p, £2 coins.

The collection is:

1× 1p
2× 2p
1× 5p
2× 10p
1× 20p
1× 50p
1× £1
7× £2
total = £16 in 16 coins

If we additionally allow 25p and £5 coins we can achieve the answer using only 13 coins:

1× 1p
2× 2p
2× 5p
1× 10p
1× 25p
1× 50p
1× £1
3× £2
1× £5
total = £13 in 13 coins

1x 1p
2× 2p
1× 5p
2× 10p
1× 20p
1× 50p
1× £1
3× £2
1× £5
total = £13 in 13 coins

LikeLike

Frits 1:30 pm on 1 July 2024 Permalink | Reply
Lucky for you the coin denominations weren’t something like [1, 2, 5, 10, 20, 50, 101, 104].
```
 
-------- number of coins: 182 [1, 2, 1, 1, 2, 1, 2, 172]
```
LikeLike

Jim Randell 2:21 pm on 3 July 2024 Permalink | Reply

I’ve just realised that [[ multiset.express() ]] already supports making an amount with a specific number of coins, so my code can be a bit more compact (and faster).

Run: [ @replit ]

from enigma import (irange, inf, multiset, printf)

# coin denominations
coins = (1, 2, 5, 10, 20, 50, 100, 200)

# consider total value in pounds
for n in irange(10, inf):
  done = 0
  # make a total of n pounds using exactly n coins
  tot = 100 * n
  for vs in multiset.from_seq(coins, count=n).express(tot, n):
    # can we make all other values between 1 and tot using these coins?
    if not vs.expressible(irange(1, tot - 1)): continue
    # output solution
    printf("{n} coins -> {vs}", vs=vs.map2str(arr='p x', sep='; '))
    done = 1
  if done: break

LikeLike

Frits 2:55 pm on 3 July 2024 Permalink | Reply
I know you said you were not doing any particular analysis but with this update the program is faster especially for more difficult cases.
```
if not all(any(vs.express(x)) for x in irange(1, max(vs) - 1)): continue     
```
LikeLike
- Jim Randell 4:24 pm on 3 July 2024 Permalink | Reply
  
  @Frits: Good idea!
  
  LikeLike

Jim Randell 8:43 am on 5 July 2024 Permalink | Reply

The following approach builds up increasing sets of coins that can make change for all values from 1..n, by adding a coin to the previous sets. We can expand a set by adding another instance of the largest denomination in the set, or we can add a larger denomination coin only if we can already make all values lower than it.

This program runs (under PyPy) in 125ms (internal runtime is 37ms).

Run: [ @replit ]

from enigma import (multiset, printf)

# coin denominations (in pence)
coins = (1, 2, 5, 10, 20, 50, 100, 200)

# build up increasing sets of coins that cover range 1..n
assert 1 in coins
(ss, tgt, done) = ([(0, [])], 0, 0)
while not done:
  tgt += 100
  ss_ = list()
  # consider current sets
  for (n, vs) in ss:
    m = (vs[-1] if vs else 0)
    # and try to add in another coin
    for d in coins:
      if d < m: continue
      if d - 1 > n: break
      (n_, vs_) = (n + d, vs + [d])
      if n_ == tgt:
        printf("{k} coins -> {vs}", k=len(vs_), vs=multiset.from_seq(vs_).map2str(arr="p x", sep="; "))
        done += 1
      ss_.append((n_, vs_))
  ss = ss_

printf("[{done} solutions]")

Note that with the following 16 coins we can make change for all values up to 1610p:

1× 1p
2× 2p
1× 5p
1× 10p
2× 20p
1× 50p
1× 100p
7× 200p
total = £16.10 in 16 coins

LikeLike

Frits 2:20 pm on 5 July 2024 Permalink | Reply

Jim’s clever latest program can use a lot of memory and become quite slow for some denominations (like “pypy3 teaser2578.py 1 2 5 10 39 71 103 131”).
His program suggested to me there might be a minimal number of pounds to have a solution. This minimal number of pounds can be used with his earlier program (unfortunately not with my program (of which I made a similar recursive version)).

from enigma import (irange, inf, multiset, map2str, printf)
from sys import argv

# coin denominations (in pence)
coins = ([1, 2, 5, 10, 20, 50, 100, 200] if len(argv) == 1 else
         list(int(x) for x in argv[1:]))

# build up increasing sets of coins that cover range 1..n
assert 1 in coins
coins.sort()

print(f"{coins = }") 

# determine the minimal number of pounds for which a solution is feasible
(tgt, ss, done, strt) = (0, [(0, [])], 0, 10)
while not done and tgt < 1000000:
  tgt += 100
  if tgt - ss[-1][0] <= coins[-1]:   # within reach
    if tgt > coins[-1]:  
      strt = tgt // 100
      print("minimal number of pounds:", strt)
      done = 1
      continue 
  
  ss_ = list()
  # consider current sets
  for (n, vs) in ss:
    m = (vs[-1] if vs else 0)
    # and try to add in another high coin
    for d in coins[::-1]:
      if d < m: continue     # not below minimum 
      # don't choose a coin higher than <n + 1>
      # otherwise number <n + 1> can never me made
      if d - 1 > n: continue
      ss_.append((n + d, vs + [d]))
      break # we have found the highest coin
  ss = ss_
  

if strt > 26:  # this can be changed to a better value
  print("Jim 1")
  # consider total value in pounds
  for n in irange(strt, inf):
    done = 0
    # make a total of n pounds using exactly n coins
    tot = 100 * n
    for vs in multiset.from_seq(coins, count=n).express(tot, n):
      # can we make all other values between 1 and tot using these coins?
      #if not vs.expressible(irange(1, tot - 1)): continue
      if not vs.expressible(irange(1, max(vs) - 1)): continue
      # output solution
      printf("{n} coins -> {vs}", vs=vs.map2str(arr='p x', sep='; '))
      done = 1
    if done: break  
else:
  print("Jim 2")
  (tgt, ss, done) = (0, [(0, [])], 0)
  while not done:
    tgt += 100
    ss_ = list()
    # consider current sets
    for (n, vs) in ss:
      m = (vs[-1] if vs else 0)
      # and try to add in another coin
      for d in coins:
        if d < m: continue
        if d - 1 > n: break
        (n_, vs_) = (n + d, vs + [d])
        if n_ == tgt:
          printf("{k} coins -> {vs}", k=len(vs_), vs=multiset.from_seq(vs_).map2str(arr="p x", sep="; "))
          done += 1
        ss_.append((n_, vs_))
    ss = ss_
   
  printf("[{done} solutions]")

LikeLike

Frits 1:25 pm on 1 July 2024 Permalink | Reply

For this program I didn’t try to keep every line within 80 bytes (it is already a bit messy).
I used a performance enhancement I don’t understand myself and I used break statements that I theoretically are not supposed to make. So far I have not encountered a case that differs from Jim’s program. The programs supports different coin denominations and also more than 8.

With the performance enhancement the program runs in 21ms.

from math import ceil
from sys import argv

# coin denominations
coins = (1, 2, 5, 10, 20, 50, 100, 200) if len(argv) == 1 else list(int(x) for x in argv[1:])
N = len(coins)
M = 20      # maximum quantity
vars = "abcdefghijklmnopqrstuxwxyz"
print(f"{coins = }, {N = }")
mn = 1e8    # minimum number of coins

# make number <n> for specific deniminations and quantities
def make(n, t, k, denoms, qs, ns=set(), ss=[]):
  if t == 0:
    yield ns | {n}
  if k :
    v, q = denoms[0], qs[0]
    ns.add(n - t)
    for i in range(min(q, t // v) + 1):
      yield from make(n, t - i * v, k - 1, denoms[1:], qs[1:], ns, ss + [i])
   
# make all numbers from <strt> to <n>      
def make_all(n, denoms, qs, strt=1):
  todo = set(i for i in range(strt, n + 1))  
  ln = len(denoms)
  while todo:
    n = max(todo)
    # make number <n>
    for made in make(n, n, ln, denoms, qs): 
      break
    else: return False  
    
    todo -= made
  return True

# enhance performance (don't know why this is the case)
if N < 9:
  _ = make_all(sum(qs := [2] * N) * 100, coins, qs)
  
exprs = ""

exprs += "mn, cnt = 1e8, 0\n\n"  
exprs += "def check(lev, qs, tv, mn, make=1):\n"
exprs += "  global cnt\n"  
exprs += f"  if mn < 1e8:\n"
exprs += "    # calculate minimum last quantity\n"  
exprs += "    h_ = ceil((100 * mn - tv) / coins[-1])\n"  
exprs += "    if sum(qs) + h_ > mn:\n"  
exprs += "      return 'break'\n"  

exprs += "  if make:\n"  
exprs += "    n = coins[lev] - 1\n"  
exprs += "    if tv < n: return False \n"  
exprs += "    strt = 1 + coins[lev - 1] if lev > 1 else 1\n"  
exprs += "    cnt += 1\n"  
exprs += "    # can we make numbers <strt>...<n> with these denominations?\n"  
exprs += "    if not make_all(n, coins[:lev], qs, strt):\n"  
exprs += "      return False\n"
exprs += "  return True\n\n"  

exprs += f"make_{vars[0]} = 1\n"
exprs += f"# can we make numbers 1..<total pence> with denominations {coins}?\n"

last_odd = [i for i, x in enumerate(coins) if x % 2][-1]
sols = dict()

for i in range(1, N + 1):
  if i < N: 
    # our worst case scenario is if we have only one odd denomination and we check
    # all combinations with only one coin of 1 with no chance of achieving an 
    # even number of pence
    if last_odd == 0 and i == 1:
      exprs += f"{'  '* (i - 1)}for {vars[i - 1]} in range({coins[1] - (coins[1] % 2)}, {max(coins[1] - (coins[1] % 2) + 15, M) if i != N - 1 else 2 * M}, 2):\n"
    elif last_odd == i - 1 and i != N:
      exprs += f"{'  '* (i - 1)}for {vars[i - 1]} in range(prod_{vars[i - 2]} % 2, max(prod_{vars[i - 2]} % 2 + 15, M) if i != N - 1 else {2 * M}, 2):\n"  
    else:  
      exprs += f"{'  '* (i - 1)}for {vars[i - 1]} in range({coins[1] - 1 if i == 1 else 0}, {max(coins[1] + 14 if i == 1 else 0, M) if i != N - 1 else 2 * M}):\n"
      
    if i == N - 1: 
      exprs += f"{'  '* i}tot = sum(lst_{vars[i - 2]}) + {vars[i - 1]}\n"
      if coins[-2] != 100:
        exprs += f"{'  '* i}# calculate last quantity so that the total is a multiple of 100\n"
        exprs += f"{'  '* i}{(last := vars[i])}, rest = divmod(prod_{vars[i - 2]} + {vars[i - 1]} * {coins[i - 1]} - "
        exprs += f"100 * tot, 100 - coins[-1])\n"
        exprs += f"{'  '* i}if rest or {last} < 0: continue\n"  
    
    exprs += f"{'  '* i}# can we make numbers 1..{coins[i] - 1} with denominations {coins[:i]}\n"
    exprs += f"{'  '* i}if not (chk := check({i}, lst_{vars[i - 1]} := [{', '.join(vars[:i])}],\n"
    if i > 1:
      exprs += f"{'  '* i}                        prod_{vars[i - 1]} := prod_{vars[i - 2]} + {vars[i - 1]} * {coins[i - 1]},\n"
    else:
      exprs += f"{'  '* i}                        prod_{vars[i - 1]} := {vars[i - 1]} * {coins[i - 1]},\n"  
    exprs += f"{'  '* i}                        mn, make_{vars[i - 1]})): continue\n"
    exprs += f"{'  '* i}if chk == 'break': break\n"
    exprs += f"{'  '* i}make_{vars[i - 1]}, make_{vars[i]} = 0, 1   # don't try to make 1..x anymore in this loop\n"
  
  if i == N - 2 and coins[-2] == 100: 
    exprs += f"{'  '* i}# we can already calculate last quantity\n"
    exprs += f"{'  '* i}{(last := vars[N - 1])}, rest = divmod(prod_{vars[i - 1]} - 100 * sum(lst_{vars[i - 1]}), 100 - coins[-1])\n"
    exprs += f"{'  '* i}if rest or {last} < 0: continue\n"
    
  if i == N: 
    exprs += f"{'  '* (i - 1)}if tot + {last} > mn: break\n"
    exprs += f"{'  '* (i - 1)}mn = tot + {last}\n"
    exprs += f"{'  '* (i - 1)}sols[mn] = sols.get(mn, []) + [lst_{vars[i - 2]} + [{last}]]\n"

exprs += "if mn not in sols:\n"   
exprs += "  print('ERROR: no solutions, mn =', mn)\n"   
exprs += "else:\n"   
exprs += "  print(f'solutions: {len(sols[mn])}            {cnt} calls to make_all')\n"    
exprs += "  for s in sols[mn]: print('-------- number of coins:', mn, s)\n"   

#print(exprs)  
exec(exprs)

The following code is generated:

mn, cnt = 1e8, 0

def check(lev, qs, tv, mn, make=1):
  global cnt
  if mn < 1e8:
    # calculate minimum last quantity
    h_ = ceil((100 * mn - tv) / coins[-1])
    if sum(qs) + h_ > mn:
      return 'break'
  if make:
    n = coins[lev] - 1
    if tv < n: return False
    strt = 1 + coins[lev - 1] if lev > 1 else 1
    cnt += 1
    # can we make numbers <strt>...<n> with these denominations?
    if not make_all(n, coins[:lev], qs, strt):
      return False
  return True

make_a = 1
# can we make numbers 1..<total pence> with denominations (1, 2, 5, 10, 20, 50, 100, 200)?
for a in range(1, 20):
  # can we make numbers 1..1 with denominations (1,)
  if not (chk := check(1, lst_a := [a],
                          prod_a := a * 1,
                          mn, make_a)): continue
  if chk == 'break': break
  make_a, make_b = 0, 1   # don't try to make 1..x anymore in this loop
  for b in range(0, 20):
    # can we make numbers 1..4 with denominations (1, 2)
    if not (chk := check(2, lst_b := [a, b],
                            prod_b := prod_a + b * 2,
                            mn, make_b)): continue
    if chk == 'break': break
    make_b, make_c = 0, 1   # don't try to make 1..x anymore in this loop
    for c in range(prod_b % 2, max(prod_b % 2 + 15, M) if i != N - 1 else 40, 2):
      # can we make numbers 1..9 with denominations (1, 2, 5)
      if not (chk := check(3, lst_c := [a, b, c],
                              prod_c := prod_b + c * 5,
                              mn, make_c)): continue
      if chk == 'break': break
      make_c, make_d = 0, 1   # don't try to make 1..x anymore in this loop
      for d in range(0, 20):
        # can we make numbers 1..19 with denominations (1, 2, 5, 10)
        if not (chk := check(4, lst_d := [a, b, c, d],
                                prod_d := prod_c + d * 10,
                                mn, make_d)): continue
        if chk == 'break': break
        make_d, make_e = 0, 1   # don't try to make 1..x anymore in this loop
        for e in range(0, 20):
          # can we make numbers 1..49 with denominations (1, 2, 5, 10, 20)
          if not (chk := check(5, lst_e := [a, b, c, d, e],
                                  prod_e := prod_d + e * 20,
                                  mn, make_e)): continue
          if chk == 'break': break
          make_e, make_f = 0, 1   # don't try to make 1..x anymore in this loop
          for f in range(0, 20):
            # can we make numbers 1..99 with denominations (1, 2, 5, 10, 20, 50)
            if not (chk := check(6, lst_f := [a, b, c, d, e, f],
                                    prod_f := prod_e + f * 50,
                                    mn, make_f)): continue
            if chk == 'break': break
            make_f, make_g = 0, 1   # don't try to make 1..x anymore in this loop
            # we can already calculate last quantity
            h, rest = divmod(prod_f - 100 * sum(lst_f), 100 - coins[-1])
            if rest or h < 0: continue
            for g in range(0, 40):
              tot = sum(lst_f) + g
              # can we make numbers 1..199 with denominations (1, 2, 5, 10, 20, 50, 100)
              if not (chk := check(7, lst_g := [a, b, c, d, e, f, g],
                                      prod_g := prod_f + g * 100,
                                      mn, make_g)): continue
              if chk == 'break': break
              make_g, make_h = 0, 1   # don't try to make 1..x anymore in this loop
              if tot + h > mn: break
              mn = tot + h
              sols[mn] = sols.get(mn, []) + [lst_g + [h]]
if mn not in sols:
  print('ERROR: no solutions, mn =', mn)
else:
  print(f'solutions: {len(sols[mn])}            {cnt} calls to make_all')
  for s in sols[mn]: print('-------- number of coins:', mn, s)

LikeLike

Ruud 3:12 pm on 1 July 2024 Permalink | Reply

You could generate exprs with:

exprs = f"""\
mn, cnt = 1e8, 0

def check(lev, qs, tv, mn, make=1):
  global cnt
  if mn < 1e8:
    # calculate minimum last quantity
    h_ = ceil((100 * mn - tv) / coins[-1])
    if sum(qs) + h_ > mn:
      return 'break'
  if make:
    n = coins[lev] - 1
    if tv < n: return False
    strt = 1 + coins[lev - 1] if lev > 1 else 1
    cnt += 1
    # can we make numbers <strt>...<n> with these denominations?
    if not make_all(n, coins[:lev], qs, strt):
      return False
  return True

make_{vars[0]} = 1
# can we make numbers 1..<total pence> with denominations {coins}?
"""

No change in functionality, just easier to understand and maintain.

LikeLike

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

Thanks, I had seen it before but had forgotten it.

I also tried to use make() and make_all() in this way but had to use
yield ns | {{n}}
for my original line 15. I hoped in making these 2 functions local as well I wouldn’t need the performance enhancement but it is still lowers the run time.

LikeLike

Frits 5:44 pm on 1 July 2024 Permalink | Reply

Does anybody have an explanation why line 38 (in the first program) lowers the run time? Is it a memory thing and does it also occur on a linux system?

LikeLike

Frits 9:26 pm on 18 July 2024 Permalink | Reply

from sys import argv
from math import ceil
from time import perf_counter

# coin denominations
coins = [1, 2, 5, 10, 20, 50, 100, 200] if len(argv) == 1 else \
         list(int(x.replace(",", "", 1)) for x in argv[1:])
coins.sort()
N = len(coins)
assert 1 in coins and coins[-1] > 100 and len(set(coins)) == N
last_odd = [i for i, x in enumerate(coins) if x % 2][-1]
mx_factor = max(divs := [ceil(coins[i + 1] / coins[i]) for i in range(N - 1)])
print(f"{coins = }")

# solve problem by adding coins of <N> different denominations  
def solve(ds, k=0, tv=0, nc=0, qs=[]):
  global mn
  if k == N - 1:
    # we can calculate the quantity of the highest denomination
    last, r = divmod(tv - 100 * nc, 100 - ds[-1])
    if r or last < 0 or (nc_ := nc + last) > mn: return
    mn = nc_
    yield qs + [last]
  else:
    min_i = max(0, ceil((ds[k + 1] - tv - 1) / ds[k]))
    if k == last_odd:
      min_i += (tv + min_i) % 2
    
    remaining = 100 * mn - tv
    # minimum elements to follow = ceil((remaining - (i * ds[k])) / ds[-1])
    # nc + i + minimum elements to follow <= mn 
    max_i = min((ds[-1] * (mn - nc) - remaining) // (ds[-1] - ds[k]),
            mn - nc,
            # do not make a total which is higher than the minimum
            remaining // ds[k])
    
    if max_i < min_i: 
      return
      
    if k < N - 2:
      # with <j - 1> quantities can we still make numbers up to ds[j] - 1
      # if we choose <i> of ds[k]    (for j >= k + 2)
      # tv + i * ds[k] + (mn - nc - i) * ds[j - 1] >= ds[j] - 1
      mx1 = min(((mn - nc) * ds[j - 1] + tv - c + 1) // (ds[j - 1] - ds[k])
              for j, c in enumerate(ds[k + 2:], k + 2))
      max_i = min(max_i, mx1)
    
    for i in range(min_i, max_i + 1, 1 if k != last_odd else 2):
      yield from solve(ds, k + 1, tv + i * ds[k], nc + i, qs + [i])
    
sols = dict()
mn = mx_factor + 27 # solving approx 80% of all cases in one pass 
inc = 15
cnt = 0
while not sols:
  print(f"try {mn = }")
  M = mn
  for s in solve(coins):
    cnt += 1
    # limit the number of printed solutions (causing slowness due to memory)
    if cnt > 999 and mn in sols: continue    
    if mn not in sols: 
      sols = dict()
      cnt = 1
    sols[mn] = sols.get(mn, []) + [s]
     
  if not sols:
    mn += inc  

for s in sols[mn]: print('-------- number of coins:', mn, s)  
print(f'[{cnt:>5} solutions]')

solving 1000 random testcases in approximately 200 seconds.

from random import sample
from os import system
from sys import argv, stdout, stderr

N = 8

c = 0
for _, _ in enumerate(iter(bool, 1), 1): # infinite loop     
  c += 1
  if c == 1001: break
  lst = [1] + sorted(sample(range(2, 2001), N - 1))
  if lst[-1] < 101: continue
  
  lst = ' '.join(str(x) for x in lst)
  print(f"{c = } {lst = }", file=stderr)
  system("python TheRightMoney.py " + lst)

LikeLike

Jim Randell 7:33 pm on 9 May 2024 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2610: Odd ages
From The Sunday Times, 30th September 2012 [link] [link]

Recently Alex, Bernard and Charles were comparing their ages in years. Alex’s age was an odd two-digit number and Bernard’s age was a whole number percentage more than that. On the other hand, Charles’s age was also an odd two-digit number but Bernard’s age was a whole number percentage less than that. They were surprised to find that the percentage was the same in both cases.

What were their three ages?

[teaser2610]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR, Frits, and Jim Randell are discussing. Toggle Comments
- Jim Randell 7:34 pm on 9 May 2024 Permalink | Reply
  Supposing the 3 are all different ages (so the percentage is non-zero).
  
  A’s age is an odd 2-digit number, and C’s age is a (larger) odd 2-digit number, and so B’s age is between them, hence also a 2-digit number.
  
  For percentage p we have:
  
  A (100 + p) / 100 = B
  C (100 − p) / 100 = B
  ⇒
  p = 100 (C − A) / (C + A)
  
  The following Python program runs in 67ms. (Internal runtime is 463µs).
  
  Run: [ @replit ]
```
from enigma import (irange, subsets, div, printf)

# ages for A and C (2-digit, odd)
for (A, C) in subsets(irange(11, 99, step=2), 2):
  # calculate percentage
  p = div(100 * (C - A), C + A)
  if p is None: continue
  # calculate B
  B = div(A * (100 + p), 100)
  if B is None: continue
  # output solution
  printf("A={A} B={B} C={C} [p={p}%]")
```
  Solution: Alex is 15. Bernard is 21. Charles is 35.
  
  And the percentage in question is 40%:
  
  15 + 40% = 15 × (1 + 0.4) = 21
  35 − 40% = 35 × (1 − 0.4) = 21
  
  LikeLike
- Frits 10:06 am on 10 May 2024 Permalink | Reply
```
for a in range(11, 100, 2):
  # determine valid percentages, maximum percentage = (99 - 12) / 99 = 0.87878
  for p in [p for p in range(2, 88, 2) if (p * a) % 100 == 0]:
    b = a + (p * a) // 100
    c, r = divmod(100 * b, 100 - p)
    if c > 99: break
    if r or c % 2 == 0: continue
    print("answer:", (a, b, c))     
```
  LikeLike
- GeoffR 10:35 am on 10 May 2024 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

var 11..99:A; var 11..99:B; var 11..99:C;
var 1..95:p; % Percentage

constraint all_different([A, B, C]);
constraint sum([A mod 2 == 1, B mod 2 == 1, C mod 2 == 1]) == 3;
constraint 100*A + p*A == 100*B;
constraint 100*C - p*C == 100*B;

solve satisfy;

output["[Alex, Bernard, Charles] = " ++ show([A, B, C]) ];
 
% [Alex, Bernard, Charles] = [15, 21, 35]
% ----------
% ==========
```
  LikeLike
Jim Randell 5:16 pm on 19 February 2024 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2671: On the face of it
From The Sunday Times, 1st December 2013 [link] [link]

At the beginning of last year my wife and I were each given a clock. When we first looked at them the hands on both clocks showed the correct time but thereafter (although the two clocks coincided at least once more during the year) they generally showed different times.

The problem was that my clock gained a certain whole number of minutes each day, and the same was true of my wife’s clock, but hers was even faster than mine. Actually my clock showed the correct time at least once in every month last year but that was not the case for my wife’s clock.

How many minutes did each clock gain in a day?

[teaser2671]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Frits and Jim Randell are discussing. Toggle Comments
- Jim Randell 5:17 pm on 19 February 2024 Permalink | Reply
  In this puzzle I am assuming that the clocks are standard 12-hour analogue clocks, that are not adjusted during the year (even for daylight savings time), and the correct time is also not adjusted for DST, and that the puzzle takes place in the year 2012 (it was originally published in 2013).
  
  Clock 1 showed the correct time at least once each month in 2012, but Clock 2 did not.
  
  Some time in January both clocks are correct, and some other time during the year (2012 had 366 days), both clocks are showing the same time. And the first time this happens Clock 2 is exactly 12 hours ahead of Clock 1. So during the course of up to 366 days, it has gained 720 minutes over Clock 1, this means the Clock 2 is gaining at least 2 minutes per day more than Clock 1.
  
  If it gains only 2 minutes more then it will take 360 days to get 720 minutes ahead of Clock 1, and so this will only work if the clocks are first looked at during the first 6 days of January. If it gains 3 or more minutes, any time in January will suffice.
  
  But if Clock 2 gains 720 minutes (or more) in any 29 day period, then it cannot avoid showing the right time in every month. So Clock 2 must gain less than 25 minutes per day.
  
  For each possible set of gains per day, this Python program looks for the earliest time in January when the clocks could give a correct time.
  
  It runs in 56ms. (Internal runtime is 302µs).
  
  Run: [ @replit ]
```
from datetime import (datetime, timedelta)
from enigma import (irange, irangef, fdiv, repeat, inc, divf, arg, printf)

# year
Y = arg(2012, 0, int)

# calculate max gain for clock 2 (depends on number of days in Feb)
M = divf(720, (datetime(Y, 3, 1) - timedelta(days=1)).day)

# return day offsets when a clock gaining <x> minutes per day
# has gained multiples of 720 minutes
offsets = lambda x: list(irangef(0, 366, step=fdiv(720, x)))

# look for earliest time when clocks are correct
# with clock 1 gaining x min/day
for x in irange(1, M - 2):
  # day offsets for clock 1
  ds1 = offsets(x)
  # clock 1 is correct at least once in each month
  if len(ds1) < 12: continue

  # clock 2 gains at least 2 min/day more than clock 1
  for y in irange(x + 2, M):

    # choose a time in Jan when the clocks are correct
    for t in repeat(inc(timedelta(minutes=1)), datetime(Y, 1, 1, 0, 0, 0)):
      if t.month > 1: break

      # find dates when clock 1 shows the correct time
      ts1 = list(t + timedelta(days=x) for x in ds1)
      # look for these occurring in 12 different months
      if not (len({t.month for t in ts1}) == 12): continue

      # find the dates when clock 2 is correct
      ts2 = list(t + timedelta(days=x) for x in offsets(y))
      # look for these occurring in fewer than 12 different months
      if not (len({t.month for t in ts2}) < 12): continue
      # check when the clocks are showing the same time
      s = t + timedelta(days=fdiv(720, y - x))
      if s.year > Y: continue

      # earliest solution found
      printf("clock 1 gains {x} mins/day")
      for z in ts1: printf("-> clock 1 correct @ {z}")
      printf("clock 2 gains {y} mins/day")
      for z in ts2: printf("-> clock 2 correct @ {z}")
      printf("clocks read same time @ {s}")
      printf()
      break
```
  Solution: The clocks gain 22 minutes and 24 minutes per day.
  
  If the clocks both show the correct time at midnight on 1st January 2012 then clock 1 shows the correct time at:
  
  2012-01-01 @ 00:00
  2012-02-02 @ 17:27
  2012-03-06 @ 10:54
  2012-04-08 @ 04:21
  2012-05-10 @ 21:49
  2012-06-12 @ 15:16
  2012-07-15 @ 08:43
  2012-08-17 @ 02:10
  2012-09-18 @ 19:38
  2012-10-12 @ 13:05
  2012-11-23 @ 06:32
  2012-12-26 @ 00:00
  
  We see that each of the 12 correct times occurs in a different month.
  
  And clock 2 shows the correct time at:
  
  2012-01-01 @ 00:00
  2012-01-31 @ 00:00
  2012-03-01 @ 00:00
  2012-03-31 @ 00:00
  2012-04-30 @ 00:00
  2012-05-30 @ 00:00
  2012-06-29 @ 00:00
  2012-07-29 @ 00:00
  2012-08-28 @ 00:00
  2012-09-27 @ 00:00
  2012-10-27 @ 00:00
  2012-11-26 @ 00:00
  2012-12-26 @ 00:00
  
  Although this clock shows 13 correct times in the same interval that the other clock shows 12 correct times, it has 2 correct times in January, 2 correct times in March, and no correct times in February.
  
  After 360 days, on 2012-12-26 @ 00:00, clock 1 has gained 7920 min = 5.5 days, and clock 2 has gained 8640 min = 6 days, so both clocks are showing the same (correct) time of 12:00.
  
  However, if we were to run the same puzzle in 2013 (not a leap year), we still get a solution with 22 min/day and 24 min/day (although dates after Feb are a day earlier, so clock 2 has 2 correct times in May not March), but we also find there is a second solution, where clock 1 gains 23 min/day and clock 2 gains 25 min/day.
  
  For example if the clocks both clocks show the correct time at 9:36am on 2nd January 2013, then clock 1 shows the correct time at:
  
  2013-01-02 @ 09:36
  2013-02-02 @ 16:54
  2013-03-06 @ 00:12
  2013-04-06 @ 07:30
  2013-05-07 @ 14:49
  2013-06-07 @ 22:07
  2013-07-09 @ 05:25
  2013-08-09 @ 12:43
  2013-09-09 @ 20:02
  2013-10-11 @ 03:20
  2013-11-11 @ 10:38
  2013-12-12 @ 17:56
  
  And clock 2 shows the correct time at:
  
  2013-01-02 @ 09:36
  2013-01-31 @ 04:48
  2013-03-01 @ 00:00
  2013-03-29 @ 19:12
  2013-04-27 @ 14:24
  2013-05-26 @ 09:36
  2013-06-24 @ 04:48
  2013-07-23 @ 00:00
  2013-08-20 @ 19:12
  2013-09-18 @ 14:24
  2013-10-17 @ 09:36
  2013-11-15 @ 04:48
  2013-12-14 @ 00:00
  
  After 360 days, on 2012-12-28 @ 09:36, clock 1 has gained 8280 min = 5.75 days, and clock 2 has gained 9000 min = 6.25 days, so both clocks are showing the same (incorrect) time of 3:36.
  
  And a third solution with the clocks gaining 22 min/day and 25 min/day, where the clocks start on 2013-01-02 @ 09:36 and show the same time after 240 days at 2013-08-30 @ 09:36.
  
  LikeLike
- Frits 9:51 am on 23 February 2024 Permalink | Reply
```
   
from datetime import date, timedelta
from math import ceil

DAYS = 366

# dictionary month number per day (day 31 becomes month 2 (2012-02-01 00:00))
d = {i: (date(2012, 1, 1) + timedelta(days=i)).month 
        for i in range(1, DAYS + 1)}

# "I" need to have a correct time in at least another 11 months 
mn = ceil(11 * 720 / DAYS)
# maximum gain for not to have a guaranteed correct time at least once a month
mx = ceil(720 / 29) - 1

for my in range(mn, mx - 1):
  mths = set(d[ceil((m * 720) / my)]
             for m in range(1, (my * DAYS) // 720 + 1)) 
  # at least twelve different months?
  if len({1} | mths) == 12:
    mytimes = set(ceil((m * 720) / my) 
                  for m in range(1, (my * DAYS) // 720 + 1))
  
    # my wife's clock is gaining at least 2 minutes per day more than my clock
    for wife in range(my + 2, mx + 1):
      mths = set(d[ceil((m * 720) / wife)]
                 for m in range(1, wife * DAYS // 720 + 1)) 
      if len({1} | mths) < 12:
        wifetimes = {ceil((m * 720) / wife) 
                     for m in range(1, wife * DAYS // 720 + 1)}
        # the two clocks coincided at least once more during the year     
        if mytimes & wifetimes:
          print(f"answer: {my} and {wife}")  
```
  LikeLike
Jim Randell 7:55 am on 14 November 2023 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2652: Square meals
From The Sunday Times, 21st July 2013 [link] [link]

A company produces five different types of muesli. The ingredients are bought from a wholesaler who numbers his items from 1 to 10. In each type of muesli there is a mixture of a square number of different ingredients and the weight in grams of each ingredient is the square of its item number: also the total weight of its ingredients is a perfect square number of grams.

Last month one of the ingredients was unavailable and so only the “basic” and “fruity” varieties could be produced. This week a different ingredient is unavailable and so only the “luxury” variety can be made.

What are the item numbers of the ingredients in the luxury muesli?

[teaser2652]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 7:55 am on 14 November 2023 Permalink | Reply
  I assumed each mixture has multiple ingredients, and as there are only 10 possible ingredients this means each must have 4 or 9.
  
  This Python program looks for sets of 4 or 9 numbers from 1 to 10 whose squares sum to a square number. We then choose 5 of these sets to form the different types of muesli made, and look for the 2 (different) unavailable ingredients. The first unavailable ingredient only allows 2 of the types to be made (these are “basic” and “fruity”) and the second only allows 1 to be made (and this is “luxury”).
  
  It runs in 84ms. (Internal runtime is 879µs).
  
  Run: [ @replit ]
```
from enigma import (irange, subsets, sq, is_square, union, intersect, printf)

# collect possible collections of ingredients
ms = list()

# choose 4 or 9 ingredients
for k in [4, 9]:
  for ns in subsets(irange(1, 10), size=k):
    # calculate the total weight
    t = sum(sq(n) for n in ns)
    if not is_square(t): continue
    printf("[k={k}: ns={ns} t={t}]")
    ms.append(ns)

# choose 5 varieties
for vs in subsets(ms, size=5):
  ns = union(vs)
  # choose the first unavailable ingredient
  for u1 in ns:
    # find how many can be made without u1
    vs1 = list(v for v in vs if u1 not in v)
    # there are 2 that cannot be made ("basic" and "fruity")
    if len(vs1) != 2: continue

    # choose the second unavailable ingredient
    for u2 in ns:
      if u2 == u1: continue
      # find how many can be made without u2
      vs2 = list(v for v in vs if u2 not in v)
      # there is only 1 that cannot be made ("luxury")
      if len(vs2) != 1: continue
      if intersect([vs1, vs2]): continue

      # output solution
      printf("u1={u1} -> basic/fruity={vs1}; u2={u2} -> luxury={vs2[0]}")
```
  Solution: Luxury muesli uses ingredients: 2, 4, 5, 6.
  
  There are only 5 possible sets of ingredients, so these correspond to each of the 5 types of museli:
  
  (2, 4, 5, 6) → 81
  (1, 2, 4, 10) → 121
  (1, 2, 8, 10) → 169
  (2, 4, 7, 10) → 169
  (5, 6, 8, 10) → 225
  
  The unavailable ingredient last month was 4, meaning only: (1, 2, 8, 10) and (5, 6, 8, 10) could be made. These are (in some order) “basic” and “fruity”.
  
  The unavailable ingredient this week is 10, meaning only (2, 4, 5, 6) can be made, and this is “luxury”.
  
  LikeLike
Jim Randell 9:48 am on 28 September 2023 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2641: Exchange rate
From The Sunday Times, 5th May 2013 [link] [link]

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

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

How many Tezar dollars did I receive?

[teaser2641]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:49 am on 28 September 2023 Permalink | Reply
  Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.
  
  The following run files executes in 68ms. (Internal runtime of the generated program is 703µs).
  
  Run: [ @replit ]
```
#! python3 -m enigma -rr

# (ABC - 12) * rate = CBA

SubstitutedExpression

--distinct=""

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

# answer is the number of dollars received
--answer="CBA"
```
  Solution: You received 612 Tezar dollars.
  
  LikeLike

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

Teaser 2631: Family progression

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

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

minute, hour, DD, MM, YY

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

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

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

[teaser2631]

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

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

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

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

Run: [ @replit ]

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

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

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

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

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

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

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

And the birth date/times are:

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

LikeLike

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

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

from enigma import SubstitutedExpression

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

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

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

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

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

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

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

LikeLike

Jim Randell 10:34 am on 23 March 2023 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2710: Sterling achievement
From The Sunday Times, 31st August 2014 [link] [link]

Some people were asked to donate one pound each to charity. They all used only “silver” coins (5p, 10p, 20p, 50p) to make up their pound and no two of them used the same combination. I also donated a pound using silver coins, but it was inevitable that my combination of coins would be a repeat of one already used. When all the coins were sorted into the different denominations we found that we had a whole number of pounds in each denomination.

Which coins did I use to make my pound?

[teaser2710]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 10:34 am on 23 March 2023 Permalink | Reply
  There are a couple of routines in enigma.py to calculate ways of expressing amounts using specified denominations (e.g. coins or stamps). In this case using the more sophisticated [[ Denominations() ]] algorithm gives a (slightly) faster solution than the simple [[ express() ]] function.
  
  This Python program runs in 51ms. (Internal runtime is 261µs).
  
  Run: [ @replit ]
```
from enigma import (Denominations, ceil, ediv, printf)

# express 100 using denominations of 5, 10, 20, 50
ds = (5, 10, 20, 50)
qss = Denominations(ds).express(100)  # or: express(100, ds)

# sum the quantities
tqs = list(sum(qs) for qs in zip(*qss))

# determine extra coins required to make the total of each
# denomination a whole number of pounds
for (d, q) in zip(ds, tqs):
  t = d * q
  x = ceil(t, 100) - t
  n = ediv(x, d)
  printf("{n} x {d}p = {x}p [{q} x {d}p coins = {t}p]")
```
  Solution: 6× 5p; 3× 10p; 2× 20p.
  
  There are 49 different ways to make 100p using 5p, 10p, 20p, 50p.
  
  And if we sum them all we get:
  
  294× 5p = 1470p
  147× 10p = 1470p
  63× 20p = 1260p
  14× 50p = 700p
  
  The setters donation makes the total of the 5p and 10p coins up £15, and the 20p coins up to £13, and the 50p coins were already at £7. Making a grand total of £50.
  
  LikeLike

Jim Randell 9:29 am on 21 March 2023 Permalink | Reply
Tags: by: Robin Nayler

Teaser 2701: Flipping ages!

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

At a recent family party the ages of the ten people present formed an arithmetic progression (i.e. the difference between each person’s age in years and the age of the next oldest person was always the same). My age was like my wife’s but with the digits in reverse order. Likewise, my sister’s age was the reverse of my mother’s, my son’s age was the reverse of my grandson’s, and my daughter’s age was the reverse of my granddaughter’s. Furthermore, the product of my brother’s age and the age of his son equalled the year of birth of one of the people at the party.

What were the ages of my brother, my sister and myself (in that order)?

[teaser2701]

Jim Randell 9:30 am on 21 March 2023 Permalink | Reply

This Python program chooses the 4 pairs of ages that are the mutually reversed, and then extends this set of 8 numbers to 10 numbers in arithmetic progression (if possible). It then allocates the given relationships between the numbers (it looks for viable parent/child ages where the parent is between 16 and 50 years older than the child).

Runtime is 282ms.

Run: [ @replit ]

from enigma import (irange, subsets, union, tuples, mgcd, call, divisor, div, decompose, diff, printf)

# collect pairs that are the reverse of each other
pairs = set((10 * a + b, 10 * b + a) for (a, b) in subsets(irange(1, 9), size=2))

# generate arithmetic progressions based on the given numbers
def generate(ns):
  ns = sorted(ns)
  (a, z) = (ns[0], ns[-1])
  # find potential common differences
  for d in divisor(call(mgcd, (y - x for (x, y) in tuples(ns, 2)))):
    # calculate number of terms
    k = div(z - a, d)
    if k is None or k > 9: continue
    k += 1
    # pad the sequence to bring it to 10 terms
    for (pa, pz) in decompose(10 - k, 2, increasing=0, sep=0, min_v=0):
      # construct the new sequence
      ns = list(irange(a - pa * d, z + pz * d, step=d))
      yield ns

# check for viable parent, child age
check = lambda parent, child: 15 < parent - child < 51

# choose 4 pairs
for ps in subsets(pairs, size=4):
  ss = union(ps)
  for ns in generate(ss):
    # the additional ages are brother and nephew
    (nep, bro) = diff(ns, ss)
    if not check(bro, nep): continue
    # and their product is the birth year of one of the party
    year = bro * nep
    x = 2014 - year
    if not { x, x - 1 }.intersection(ns): continue

    # choose the pairs
    for ((sis, mum), (gson, son), (gdtr, dtr), other) in subsets(ps, size=4, select="P"):
      # check parent/child relationships
      if not (check(mum, sis) and check(mum, bro)): continue
      if not (check(son, gson) or check(dtr, gson)): continue
      if not (check(son, gdtr) or check(dtr, gdtr)): continue
      # the remaining pair is (me, wife) (in some order)
      for (me, wife) in subsets(other, size=2, select="P"):
        # check parent/child relationships
        if not (check(mum, me) and check(me, son) and check(me, dtr)): continue
        if not (check(wife, son) and check(wife, dtr)): continue
        # output solution
        printf("{ns}")
        printf("-> me={me} wife={wife}")
        printf("-> sis={sis} mum={mum}")
        printf("-> son={son} gson={gson}")
        printf("-> dtr={dtr} gdtr={gdtr}")
        printf("-> bro={bro} nep={nep}; year={year}")
        printf()

Solution: Brother = 60. Sister = 69. Self = 78.

The arithmetic progression is (15, 24, 33, 42, 51, 60, 69, 78, 87, 96).

And the pairs are:

me = 78; wife = 87
sister = 69; mother = 96
child = 51; grandchild = 15
child = 42; grandchild = 24
brother = 60; nephew = 33

And the product of the ages of the brother and nephew give 1980. And if the 33 year-old nephew has not yet celebrated his birthday in 2014, his year of birth is 1980.

But we can’t tell how the child/grandchild pairs correspond to the son/grandson and daughter/granddaughter pairs.

LikeLike

Jim Randell 9:14 am on 7 February 2023 Permalink | Reply
Tags: by: Robin Nayler, flawed ( 53 )
Teaser 2692: Runners-up
From The Sunday Times, 27th April 2014 [link] [link]

In our local football league each team plays each other team twice each season, once at home and once away. The teams get three points for a win and one point for a draw. All games are on Saturdays at 3pm, and yesterday all the teams played their last game, so the final league table has now been published. Our team were runners-up, but we should have won! We were just one point behind the winners and, although they won two-thirds of their games, our team won more. Furthermore, looking at our drawn games, I notice that the league winners lost twice as many games as we drew.

How many games did the league winners win, draw and lose?

[teaser2692]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 9:15 am on 7 February 2023 Permalink | Reply
  This puzzle should have been worded more carefully to eliminate multiple solutions.
  
  If there are n teams in the league, then each team plays each of the other (n − 1) teams both at home and away, so each team plays (2n − 2) matches.
  
  The fact that all teams can play at one time tells us that n must be even (so the teams can all be paired up).
  
  We are not told how long the season is, but if we suppose that it lasts less than 1 year, then as the teams play 1 match per week, we can suppose than n ≤ 26 (otherwise it would not be possible to fit all the matches in).
  
  I am assuming that “the league winners lost twice as many games as we drew” implies that the numbers involved are non-zero (otherwise it would be a bit of an odd way to phrase it), but this does not give a unique solution.
  
  The following Python program runs in 52ms. (Internal runtime is 190µs).
  
  Run: [ @replit ]
```
from enigma import (irange, inf, div, printf)

# consider number of teams in the league (must be even)
for n in irange(2, inf, step=2):
  # total number of matches played by each team
  played = 2 * (n - 1)
  if played > 52: break
  # the winners won 2/3 of their matches
  w1 = div(2 * played, 3)
  if w1 is None: continue

  # consider the number of draws for the runners up (at least 1)
  for d2 in irange(1, played):
    # the winners lost twice this amount
    l1 = 2 * d2
    # calculate the draws and points for the winners
    d1 = played - w1 - l1
    if d1 < 0: break
    pts1 = 3 * w1 + d1
    # calculate the points, wins for the runners up
    pts2 = pts1 - 1
    w2 = div(pts2 - d2, 3)
    if w2 is None or not (w2 > w1): continue
    l2 = played - w2 - d2
    if l2 < 0: continue
    # some sanity checks
    if not (w1 + l2 < played - 2 and w2 + l1 < played - 2): continue
    # output solution
    printf("n={n} d2={d2}: played={played}; (w, d, l, pts) #1 ({w1}, {d1}, {l1}, {pts1}); #2 ({w2}, {d2}, {l2}, {pts2})")
```
  There are two candidate solutions:
  
  16 teams in the league; each team plays 30 matches.
  
  winners: w=20, d=8, l=2, pts=68; runners up: w=22, d=1, l=7, pts=67
  winners: w=20, d=6, l=4, pts=66; runners up: w=21, d=2, l=7, pts=65
  
  The published answer (“20, 6 and 4”) corresponds to the second of these scenarios.
  
  It has been suggested that “looking at our drawn games” necessarily implies that the runners-up must have more than one drawn match (eliminating the first of the above solutions), but I think if this was the intention a clearer choice of words would be necessary.
  
  LikeLike
Jim Randell 8:45 am on 27 September 2022 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2749: Round the river
From The Sunday Times, 31st May 2015 [link] [link]

My school holds “Round the river” runs — a whole number of metres to a bridge on the river and then the same number of metres back. Some years ago I took part with my friends Roy, Al, David and Cy. We each did the outward half at our own steady speeds (each being a whole number of centimetres per minute). For the return half I continued at my steady speed, Roy increased his speed by 10%, Al increased his speed by 20%, David increased his by 30%, and Cy increased his by 40%. We all finished together in a whole number of minutes, a little less than half an hour.

What (in metres) is the total length of the race?

[teaser2749]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 8:46 am on 27 September 2022 Permalink | Reply
  The speeds are whole numbers of centimetres per minute, so we will work in units of centimetres and minutes.
  
  If the distance to bridge is x centimetres, then x must be divisible by 100.
  
  And the time is t minutes (less than 30).
  
  If the 5 speeds are: a, b, c, d, e, then we have:
  
  t = x/a + x/a = 2x / a
  t = x/b + x/1.1b = 21x / 11b
  t = x/c + x/1.2c = 11x / 6c
  t = x/d + x/1.3d = 23x / 13d
  t = x/e + x/1.4e = 12x / 7e
  
  From which we see that x must also be divisible by 11, 6, 13, 7.
  
  Placing some sensible limits on distance and speeds, we can suppose x is less than 10km (= 10,000m = 1,000,000cm), and that speeds are less than 15mph (≈ 40,000cm/min).
  
  This Python program runs in 61ms. (Internal runtime is 129µs).
  
  Run: [ @replit ]
```
from enigma import (irange, mlcm, div, printf)

# x must be a multiple of m
m = mlcm(100, 11, 6, 13, 7)

# consider possible total times: "a little less than half an hour"
for t in irange(29, 21, step=-1):

  # consider possible values of x (up to 10km)
  for x in irange(m, 1000000, step=m):

    # calculate the speeds
    vs = [
      div(20 * x, 10 * t),
      div(21 * x, 11 * t),
      div(22 * x, 12 * t),
      div(23 * x, 13 * t),
      div(24 * x, 14 * t),
    ]
    # check speeds
    if None in vs or vs[-1] * 1.4 > 40000: continue

    # output solution
    printf("d={d} metres [t={t} x={x} {vs}]", d=div(2 * x, 100))
```
  Solution: The total length of the race is 6006m.
  
  And the race took exactly 25 minutes.
  
  The outward speeds are:
  
  1: 24024 cm/min (≈ 8.96 mph); 12.5 min out + 12.5 min back (@ 8.96 mph)
  2: 22932 cm/min (≈ 8.55 mph); 13.1 min out + 11.9 min back (@ 9.40 mph)
  3: 22022 cm/min (≈ 8.21 mph); 13.6 min out + 11.4 min back (@ 9.85 mph)
  4: 21252 cm/min (≈ 7.92 mph); 14.1 min out + 10.9 min back (@ 10.30 mph)
  5: 20592 cm/min (≈ 7.68 mph); 14.6 min out + 10.4 min back (@ 10.75 mph)
  
  Note that the speeds on the return leg are not all whole numbers of cm/min.
  
  LikeLike
Jim Randell 3:24 pm on 22 June 2021 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2798: Housey-housey
From The Sunday Times, 8th May 2016 [link] [link]

Philip, Daphne and I live in different houses on Teaser Drive. Philip lives at number 1 and the houses are then numbered consecutively along one side of the road. The sum of the house numbers strictly between Philip’s house and mine is equal to the sum of the house numbers strictly between my house and Daphne’s. Furthermore, the digits of Daphne’s house number add up to the same total as the digits of my house number.

What is my house number and what is Daphne’s?

[teaser2798]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
GeoffR, John Crabtree, and Jim Randell are discussing. Toggle Comments
- Jim Randell 3:24 pm on 22 June 2021 Permalink | Reply
  We can calculate the sum of the house numbers between two houses (non-inclusive):
  
  S(a, b) = (a + 1) + … + (b − 1)
  S(a, b) = T(b − 1) − T(a)
  
  This program finds the first viable solution. It runs in 51ms.
  
  Run: [ @replit ]
```
from enigma import T, irange, inf, dsum, printf

# calculate the "inter-sum" of a and b
S = lambda a, b: T(b - 1) - T(a)

# generate solutions
def solve(P):
  # consider values for setters house number (R)
  for R in irange(P + 1, inf):
    s = S(P, R)
    # look for D with an equal value, and equal digit sum
    for D in irange(R + 1, inf):
      s_ = S(R, D)
      if s_ > s: break
      if s_ == s and dsum(D) == dsum(R):
        yield (R, D)

# look for the first solution
for (R, D) in solve(1):
  printf("R={R}, D={D}")
  break
```
  Solution: Your house number is 64. Daphne’s house number is 91.
  
  LikeLike
  - Jim Randell 3:27 pm on 22 June 2021 Permalink | Reply
    The program above finds the smallest solution (which is the required answer), but there are larger solutions. The next one is:
    
    R=85225144, D=120526555
    
    The numbers involved are too large to be house numbers, but we can write a more efficient program to investigate larger solutions.
    
    Ignoring the digit sum condition, we can look for (R, D) values that give equal inter-sums:
    
    S(1, R) = S(R, D)
    2R² = D² − D + 2
    R² − 1 = D(D − 1)/2
    
    So we can look for triangular numbers that are one less than a square, and this lets us find the larger solution in a few seconds:
```
from enigma import (is_square, dsum, printf)

# generate solutions
def solve():
  t = 0
  D = 1
  # look for triangular numbers that are 1 less than a square
  while True:
    t += D
    R = is_square(t + 1)
    D += 1
    if R is not None and dsum(D) == dsum(R):
      yield (R, D)

# look for the first solution
for (R, D) in solve():
  printf("R={R} D={D}")
  break
```
    To get a faster program we can look at the sequence of (R, D) values with equal “inter-sums”:
    
    R = 1, 1, 2, 4, 11, 23, 64, … [= OEIS A006452]
    D = 0, 1, 3, 6, 16, 33, 91, … [= OEIS A006451 + 1]
    
    After the first 4 values these sequences can be generated by the following recurrence relations:
    
    R[n] = 6 R[n − 2] − R[n − 4]
    D[n] = 6 D[n − 2] − D[n − 4] − 2
    
    We can then test the generated (R, D) values to look for pairs with equal digit sums:
```
from enigma import (dsum, first, arg, printf)

# find (R, D) pairs
def solve():
  # first 4 (R, D) pairs
  q = [(1, 0), (1, 1), (2, 3), (4, 6)]
  
  while True:
    # compute the next pair
    (R2, D2) = q[2]
    (R0, D0) = q[0]
    R = 6 * R2 - R0
    D = 6 * D2 - D0 - 2
    if dsum(R) == dsum(D): yield (R, D)

    q.pop(0)
    q.append((R, D))

# find the first N solutions
N = arg(8, 0, int)
for (i, (R, D)) in enumerate(first(solve(), N, fn=iter), start=1):
  printf("{i}: R={R}, D={D}")
```
    Here are the first 8 solutions:
```
% python3 teaser2798g.py 8
1: R=64, D=91
2: R=85225144, D=120526555
3: R=98349742324, D=139087539451
4: R=151143569481047247784, D=213749285825577237211
5: R=1844521723207478395861, D=2608547637051808009585
6: R=2128576470207852702322273, D=3010261712716195592552833
7: R=2834655085444781980043036964601, D=4008807666485875255750052272225
8: R=268047403891416806462822495283352, D=379076273942140382330486943077083
```
    The (R, D) values can also be generated using Pell’s Equation ((2D − 1)² − 8R² = −7), which gives the following recurrence relation (as noted by Brian Gladman [link]):
    
    R = 1, 1, …
    D = 0, 1, …
    R[n] = 2 D[n − 2] + 3 R[n − 2] − 1
    D[n] = 3 D[n − 2] + 4 R[n − 2] − 1
    
    LikeLike
- GeoffR 8:01 pm on 22 June 2021 Permalink | Reply
  I tested for a solution for 2-digit house numbers up to 100.
  
  This solution tests for equality of the sum of two arithmetic series of house numbers:
  
  1) Between Philip and Me (P and M)
  2) Between Me and Daphne (M and D)
```
# P..................M..............D  house numbers
# no. of houses between M and D is (D - M - 1)

P = 1

for M in range(10, 100):
  for D in range(M+1, 100):
    # no. of houses for series between P -> M
    nh1 = M - 2
    # no. of houses for series between M -> D
    nh2 = D - M - 1
    # S1 = arithmetic sum of numbers between P and M
    S1 = nh1 // 2 * (2 * (P + 1) + (nh1 - 1) * 1)
    # S2 = arithmetic sum of numbers between M and D
    S2 = nh2 // 2 * (2 * (M + 1) + (nh2 - 1) * 1)
    if S1 == S2:
      # digits in house numbers M and D
      d1, d2 = M // 10, M % 10
      d3, d4 = D // 10, D % 10
      # the digits of Daphne’s house number add up to
      # ..the same total as the digits of my house number
      if d1 + d2 == d3 + d4:
        print(f"My house number is {M}.")
        print(f"Daphne's house number is {D}.")

# My house number is 64.
# Daphne's house number is 91.
```
  LikeLike
- John Crabtree 4:45 pm on 25 June 2021 Permalink | Reply
  
  Brian Gladman expresses the Pell equation as
  (2D- 1)^2 – 8R^2 = – 7
  Let E = 2D – 1 and then E^2 -8R^2 = -7
  The Wolfram web page on the Pell equation suggests that there may be multiple series derived from multiple basic solutions. That is the case here. One sequence is
  R = 1, 4, 23, …..
  E = 1, 11, 65, …
  The other sequence is:
  R = 1, 2, 11, 64, …..
  E = -1, 5, 31, 181, ….
  In each case R(n) = 6 * R(n-1) – R(n-2) and E(n) = 6 * E(n-1) – E(n-2)
  This makes it easier to solve the difference equations.
  Or R(n) = 3 * R(n – 1) + E(n – 1) and E(n) = 3 * E(n – 1) + 8(n-1)
  
  One can show that the fact that the digits in D’s and R’s numbers add to the same number means that R = D = 1 mod 3. The reduces the work in a manual (calculator) search.
  
  LikeLike
- GeoffR 6:46 pm on 26 June 2021 Permalink | Reply
```
% A Solution in MiniZinc
include "globals.mzn";

var 10..99:M;  % My house number
var 10..99:D;  % Daphne's house number

% house number digits for Me and Daphne
var 1..9:d1; var 1..9:d2; var 1..9:d3; var 1..9:d4;

% Using Brian's equation: (2.D - 1)^2 - 2(2.M)^2 = -7
constraint (2*D - 1) * (2*D - 1) - 2 * (2 * M)*(2 * M) == -7;

% Equate sum of digits of M and D
constraint d1 == M div 10 /\ d2 == M mod 10 /\ d3 == D div 10 
/\ d4 == D mod 10 /\ (d1 + d2) == (d3 + d4);

solve satisfy;

output[ "My house = " ++ show(M) ++ " and Daphne's house = " ++ show(D) ];

% My house = 64 and Daphne's house = 91
% ----------
% ==========
```
  LikeLike

Jim Randell 9:18 am on 10 September 2020 Permalink | Reply
Tags: by: Robin Nayler

Teaser 2730: It’s a lottery

From The Sunday Times, 18th January 2015 [link]

I regularly entered the Lottery, choosing six numbers from 1 to 49. Often some of the numbers drawn were mine but with their digits in reverse order. So I now make two entries: the first entry consists of six two-figure numbers with no zeros involved, and the second entry consists of six entirely different numbers formed by reversing the numbers in the first entry. Interestingly, the sum of the six numbers in each entry is the same, and each entry contains just two consecutive numbers.

What (in increasing order) are the six numbers in the entry that contains the highest number?

[teaser2730]

Jim Randell 9:18 am on 10 September 2020 Permalink | Reply

Each digit in the 2-digit numbers must form a tens digit of one of the 2-digit lottery numbers, so the digits are restricted to 1, 2, 3, 4, and no number may use two copies of the same digit.

The following Python program runs in 51ms.

Run: [ @replit ]

from enigma import (subsets, irange, intersect, tuples, printf)

# generate (number, reverse) pairs
ps = list((10 * a + b, 10 * b + a) for (a, b) in subsets(irange(1, 4), size=2, select="P"))

# count consecutive pairs of numbers
cons = lambda s: sum(y == x + 1 for (x, y) in tuples(s, 2))

# find 6-sets of pairs
for ss in subsets(ps, size=6):
  # split the pairs into numbers, and reverse numbers
  (ns, rs) = zip(*ss)
  rs = sorted(rs)
  # ns has the highest number
  if not (ns[-1] > rs[-1]): continue
  # sequences have the same sum
  if sum(ns) != sum(rs): continue
  # sequences have no numbers in common
  if intersect((ns, rs)): continue
  # sequences have exactly one consecutive pair
  if not (cons(ns) == 1 and cons(rs) == 1): continue
  # output solution
  printf("{ns}; {rs}", rs=tuple(rs))

Solution: The six numbers are: 13, 21, 23, 24, 41, 43.

23 and 24 are consecutive.

Which means the reversed numbers (in order) are: 12, 14, 31, 32, 34, 42.

31 and 32 are consecutive.

LikeLike

Frits 6:11 pm on 10 September 2020 Permalink | Reply

As all 12 numbers must be different we can reduce the main loop from 924 to 64 iterations.
We can’t pick more than one item from each of the 6 groups.

There probably is a more elegant way to create the list sixgroups.

Using function seq_all_different instead of intersect doesn’t seem to matter.

 
from enigma import subsets, irange, printf, seq_all_different
from itertools import product

# group 1:  (12, 21) (21, 12)
# group 2:  (13, 31) (31, 13)
# group 3:  (14, 41) (41, 14)
# group 4:  (23, 32) (32, 23)
# group 5:  (24, 42) (42, 24)
# group 6:  (34, 43) (43, 34)

sixgroups = [[]]*6
i = 0
for a in range(1,4):
  for b in range(a+1,5):
    sixgroups[i] = [((10 * a + b, 10 * b + a))]
    sixgroups[i].append((10 * b + a, 10 * a + b))
    i += 1

# pick one from each group
sel = [p for p in product(*sixgroups)]

# count consecutive pairs of numbers
cons = lambda s: sum(y == x + 1 for (x, y) in list(zip(s, s[1:])))
 
# find 6-sets of pairs
for ss in sel:
  # split the pairs into numbers, and reverse numbers
  (ns, rs) = zip(*ss)
  ns = sorted(ns)
  rs = sorted(rs)
  # ns has the highest number
  if not(ns[-1] > rs[-1]): continue
  # sequences have the same sum
  if sum(ns) != sum(rs): continue
  # sequences have no numbers in common
  if not seq_all_different(ns + rs): continue
  # sequences have exactly one consective pair
  if not(cons(ns) == 1 and cons(rs) == 1): continue
  # output solution
  printf("{ns}; {rs}", rs=tuple(rs))

LikeLike

Jim Randell 9:25 pm on 10 September 2020 Permalink | Reply
For this particular puzzle (where all 12 possible numbers are used) we can go down to 32 pairs of sequences, as we always need to put the largest number (43) into the first sequence (and so 34 goes in the second sequence, and we don’t need to check the sequences have no numbers in common).

Here’s my way of dividing the 12 candidate digit pairs into the 32 pairs of sequences:
```
from enigma import (subsets, irange, nconcat, tuples, printf)

# possible digit pairs
ps = list(subsets(irange(1, 4), size=2))

# construct numbers from digit pairs <ps> and flags <fs> (and xor flag <x>)
def _construct(ps, fs, x=0):
  for ((a, b), f) in zip(ps, fs):
    yield (nconcat(a, b) if f ^ x else nconcat(b, a))
construct = lambda *args: sorted(_construct(*args))

# count consecutive pairs of numbers
cons = lambda s: sum(y == x + 1 for (x, y) in tuples(s, 2))

# choose an order to assemble digits
for fs in subsets((0, 1), size=5, select="M"):
  fs += (0,)
  ns = construct(ps, fs, 0)
  rs = construct(ps, fs, 1)
  # sequences have the same sum
  if sum(ns) != sum(rs): continue
  # sequences have exactly one consecutive pair
  if not (cons(ns) == 1 and cons(rs) == 1): continue
  # output solution
  printf("{ns}; {rs}")
```
And as all the numbers are used, and their sum is 330, we know each of the sequences must sum to 165.

The more analysis we do, the less work there is for a program to do.

LikeLike
- Frits 5:11 pm on 11 September 2020 Permalink | Reply
  We can go on like this.
  
  fi, three consecutive numbers, we can exclude 111…, 000… and ..0.00 from fs and get it down from 34 to 18.
```
12 13 14 23 24 34 Group A
21 31 41 32 42 43 Group B
-----------------
 9 18 27  9 18  9 Difference 
```
  Regarding the sum constraint we can derive that for each lottery entry from each group 2, 3 or 4 numbers have to picked.
  The numbers picked from group B must have a total difference of 45 (same for the numbers picked from group A)..
  
  If only 2 numbers are picked from a group then this group must be group B and the numbers {41, 42} or {41, 31}.
  
  LikeLike

Frits 11:47 am on 10 September 2020 Permalink | Reply

Based on Jim’s cons lambda function.

 
from enigma import SubstitutedExpression, irange, seq_all_different, tuples

p = SubstitutedExpression([
    # sum of the six numbers in each entry is the same
    "AB + CD + EF + GH + IJ + KL == BA + DC + FE + HG + JI + LK",
    # ascending range
    "AB < CD", "CD < EF", "EF < GH", "GH < IJ", "IJ < KL",
    # all different numbers
    "diff([AB, CD, EF, GH, IJ, KL, BA, DC, FE, HG, JI, LK])",
    # each entry contains just two consecutive numbers
    "consec([AB, CD, EF, GH, IJ, KL]) == 1",
    "consec([BA, DC, FE, HG, JI, LK]) == 1",
    # report entry that contains the highest number
    "max(AB, CD, EF, GH, IJ, KL) >= max(BA, DC, FE, HG, JI, LK)",
   ],
    verbose=0,
    answer="AB, CD, EF, GH, IJ, KL",
    code="diff = lambda x: seq_all_different(x); \
          consec = lambda s: sum(y == x + 1 \
                             for (x, y) in tuples(sorted(s), 2))",
    distinct="",
    digits=irange(1,4)
)

# Print answers
for (_, ans) in p.solve():
  print(ans)  

# Output:
#
# (13, 21, 23, 24, 41, 43)

LikeLike

Frits 12:16 pm on 10 September 2020 Permalink | Reply

list(zip(s, s[1:])) is the same as tuples(s, 2)

LikeLike

Jim Randell 1:23 pm on 21 July 2020 Permalink | Reply
Tags: by: Robin Nayler
Teaser 2683: House-to-house
From The Sunday Times, 23rd February 2014 [link] [link]

Tezar Road has houses on one side only, numbered consecutively. The Allens, Browns, Carrs and Daws live in that order along the road, with the Allens’ house number being in the teens. The number of houses between the Allens and the Browns is a multiple of the number of houses between the Browns and the Carrs. The number of houses between the Allens and the Carrs is the same multiple of the number of houses between the Carrs and the Daws. The Daws’ house number consists of the same two digits as the Allens’ house number but in the reverse order.

What are the house numbers of the four families?

[teaser2683]
Rate this:
Share:
X
Facebook
WhatsApp
Email
Like Loading...
Jim Randell is discussing. Toggle Comments
- Jim Randell 1:23 pm on 21 July 2020 Permalink | Reply
  In order to get a unique solution we require “multiple” to be a “proper multiple” (i.e. not ×1).
  
  This Python program runs in 51ms.
  
  Run: [ @replit ]
```
from enigma import (irange, divisors, div, printf)

# A is in [13, 19]
for d in irange(3, 9):
  A = 10 + d
  # D is the reverse of A
  D = 10 * d + 1
  # C divides AD in to m-1:1
  n = D - A - 2
  for m in divisors(n):
    if not (2 < m < n): continue
    C = D - (n // m) - 1
    # B divides AC into the same ratio
    x = div(C - A - 2, m)
    if x is None: continue
    B = C - x - 1
    # output solution
    printf("A={A} B={B} C={C} D={D} [ratio = {m}:1]", m=m - 1)
```
  Solution: The house numbers are: 19, 64, 76, 91.
  
  There are 44 houses between A and B, and 11 between B and C.
  
  There are 56 houses between A and C, and 14 between C and D.
  
  Allowing m = 1 also gives the following solutions:
  
  A=15, B=24, C=33, D=51
  A=19, B=37, C=55, D=91
  
  LikeLike

	Frits on Teaser 2363: [A round num…
	Jim Randell on Teaser 2363: [A round num…
	Jim Randell on Teaser 2363: [A round num…
	Frits on Teaser 2363: [A round num…
	Ruud on Teaser 2363: [A round num…
	Jim Randell on Teaser 2363: [A round num…
	Frits on Teaser 3304: Roaming bull
	Jim Randell on Teaser 3304: Roaming bull

Search

Recent Posts

Recent Comments

Archives

Categories

Subscribe

RSS Links

Site Stats

Meta

Tagged: by: Robin Nayler Toggle Comment Threads | Keyboard Shortcuts

Jim Randell 8:27 am on 8 April 2025 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 8:27 am on 8 April 2025 Permalink | Reply

Reply Cancel reply

Jim Randell 10:22 pm on 3 January 2025 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 10:22 pm on 3 January 2025 Permalink | Reply

Hugo 7:23 am on 5 January 2025 Permalink | Reply

Hugo 7:32 am on 6 January 2025 Permalink | Reply

Jim Randell 10:46 am on 15 August 2024 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 10:46 am on 15 August 2024 Permalink | Reply

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply

Frits 1:30 pm on 1 July 2024 Permalink | Reply

Jim Randell 2:21 pm on 3 July 2024 Permalink | Reply

Frits 2:55 pm on 3 July 2024 Permalink | Reply

Jim Randell 4:24 pm on 3 July 2024 Permalink | Reply

Jim Randell 8:43 am on 5 July 2024 Permalink | Reply

Frits 2:20 pm on 5 July 2024 Permalink | Reply

Frits 1:25 pm on 1 July 2024 Permalink | Reply

Ruud 3:12 pm on 1 July 2024 Permalink | Reply

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

Frits 5:44 pm on 1 July 2024 Permalink | Reply

Frits 9:26 pm on 18 July 2024 Permalink | Reply

Jim Randell 7:33 pm on 9 May 2024 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 7:34 pm on 9 May 2024 Permalink | Reply

Frits 10:06 am on 10 May 2024 Permalink | Reply

GeoffR 10:35 am on 10 May 2024 Permalink | Reply

Jim Randell 5:16 pm on 19 February 2024 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 5:17 pm on 19 February 2024 Permalink | Reply

Frits 9:51 am on 23 February 2024 Permalink | Reply

Jim Randell 7:55 am on 14 November 2023 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 7:55 am on 14 November 2023 Permalink | Reply

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

Rate this:

Share:

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

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

Rate this:

Share:

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

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

Jim Randell 10:34 am on 23 March 2023 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 10:34 am on 23 March 2023 Permalink | Reply

Jim Randell 9:29 am on 21 March 2023 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 9:30 am on 21 March 2023 Permalink | Reply

Jim Randell 9:14 am on 7 February 2023 Permalink | Reply Tags: by: Robin Nayler, flawed ( 53 )

Rate this:

Share:

Jim Randell 9:15 am on 7 February 2023 Permalink | Reply

Jim Randell 8:45 am on 27 September 2022 Permalink | Reply Tags: by: Robin Nayler

Rate this:

Share:

Jim Randell 8:46 am on 27 September 2022 Permalink | Reply

Jim Randell 8:27 am on 8 April 2025 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 10:22 pm on 3 January 2025 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 3:59 pm on 25 June 2024 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 7:33 pm on 9 May 2024 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 5:16 pm on 19 February 2024 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 7:55 am on 14 November 2023 Permalink | Reply
Tags: by: Robin Nayler

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

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

Jim Randell 10:34 am on 23 March 2023 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 9:29 am on 21 March 2023 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 9:14 am on 7 February 2023 Permalink | Reply
Tags: by: Robin Nayler, flawed ( 53 )

Jim Randell 8:45 am on 27 September 2022 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 3:24 pm on 22 June 2021 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 9:18 am on 10 September 2020 Permalink | Reply
Tags: by: Robin Nayler

Jim Randell 1:23 pm on 21 July 2020 Permalink | Reply
Tags: by: Robin Nayler