Sunday Times Teaser 2580 – Hard Times
by Victor Bryant
Published: 4 March 2012 (link)
| 11 | 22 | 3 | 4 | .. | |
| 1 | 1 | 2 | 3 | 4 | .. |
| 2 | 2 | 4 | 6 | 8 | .. |
| 3 | 3 | 6 | 9 | 12 | .. |
| 4 | 4 | 8 | 12 | 16 | .. |
| : | : | : | : | : |
Penny found a multiplication table in the back of one of Joe’s old school books — the top corner of it is illustrated. She noticed that prime numbers only appeared twice in the body of the table, whereas 4 (for example) appeared 3 times and 12 appeared 6 times. Penny could not help wondering how many times large numbers appeared in a huge table.
What is the smallest number that will appear 250 times?
One Comment
Leave one →
-
Brian Gladman permalink12345678910111213141516171819202122232425262728293031323334from functools import reducefrom operator import mulfrom number_theory import factors# if N = p1^e1.p2^e2.p3^3 ... pn^n then all its# divisors are of the form:## p1^x1.p2^x2.p3^x3 ... pn^xn## where each xi ranges over the values from 0 to ei# inclusive. So the number of divisors D(N) will be## D(N) = (e1 + 1).(e2 + 1).(e3 + 1) .. (en + 1)## if, given D(N), we want to know the smallest# number with this number of divisors, we need# to match up a prime value with each e value# in such a way that the resulting N is as small# as possible. So we need to match the smallest# primes with the largest e values.# low prime valuespr = [2, 3, 5, 7, 9, 11, 13, 17]# factor 250 to find the e values and reverse# their order so that the smallest prime will# be associated with thye largest e valueev = list(p - 1 for p in factors(250))[::-1]components = map(lambda x, y : x ** y, iter(pr), iter(ev))print('The number {} will appear 250 times.'.format(reduce(mul, components, 1)))
