Enigmatic Code
Programming Enigma Puzzles
Rudolphogram #1
Posted by on 3 April 2024
Find the smallest perfect square with exactly 2 zeroes, 2 ones, 2 twos, …, 2 nines.
The perfect square may not start with a zero.
This weeks bonus puzzle was suggested by new contributor ruudvanderham.
[ruud1]
Enigmatic Code 
We know that each square with the required property must be a 20-digit number (as each of the digits 0-9 occurs exactly twice), and so we can choose an appropriate lower bound on values to square to start our search.
The following Python program can also be used to explore numbers with the desired property in different bases.
Run: [ @replit ]
from enigma import (irange, powers, sqrtc, sqrtf, flatten, nconcat, rev, nsplit, int2base, arg, printf) # find the smallest positive integer that in base <b> uses each digit exactly <k> times def solve(k, b=10): # the collection of digits (in ascending order) ds = flatten([x] * k for x in irange(b)) # for the lower bound we bring the first non-zero digit to the front x = sqrtc(nconcat([ds[k]] + ds[:k] + ds[k + 1:], base=b)) # for the upper bound we reverse the digits y = sqrtf(nconcat(rev(ds), base=b)) # consider squares between <a> and <b> in the appropriate base for n in powers(x, y, 2): if sorted(nsplit(n, base=b)) == ds: return n # solve for specified base b = arg(10, 0, int) n = solve(2, b) printf("base {b}: {n} = {x}", x=int2base(n, base=b))Solution: The smallest such number is 10012495377283485696.
In base b the number will be 2b digits long.
Here are the corresponding numbers for bases 2 – 16 (given in decimal and the appropriate base):
With a little adaptation we can also find a cube 10056421854778936239 and a biquadrate 23514473895962870016.
For base = 10 we can accelerate it a bit by only considering roots that are divisible by 3 (as the perfect square is divisible by 9 (sum digits = 90)).
Thanks to @jim randell, I start my search now later than my original sqrt(1e19).
This my one-liner using Counter.
from collections import Counter from math import sqrt, ceil result = next(i for i in range(ceil(sqrt(10012233445566778899)), int(sqrt(99887766554433221100))) if set(Counter(f"{i * i}").values()) == {2}) print(f"{result} ** 2 = {result*result}")And an -arguably more performant- implementation with a defaultdict. The moment a digit occurs three times, the scan will be aborted.
from collections import defaultdict from math import sqrt, ceil for i in range(ceil(sqrt(10012233445566778899)), int(sqrt(99887766554433221100))): count_per_digit = defaultdict(int) for digit in f"{i*i}": if count_per_digit[digit] == 2: # we can't have more than two occurences of the same digit break count_per_digit[digit] += 1 else: # all digits passed print(f"{i} ** 2 = {i*i}") breakThe fastest I can get is a search of squares of numbers that are multiples of 3. (A double pandigital is a multiple of 9, so its square root is a multiple of 3)
def search(): n = int( 10012233445566778899**0.5) n -= n%3 target = list('00112233445566778899') while 1: if sorted(str(n*n)) == target: print(f"{n}^2 = {n*n}" ) return n+=3 search()This is a little bit faster. Strange thing is that the an any() version of line 5-7 seems to be slower.
def search(): def is_double_pandigital(n): s = str(n) for x in "0123456789": if s.count(x) != 2: return False return True n = int( 10012233445566778899**0.5) n -= n%3 while 1: if is_double_pandigital(n * n): print(f"{n}^2 = {n*n}" ) return n+=3 search()