Problem 062

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
kdoiron
Posts: 3
Joined: Fri Sep 19, 2008 7:44 pm

Problem 062

Post by kdoiron » Fri Sep 19, 2008 7:55 pm

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?

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 62 - Clarification needed?

Post by daniel.is.fischer » Fri Sep 19, 2008 8:08 pm

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).
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

kdoiron
Posts: 3
Joined: Fri Sep 19, 2008 7:44 pm

Re: Problem 62 - Clarification needed?

Post by kdoiron » Fri Sep 19, 2008 8:23 pm

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.

armitage
Posts: 1
Joined: Thu Jan 21, 2010 6:02 pm

Re: Problem 062

Post by armitage » Mon Mar 08, 2010 10:38 pm

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. :)

Kurushimi
Posts: 3
Joined: Mon Jul 05, 2010 4:41 am

Re: Problem 062

Post by Kurushimi » Sun Aug 22, 2010 1:42 pm

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.

User avatar
jaap
Posts: 515
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 062

Post by jaap » Sun Aug 22, 2010 5:17 pm

The answer has more than 11 digits.

frogjg2003
Posts: 11
Joined: Thu Jul 14, 2011 1:37 pm

Re: Problem 062

Post by frogjg2003 » Sun Sep 04, 2011 5:35 am

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?
Image
All with Phython.

Kelvin17
Posts: 2
Joined: Wed Sep 14, 2011 8:54 pm

Re: Problem 062

Post by Kelvin17 » Wed Sep 14, 2011 9:02 pm

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).
Image

User avatar
jaap
Posts: 515
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 062

Post by jaap » Wed Sep 14, 2011 9:36 pm

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.

Kelvin17
Posts: 2
Joined: Wed Sep 14, 2011 8:54 pm

Re: Problem 062

Post by Kelvin17 » Wed Sep 14, 2011 11:35 pm

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.
Image

User avatar
Francky
Posts: 90
Joined: Sat May 07, 2011 2:49 pm
Location: South of France

Re: Problem 062

Post by Francky » Thu Sep 15, 2011 8:59 am

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.
ImageEntia non sunt multiplicanda praeter necessitatem

xe3tec
Posts: 46
Joined: Thu May 05, 2011 7:52 am
Location: Vienna
Contact:

Re: Problem 062

Post by xe3tec » Mon Oct 03, 2011 9:25 am

I could use a hint...

Winthermute
Posts: 1
Joined: Mon Jun 11, 2018 1:59 pm

Problem 062 result

Post by Winthermute » Mon Jun 11, 2018 2:02 pm

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

User avatar
hk
Administrator
Posts: 10049
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 062 result

Post by hk » Mon Jun 11, 2018 2:23 pm

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

User avatar
RobertStanforth
Administrator
Posts: 583
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 062

Post by RobertStanforth » Mon Jun 11, 2018 5:46 pm

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

User avatar
hk
Administrator
Posts: 10049
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 062

Post by hk » Mon Jun 11, 2018 6:20 pm

Handled by PM.
Image

Post Reply