Sunday Times Teaser 2817 – Our Secret

by Victor Bryant

Published: 18 September 2016

Eight friends joined a very secret society and each was given a different membership number between 70 and 100. The friends are Bec, Cal, Doc, Ian, Jon, Luv, Rev and one other – and I am not willing to divulge his common three-letter name. But I can tell you that his membership number is 84. Also, Bec’s membership number is the highest of the eight. The friends noticed that, for any pair of them, their names had at least one letter in common if and only if their membership numbers had a common prime factor.

(a) What was Ian’s membership number?

(b) What was the name of the eighth friend?

7 Comments Leave one →

Brian Gladman permalink

My first fully programmed solution of this teaser was close to Jim’s below but my manual exploration revealed the possibility for a one-to-one mapping from shared letters to shared primes, so I looked for a solution that exploited such a relationship. This is the same approach as that used by Arthur below and turns out to be faster, although a lot longer, than my first solution.


from collections import defaultdict
from itertools import combinations, permutations, product
from operator import and_
from functools import reduce
from number_theory import factors

# the seven known names
names = ('bec', 'cal', 'doc', 'ian', 'jon', 'luv', 'rev')

# Each pair of names has one shared letter and each name has either
# two or three letters shared with other names.   In order to match
# this structure with the membership numbers,  each pair of numbers
# must have only one shared prime factor and each number must share
# two or three prime factors with other numbers

# the membership number for the unknown member
unk_no = 84

# map letters to the sets of names that contain them
l2n = defaultdict(set)
for name in names:
  for ltr in name:
    l2n[ltr].add(name)

# map letters that appear in two or more names to the sets of names
# that contain them (this gives a map with seven entries)
l2nm = {k:v for k, v in l2n.items() if len(v) > 1}

# for numbers in the range 70 to 100 inclusive that are the product
# of two or more primes, map the numbers to their prime factors and
# map the prime factors to the numbers for which they are factors 
# (this also gives a map with seven entries, allowing a one-to-one
# mapping from letters to prime factors)
n2p, p2n = dict(), defaultdict(set)
for nbr in range(70, 101):
  f = set(factors(nbr))
  if len(f) > 1:
    n2p[nbr] = f
    for p in f:
      p2n[p].add(nbr)
p2n = {p:ln for p, ln in p2n.items() if len(ln) > 1}

# for each pair or triplet of primes, find membership numbers that
# have these primes as factors but which do not have any of the 
# other primes as factors
pt2n = defaultdict(set)
for np in (2, 3):
  # try all combinations of this number of primes
  for t in combinations(sorted(p2n.keys()), np):
    # for numbers with these prime factors 
    for n in reduce(and_, (p2n[x] for x in t)):
      # retain only those that have no other primes as factors
      if all(n % p for p in p2n if p not in t):
        pt2n[t].add(n)

# consider all possible mappings from letters to primes
for p7 in permutations(p2n):
  l2p = dict(zip(l2nm, p7))
  # find the possible sets of seven numbers for the seven names
  for n7 in product(*(pt2n[tuple(sorted([l2p[x] 
              for x in set(n) & set(l2nm)]))] for n in names)):
    
    # Bec's membership number is the highest
    if n7[0] == max(n7):
      
      # output the mapping from names to membership numbers
      print(', '.join(['{} -> {}'.format(nm.capitalize(), no) 
                       for no, nm in sorted(zip(n7, names))]))
            
      # consider all three letter names formed from all the used letters
      ss = []
      for p in combinations(set(''.join(names)), 3):
        
        # check that this name obeys the rules (shared letters imply shared primes)
        unk = ''.join(sorted(p))
        if all(bool(set(unk).intersection(name)) == bool(n2p[unk_no] & n2p[nbr]) 
                          for name, nbr in zip(names, n7)):
          ss.append("'" + unk + "'")
      f, s, l = (', '.join(ss)).rpartition(', ')
      fs = 'The 8th name is formed from the letters {}'
      print(fs.format(' or '.join((f, l))))

from collections import defaultdict

from itertools import combinations, permutations, product

from operator import and_

from functools import reduce

from number_theory import factors

# the seven known names

names = ('bec', 'cal', 'doc', 'ian', 'jon', 'luv', 'rev')

# Each pair of names has one shared letter and each name has either

# two or three letters shared with other names. In order to match

# this structure with the membership numbers, each pair of numbers

# must have only one shared prime factor and each number must share

# two or three prime factors with other numbers

# the membership number for the unknown member

unk_no = 84

# map letters to the sets of names that contain them

l2n = defaultdict(set)

for name in names:

for ltr in name:

l2n[ltr].add(name)

# map letters that appear in two or more names to the sets of names

# that contain them (this gives a map with seven entries)

l2nm = {k:v for k, v in l2n.items() if len(v) > 1}

# for numbers in the range 70 to 100 inclusive that are the product

# of two or more primes, map the numbers to their prime factors and

# map the prime factors to the numbers for which they are factors

# (this also gives a map with seven entries, allowing a one-to-one

# mapping from letters to prime factors)

n2p, p2n = dict(), defaultdict(set)

for nbr in range(70, 101):

f = set(factors(nbr))

if len(f) > 1:

n2p[nbr] = f

for p in f:

p2n[p].add(nbr)

p2n = {p:ln for p, ln in p2n.items() if len(ln) > 1}

# for each pair or triplet of primes, find membership numbers that

# have these primes as factors but which do not have any of the

# other primes as factors

pt2n = defaultdict(set)

for np in (2, 3):

# try all combinations of this number of primes

for t in combinations(sorted(p2n.keys()), np):

# for numbers with these prime factors

for n in reduce(and_, (p2n[x] for x in t)):

# retain only those that have no other primes as factors

if all(n % p for p in p2n if p not in t):

pt2n[t].add(n)

# consider all possible mappings from letters to primes

for p7 in permutations(p2n):

l2p = dict(zip(l2nm, p7))

# find the possible sets of seven numbers for the seven names

for n7 in product(*(pt2n[tuple(sorted([l2p[x]

for x in set(n) & set(l2nm)]))] for n in names)):

# Bec's membership number is the highest

if n7[0] == max(n7):

# output the mapping from names to membership numbers

print(', '.join(['{} -> {}'.format(nm.capitalize(), no)

for no, nm in sorted(zip(n7, names))]))

# consider all three letter names formed from all the used letters

ss = []

for p in combinations(set(''.join(names)), 3):

# check that this name obeys the rules (shared letters imply shared primes)

unk = ''.join(sorted(p))

if all(bool(set(unk).intersection(name)) == bool(n2p[unk_no] & n2p[nbr])

for name, nbr in zip(names, n7)):

ss.append("'" + unk + "'")

f, s, l = (', '.join(ss)).rpartition(', ')

fs = 'The 8th name is formed from the letters {}'

print(fs.format(' or '.join((f, l))))

Jim Randell permalink

Here’s my solution.

It outputs a list of possible names for the mystery man. You can select the most appropriate.


from itertools import permutations
from enigma import irange, factor, join, update, subsets, cached, printf

factor = cached(factor)

# membership numbers are allocated such that membership numbers share
# factors exactly when the corresponding members names share letters

# number for the mystery man
xxx = 84

# check if <name>, <number> can be added to members in dict <d>
def check(name, number, d):
  ls = set(name)
  fs = set(factor(number))
  return all(bool(ls.intersection(k)) 
                 == bool(fs.intersection(factor(v))) for (k, v) in d.items())

# allocate numbers from <numbers> to the names in <names>
# (the assignment is stored in dictionary <d>)
def allocate(names, numbers, d):
  # are we done?
  if not names:
    yield d
  else:
    # consider the next name
    for (i, n) in enumerate(numbers):
      # check names share letters only when they share factors
      if check(names[0], n, d):
        yield from allocate(names[1:], numbers[:i] + numbers[i + 1:], 
                                                  update(d, [(names[0], n)]))

# choose a number for Bec (the highest number)
for b in irange(85, 100):

  # remaining allowable numbers
  ns = list(irange(70, b - 1))
  if xxx in ns: ns.remove(xxx)

  # allocate numbers for the remaining names
  for d in allocate(['cal', 'doc', 'ian', 'jon', 'luv', 'rev'], 
                                                           ns, { 'bec': b }):

    # output the allocations
    printf("{d}", d=join((join((k, '=', v)) for (k, v) in sorted(d.items(), 
                                           key=lambda x: x[::-1])), sep=' '))

    # find names that match factors with xxx
    fs = set(factor(xxx))
    match = list(k for (k, v) in d.items() if fs.intersection(factor(v)))

    # find three letters that match these names, but not the others
    for ls in subsets(set(join(d.keys())), min_size=1, max_size=3):
      if check(ls, xxx, d):
        ls = join(sorted(ls)).ljust(3, '?')
        names = set(join(s) for s in permutations(ls))
        printf("letters = {ls} -> names = {names}", 
                                         names=join(sorted(names), sep=', '))

from itertools import permutations

from enigma import irange, factor, join, update, subsets, cached, printf

factor = cached(factor)

# membership numbers are allocated such that membership numbers share

# factors exactly when the corresponding members names share letters

# number for the mystery man

xxx = 84

# check if <name>, <number> can be added to members in dict <d>

def check(name, number, d):

ls = set(name)

fs = set(factor(number))

return all(bool(ls.intersection(k))

== bool(fs.intersection(factor(v))) for (k, v) in d.items())

# allocate numbers from <numbers> to the names in <names>

# (the assignment is stored in dictionary <d>)

def allocate(names, numbers, d):

# are we done?

if not names:

yield d

else:

# consider the next name

for (i, n) in enumerate(numbers):

# check names share letters only when they share factors

if check(names[0], n, d):

yield from allocate(names[1:], numbers[:i] + numbers[i + 1:],

update(d, [(names[0], n)]))

# choose a number for Bec (the highest number)

for b in irange(85, 100):

# remaining allowable numbers

ns = list(irange(70, b - 1))

if xxx in ns: ns.remove(xxx)

# allocate numbers for the remaining names

for d in allocate(['cal', 'doc', 'ian', 'jon', 'luv', 'rev'],

ns, { 'bec': b }):

# output the allocations

printf("{d}", d=join((join((k, '=', v)) for (k, v) in sorted(d.items(),

key=lambda x: x[::-1])), sep=' '))

# find names that match factors with xxx

fs = set(factor(xxx))

match = list(k for (k, v) in d.items() if fs.intersection(factor(v)))

# find three letters that match these names, but not the others

for ls in subsets(set(join(d.keys())), min_size=1, max_size=3):

if check(ls, xxx, d):

ls = join(sorted(ls)).ljust(3, '?')

names = set(join(s) for s in permutations(ls))

printf("letters = {ls} -> names = {names}",

names=join(sorted(names), sep=', '))

I used a few useful routines from the enigma.py library [ https://www.magwag.plus.com/jim/enigma.html ]

Arthur Vause permalink

Each pair of the 7 names Bec, Cal, Doc, Ian, Jon, Luv, Rev has at most one letter in common. There are 7 of these letters: v, e, c, l, a, n, o.

Each of the 7 names Bec, Cal, Doc, Ian, Jon, Luv, Rev has a letter in common with at least 2 other names.

The only primes with 2 or more multiples between 70 and 100 are 2, 3, 5, 7, 11, 13, 19.

So we can consider the letters v, e, c, l, a, n, o to be some permutation of 2, 3, 5, 7, 11, 13, 19 and the membership number to be a multiple of the product of the letters v, e, c, l, a, n, o in the name.

For example, bec is a multiple of e * c, and, furthermore, it is co-prime with all the primes 2, 3, 5, 7, 11, 13,19 that are neither e or c.


from itertools import permutations, combinations
from fractions import gcd
from operator import mul

primes = (2,3,5,7,11,13,19)

memnum = {b:[x for x in xrange(b,101,b) if 70<=x and gcd(x,(2*3*5*7*11*13*19)/b)==1]
             for i in (2,3)
             for c in combinations(primes,i)
             for b in [reduce(mul,c,1)]
 }


for v,e,c,l,a,n,o in permutations(primes):
  for bec in memnum[e*c] :
    for cal in memnum[c*a*l]:
      for doc in memnum[o*c]:
        for ian in memnum[a*n]:
          for jon in memnum[o*n]:
            for luv in memnum[l*v]:
              for rev in memnum[e*v]:
                if bec == max((bec,cal,doc,ian,jon,luv,rev)):
                  print "bec,cal,doc,ian,jon,luv,rev :", bec,cal,doc,ian,jon,luv,rev
                  print "v,e,c,l,a,n,o :", v,e,c,l,a,n,o
                  num2letter = {v:'v',e:'e',c:'c',l:'l',a:'a',n:'n',o:'o'}
                  print "eigth friend's name is formed from ", num2letter[2]+num2letter[3]+num2letter[7]

from itertools import permutations, combinations

from fractions import gcd

from operator import mul

primes = (2,3,5,7,11,13,19)

memnum = {b:[x for x in xrange(b,101,b) if 70<=x and gcd(x,(2*3*5*7*11*13*19)/b)==1]

for i in (2,3)

for c in combinations(primes,i)

for b in [reduce(mul,c,1)]

}

for v,e,c,l,a,n,o in permutations(primes):

for bec in memnum[e*c] :

for cal in memnum[c*a*l]:

for doc in memnum[o*c]:

for ian in memnum[a*n]:

for jon in memnum[o*n]:

for luv in memnum[l*v]:

for rev in memnum[e*v]:

if bec == max((bec,cal,doc,ian,jon,luv,rev)):

print "bec,cal,doc,ian,jon,luv,rev :", bec,cal,doc,ian,jon,luv,rev

print "v,e,c,l,a,n,o :", v,e,c,l,a,n,o

num2letter = {v:'v',e:'e',c:'c',l:'l',a:'a',n:'n',o:'o'}

print "eigth friend's name is formed from ", num2letter[2]+num2letter[3]+num2letter[7]

Arthur Vause permalink

However, unlike Jim’s program, mine only finds the eighth friend’s name “Vac”, and fails to find the name “Vic”, which is presumably the name that Victor Bryant intended to be found.

Reply
- geoffrounce permalink
  
  Hi Arthur
  
  I found your programme needs an extra line to run under Python 3
  ( after amending the xrange and print statements)
  
  ie from functools import reduce
  
  Maybe needed for Python 2.7 too?
  
  Geoff
  
  Reply
  - Arthur Vause permalink
    
    Hi Geoff,
    
    Thanks for spotting that. I am using 2.7, which doesn’t need to explicity import reduce, so I hadn’t realised that it wouldn’t run in Python 3.
    
    Arthur
    
    Reply

Brian Gladman permalink

Here is Arthur’s solution in Python 3 with a few tweaks:


from itertools import combinations, permutations, product
from math import gcd
from operator import mul
from functools import reduce
from number_theory import factors

# the seven known names
names = ('bec', 'cal', 'doc', 'ian', 'jon', 'luv', 'rev')

# the membership number for the unknown member
unk_no = 84

# primes to be considered and their product
primes = (2, 3, 5, 7, 11, 13, 19)
prod = reduce(mul, primes)

# a dictionary that maps numbers to their multiples between
# 70 and 100 inclusive that are not also multiples of primes 
# in the above list apart from their own prime factors
memnum = {n:[x for x in range(n, 101, n) 
               if x >= 70 and gcd(x, prod // n) == 1]
            for i in (2, 3)
              for c in combinations(primes, i)
                for n in [reduce(mul, c, 1)]
         } 

# assign primes to the letters a, c, e, l, n, o and v in some order
for p in permutations(primes):
  a, c, e, l, n, o, v = p
  
  # assign numbers to names according to the letters (and hence primes)
  # that they contain
  for q in product(*(memnum[x] for x in 
            (e * c, c * a * l, o * c, a * n, o * n, l * v, e * v))):
    bec, cal, doc, ian, jon, luv, rev = q
    
    # use only solutions where Bec's number is the highest
    if bec == max(q):
      
      # output the assignments of primes to letters 
      print('(a, c, e, l, n, o, v) = {}'.format(p))

      # output the membership numbers for the seven known members
      print('(bec, cal, doc, ian, jon, luv, rev) = {}'.format(q))
           
      # consider all three letter names formed from all the used letters
      ss = []
      for p in combinations(set(''.join(names)), 3):
        
        # check that letters shared with other names imply shared primes
        unk = ''.join(sorted(p))
        if all(bool(set(unk) & set(name)) == 
                  bool(set(factors(unk_no)) & set(factors(nbr))) 
                     for name, nbr in zip(names, q)):
          ss.append("'" + unk + "'")
      f, s, l = (', '.join(ss)).rpartition(', ')
      fs = 'The 8th name is formed from the letters {}'
      print(fs.format(' or '.join((f, l))))

from itertools import combinations, permutations, product

from math import gcd

from operator import mul

from functools import reduce

from number_theory import factors

# the seven known names

names = ('bec', 'cal', 'doc', 'ian', 'jon', 'luv', 'rev')

# the membership number for the unknown member

unk_no = 84

# primes to be considered and their product

primes = (2, 3, 5, 7, 11, 13, 19)

prod = reduce(mul, primes)

# a dictionary that maps numbers to their multiples between

# 70 and 100 inclusive that are not also multiples of primes

# in the above list apart from their own prime factors

memnum = {n:[x for x in range(n, 101, n)

if x >= 70 and gcd(x, prod // n) == 1]

for i in (2, 3)

for c in combinations(primes, i)

for n in [reduce(mul, c, 1)]

}

# assign primes to the letters a, c, e, l, n, o and v in some order

for p in permutations(primes):

a, c, e, l, n, o, v = p

# assign numbers to names according to the letters (and hence primes)

# that they contain

for q in product(*(memnum[x] for x in

(e * c, c * a * l, o * c, a * n, o * n, l * v, e * v))):

bec, cal, doc, ian, jon, luv, rev = q

# use only solutions where Bec's number is the highest

if bec == max(q):

# output the assignments of primes to letters

print('(a, c, e, l, n, o, v) = {}'.format(p))

# output the membership numbers for the seven known members

print('(bec, cal, doc, ian, jon, luv, rev) = {}'.format(q))

# consider all three letter names formed from all the used letters

ss = []

for p in combinations(set(''.join(names)), 3):

# check that letters shared with other names imply shared primes

unk = ''.join(sorted(p))

if all(bool(set(unk) & set(name)) ==

bool(set(factors(unk_no)) & set(factors(nbr)))

for name, nbr in zip(names, q)):

ss.append("'" + unk + "'")

f, s, l = (', '.join(ss)).rpartition(', ')

fs = 'The 8th name is formed from the letters {}'

print(fs.format(' or '.join((f, l))))

Sunday Times Teaser 2817 – Our Secret

by Victor Bryant

Published: 18 September 2016

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta