Problem 171

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
LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Problem 171

Post by LarryBlake »

Problem 171 (View Problem)
1. I broke this problem into 2 pieces: possible digit combinations and their permutations.

For example, 34 is one possible combination. Permutations include 43, 304, 4003, etc.

Not counting the zeros as separate combinations, my number of digit combinations ends in 372. Is this correct?

2. If you think I'm giving too much strategy away, please let me know and I'll remove the post.
Image
Top
thkang
Posts: 8
Joined: Thu Nov 15, 2012 8:34 am

Re: Problem 171

Post by thkang »

How come your number of digit combinations is 372?

I am putting my efforts to this problem, and for example when f(x) to be 49,
there are:

Code: Select all

[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3]
[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3]
[1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3]
[1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3]
[1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 3, 3]
[1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3]
[1, 2, 2, 2, 3, 3, 3, 3]
[1, 1, 1, 1, 3, 3, 3, 3, 3]
[2, 3, 3, 3, 3, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 4]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 4]
[1, 2, 2, 2, 2, 2, 2, 2, 2, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4]
[1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 4]
[2, 2, 2, 2, 2, 2, 3, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4]
[1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4]
[1, 1, 1, 2, 2, 2, 3, 3, 4]
[1, 1, 1, 1, 1, 1, 3, 3, 3, 4]
[1, 1, 2, 3, 3, 3, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 4]
[1, 1, 1, 1, 1, 2, 2, 2, 4, 4]
[1, 2, 2, 2, 2, 4, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 3, 4, 4]
[1, 1, 1, 1, 2, 3, 4, 4]
[2, 2, 3, 4, 4]
[1, 4, 4, 4]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5]
[1, 1, 1, 1, 2, 2, 2, 2, 2, 5]
[2, 2, 2, 2, 2, 2, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 5]
[1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 5]
[1, 1, 1, 2, 2, 2, 3, 5]
[1, 1, 1, 1, 1, 1, 3, 3, 5]
[1, 1, 2, 3, 3, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 4, 5]
[1, 1, 1, 1, 2, 4, 5]
[2, 2, 4, 5]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6]
[1, 1, 1, 1, 1, 2, 2, 6]
[1, 2, 2, 2, 6]
[1, 1, 1, 1, 3, 6]
[2, 3, 6]
[7]
x^2 and number of possible combinations to build x^2:

Code: Select all

1 1
4 2
9 4
16 8
25 17
36 33
49 65
64 120
81 227
100 408
121 717
144 1180
169 1937
196 2984
225 4412
256 6284
289 8546
324 11012
361 13731
400 16202
441 18238
484 19575
529 20059
576 19420
625 17965
676 15657
729 12951
784 10100
841 7409
900 5038
961 3255
1024 1916
1089 1048
1156 505
1225 226
1296 85
1369 28
1444 6
1521 1
1600 0
can you tell me what is wrong? I used dynamic programming(I'm not got at that though) and it takes 2.3gb of memory for a dictionary of numbers between 1~1600 and their combinations.
Top
thkang
Posts: 8
Joined: Thu Nov 15, 2012 8:34 am

Re: Problem 171

Post by thkang »

eventually I solved this problem, but judging from the thread for 171 my performance was abysmal :( 2gb of ram and 3 minutes to solve it, Darn!
Top
User avatar
youth4ever
Posts: 12
Joined: Sun Jan 08, 2017 8:34 pm
Contact:
Contact youth4ever

Re: Problem 171

Post by youth4ever »

Hi,

Are the numbers containing zeros valid numbers ?
For example for n = 36 one solution is f(442) = 4^2 + 4^2 + 2^2 = 16 + 16 + 4
But then we can put as many zeros as we want to form a 20-digit number like :
4420 with every valid combination 2044, 4402 ....
44200 with every valid combinations ...
to 44200000000000000000 with all validcombinations .
So we should include in the sum calculation these numbers with zeros ?

Thanks.
Top
MuthuVeerappanR
Posts: 539
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:
Contact MuthuVeerappanR

Re: Problem 171

Post by MuthuVeerappanR »

Yes. All those are valid combinations. We should find numbers with maximum of 20 digits.
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Top
Post Reply

Return to “Clarifications on Project Euler Problems”