Problem 20 of Project Euler

5 次查看（过去 30 天）
Jonas Hzf
Jonas Hzf 2018-7-11
评论： Michiele Ogbagabir 2018-7-11
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 个评论
显示 2更早的评论
Jonas Hzf
Jonas Hzf 2018-7-11
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
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
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 个评论
显示 3更早的评论
Geoff Hayes
Geoff Hayes 2018-7-11
The Symbolic Toolbox allows you to do High Precision Calculations which might be necessary for this problem.
Michiele Ogbagabir
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
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.
  1 个评论
Jonas Hzf
Jonas Hzf 2018-7-11
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'))));

请先登录，再进行评论。

类别

在 Help Center 和 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