Thank you to everybody who entered our first Coding Challenge: Prove Your Factorial Fluency. We received a total of 61 entries, from 58 individuals -- three players submitted extra entries in different languages, and I treated each one as a separate entry. 
C++ proved to be the fastest language, with eight of the nine fastest programs written in it. The author of one of them, Rick Matter, proved that Java could be fast as well: His Java entry took 0.00000007706 of a second, not much longer than the 0.000000068845 of a second that it took his C++ version. The one exception to the top nine programs: The one with second fastest time, which was written in C. C wasn't the only unusual programming language: Tom Gauthier provided a VBA Module, which ran in an Excel spreadsheet and tracked all the numbers in the series. It took 0.00001139 of a second, making it the 37th fastest. The fastest time was zero, i.e., too small to measure. And no, it wasn't a statement like:
cout << 752184639 << endl;
Three entrants got a zero time: Thierry Seegers used Template metaprogramming to work out the answer while it compiled. The other two zero-time entrants (Karl Anderson and Steven Heithoff) both figured out an extremely quick method to solve it, which I'll attempt to explain: There are 9! nine-digit numbers. 9! is mathematical notation for 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2. The factorial of a whole number is itself multiplied by itself -1 * itself -2 ... all the way down to x 2. We don't worry about multiplying by 1. Putting it slightly differently, there are 8! unique nine-digit numbers that use each digit only once and start with any given number. So, there are 8! of them that start with 1, 8! that start with 2, 8! that start with 3, etc. The value of 8! is 40,320. So starting at the largest possible number, we can forget the first 40,320 numbers that start with 9 and likewise the next with 8, because 80,640 is still less than 100,000. 120,960 (40,320 * 3) is not less than 100,000, so we know that the 100,000th number must start with a 7. There are 7! (which equals 5,040) of those that have a 1 next, 7! that have a 2 next, etc. After skipping the first 80,640 numbers in the sequence (those that started with an 8 or 9), there are 20,960 numbers that start with 7 before the one we want. So the first 7! (5,040) of these numbers start with a 71, the next 5,040 start 72 and you can see that we can skip the 73s and 74s as well. The number must start with 75. Now repeat this for each successive digit. For the third place there are 6! (or 720) numbers that start with 751, 720 with 752, etc. Eliminating the numbers that start with 71, 72, 73, and 74 eliminates 20,160 more numbers (4 x 5,040 = 20,160). That means there are 800 that start with 75 before the one we want (20,960 – 20,160 = 800). The first 720 numbers after that start with 751, so the 100,000th number must start with 752. You can repeat this reduction very rapidly to find the answer: 752,184,639. Fifty eight of the 61 entries got that answer. Both Karl and Steven used this method to get the answer is no time. The next fastest time was Robert Rodriguez's C program, which did it in 1.241 nanoseconds, and then John Sandberg's C++ in 1.270 nanoseconds. A nano second is a thousand millionth of a second, so these two differed by 310 thousand millionths of a second -- a very small time indeed! Karl's program is actually one of the most lovely, if not cryptic, so I'm showing part of it here:
F(1), F(2), F(3), F(4), F(5), F(6), F(7), F(8), F(9); A(1,2), A(1,3), A(1,4), A(1,5), A(1,6), A(1,7), A(1,8), A(1,9); A(2,3), A(2,4), A(2,5), A(2,6), A(2,7), A(2,8), A(2,9); A(3,4), A(3,5), A(3,6), A(3,7), A(3,8), A(3,9); A(4,5), A(4,6), A(4,7), A(4,8), A(4,9); A(5,6), A(5,7), A(5,8), A(5,9); A(6,7), A(6,8), A(6,9); A(7,8), A(7,9); A(8,9); D(9), D(8), D(7), D(6), D(5), D(4), D(3), D(2), D(1);
Yes, that is code. It uses #define macros.
Results
Note, positions 1-3 are joint winners.
- Steven Heithoff (C++) Time = 0
- Karl Anderson (C++) Time = 0
- Thierry Seegers (C++) Time = 0
- Robert Rodriguez (C) Time = 0.00000000124107
- John Sandberg (C++) Time = 0.00000000127
- Sandeep Desai (C++) Time = 0.000000002477237
- Richard Vasquez (C++) Time = 0.00000005
- Anil Guchait (C++) Time = 0.0000000535787
- Rick Matter (C++) Time = 0.0000000688453
- Rick Matter (Java) Time = 0.00000007706
- Krassimir Emilov (C) Time = 0.0000001
- Yuriy Kachanov (C++) Time = 0.000000125388
- Rob Polocz (Java) Time = 0.00000014
- Heithoff (Java) Time = 0.00000016044
- Aliaksei Sanko (C++) Time = 0.000000192072
- Jozsef Hollosi (C) Time = 0.00000025
- Richard Kendall Wolf (C++) Time = 0.00000026
- Volodmyr Tkachyshyn (C++) Time = 0.000000266516
- Michael Gould (Java) Time = 3.04346625164339E-07
- Majid Darabi (Java) Time = 0.000000343
- Tim Wiant (C++) Time = 0.0000003949
- Dean Giles (C++) Time = 0.00000045
- Vasan (Java) Time = 0.000000474
- Matthew Yin (C++) Time = 0.000000474994
- J G (C#) Time = 0.000000485653
- Brendan van der Es (Java) Time = 5.48781395760869E-07
- Richard Lerner (C#) Time = 8.13491166786633E-07
- Dave Giusto (C#) Time = 0.00000088662909
- Jay Nagel (Java) Time = 0.000001
- Xueyang Han (Java) Time = 1.00571428571428E-06
- Brent Hauble (C#) Time = 0.0000012385
- Robert Linden (Java) Time = 2.01819687026102E-06
- Andreas Falkenberg (Java) Time = 0.000003614
- Marina Stolyar (C#) Time = 7.0316440696649E-06
- Joseph Brown (C#) Time = 0.0000078
- Deepak Kejrwal (Java) Time = 0.0000102
- Tom Gauthier (VBA) Time = 1.13900405485444E-05
- Satiesh Kumar (Java) Time = 0.0000241473456
- Teresa Carrigan (Java) Time = 0.000051
- David Lotts (Java) Time = 0.000291
- Punith Kumar (C) Time = 0.001
- John Yurina (C++) Time = 0.00101641
- Farjad-H (Java) Time = 0.001259688
- Janusz Szpilewski (C++) Time = 0.00159618
- Hussain Rangwala (Java) Time = 0.0030335
- Namit Swaroop (C#) Time = 0.00400002
- Ian Heneway (C++) Time = 0.0250957
- Ryan B Fore (C) Time = 0.18829
- John Lujan (Java) Time = 1.197
- Vignesh Kumar (Java) Time = 1.491
- Bill Waugh (C#) Time = 1.958796
- Bill Waugh (C++) Time = 2.21507
- Allesandro Rossi (Java) Time = 3
- Ramesh Kapa (Java) Time = 5.738
- Benjamin Thompson (Java) Time = 8.794173
- Joel Harvell (C#) Time = 23.0840523
I'll put the source code with the correct results on SourceForge over the weekend. Thanks once again to everyone that entered and commiserations to these five who didn’t get the correct answer: Michael Tingey, Tom Jill, Nathan Pfluger, Don Taylor and John Philip Britt.
