27
\$\begingroup\$

Given an integer 1 ≤ N ≤ 1,000,000 as input, output the last non-zero digit of N!, where ! is the factorial (the product of all numbers from 1 to N, inclusive). This is OEIS sequence A008904.

Your program needs finish within 10 seconds on a reasonable machine for any valid input.

Test Cases

1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4

This is a so the shortest code in bytes wins!

\$\endgroup\$
8
  • \$\begingroup\$ Single function or complete program? \$\endgroup\$
    – Joey
    Feb 8, 2011 at 12:15
  • \$\begingroup\$ @joey No, they are just test cases. Single Input, Single Output. \$\endgroup\$
    – fR0DDY
    Feb 8, 2011 at 14:09
  • \$\begingroup\$ @joey Complete program. \$\endgroup\$
    – fR0DDY
    Feb 8, 2011 at 14:36
  • 1
    \$\begingroup\$ Requirement for a full program is discouraged... \$\endgroup\$ Jan 18, 2018 at 16:12
  • 3
    \$\begingroup\$ @EriktheOutgolfer this is from ~7 years ago, so I don't think that was determined at the time \$\endgroup\$ Jan 18, 2018 at 22:35

19 Answers 19

11
\$\begingroup\$

Mathematica, 45 36 bytes

Last@Select[IntegerDigits[#!],#>0&]&

Very readable for a winning answer. :) (Then again, there's no GolfScript & Co. submission yet.)

This handles input 1,000,000 in about 5 seconds on my machine.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Mathematica is pretty much the perfect language for this question. \$\endgroup\$ Feb 2, 2015 at 0:03
10
\$\begingroup\$

Ruby - 63 chars

f=->n{n<2?1:6*[1,1,2,6,4,4,4,8,4,6][n%10]*3**(n/5%4)*f[n/5]%10}

Source - http://oeis.org/A008904

Handles f upto a thousand digits under a second.

Test

irb(main):014:0> for n in 2..6
irb(main):015:1> puts f[10**n]
irb(main):016:1> end
4
2
8
6
4
\$\endgroup\$
0
4
\$\begingroup\$

Python - 75

n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10
\$\endgroup\$
3
\$\begingroup\$

PARI/GP - 27 bytes

This trades speed for size -- the testcase takes a long time (~6 seconds).

n->n!/10^valuation(n!,5)%10

This version is much faster (~15 microseconds) but takes 81 bytes:

n->r=1;while(n,r*=Mod(4,10)^(n\10%2)*[1,2,6,4,2,2,4,2,8][max(n%10,1)];n\=5);lift(r)

You can use this (non-golfed) code to test either:

[%(10^n) | n <- [1..6]]
\$\endgroup\$
3
\$\begingroup\$

JavaScript, 59 bytes

Based on this answer

f=n=>n>9?'6248'[(a=n/5|0)%4]*f(a)*f(n%5)%10:'1126422428'[n]

Try it:

f=n=>n>9?'6248'[(a=n/5|0)%4]*f(a)*f(n%5)%10:'1126422428'[n]

;[
  0, // 1
  1, // 1
  2, // 2
  3, // 6
  4, // 4
  5, // 2
  6, // 2
  7, // 4
  8, // 2
  9, // 8
  10, // 8
  20, // 4
  100, // 4
  1000, // 2
  10000, // 8
  100000, // 6
  1000000, // 4
].forEach(n=>console.log(n, f(n)))

Modified formula is:

$$ D(0) = 1 \\ D(1) = 1 \\ D(2) = 2 \\ D(3) = 6 \\ D(4) = 4 \\ D(5) = 2 \\ D(6) = 2 \\ D(7) = 4 \\ D(8) = 2 \\ D(9) = 8 \\ D(n) = (LastDigitOf(2^{\lfloor n/5 \rfloor}) * D(\lfloor n/5 \rfloor) * D(n \mod 5)) \mod 10, \;where \;n > 9 $$

How?

The original formula is \$D(n) = (2^{[n/5]} * D([n/5]) * D(n \mod 5)) \mod 10\$

But there is a problem: we need to calculate \$2^{[n/5]}\$. For example if \$n = 10 000 \$ then we need to calculate \$2^{2000}\$ which is already too hard (in JS it will output Infinity). But I discovered that we don't need to calculate it instead of this we just need to calculate the last digit of \$2^{[n/5]}\$. Why? Because each time we just need to calculate the last digit of \$2^{[n/5]} * D([n/5]) * D(n \mod 5)\$

Theorem

The last digit of multiplication is the last digit of multiplication of last digits of each multiplier

Proof

Let's say we have two numbers \$a\$ and \$b\$. We can represent each of them to the power of 10:

$$ a = x_n * 10^n + x_{n - 1} * 10^{n - 1} + \ldots + x_1 * 10^1 + x_0 \\ b = y_n * 10^m + y_{m - 1} * 10^{m - 1} + \ldots + y_1 * 10^1 + y_0 $$

or

$$ a = (x_n * 10^{n - 1} + x_{n - 1} * 10^{n - 2} + \ldots + x_1) * 10 + x_0 \\ b = (y_n * 10^{m - 1} + y_{m - 1} * 10^{m - 2} + \ldots + y_1) * 10 + y_0 $$

When we multiply them we will get:

$$ a * b = (...) * 10 + x_0 * y_0 $$

Now it is clear that the last digit of multiplication is the last digit of \$x_0 * y_0\$, where the \$x_0\$ and \$y_0\$ are the last digits of \$a\$ and \$b\$ respectively. So we proved the theorem

Now we need to find the last digits of powers of 2. Let's write some of them:

$$ 2^0 = 1 \\ 2^1 = 2 \\ 2^2 = 4 \\ 2^3 = 8 \\ 2^4 = 16 \\ 2^5 = 32 \\ 2^6 = 64 \\ 2^7 = 128 \\ 2^8 = 256 $$

Now we can see the pattern 1 (2 4 8 6) (2 4 8 6) and can write it \$(k = [n / 5])\$:

if (k == 0) return 1;
else return [6, 4, 8, 7][k % 4];

We can ignore the first case when k == 0 and here is why:

k % 4 == 0 when k is one of [0, 4, 8, 12, 16, ...] but we need to consider cases when k is one of [0, 4, 8] because for bigger values we will run recursion. The second multiplier in our formula is \$D(k)\$ and for k is on of [0, 4, 8] we get [1, 4, 2] respectively. We had to multiply these values by 1 but instead of this we will multiply them by 6 so we will get [1, 24, 12], the last digits of these values are [1, 4, 2]. Now we can see that it doesn't matter to multiply them by 1 or 6 the last digits will be the same

The last thing we need it is to prove that \$[n / 5] = \lfloor n / 5 \rfloor\$ for \$n \ge 0\$. I think it is obvious

\$\endgroup\$
2
\$\begingroup\$

Perl, 53 58 61 characters

All whitespace can be removed, but I left it in for "readability". Note: not using some silly explicit formula from Sloane.

sub f {
    $_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $_[0];
    $1 % 10
}

Calculates f(10^6) in 8.7 seconds on my machine.

Update: OP wanted it to be a whole program:

$_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $ARGV[0];
print $1 % 10

That makes it 55 characters.

\$\endgroup\$
2
\$\begingroup\$

CJam - 28

1ri{I)*_AbW%{}#A\#/1e7%}fIA%

You can try it at http://cjam.aditsu.net/ for values up to 10000 or so; for larger numbers you should use the java interpreter. 1000000 runs in about 3 seconds on my laptop.

Explanation:

Unfortunately the straightforward solution is too slow, so I'm keeping only the last 7 digits (before the trailing zeros) after each multiplication.

1           push 1 on the stack
ri          read a token and convert to integer
{           loop (for I from 0 to N - 1)
    I)      push I and increment
    *       multiply with the previous value (initially 1)
    _Ab     duplicate and convert to array of digits
    W%      reverse array
    {}#     find the position of the first non-zero digit
    A\#     raise 10 to that power
    /       divide, thus removing all trailing zeros
    1e7%    keep the remainder modulo 10000000
}fI         end for loop
A%          get the last digit

Note: this language is a lot newer than the question.

\$\endgroup\$
0
2
\$\begingroup\$

Mathematica, 34 bytes

Mod[#!/10^IntegerExponent[#!],10]&
\$\endgroup\$
2
\$\begingroup\$

Java (OpenJDK 8), 62 bytes

n->{long f=n;for(;n>1||f%10==0;)f=n>1?f*--n:f/10;return f%10;}

Try it online!

Similar to @Kevin Cruijssen but saves 5 bytes by combining the loops.

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to PPCG! Nice first post! Hope you stick around! \$\endgroup\$
    – Riker
    Jan 19, 2018 at 1:11
  • \$\begingroup\$ Welcome to PPCG! I agree with @Riker, great first post. Well done golfing my code by combining the loops. You can golf 1 more byte in your current answer by replacing || with |, and an additional byte by replacing ==0 with <1. Enjoy your stay! \$\endgroup\$ Feb 1, 2018 at 12:19
2
\$\begingroup\$

C, 150 140 135 bytes

r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}

This is the version for ASCII systems; replace the string 33436 with 11214 for an EBCDIC system, or with \1\1\2\1\4 for a portable program.

C solutions are a bit hampered by the requirement to provide a full program; however, this does answer the question fully.

Try it online (requires Javascript):

Explanation

It's based on the algorithm outlined in Least Significant Non-Zero Digit of n!, turned around so that we recurse in to find the highest power of five, and do the calculation on the way out. The tables of constants were too big, so I reduced them by finding a relationship between the previous residue r, the current digit d and the recursion depth k:

r d=0 d=1 d=2 d=3 d=4
0 0 3×2^k 1×2^2k 3×2^3k 2
1 1 1×2^k 2×2^2k 1×2^3k 4
2 2 2×2^k 4×2^2k 2×2^3k 3
3 3 3×2^k 3×2^2k 3×2^3k 2
4 4 4×2^k 4×2^2k 4×2^3k 1

For r>0, this resolves to a constant times r times 2^dk (mod 5); the constants are in a[] below (inlined in the golfed code). We also observe that (2^4)%5 is 1, so we can reduce the exponent to avoid overflowing the range of int.

const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x)
{
    int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
    int d = x%5;
    if (!d)
        return r;
    return r * a[d] * (1 << d*k%4) % 5;
}

int main(int c, char **v)
{
    c = atoi(*++v);
    printf("%d",
           c<2
           ? 1                  /* special-case 0 & 1 */
           : 2*f(0,c));         /* otherwise, it's 2 times r */
}

Tests:

$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4

Performance is respectable, too. Here's a maximum input for a system with 32-bit int:

$ time ./694 2147483647
8
real    0m0.001s
user    0m0.000s
sys     0m0.000s

I got the same timings with a maximal 64-bit int, too.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It may be of interest to note that 2147483647! has over 19 billion digits, and (2^63-1)! over 170,000,000,000,000,000,000 digits, so this is a big win over calculating the factorials. 1000000! as specified in the question is feasible to calculate on current hardware; that's only 5½ million digits. :-) \$\endgroup\$ May 17, 2016 at 9:49
  • 1
    \$\begingroup\$ I think main(int c,char**v) can be replaced by a K&R-style main(c,v)char**v; to save 2 bytes. \$\endgroup\$
    – Peter
    Apr 3 at 13:15
1
\$\begingroup\$

PHP - 105

 <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";}

Runs under 10 seconds with the given testcase.

\$\endgroup\$
1
\$\begingroup\$

Python3

239 Chars

Can do 10000 in ~3.2 seconds (Ideone cuts me off at 8 seconds, i'm sure it'll take longer than 10secs though :( )

from functools import *
N=100
r=range
s=(p for p in r(2,N)if all(p%n>0for n in r(2,p)))
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=list([p,f(N,p)]for p in s)
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:x[0]**x[1],e))%10)

Python2.6

299 Chars (a bit faster)

from itertools import *
N=100000
r=xrange
def s(c=count(2)):
        while 1:p=c.next();c=ifilter(p.__rmod__,c);yield p
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=[[p,f(N,p)]for p in takewhile(lambda x:x<N,s())]
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:pow(x[0],x[1],10),e))%10)
\$\endgroup\$
1
\$\begingroup\$

Haskell, 78 characters

f n=head$dropWhile(=='0')$reverse$show$product[1..n]
main=interact(show.f.read)

(Would probably need to be compiled to compute 1,000,000! in 10 secs).

\$\endgroup\$
4
  • \$\begingroup\$ Save two chars, replace that foldl1 with product (cf codegolf.stackexchange.com/questions/607/find-the-factorial/…). But have you actually tried with 1000000! ? \$\endgroup\$
    – J B
    Feb 8, 2011 at 14:48
  • \$\begingroup\$ PS: not a complete program. \$\endgroup\$
    – J B
    Feb 8, 2011 at 14:49
  • \$\begingroup\$ Sorry, did it before that was clarified in the comments. I'll update it. \$\endgroup\$
    – stusmith
    Feb 8, 2011 at 16:09
  • \$\begingroup\$ main=do x<-readLn;print$head$snd$span(=='0')$reverse$show$product[1..x] saves 7 characters \$\endgroup\$
    – Benji
    Oct 14, 2020 at 16:00
1
\$\begingroup\$

J – 42 40 characters

A whole program. Save this program in a file and run with jconsole script.ijs 1234. Notice that this program does not exit the interpreter after printing a result. Type ^D or exit]0 to exit the interpreter.

echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV

Here is an explanation:

  • x #. y interprets the integer vector y as a base x number; for example, 10 #. 1 2 3 4 yields 1234.
  • u inv yields the inverse of a verb u. In particular, x #. inv y represents y as a base x number; for example, 10 #. 1234 yields 1 2 3 4. Notice that inv is defined as ^:_1, that is, u applied -1 time.
  • x * y is the product of x and y, thus x 10&#.inv@* y yields a base-10 representation of the product of x and y.
  • x # y copies the n-th item of y as often as the n-th item of x; when x is a vector of booleans, x selects which items of y to take. For instance, 1 0 1 0 # 1 2 3 4 yields 1 3.
  • * y yields the signum of y.
  • x u~ y is the reflexive of u, that is, the same as y u x.
  • Thus, y #~ * y yields a vector of all items of y that are positive. In tacit notation, this can written with a hook as (#~ *).
  • {: y yields the last item in y.
  • assembled together, we get the tacit phrase ([:{:@(#~*)10&#.inv@*).
  • u/ y is the reduction of y, that is, the dyadic verb u inserted between elements of y. For instance, +/1 2 3 4 is like 1 + 2 + 3 + 4 and yields 10.
  • Thus, the phrase ([:{:@(#~*)10&#.inv@*)/ y yields the last digit of the product of the items of y.
  • ARGV is a boxed vector of the command line arguments.
  • ".>{:ARGV is the last argument unboxed and interpreted as a number.
  • i. y computes natural numbers from 0 to y - 1.
  • Thus, 1+i. y yields natural numbers from 1 to y. I could have also used >: increment here, but 1+ is clearer at the same cost of characters.
  • The entire program just applies 1+i.".>{:ARGV (the vector of 1 to the number in the last command line argument) to the verb ([:{:@(#~*)10&#.inv@*)/ and prints the result with echo.
\$\endgroup\$
1
\$\begingroup\$

Perl 6,  26  35 bytes

{[*](1..$_)~~/.*<(<-[0]>/}

Try it


As a full program:

put [*](1..@*ARGS[0])~~/.*<(<-[0]>/

Try it

Expanded:

{
  [*]( 1..$_ ) # reduce using &infix:« * »
  ~~           # match with
  /
    .*         # any number of values (so it matches from the end)
    <(         # only capture the following
    <-[0]>     # any value but 0 (negated character class)
  /
}
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 72 bytes (function)

f(n,d)long long n,d;{for(d=1;n;d%=10000)for(d*=n--;d%10<1;d/=10);d%=10;}

Try it online!

C (gcc), 101 99 bytes (whole program)

main(){long long n,d=1;for(scanf("%lld",&n);n;d%=10000)for(d*=n--;d%10<1;d/=10);printf("%d",d%10);}

Try it online!

This question is just shy of 8 years old so "reasonable machine" is not the same as back then, but I'm getting times of ~.01 seconds on my computer when doing all test cases together, so unless computers have increased in speed by a factor of 1000 this last decade, it should be fine.

\$\endgroup\$
2
  • \$\begingroup\$ Moore's law is still (kinda) holding up, so it should be about x16 times faster \$\endgroup\$
    – ASCII-only
    Jan 11, 2019 at 0:51
  • \$\begingroup\$ Also, a function is fine \$\endgroup\$
    – ASCII-only
    Jan 11, 2019 at 0:51
1
\$\begingroup\$

Attache, 64 bytes

{k.=Floor[_/5]If[_<2,1,6*Digits@$`U1sTny@(_%10)*3^(k%4)*$@k%10]}

Try it online!

Simple implementation of the OEIS formula. Digits@$`U1sTny compresses the hardcoded dictionary using Attache's compressed number feature. $ refers to the function itself within this answer.

\$\endgroup\$
0
0
\$\begingroup\$

AWK, 47 57 bytes

{for(p=$1;--$1;p=(p*$1)%1e4)while(!(p%10))p/=10;$0=p%10}1

Try it online!

Original solution did not handle "large" input values very well. Could add -M to force it to work, but that also requires a lot more processing time.

\$\endgroup\$
2
  • \$\begingroup\$ Yeah, @TobySpeight , inf doesn't % very well. :( \$\endgroup\$ Feb 20, 2018 at 16:05
  • \$\begingroup\$ Ah... looking at the version of the question I answered, large numbers weren't required. \$\endgroup\$ Feb 20, 2018 at 16:14
0
\$\begingroup\$

PowerShell Core, 56 bytes

($s=1).."$args"|%{$s=+("$(($s%1e5)*$_)".Trim(48))}
$s%10

Try it online!

Naive implementation, takes under 5 seconds on my local, 25 seconds on TIO
I'll rework it when I get a chance

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.