Sunday Times Teaser 2947 – 55 Divisions

by Tom Wills-Sandford

Published March 17 2019 (link)

To mark her 55th birthday, Martha, a school teacher, gave each of her nine pupils a sheet of paper with a single different digit from 1 to 9 written on it.

They stood at the front of the classroom in a row and the 9-digit number on display was divisible by 55. Martha then asked the first 3 in the row (from the left) to sit down. The remaining 6-digit number was also divisible by 55. The next 3 then sat down and the remaining 3-digit number was also divisible by 55.

The 9 digit number was the smallest possible. What was it?

6 Comments Leave one →

Brian Gladman permalink


from itertools import permutations
        
def find_it():
  # consider the three right hand digits
  s1 = set(range(1, 10))
  for a, b, c in permutations(s1, 3):
    n3 = 100 * a + 10 * b + c
    if n3 % 55 == 0:
      
      # ... then the three middle digits
      s2 = s1.difference((a, b, c))
      for d, e, f in permutations(s2, 3):
        n2 = 100 * d + 10 * e + f
        if n2 % 11 == 0:
          
          # ... and finally the three left hand digits
          for g, h, i in permutations(s2.difference((d, e, f))):
            n1 = 100 * g + 10 * h + i
            if n1 % 11 == 0:
              
              # return the value found
              yield 1000 * (1000 * n1 + n2) + n3
              
print(f"The number is {min(find_it()):,}.")

from itertools import permutations

def find_it():

# consider the three right hand digits

s1 = set(range(1, 10))

for a, b, c in permutations(s1, 3):

n3 = 100 * a + 10 * b + c

if n3 % 55 == 0:

# ... then the three middle digits

s2 = s1.difference((a, b, c))

for d, e, f in permutations(s2, 3):

n2 = 100 * d + 10 * e + f

if n2 % 11 == 0:

# ... and finally the three left hand digits

for g, h, i in permutations(s2.difference((d, e, f))):

n1 = 100 * g + 10 * h + i

if n1 % 11 == 0:

# return the value found

yield 1000 * (1000 * n1 + n2) + n3

print(f"The number is {min(find_it()):,}.")

Erling Torkildsen permalink

Thanks Brian

My ambition was to engage Python’s new data types such as ‘lists’ and ‘sets’ rather than use traditional arrays. Apart from traces left from struggling with the different types of data and their methods and functions and thereby unnecessary conversions from one to the other, I feel that I started out well, but in the latter part fell back to relaying on extremely inefficient loops.

I am prepared to upload my script, but don’t know quite how to do it..

Reply
- Brian Gladman permalink
  
  Hi Erling, The way to upload Python programs is explained on the about page above.
  
  Reply

Erling Torkildsen permalink


from itertools import permutations

all = set(range(1, 10))
l_s = list()         # To hold the least significant digits as 3-tuples 
m_s = list()         # To hold the rest of the usable 3-tuples for 
solutions = list()

all = set(range(1, 10))

# Set up a list, p, of all possible 3-tuples made from '123456789'
p = list(permutations(all, 3))

# Pick all 3-tuples divisible by 11 and not containing 5, in the list m_s
for x in p:
  if (x[0] * 100 + x[1] * 10 + x[2]) % 11 == 0 and 5 not in x:
    m_s.append(x)

# Store all candidates for the least significant three digits in l_s
for x in p:
  if (x[0] * 100 + x[1] * 10 + x[2]) % 11 == 0 and x[2] == 5:
    l_s.append(x)

# Counting loop-collecting possible solutions by inspection.
antall = 0
for l in l_s:
  for m in m_s:
    for n in m_s:
      if (len(set(l).intersection(set(m))) == 0 and 
               len(set(l).intersection(set(n))) == 0 and 
                    len(set(m).intersection(set(n))) == 0):
        antall = antall + 1
        # Collecting the solutions as strings enabling spaces 
        # as 'thousand separator'
        solutions.append([str(n[0]) + str(n[1]) + str(n[2]) + " " 
                        + str(m[0]) + str(m[1]) + str(m[2]) + " " 
                        + str(l[0]) + str(l[1]) + str(l[2])])

# Sort, and print the smallest solution.            
solutions.sort()
print(f"Of {antall} solutions {solutions[0][0]} is the smallest.")

from itertools import permutations

all = set(range(1, 10))

l_s = list() # To hold the least significant digits as 3-tuples

m_s = list() # To hold the rest of the usable 3-tuples for

solutions = list()

all = set(range(1, 10))

# Set up a list, p, of all possible 3-tuples made from '123456789'

p = list(permutations(all, 3))

# Pick all 3-tuples divisible by 11 and not containing 5, in the list m_s

for x in p:

if (x[0] * 100 + x[1] * 10 + x[2]) % 11 == 0 and 5 not in x:

m_s.append(x)

# Store all candidates for the least significant three digits in l_s

for x in p:

if (x[0] * 100 + x[1] * 10 + x[2]) % 11 == 0 and x[2] == 5:

l_s.append(x)

# Counting loop-collecting possible solutions by inspection.

antall = 0

for l in l_s:

for m in m_s:

for n in m_s:

if (len(set(l).intersection(set(m))) == 0 and

len(set(l).intersection(set(n))) == 0 and

len(set(m).intersection(set(n))) == 0):

antall = antall + 1

# Collecting the solutions as strings enabling spaces

# as 'thousand separator'

solutions.append([str(n[0]) + str(n[1]) + str(n[2]) + " "

+ str(m[0]) + str(m[1]) + str(m[2]) + " "

+ str(l[0]) + str(l[1]) + str(l[2])])

# Sort, and print the smallest solution.

solutions.sort()

print(f"Of {antall} solutions {solutions[0][0]} is the smallest.")

Brian Gladman permalink

HI Erling, I hope you don’t mind but I have adjusted it a bit so that it fits between the margins without scrolling.

Reply

GeoffR permalink


from itertools import permutations

digits = set('123456789')
list9 = []

# 9 digit number is abcDEFghi

# 1st stage permutation - for last 3 digits
for p1 in permutations (digits, 3):                       
  g, h, i = p1
  ghi = int(g + h + i)
  if ghi % 55 != 0: continue

  # 2nd stage permutation - for middle 3 digits
  qs = digits.difference(p1)
  for p2 in permutations(qs, 3):
    D, E, F = p2
    DEFghi = int(D + E + F + g + h + i)
    if DEFghi % 55 != 0: continue

    # 3rd stage permutation  - for first 3 digits
    qs2 = qs.difference(p2)
    for p3 in permutations(qs2,3):
      a, b, c = p3
      abcDEFghi = int(a + b + c + D + E + F + g + h + i)
      if abcDEFghi % 55 == 0:
        list9.append(abcDEFghi)

print(f"9 digit number was {min(list9)}")

from itertools import permutations

digits = set('123456789')

list9 = []

# 9 digit number is abcDEFghi

# 1st stage permutation - for last 3 digits

for p1 in permutations (digits, 3):

g, h, i = p1

ghi = int(g + h + i)

if ghi % 55 != 0: continue

# 2nd stage permutation - for middle 3 digits

qs = digits.difference(p1)

for p2 in permutations(qs, 3):

D, E, F = p2

DEFghi = int(D + E + F + g + h + i)

if DEFghi % 55 != 0: continue

# 3rd stage permutation - for first 3 digits

qs2 = qs.difference(p2)

for p3 in permutations(qs2,3):

a, b, c = p3

abcDEFghi = int(a + b + c + D + E + F + g + h + i)

if abcDEFghi % 55 == 0:

list9.append(abcDEFghi)

print(f"9 digit number was {min(list9)}")

Sunday Times Teaser 2947 – 55 Divisions

by Tom Wills-Sandford

Published March 17 2019 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta