Brain Teaser: Noughts and crosses
From The Sunday Times, 23rd December 1956 [link]
Each square is to be occupied by either a nought or a cross.
The cross (or x) stands for one particular digit which you may discover for yourself.
No light begins with nought.
The following clues give the prime factors of the various lights, each letter representing a different prime:
Across:
(I) abcd
(II) a²b²ef
(III) ab²gh
(IV) abij²k
(V) a²bejl
(VI) ab²ikmDown:
(i) ab²ijkm
(ii) a²beij²k
(iii) ab²mnp
(iv) a²bcde
(v) abijkl
This is one of the occasional Holiday Brain Teasers published in The Sunday Times prior to the start of numbered Teasers in 1961. Prizes of £5, £3 and £1 were offered for the first 3 correct solutions.
[teaser-1956-12-23] [teaser-unnumbered]
Frits are discussing. 
S2T2 
Jim Randell 11:04 am on 28 November 2021 Permalink |
Once you get going I think it is easier to solve this puzzle by hand. But here is a fully programmed solution:
The numbers (I) and (i) must be repdigits of the appropriate length with the appropriate prime factorisation patterns.
This immediately gives us the required digit x, then we just have to fill out the remaining numbers, matching the factorisation patterns.
This Python program runs in 49ms.
Run: [ @replit ]
from enigma import irange, repdigit, singleton, intersect, subsets, nconcat, prime_factor, div, choose, diff, chain, multiply, nsplit, unzip, printf # find factors of n, with multiplicities in ms def factor(n, ms={1, 2}): r = dict((k, list()) for k in ms) for (p, e) in prime_factor(n): if e not in r: return r[e].append(p) return r # consider values for the digit x for x in irange(1, 9): # (I) = xxxxx = a.b.c.d a1 = repdigit(5, x) fsa1 = factor(a1, {1}) if fsa1 is None or not(len(fsa1[1]) == 4): continue # (i) = xxxxxx = a.b^2.i.j.k.m d1 = repdigit(6, x) fsd1 = factor(d1) if fsd1 is None or not(len(fsd1[2]) == 1 and len(fsd1[1]) == 5): continue b = singleton(fsd1[2]) a = singleton(intersect([fsd1[1], fsa1[1]])) printf("x={x}; dn1={d1} ac1={a1}; a={a} b={b}") # calculate factorisations of x???? / (a.b) fs5 = dict() for ds in subsets((0, x), size=4, select="M", fn=list): ds.insert(0, x) n = nconcat(ds) n_ = div(n, a * b) if n_ is None: continue fs = factor(n_, {1, 2}) if fs: fs5[n] = fs # look for values for (II), (III), (IV), (V) def fna6(a6): (a6, fs) = a6 # there should be 4 single factors, one is b, none is a return (len(fs[2]) == 0 and len(fs[1]) == 4 and b in fs[1] and a not in fs[1]) def fna5(a6, a5): (a5, fs) = a5 # there should be 4 single factors, one is a, none is b return (len(fs[2]) == 0 and len(fs[1]) == 4 and a in fs[1] and b not in fs[1]) def fna4(a6, a5, a4): (a4, fs) = a4 # there should be 2 single factors and one double factor, [none is a or b] return (len(fs[2]) == 1 and len(fs[1]) == 2 and not intersect([[a, b], fs[1] + fs[2]])) def fna2(a6, a5, a4, a2): (a2, fs) = a2 # there are no double factors, 4 single factors, one of them is a, one of them is b return (len(fs[2]) == 0 and len(fs[1]) == 4 and a in fs[1] and b in fs[1]) def fna3(a6, a5, a4, a2, a3): (a3, fs) = a3 # there no double factors, 3 single factors, one of them is b, none of them a return (len(fs[2]) == 0 and len(fs[1]) == 3 and b in fs[1] and a not in fs[1]) for xs in choose(fs5.items(), [fna6, fna5, fna4, fna2, fna3], distinct=1): ((a6, fsa6), (a5, fsa5), (a4, fsa4), (a2, fsa2), (a3, fsa3)) = xs # determine factors j = singleton(fsa4[2]) ik = fsa4[1] m = singleton(diff(fsa6[1], [b] + ik)) e = singleton(diff(intersect([fsa2[1], fsa5[1]]), [a])) f = singleton(diff(fsa2[1], [a, b, e])) l = singleton(diff(fsa5[1], [a, e, j])) gh = diff(fsa3[1], [b]) cd = diff(fsa1[1], [a, b]) # check the down factorisations if not(d1 == multiply(chain([a, b, b, j, m], ik))): continue (_, d2, d3, d4, d5) = (nconcat(x) for x in unzip(nsplit(x) for x in (a1, a2, a3, a4, a5, a6))) if not(d2 == multiply(chain([a, a, b, e, j, j], ik))): continue if not(d4 == multiply(chain([a, a, b, e], cd))): continue if not(d5 == multiply(chain([a, b, j, l], ik))): continue np = div(d3, a * b * b * m) if np is None: continue np = factor(np, {1}) if np is None or len(np[1]) != 2: continue np = np[1] # check all the numbers are different if len(chain([a, b, j, m, e, f, l], ik, gh, cd, np, fn=set)) != 15: continue printf(" (I)={a1} (II)={a2} (III)={a3} (IV)={a4} (V)={a5} (VI)={a6}") printf(" (i)={d1} (ii)={d2} (iii)={d3} (iv)={d4} (v)={d5}") printf(" -> j={j} ik={ik} m={m} e={e} f={f} l={l} gh={gh} cd={cd} np={np}") printf()Solution: The completed grid looks like this:
We can determine the primes as:
Note that although it may look like the prime factorisation may have been presented in numerical order, this is not the case for at least 2 of the clues.
LikeLike
Jim Randell 9:57 am on 29 November 2021 Permalink |
Here is my manual solution:
(I) 11111 factorises as (41, 271), so that gives us two of a, b, c, d, and the remaining two come from the single digit x. So x = 6, and (a, b, c, d) = (2, 3, 41, 271) (in some order).
(i) 666666 factorises as (2, 3², 7, 11, 13, 37), so b = 3, a = 2, and (i, j, k, m) = (7, 11, 13, 37), (c, d) = (41, 271).
(iv) = (a², b, c, d, e) = 2 × (I) × e = 133332 × e, and consists of 6 digits chosen from (0, 6). The only possible prime value for e is 5, giving (iv) = 666660.
(VI) = (a, b², i, k, m) = 18 × ikm. Choosing one of the values from (7, 11, 13, 37) for j we get:
So j = 11, and (VI) = 60606.
(IV) = (a, b, i, j², k) = 726 × ik. Choosing one of the values from (7, 13, 37) for m we get:
So m = 37, ik = 7 × 13, and (IV) = 66066.
(ii) = (a², b, e, i, j², k) = 660660.
(II) = (a², b², e, f) = 180 × f, which matches 66?6?. The possible numbers are:
So, f = 367, and (II) = 66060.
(V) = (a², b, e, j, l) = 660 × l, and matches 66?6?. The possibilities are:
So l = 101 and (V) = 66660.
(v) = (a, b, i, j, k, l) = 606606.
(III) = (a, b², g, h) = 18 × gh, and matches 60?66. The possibilities are:
So (III) = 60066, and the grid is complete.
The solution was published in the 6th January 1957 issue of The Sunday Times along with the following note:
LikeLike
Frits 1:32 pm on 28 November 2021 Permalink |
from enigma import SubstitutedExpression, prime_factor, div, gcd # find multiplicities of factors of n mfac = lambda n: [[e for (p, e) in prime_factor(n)].count(i) for i in [1, 2]] # Z is cross digit (1 - 9) # # A B C D E # F G H I J # K L M N O # P Q R S T # U V W X Y # p q s t u # the alphametic puzzle p = SubstitutedExpression( [ # (I) abcd "mfac(ABCDE * Z) == [4, 0]", # (II) a²b²ef "mfac(FGHIJ * Z) == [2, 2]", # (III) ab²gh "mfac(KLMNO * Z) == [3, 1]", # (IV) abij²k "mfac(PQRST * Z) == [4, 1]", # (V) a²bejl "mfac(UVWXY * Z) == [4, 1]", # (VI) ab²ikm "mfac(pqstu * Z) == [4, 1]", # Down: # (i) ab²ijkm "mfac(AFKPUp * Z) == [5, 1]", # (ii) a²beij²k "mfac(BGLQVq * Z) == [4, 2]", # (iii) ab²mnp "mfac(CHMRWs * Z) == [4, 1]", # (iv) a²bcde "mfac(DINSXt * Z) == [4, 1]", # (v) abijkl "mfac(EJOTYu * Z) == [6, 0]", ], answer="([x * Z for x in [ABCDE, FGHIJ, KLMNO, PQRST, UVWXY, pqstu]]), \ ([x * Z for x in [AFKPUp, BGLQVq, CHMRWs, DINSXt, EJOTYu]])", symbols="ABCDEFGHIJKLMNOPQRSTUVWXYZpqstu", d2i=dict([(0, "ZABCDEFKPUp")] + [(k, "ABCDEFGHIJKLMNOPQRSTUVWXYpqstu") for k in range(2, 10)]), distinct="", env=dict(mfac=mfac), verbose=0, ) # print answers for (_, ans) in p.solve(): j = div(ans[1][0], ans[0][-1]) # (VI) and (i) if not j: continue l = div(j * ans[1][-1], ans[0][3]) # (IV) and (v) if not l: continue cd = div(j * l * ans[1][3], ans[0][4]) # (V) and (iv) if not cd: continue ab = div(ans[0][0], cd) # (I) if not ab: continue ik = div(ans[1][-1], j * l * ab) # (v) if not ik: continue ef = div(ans[0][1], ab**2) # (II) if not ef: continue a2be = div(ans[0][4], j * l) # (V) if not a2be: continue bf = div(ans[0][1], a2be) # (II) if not bf: continue f = gcd(ef, bf) e = ef // f b = bf // f a = ab // b m = div(ans[0][-1], a * b**2 * ik) # (VI) if not m: continue gh = div(ans[0][2], a * b**2) # (III) np = div(ans[1][2], a * b**2 * m) # (iii) print(" a b e f j l m cxd gxh ixk nxp\n", a, b, e, f, j, l, m, cd, gh, ik, np, "\n") for a in ans[0]: print(a)LikeLike
Jim Randell 4:41 pm on 28 November 2021 Permalink |
A neat use of the [[
SubstitutedExpression()]] solver.But do you think [[
mfac()]] is strong enough? A number like 9240 would give an answer of [4, 0], but not match the pattern a⋅b⋅c⋅d.Although checking the numbers have the right number of single and double prime factors turns out to be enough to narrow down the solution space to a single candidate, even without matching up the primes in the patterns.
LikeLike
Frits 9:37 pm on 28 November 2021 Permalink |
With a better “find multiplicities” function (thanks Jim).
Most of the work is now done by [[ SubstitutedExpression() ]].
from enigma import SubstitutedExpression, prime_factor, div, gcd as z # find multiplicities of factors of n def v(n, allowed): lst = [e for (p, e) in prime_factor(n)] # only consider factors with multiplicity 1 or 2 if any(x > 2 for x in lst): return False return [lst.count(i) for i in [1, 2]] == allowed # multiply all items by n def w(lst, n): return [x * n for x in lst] # Z is cross digit (1 - 9) # # A B C D E # F G H I J # K L M N O # P Q R S T # U V W X Y # p q s t u answer = "(w([ABCDE, FGHIJ, KLMNO, PQRST, UVWXY, pqstu], Z))," # a = ab / b answer += "(div(ab * UVWXY * feh, FGHIJ * jl * lcg)," # b = bf / f answer += "div(FGHIJ * jl * lcg, UVWXY * feh)," # e = ef / f answer += "div(FGHIJ * Z, ab**2 * feh), " answer += "feh, " # f answer += "jk, " # j answer += "lcg, " # l # m = ab²ikm / ab²ik) answer += "div(pqstu * (UVWXY * feh), FGHIJ * EJOTYu)," answer += "div(ABCDE * Z, ab)," # cd answer += "div(KLMNO * Z * UVWXY * feh, ab * FGHIJ * jl * lcg)," # gh answer += "div(EJOTYu * Z, ab * jl * lcg)," # ik answer += "div(CHMRWs * Z * EJOTYu, ab * jl * lcg * pqstu))," # np # the alphametic puzzle p = SubstitutedExpression( [ # Up: "v(ABCDE * Z, [4, 0])", # (I) abcd "v(FGHIJ * Z, [2, 2])", # (II) a²b²ef "v(KLMNO * Z, [3, 1])", # (III) ab²gh "v(PQRST * Z, [4, 1])", # (IV) abij²k "v(UVWXY * Z, [4, 1])", # (V) a²bejl "v(pqstu * Z, [4, 1])", # (VI) ab²ikm # Down: "v(AFKPUp * Z, [5, 1])", # (i) ab²ijkm "v(BGLQVq * Z, [4, 2])", # (ii) a²beij²k "v(CHMRWs * Z, [4, 1])", # (iii) ab²mnp "v(DINSXt * Z, [4, 1])", # (iv) a²bcde "v(EJOTYu * Z, [6, 0])", # (v) abijkl # j = ab²ijkm / ab²ikm "div(AFKPUp, pqstu) = jk", # l = j * abijkl / abij²k "div(jk * EJOTYu, PQRST) = lcg", # ab = abcd / (j*l*a²bcde / a²bejl) = (I) * (V) / (j * l * (iv) ) "div(Z * ABCDE * UVWXY, jk * lcg * DINSXt) = ab", # f = gcd(ef, bf) "z(div(FGHIJ * Z, ab**2), div(FGHIJ * jl * lcg, UVWXY)) = feh", ], answer=answer, symbols="ABCDEFGHIJKLMNOPQRSTUVWXYZabcefghjklpqstu", d2i=dict([(0, "ZABCDEFKPUp")] + [(k, "ABCDEFGHIJKLMNOPQRSTUVWXYpqstu") for k in range(2, 10)]), distinct="", env=dict(v=v,w=w,z=z), verbose=0, ) # check and print answers for (_, ans) in p.solve(): # check if all items are numbers if any(x is None for x in ans[1]): continue # check last 4 numbers on being a product of 2 primes if any(not v(x, [2, 0]) for x in ans[1][-4:]) : continue print("a b e f j l m cxd gxh ixk nxp") print(*ans[1]) for a in ans[0]: print(a)LikeLike
Sunday Times Brainteaser – Noughts and Crosses | PuzzlingInPython 5:01 pm on 29 November 2021 Permalink |
[…] Published 23rd December 1956 (link) […]
LikeLike