Sunday Times Teaser 2790 – Factoidels
by Tom Wills-Sandford
Published: 13 March 2016 (link)
In order to introduce the class to “lowest common denominators”, Amelia’s teacher asked them to find the lowest number with the property that each of 1, 2, 3, 4 and 5 divided exactly into it. They correctly calculated the answer as 60, and the teacher called this the “factoidel” of 5. He went on to demonstrate that the factoidel of 6 was also 60. Being keen, Amelia investigated factoidels at home and then told the teacher that she had found the highest set of four consecutive numbers whose factoidels are all different (at least she had cleverly checked well into the billions).
What were those four consecutive numbers?
One Comment
Leave one →
-
Brian Gladman permalink123456789101112131415161718192021222324252627282930# Consider moving from lcd(1..n-1) to lcd(1..n). If n has factors p1^e1,# p2^e2 ... involving two or more primes, then lcd(1..n-1) will already# contain its factors, which means that lcd(1..n) = lcd(1..n-1). So the# values of lcd(1..n-1) and lcd(1..n) can only differ when n is a prime# or a prime power. So n, n+1 and n+2 must all be primes or prime powers# in order to obtain four different values of lcd(1..n) for consecutive# integers.## If n is even this requires that n = 2^e and n + 2 = 2^f for integers e# and f, giving only one solution 2^1 + 2 = 2^2. For odd n (n, n+1, n+2)# = (2^k-1, 2^k, 2^k+1) must all be primes or prime powers. Mihăilescu's# theorem, however, states that 8 and 9 are the only consecutive integers# that are non-trivial integer powers. Hence neither 2^k-1 nor 2^k+1 can# be powers if k > 3. Hence they can only be primes but since twin primes# have remainders of -1 and + 1 mod 6, there are again no solutions for k# greater than three (since 2^k would need to be a multiple of 6)from math import gcd# initialise a list to the first four 'factoidels'lc = [1, 2, 6, 12]for n in range(5, 16):# if the list has four different values, output# the last four indexes and their factoidelsif len(set(lc)) == 4:print(*tuple(range(n - 4, n)), tuple(lc))# update the list for the next four factoidelslc = lc[1:] + [lc[-1] * n // gcd(lc[-1], n)]
