Project Euler 20

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

authorblues
Posts: 4
Joined: Wed Aug 08, 2007 2:28 pm UTC

Project Euler 20

Postby authorblues » Wed Dec 05, 2007 2:22 am UTC

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.

User avatar
Aluminus
Posts: 1337
Joined: Sun Nov 04, 2007 7:51 pm UTC
Location: View From Space

Re: Project Euler 20

Postby Aluminus » Wed Dec 05, 2007 2:25 am UTC

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 non-people-person running around, trying to steal the people-person section of people-peoples' brains to implant into their own brain.

User avatar
Alpha Omicron
Posts: 2765
Joined: Thu May 10, 2007 1:07 pm UTC

Re: Project Euler 20

Postby Alpha Omicron » Wed Dec 05, 2007 2:26 am UTC

Just a guess: divisibility rules?

nevermind, Aluminus' way is more fun/fruitful.
Here is a link to a page which leverages aggregation of my tweetbook social blogomedia.

User avatar
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

Postby Anpheus » Wed Dec 05, 2007 2:33 am UTC

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.
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

authorblues
Posts: 4
Joined: Wed Aug 08, 2007 2:28 pm UTC

Re: Project Euler 20

Postby authorblues » Wed Dec 05, 2007 2:38 am UTC

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.

User avatar
Aluminus
Posts: 1337
Joined: Sun Nov 04, 2007 7:51 pm UTC
Location: View From Space

Re: Project Euler 20

Postby Aluminus » Wed Dec 05, 2007 2:43 am UTC

I only said recursive function because I am frantically studying for my C++ final :!: But the divisible-by-three hint could really help
F(1)=1 (1)
F(2)=1 (2)
F(3)=1 (6)
F(4)=2 (24)
...
PROFIT

Hint: for a cheap-and-dirty solution, use an excel spreadsheet your favourite formula table and graph-drawing software.

Riemann Sum anybody? Damn you Differential Equations! :shakefist:
fyrenwater wrote:Oh dear God, I just imagined this horrible scenario of a psychotic non-people-person running around, trying to steal the people-person section of people-peoples' brains to implant into their own brain.

User avatar
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

Postby Anpheus » Wed Dec 05, 2007 2:48 am UTC

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?
Spoiler:

Code: Select all

  /###\_________/###\
  |#################|
  \#################/
   |##┌         ┐##|
   |##  (¯`v´¯)  ##|
   |##  `\ ♥ /´  ##|
   |##   `\¸/´   ##|
   |##└         ┘##|
  /#################\
  |#################|
  \###/¯¯¯¯¯¯¯¯¯\###/

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Project Euler 20

Postby quintopia » Wed Dec 05, 2007 3:14 am UTC

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!
Last edited by quintopia on Wed Dec 05, 2007 3:50 am UTC, edited 1 time in total.

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: Project Euler 20

Postby imatrendytotebag » Wed Dec 05, 2007 3:38 am UTC

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..
Hey baby, I'm proving love at nth sight by induction and you're my base case.

User avatar
Hamorad
Posts: 105
Joined: Fri Sep 29, 2006 7:14 pm UTC

Re: Project Euler 20

Postby Hamorad » Wed Dec 05, 2007 3:48 am UTC

93326215443944152681699238856266700490715968264381621
46859296389521759999322991560894146397615651828625369
7920827223758251185210916864000000000000000000000000

Add!

Honestly, I'm not sure how you'd do this one without some brute-force method...

User avatar
thoughtfully
Posts: 2253
Joined: Thu Nov 01, 2007 12:25 am UTC
Location: Minneapolis, MN
Contact:

Re: Project Euler 20

Postby thoughtfully » Wed Dec 05, 2007 3:57 am UTC

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!
Image
Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.
-- Antoine de Saint-Exupery

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26765
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Project Euler 20

Postby gmalivuk » Wed Dec 05, 2007 5:27 am UTC

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 longer-term trends interesting, though. If f(n) is the (base-10) 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)/log10n *looks* to be pretty close to linear:
fnoverlogn.jpg
fnoverlogn.jpg (8.43 KiB) Viewed 8962 times


but when dividing by n to check the slope, it turns out not to be approaching any constant:
fnovernlogn.jpg
fnovernlogn.jpg (10.54 KiB) Viewed 8961 times
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
glup.up
Posts: 15
Joined: Tue Nov 20, 2007 9:52 am UTC

Re: Project Euler 20

Postby glup.up » Wed Dec 05, 2007 8:00 am UTC

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).

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Project Euler 20

Postby quintopia » Wed Dec 05, 2007 8:31 am UTC

24 is correct. my calculations were off.

100 in base 5 = 400
400-4=341
341/4=44
44 in base 10 = 24
W^5

User avatar
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

Postby jestingrabbit » Wed Dec 05, 2007 9:28 am UTC

@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.

gmalivuk wrote:If f(n) is the (base-10) 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/2nne-n

where ~ is "approximately equals", so we have about


log10((2*pi*n)1/2nne-n)

=1/2log10(2*pi) + (n+1/2)log10(n) -nlog10(e)


digits in total.


number of trailing zeros

We have that 10k|n! iff 5k|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/5i))

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 (5k)! = 5k/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 (5k-1)! = 5k/4 -1/4 -k

which is the worst case I think. So we can guess that

n/4 -1/4 -log5n < 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/2log10(2*pi) and my guess is

9/2 ( C + (n+1/2)log10(n) -nlog10(e) - n/4) < f(n) < 9/2 ( C + (n+1/2)log10(n) -nlog10(e) - n/4 + log5n +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.

User avatar
Mouffles
Posts: 60
Joined: Fri Jul 06, 2007 10:02 am UTC
Location: New Zealand

Re: Project Euler 20

Postby Mouffles » Wed Dec 05, 2007 12:09 pm UTC

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.
fnoverndigits.JPG
fnoverndigits.JPG (24.42 KiB) Viewed 8899 times

(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.

User avatar
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

Postby jestingrabbit » Wed Dec 05, 2007 12:31 pm UTC

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.

User avatar
Shinju
Posts: 105
Joined: Wed Aug 22, 2007 8:33 am UTC
Location: Newcastle
Contact:

Re: Project Euler 20

Postby Shinju » Wed Dec 05, 2007 12:59 pm UTC

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 :)

User avatar
Alpha Omicron
Posts: 2765
Joined: Thu May 10, 2007 1:07 pm UTC

Re: Project Euler 20

Postby Alpha Omicron » Wed Dec 05, 2007 1:38 pm UTC

See, I told you it was divisibility.
Here is a link to a page which leverages aggregation of my tweetbook social blogomedia.

User avatar
BaldAdonis
Posts: 81
Joined: Fri Nov 24, 2006 11:32 pm UTC

Re: Project Euler 20

Postby BaldAdonis » Wed Dec 05, 2007 9:56 pm UTC

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(1099), because that's pretty clearly just 1. You want maxx<1099SOD(x)=99*9=891. But really, a closer bound should be log10 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:
134*5=670 would give you a good estimate of SOD(100!), multiplying by 5 since we've removed most of the zeros (there are still some, but it works out closer this way) and 5 is the average of the remaining digits. Also, begs an interesting question, how many non-trailing zeros are there in the expansion of n! ?

As it turns out, SOD(SOD(100!))=18.

Also,
quintopia wrote:By the same logic, SOD(100!) is divisible by 99.
doesn't follow. Maybe 9*9.
SOD(100!)=648=23*34 for anyone not interested in sums.

saus
Posts: 176
Joined: Fri Nov 02, 2007 12:19 am UTC

Re: Project Euler 20

Postby saus » Fri Dec 07, 2007 4:28 am UTC

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...

grom
Posts: 11
Joined: Thu Aug 07, 2008 12:28 pm UTC

Re: Project Euler 20

Postby grom » Mon Dec 08, 2008 4:46 am UTC

Well I just used haskell and it executes under 2 seconds with the ghc interpreter:

Spoiler:

Code: Select all

import Data.Char

factorial :: Integer -> Integer
factorial 1 = 1
factorial n = n * factorial (n - 1)

main = print $ sum . map (\c -> digitToInt c) . show $ factorial 100

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Project Euler 20

Postby skeptical scientist » Mon Dec 08, 2008 5:36 am UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests