Sunday Times Teaser 2825 – Twin Sets

by Victor Bryant

Published: 13 November 2016 (link)

The twins Wunce and Repete each made a list of positive perfect squares. In Wunce’s list each of the digits 0 to 9 was used exactly once, whereas in Repete’s list each of the digits was used at least once. Wunce commented that the sum of his squares equalled their year of birth, and Repete responded by saying that the sum of his squares was less than the square of their age [1].

What is the sum of Wunce’s squares, and what is the sum of Repete’s?

[1] “.. in 2018.” was omitted in error here.

2 Comments Leave one →

Brian Gladman permalink

There are problems with the wording of this teaser beyond that noted above. Repete’s list of squares could be [4, 9, 25, 36, 81, 100, 576] with a sum of 831. But we can add 1’s, 4’s or a 9 without exceeding the 841 sum of squares limit set by age of 29. Even if we assume that the lists don’t contain duplicates, we can still add a one to Repete’s set of squares so we don’t know whether his sum is 831 or 832.


from bisect import bisect

# find combinations of squares that use all the digits
# 0 .. 9 exactly once among them (sq: list of squares
# to try; set_d: digits seen so far; sql: squares used)
def find1(sq, set_d=set(), sql=[]):
  # if all digits are present
  if set_d == set('0123456789'):
    yield sum(sql), sql
  else:
    # add another square 
    for i, s in enumerate(sq):
      # check it adds only digits not already present
      if not set_d or not set_d.intersection(str(s)):
        # continue to add more squares if possible
        yield from find1(sq[i:], set_d.union(str(s)), sql + [s])

# find combinations of squares that use all the digits
# 0 .. 9 at least one and whose sum is less than some
# given maximum value (sq: list of squares to try;
# sum_sq_max: max sum of squares; rec: record minimum
# sum; set_d: digits seen so far; sql: squares used)
def find2(sq, sum_sq_max, set_d=set(), sql=[]):
  # compute the limit for remaining squares
  sq_lim = sum_sq_max - sum(sql)
  if sq_lim > 0:
    # are all digits present
    if set_d == set('0123456789'):
      yield sum(sql), sql
    # can we add another square?
    if sq and sq[0] < sq_lim:
      # consider each square that we can add
      for i in range(bisect(sq, sq_lim)):
        yield from find2(sq[i + 1:], sum_sq_max, 
                         set_d.union(str(sq[i])), sql + [sq[i]])

# squares less than 50^2, those less than 50^2 without
# duplicated digits
sq1 = [x * x for x in range(1, 50)]
sq2 = [x for x in sq1 if len(str(x)) == len(set(str(x)))]
# squares less than 29^2 
sq3 = [x * x for x in range(1, 29)]

# the possible lists for Wunce
for birth_year, sq_seq in find1(sq2):
  # birth year must be in or before the publication year
  if birth_year <= 2016:
    print("Wunce's sum is {} {}".format(birth_year, sq_seq))
    
    # now consider Repete's list for ages in 2018
    age = 2018 - birth_year
    sq3 = [x * x for x in range(1, age)]    
    for sm, seq in find2(sq3, age ** 2):
      print("Repete's sum is {} {}".format(sm, seq))

from bisect import bisect

# find combinations of squares that use all the digits

# 0 .. 9 exactly once among them (sq: list of squares

# to try; set_d: digits seen so far; sql: squares used)

def find1(sq, set_d=set(), sql=[]):

# if all digits are present

if set_d == set('0123456789'):

yield sum(sql), sql

else:

# add another square

for i, s in enumerate(sq):

# check it adds only digits not already present

if not set_d or not set_d.intersection(str(s)):

# continue to add more squares if possible

yield from find1(sq[i:], set_d.union(str(s)), sql + [s])

# find combinations of squares that use all the digits

# 0 .. 9 at least one and whose sum is less than some

# given maximum value (sq: list of squares to try;

# sum_sq_max: max sum of squares; rec: record minimum

# sum; set_d: digits seen so far; sql: squares used)

def find2(sq, sum_sq_max, set_d=set(), sql=[]):

# compute the limit for remaining squares

sq_lim = sum_sq_max - sum(sql)

if sq_lim > 0:

# are all digits present

if set_d == set('0123456789'):

yield sum(sql), sql

# can we add another square?

if sq and sq[0] < sq_lim:

# consider each square that we can add

for i in range(bisect(sq, sq_lim)):

yield from find2(sq[i + 1:], sum_sq_max,

set_d.union(str(sq[i])), sql + [sq[i]])

# squares less than 50^2, those less than 50^2 without

# duplicated digits

sq1 = [x * x for x in range(1, 50)]

sq2 = [x for x in sq1 if len(str(x)) == len(set(str(x)))]

# squares less than 29^2

sq3 = [x * x for x in range(1, 29)]

# the possible lists for Wunce

for birth_year, sq_seq in find1(sq2):

# birth year must be in or before the publication year

if birth_year <= 2016:

print("Wunce's sum is {} {}".format(birth_year, sq_seq))

# now consider Repete's list for ages in 2018

age = 2018 - birth_year

sq3 = [x * x for x in range(1, age)]

for sm, seq in find2(sq3, age ** 2):

print("Repete's sum is {} {}".format(sm, seq))

Jim Randell permalink

I’ve used the following clarifications to give a unique solution to this puzzle:

1. the puzzle is set on/after the twins birthday in 2018;
2. the lists are of *different* squares;
3. the squares are greater than 1

With these clarifications this Python 3 program finds the solution in 281ms.


from enigma import irange, isqrt, filter2, is_duplicate, subsets, arg, printf

# Y = year the puzzle is set (which apparently should be 2018)
Y = arg(2018, 0, int)
# m = minimum allowable square (the root of the square is used)
m = arg(2, 1, int)
printf("[Y = {Y}, m={m}]")

# squares (as strings)
(_, squares) = filter2(is_duplicate, (str(i * i) for i in irange(m, isqrt(Y))))

# for Wunce find a pan-digital subset (without repeated digits)
# ss = squares to consider
# s = squares used so far
# ds = digits used so far
def solve1(ss, s=[], ds=set()):
  # are we done?
  if len(ds) == 10:
    yield s
  else:
    # chose the next element
    for (i, x) in enumerate(ss):
      if ds.intersection(x): continue
      yield from solve1(ss[i + 1:], s + [x], ds.union(x))

# for Repete find a pan-digital set of squares (allowing repeated digits)
# below a given total
# n = largest square to consider
# t = sum of squares must be less than this
# s = squares used so far
# ds = digits used so far
def solve2(n, t, s=[], ds=set()):
  # are we done?
  if len(ds) == 10:
    yield s
  # choose the next element
  for i in irange(n, m, step=-1):
    i2 = i * i
    if i2 < t:
      yield from solve2(i - 1, t - i2, s + [i2], ds.union(str(i2)))

# find sequences for Wunce
for s1 in solve1(squares):
  s1 = list(int(x) for x in s1)
  t1 = sum(s1)
  printf("Wunce: total = {t1}, squares = {s1}")

  # calculate the age
  age = Y - t1
  age2 = age * age
  printf("age = {age}, age^2 = {age2}")

  # find sequences for Repete
  for s2 in solve2(age - 1, age2):
    t2 = sum(s2)
    printf("Repete: total = {t2}, squares = {s2}")

from enigma import irange, isqrt, filter2, is_duplicate, subsets, arg, printf

# Y = year the puzzle is set (which apparently should be 2018)

Y = arg(2018, 0, int)

# m = minimum allowable square (the root of the square is used)

m = arg(2, 1, int)

printf("[Y = {Y}, m={m}]")

# squares (as strings)

(_, squares) = filter2(is_duplicate, (str(i * i) for i in irange(m, isqrt(Y))))

# for Wunce find a pan-digital subset (without repeated digits)

# ss = squares to consider

# s = squares used so far

# ds = digits used so far

def solve1(ss, s=[], ds=set()):

# are we done?

if len(ds) == 10:

yield s

else:

# chose the next element

for (i, x) in enumerate(ss):

if ds.intersection(x): continue

yield from solve1(ss[i + 1:], s + [x], ds.union(x))

# for Repete find a pan-digital set of squares (allowing repeated digits)

# below a given total

# n = largest square to consider

# t = sum of squares must be less than this

# s = squares used so far

# ds = digits used so far

def solve2(n, t, s=[], ds=set()):

# are we done?

if len(ds) == 10:

yield s

# choose the next element

for i in irange(n, m, step=-1):

i2 = i * i

if i2 < t:

yield from solve2(i - 1, t - i2, s + [i2], ds.union(str(i2)))

# find sequences for Wunce

for s1 in solve1(squares):

s1 = list(int(x) for x in s1)

t1 = sum(s1)

printf("Wunce: total = {t1}, squares = {s1}")

# calculate the age

age = Y - t1

age2 = age * age

printf("age = {age}, age^2 = {age2}")

# find sequences for Repete

for s2 in solve2(age - 1, age2):

t2 = sum(s2)

printf("Repete: total = {t2}, squares = {s2}")

The year (Y) and minimum value to be squared (m) can be specified on the command line.

If m=1 is specified there is an additional solution for Repete.

Another way to fix the puzzle is to specify that the digits in Repete’s list appear either once or twice, but that requires code changes to implement.

As usual, the latest version of the enigma.py library is available at [ https://www.magwag.plus.com/jim/enigma.html ].

Sunday Times Teaser 2825 – Twin Sets

by Victor Bryant

Published: 13 November 2016 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta