The cube, 41063625=(345)^3 can be permuted to produce two other cubes:
56623104=(384)^3 and 66430125=(405)^3.
In fact, 41063625 is the smallest cube for which exactly three permutations of its digits also form cubes.
Find the smallest cube for which exactly five permutations of its digits form cubes. (Project Euler, problem 62)
The smallest cube for which exactly five permutations of its digits form cubes is 127035954683.
The set of 5: [127035954683, 352045367981, 373559126408, 569310543872, 589323567104]
Their cube roots are [5027, 7061, 7202, 8288, 8384].
Algorithm notes:
My prior program (see 3 Cubes #2; pid=13537) was way too slow. It made a list of cubes, then for each cube, it tested every permutation of the digits to see the the result was also in the list of cubes.
For the first improvement, we need only compare cubes to other cubes of same length.
If n is the number of digits in the cube:
n smallest largest
1 1 2 (2^3 = 8 is largest one-digit cube)
2 3 4
3 5 9
4 10 21
5 22 46
etc
Second improvement: instead of looking at a cube then checking all its permutations, make a dictionary. Each cube is encoded into a string which is sorted in alphabetic order. For example 345^3 is 41063625 which encodes to the string '01234566'.
The dictionary has those sorted strings as keys, and the values are lists of cubes who have that same key. Now just look at dictionary values (which are lists of cubes) according to the length of the list.
The program is now orders of magnitude faster:
2 [125, 512]
3 [41063625, 56623104, 66430125]
4 [1006012008, 1061208000, 8012006001, 8120601000]
5 [127035954683, 352045367981, 373559126408, 569310543872, 589323567104]
6 [1426487591593, 1432197595648, 3496581419752, 4275981654391, 4813967954125, 7591941538264]
7 [12804692354875, 13097526845248, 15490388426752, 16443257028589, 17205482538496, 38405782562419, 42607284155983]
8 [10340284735656, 18437405506632, 26055434078136, 35245610867403, 36015465037824, 36310726085544, 43410085673625, 65724053438016]
9 [13465983902671, 18102364796593, 23667095189431, 23719065439168, 38160429751963, 68312596071439, 68523370149961, 80997264315163, 96803741135296]
10 [126120833457949, 127369820359144, 129523494108736, 196538434097221, 223947119460583, 269811549437032, 297061398351424, 304698942523171, 340229194658731, 341019324789625]
11 [106874325794816, 168791480734625, 176889144260375, 209764581864713, 250714384879616, 276951061483487, 291658484677013, 312148669407875, 351776204914688, 521737891864064, 661277140539848]
12 [106874325794816, 168791480734625, 176889144260375, 209764581864713, 250714384879616, 276951061483487, 291658484677013, 312148669407875, 351776204914688, 521737891864064, 661277140539848, 683518461097472]
13 [106874325794816, 168791480734625, 176889144260375, 209764581864713, 250714384879616, 276951061483487, 291658484677013, 312148669407875, 351776204914688, 521737891864064, 661277140539848, 683518461097472, 791016836442587]
14 [106874325794816, 168791480734625, 176889144260375, 209764581864713, 250714384879616, 276951061483487, 291658484677013, 312148669407875, 351776204914688, 521737891864064, 661277140539848, 683518461097472, 791016836442587, 854616314078792]
15 [106874325794816, 168791480734625, 176889144260375, 209764581864713, 250714384879616, 276951061483487, 291658484677013, 312148669407875, 351776204914688, 521737891864064, 661277140539848, 683518461097472, 791016836442587, 854616314078792, 874710238619456]
----------
import math
mostDigits = 21
smalls = [math.ceil(10**((n-1)/3)) for n in range(mostDigits+1)]
smalls[0] = 0
cubedict = {}
permnumber = 2 #increment to find first instance for each number of cubes
listOfPermutations = []
for ndigits in range(1, mostDigits):
lo = smalls[ndigits]
hi = smalls[ndigits + 1]
cubes = [c**3 for c in range(lo,hi)]
cubedict.clear()
for c in cubes:
s = str(c)
sorted_s = ''.join(sorted(s))
if sorted_s not in cubedict:
cubedict[sorted_s] = [c]
else:
cubedict[sorted_s].append(c)
lenDicVal = len(cubedict[sorted_s])
if lenDicVal == permnumber:
listOfPermutations.append([ndigits,lenDicVal, cubedict[sorted_s]])
print(permnumber, cubedict[sorted_s])
permnumber += 1
Edited on February 25, 2024, 12:08 pm
|
|
Posted by Larry
on 2024-02-25 12:03:23 |
Computer solution
