Sunday Times Teaser 3080 – One of a Kind

by BRG on October 1, 2021

by Andrew Skidmore

Published Sunday October 03 2021

The raffle tickets at the Mathematical Society Dinner were numbered from 1 to 1000. There were four winning tickets and together they used each of the digits from 0 to 9 once only. The winning numbers could be classified uniquely as one square, one cube, one prime and one triangular number. For example, 36 is a triangular number as 1+2+3+4+5+6+7+8 = 36, but it cannot be a winner as 36 is also a square. The tickets were all sold in strips of five, and two of the winning numbers were from consecutive strips. The first prize was won by the holder of the smallest-numbered winning ticket, which was not a cube.

List the four winning numbers in ascending order.

From → Uncategorized

5 Comments Leave one →

Brian Gladman permalink


from itertools import permutations

# primes less than 1000
pr = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}
pr |= set(x for x in range(33, 1000, 2) if all(x % p for p in pr))

trf = lambda x : x * (x + 1) // 2
# cubes, squares and triangular numbers less than 1000 with no duplicate digits
cb = set(r for x in range(1, 10) if (r := str(x ** 3)) if len(r) == len(set(r)))
sq = set(r for x in range(1, 32) if (r := str(x ** 2)) if len(r) == len(set(r)))
tr = set(r for x in range(1, 45) if (r := str(trf(x))) if len(r) == len(set(r)))

# consider possible cubes
for c in cb:  
  # consider possible squares 
  
  for s in sq:
    # that don't share digits with cubes
    if set(c).intersection(s):
      continue
    
    # consider possible triangular numbers
    for t in tr:
      # that don't share digits with cubes or squares
      if set(c + s).intersection(t):
        continue
      
      # find the (so far) unused digits (three or less)
      rd = set('0123456789').difference(c + s + t)
      if len(rd) > 3:
        continue
      
      # consider possible primes with these digits
      for ps in permutations(rd):
        p = ''.join(ps)
        if p[0] == '0' or int(p) not in pr:
          continue
        
        # find the strip numbers of the four tickets (two of
        # which must be in adjacent strips)
        sns = sorted((int(x) - 1) // 5 for x in (c, s, t, p))
        if all(sns[i + 1] - sns[i] != 1 for i in range(3)):
          continue

        # make sure that the sequence can be classified uniquely         
        if any(sum(i in x for x in (cb, sq, tr, pr)) > 1 
                        for i in (c, s, t, p)):
          continue

        # find the winning ticket which must not be a cube
        wnr = min((x for x in (c, s, t, p)), key=int)
        if wnr not in cb:

          w4 = sorted([(int(c), 'cube'), (int(s), 'square'), 
                         (int(t), 'triangular'), (int(p), 'prime')])
          print(f"{', '.join(f'{x[0]} ({x[1]})' for x in w4)}.")

from itertools import permutations

# primes less than 1000

pr = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}

pr |= set(x for x in range(33, 1000, 2) if all(x % p for p in pr))

trf = lambda x : x * (x + 1) // 2

# cubes, squares and triangular numbers less than 1000 with no duplicate digits

cb = set(r for x in range(1, 10) if (r := str(x ** 3)) if len(r) == len(set(r)))

sq = set(r for x in range(1, 32) if (r := str(x ** 2)) if len(r) == len(set(r)))

tr = set(r for x in range(1, 45) if (r := str(trf(x))) if len(r) == len(set(r)))

# consider possible cubes

for c in cb:

# consider possible squares

for s in sq:

# that don't share digits with cubes

if set(c).intersection(s):

continue

# consider possible triangular numbers

for t in tr:

# that don't share digits with cubes or squares

if set(c + s).intersection(t):

continue

# find the (so far) unused digits (three or less)

rd = set('0123456789').difference(c + s + t)

if len(rd) > 3:

continue

# consider possible primes with these digits

for ps in permutations(rd):

p = ''.join(ps)

if p[0] == '0' or int(p) not in pr:

continue

# find the strip numbers of the four tickets (two of

# which must be in adjacent strips)

sns = sorted((int(x) - 1) // 5 for x in (c, s, t, p))

if all(sns[i + 1] - sns[i] != 1 for i in range(3)):

continue

# make sure that the sequence can be classified uniquely

if any(sum(i in x for x in (cb, sq, tr, pr)) > 1

for i in (c, s, t, p)):

continue

# find the winning ticket which must not be a cube

wnr = min((x for x in (c, s, t, p)), key=int)

if wnr not in cb:

w4 = sorted([(int(c), 'cube'), (int(s), 'square'),

(int(t), 'triangular'), (int(p), 'prime')])

print(f"{', '.join(f'{x[0]} ({x[1]})' for x in w4)}.")

Frits permalink

@Brian,

Nice and fast code, but you have interpreted “classified uniquely” differently as I would have thought. Fi, you don’t seem to dismiss c = 64 (as it is a square as well).

Reply
- Brian Gladman permalink
  
  @Frits
  
  I didn’t interpret it at all as I wasn’t sure what it meant. So I proceeded without it and found that it wasn’t needed in finding the solution. But I have now added a test for the sake of completeness.
  
  Reply

Frits permalink

Starting with consecutive strip logic.


from itertools import permutations as perm

digits = set("0123456789")

squares = set(i2 for i in range(1, 32)
              if len(str(i2 := i ** 2)) == len(set(str(i2))))
# as smallest ticket may not be a cube start with 27
cubes = set(i3 for i in range(3, 11)
            if len(str(i3 := i ** 3)) == len(set(str(i3))))
tris = set(t for i in range(1, 45)
           if len(str(t := (i * (i + 1)) // 2)) == len(set(str(t))))

# set of prime numbers up to 1000
P = {2, 3, 5, 7}
P |= {x for x in range(11, 33, 2) if all(x % p for p in P)}
P |= {x for x in range(33, 1000, 2) if all(x % p for p in P)}
P = set(i for i in P if len(str(i)) == len(set(str(i))))

mat = [[]] * 4
# build list of "classified uniquely" numbers
for n in range(1, 1000):
  # skip numbers with duplicate digits
  if len(set(str(n))) != len(str(n)): continue
  cnt = 0
  for i, y in enumerate([squares, cubes, tris, P]):
    if n in y:
      cnt += 1
      i1 = i
  # classified uniquely?
  if cnt == 1:
    mat[i1] = mat[i1] + [n]

# determine digits that occur in all cubes
mand_dgts = set(str(mat[1][0]))
for c in mat[1][1:]:
  mand_dgts &= set(str(c))

# remove non-cube entries which use digits that occur in all cubes
for y in [0, 2, 3]:
  mat[y] = [x for x in mat[y] if all(c not in str(x) for c in mand_dgts)]

# flatten the mat list
flat = sorted((x, i) for i in range(4) for x in mat[i])
lngth = len(flat)

# check if two numbers x1 and x2 are on consecutive strips
for i, (x1, y1) in enumerate(flat[:-1]):
  nxt = (x1 - 1) // 5 + 1  # next expected adjacent strip number
  j = 1
  # loop until there is a gap in strip numbers
  while j < lngth - i:
    x2 = flat[i + j][0]
    y2 = flat[i + j][1]
    j += 1

    s = str(x1) + str(x2)
    ls = len(s)

    stripno = (x2 - 1) // 5
    if y1 == y2 or ls < 4 or ls != len(set(s)) or stripno < nxt:
      continue

    # gap in strip numbers?
    if stripno > nxt: break

    rest_num = digits.difference(s)
    rest_typ = list({0, 1, 2, 3}.difference({y1, y2}))
    minx = 10 ** (len(rest_num) - 4)

    # look for numbers x3 and x4 which complement x1 and x2

    # for first missing type determine x3 candidates
    cands1 = sorted((x, "".join(rest_num.difference(str(x))))
                    for x in mat[rest_typ[0]] if x >= minx and
                    all(y in rest_num for y in str(x)))
    if not cands1: break

    # for each x3 candidate check if remaining digits form into the 4th type
    prev = set()
    ans = []
    for x3, t in cands1:
      # skip if we already have checked the same permutations
      if set(t) == prev and not ans: continue
      prev = set(t)

      for p in perm(t):
        if p[0] == '0': continue
        x4 = int("".join(p))
        if x4 in mat[rest_typ[1]]:
          ans = sorted([x1, x2, x3, x4])
          # the minimum is not a cube
          if ans[0] not in cubes:
            print("answer:", ans)
          else:
            ans = []

from itertools import permutations as perm

digits = set("0123456789")

squares = set(i2 for i in range(1, 32)

if len(str(i2 := i ** 2)) == len(set(str(i2))))

# as smallest ticket may not be a cube start with 27

cubes = set(i3 for i in range(3, 11)

if len(str(i3 := i ** 3)) == len(set(str(i3))))

tris = set(t for i in range(1, 45)

if len(str(t := (i * (i + 1)) // 2)) == len(set(str(t))))

# set of prime numbers up to 1000

P = {2, 3, 5, 7}

P |= {x for x in range(11, 33, 2) if all(x % p for p in P)}

P |= {x for x in range(33, 1000, 2) if all(x % p for p in P)}

P = set(i for i in P if len(str(i)) == len(set(str(i))))

mat = [[]] * 4

# build list of "classified uniquely" numbers

for n in range(1, 1000):

# skip numbers with duplicate digits

if len(set(str(n))) != len(str(n)): continue

cnt = 0

for i, y in enumerate([squares, cubes, tris, P]):

if n in y:

cnt += 1

i1 = i

# classified uniquely?

if cnt == 1:

mat[i1] = mat[i1] + [n]

# determine digits that occur in all cubes

mand_dgts = set(str(mat[1][0]))

for c in mat[1][1:]:

mand_dgts &= set(str(c))

# remove non-cube entries which use digits that occur in all cubes

for y in [0, 2, 3]:

mat[y] = [x for x in mat[y] if all(c not in str(x) for c in mand_dgts)]

# flatten the mat list

flat = sorted((x, i) for i in range(4) for x in mat[i])

lngth = len(flat)

# check if two numbers x1 and x2 are on consecutive strips

for i, (x1, y1) in enumerate(flat[:-1]):

nxt = (x1 - 1) // 5 + 1 # next expected adjacent strip number

j = 1

# loop until there is a gap in strip numbers

while j < lngth - i:

x2 = flat[i + j][0]

y2 = flat[i + j][1]

j += 1

s = str(x1) + str(x2)

ls = len(s)

stripno = (x2 - 1) // 5

if y1 == y2 or ls < 4 or ls != len(set(s)) or stripno < nxt:

continue

# gap in strip numbers?

if stripno > nxt: break

rest_num = digits.difference(s)

rest_typ = list({0, 1, 2, 3}.difference({y1, y2}))

minx = 10 ** (len(rest_num) - 4)

# look for numbers x3 and x4 which complement x1 and x2

# for first missing type determine x3 candidates

cands1 = sorted((x, "".join(rest_num.difference(str(x))))

for x in mat[rest_typ[0]] if x >= minx and

all(y in rest_num for y in str(x)))

if not cands1: break

# for each x3 candidate check if remaining digits form into the 4th type

prev = set()

ans = []

for x3, t in cands1:

# skip if we already have checked the same permutations

if set(t) == prev and not ans: continue

prev = set(t)

for p in perm(t):

if p[0] == '0': continue

x4 = int("".join(p))

if x4 in mat[rest_typ[1]]:

ans = sorted([x1, x2, x3, x4])

# the minimum is not a cube

if ans[0] not in cubes:

print("answer:", ans)

else:

ans = []

Frits permalink


squares = [i2 for i in range(1, 32)
              if len(str(i2 := i ** 2)) == len(set(str(i2)))]
# as smallest ticket may not be a cube start with 27
cubes = [i3 for i in range(3, 11)
            if len(str(i3 := i ** 3)) == len(set(str(i3)))]
tris = [t for i in range(1, 45)
           if len(str(t := (i * (i + 1)) // 2)) == len(set(str(t)))]

# set of prime numbers up to 1000
P = {2, 3, 5, 7}
P |= {x for x in range(11, 33, 2) if all(x % p for p in P)}
P |= {x for x in range(33, 1000, 2) if all(x % p for p in P)}
P = set(i for i in P if len(str(i)) == len(set(str(i))))

mat = [[] for _ in range(4)]
# built list of "classified uniquely" numbers
for n in range(1, 1000):
  # skip numbers with duplicate digits
  if len(set(str(n))) != len(str(n)): continue
  cnt = 0
  for i, y in enumerate([P, tris, cubes, squares]):
    if n in y:
      cnt += 1
      i1 = i
  if cnt == 1:
    mat[i1] += [n]

# two ticket numbers must be in adjacent strips
def consecutive(li):
  strips = [(x + 4) // 5 for x in li]
  if any(strips[i + 1] == strips[i] + 1 for i in range(3)):
    return True
  return False

minlen = [7, 4, 1, 0]

# pick one element from each row of matrix <mat> so that all selected numbers
# use exactly 10 digits (which must be different as well)
def pickFromEachRow(k, m, s=[]):
  if k == -1:
    if len("".join(str(x) for x in s)) == 10:
      yield sorted(s)
  else:
    ss = "".join(str(x) for x in s)
    len_ss = len(ss)
    if len_ss >= minlen[k]:
      for i in m[k]:
        if len_ss + len(str(i)) == len(set(ss + str(i))):
          yield from pickFromEachRow(k - 1, m, s + [i])

for p in pickFromEachRow(len(mat) - 1, mat):
  # smallest ticket may not be a cube and
  # two ticket numbers must be in adjacent strips
  if p[0] not in cubes and consecutive(p):
    print("answer:", p)

squares = [i2 for i in range(1, 32)

if len(str(i2 := i ** 2)) == len(set(str(i2)))]

# as smallest ticket may not be a cube start with 27

cubes = [i3 for i in range(3, 11)

if len(str(i3 := i ** 3)) == len(set(str(i3)))]

tris = [t for i in range(1, 45)

if len(str(t := (i * (i + 1)) // 2)) == len(set(str(t)))]

# set of prime numbers up to 1000

P = {2, 3, 5, 7}

P |= {x for x in range(11, 33, 2) if all(x % p for p in P)}

P |= {x for x in range(33, 1000, 2) if all(x % p for p in P)}

P = set(i for i in P if len(str(i)) == len(set(str(i))))

mat = [[] for _ in range(4)]

# built list of "classified uniquely" numbers

for n in range(1, 1000):

# skip numbers with duplicate digits

if len(set(str(n))) != len(str(n)): continue

cnt = 0

for i, y in enumerate([P, tris, cubes, squares]):

if n in y:

cnt += 1

i1 = i

if cnt == 1:

mat[i1] += [n]

# two ticket numbers must be in adjacent strips

def consecutive(li):

strips = [(x + 4) // 5 for x in li]

if any(strips[i + 1] == strips[i] + 1 for i in range(3)):

return True

return False

minlen = [7, 4, 1, 0]

# pick one element from each row of matrix <mat> so that all selected numbers

# use exactly 10 digits (which must be different as well)

def pickFromEachRow(k, m, s=[]):

if k == -1:

if len("".join(str(x) for x in s)) == 10:

yield sorted(s)

else:

ss = "".join(str(x) for x in s)

len_ss = len(ss)

if len_ss >= minlen[k]:

for i in m[k]:

if len_ss + len(str(i)) == len(set(ss + str(i))):

yield from pickFromEachRow(k - 1, m, s + [i])

for p in pickFromEachRow(len(mat) - 1, mat):

# smallest ticket may not be a cube and

# two ticket numbers must be in adjacent strips

if p[0] not in cubes and consecutive(p):

print("answer:", p)

Sunday Times Teaser 3080 – One of a Kind

by Andrew Skidmore

Published Sunday October 03 2021

Leave a comment to Frits Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta