Project Euler 20
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 4
 Joined: Wed Aug 08, 2007 2:28 pm UTC
Project Euler 20
I'm working on a solution for problem 20 on Project Euler. The problem is to find the sum of the digits in 100!. Now, I can only assume that they don't actually expect me to compute 100!, though I have brute forced problems like this in the past. I would really rather understand the theory behind solving this problem, if anyone can point me in the right direction. I'm really interested in learning, so feel free to throw a little theory my way.
Re: Project Euler 20
Recursive solution? Find the base case (the simplest problem of this format). For example, find the sum of the digits of 1!, then 2! then 3!. try to find a pattern. Write some formulas. The recursive solution to an iterative problem may not be immediately apparent.
fyrenwater wrote:Oh dear God, I just imagined this horrible scenario of a psychotic nonpeopleperson running around, trying to steal the peopleperson section of peoplepeoples' brains to implant into their own brain.
 Alpha Omicron
 Posts: 2765
 Joined: Thu May 10, 2007 1:07 pm UTC
Re: Project Euler 20
Just a guess: divisibility rules?
nevermind, Aluminus' way is more fun/fruitful.
nevermind, Aluminus' way is more fun/fruitful.
Here is a link to a page which leverages aggregation of my tweetbook social blogomedia.
 Anpheus
 I can't get any worse, can I?
 Posts: 860
 Joined: Fri Nov 16, 2007 10:38 pm UTC
 Location: A privileged frame of reference.
Re: Project Euler 20
Is there a pattern to the digits of n!?
For example, 10! is:
1*2*3*4*5*6*7*8*9*10
Well, we can eliminate things which produce no impact, for example, 1, and 10. Because ten appends a zero to the result, we can ignore it.
Likewise, if we do 20!, we have that series multiplied by 11*12*13*14*15*16*17*18*19*20, the 20 appends a zero and multiplies by two.
So just in 20!, with a few seconds of work I managed to reduce the sum of the digits from:
The sum of the digits in 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 to
The sum of the digits in 2*3*4*5*6*7*8*9*11*12*13*14*15*16*17*18*19*2
Stuff like that. Use any application of number theory you can think of that wherein multiplying by a certain number produces a certain other number.
I can tell you off hand that the sum of the digits will be a multiple of 3, for example, because in base 10, the sum of the digits of any number multiplied by 3 is itself a multiple of 3.
For example, 10! is:
1*2*3*4*5*6*7*8*9*10
Well, we can eliminate things which produce no impact, for example, 1, and 10. Because ten appends a zero to the result, we can ignore it.
Likewise, if we do 20!, we have that series multiplied by 11*12*13*14*15*16*17*18*19*20, the 20 appends a zero and multiplies by two.
So just in 20!, with a few seconds of work I managed to reduce the sum of the digits from:
The sum of the digits in 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 to
The sum of the digits in 2*3*4*5*6*7*8*9*11*12*13*14*15*16*17*18*19*2
Stuff like that. Use any application of number theory you can think of that wherein multiplying by a certain number produces a certain other number.
I can tell you off hand that the sum of the digits will be a multiple of 3, for example, because in base 10, the sum of the digits of any number multiplied by 3 is itself a multiple of 3.
Spoiler:

 Posts: 4
 Joined: Wed Aug 08, 2007 2:28 pm UTC
Re: Project Euler 20
Aluminus wrote:Recursive solution? Find the base case (the simplest problem of this format). For example, find the sum of the digits of 1!, then 2! then 3!. try to find a pattern. Write some formulas. The recursive solution to an iterative problem may not be immediately apparent.
i feel like any solution i might try to find in that way would inevitably be the long way around creating, essentially, my own bignum implementation. which is fine, honestly, but i dont feel like that is the approach that they are expecting from me. i know that any approach to the right solution is fine, but id rather be able to solve it with a little number theory.
Anpheus wrote:So just in 20!, with a few seconds of work I managed to reduce the sum of the digits from:
The sum of the digits in 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 to
The sum of the digits in 2*3*4*5*6*7*8*9*11*12*13*14*15*16*17*18*19*2
that is actually very helpful, but youll understand if i dont feel entirely relieved. no "long" or "long long" is going to be able to hold the actual number, so i feel like creating a rough bignum application is going to be my only option, which i DONT like.
Re: Project Euler 20
I only said recursive function because I am frantically studying for my C++ final But the divisiblebythree hint could really help
F(1)=1 (1)
F(2)=1 (2)
F(3)=1 (6)
F(4)=2 (24)
...
PROFIT
Hint: for a cheapanddirty solution, use anexcel spreadsheet your favourite formula table and graphdrawing software.
Riemann Sum anybody? Damn you Differential Equations! :shakefist:
F(1)=1 (1)
F(2)=1 (2)
F(3)=1 (6)
F(4)=2 (24)
...
PROFIT
Hint: for a cheapanddirty solution, use an
Riemann Sum anybody? Damn you Differential Equations! :shakefist:
fyrenwater wrote:Oh dear God, I just imagined this horrible scenario of a psychotic nonpeopleperson running around, trying to steal the peopleperson section of peoplepeoples' brains to implant into their own brain.
 Anpheus
 I can't get any worse, can I?
 Posts: 860
 Joined: Fri Nov 16, 2007 10:38 pm UTC
 Location: A privileged frame of reference.
Re: Project Euler 20
No no, you see, you should do what I did, but keep using number theoretic properties in Base 10 to reduce what you have to compute.
Here are some other examples, we can factor out two numbers that multiply to become a constant multiplied by ten, and substitute in the constant for both numbers.
In 1*2*3*4*5*6*7*8*9*10:
We remove the 1, the 10, the 5, and the 2:
3*4*6*7*8*9
In 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20:
3*4*6*7*8*9*11*12*13*14*15*16*17*18*19*2
4 * 15 = 60 (and this can be used multiple times, bear in mind, 4 * 15 * 25 * 35...)
3*6*7*8*9*11*12*13*14*16*17*18*19*2*6
Can you think of any other reductions?
Here are some other examples, we can factor out two numbers that multiply to become a constant multiplied by ten, and substitute in the constant for both numbers.
In 1*2*3*4*5*6*7*8*9*10:
We remove the 1, the 10, the 5, and the 2:
3*4*6*7*8*9
In 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20:
3*4*6*7*8*9*11*12*13*14*15*16*17*18*19*2
4 * 15 = 60 (and this can be used multiple times, bear in mind, 4 * 15 * 25 * 35...)
3*6*7*8*9*11*12*13*14*16*17*18*19*2*6
Can you think of any other reductions?
Spoiler:
Re: Project Euler 20
Since x=SOD(x) (mod 9), the answer (divided by 10^54 to remove zeroes) must be a multiple of 9.
(Proof here)
By the same logic, SOD(100!) is divisible by 99.
Hope this helps!
(Proof here)
By the same logic, SOD(100!) is divisible by 99.
Hope this helps!
Last edited by quintopia on Wed Dec 05, 2007 3:50 am UTC, edited 1 time in total.
 imatrendytotebag
 Posts: 152
 Joined: Thu Nov 29, 2007 1:16 am UTC
Re: Project Euler 20
Well, something I noticed:
The sum of the digits in 4! (24) is 6. The sum of the digits in 5! (120) is 3, which is the same as the sum of the digits in 5*6 (30). In other words:
The sum of the digits in 5*4! is the same as the sum of the digits in 5*(the sum of the digits in 4!).
Similarly the sum of the digits in 6*5! (= 720, sum = 9) is the same as the sum of the digits in 6*(sum of digits in 5!) (= 6*3 = 18, sum = 9).
Sum in 7*6! (= 5040, sum = 9), 7*(sum in 6!) (= 7*9 = 63, sum = 9)
Sum in 8*7! (= 40320 = 9), 8*(sum in 7!) (= 8*9 = 72, sum = 9)
Dunno if that idea helps at all... a few more data points to help spot a pattern perhaps:
9! = 3628800 (sum = 27 (pattern breaks down))
10! = 3628800 (sum = 27)
11! = 39916800 (sum = 36)
12! = 479001600 (sum = 27)
happy figuring..
The sum of the digits in 4! (24) is 6. The sum of the digits in 5! (120) is 3, which is the same as the sum of the digits in 5*6 (30). In other words:
The sum of the digits in 5*4! is the same as the sum of the digits in 5*(the sum of the digits in 4!).
Similarly the sum of the digits in 6*5! (= 720, sum = 9) is the same as the sum of the digits in 6*(sum of digits in 5!) (= 6*3 = 18, sum = 9).
Sum in 7*6! (= 5040, sum = 9), 7*(sum in 6!) (= 7*9 = 63, sum = 9)
Sum in 8*7! (= 40320 = 9), 8*(sum in 7!) (= 8*9 = 72, sum = 9)
Dunno if that idea helps at all... a few more data points to help spot a pattern perhaps:
9! = 3628800 (sum = 27 (pattern breaks down))
10! = 3628800 (sum = 27)
11! = 39916800 (sum = 36)
12! = 479001600 (sum = 27)
happy figuring..
Hey baby, I'm proving love at nth sight by induction and you're my base case.
Re: Project Euler 20
93326215443944152681699238856266700490715968264381621
46859296389521759999322991560894146397615651828625369
7920827223758251185210916864000000000000000000000000
Add!
Honestly, I'm not sure how you'd do this one without some bruteforce method...
46859296389521759999322991560894146397615651828625369
7920827223758251185210916864000000000000000000000000
Add!
Honestly, I'm not sure how you'd do this one without some bruteforce method...
 thoughtfully
 Posts: 2253
 Joined: Thu Nov 01, 2007 12:25 am UTC
 Location: Minneapolis, MN
 Contact:
Re: Project Euler 20
You might be able to do something with the Gamma Function, which is a sortof generalized factorial (domain contains nonintegers, even complex numbers!).
Also, the series of sum of the first n whole number is sometimes referred to as the triangular numbers, which contain a lot of nifty connections to binomial coefficients and Pascal's Triangle.
I bet the answer lies in Pascal's Triangle, myself.
EDIT: Oops! That last part was for the wrong problem. Buggers!
Also, the series of sum of the first n whole number is sometimes referred to as the triangular numbers, which contain a lot of nifty connections to binomial coefficients and Pascal's Triangle.
I bet the answer lies in Pascal's Triangle, myself.
EDIT: Oops! That last part was for the wrong problem. Buggers!
 gmalivuk
 GNU Terry Pratchett
 Posts: 26765
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Project Euler 20
I strongly doubt the gamma function is going to make anything easier, seeing as it is really quite a bit more complicated than the factorial, and considering that we don't care at all about noninteger values. Also, I have a hunch that triangular numbers aren't going to help us much, either, seeing as we're multiplying rather than adding.
Probably, for something small like 100!, if you insist on not using brute force, one of the methods already suggested would work.
I find the longerterm trends interesting, though. If f(n) is the (base10) sum of the digits of n!, anyone have any ideas of a smooth function of n about which f(n) will "congregate"? For instance, a plot of f(n)/log_{10}n *looks* to be pretty close to linear:
but when dividing by n to check the slope, it turns out not to be approaching any constant:
Probably, for something small like 100!, if you insist on not using brute force, one of the methods already suggested would work.
I find the longerterm trends interesting, though. If f(n) is the (base10) sum of the digits of n!, anyone have any ideas of a smooth function of n about which f(n) will "congregate"? For instance, a plot of f(n)/log_{10}n *looks* to be pretty close to linear:
but when dividing by n to check the slope, it turns out not to be approaching any constant:
Re: Project Euler 20
quintopia wrote:Since x=SOD(x) (mod 9), the answer (divided by 10^54 to remove zeroes) must be a multiple of 9.
(Proof here)
By the same logic, SOD(100!) is divisible by 99.
Hope this helps!
i believe that 100! divisible by 10^24 but not 10^54, because the the greatest exponent, x, such that 5^x divide 100! is floor(100/5)+floor(100/25)=24.
i dont think that x = SOD(x) (mod 11).
yep this idea reduce number of possible value of SOD(100!),
SOD(100!) < SOD(10^99) < 99*9 = 891
so we search a three digit number less than 891 that divisible by 9.
it would be so easy if the question is SOD(SOD(100!)): because that positive number < 18 and divisible by 9, it much be 9.
while moronic idle do something (stupid).
Re: Project Euler 20
24 is correct. my calculations were off.
100 in base 5 = 400
4004=341
341/4=44
44 in base 10 = 24
W^5
100 in base 5 = 400
4004=341
341/4=44
44 in base 10 = 24
W^5
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Project Euler 20
@the OP: use brute force. The crappy little implementation that I wrote out in haskell took less time to execute than it takes me to fart.
As I see it, we've got two relevant quantities that we can count pretty easily: the number of digits and the number of trailing 0's.
number of digits
Stirling's says
n! ~ (2*pi*n)^{1/2}n^{n}e^{n}
where ~ is "approximately equals", so we have about
log_{10}((2*pi*n)^{1/2}n^{n}e^{n})
=^{1}/_{2}log_{10}(2*pi) + (n+^{1}/_{2})log_{10}(n) nlog_{10}(e)
digits in total.
number of trailing zeros
We have that 10^{k}n! iff 5^{k}n!. How to find the largest k? With a bit of thought, you can see that the following works.
The highest power of 5 that divides n! = sum(i=1 to infinity, floor(n/5^{i}))
If we forget the floors then we have a simple geometric series whose sum is n/4. This will be a (sometimes very) high estimate. For a different way, we can calculate
The highest power of 5 that divides (5^{k})! = 5^{k}/4 1/4
but this isn't much better (though is tells us our high estimate isn't too bad for powers of 5). Also
The highest power of 5 that divides (5^{k}1)! = 5^{k}/4 1/4 k
which is the worst case I think. So we can guess that
n/4 1/4 log_{5}n < number of trailing 0's in n! < n/4.
it all comes together
My guess is as follows. Start with the total number of digits, subtract the number of trailing 0's and multiply by 4.5 (because assuming a uniform distribution of digits is the laziest way to go (I know its wrong for the first digit, but who cares?)).
So, let C = ^{1}/_{2}log_{10}(2*pi) and my guess is
^{9}/_{2} ( C + (n+^{1}/_{2})log_{10}(n) nlog_{10}(e)  n/4) < f(n) < ^{9}/_{2} ( C + (n+^{1}/_{2})log_{10}(n) nlog_{10}(e)  n/4 + log_{5}n +^{1}/_{4})
Be interested to see how that goes vs the real data. You can see that the growth is going to be nlog(n), which looks about right for your graphs.
Edit: moved some ^{1}/_{4}'s around.
gmalivuk wrote:If f(n) is the (base10) sum of the digits of n!, anyone have any ideas of a smooth function of n about which f(n) will "congregate"?
As I see it, we've got two relevant quantities that we can count pretty easily: the number of digits and the number of trailing 0's.
number of digits
Stirling's says
n! ~ (2*pi*n)^{1/2}n^{n}e^{n}
where ~ is "approximately equals", so we have about
log_{10}((2*pi*n)^{1/2}n^{n}e^{n})
=^{1}/_{2}log_{10}(2*pi) + (n+^{1}/_{2})log_{10}(n) nlog_{10}(e)
digits in total.
number of trailing zeros
We have that 10^{k}n! iff 5^{k}n!. How to find the largest k? With a bit of thought, you can see that the following works.
The highest power of 5 that divides n! = sum(i=1 to infinity, floor(n/5^{i}))
If we forget the floors then we have a simple geometric series whose sum is n/4. This will be a (sometimes very) high estimate. For a different way, we can calculate
The highest power of 5 that divides (5^{k})! = 5^{k}/4 1/4
but this isn't much better (though is tells us our high estimate isn't too bad for powers of 5). Also
The highest power of 5 that divides (5^{k}1)! = 5^{k}/4 1/4 k
which is the worst case I think. So we can guess that
n/4 1/4 log_{5}n < number of trailing 0's in n! < n/4.
it all comes together
My guess is as follows. Start with the total number of digits, subtract the number of trailing 0's and multiply by 4.5 (because assuming a uniform distribution of digits is the laziest way to go (I know its wrong for the first digit, but who cares?)).
So, let C = ^{1}/_{2}log_{10}(2*pi) and my guess is
^{9}/_{2} ( C + (n+^{1}/_{2})log_{10}(n) nlog_{10}(e)  n/4) < f(n) < ^{9}/_{2} ( C + (n+^{1}/_{2})log_{10}(n) nlog_{10}(e)  n/4 + log_{5}n +^{1}/_{4})
Be interested to see how that goes vs the real data. You can see that the growth is going to be nlog(n), which looks about right for your graphs.
Edit: moved some ^{1}/_{4}'s around.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Project Euler 20
This is a plot of f(n) divided by jestingrabbit's formula for the number of digits minus the number of trailing zeros. As expected, it converges to 4.5.
(I took an average of the upper and lower estimates, but it makes no difference when n is large enough)
(I took an average of the upper and lower estimates, but it makes no difference when n is large enough)
In the spirit of taking things too far  the 5x5x5x5x5 Rubik's Cube.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Project Euler 20
Cool. My final inequality is obviously crap (the "uniform distribution of digits" assumption introduces too much error to be true all but occasionally), but the estimate and the reasoning behind it seems to be born out by the data.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Project Euler 20
I hate to be obvious (and probably completely wrong) but isnt the answer 9, since any multiple of 9's digits sum to 9?
Edit, no forget that, I'm think of repeatedly summed, ignore me
Edit, no forget that, I'm think of repeatedly summed, ignore me
 Alpha Omicron
 Posts: 2765
 Joined: Thu May 10, 2007 1:07 pm UTC
Re: Project Euler 20
See, I told you it was divisibility.
Here is a link to a page which leverages aggregation of my tweetbook social blogomedia.
 BaldAdonis
 Posts: 81
 Joined: Fri Nov 24, 2006 11:32 pm UTC
Re: Project Euler 20
glup.up wrote:yep this idea reduce number of possible value of SOD(100!),
SOD(100!) < SOD(10^99) < 99*9 = 891
so we search a three digit number less than 891 that divisible by 9.
it would be so easy if the question is SOD(SOD(100!)): because that positive number < 18 and divisible by 9, it much be 9.
Careful around here:
SOD(SOD(100!)) is not necessarily less than 18.
You don't want SOD(10^{99}), because that's pretty clearly just 1. You want max_{x<1099}SOD(x)=99*9=891. But really, a closer bound should be log_{10} of Stirling's estimate, which is pretty good when n is 100 (so much so that it gets 157.97 for the number of digits; there are 158). Taking off the trailing zeros, which we know are 24, and we get SOD(100!)<134*9=1206.
Spoiler:
Re: Project Euler 20
I spent about 3 hours making a formula/computational algorithm. It didn't really go anywhere though, because actually calculating with it would take longer than the brute force way. What I came up with is like a brute forcier way. I kind of want my 3 hours back now...
Re: Project Euler 20
Well I just used haskell and it executes under 2 seconds with the ghc interpreter:
Spoiler:
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Project Euler 20
How did you end up reviving a thread which is almost exactly 1 year old?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Who is online
Users browsing this forum: No registered users and 9 guests