Factorial of 1000000

[Dreamlax]

It took Mathematica 29 seconds to find out this HUGE number... I saved it as raw text and it's 5.5MB, so that's a number about 10^570000000 digits long isn't it? I zipped it up and was going to post it but it only compressed to around 2.5MB which is still too large.

[DavidHooper]

Hehe, well post it up on some webspace somewhere.

Let me see, I bet it ends in a minimum of 21 0s. Can't think of anything else I know about it tho

Anyone?

[Dreamlax]

It ends with a heap more than 21 zeros... try about 21,000 zeros...

[siyan]

It took Mathematica about ten minutes to figure PI to the millionth digit (but it was on a Celeron 550...)

btw the millionth digit is 5

-C

[Kalkewl8ter]

siyan,

I do not know how I could have lived up until this moment without knowing the fascinating fact that the millionth digit of pi is 5.

[bugzpodder]

check out this guy's pi pages, apparently he'll tell you how to compute the 100 billionth digit of pi in under 10 minutes. http://www.cecm.sfu.ca/~pborwein/

and i heard of a method which lets you compute nth digit of pi without computing other digits but i can't seem to find it.

[A$$Bandit]

How many zeros on the end of x! depends on how many 5s you can stuff into it. As an example, 100! has 24 zeros on the end, because in 1 x 2 x 3 x ... x 99 x 100, you have multiples of 5 (there are 20), and also 25 can be expressed as 5 x 5, and likewise so can multiples of that (of which there are 4). So that's 24. The reason this all works is that there are god knows how many more 2s than 5s, and each 5 can pair off with a 2 to make a 10, adding a zero onto the end.

On the end of 1000000! there should be:

200000 multiples of 5, 40000 multiples of 5 x 5, 1600 multiples of 5 x 5 x 5, 320 multiples of 5⁴, 64 multiples of 5⁶, 12 multiples of 5⁷, and finally 2 multiples of 5⁸ which makes 241998 zeros on the end of 1000000!

Hey Bugz dude, is that right? Can you count them for me?

[Dreamlax]

That looks about right, after saving just the zeros into another file... it was around 250kb or something.

I heard somewhere, that even if every atom could represent a number, there would not be enough of them to store all the prime numbers up to 10⁵⁰⁰. In fact if you think about it you can't get very near that number at all.

[Evil_Giraffe]

Represent it as a product of primes shouldn't be so bad. Especially if you got a computer on the case.
For each integer from 1 to 1000000 work out its product of prime representation then keep a count of how many times each prime comes up. Should be a bit smaller than just writing it out. That should also give you a fairly good way to work out how many zeroes are at the end.

[Dreamlax]

Someone else can do that... I'm not very good at maths nor am I very good at Mathematica.

[SilverSprite]

What's Mathematica?

[Dreamlax]

Edited parts in BOLD

It's a computer program which can do a lot of mathematical stuff, ie Factorial of 1,000,000. It uses it's own kernel to do the math (so obviously it will take longer), but it can calculate almost anything you give it provided it's solve-able and to do with maths. It's more advanced than I've described it here, muuuuuch more advanced. More information below.

Unfortunately it's not free and my version is pirated. It costs a large sum, and I think it's from http://www.wolfram.com/.

Happy hunting.

[SilverSprite]

Yeah i think i have that too. I'm not sure how it works though lol.

[Dreamlax]

Just type in 5+8 and press Shift+Enter and if it's configured right it will take 2 seconds to 'warm up' the kernel and then return 13. After that the calculations take less time since the kernel is in memory (already loaded).

[SilverSprite]

wow that works! anyway i have version 4.2. How do factorials or pi?

[plenderj]

I've only got version 4.0 here

[SilverSprite]

How would you do factorials, pi, or exponential notation using mathematica?

[Dreamlax]

Factorial[100] shift enter

N[Pi, 100] shift enter

The first one calculates the factorial of 100, the second calculates Pi to 100 d.p.

[sql_lall]

Yes, that is how you work out how many Terminal zeros there are. (Just count up factors of fives as you did) However, the more challenging Question is, what is the right-most non zero digit???? There is a quick way of finding it, i just have to find the book its in.

[SilverSprite]

how come i cant take the factorial of a large number? And the pi thing is real cool!

[bugzpodder]

right most non-zero digit? easy.

of course you need to use a program to do it.

loop from 1 to N {i}
lets say 'i' is divisible by 2^a, where a is the largest integer such that 2^a<i
and 'i' is divisible by 5^b, where b is the largest integer such that 5^b<i
k=(k*i/(2^a*5^b)) mod 10
numberOfTwo+=a
numberOfFive+=b
}

loop from 1 to numberOfTwo-numberOfFive
k=(k*2)mod 10

and k would be the right-most non-zero digit

[bugzpodder]

another way is to count up the prime factors of every number from 1 to N, and keep it in an array. just set the number of twos to number of twos - number of fives and set number of fives to 0 and then multiply them all together (do mod 10 every time) and u get ur digit

[Dreamlax]

Originally posted by SilverSprite
how come i cant take the factorial of a large number? And the pi thing is real cool!

Give it some time. Factorial of 1,000,000 took 29 seconds on an overclocked dual 1,400MHz (not that the dual makes any difference [Mathematica only uses one CPU], just sounds better) with 1.5GB DDR memory. It's like this because my brother and I use it to benchmark stuff, and or course doing large calculations, or brute forcing ZIP files etc etc.

In order to use e (2.71828) you have to use a capital E. For i (i²=-1) you have to use a capital I. Basically any constant or function begins with a capital (E, I, Pi, Log, Solve, Factor, Expand etc.)


On another note:
Has anyone coded that new formula for finding primes which is apparently the most efficient way yet?

[plenderj]

Originally posted by Dreamlax

Has anyone coded that new formula for finding primes which is apparently the most efficient way yet?

which ?

[Dreamlax]

http://zdnet.com.com/2100-1104-949170.html

http://www.cse.iitk.ac.in/news/primality.pdf

First one is just a news article about the new prime number thing, the second is the actual algorithm.

[SilverSprite]

No dreamlax. When i input Factorial[100000000]or something big like that, i just get 100000000! as output. It doesnt say running as it should. When i factorial smaller numbers it works fine.

[Dreamlax]

Woah woah! Even Mathematica has a limit! Just because it can do stuff Windows Calculator can't do doesn't mean it can do the factorial of 100,000,000 ! That number would be excessively huge and would probably need A LOT of RAM and CPU power... not to mention time.

[plenderj]

Not necessarily.
If you think about it, you start at half the number itself.
Then a third of the number.
Then a quarter of the number.

Those should be the whole number factors of the number in order.
And basically once you've gone far enough with those, then just get the factors of those smaller numbers.

You could in fact store them in a DB for handiness

[Evil_Giraffe]

Factorial, not Factor.
As in n! = 1*2*3*...*(n-1)*n
Theoretically, it shouldn't need to have an upper limit. I wrote a class in VB in a couple of hours that could extend to any integer. When it got beyond the range, it just added another byte to itself and continued. Got the basic mathematical operations - add, subtract, multiply, divide, divide by a power of two (optimised to be a bit shift ), exponential. It was all written to take advantage of modulus arithmetic, so it would have needed rewriting for general use. It wasn't hugely quick either, I was trying to raise a number (approx 20 hex digits) to a power (approx 40 hex digits) modulus another number (approx 30 hex digits) and it took about a day and a half. Of course, I did forget I could reduce the exponent first :$

[Dreamlax]

I remember I attempted to do something similar to that, but then again let your kernel do 100,000,000 factorial! It will take a while and eat a LOT of RAM I bet!

[plenderj]

Duh sorry yeah I read factors, not factorial

Anyway, Evil_Giraffe, you're talking about PowerMod.
That's required in RSA cryptography, and there are well known methods of simplifying the expression

[Evil_Giraffe]

No, it was one I wrote myself. The place where I do my summer work had lost the admin password to one of their systems, but managed to find an encrypted password and a "server key" in the Windows registry. So the first task they set me on was trying to crack it. But it turns out that it wasn't just a straight RSA encrypted password. When I'd spent a week finely crafting a decryption program (read: coding one big huge dirty hack) and come out with a password that contained over 50% of the non-keyboard characters they tried ringing the company that produced to get a password reset script.

[sql_lall]

bugz, how does that loop work??

neway, if you are using programming, wouldn't it be easier to do this:
[Highlight=VB]
dim lastdigit
For a = 1 to 10000000 'whatever number
lastdigit = lastdigit * a
do while lastdigit mod 10 = 0
lastdigit = lastdigit/10
loop
next a

[bugzpodder]

i don't think so sql_lall

5*20=100
25*20=500

if u chop off the digits soon enough, you'll get 100 as an answer
otherwise you get 500. well you get the idea


plz state the part you don't understand about the loop.

[Evil_Giraffe]

Originally posted by bugzpodder
right most non-zero digit? easy.

of course you need to use a program to do it.

loop from 1 to N {i}
lets say 'i' is divisible by 2^a, where a is the largest integer such that 2^a<i
and 'i' is divisible by 2^b, where b is the largest integer such that 2^b<i
k=(k*i/(2^a*5^b)) mod 10
numberOfTwo+=a
numberOfFive+=b
}

loop from 1 to numberOfTwo-numberOfFive
k=(k*2)mod 10

and k would be the right-most non-zero digit

if you wrote ...and 'i' is divisible by 5^b, where b is the largest integer s.t. 5^b<i there may be less confusion

[Kalkewl8ter]

On the note of pi, a professor informed me that the distribution of the digits of pi are so close to being 10% for each digit, 1% for each pair of two digits, etc, that it suspiciously resembles a random set of digits. Despite the fact that there is mathematical formula for generating pi, it's digits appear to come from a random number generator!!!

[bugzpodder]

Originally posted by Evil_Giraffe
if you wrote ...and 'i' is divisible by 5^b, where b is the largest integer s.t. 5^b<i there may be less confusion

thx i've fixed it now silly old me

[SilverSprite]

Nobody care for kalkewl8ter! lol