Teaser 3046: Square phone numbers
From The Sunday Times, 7th February 2021 [link] [link]
George and Martha run a business in which there are 22 departments. Each department has a perfect-square three-digit extension number, i.e., everything from 100 (10²) to 961 (31²), and all five of their daughters are employees in separate departments.
Andrea, Bertha, Caroline, Dorothy and Elizabeth have extensions in numerical order, with Andrea having the lowest number and Elizabeth the highest. George commented that, if you look at those of Andrea, Bertha and Dorothy, all nine positive digits appear once. Martha added that the total of the five extensions was also a perfect square.
What is Caroline’s extension?
[teaser3046]
Frits, 
Tony Brooke-Taylor, 
GeoffR, and 1 other are discussing. 
S2T2 
Jim Randell 5:03 pm on 5 February 2021 Permalink |
A simple Python program finds the solution in 67ms.
Run: [ @repl.it ]
from enigma import powers, subsets, concat, is_square, printf # possible square numbers squares = powers(10, 31, 2) # choose 5 of the squares (in order) for (A, B, C, D, E) in subsets(squares, size=5): # the sum of the numbers is also a square if not is_square(A + B + C + D + E): continue # A, B, D use the digits 1-9 ds = concat(A, B, D) if '0' in ds or len(set(ds)) != 9: continue # output solution printf("A={A} B={B} C={C} D={D} E={E}")Solution: Caroline’s extension is 729.
Manually, you can write out the squares, and then working through the possible candidates for A, B, D, the solution is discovered quite quickly.
LikeLike
GeoffR 7:51 pm on 5 February 2021 Permalink |
% A Solution in MiniZinc include "globals.mzn"; % Andrea, Bertha, Caroline, Dorothy and Elizabeth's numbers var 100..961:A; var 100..961:B; var 100..961:C; var 100..961:D; var 100..961:E; constraint all_different([A, B, C, D, E]); constraint A < B /\ B < C /\ C < D /\ D < E; % digits for squares A, B and D var 1..9:a1; var 1..9:a2; var 1..9:a3; var 1..9:b1; var 1..9:b2; var 1..9:b3; var 1..9:d1; var 1..9:d2; var 1..9:d3; % all 3-digit squares set of int: sq3 = {n*n | n in 10..31}; predicate is_sq(var int: y) = exists(z in 1..ceil(sqrt(int2float(ub(y))))) (z*z = y); % the total of the five extensions was also a perfect square constraint is_sq(A + B + C + D + E); % all five telephone extensions are 3-digit squares constraint A in sq3 /\ B in sq3 /\ C in sq3 /\ D in sq3 /\ E in sq3; % digit components in squares A, B and D constraint a1 == A div 100 /\ a2 == A div 10 mod 10 /\ a3 == A mod 10; constraint b1 == B div 100 /\ b2 == B div 10 mod 10 /\ b3 == B mod 10; constraint d1 == D div 100 /\ d2 == D div 10 mod 10 /\ d3 == D mod 10; set of int: all_dig ={1, 2, 3 ,4, 5, 6, 7, 8, 9}; var set of int: S1 == {a1, a2, a3, b1, b2, b3, d1, d2, d3}; constraint all_dig == S1; solve satisfy; output ["Caroline's extension is " ++ show(C) ++"\nOther extensions are " ++ show(A) ++ ", " ++ show(B) ++ ", " ++ show(D) ++ ", " ++ show(E) ];LikeLike
GeoffR 8:44 am on 6 February 2021 Permalink |
from itertools import combinations from enigma import nsplit, is_square squares =[x * x for x in range(10, 32)] for A, B, C, D, E in combinations(squares, 5): # five extensions are in numerical order if A < B < C < D < E: sq_total = A + B + C + D + E if is_square(sq_total): # find individual digits of A, B and D a1, a2, a3 = nsplit(A) b1, b2, b3 = nsplit(B) d1, d2, d3 = nsplit(D) S1 = set((a1, a2, a3, b1, b2, b3, d1, d2, d3)) # check this set contains nine positive digits if len(S1) == 9 and 0 not in S1: print(f"Five extensions are {A}, {B}, {C}, {D}, {E}")LikeLike
Frits 7:44 pm on 6 February 2021 Permalink |
squares = [x * x for x in range(15, 66)] ABD_squares = [x * x for x in range(13, 31) if len(set(str(x * x) + "0")) == 4] for i, a in enumerate(ABD_squares[:-2]): for j, b in enumerate(ABD_squares[i + 1:-1]): if len(set(str(a) + str(b))) != 6: continue for d in ABD_squares[i + j + 2:]: if len(set(str(a) + str(b) + str(d))) != 9: continue p = squares.index(b) q = squares.index(d) for c in squares[p + 1:q]: for e in squares[q + 1:17]: if not (a + b + c + d + e) in squares: continue print(f"Caroline's extension is {c}.")LikeLike
Tony Brooke-Taylor 10:21 am on 7 February 2021 Permalink |
import itertools digits = set([str(j) for j in range(1, 10)]) for M in itertools.combinations([i**2 for i in range(10, 32)], 5): if (sum(M)**(1/2))%1 == 0: if set(str(M[0])+str(M[1])+str(M[3])) == digits: print("Caroline's extension is", M[2])LikeLike
Frits 4:21 pm on 7 February 2021 Permalink |
Logic can reduce a,b and d to specific squares.
The version without reduction logic is faster.
from collections import defaultdict squares = [x * x for x in range(15, 66)] ABD_squares = [x * x for x in range(13, 31) if len(set(str(x * x) + "0")) == 4] # return first column col0 = lambda li: [x[0] for x in li] fixed = set() str_fixed = "" mut_excl = defaultdict(set) # reduce candidates in list <ABD_squares> # by looking for digits occurring once or twice in list <ABD_squares> for loop in range(9): occ = defaultdict(list) for x in "123456789": # add entries to occurence dictionary <occ> for i, s in enumerate(ABD_squares): s1 = str(s) if x not in s1 or s1 in fixed: continue # skip if a square digit already occurs in <fixed> if any(y in str_fixed for y in s1): continue occ[x].append([i, s1]) if len(occ[x]) == 1: # a square has to occur in <ABD_squares> if not occ[x][0][1] in fixed: fixed.add(occ[x][0][1]) str_fixed = "".join(fixed) # also update occurrence for other 2 related digits to same square for c in occ[x][0][1]: if c == x: continue occ[c] = occ[x] elif len(occ[x]) == 2: # we have a square with digits x,e,f and a square with digits x,g,h # so e, e, f, f may not occur in another square with resp. g, h ,g, h for y in occ[x][0][1]: if y == x: continue for z in occ[x][1][1]: if z == x: continue mut_excl[y].add(z) mut_excl[z].add(y) # check if 2 digits always occur in different squares for x1, y1 in occ.items(): for x2, y2 in occ.items(): if x1 >= x2: continue if len(set(col0(y1) + col0(y2))) != \ len(col0(y1)) + len(col0(y2)): continue # digit x1 and x2 occur in different squares # so maintain dictionary <mut_excl> mut_excl[x1].add(x2) mut_excl[x2].add(x1) # reduce squares if a square contains mutually exclusive digits ABD_squares = [s for s in ABD_squares if not any(m in str(s) for y in str(s) for m in mut_excl[y]) ] if len(ABD_squares) == 3: break # start with a,b,d and then check c and e for i, a in enumerate(ABD_squares[:-2]): for j, b in enumerate(ABD_squares[i + 1:-1]): if len(set(str(a) + str(b))) != 6: continue for d in ABD_squares[i + j + 2:]: if len(set(str(a) + str(b) + str(d))) != 9: continue p = squares.index(b) q = squares.index(d) for c in squares[p + 1:q]: for e in squares[q + 1:17]: if not (a + b + c + d + e) in squares: continue print(f"Caroline's extension is {c}.")LikeLike
Frits 1:25 pm on 8 February 2021 Permalink |
Not very efficient.
# decompose a number into <k> increasing 3-digit squares a, b, c, d, e # (a, b, d) has to contain all digits 1-9 def decompose(t, k, m=1, ss=[]): if k == 1: # check if last number is higher and a square if t > ss[-1] and int(t ** 0.5) ** 2 == t: yield ss + [t] else: for i in range(m, 32 - k + 1): s = i * i if s > t: break if k in {3, 1} or len(set(str(s) + "0")) == 4: yield from decompose(t - s, k - 1, i + 1, ss + [s]) # sum first five 3-digit squares is 750 and last five 3-digit squares is 4215 for r in range(28, 65): # get five 3-digit squares which add up to square <r * r> for x in decompose(r * r, 5, 10): sabd = set(str(1000000 * x[0] + 1000 * x[1] + x[3])) if len(sabd) != 9: continue print(f"Caroline's extension is {x[2]}.")LikeLike