Project Euler Forum

Hey!
Uh, can sombody please explain problem 20 to me or send me to a site that can.
I have no clue what so ever to the theory, etc.
It would be great if it was in a way that a high school student could understand it.
Cheers.

PS I think I put this in the wrong place

Are we talking about: Find the sum of the digits in the number 100!

Take a simpler example:
5!=5*4*3*2*1=120
The digits of 120 are 1,2 and 0.
Then 1+2+0=3.
The sum of the digits of 5! is 3.

Oh now I see
easy
Thanks mate

I'm confused - I've run my code for this example and it works for the test answer of 5!, the answer being sum of 120 which equals 3. However I'm running into problems when I do it for 100. I'm pretty sure it's something to do with accuracy of scientific numbers as if I run my code in C#, using a double, it returns a value of 60. In desperation I've tried windows calculator, which appears to return a better populated scientific number , which results in a sum of 153. Any pointers would be gratefully appreciated.

100! [asymp] 9.33262154 × 10¹⁵⁷

Which is more than 64 bit precision, so you'll need to do it in another way...

Since the answer is 157 digits long, perhaps you can represent it as a an array/vector of 157 digits.

Thanks for the pointer, just shows why I need to do these things!

stijn263 wrote:100! [asymp] 9.33262154 × 10¹⁵⁷

Which is more than 64 bit precision, so you'll need to do it in another way...

Since the answer is 157 digits long, perhaps you can represent it as a an array/vector of 157 digits.

9.33262154 × 10¹⁵⁷ is the answer I get. when I do 100!. But I can not understand why it ends as a decimal number when no decimals are involved in 100!. Can somebody explain?

Roxxor wrote:9.33262154 × 10¹⁵⁷ is the answer I get. when I do 100!. But I can not understand why it ends as a decimal number when no decimals are involved in 100!. Can somebody explain?

100! is an integer; it has no decimals.
But it is a very large integer, containing 158 digits.
Most calculators, programs etc cannot display or print such very large numbers.
Instead, they print something like 9.33262154 × 10¹⁵⁷ which is only an approximation to the actual value, showing in a compact form the first 9 significant digits of the number as well as the order of its magnitude (the number of its digits).

9.33262154 × 10¹⁵⁷ = 933262154 × 10¹⁴⁹ and now, there are no decimals!
Of course, it still only an approximate value for 100!.
What it means is that 100! is an integer which starts with 933262154... (followed by 149 more digits).

A bigger calculator, would tell you that 100! is approximately equal to 9.3326215443944152681699238856 × 10¹⁵⁷
which is equal to 93326215443944152681699238856 × 10¹²⁹,
So, 100! is an integer starting with 93326215443944152681699238856... (and followed by 129 more digits).

However, that's still an approximation for the value of 100!.
It is a better approximation (since you now have more significant digits than before), but you still don't have the remaining 129 digits.

If you're using C# 2010, you can use the BigInteger class (you'll need to import System.Numerics).

I should mention that while BigInteger will work fine for this problem, it's really slow compared to the normal numeric types. Don't overuse it.

EDIT: BTW, I solved this one by writing my own large number logic as stijn263 suggested. It's a fun exercise if you like that sort of thing.

Hi everyone

The answer field on the problem page have a max length of 30. Its a page problem or mine?

Yours.

nvno wrote:Hi everyone

The answer field on the problem page have a max length of 30. Its a page problem or mine?

Problem 020 (View Problem)

You only need the last ten digits, not all of them.

elendiastarman wrote:

nvno wrote:Hi everyone

The answer field on the problem page have a max length of 30. Its a page problem or mine?

Problem 020 (View Problem)

You only need the last ten digits, not all of them.

Are you sure?

Bah, I was thinking of a different problem. [smacks forehead]

Restatement: You only need the SUM of the digits...not all of them.

As usual there is a very elegant way to solve this problem.

To be honest, I can't remember exactly how I did it but I solely program in C++ (it's the only language I know) and I remember that I found a very handy C++ solution in the forum once I solved it.

Not giving it away but think about school and how you learned to multiply in your head or by pen and paper. Now try to learn the computer to do it in the same way. For instance, when you were asked to do 28*56, you would do it step by step.

I didn't think of creating big numbers this way but it has helped me in alot of problems on this site. Until now I never used BigInt, not that I have anything against it, it's just fun that you can solve problems this way.

I'm trying to solve Problem #20 and I already got a way to get the answer of n!. However, I can't figure out how to get the sum of digits within the n! answer. In the problem, the sample showed that 10! = 3628800 and adding the digit of those numbers equals to 27. Before I try to get the sum of digits of 100!, I need to figure out how to program such a thing.

I first thought of using strings to convert one digit of the result of n! at a time, revert back to an integer, and add the digit to another variable consisting the final answer. However, I have no clue on how to do this.

I'm using C++. I don't want the answer to Problem #20 though, just a way to get to the desired result with 10!.

That really depends on how you're storing the answer of 100!. For example, if you wanted to sum the digits of an int N, consider N%10 and N/10 and how you could use that to find the sum you're looking for.

However, since 100! doesn't fit in an int, that doesn't apply. Since storing 100! is the main point of this problem, that's where you need to start.

Your post was related to Problem 020 and was moved to its proper topic. The Suggestion & FAQ forum is not designed for this kind of post.

100! will fit in a long long integer, but you will have x.xxxxxxe+xx as your answer

No, it doesn't - a long long can only store numbers up to 2^63, which won't fit 21! let alone 100!. If you meant a long double, that's even worse as it can only store integers up to about 2^53 before drastically rounding anything bigger.

Try calculating 21! in a long long and then print out the result - you'll get a negative number, meaning you've overflowed the maximum.

As mentioned earlier in this thread, in-built data types aren't going to solve this one for you - you'll need to write an algorithm to perform the factorial like you would do with pen and paper.