Brain teaser 988: Pythagoras was never like this
From The Sunday Times, 28th June 1981 [link]
In accordance with tradition the retiring President of the All Square Club set members a special competition. Titled as above, it required new meanings for the signs “+” and “=” as in:
6² + 1² = 19²
indicating that both sides could be taken to represent 361.
The number 361 was then called a “Special Pythogorean Square” (SPS) and the numbers 36 and 1 its “contributing squares”.
Other examples given were:
7² + 27² = 223²
15² + 25² = 475²giving 49729 and 225625 as Special Pythogorean Squares.
Members were invited to submit series of Special Pythogorean Squares which they could claim to be unique in some way. Each number in their series had to be less than a million, and no two numbers in their series could have the same number of digits.
After much deliberation the prize was awarded to the member who submitted a series of Special Pythogorean Squares which he correctly claimed was the longest possible list of such numbers all with the same second contributing square.
What (in increasing order) were the numbers in the winning series?
This puzzle is included in the book The Sunday Times Book of Brainteasers (1994).
[teaser988]
Frits and 
NigelR, 
GeoffR, and 
Hugo, 
S2T2 
Jim Randell 11:17 am on 31 December 2023 Permalink |
So we treat “+” and “=” as string operations, being concatenation and equality respectively.
This Python program generates all SPSs below 1 million, and then constructs maximal length sequences which share the same suffix square.
It runs in 61ms. (Internal runtime is 2ms).
Run: [ @replit ]
from enigma import ( defaultdict, Accumulator, irange, inf, sq, cproduct, join, printf ) # generate SPSs def generate(N): # record squares (as strings) d = dict() for i in irange(0, inf): n = sq(i) if not (n < N): break s = str(n) d[s] = i # split the square into prefix and suffix for j in irange(1, len(s) - 1): (pre, suf) = (s[:j], s[j:]) (pi, si) = (d.get(pre), d.get(suf)) if pi is None or si is None: continue printf("[{n} = {pre} + {suf} -> {i}^2 = {pi}^2 + {si}^2]") yield (s, pre, suf) # collect SPSs: <suffix> -> <length> -> [<SPS>...] d = defaultdict(lambda: defaultdict(list)) for (s, pre, suf) in generate(1000000): d[suf][len(s)].append(s) # find maximal length sequences sharing the same suffix r = Accumulator(fn=max, collect=1) for (suff, v) in d.items(): r.accumulate_data(len(v.keys()), suff) printf("maximal sequence length = {r.value}") # output maximal length sequences for k in r.data: printf("suffix = {k}") for ss in cproduct(d[k].values()): printf("-> {ss}", ss=join(ss, sep=", ", enc="()"))Solution: The winning series was: 49, 169, 3249, 64009, 237169.
Which are constructed as follows:
Each has a suffix square of 9.
LikeLike
Frits 4:55 pm on 3 January 2024 Permalink |
Slower.
from enigma import SubstitutedExpression # the alphametic puzzle p = SubstitutedExpression( [ # ABC^2 concatenated with DEF^2 = square "ABC > 0", # RHS must be less than a million "(d2 := DEF**2) < 10 ** (6 - len(str(a2 := ABC**2)))", "is_square(int(str(a2) + str(d2)))", ], answer="ABC, DEF", d2i="", distinct="", reorder=0, verbose=0, # use 256 to see the generated code ) # store answers in dictionary (key = suffix) d = dict() for a, b in p.answers(): d[b] = d.get(b, []) + [a] # find maximal length sequences sharing the same suffix m = len(max(d.values(), key=lambda k: len(k))) # assume more than one answer is possible print("answer:", ' or '.join(str(x) for x in [sorted(int(str(v**2) + str(k**2)) for v in vs) for k, vs in d.items() if len(vs) == m]))LikeLike
Jim Randell 10:25 pm on 4 January 2024 Permalink |
@Frits: Would this work if there were multiple SPSs with the same length and suffix?(e.g. if 99856+9 were a valid SPS).
LikeLike
Frits 6:39 pm on 5 January 2024 Permalink |
@Jim, you are right. This wouldn’t work as I forgot the condition “no two numbers in their series could have the same number of digits”.
LikeLike