Find the smallest 20-digit integer N which contains each of the digits 0 to 9 twice, whose cube is a 60-digit number which contains each of the digits 0 to 9 six times.
A "2pan" is a 20 digit integer with 2 of each digit.
Algorithm notes.
The purpose of function nextDoublePan(n) is to return the closest larger number than n which is a 2pan, i.e. 2 of each digit. By just looking at these integers, we skip over maybe a few thousand numbers each time.
Algo to find the next 2pan first checks to see if n is already a 2pan. If so, increment by 1 and continue checking.
Scan the number from left to right looking for the first digit which is the third instance. Stop there and truncate including the first "bad" digit but removing everything to the right.
Repeated add 1 and test until finding an integer with no more than 2 instances of any digit. This will be the left part. Next remove any digits present in the left part from the string '00112233445566778899' to make the right part. Then concatentate the left and right parts.
Done finding the next 2pan.
The first number to check is the cube root of 10^59, rounded up to the nearest integer, then run through function nextDoublePan(n) to get the smallest 2pan which, when cubed, yields a 60 digit integer.
Then test the 60-digit cube to see if it is a 6pan.
The first number tested was:
first = 46415889001223356779.
I ran this program for a few hours:
The counter 'i' got to 498959
n20 got to 46415889010977653322
(n20 - first)/i = about 19549 (average difference between a 2pan and the next one)
No solution found yet.
------------
smallsort = ''.join([str(i)*2 for i in range(10)])
largesort = ''.join([str(i)*6 for i in range(10)])
def nextDoublePan(n):
""" assumes 20 digit integer, returns next higher which has 2 of each digit, ie a double pandigital """
s = str(n)
if ''.join(sorted(s)) == smallsort:
n += 1
s = str(n)
for pos,val in enumerate(s):
if s[:pos+1].count(val) > 2:
firstbadpos = pos
break
lastOneIsBad = int(s[:firstbadpos+1])
valid = False
leftpart = lastOneIsBad
while not valid:
leftpart += 1
left_str = str(leftpart)
notriples = True
for digit in left_str:
if left_str.count(digit) > 2:
notriples = False
break
if notriples:
valid = True
unused = smallsort
for ch in left_str:
unused = unused.replace(ch, '',1)
return int(left_str + unused)
tries = 1000000
cuberoot_59_3 = 46415888336127788925
first = nextDoublePan(cuberoot_59_3)
n20 = first
for i in range(tries):
cube = n20**3
str_cube = str(cube)
if ''.join(sorted(str_cube)) == largesort:
print(i, n20, cube)
else:
n20 = nextDoublePan(n20)
print('done', n20)
print((n20-first)/tries)
|
|
Posted by Larry
on 2025-01-02 15:02:50 |
Methodology; no solution yet