Sunday Times Teaser 3107 – Room 101
by Nick MacKinnon
Published Sunday April 10 2022 (link)
In the Ministry of Love, O’Brien told Winston Smith to calculate five-digit perfect squares, none sharing a prime factor with 1984. “And Winston, no two of them may differ by a multiple of 101 or you know what will happen. Now find as many as you can.” When Winston said he had found more than fifty, O’Brien replied, “Well done, Winston. Although there were a quadrillion solutions, I know some of your squares.” “Does the party control my mind?” “We do Winston. Did you choose 10201, for example?” “Of course not! It’s the worst square in the world!” “How many fingers am I holding up Winston?” “Three? Four? I don’t know!” “That’s how many of your squares we know.”
What four squares did O’Brien know?
-
Brian Gladman permalink1234567891011121314151617# 10201 = 101^2; 1984 = 31.2^6; hence the 5-digit squares# except 101^2 that share no prime factors with 1984 are:psq = list(x * x for x in range(103, 317, 2) if x % 31)# collect squares with the same residues mod 101 (hence# only one candidate can be used from each group)r2sqs = {}for sq in psq:k = sq % 101r2sqs[k] = r2sqs.get(k, []) + [sq]# the only squares O’Brien can know are in groups with one memberans = ', '.join(str(v[0]) for v in r2sqs.values() if len(v) == 1)f, s, l = ans.rpartition(', ')print(f"O’Brien knew {f} and {l}.")
-
John Z permalink12345678910111213141516171819from itertools import chainfrom math import isqrtdef factors(n):return set(sum(([i, n // i] for i in range(1, isqrt(n) + 1) if not n % i), []))f1984 = factors(1984)# 5-digit perfect squares that only share the factor '1' with 1984# exclude 10201 (101 * 101)sqrs = [i * i for i in range(103, 317, 2) if len(f1984 & factors(i * i)) == 1]# make the set of squares whose differences are divisible by 101e101 = set(chain(*((s1, s2) for i, s1 in enumerate(sqrs[:-1])for s2 in sqrs[i + 1:] if not (s2 - s1) % 101)))print(f"O'Brien's numbers: {str(sorted(set(sqrs) - e101))[1:-1]}")