From The Sunday Times, 10th September 1995 [link]
The history-cum-maths teacher asked the class to name some years which the knew from history lessons. Johnny named 1066, the Battle of Hastings, and 1939, the outbreak of the Second World War. The teacher then asked him to calculate the difference between the two and Johnny got the correct answer of 873.
The teacher then asked Johnny if this difference was prime and Johnny answered correctly that it was not because, for example, it was divisible by three.
The teacher then asked the class to find the longest list of years they could from 0, 1, 2, …, 1999, 2000 so that for any two numbers in the list their difference was not prime.
Which numbers are in the longest such list?
This puzzle is included in the book Brainteasers (2002). The puzzle text above is taken from the book.
[teaser1721]
Frits, 
GeoffR, and 
Lise Andreasen and 
S2T2 
Jim Randell 9:11 am on 13 July 2023 Permalink |
This Python program runs in 94ms. Internal runtime is 30ms.
Run: [ @replit ]
from enigma import (Accumulator, irange, subsets, fraction, printf) # available digits digits = set(irange(1, 9)) # find maximum configurations r = Accumulator(fn=max, collect=1) # choose the denominators R, T, V, X in increasing order for (R, T, V, X) in subsets(digits, size=4, select='C'): # allocate the numerators for (Q, S, U, W, Y) in subsets(digits.difference((R, T, V, X)), size=5, select='P'): # evaluate the expression (a, b) = fraction(Q, R, S, T, U, V, W, X, -Y, 1) if b == 1: r.accumulate_data(a, (Q, R, S, T, U, V, W, X, Y)) # output solution(s) for (Q, R, S, T, U, V, W, X, Y) in r.data: printf("{Q}/{R} + {S}/{T} + {U}/{V} + {W}/{X} - {Y} = {r.value}")Solution: The largest possible answer is 12.
LikeLike
Frits 1:11 pm on 13 July 2023 Permalink |
LikeLike
Frits 1:20 pm on 13 July 2023 Permalink |
@Jim, is it possible to get a button like crayon on PuzzlingInPython?
It makes it less error prone to post replies.
LikeLike
Jim Randell 2:02 pm on 13 July 2023 Permalink |
Requiring the denominators be ordered makes this approach run about 10× faster:
Run: [ @replit ]
(Is “crayon” a WordPress plugin? I don’t think it is possible to install plugins on a free WordPress site. It looks like you need to pay £20/month to be able to do that).
LikeLike
Frits 5:48 pm on 13 July 2023 Permalink |
Not using the fact that 5 and 7 can’t be used as denominators.
from fractions import Fraction as RF # Q/R + S/T + U/V + W/X - Y = mx # available digits digits = set(range(1, 10)) # maximum sum for <k> fractions choosing numbers from a sorted sequence <s> def maxleft(s, k=4): assert len(s) >= 2 * k return int(sum([RF(s[-1 - x], s[x]) for x in range(k)])) # check if we can make total m of <k> fractions from digits in set <s> def check(s, m, k=4, ns=[]): if k == 1: ls = list(s) if m in {RF(ls[0], ls[1]), RF(ls[1], ls[0])}: print("answer:", sum(RF(x[0], x[1]) for x in ns) + m - Y) print(f"we can make remaining fraction {m} with digits {s}, other " f"fractions = {', '.join(str(x) + '/' + str(y) for x, y in ns)}") exit(0) else: # start with lowest denominators for d in (ss := sorted(s)): # ascending denominators if ns and d < ns[-1][1]: continue # start with highest numerators for n in ss[::-1]: if n != d: yield from check(s.difference([n, d]), m - RF(n, d), k - 1, ns + [(n, d)]) # build a descending list of maxima per Y M = sorted([(maxleft(sorted(digits.difference([Y]))) - Y, Y) for Y in range(1, 10)], reverse=1) inc = 0 # keep checking until solution gets too low (-9) while True: cnt = 0 # check Y's with the highest maximum first for (mx, Y) in M: if mx + Y - inc >= -8: cnt += 1 # check if we can make total from eight remaining digits for c in check(digits.difference([Y]), mx + Y - inc): pass if not cnt: break inc += 1LikeLike
GeoffR 2:05 pm on 14 July 2023 Permalink |
I found two integer solutions for the equation for the largest whole number. The largest of the two integer solutions was 12.
LikeLike
Frits 3:10 pm on 14 July 2023 Permalink |
Highest rational number seems to be 12.95 (9/1 + 8/2 + 7/4 + 6/5 – 3) and
-7.5381 (1/5 + 2/6 + 3/7 + 4/8 – 9) for the lowest.
LikeLike