Problem 034

[kaldrenon]

Hi all.

Let me preface by saying that I am a college student (just finished first year) whose background is primarily programming and not math - I know that the line between the two is easily blurred, but what I mean is that complex numeric computations are not my forte.

Today I was working on Project Euler's 34th challenge:

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

And I figured out pretty quickly how to actually calculate the sum of the factorials of the digits (I'm working in Ruby), but what I don't understand is how I'm supposed to know or determine the 'ceiling'. It says "all numbers", as opposed to "all numbers less than N." How can I determine the highest XYZ for which X! + Y! + Z! = XYZ?

I don't want the number itself, since that's part of the challenge, and I'd prefer some helpful hints as opposed to the answer outright, but I can be a little dense sometimes so more is better than less.

Many thanks in advance.

-Andrew

[tomcant]

I see two ways of going about this. The first and simplest is to keep checking consecutive positive integers and printing the result (the sum found so far) until you notice a consistency. This way, you'll eventually arrive at a value that isn't going to change no matter how many more values you check. The second way is to give this a little more thought. The largest digit in any of the numbers to be checked for this quality is clearly 9, and so the largest value we'll be adding to the factorial sum is 9!. When the number of digits in the value to be checked exceeds some limit, 9! won't be large enough to get our factorial sum anywhere close to the number we're checking. We know that 9! = 362880, so there is no point in checking numbers with more than X ammount of digits, since the factorial sum won't ever get that high.

That all comes out clear in my mind, but I'v never been very good at explaining things. I hope it helps.

[kaldrenon]

Thanks for your input!

I had been giving this problem a much higher upper bound than it seems I needed - I initially ran the program at an upper of ten million. Some of PE's problems work with some big numbers, so I decided to play it safe. But a more logical way to deduce the upper bound is to find the first number X of N digits where every digit = 9 and 9! * N < X

Edit: I had to erase some of this post. Being an open forum, all participants have access to it and giving answers to any of the problems is inappropriate.

[Eureka]

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial of their digits.

I figured the maximum I need to check is ...


When I check all the numbers from 3 to the maximum amount, it only adds up to 145. It finds no other number. I can't figure out what's wrong. Help is much appreciated, thanks.

[Tommy137]

case 0:
f = 0;
break;

0! = 1

[Eureka]

Oops. Thank you!

[JPGargoyle]

Hi!

I am presently trying to solve this problem, and one doubt got into me:
how much is 0! ?

By logic I would say it is 0 (zero), and I am using that value, but the windows calculator gives 1 as the result.

Which one is correct?

Thanks a lot.

Best regards.

[David F]

Windows.

[JPGargoyle]

Thanks a lot David F.



Best regards.

[jaap]

Here are two ways of looking at it.

n! / n = (n-1)!
This is true for n>1, and by assuming it is true for n=1 gives 0! = 1!/1 = 1.

n! is the number of ways you can order n things in a row. 1!=1 because you have no choice, there is only one way it can be. Similarly with 0 objects there is only 1 way it can be.

[JPGargoyle]

Thanks for the explanation jaap.

That was cool


Best regards.

[pjt33]

I can't find my copy of Concrete Mathematics to give an exact quote, but it says something to the effect of: 0! = 1 allows nCr = n!/(r!(n-r)!) to work for r = 0 or r = n: this is sufficient reason to define 0! as 1.

[Ikcelaks]

n! is the number of ways you can order n things in a row. 1!=1 because you have no choice, there is only one way it can be. Similarly with 0 objects there is only 1 way it can be.

That's brilliant. I've explained 0!=1 to several people before, and they're always unsatisfied with the "We can define a function however we want, and it works best this way" explanation. But defining factorial directly as the number of permutations of n distinct objects makes it all clear. Now it's just happenstance that the n*(n-1)*... recursion is ever equivalent.

I'm going to steal this for the future.

[piyush]

Somebody please tell me how to find the upper bound for such numbers.

[hk]

Please don't start a new topic for a problem when there exists one already.
Reading the posts above might give you a way to find that out for yourself.

[marioxcc]

Hello. Are the following assumtions valid for problem 34?.

• The factorial of 0 is 1.
• By digits in sum of the factorial of their digits, what is meant is the digits appearing in the smallest decimal representation. For instance, f(1000)=1!+3×0!.

Regards and thanks.

This message is Copyright 2014 Mario Castelán Castro and it is under the Creative Commons Attribution ShareAlike 4.0 International license.

[mpiotte]

Please don't start a new topic for a problem when there exists one already.

[hk]

Hello. Are the following assumtions valid for problem 34?.

• The factorial of 0 is 1.
• By digits in sum of the factorial of their digits, what is meant is the digits appearing in the smallest decimal representation. For instance, f(1000)=1!+3×0!.

Regards and thanks.

This message is Copyright 2014 Mario Castelán Castro and it is under the Creative Commons Attribution ShareAlike 4.0 International license.

You're interpretation is creative, but making it copyrighted doesn't mean it is correct.

[TerranDrop]

EDIT: Wrong remark, I must have been confused after the debugging.

Hello,
I am not sure this is the right section to post my concern, but I have a remark concerning a lack of clarity in problem 34.
The final note states:

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

However, these two numbers need to be included in the final sum for the answer to be right. I spent a lot of time trying to debug my program before just trying to add 3 to my result and it worked... I think the note should be deleted or clarified by stating that 1 and 2 are included.

[pj6444]

However, these two numbers need to be included in the final sum for the answer to be right. I spent a lot of time trying to debug my program before just trying to add 3 to my result and it worked... I think the note should be deleted or clarified by stating that 1 and 2 are included.

That is not the case. I just ran my program and it worked without 1 or 2. There must be a small error in your program that you don't know about.