Algorithms



I'm a desperate Geocacher (www.geocaching.com) trying to solve a difficult puzzle.
I see discussions in this forum about the rightmost nonzero digit of 1000000! is 4.
Can anybody figure out the six rightmost nonzero digits of one million factorial?
As an incentive, I'll send $20 (via PayPal) to the first person who posts the correct answer.
Thanks! Rod





The last six nonzero digits of 1,000,000! are 412544. Please, keep your money.
I wrote this code to calculate your answer:
using System;
class Program
{
const ulong Target = 1000000; const ulong RoundOff = 10000000000;
static void Main(string[] args)
{
ulong factorial = 1;
for (ulong n = 1; n <= Target; n++)
{
factorial *= n;
while (factorial % 10 == 0)
{
factorial /= 10;
}
factorial %= RoundOff;
}
Console.WriteLine("{0}! (truncated) = {1}", Target, factorial);
}
}
Why it works:
When multiplying numbers, the trailing zeros at the end will not change the outcome... so I threw those out.
Also, if you are only interested in the least significant digits, then the uppermost digits will not have an effect on the outcome of the lower digits... so I threw those out.
With all the rounding, I didn't have to worry about overflow so I was able to calculate the "truncated factorials" of very large numbers iteratively.
Enjoy,
Robert C. Cartaino
modified on Wednesday, July 2, 2008 1:26 PM





Way cool! Thank you very much! Rod





One thing I forgot to mention in the source code; I rounded off to a few more digits than required because the top digit or two might be wrong because of the rounding. In other words, if you need six digits, calculate for eight. The sixdigit answer I gave above is accurate.







General News Suggestion Question Bug Answer Joke Praise Rant Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.