Sunday Times Teaser 2539 – Doubling Up

by DJT Hogg

Published: 22 May 2011 (link)

One day at school I found myself in charge of two classes. Faced with 64 pupils and only 32 desks, I gave each child a different whole number and told them the highest number must share with the lowest, the second highest with the second lowest, etc. When they had sorted themselves into pairs, I got each child to multiply their own number by that of their desk-mate. They discovered all the products were the same. In fact I chose the original numbers so that this common product would be as low as possible.

What was the common product?

One Comment Leave one →

Brian Gladman permalink


# We need a number with 64 different divisors in order to make 32 pairs
# with the same product. For a number with the prime factorisation:
#
#  n = p[1]^e[1] * p[2]^e[2] * p[3]^ e[3] * ... = product(p[i]^e[i])
#  
# the number of values that divide into it exactly is given by:
#
#  nf = (e[1] + 1) * (e[2] + 1) * (e[3] + 1) * ... = product((e[i] + 1))
#  
# which we want to be 64. Hence: 
#
#  (e[1] + 1) * (e[2] + 1) * (e[3] + 1) *  ... = 64 = 2^6
#
# Since each term is an integer and the right hand side is a power of 
# two, each term must also be a power of 2. So we can find numbers 
# with 64 divisors by partitioning the integer 6 into sets of integers
# (v[1], v[2], ...) and setting:
#
#  e[i] = 2^v[i] - 1
#
# To get the lowest values with this number of divisors we can then
# associate higher e[i] values with lower primes (2, 3, ...).

from functools import reduce
from operator import mul
from itertools import islice
from number_theory import Primes
from math import log2
from sys import argv

# partition an integer into a non increasing list of integers
def int_part(val, seq=[]):
  if not val:
    yield seq
  else:
    for v in range(1, val + 1):
      if not seq or v <= seq[-1]:
        yield from int_part(val - v, seq + [v])

# the number of divisors needed
D = 64 if len(argv) == 1 else int(argv[1])
N = round(log2(D))

# primes to associate with the partitions of the integer 
pr = tuple(islice(Primes().extend(), N))

# list the numbers needed for different partitions of N
vals = []
for v in int_part(N):
  vals.append(reduce(mul, (p ** (2 ** x - 1) for p, x in zip(pr, v))))

# output the minimum value that gives the required number of divisors
print('The common product was {}.'.format(min(vals)))

# We need a number with 64 different divisors in order to make 32 pairs

# with the same product. For a number with the prime factorisation:

# n = p[1]^e[1] * p[2]^e[2] * p[3]^ e[3] * ... = product(p[i]^e[i])

# the number of values that divide into it exactly is given by:

# nf = (e[1] + 1) * (e[2] + 1) * (e[3] + 1) * ... = product((e[i] + 1))

# which we want to be 64. Hence:

# (e[1] + 1) * (e[2] + 1) * (e[3] + 1) * ... = 64 = 2^6

# Since each term is an integer and the right hand side is a power of

# two, each term must also be a power of 2. So we can find numbers

# with 64 divisors by partitioning the integer 6 into sets of integers

# (v[1], v[2], ...) and setting:

# e[i] = 2^v[i] - 1

# To get the lowest values with this number of divisors we can then

# associate higher e[i] values with lower primes (2, 3, ...).

from functools import reduce

from operator import mul

from itertools import islice

from number_theory import Primes

from math import log2

from sys import argv

# partition an integer into a non increasing list of integers

def int_part(val, seq=[]):

if not val:

yield seq

else:

for v in range(1, val + 1):

if not seq or v <= seq[-1]:

yield from int_part(val - v, seq + [v])

# the number of divisors needed

D = 64 if len(argv) == 1 else int(argv[1])

N = round(log2(D))

# primes to associate with the partitions of the integer

pr = tuple(islice(Primes().extend(), N))

# list the numbers needed for different partitions of N

vals = []

for v in int_part(N):

vals.append(reduce(mul, (p ** (2 ** x - 1) for p, x in zip(pr, v))))

# output the minimum value that gives the required number of divisors

print('The common product was {}.'.format(min(vals)))

Sunday Times Teaser 2539 – Doubling Up

by DJT Hogg

Published: 22 May 2011 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta