Teaser 2772: Madam I’m Adam
From The Sunday Times, 8th November 2015 [link] [link]
Adam noticed that today’s Teaser number was a four-figure palindrome. He told me that he had written down [a] four-figure palindrome and he asked me to guess what it was. I asked for some clues regarding its prime factors and so he told me, in turn, whether his number was divisible by 2, 3, 5, 7, 11, 13, … Only after he had told me whether it was divisible by 13 was it possible to work out his number.
What was his number?
When this was originally published “another” was used where I have placed “[a]”, but this makes the puzzle unsolvable. However, as presented above, there is a unique solution.
[teaser2772]
Frits and 
GeoffR and 
Hugh Casement, 
John Crabtree, and 
Tony Brooke-Taylor, and 2 others are discussing. 
Geoff, 
S2T2 
Jim Randell 8:17 am on 26 January 2021 Permalink |
The use of “another” in the puzzle text implies that the palindrome 2772 is excluded from the set of possibilities, but if this is the case the puzzle is not solvable. So instead we just consider that Adam has told the setter that he has written down some 4-digit palindrome (which may be 2772), and the setter has to guess it.
This Python program considers increasing prime numbers p, and looks for palindromes that can be uniquely identified by knowing if it is divisible by primes up to (and including) p.
To solve this puzzle we look up to p = 13, but the maximum prime can be specified on the command line. (We have to go to 859 to be sure of determining the palindrome).
The program runs in 45ms.
Run: [ @repl.it ]
from enigma import Primes, irange, filter_unique, diff, join, arg, printf # max prime N = arg(13, 0, int) # 4-digit palindromes palindromes = sorted(1001 * a + 110 * b for a in irange(1, 9) for b in irange(0, 9)) #palindromes.remove(2772) # puzzle text says 2772 is excluded, but that makes it impossible # palindromes unique by divisibility of primes, but not unique by shorter sequences r = set() # consider sequences of primes by increasing length ps = list() for p in Primes(N + 1): ps.append(p) # find unique palindromes by this sequence of primes s = filter_unique(palindromes, lambda x: tuple(x % p == 0 for p in ps)).unique # unique palindromes we haven't seen before s = diff(s, r) if s: printf("{p} -> {s}", s=join(s, sep=", ", enc="()")) # update the list of unique palindromes r.update(s)Solution: The number was 6006.
If 2772 is removed from the set of possible palindromes (by removing the comment from line 8), we see that 8778 would also be uniquely identified by the divisibility values for primes up to 13.
So although the setter would know the answer (because he knows if the number is divisible by 13 or not), we can’t work it out:
But, if 2772 is included in the set of possible palindromes, then 8778 and 2772 cannot be distinguished until we are told the answer for divisibility by 19, so the fact that the setter can work out the number at p = 13 means that it must be 6006.
There are two palindromes that can be distinguished with a shorter sequence of answers:
Note that all palindromes are divisible by 11.
LikeLike
Frits 8:08 pm on 26 January 2021 Permalink |
With fewer modulo calculations.
from collections import Counter # max prime N = 13 # list of prime numbers P = [2, 3, 5, 7, 11, 13] # 4-digit palindromes palindromes = sorted(1001 * a + 110 * b for a in range(1, 10) for b in range(0, 10)) # initialize dictionary (divisibility by prime) d = {key: [] for key in palindromes} singles = [] # consider sequences of primes by increasing length for p in P: # maintain dictionary (divisibility by prime) for x in palindromes: d[x].append(x % p == 0) c = Counter(map(tuple, d.values())) # get combinations unique by divisibility of primes # but not unique by shorter sequences c2 = [k for k, v in c.items() if v == 1 and all(k[:-i] not in singles for i in range(1, len(k)))] if len(c2) == 1: for x in palindromes: if d[x] == list(c2[0]): print(f"{p} -> {x}") if p != N: print("Error: palindrome already known before prime", N) exit() # add "unique by shorter sequences" to singles for x in [k for k, v in c.items() if v == 1]: singles.append(x)LikeLike