Teaser 3107: Room 101
From The Sunday Times, 10th April 2022 [link] [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?
[teaser3107]
Hugh+Casement, 
GeoffR, and 
Jim Olson are discussing. 
Robert Brown are discussing. 
Alex T Sutherland and 
Tony Brooke-Taylor and 
S2T2 
Jim Randell 3:19 pm on 8 April 2022 Permalink |
This Python program collects groups of 5-digit squares (excluding 10201) by their residue modulo 101. Any two squares with the same residue will differ by a multiple of 101.
So Smith can choose at most one square from each group.
It turns out there are 51 groups, so if Smith has correctly found more than 50 squares he must have chosen 1 from each group. And the only choices we (and O’Brien) can know for sure are from groups that have exactly 1 member.
The program runs in 55ms.
Run: [ @replit ]
from enigma import (powers, is_coprime, group, mod, join, printf) # group 5-digit squares, except 10201, that are coprime to 1984 by their residue mod 101 d = group( powers(100, 316, 2), st=(lambda x: x != 10201 and is_coprime(x, 1984)), by=mod(101), ) printf("[{n} groups]", n=len(d.keys())) # look for keys with only one candidate for k in sorted(d.keys()): vs = d[k] if len(vs) == 1: printf("{k} -> {vs}", vs=join(vs, sep=", "))Solution: The four squares O’Brien knew are: 15625, 34969, 62001, 91809.
LikeLike
GeoffR 8:13 am on 14 April 2022 Permalink |
from enigma import is_coprime from collections import defaultdict SQList = defaultdict(list) # 5-digit squares must be co-prime with 1984 # omit 101 as 101 ^ 2 = 10201, which is not needed squares = [x * x for x in range(102, 317) if is_coprime(x * x, 1984)] # index squares on remainder after dividing square by 101. for n in squares: SQList[n % 101].append(n) print("O'Brien knew the following squares:" ) for k, v in SQList.items(): if len(v) == 1: print( v[0], end = ' ')LikeLike
Hugh+Casement 10:58 am on 17 April 2022 Permalink |
I think it can be done without a program.
1984 = 2^6 × 31, so all even integers are excluded, as are the squares of multiples of 31, which are 155, 217, and 279 in the range under consideration (101 to 315). We are also told that 101² is absent.
If i² – j² is a multiple of 101, then so is either (i – j) or (i + j).
That means that nearly every odd integer in the range is paired with at least one other. The exceptions are 125 = 404 – 279, 187 = 404 – 217, 249 = 404 – 155, and 303 = 404 – 101 = 101 + 202.
And there certainly weren’t a quadrillion: in English we would say “Though there be a quadrillion …”.
LikeLike