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
4 个评论
Magdy Saleh
2018-7-11
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
2018-7-11
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
2018-7-11
Geoff Hayes
2018-7-11
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.
采纳的回答
Michiele Ogbagabir
2018-7-11
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.
5 个评论
Geoff Hayes
2018-7-11
编辑：Geoff Hayes
2018-7-11
Jonas - do you have the Symbolic Toolbox (which is what I think that Michiele is hinting that you use).
Geoff Hayes
2018-7-11
The Symbolic Toolbox allows you to do High Precision Calculations which might be necessary for this problem.
Michiele Ogbagabir
2018-7-11
I am sorry. I should have clarified that part. Thanks for clarifying Goeff. Glad it is working now.
更多回答（1 个）
Geoff Hayes
2018-7-11
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.
类别
在 帮助中心 和 File Exchange 中查找有关 Number Theory 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
