Project Euler Forum

I think a clarification may be needed for problem 62. You state in the example that 41063625 (345^3) is the smallest cube that has exactly 3 of its permutations that are also cubes. But what about 1,000,000 = 100^3?

For this, 0000001 (= 1^3) and 0001000 (= 10^3) are also cubes. Or do these not count as permutations, since they begin with zero?

Quite. Leading zeros are always excluded (unless explicitly allowed). Nobody uses leading zeros in real life anyway, or do they? (Except in dates, where they have become quite common due to the spread of computers - I don't count non-numbers like zip-codes, ISBN, article-numbers and such, they are really strings which are only by chance composed of digits).

Thanks, Daniel. I figured as much when I saw a cube with exactly 3 permutations much earlier than I expected, so I knew something was wrong.

Actually - never mind, I was returning the first result in my list, which wasn't sorted. Once again, trying to communicate the problem to people has helped me solve it.

This is just a quick question to help me know whether or not my algorithm missed it. How many digits does the answer actually have? I've checked up to 11 digits then stopped it after it ran for a while.

The answer has more than 11 digits.

My code is taking a really long time.
I have let it run for a few hours, and it still hasn't come up with the answer. Just in case I've got some kind of mistake, here are my values for the smallest cubes with n permutations also cubic, as well as the time (s) it took to get these numbers.
1 1 1 0.0090000629425
2 5 125 0.0220000743866
3 345 41063625 21.4930000305
4 1002 1006012008 760.402999878
I have no doubt that my program will eventually find it. Not knowing any kind of combinatorial, algebraic, or analytic solution, my algorithm simply checks all the permutations of each cubic number (with a few shortcuts to reduce it a bit). Assuming that there is some kind of pattern, I've tried a few different fits, with results ranging from a few hours to close to a year. Is there some glaringly obvious thing I probably missed?

Would someone be able to confirm that the answer would be 10169526593387478421 for the smallest cube with exactly 100 permutations? I want to see how accurate my algorithm is (written in Python and runs this in ~40 seconds and the actual problem in <100 ms).

Kelvin17 wrote:Would someone be able to confirm that the answer would be 10169526593387478421 for the smallest cube with exactly 100 permutations? I want to see how accurate my algorithm is (written in Python and runs this in ~40 seconds and the actual problem in <100 ms).

I get 10659867245972738513 as the first with exactly 100 and 10019246753502378496 as the first with at least 100 cube permutations (106 in fact).

Edit: Changed my second answer from 10144270878565032936 (with 114 cube perms) when I realised that my program used an unsorted collection so that my answer was not necessarily the smallest.

Edit2: 10169526593387478421 has 122 cube permutations.

jaap wrote:

Kelvin17 wrote:Would someone be able to confirm that the answer would be 10169526593387478421 for the smallest cube with exactly 100 permutations? I want to see how accurate my algorithm is (written in Python and runs this in ~40 seconds and the actual problem in <100 ms).

I get 10659867245972738513 as the first with exactly 100 and 10019246753502378496 as the first with at least 100 cube permutations (106 in fact).

Edit: Changed my second answer from 10144270878565032936 (with 114 cube perms) when I realised that my program used an unsorted collection so that my answer was not necessarily the smallest.

Edit2: 10169526593387478421 has 122 cube permutations.

Thank you. What happened was whenever a permutation was added to a list, it would check the length of the list and return that list if it was 100, even though there could be more possible permutations.

I got PE062(k=5) in 34.5ms,
and PE062(k=100) = 10659867245972738513 in 30.5s.
In Python3, uncompiled.
--
10019246753502378496 for 106 perms with my algo.

I could use a hint...

I cannot send solution for problem 062 - I know that my result is proper but page refuses it. Someone has similar problem?

What does the page say?
If it says: wrong answer, your answer is wrong.

@Winthermute - I have merged your post with the existing clarification topic for this problem.

Handled by PM.