Problem 20 of Project Euler

Hello there, I have a question concerning my code to solve the following Problem of Project Euler (https://projecteuler.net/problem=20)

*n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!*

I used the following code to solve the problem (I know this is not highly sophisticated and I already saw various other solutions but I would like to make it work this way)

For all "test values" that I tried the script works just fine and gives the correct answer, though for the value of 100 it gives 683 instead of the correct 648. Can you help me find the reason why?

Thank you!

Sum=0;
Prod=1;
for i=1:20
  Prod=Prod*i;
end
StrProd=num2str(Prod,'%.0f')
for i=1:length(StrProd)
      Sum=Sum+str2num(StrProd(i)); 
end

[Magdy Saleh]

I think this is because of the floating point representation of the number. 100! = 9.3326e+15. This number is so big that the computer stores an approximation of that number, not the exact number. As a result, when you come to sum up the digits, the lower digits might not be exact and that will lead to the inaccuracy. I encourage you to read more about floating point errors and understand the significance of the fact that eps(9.3326e+15) = 1.2194e+142.

[Geoff Hayes]

Jonas - when you compute 100! via your above code, what does Prod look like before and after you convert it to a string? It could be that the number does not convert well to a string (see num2str for details).

[Jonas Hzf]

Hello Geoff, before converting Prod it has the value 9.3326e+157 afterwarts StrProd has the value 93326215443944102188325606108575267240944254854960571509166910400407995064242937148632694030450512898042989296944474898258737204311236641477561877016501813248. Your suggestion goes into a similar direction like Magdys I guess.

Maybe it is really some kind of error in the approximation of the float value. But than at least I know that the general "logic" of my script was correct ;)

[Geoff Hayes]

Jonas - you can see from the above string that this is the wrong number. Since your 100! includes 100, 90, 80, 70, ..., 20, and 10, then I would expect to see this number terminating with 11 zeros.

Answer 1

[Michiele Ogbagabir]

If you do

    class(prod)

you will see that it is a double data type. Double types in matlab have 16 decimal digits precision and 100! is clearly more than that. So instead of the default double value, initialize your prod variable as a symbolic type. To convert your symbolic type to char array, use

char(prod)

instead of

num2str(prod)

and that should give you the right answer.

[Jonas Hzf]

Hello Michielle, thank you for your answer!

Unfortunately when I change num2str(Prod) to char(Prod)

for i=1:100
    Prod=Prod*i;
end

StrProd=char(Prod)

it outputs only

 []

instead of the array

[Geoff Hayes]

Jonas - do you have the Symbolic Toolbox (which is what I think that Michiele is hinting that you use).

[Jonas Hzf]

Okay I see now my fault I did not get the "initializing as symbolic type" part at first!

I did now like you said Michiele and it worked out perfectly. Thank you very much!

[Geoff Hayes]

The Symbolic Toolbox allows you to do High Precision Calculations which might be necessary for this problem.

[Michiele Ogbagabir]

I am sorry. I should have clarified that part. Thanks for clarifying Goeff. Glad it is working now.

Answer 2

[Geoff Hayes]

Jonas - I wonder if this problem is trying to get you to come up with an alternative (to a for loop) algorithm to find the sum of the digits in 100!. For example, if I am concerned with 20!, then I have the numbers

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Are there any numbers in the above list that I can exclude? The 1 has no impact so it can be removed. The 10 only appends a zero to the end of the product so it has no impact on the sum. So I can reduce my list of numbers to

 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20

20 is the same as 10*2 and if I ignore the 10 (for the same previously stated reason) then my list becomes

 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 2

4*5 is 20 so I can replace these two numbers with 2

 2 3 2 6 7 8 9 11 12 13 14 15 16 17 18 19 2

14*15 is 210 (=21*10) so my list now becomes

 2 3 2 6 7 8 9 11 12 13 21 16 17 18 19 2

So you may be able to do something similar for 100! Remove any numbers that have no impact on the sum of the digits (1,10,100) and then replace all the others that are divisible by 10: (20,30,40,...,90) with (2,3,4,...,9). You can then replace all pairs of numbers whose product is 10: (4,5), (14,15), ..., (94,95) with an equivalent like (2), (21), ..., (893). This might result in a list of numbers whose product is more manageable and one that you can then convert to correctly to a string.

Please note that this is not guaranteed to work and just provides an alternative means to perhaps finding the solution.

[Jonas Hzf]

Hi Geoff, interesting approach!

This might be a way to solve the issue, the problems are in general intentionally open I think for multiple solution opportunities because they are also open for the platform/language in which you are programming.

The other solution I found for Matlab is the following

disp(sum(str2num(strread(char(prod(sym(1:100))),'%c'))));