All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Cube Permutations (Posted on 2024-02-25)
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)

 See The Solution Submitted by Steven Lord No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Computer solution | Comment 1 of 4
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

 Search: Search body:
Forums (0)