Teaser 3117: Stop me if you’ve heard this one
From The Sunday Times, 19th June 2022 [link] [link]
A square, a triangle and a circle went into a bar.
The barman said: “Are you numbers over 18?”
They replied: “Yes, but we’re under a million”
The square boasted: “I’m interesting, because I’m the square of a certain integer”
The triangle said: “I’m more interesting — I’m a triangular number, the sum of all the integers up to that same integer”
The circle said: “I’m most interesting — I’m the sum of you other two”
“Well, are you actually a circular number?”
“Certainly, in base 1501, because there my square ends in my number exactly. Now, shall we get the drinks in?”
The square considered a while, and said: “All right, then. You(‘)r(e) round!”
In base 10, what is the circular number?
[teaser3117]
GeoffR, 
Frits, and 1 other are discussing. 
Hugh+Casement and 
John Crabtree, and 
Mark Valentine, and 1 other are discussing. 
bencooperjamin, and 4 others are discussing. 
S2T2 
Jim Randell 5:27 pm on 17 June 2022 Permalink |
Circular numbers are also called automorphic numbers [@wikipedia], and we have encountered them before. See: Enigma 49, Enigma 1736.
There is a unique value for the “certain integer” (and so S, T, C).
This Python program runs in 59ms. (Internal runtime is 4.5ms).
from enigma import (irange, inf, sq, tri, nsplit, zip_eq, join, printf) # consider possible "certain" integers for n in irange(6, inf): S = sq(n) T = tri(n) C = S + T if not (C < 1000000): break # consider the digits of C and C^2 in base 1501 Cds = nsplit(C, base=1501) C2ds = nsplit(sq(C), base=1501) # does C^2 end with C? if zip_eq(Cds, C2ds, reverse=1): # output solution fmt = lambda ds: join(ds, sep=":", enc="{}") printf("n={n}: S={S} T={T} C={C} [C={Cds} C^2={C2ds}]", Cds=fmt(Cds), C2ds=fmt(C2ds))Solution: The circular number is 1027.
Numbers up to 999,999 can be represented in base 1501 using 1- or 2- digits.
And there are six 1- or 2- digit automorphic numbers in base 1501, which give potential values for C:
The first two are too small. The last one is too big.
Of the remaining three only 1027 gives a viable value for n, which is n = 26.
i.e.
And in base 1501 we have:
So (in base 1501) the final digit of C² is C.
In fact, even if S and T are square and triangular numbers of (possibly) different integers, we can still work out a unique value for C.
LikeLike
Jim Randell 8:26 pm on 17 June 2022 Permalink |
Here is a faster version that doesn’t construct the base 1501 representations.
It has an internal run time of 852µs.
from enigma import (irange, inf, sq, tri, printf) # consider possible "certain" integers M = B = 1501 for n in irange(6, inf): S = sq(n) T = tri(n) C = S + T if not (C < 1000000): break # consider the digits of C and C^2 in base 1501 while not (C < M): M *= B if pow(C, 2, M) == C: # output solution printf("n={n}: S={S} T={T} C={C}")LikeLiked by 1 person
Jim Randell 4:11 pm on 30 June 2022 Permalink |
I read up on how to find modular roots of integer-valued polynomials using Hensel lifting and the Chinese Remainder Theorem, and then wrote some code to implement it.
Given the “certain integer” n, the following Python code constructs a polynomial function for f(n) = sq(C(n)) − C(n), and then finds the roots of this function modulo 1501^k (for k = 1, 2). We then check these roots give viable values of S, T, C.
The internal runtime is 564µs, so it is faster than my simple approach above, but quite a lot more complicated.
from enigma import (irange, prime_factor, gcd, lcm, egcd, cproduct, sq, tri, ndigits, arg, printf) # simplified CRT # solve: x = a (mod m); x = b (mod n) def crt1(a, b, m, n): g = gcd(m, n) if (a - b) % g != 0: return None (x, y, z) = (m // g, n // g, (m * n) // g) (u, v, _) = egcd(x, y) return (b * u * x + a * v * y) % z # general Chinese Remainder Theorem # solve: x = rs[i] (mod ms[i]) def crt(rs, ms): assert len(rs) == len(ms) # or use zip(..., strict=1) x = mm = None for (r, m) in zip(rs, ms): if x is None: (x, mm) = (r, m) else: x = crt1(r, x, m, mm) if x is None: return None mm = lcm(m, mm) return x # find modular roots of a polynomial class PolyRootsMod(object): def __init__(self, f, cache=1): self.f = f self.cache = (dict() if cache else None) # find roots of <f> mod (<b>^<k>) using Hensel's lemma def hensel(self, b, k): if k == 0: return [0] assert k > 0 bk = b**k # check the cache cache = self.cache if cache: rs = cache.get(bk) if rs is not None: return rs # find the roots f = self.f k_ = k - 1 bk_ = b**k_ rs = list() for r in self.hensel(b, k_): for i in irange(b): x = i * bk_ + r if f(x) % bk == 0: rs.append(x) # cache if necessary if cache is not None: cache[bk] = rs return rs # find roots of polynomial <p> mod <n>^<k> def roots_mod(self, n, k=1): # find roots for each prime factor of <n>^<k> (rs, bs) = (list(), list()) for (f, e) in prime_factor(n): rs.append(self.hensel(f, e * k)) bs.append(pow(f, e * k)) # combine roots using CRT for xs in cproduct(rs): yield crt(xs, bs) B = arg(1501, 0, int) printf("[B={B}]") # start with polynomial functions: sq, tri, circ circ = lambda n: sq(n) + tri(n) # find k-digit automorphic values for C in base B f = lambda x: x * (x - 1) poly = PolyRootsMod(lambda n: f(circ(n))) for k in irange(1, ndigits(999999, base=B)): for n in poly.roots_mod(B, k): S = sq(n) T = tri(n) C = circ(n) if S < 18 or T < 18 or not (C < 1000000): continue if ndigits(C, base=B) != k: continue printf("S={S} T={T} C={C} [n={n}]")LikeLike
Jim Randell 9:50 am on 18 June 2022 Permalink |
Here is a version adapted from my code for Enigma 49. It proceeds by constructing possible automorphic values for C and then calculating the corresponding “certain integer” n, and from that S and T. Although this is not as fast as my previous program.
from enigma import (irange, ndigits, uniq, quadratic, sq, tri, printf) # generate <k> digit automorphic numbers (in base <b>) # i.e. x where the rightmost k digits of x^n are the digits of x # yield (<k>, <x>) where <k> in <ks> def automorphic(ks, b=10, n=2): K = max(ks) (k, xs, p, q) = (1, [0], 1, b) while not (k > K): f = (k in ks) xs_ = list() for d in irange(b): for x in xs: x_ = d * p + x if pow(x_, n, q) == x_: if f: yield (k, x_) xs_.append(x_) (k, xs, p, q) = (k + 1, xs_, q, q * b) # consider 1-, 2- digit automorphic numbers in base 1501 d = ndigits(999999, base=1501) for C in uniq(x for (k, x) in automorphic(irange(1, d), 1501)): if C < 18 or not (C < 1000000): continue # calculate n: C = n(3n + 1)/2 for n in quadratic(3, 1, -2 * C, domain="Z"): if n < 6: continue S = sq(n) T = tri(n) printf("C={C} S={S} T={T} [n={n}]")And here is a version which proceeds by constructing possible values for C using the technique given on the Wikipedia page for automorphic numbers [@wikipedia].
from enigma import (irange, quadratic, sq, tri, printf) # Hensel's lemma - see [ https://en.wikipedia.org/wiki/Automorphic_number ] def hensel(poly, base, power): if power == 0: return [0] roots = hensel(poly, base, power - 1) rs = list() for r in roots: for i in irange(base): j = i * base ** (power - 1) + r x = poly(j) % (base ** power) if x == 0: rs.append(j) return rs # generate <k> digit automorphic numbers in base <b> # i.e. values of x where the rightmost k digits of x^2 are the digits of x def automorphic(k, b=10): poly = lambda x: x * x - x return hensel(poly, b, k) # consider 1-, 2- digit automorphic numbers in base 1501 for k in (1, 2): for C in automorphic(k, 1501): if C < 18 or not (C < 1000000): continue # calculate n: C = n(3n + 1)/2 for n in quadratic(3, 1, -2 * C, domain="Z"): if n < 6: continue S = sq(n) T = tri(n) printf("C={C} S={S} T={T} [n={n}]")LikeLike
Robert Brown 6:19 pm on 17 June 2022 Permalink |
Hi Jim
Your version of the text differs from the Sunday Times site. This asks “In base 10, what is the circular number?” You seem to have “what is the certain integer”.
LikeLike
Jim Randell 6:27 pm on 17 June 2022 Permalink |
Thanks. Of course if you know the “certain integer”, you can easily calculate the square, triangular and circular numbers.
Interestingly, there is only one possible value for C, even if S and T are square and triangular numbers of different integers.
LikeLike
GeoffR 8:32 pm on 17 June 2022 Permalink |
if S and T are both less than 1,000,000, then C is less than 2,000,000.
The last two digits in base 1501 give a max value of 2,253,000.
i.e. 1500 *1501 + 1500, which is adequate to define C.
# Square and triangular numbers are less than 1,000,000 sqs = [x * x for x in range(5, 1000)] tris = [ x * (x+1)// 2 for x in range(6, 1410)] CNum = [] # list to store circular numbers # consider possible (S, T) combinations for S in sqs: for T in tris: C = S + T C2 = C * C # only 2 digits in base 1501 are needed # for the maximum value of C num, rem = divmod(C2, 1501) if rem == C: if C not in CNum: CNum.append(C) for n in CNum: print(f"Circular number = {n}")LikeLike
Jim Randell 9:42 pm on 17 June 2022 Permalink |
@GeoffR: This is very similar to the first program I wrote. And then I realised that S = n² and T = tri(n) for the same value of n, which makes things much faster.
It does however lead to the same answer for C, so there is a harder problem lurking inside this puzzle.
Also I think the text implies that all of S, T, C are less than a million (and more than 17).
But C is 1- or 2-digits in base 1501, so C² could be up to 4 digits, and we need to check the final 2 digits if C is length 2.
LikeLike
Frits 11:11 pm on 17 June 2022 Permalink |
Approaching it from the possible C values.
I have assumed that when the number of digits in the remainder of (C^2 base 1501) is smaller than the number of digits in C we need to also check the last digits of the divisor of (C^2 base 1501).
B = 1501 # C = f(n) = n(3n + 1) // 2 # f(n+1) - f(n) = (n + 1)(3(n + 1) + 1) // 2 - n(3n + 1) // 2 # = 2 + 3n C = 40 # as C >= 2 * 18 for n in range(5, 817): sC = str(C) lC = len(sC) C2 = C**2 sC2 = str(C2) # next C C += (2 + 3 * n) # calculate remainder R1 = C2 % B lR1 = len(str(R1)) # can we directly check all digits of C if lR1 >= lC: if str(R1)[-lC:] != sC: continue else: # len(R1) < lC # check last digits of C if sC[-lR1:] != str(R1): continue # check the digits of the divisor R2 = ((C2 - R1) // B) % B lR2 = len(str(R2)) # check if digits in C correspond with the remainder of the divisor if sC[-lR1 + lR2:-lR1] != str(R2): continue # too lazy to code what happens if lR1 + lR2 < lC if lR1 + lR2 < lC: continue print("answer:", sC)LikeLike
Frits 2:39 pm on 18 June 2022 Permalink |
@Jim,
If the base is 272 is C = 57 an answer as C2ds=(11, 257) ?
LikeLike
Jim Randell 2:55 pm on 18 June 2022 Permalink |
@Frits: 57 is not automorphic in base 272.
You compare the “digits” as atomic values not strings, so the final digit of 57² is 257 and this is not the same as 57.
But 17 and 256 are both 1-digit automorphic numbers in base 272:
LikeLike
Frits 4:48 pm on 18 June 2022 Permalink |
There is no solution if the circular number has to be a round number as well (at least not in base 10).
LikeLike
Jim Randell 6:14 pm on 18 June 2022 Permalink |
Although the answer is a spherical number.
LikeLike
Jim Randell 9:06 am on 21 June 2022 Permalink |
For an answer with larger values for S, T, C, but a smaller base, try solving the same puzzle with a base of 105.
LikeLike
GeoffR 12:08 pm on 21 June 2022 Permalink |
Easy to adapt Jim’s first program, substituting 105 for 1501 as the number base.
This gives:
n=458: S=209764 T=105111 C=314875 [C={28:58:85} C^2={7:80:71:28:58:85}]
C is 3 digits long, so:
28 * 105**2 + 58 * 105 + 85 = 314875
LikeLike