Project Euler Forum

In Problem 254 (View Problem) the text states that g(5) was 25 and sf(25) equals 5. While I verify that sf(25) = 5,
g(5) is not 25 because 25 is not the smallest integer n that satisfies sf(n) = 5:

f(00001) = Sum of (0! + 0! + 0! + 0! + 1!) = 1 + 1 + 1 + 1 + 1 = 5
sf(00001) = Digit sum of (5) = 5

I bring this up because the idea of trailing zeroes presented itself to me while I was coming to terms with understanding the problem. Maybe it would be helpful to add to the problem description a further constraint on the positive integers in question, namely that they be written without any leading zeroes.

A very interesting and entertaining problem! Thank you.

ukimiku wrote:Maybe it would be helpful to add to the problem description a further constraint on the positive integers in question, namely that they be written without any leading zeroes.

In general, for PE problems the policy is that no leading zeroes are allowed, except if explicitly mentioned.

Thanks for replying. I quite distinctly remember a couple of problems (with pandigital/palindromatic numbers, for instance) that explicitly excluded trailing zeroes in the problem statement. So it is not clear that the "general PE policy" is to forbid leading zeroes. Anyhow, a short remark in the problem statement would certainly clarify things a bit, in my opinion.

Regards,

If leading 0s were allowed, the entire problem wouldn't make sense - f(n) wouldn't be well defined. If I asked you how many digits the number 342 had, I don't think many people would answer '3 or 4 or 5 or ...' or think it needed clarification

I've been playing around with this problem, and can't see where I'm going wrong. I get g(20) is 267, and g(5) is 25, so I think I'm finding the right G(i) numbers (but not nearly fast enough for 150). However my value for ∑ sg(i) for 1 ≤ i ≤ 20 is 166 not 156 as stated in the problem.

Could someone who has solved this confirm that ∑ sg(i) for 1 ≤ i ≤ 20 is 156?

I've challenged myself to solve a problem that less than 500 people have solved for my 50th problem to get to level 2. I think I'm going to be losing sleep over this one

I just found my problem (typo on the value of 9!)
Now on to the solution.....

I had no trouble getting the answer for 1 <= i <= 20. However, I just tried running my program for up through 150 and it's basically freezing at 41, 45, 46, and 47, and I'm getting to numbers in the tens of millions before I find a correct value. For example, I'm getting g(45) = 12378889. Can someone verify this so I know I'm at least not doing anything incorrectly?

That looks right to me.

I suppose that's good news. However, my code gets stuck on 47 for at least 45 minutes (I terminated it at that point). Any advice?

n start to grow exponentially around i=42, you should find another way.
good luck!

Anyone tried taking this on with pencil and paper? It's not too bad until you get into the 30's...

I may need to think hard on a program. Or just skip it for now.

can this be solved without knowing a fitting theorem etc by chance?
if not, what's the topic i need to investigate?
obviously "optimized brute force" is getting me nowhere

Listed below are the values of g(n) and sg(n) for n in [1, 20]

 1,  1, 1
 2,  2, 2
 3,  5, 5
 4, 22, 4
 5, 25, 7
 6,  3, 3
 7, 13, 4
 8, 23, 5
 9,  6, 6
10, 16, 7
11, 26, 8
12, 44, 8
13,144, 9
14,256,13
15, 36, 9
16,136,10
17,236,11
18, 67,13
19,167,14
20,267,15

They sum up to 154 (not 156). Could anyone please point me to the wrong value(s)?

Thank you,