Teaser 3019: William’s prime
From The Sunday Times, 2nd August 2020 [link]
William was searching for a number he could call his own. By consistently replacing digits with letters, he found a number represented by his name: WILLIAM.
He noticed that he could break WILLIAM down into three smaller numbers represented by WILL, I and AM, where WILL and AM are prime numbers.
He then calculated the product of the three numbers WILL, I and AM.
If I told you how many digits there are in the product, you would be able to determine the number represented by WILLIAM.
What number is represented by WILLIAM?
[teaser3019]
GeoffR, 
Frits, and 
Robert Brown are discussing. 
Benet Allen are discussing. 
Brian Gladman, 
S2T2 
Jim Randell 4:40 pm on 31 July 2020 Permalink |
We can use the [[
SubstitutedExpresison()]] solver to solve the alphametic problem, and [[filter_unique()]] function to collect the answer (both from the enigma.py library).This Python program runs in 71ms.
Run: [ @repl.it ]
from enigma import SubstitutedExpression, filter_unique, nsplit, unpack, printf # the alphametic problem p = SubstitutedExpression( [ "is_prime(WILL)", "is_prime(AM)" ], answer="(WILLIAM, WILL * I * AM)", verbose=0, ) # find results unique by the length of the product in the answer (rs, _) = filter_unique( (ans for (_, ans) in p.solve()), unpack(lambda w, p: len(nsplit(p))), ) # output solution for (w, p) in rs: printf("WILLIAM = {w} [product = {p}]")Solution: WILLIAM = 4177123.
If the value of I is unconstrained there are 579 solutions to the alphametic puzzle. (If we don’t allow I to be prime this number is reduced to 369 solutions, but the answer to the puzzle remains unchanged).
114 give a 1-digit product (when I is 0), 221 give a 7-digit product, 243 give a 6-digit product, and 1 solution gives a 5-digit product, so this gives us the answer to the problem.
As suggested by the puzzle’s title, 4177123 is prime.
Using the recently added [[
accumulate]] parameter for the [[SubstitutedExpression()]] solver in the enigma.py library (and the even more recently added annotated return value from [[filter_unique()]]), we can write a run-file that solves this puzzle:Run: [ @repl.it ]
LikeLike
GeoffR 8:53 am on 4 August 2020 Permalink |
I found I had to test for the three constraints individually (for the three constraints following this line) by remmimg out two of the three constraints to test the other constraint. Using all the constraints together gave multiple solutions.
i.e.
% Three tests for product – if 5, 6 or 7 digits long
This is a part manual / part programme solution, but it does get the answer – but it is not an ideal programme solution.
@Jim: Do you think there could be a better fix in MiniZinc to get a full programme solution?
Unfortunately we don’t seem to have the len(str(int)) fix in MiniZinc.
LikeLike
Jim Randell 11:53 am on 4 August 2020 Permalink |
@Geoff: MiniZinc does have
log10(), which can be used to determine the number of digits in a number.But I would probably have MiniZinc generate all the solutions to the alphametic, and then use Python to analyse the output.
LikeLike
Frits 12:03 am on 6 August 2020 Permalink |
Same as Jim’s but for me easier to understand.
Ideal would be a kind of HAVING clause in the SubstitutedExpression
(something like HAVING COUNT(len(nsplit(WILL * I * AM)) == 1).
from enigma import SubstitutedExpression, nsplit, printf # the alphametic problem p = SubstitutedExpression( [ "is_prime(WILL)", "is_prime(AM)", ], answer="(len(nsplit(WILL * I * AM)), WILLIAM, WILL * I * AM)", verbose=0, ) # collect all answers and maintain frequency answs = [] mltpl = {} for (_, ans) in p.solve(verbose=0): answs.append(ans) mltpl[ans[0]] = ans[0] in mltpl # only print answers with a unique first element for (ans) in answs: if not mltpl[ans[0]]: printf("WILLIAM = {ans[1]}, WILL * I * AM = {ans[2]}")LikeLike
Frits 3:19 pm on 6 August 2020 Permalink |
prms = {2, 3, 5, 7} # P1 = AM primes P1 = {x for x in range(13, 97, 2) if all(x % p for p in prms)} prms = {2, 3, 5, 7, 11} | P1 # P2 = WILL primes, exclude primes WXYZ where Y!=Z and where X = 0 P2 = {x for x in range(1001, 9999, 2) if all(x % m for m in prms) and str(x)[-1] == str(x)[-2] and str(x)[1] != '0'} answs = {} mltpl = {} for p2 in P2: I = str(p2)[1] # WIL digits have to be different if len(list(set(str(p2)[0:3]))) < 3: continue for p1 in P1: # WILAM digits have to be different if len(list(set(str(p1)+str(p2)[0:3]))) < 5: continue prodlen = len(str(p2 * int(I) * p1)) mltpl[prodlen] = prodlen in mltpl # store first prodlen entry if not mltpl[prodlen] : answs[prodlen] = str(p2) +" " + I + " " + str(p1) print("WILL I AM") for ans in answs: # only print answers with a unique product length if not mltpl[ans]: print(answs[ans])LikeLike
GeoffR 11:05 pm on 2 December 2020 Permalink |
from collections import defaultdict from itertools import permutations from enigma import is_prime D = defaultdict(list) for P in permutations('123456789', 5): w, i, l, a, m = P will, am = int(w + i + l + l), int(a + m) if not is_prime(will) or not is_prime(am): continue i = int(i) product = str(will * i * am) D[len(product)] += [(will, i, am)] for k, v in D.items(): # there must be a unique number of digits in the product if len(v) == 1: will, i, am = v[0][0], v[0][1], v[0][2] william = 1000 * will + 100 * i + am print(f"WILLIAM = {william}") # WILLIAM = 4177123LikeLike