Sunday Times Teaser 2997 – Cemetery Lottery Symmetry

by Stephen Hogg

Published Sunday March 01 2020 (link)

Our local cemetery conservation lottery tickets have four numbers for a line. Using eight different numbers, my two lines have several symmetries. For each line: just one number is odd; there is one number from each of the ranges 1-9, 10-19, 20-29 and 30-39, in that order; the sum of the four numbers equals that sum for the other line; excluding 1 and the numbers themselves, the 1st and 2nd numbers share just one factor — as do the 2nd and 3rd (a different factor) and the 3rd and 4th (another different factor) and, finally, the 4th and 1st.

Printed one line directly above the other, my top line includes the largest of the eight numbers.

What is the bottom line?

One Comment Leave one →

Brian Gladman permalink

I originally thought that this might be possible by showing that the Greatest Common Divisor (GCD) of adjacent numbers on a line was prime but it turns out that the teaser constraints make this a bit more complicated since prime powers have to be checked as well. So I moved to a solution based on the divisors of the numbers. There is also a potential confusion in the use of the term ‘factor’ since there is a concern about whether this means any factor or only prime factors. Nevertheless the solution is fairly straightforward and this program finds it in less than 3 milliseconds.


from itertools import combinations, product 
from collections import defaultdict

# return the divisors of <n> in the range 2 .. n - 1
def divs(n):
  return set(d for d in range(2, n) if n % d == 0)

# if there is a single shared divisor of <m> and <n>
# return it, otherwise return None
def sh_div(m, n):
  f = divs(m) & divs(n)
  return f.pop() if len(f) == 1 else None 

# collect 4-tuples of numbers indexed on their sum
sm2t = defaultdict(list)

# find the possible first two numbers that share a single divisor
for a, b in product(range(1, 10), range(10, 20)):
  if (ab := sh_div(a, b)):
    
    # find possible third numbers that share a (different) 
    # single divisor with the second number  
    for c in range(20, 30):
      if (bc := sh_div(b, c)) and bc != ab:
        
        # and possible fourth numbers that share a (different 
        # again) single divisor with the third number
        for d in range(30, 40):
          if (cd := sh_div(c, d)) and cd not in {ab, bc}:
            
            # the shared divisor between the fourth and the first
            # numbers does not have to be different
            if sh_div(d, a):
              # collect 4-tuples with only one odd number
              t = (a, b, c, d)
              if sum(x & 1 for x in t) == 1:
                sm2t[sum(t)].append(t)

for k, v in sm2t.items():
  # find two pairs of four numbers (ordered on their last number) 
  # with eight different numbers
  for u, v in combinations(sorted(v, key=lambda x:x[3]), 2):
    if len(set(u + v)) == 8:
      print(f"bottom line {u}, top line {v}")

from itertools import combinations, product

from collections import defaultdict

# return the divisors of <n> in the range 2 .. n - 1

def divs(n):

return set(d for d in range(2, n) if n % d == 0)

# if there is a single shared divisor of <m> and <n>

# return it, otherwise return None

def sh_div(m, n):

f = divs(m) & divs(n)

return f.pop() if len(f) == 1 else None

# collect 4-tuples of numbers indexed on their sum

sm2t = defaultdict(list)

# find the possible first two numbers that share a single divisor

for a, b in product(range(1, 10), range(10, 20)):

if (ab := sh_div(a, b)):

# find possible third numbers that share a (different)

# single divisor with the second number

for c in range(20, 30):

if (bc := sh_div(b, c)) and bc != ab:

# and possible fourth numbers that share a (different

# again) single divisor with the third number

for d in range(30, 40):

if (cd := sh_div(c, d)) and cd not in {ab, bc}:

# the shared divisor between the fourth and the first

# numbers does not have to be different

if sh_div(d, a):

# collect 4-tuples with only one odd number

t = (a, b, c, d)

if sum(x & 1 for x in t) == 1:

sm2t[sum(t)].append(t)

for k, v in sm2t.items():

# find two pairs of four numbers (ordered on their last number)

# with eight different numbers

for u, v in combinations(sorted(v, key=lambda x:x[3]), 2):

if len(set(u + v)) == 8:

print(f"bottom line {u}, top line {v}")

Sunday Times Teaser 2997 – Cemetery Lottery Symmetry

by Stephen Hogg

Published Sunday March 01 2020 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta