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 permalink12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455# 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 reducefrom operator import mulfrom itertools import islicefrom number_theory import Primesfrom math import log2from sys import argv# partition an integer into a non increasing list of integersdef int_part(val, seq=[]):if not val:yield seqelse: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 neededD = 64 if len(argv) == 1 else int(argv[1])N = round(log2(D))# primes to associate with the partitions of the integerpr = tuple(islice(Primes().extend(), N))# list the numbers needed for different partitions of Nvals = []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 divisorsprint('The common product was {}.'.format(min(vals)))