Sunday Times Teaser 3117 – Save Stop Me If You’ve Heard This One
by Colin Vout
Published Sunday June 19 2022 (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?
Here is a straightforward but slow solution:
Here are two alternative fast solutions, both of which use my number_theory library.
This version uses the Chinese Remainder Theorem:
and a second using modular square roots of unity:
@Frits
This is not an assumption. Since C is the last digit of C^2 when C^2 is expressed
as a number in base 1501, C must be less than 1501 (all digits in a base B integer
are less than B).
Note that I have just edited the first version.
Brian
If the base is 209 you seem to miss C’s 21660 and 22022.
I wouldn’t expect them to see these solutions since both
programs use a short cut to solve the specific case set
by this teaser.
@Brian, your alternative program doesn’t print a solution.
C being less than 1501 seems a bit strange as all three numbers are reported to be under a million.
@Frits
Thanks, I have corrected the alternative version now.
Yes, its a bit surprising that the solution is so low compared to the
range given in the teaser. But the teasers are intended for manual
solution so including a clue that C is less than 1501 makes sense
in my view.
Easier for me to understand (modular square roots):
(C^2 – C) % 1501 = 0
(4C^2 – 4C) % 1501 = 0
(4C^2 – 4C + 1) % 1501 = 1
(2C – 1)^2 % 1501 = 1
Modular square roots are tricky to compute in general but the mod
value in this case has been chosen to make this easy since 1501 is
the product of two primes – 19 and 79 .
The extended GCD algorithm can be used to express any number as a
linear combination of multiples of 19 and 79. Finding the square
roots of 1 mod 19 and 79 is easy enough to do manually, after which
the Chinese Remainder Theorem can be used to combine them to find
square roots of 1 mod 1501.
I also found it disappointing that the solution was so small