Left factorials: Difference between revisions
ReeceGoding (talk | contribs) m →{{header|R}}: Syntax highlighting. |
Thundergnat (talk | contribs) m syntax highlighting fixup automation |
||
Line 49: | Line 49: | ||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="11l">F left_fact(n) |
||
BigInt result = 0 |
BigInt result = 0 |
||
BigInt factorial = 1 |
BigInt factorial = 1 |
||
Line 63: | Line 63: | ||
print(left_fact(i)) |
print(left_fact(i)) |
||
print("\nDigits in 1,000 through 10,000 by thousands:") |
print("\nDigits in 1,000 through 10,000 by thousands:") |
||
print((1000..10000).step(1000).map(i -> String(left_fact(i)).len))</ |
print((1000..10000).step(1000).map(i -> String(left_fact(i)).len))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 89: | Line 89: | ||
Uses the Algol 68G LONG LONG INT type which has programmer definable precision. |
Uses the Algol 68G LONG LONG INT type which has programmer definable precision. |
||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
||
< |
<syntaxhighlight lang="algol68"># set the precision of LONG LONG INT - large enough for !n up to ! 10 000 # |
||
PR precision 36000 PR |
PR precision 36000 PR |
||
# stores left factorials in an array # |
# stores left factorials in an array # |
||
Line 156: | Line 156: | ||
OD |
OD |
||
END |
END |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 197: | Line 197: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
Old posix AWK doesn't support computing with large numbers. However modern gawk can use GMP if the flag -M is used. |
Old posix AWK doesn't support computing with large numbers. However modern gawk can use GMP if the flag -M is used. |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
#!/usr/bin/gawk -Mf |
#!/usr/bin/gawk -Mf |
||
function left_factorial(num) { |
function left_factorial(num) { |
||
Line 221: | Line 221: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 260: | Line 260: | ||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
Use the 'Mapm' library. |
Use the 'Mapm' library. |
||
< |
<syntaxhighlight lang="bbcbasic"> INSTALL @lib$+"BB4WMAPMLIB" : PROCMAPM_Init : MAPM_Dec%=200 |
||
Result$="0" : A$="1" |
Result$="0" : A$="1" |
||
Line 270: | Line 270: | ||
IF I% > 999 IF I% MOD 1000 = 0 PRINT "!";I% " has " LENFNMAPM_FormatDec(Result$,0) " digits" |
IF I% > 999 IF I% MOD 1000 = 0 PRINT "!";I% " has " LENFNMAPM_FormatDec(Result$,0) " digits" |
||
NEXT |
NEXT |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 307: | Line 307: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="bracmat">( ( leftFact |
||
= result factorial i |
= result factorial i |
||
. 0:?result |
. 0:?result |
||
Line 343: | Line 343: | ||
. (=L.@(!arg:? [?L)&out$!L) |
. (=L.@(!arg:? [?L)&out$!L) |
||
) |
) |
||
)</ |
)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 11 left factorials: |
<pre>First 11 left factorials: |
||
Line 384: | Line 384: | ||
=={{header|C}}== |
=={{header|C}}== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
<syntaxhighlight lang="c"> |
|||
<lang C> |
|||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 435: | Line 435: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 472: | Line 472: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp"> |
||
using System; |
using System; |
||
using System.Numerics; |
using System.Numerics; |
||
Line 525: | Line 525: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 563: | Line 563: | ||
Faster Implementation |
Faster Implementation |
||
< |
<syntaxhighlight lang="csharp"> |
||
using System; |
using System; |
||
using System.Numerics; |
using System.Numerics; |
||
Line 614: | Line 614: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
<syntaxhighlight lang="cpp"> |
|||
<lang CPP> |
|||
#include <vector> |
#include <vector> |
||
#include <string> |
#include <string> |
||
Line 745: | Line 745: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 783: | Line 783: | ||
===Faster alternative=== |
===Faster alternative=== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <gmpxx.h> |
#include <gmpxx.h> |
||
Line 820: | Line 820: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 861: | Line 861: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="lisp">(ns left-factorial |
||
(:gen-class)) |
(:gen-class)) |
||
Line 880: | Line 880: | ||
(doseq [n (range 1000 10001 1000)] |
(doseq [n (range 1000 10001 1000)] |
||
(println (format "!%-5d has %5d digits" n (count (str (biginteger (left-factorial n))))))) |
(println (format "!%-5d has %5d digits" n (count (str (biginteger (left-factorial n))))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Output}} |
{{Output}} |
||
<pre> |
<pre> |
||
Line 917: | Line 917: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun fact (n) |
(defun fact (n) |
||
(reduce #'* (loop for i from 1 to n collect i))) |
(reduce #'* (loop for i from 1 to n collect i))) |
||
Line 930: | Line 930: | ||
(format t "1000 -> 10000 by 1000~&") |
(format t "1000 -> 10000 by 1000~&") |
||
(format t "~{~a digits~&~}" (loop for i from 1000 upto 10000 by 1000 collect (length (format nil "~a" (left-fac i))))) |
(format t "~{~a digits~&~}" (loop for i from 1000 upto 10000 by 1000 collect (length (format nil "~a" (left-fac i))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 960: | Line 960: | ||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.bigint, std.range, std.algorithm, std.conv; |
||
BigInt leftFact(in uint n) pure nothrow /*@safe*/ { |
BigInt leftFact(in uint n) pure nothrow /*@safe*/ { |
||
Line 977: | Line 977: | ||
writefln("\nDigits in 1,000 through 10,000 by thousands:\n%s", |
writefln("\nDigits in 1,000 through 10,000 by thousands:\n%s", |
||
iota(1_000, 10_001, 1_000).map!(i => i.leftFact.text.length)); |
iota(1_000, 10_001, 1_000).map!(i => i.leftFact.text.length)); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 11 left factorials: |
<pre>First 11 left factorials: |
||
Line 999: | Line 999: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
We use the 'bigint' library and memoization : (remember 'function). |
We use the 'bigint' library and memoization : (remember 'function). |
||
< |
<syntaxhighlight lang="lisp"> |
||
(lib 'bigint) |
(lib 'bigint) |
||
(define (!n n) |
(define (!n n) |
||
Line 1,005: | Line 1,005: | ||
(+ (!n (1- n)) (factorial (1- n))))) |
(+ (!n (1- n)) (factorial (1- n))))) |
||
(remember '!n) |
(remember '!n) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
< |
<syntaxhighlight lang="lisp"> |
||
(for ((n 11)) (printf "!n(%d) = %d" n (!n n))) |
(for ((n 11)) (printf "!n(%d) = %d" n (!n n))) |
||
(for ((n (in-range 20 120 10))) (printf "!n(%d) = %d" n (!n n))) |
(for ((n (in-range 20 120 10))) (printf "!n(%d) = %d" n (!n n))) |
||
Line 1,046: | Line 1,046: | ||
Digits of !n(9000) = 31678 |
Digits of !n(9000) = 31678 |
||
Digits of !n(10000) = 35656 |
Digits of !n(10000) = 35656 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule LeftFactorial do |
||
def calc(0), do: 0 |
def calc(0), do: 0 |
||
def calc(n) do |
def calc(n) do |
||
Line 1,068: | Line 1,068: | ||
digits = LeftFactorial.calc(i) |> to_char_list |> length |
digits = LeftFactorial.calc(i) |> to_char_list |> length |
||
IO.puts "!#{i} has #{digits} digits" |
IO.puts "!#{i} has #{digits} digits" |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,107: | Line 1,107: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===The Functıon=== |
===The Functıon=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Generate Sequence of Left Factorials: Nigel Galloway, March 5th., 2019. |
// Generate Sequence of Left Factorials: Nigel Galloway, March 5th., 2019. |
||
let LF=Seq.unfold(fun (Σ,n,g)->Some(Σ,(Σ+n,n*g,g+1I))) (0I,1I,1I) |
let LF=Seq.unfold(fun (Σ,n,g)->Some(Σ,(Σ+n,n*g,g+1I))) (0I,1I,1I) |
||
</syntaxhighlight> |
|||
</lang> |
|||
===The Tasks=== |
===The Tasks=== |
||
;Display LF 0..10 |
;Display LF 0..10 |
||
< |
<syntaxhighlight lang="fsharp"> |
||
LF |> Seq.take 11|>Seq.iter(printfn "%A") |
LF |> Seq.take 11|>Seq.iter(printfn "%A") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,131: | Line 1,131: | ||
</pre> |
</pre> |
||
;Display LF 20..110 in steps of 10 |
;Display LF 20..110 in steps of 10 |
||
< |
<syntaxhighlight lang="fsharp"> |
||
LF |> Seq.skip 20 |> Seq.take 91 |> Seq.iteri(fun n g->if n%10=0 then printfn "%A" g) |
LF |> Seq.skip 20 |> Seq.take 91 |> Seq.iteri(fun n g->if n%10=0 then printfn "%A" g) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,148: | Line 1,148: | ||
</pre> |
</pre> |
||
;Display the length (in decimal digits) of LF 1000 .. 10000 in steps of 1000 |
;Display the length (in decimal digits) of LF 1000 .. 10000 in steps of 1000 |
||
< |
<syntaxhighlight lang="fsharp"> |
||
LF |> Seq.skip 1000 |> Seq.take 9001 |> Seq.iteri(fun n g->if n%1000=0 then printfn "%d" (string g).Length) |
LF |> Seq.skip 1000 |> Seq.take 9001 |> Seq.iteri(fun n g->if n%1000=0 then printfn "%d" (string g).Length) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,167: | Line 1,167: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.98}} |
{{works with|Factor|0.98}} |
||
<lang>USING: formatting fry io kernel math math.factorials |
<syntaxhighlight lang="text">USING: formatting fry io kernel math math.factorials |
||
math.functions math.parser math.ranges sequences ; |
math.functions math.parser math.ranges sequences ; |
||
IN: rosetta-code.left-factorials |
IN: rosetta-code.left-factorials |
||
Line 1,193: | Line 1,193: | ||
: main ( -- ) part1 part2 part3 ; |
: main ( -- ) part1 part2 part3 ; |
||
MAIN: main</ |
MAIN: main</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,235: | Line 1,235: | ||
{{works with|Gforth 0.7.3}} |
{{works with|Gforth 0.7.3}} |
||
This solution inspired by the Fortran one. |
This solution inspired by the Fortran one. |
||
< |
<syntaxhighlight lang="forth">36000 CONSTANT #DIGITS \ Enough for !10000 |
||
CREATE S #DIGITS ALLOT S #DIGITS ERASE VARIABLE S# |
CREATE S #DIGITS ALLOT S #DIGITS ERASE VARIABLE S# |
||
CREATE F #DIGITS ALLOT F #DIGITS ERASE VARIABLE F# |
CREATE F #DIGITS ALLOT F #DIGITS ERASE VARIABLE F# |
||
Line 1,282: | Line 1,282: | ||
dup REPORT |
dup REPORT |
||
dup F F# @ rot B* F# ! |
dup F F# @ rot B* F# ! |
||
1+ REPEAT drop ;</ |
1+ REPEAT drop ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>$ gforth left-factorials.fs -e 'GO bye' |
<pre>$ gforth left-factorials.fs -e 'GO bye' |
||
Line 1,324: | Line 1,324: | ||
Because this calculation won't get far, no attempt is made to save intermediate results (such as the factorial numbers) nor develop the results progressively even though they are to be produced in sequence. Each result is computed from the start, as per the specified formulae. |
Because this calculation won't get far, no attempt is made to save intermediate results (such as the factorial numbers) nor develop the results progressively even though they are to be produced in sequence. Each result is computed from the start, as per the specified formulae. |
||
For output, to have the exclamation mark precede the number without a gap, format sequence <code>"!",I0</code> will do, the <code>I0</code> format code being standardised in F90. However, this produces varying-length digit sequences, which will mean that the following output changes position likewise. Rather than use say <code>I20</code> for the result and have a wide gap, code <code>I0</code> will do, and to start each such number in the same place, the code <code>T6</code> will start it in column six, far enough along not to clash with the first number on the line, given that it will not be large. < |
For output, to have the exclamation mark precede the number without a gap, format sequence <code>"!",I0</code> will do, the <code>I0</code> format code being standardised in F90. However, this produces varying-length digit sequences, which will mean that the following output changes position likewise. Rather than use say <code>I20</code> for the result and have a wide gap, code <code>I0</code> will do, and to start each such number in the same place, the code <code>T6</code> will start it in column six, far enough along not to clash with the first number on the line, given that it will not be large. <syntaxhighlight lang="fortran"> MODULE LAIROTCAF !Calculates "left factorials". |
||
CONTAINS !The usual suspects. |
CONTAINS !The usual suspects. |
||
INTEGER*8 FUNCTION FACT(N) !Factorial, the ordinary. |
INTEGER*8 FUNCTION FACT(N) !Factorial, the ordinary. |
||
Line 1,361: | Line 1,361: | ||
WRITE (6,1) I,LFACT(I) |
WRITE (6,1) I,LFACT(I) |
||
END DO |
END DO |
||
END</ |
END</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,382: | Line 1,382: | ||
</pre> |
</pre> |
||
Obviously, one could proceed using the services of some collection of "bignum" routines, and then the code would merely depict their uses for this problem. Since the task is to produce consecutive values, all that need be done is to maintain a S value holding the accumulated sum, and a F value for the successive factorials to be added into S. The only difficulty is to arrange the proper phasing of the starting values so that the calculation will work. Since only one multiply and one addition is needed per step, explicit code might as well be used, as follows: < |
Obviously, one could proceed using the services of some collection of "bignum" routines, and then the code would merely depict their uses for this problem. Since the task is to produce consecutive values, all that need be done is to maintain a S value holding the accumulated sum, and a F value for the successive factorials to be added into S. The only difficulty is to arrange the proper phasing of the starting values so that the calculation will work. Since only one multiply and one addition is needed per step, explicit code might as well be used, as follows: <syntaxhighlight lang="fortran">Calculates "left factorials", in sequence, and shows some. |
||
INTEGER ENUFF,BASE !Some parameters. |
INTEGER ENUFF,BASE !Some parameters. |
||
PARAMETER (BASE = 10, ENUFF = 40000) !This should do. |
PARAMETER (BASE = 10, ENUFF = 40000) !This should do. |
||
Line 1,448: | Line 1,448: | ||
END DO !If there is one, as when N > BASE. |
END DO !If there is one, as when N > BASE. |
||
END DO !On to the next result. |
END DO !On to the next result. |
||
END !Ends with a new factorial that won't be used.</ |
END !Ends with a new factorial that won't be used.</syntaxhighlight> |
||
Output: achieved in a few seconds. A larger BASE would give a faster calculation, but would complicate the digit count. |
Output: achieved in a few seconds. A larger BASE would give a faster calculation, but would complicate the digit count. |
||
<pre> |
<pre> |
||
Line 1,487: | Line 1,487: | ||
{{trans|C}} |
{{trans|C}} |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
#include "gmp.bi" |
#include "gmp.bi" |
||
Line 1,529: | Line 1,529: | ||
Print |
Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,578: | Line 1,578: | ||
Frink contains efficient algorithms for calculating and caching factorials and this program will work for arbitrarily-large numbers. |
Frink contains efficient algorithms for calculating and caching factorials and this program will work for arbitrarily-large numbers. |
||
< |
<syntaxhighlight lang="frink">leftFactorial[n] := |
||
{ |
{ |
||
sum = 0 |
sum = 0 |
||
Line 1,597: | Line 1,597: | ||
println["\nlength of 1000 through 10000"] |
println["\nlength of 1000 through 10000"] |
||
for n = 1000 to 10000 step 1000 |
for n = 1000 to 10000 step 1000 |
||
println["$n has " + length[toString[leftFactorial[n]]] + " digits"]</ |
println["$n has " + length[toString[leftFactorial[n]]] + " digits"]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,639: | Line 1,639: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,683: | Line 1,683: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,702: | Line 1,702: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">leftFact :: [Integer] |
||
leftFact = scanl (+) 0 fact |
leftFact = scanl (+) 0 fact |
||
Line 1,721: | Line 1,721: | ||
, show $ length . show . (leftFact !!) <$> [1000,2000 .. 10000] |
, show $ length . show . (leftFact !!) <$> [1000,2000 .. 10000] |
||
, "" |
, "" |
||
]</ |
]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>0 ~ 10: |
<pre>0 ~ 10: |
||
Line 1,745: | Line 1,745: | ||
{{trans|D}} |
{{trans|D}} |
||
The following works in both languages: |
The following works in both languages: |
||
<lang>procedure main() |
<syntaxhighlight lang="text">procedure main() |
||
every writes(lfact(0 | !10)," ") |
every writes(lfact(0 | !10)," ") |
||
write() |
write() |
||
Line 1,760: | Line 1,760: | ||
every (i := !n, r +:= .f, f *:= .i) |
every (i := !n, r +:= .f, f *:= .i) |
||
return r |
return r |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,786: | Line 1,786: | ||
This could be made more efficient (in terms of machine time), is there a practical application for this? The more efficient machine approach would require a more specialized interface or memory dedicated to caching. |
This could be made more efficient (in terms of machine time), is there a practical application for this? The more efficient machine approach would require a more specialized interface or memory dedicated to caching. |
||
< |
<syntaxhighlight lang="j">leftFact=: +/@:!@i."0</syntaxhighlight> |
||
Task examples: |
Task examples: |
||
< |
<syntaxhighlight lang="j"> (,. leftFact) i.11 |
||
0 0 |
0 0 |
||
1 1 |
1 1 |
||
Line 1,823: | Line 1,823: | ||
8000 27749 |
8000 27749 |
||
9000 31678 |
9000 31678 |
||
10000 35656</ |
10000 35656</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">import java.math.BigInteger; |
||
public class LeftFac{ |
public class LeftFac{ |
||
Line 1,858: | Line 1,858: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>!0 = 0 |
<pre>!0 = 0 |
||
Line 1,897: | Line 1,897: | ||
'''Using builtin arithmetic''': |
'''Using builtin arithmetic''': |
||
< |
<syntaxhighlight lang="jq">def left_factorial: |
||
reduce range(1; .+1) as $i |
reduce range(1; .+1) as $i |
||
# state: [i!, !i] |
# state: [i!, !i] |
||
([1,0]; .[1] += .[0] | .[0] *= $i) |
([1,0]; .[1] += .[0] | .[0] *= $i) |
||
| .[1];</ |
| .[1];</syntaxhighlight> |
||
'''Using BigInt.jq''': |
'''Using BigInt.jq''': |
||
Line 1,910: | Line 1,910: | ||
To compute the lengths of the decimal representation without having to recompute !n, |
To compute the lengths of the decimal representation without having to recompute !n, |
||
we also define left_factorial_lengths(gap) to emit [n, ( !n|length) ] when n % gap == 0. |
we also define left_factorial_lengths(gap) to emit [n, ( !n|length) ] when n % gap == 0. |
||
< |
<syntaxhighlight lang="jq">import "BigInt" as BigInt; |
||
# integer input |
# integer input |
||
Line 1,930: | Line 1,930: | ||
| (.[1] | tostring | length) as $lf |
| (.[1] | tostring | length) as $lf |
||
| if $i % gap == 0 then .[2] += [[$i, $lf]] else . end) |
| if $i % gap == 0 then .[2] += [[$i, $lf]] else . end) |
||
| .[2];</ |
| .[2];</syntaxhighlight> |
||
'''The specific tasks''': |
'''The specific tasks''': |
||
< |
<syntaxhighlight lang="sh">((range(0;11), (range(2; 12) * 10)) | "\(.): \(long_left_factorial)"), |
||
(10000 | long_left_factorial_lengths(1000) | .[] | "\(.[0]): length is \(.[1])")</ |
(10000 | long_left_factorial_lengths(1000) | .[] | "\(.[0]): length is \(.[1])")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
(scrollable) |
(scrollable) |
||
<div style="overflow:scroll; height:200px;"> |
<div style="overflow:scroll; height:200px;"> |
||
< |
<syntaxhighlight lang="sh">$ jq -r -n -L . -f Long_left_factorial.jq |
||
0: 0 |
0: 0 |
||
1: 1 |
1: 1 |
||
Line 1,971: | Line 1,971: | ||
8000: length is 27749 |
8000: length is 27749 |
||
9000: length is 31678 |
9000: length is 31678 |
||
10000: length is 35656</ |
10000: length is 35656</syntaxhighlight> |
||
</div> |
</div> |
||
Line 1,977: | Line 1,977: | ||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">leftfactorial(n::Integer) = n ≤ 0 ? zero(n) : sum(factorial, 0:n-1) |
||
@show leftfactorial.(0:10) |
@show leftfactorial.(0:10) |
||
@show ndigits.(leftfactorial.(big.(1000:1000:10_000)))</ |
@show ndigits.(leftfactorial.(big.(1000:1000:10_000)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,987: | Line 1,987: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
import java.math.BigInteger |
import java.math.BigInteger |
||
Line 2,009: | Line 2,009: | ||
for (i in 1000..10000 step 1000) |
for (i in 1000..10000 step 1000) |
||
println("!${i.toString().padEnd(5)} has ${leftFactorial(i).toString().length} digits") |
println("!${i.toString().padEnd(5)} has ${leftFactorial(i).toString().length} digits") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,051: | Line 2,051: | ||
The code can be tested in this wiki page: http://lambdaway.free.fr/lambdawalks/?view=left_factorial |
The code can be tested in this wiki page: http://lambdaway.free.fr/lambdawalks/?view=left_factorial |
||
< |
<syntaxhighlight lang="scheme"> |
||
'''1) defining !n''' |
'''1) defining !n''' |
||
Line 2,132: | Line 2,132: | ||
Digits of !n(10000) = 35656 |
Digits of !n(10000) = 35656 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Takes about five seconds... |
Takes about five seconds... |
||
< |
<syntaxhighlight lang="lua">-- Lua bindings for GNU bc |
||
require("bc") |
require("bc") |
||
Line 2,163: | Line 2,163: | ||
for i = 1000, 10000, 1000 do |
for i = 1000, 10000, 1000 do |
||
print("!" .. i .. " contains " .. #leftFac(i) .. " digits") |
print("!" .. i .. " contains " .. #leftFac(i) .. " digits") |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>!0 = 0 |
<pre>!0 = 0 |
||
Line 2,198: | Line 2,198: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
< |
<syntaxhighlight lang="maple">left_factorial := n -> add(k!, k = 1 .. n - 1); |
||
seq(left_factorial(i), i = 1 .. 10); |
seq(left_factorial(i), i = 1 .. 10); |
||
seq(left_factorial(i), i = 20 .. 110, 10); |
seq(left_factorial(i), i = 20 .. 110, 10); |
||
seq(length(left_factorial(i)), i = 1000 .. 10000, 1000);</ |
seq(length(left_factorial(i)), i = 1000 .. 10000, 1000);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0, 1, 3, 9, 33, 153, 873, 5913, 46233, 409113 |
<pre>0, 1, 3, 9, 33, 153, 873, 5913, 46233, 409113 |
||
Line 2,210: | Line 2,210: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">left[n_] := left[n] = Sum[k!, {k, 0, n - 1}] |
||
Print["left factorials 0 through 10:"] |
Print["left factorials 0 through 10:"] |
||
Print[left /@ Range[0, 10] // TableForm] |
Print[left /@ Range[0, 10] // TableForm] |
||
Line 2,216: | Line 2,216: | ||
Print[left /@ Range[20, 110, 10] // TableForm] |
Print[left /@ Range[20, 110, 10] // TableForm] |
||
Print["Digits in left factorials 1,000 through 10,000, by thousands:"] |
Print["Digits in left factorials 1,000 through 10,000, by thousands:"] |
||
Print[Length[IntegerDigits[left[#]]] & /@ Range[1000, 10000, 1000] // TableForm]</ |
Print[Length[IntegerDigits[left[#]]] & /@ Range[1000, 10000, 1000] // TableForm]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>left factorials 0 through 10: |
<pre>left factorials 0 through 10: |
||
Line 2,257: | Line 2,257: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="nim">import iterutils, bigints |
||
proc lfact: iterator: BigInt = |
proc lfact: iterator: BigInt = |
||
Line 2,282: | Line 2,282: | ||
echo "Digits in 1,000 through 10,000 (inclusive) by thousands:" |
echo "Digits in 1,000 through 10,000 (inclusive) by thousands:" |
||
for i in lfact().slice(1_000, 10_000, 1_000): |
for i in lfact().slice(1_000, 10_000, 1_000): |
||
echo " ", ($i).len</ |
echo " ", ($i).len</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>first 11: |
<pre>first 11: |
||
Line 2,321: | Line 2,321: | ||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
< |
<syntaxhighlight lang="oforth">: leftFact | i | 0 1 rot loop: i [ tuck + swap i * ] drop ;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,349: | Line 2,349: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">lf(n)=sum(k=0,n-1,k!); |
||
apply(lf, [0..10]) |
apply(lf, [0..10]) |
||
apply(lf, 10*[2..11]) |
apply(lf, 10*[2..11]) |
||
forstep(n=1000,1e4,1000,print1(#digits(lf(n))", "))</ |
forstep(n=1000,1e4,1000,print1(#digits(lf(n))", "))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>%1 = [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] |
<pre>%1 = [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] |
||
Line 2,363: | Line 2,363: | ||
If performance is a concern, this will run over 100x faster by replacing the line "use bigint" with "use Math::GMP qw/:constant/" (after installing that module). |
If performance is a concern, this will run over 100x faster by replacing the line "use bigint" with "use Math::GMP qw/:constant/" (after installing that module). |
||
< |
<syntaxhighlight lang="perl">#!perl |
||
use 5.010; |
use 5.010; |
||
use strict; |
use strict; |
||
Line 2,387: | Line 2,387: | ||
printf "!%d has %d digits.\n", $_, length leftfact($_) for map $_*1000, 1..10; |
printf "!%d has %d digits.\n", $_, length leftfact($_) for map $_*1000, 1..10; |
||
</syntaxhighlight> |
|||
</lang> |
|||
Since I copied the printf format strings from the Raku implementation, |
Since I copied the printf format strings from the Raku implementation, |
||
Line 2,395: | Line 2,395: | ||
{{trans|Lua}} |
{{trans|Lua}} |
||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 2,426: | Line 2,426: | ||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1000</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10000</span> <span style="color: #008080;">by</span> <span style="color: #000000;">1000</span> <span style="color: #008080;">do</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"!%d contains %s digits\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)})</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1000</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10000</span> <span style="color: #008080;">by</span> <span style="color: #000000;">1000</span> <span style="color: #008080;">do</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"!%d contains %s digits\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)})</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"complete (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"complete (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,464: | Line 2,464: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de n! (N) |
||
(cache '(NIL) N |
(cache '(NIL) N |
||
(if (> 2 N) 1 |
(if (> 2 N) 1 |
||
Line 2,481: | Line 2,481: | ||
(prinl "length of 1000 - 10000") |
(prinl "length of 1000 - 10000") |
||
(pril (mapcar 'length (mapcar '!n (range 1000 10000 1000)))) |
(pril (mapcar 'length (mapcar '!n (range 1000 10000 1000)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<lang>0-10 |
<syntaxhighlight lang="text">0-10 |
||
1 |
1 |
||
1 |
1 |
||
Line 2,517: | Line 2,517: | ||
31678 |
31678 |
||
35656 |
35656 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
Line 2,524: | Line 2,524: | ||
Results are shown for the first 11 integers, as required; |
Results are shown for the first 11 integers, as required; |
||
then for the integers from 20 through 30 only, because factorials for n = 40 and larger are not possible. |
then for the integers from 20 through 30 only, because factorials for n = 40 and larger are not possible. |
||
< |
<syntaxhighlight lang="pli">lf: procedure (n) returns (fixed decimal (31) ); |
||
declare n fixed binary; |
declare n fixed binary; |
||
declare (s, f) fixed (31); |
declare (s, f) fixed (31); |
||
Line 2,546: | Line 2,546: | ||
end; |
end; |
||
end left_factorials;</ |
end left_factorials;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,575: | Line 2,575: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
{{works with|PowerShell|4.0}} |
{{works with|PowerShell|4.0}} |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function left-factorial ([BigInt]$n) { |
function left-factorial ([BigInt]$n) { |
||
[BigInt]$k, [BigInt]$fact = ([BigInt]::Zero), ([BigInt]::One) |
[BigInt]$k, [BigInt]$fact = ([BigInt]::Zero), ([BigInt]::One) |
||
Line 2,602: | Line 2,602: | ||
else {"!$i has $digits digit"} |
else {"!$i has $digits digit"} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
<pre> |
<pre> |
||
Line 2,644: | Line 2,644: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
{{works with|SWI Prolog}} |
{{works with|SWI Prolog}} |
||
< |
<syntaxhighlight lang="prolog">leftfact(N):- |
||
leftfact(N, 0, 0, 1). |
leftfact(N, 0, 0, 1). |
||
Line 2,665: | Line 2,665: | ||
main:- |
main:- |
||
leftfact(10001).</ |
leftfact(10001).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,703: | Line 2,703: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from itertools import islice |
||
def lfact(): |
def lfact(): |
||
Line 2,717: | Line 2,717: | ||
print(lf) |
print(lf) |
||
print('Digits in 1,000 through 10,000 (inclusive) by thousands:\n %r' |
print('Digits in 1,000 through 10,000 (inclusive) by thousands:\n %r' |
||
% [len(str(lf)) for lf in islice(lfact(), 1000, 10001, 1000)] )</ |
% [len(str(lf)) for lf in islice(lfact(), 1000, 10001, 1000)] )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,743: | Line 2,743: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="python">'''Left factorials''' |
||
from itertools import (accumulate, chain, count, islice) |
from itertools import (accumulate, chain, count, islice) |
||
Line 2,834: | Line 2,834: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Terms 0 thru 10 inclusive: |
<pre>Terms 0 thru 10 inclusive: |
||
Line 2,856: | Line 2,856: | ||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
< |
<syntaxhighlight lang="quackery"> [ 1 swap times [ i 1+ * ] ] is ! ( n --> n ) |
||
[ 0 swap times [ i ! + ] ] is !n ( n --> n ) |
[ 0 swap times [ i ! + ] ] is !n ( n --> n ) |
||
Line 2,868: | Line 2,868: | ||
say "Digits in 1,000 through 10,000 by thousands:" cr |
say "Digits in 1,000 through 10,000 by thousands:" cr |
||
10 times [ i^ 1+ 1000 * !n number$ size echo cr ] |
10 times [ i^ 1+ 1000 * !n number$ size echo cr ] |
||
cr</ |
cr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,901: | Line 2,901: | ||
=={{header|R}}== |
=={{header|R}}== |
||
===Imperative solution=== |
===Imperative solution=== |
||
< |
<syntaxhighlight lang="rsplus">library(gmp) |
||
left_factorial <- function(n) { |
left_factorial <- function(n) { |
||
Line 2,932: | Line 2,932: | ||
cat("!",n," has ",digit_count(left_factorial(n))," digits\n", sep = "") |
cat("!",n," has ",digit_count(left_factorial(n))," digits\n", sep = "") |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,968: | Line 2,968: | ||
===Vectorization solution=== |
===Vectorization solution=== |
||
Due to vectorization, these sorts of problems are R's bread and butter. The only challenge comes from making sure that R plays nice with objects from the gmp library. |
Due to vectorization, these sorts of problems are R's bread and butter. The only challenge comes from making sure that R plays nice with objects from the gmp library. |
||
< |
<syntaxhighlight lang="rsplus">library(gmp) |
||
leftFact <- function(numbs) |
leftFact <- function(numbs) |
||
{ |
{ |
||
Line 2,985: | Line 2,985: | ||
#Task 3 |
#Task 3 |
||
inputs<-seq(1000, 10000, by = 1000) |
inputs<-seq(1000, 10000, by = 1000) |
||
print(data.frame(Digits = sapply(leftFact(inputs), nchar), row.names = paste0("!", inputs)))</ |
print(data.frame(Digits = sapply(leftFact(inputs), nchar), row.names = paste0("!", inputs)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,030: | Line 3,030: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define ! (let ((rv# (make-hash))) (λ (n) (hash-ref! rv# n (λ () (if (= n 0) 1 (* n (! (- n 1))))))))) |
(define ! (let ((rv# (make-hash))) (λ (n) (hash-ref! rv# n (λ () (if (= n 0) 1 (* n (! (- n 1))))))))) |
||
Line 3,046: | Line 3,046: | ||
"Display the length (in decimal digits) of the left factorials for:" |
"Display the length (in decimal digits) of the left factorials for:" |
||
"1,000, 2,000 through 10,000 (inclusive), by thousands." |
"1,000, 2,000 through 10,000 (inclusive), by thousands." |
||
(pretty-format (for/list ((i (in-range 1000 10001 1000))) (add1 (order-of-magnitude (!n i))))))</ |
(pretty-format (for/list ((i (in-range 1000 10001 1000))) (add1 (order-of-magnitude (!n i))))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,072: | Line 3,072: | ||
Implement left factorial as a prefix !. Note that this redefines the core prefix ! (not) function. |
Implement left factorial as a prefix !. Note that this redefines the core prefix ! (not) function. |
||
<lang |
<syntaxhighlight lang="raku" line>sub prefix:<!> ($k) { (constant l = 0, |[\+] 1, (|[\*] 1..*))[$k] } |
||
$ = !10000; # Pre-initialize |
$ = !10000; # Pre-initialize |
||
.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, !$_ }; |
.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, !$_ }; |
||
.say for (1000, 2000 … 10000).hyper(:4batch).map: { sprintf "!%d has %d digits.", $_, chars !$_ };</ |
.say for (1000, 2000 … 10000).hyper(:4batch).map: { sprintf "!%d has %d digits.", $_, chars !$_ };</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>!0 = 0 |
<pre>!0 = 0 |
||
Line 3,111: | Line 3,111: | ||
!10000 has 35656 digits.</pre> |
!10000 has 35656 digits.</pre> |
||
If you would rather not override prefix ! operator and you can live with just defining lazy lists and indexing into them, this should suffice; (and is in fact very slightly faster than the first example since it avoids routine dispatch overhead): |
If you would rather not override prefix ! operator and you can live with just defining lazy lists and indexing into them, this should suffice; (and is in fact very slightly faster than the first example since it avoids routine dispatch overhead): |
||
<lang |
<syntaxhighlight lang="raku" line>constant leftfact = 0, |[\+] 1, (|[\*] 1..*); |
||
$ = leftfact[10000]; # Pre-initialize |
$ = leftfact[10000]; # Pre-initialize |
||
.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, leftfact[$_] }; |
.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, leftfact[$_] }; |
||
.say for (1000, 2000 … 10000).hyper(:4batch).map: { sprintf "!%d has %d digits.", $_, chars leftfact[$_] };</ |
.say for (1000, 2000 … 10000).hyper(:4batch).map: { sprintf "!%d has %d digits.", $_, chars leftfact[$_] };</syntaxhighlight> |
||
Same output. |
Same output. |
||
Line 3,124: | Line 3,124: | ||
This is possible because there will be a number of trailing zeros which allow a floating point number to be converted to an integer. |
This is possible because there will be a number of trailing zeros which allow a floating point number to be converted to an integer. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program computes/display the left factorial (or its dec. width) of N (or a range)*/ |
||
parse arg bot top inc . /*obtain optional arguments from the CL*/ |
parse arg bot top inc . /*obtain optional arguments from the CL*/ |
||
if bot=='' | bot=="," then bot= 1 /*Not specified: Then use the default.*/ |
if bot=='' | bot=="," then bot= 1 /*Not specified: Then use the default.*/ |
||
Line 3,143: | Line 3,143: | ||
$= $ + ! /*add the factorial ───► L! sum. */ |
$= $ + ! /*add the factorial ───► L! sum. */ |
||
end /*#*/ /* [↑] handles gihugeic numbers. */ |
end /*#*/ /* [↑] handles gihugeic numbers. */ |
||
return $ /*return the sum (L!) to the invoker.*/</ |
return $ /*return the sum (L!) to the invoker.*/</syntaxhighlight> |
||
{{out|output|text= when using the input of: <tt> 0 10 </tt>}} |
{{out|output|text= when using the input of: <tt> 0 10 </tt>}} |
||
<pre> |
<pre> |
||
Line 3,186: | Line 3,186: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
a = leftFact(0,10,1) |
a = leftFact(0,10,1) |
||
see "" + a + nl |
see "" + a + nl |
||
Line 3,202: | Line 3,202: | ||
else see "" + i + " " + leftFact + nl ok |
else see "" + i + " " + leftFact + nl ok |
||
next |
next |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">left_fact = Enumerator.new do |y| |
||
f, lf = 1, 0 |
f, lf = 1, 0 |
||
1.step do |n| |
1.step do |n| |
||
Line 3,212: | Line 3,212: | ||
f *= n |
f *= n |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
'''Test:''' |
'''Test:''' |
||
< |
<syntaxhighlight lang="ruby">tens = 20.step(110, 10) |
||
thousands = 1000.step(10_000, 1000) |
thousands = 1000.step(10_000, 1000) |
||
Line 3,225: | Line 3,225: | ||
puts "!#{n} has #{lf.to_s.size} digits" |
puts "!#{n} has #{lf.to_s.size} digits" |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>!0 = 0 |
<pre>!0 = 0 |
||
Line 3,261: | Line 3,261: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang="runbasic">a = lftFct(0,10,1) |
||
a = lftFct(20,110,10) |
a = lftFct(20,110,10) |
||
a = lftFct(1000,10000,1000) |
a = lftFct(1000,10000,1000) |
||
Line 3,280: | Line 3,280: | ||
end if |
end if |
||
next i |
next i |
||
end function</ |
end function</syntaxhighlight>Output: |
||
<pre>------ From 0 --To-> 10 Step 1 ------- |
<pre>------ From 0 --To-> 10 Step 1 ------- |
||
0 1 |
0 1 |
||
Line 3,319: | Line 3,319: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
<syntaxhighlight lang="rust"> |
|||
<lang Rust> |
|||
#[cfg(target_pointer_width = "64")] |
#[cfg(target_pointer_width = "64")] |
||
type USingle = u32; |
type USingle = u32; |
||
Line 3,443: | Line 3,443: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,482: | Line 3,482: | ||
This solution uses the arbitrary precision integers from the rug crate, |
This solution uses the arbitrary precision integers from the rug crate, |
||
which uses GMP under the covers. |
which uses GMP under the covers. |
||
< |
<syntaxhighlight lang="rust">// [dependencies] |
||
// rug = "1.9" |
// rug = "1.9" |
||
Line 3,513: | Line 3,513: | ||
println!("length of !{} = {}", i, n.to_string().len()); |
println!("length of !{} = {}", i, n.to_string().len()); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,554: | Line 3,554: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">object LeftFactorial extends App { |
||
// this part isn't really necessary, it just shows off Scala's ability |
// this part isn't really necessary, it just shows off Scala's ability |
||
Line 3,574: | Line 3,574: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,617: | Line 3,617: | ||
and (iota 5 100 2) produces a list (100 102 104 106 108) |
and (iota 5 100 2) produces a list (100 102 104 106 108) |
||
< |
<syntaxhighlight lang="scheme"> |
||
(import (scheme base) ;; library imports in R7RS style |
(import (scheme base) ;; library imports in R7RS style |
||
(scheme write) |
(scheme write) |
||
Line 3,645: | Line 3,645: | ||
(lambda (i) (show i (string-length (number->string (left-factorial i))))) |
(lambda (i) (show i (string-length (number->string (left-factorial i))))) |
||
(iota 10 1000 1000)) |
(iota 10 1000 1000)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
include "bigint.s7i"; |
include "bigint.s7i"; |
||
Line 3,683: | Line 3,683: | ||
end for; |
end for; |
||
writeln; |
writeln; |
||
end func;</ |
end func;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,716: | Line 3,716: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
Built-in: |
Built-in: |
||
< |
<syntaxhighlight lang="ruby">say 20.of { .left_factorial }</syntaxhighlight> |
||
Straightforward: |
Straightforward: |
||
< |
<syntaxhighlight lang="ruby">func left_factorial(n) { |
||
^n -> sum { _! } |
^n -> sum { _! } |
||
}</ |
}</syntaxhighlight> |
||
Alternatively, using ''Range.reduce()'': |
Alternatively, using ''Range.reduce()'': |
||
< |
<syntaxhighlight lang="ruby">func left_factorial(n) { |
||
^n -> reduce({ |a,b| a + b! }, 0) |
^n -> reduce({ |a,b| a + b! }, 0) |
||
}</ |
}</syntaxhighlight> |
||
A faster approach: |
A faster approach: |
||
< |
<syntaxhighlight lang="ruby">func left_factorial(n) { |
||
static cached = 0 |
static cached = 0 |
||
static factorial = 1 |
static factorial = 1 |
||
Line 3,746: | Line 3,746: | ||
leftfact |
leftfact |
||
}</ |
}</syntaxhighlight> |
||
Completing the task: |
Completing the task: |
||
< |
<syntaxhighlight lang="ruby">for n in (0..10, 20..110 `by` 10) { |
||
printf("!%d = %s\n", n, left_factorial(n)) |
printf("!%d = %s\n", n, left_factorial(n)) |
||
} |
} |
||
Line 3,755: | Line 3,755: | ||
for n in (1000..10000 `by` 1000) { |
for n in (1000..10000 `by` 1000) { |
||
printf("!%d has %d digits.\n", n, left_factorial(n).len) |
printf("!%d has %d digits.\n", n, left_factorial(n).len) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,792: | Line 3,792: | ||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
< |
<syntaxhighlight lang="sml"> |
||
(* reuse earlier factorial calculations in dfac, apply to listed arguments in cumlfac *) |
(* reuse earlier factorial calculations in dfac, apply to listed arguments in cumlfac *) |
||
(* example: left factorial n, is #3 (dfac (0,n-1,1,1) ) *) |
(* example: left factorial n, is #3 (dfac (0,n-1,1,1) ) *) |
||
Line 3,822: | Line 3,822: | ||
List.app (fn triple :int*int*int => |
List.app (fn triple :int*int*int => |
||
print( Int.toString (1+ #1 triple ) ^ " : " ^ Int.toString (size(Int.toString (#3 triple ))) ^" \n" ) ) (List.drop(result,21) ); |
print( Int.toString (1+ #1 triple ) ^ " : " ^ Int.toString (size(Int.toString (#3 triple ))) ^" \n" ) ) (List.drop(result,21) ); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,864: | Line 3,864: | ||
{{libheader|AttaSwift BigInt}} |
{{libheader|AttaSwift BigInt}} |
||
< |
<syntaxhighlight lang="swift">import BigInt |
||
func factorial<T: BinaryInteger>(_ n: T) -> T { |
func factorial<T: BinaryInteger>(_ n: T) -> T { |
||
Line 3,900: | Line 3,900: | ||
for i in stride(from: BigInt(2000), through: 10_000, by: 1000) { |
for i in stride(from: BigInt(2000), through: 10_000, by: 1000) { |
||
print("!\(i) = \((!i).description.count) digit number") |
print("!\(i) = \((!i).description.count) digit number") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,940: | Line 3,940: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">proc leftfact {n} { |
||
set s 0 |
set s 0 |
||
for {set i [set f 1]} {$i <= $n} {incr i} { |
for {set i [set f 1]} {$i <= $n} {incr i} { |
||
Line 3,954: | Line 3,954: | ||
for {set i 1000} {$i <= 10000} {incr i 1000} { |
for {set i 1000} {$i <= 10000} {incr i 1000} { |
||
puts "!$i has [string length [leftfact $i]] digits" |
puts "!$i has [string length [leftfact $i]] digits" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,993: | Line 3,993: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
{{libheader|Wren-big}} |
{{libheader|Wren-big}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt |
||
import "/big" for BigInt |
import "/big" for BigInt |
||
Line 4,022: | Line 4,022: | ||
} |
} |
||
System.print("\nLengths of left factorals from 1000 to 10000 by thousands:") |
System.print("\nLengths of left factorals from 1000 to 10000 by thousands:") |
||
for (i in 1..10) Fmt.print(" !$-5d -> $5s", i * 1000, lfacts[i].toString.count)</ |
for (i in 1..10) Fmt.print(" !$-5d -> $5s", i * 1000, lfacts[i].toString.count)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,056: | Line 4,056: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="zkl">var BN=Import("zklBigNum"); |
||
fcn leftFact(n){ |
fcn leftFact(n){ |
||
[1..n].reduce(fcn(p,n,rf){ p+=rf.value; rf.set(rf.value*n); p }, |
[1..n].reduce(fcn(p,n,rf){ p+=rf.value; rf.set(rf.value*n); p }, |
||
BN(0),Ref(BN(1))); |
BN(0),Ref(BN(1))); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">println("First 11 left factorials:\n", [0..10].apply(leftFact)); |
||
lfs:=[20..111,10].apply(leftFact); |
lfs:=[20..111,10].apply(leftFact); |
||
println(("\n20 through 110 (inclusive) by tens:\n" + |
println(("\n20 through 110 (inclusive) by tens:\n" + |
||
Line 4,068: | Line 4,068: | ||
println("Digits in 1,000 through 10,000 by thousands:\n", |
println("Digits in 1,000 through 10,000 by thousands:\n", |
||
[0d1_000..0d10_000, 1000].pump(List,fcn(n){leftFact(n).toString().len()}));</ |
[0d1_000..0d10_000, 1000].pump(List,fcn(n){leftFact(n).toString().len()}));</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 17:45, 27 August 2022
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Left factorials, !n, may refer to either subfactorials or to factorial sums;
the same notation can be confusingly seen being used for the two different definitions.
Sometimes, subfactorials (also known as derangements) may use any of the notations:
- !n`
- !n
- n¡
(It may not be visually obvious, but the last example uses an upside-down exclamation mark.)
This Rosetta Code task will be using this formula (factorial sums) for left factorial:
- where
- Task
Display the left factorials for:
- zero through ten (inclusive)
- 20 through 110 (inclusive) by tens
Display the length (in decimal digits) of the left factorials for:
- 1,000 through 10,000 (inclusive), by thousands.
- Also see
- The OEIS entry: A003422 left factorials
- The MathWorld entry: left factorial
- The MathWorld entry: factorial sums
- The MathWorld entry: subfactorial
- Related task
11l
F left_fact(n)
BigInt result = 0
BigInt factorial = 1
L(i) 1 .. n
result += factorial
factorial *= i
R result
print(‘First 11 left factorials:’)
print((0..10).map(i -> left_fact(i)))
print("\n20 through 110 (inclusive) by tens:")
L(i) (20..110).step(10)
print(left_fact(i))
print("\nDigits in 1,000 through 10,000 by thousands:")
print((1000..10000).step(1000).map(i -> String(left_fact(i)).len))
- Output:
First 11 left factorials: [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 by thousands: [2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656]
ALGOL 68
Uses the Algol 68G LONG LONG INT type which has programmer definable precision.
# set the precision of LONG LONG INT - large enough for !n up to ! 10 000 #
PR precision 36000 PR
# stores left factorials in an array #
# we calculate the left factorials, storing their values in the "values" array #
# if step is <= 1, we store we store every left factorial, otherwise we store !x when x MOD step = 0 #
# note this means values[ 0 ] is always !0 #
PROC get left factorials = ( REF[]LONG LONG INT values, INT step )VOID:
BEGIN
INT store position := LWB values;
INT max values := UPB values;
LONG LONG INT result := 0;
LONG LONG INT factorial k := 1;
FOR k FROM 0
WHILE
IF IF step <= 1 THEN TRUE ELSE k MOD step = 0 FI THEN
values[ store position ] := result;
store position +:= 1
FI;
store position <= max values
DO
result +:= factorial k;
factorial k *:= ( k + 1 )
OD
END # get left factorials # ;
# returns the number of digits in n #
OP DIGITCOUNT = ( LONG LONG INT n )INT:
BEGIN
INT result := 1;
LONG LONG INT v := ABS n;
WHILE v > 100 000 000 DO
result +:= 8;
v OVERAB 100 000 000
OD;
WHILE v > 10 DO
result +:= 1;
v OVERAB 10
OD;
result
END # DIGITCOUNT # ;
BEGIN
print( ( "!n for n = 0(1)10", newline ) );
[ 0 : 10 ]LONG LONG INT v;
get left factorials( v, 1 );
FOR i FROM 0 TO UPB v DO
print( ( whole( v[ i ], 0 ), newline ) )
OD
END;
BEGIN
print( ( "!n for n = 20(10)110", newline ) );
[ 0 : 11 ]LONG LONG INT v;
get left factorials( v, 10 );
FOR i FROM 2 TO UPB v DO
print( ( whole( v[ i ], 0 ), newline ) )
OD
END;
BEGIN
print( ( "digit counts of !n for n = 1000(1000)10 000", newline ) );
[ 0 : 10 ]LONG LONG INT v;
get left factorials( v, 1 000 );
FOR i FROM 1 TO UPB v DO
print( ( whole( DIGITCOUNT v[ i ], 0 ), newline ) )
OD
END
- Output:
!n for n = 0(1)10 0 1 2 4 10 34 154 874 5914 46234 409114 !n for n = 20(10)110 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 digit counts of !n for n = 1000(1000)10 000 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
AWK
Old posix AWK doesn't support computing with large numbers. However modern gawk can use GMP if the flag -M is used.
#!/usr/bin/gawk -Mf
function left_factorial(num) {
result=0
adder=1
if (num==0) return(0)
for (k = 1; k <=num; k++) {
result = result + adder
adder = adder * k
}
return(result)
}
BEGIN {
for (i = 0; i <= 10; i++) {
print "!" i " = " left_factorial(i)
}
for (i = 20; i<= 110; i+=10) {
print "!" i " = " left_factorial(i)
}
for (i = 1000; i<= 10000; i+=1000) {
print "!" i " has " length(left_factorial(i)) " digits"
}
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
BBC BASIC
Use the 'Mapm' library.
INSTALL @lib$+"BB4WMAPMLIB" : PROCMAPM_Init : MAPM_Dec%=200
Result$="0" : A$="1"
FOR I%=0 TO 10000
IF I% Result$=FNMAPM_Add(Result$,A$) : A$=FNMAPM_Multiply(A$,STR$I%)
IF I% < 111 IF I% MOD 10 = 0 OR I% < 11 PRINT "!";I% " = " FNMAPM_FormatDec(Result$,0)
IF I% > 999 IF I% MOD 1000 = 0 PRINT "!";I% " has " LENFNMAPM_FormatDec(Result$,0) " digits"
NEXT
END
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Bracmat
( ( leftFact
= result factorial i
. 0:?result
& 1:?factorial
& 0:?i
& whl
' ( !i+1:~>!arg:?i
& !factorial+!result:?result
& !factorial*!i:?factorial
)
& !result
)
& ( iterate
= from to step c fun
. !arg:(?from.?to.?step.?fun)
& !from+-1*!step:?from
& !step:?c
& whl
' ( !step+!from:~>!to:?from
& !fun$(leftFact$!from)
)
&
)
& out$"First 11 left factorials:"
& iterate$(0.10.1.out)
& out$"
20 through 110 (inclusive) by tens:"
& iterate$(20.110.10.out)
& out$"
Digits in 1,000 through 10,000 by thousands:"
& iterate
$ ( 1000
. 10000
. 1000
. (=L.@(!arg:? [?L)&out$!L)
)
)
- Output:
First 11 left factorials: 0 1 2 4 10 34 154 874 5914 46234 409114 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 by thousands: 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
void mpz_left_fac_ui(mpz_t rop, unsigned long op)
{
mpz_t t1;
mpz_init_set_ui(t1, 1);
mpz_set_ui(rop, 0);
size_t i;
for (i = 1; i <= op; ++i) {
mpz_add(rop, rop, t1);
mpz_mul_ui(t1, t1, i);
}
mpz_clear(t1);
}
size_t mpz_digitcount(mpz_t op)
{
/* mpz_sizeinbase can not be trusted to give accurate base 10 length */
char *t = mpz_get_str(NULL, 10, op);
size_t ret = strlen(t);
free(t);
return ret;
}
int main(void)
{
mpz_t t;
mpz_init(t);
size_t i;
for (i = 0; i <= 110; ++i) {
if (i <= 10 || i % 10 == 0) {
mpz_left_fac_ui(t, i);
gmp_printf("!%u = %Zd\n", i, t);
}
}
for (i = 1000; i <= 10000; i += 1000) {
mpz_left_fac_ui(t, i);
printf("!%u has %u digits\n", i, mpz_digitcount(t));
}
mpz_clear(t);
return 0;
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
C#
using System;
using System.Numerics;
namespace LeftFactorial
{
class Program
{
static void Main(string[] args)
{
for (int i = 0; i <= 10; i++)
{
Console.WriteLine(string.Format("!{0} = {1}", i, LeftFactorial(i)));
}
for (int j = 20; j <= 110; j += 10)
{
Console.WriteLine(string.Format("!{0} = {1}", j, LeftFactorial(j)));
}
for (int k = 1000; k <= 10000; k += 1000)
{
Console.WriteLine(string.Format("!{0} has {1} digits", k, LeftFactorial(k).ToString().Length));
}
Console.ReadKey();
}
private static BigInteger Factorial(int number)
{
BigInteger accumulator = 1;
for (int factor = 1; factor <= number; factor++)
{
accumulator *= factor;
}
return accumulator;
}
private static BigInteger LeftFactorial(int n)
{
BigInteger result = 0;
for (int i = 0; i < n; i++)
{
result += Factorial(i);
}
return result;
}
}
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Faster Implementation
using System;
using System.Numerics;
namespace LeftFactorial
{
class Program
{
static void Main(string[] args)
{
for (int i = 0; i <= 10; i++)
{
Console.WriteLine(string.Format("!{0} : {1}", i, LeftFactorial(i)));
}
for (int j = 20; j <= 110; j += 10)
{
Console.WriteLine(string.Format("!{0} : {1}", j, LeftFactorial(j)));
}
for (int k = 1000; k <= 10000; k += 1000)
{
Console.WriteLine(string.Format("!{0} : has {1} digits", k, LeftFactorial(k).ToString().Length));
}
Console.ReadKey();
}
private static BigInteger LeftFactorial(int n)
{
BigInteger result = 0;
BigInteger subResult = 1;
for (int i = 0; i < n; i++)
{
if (i == 0)
{
subResult = 1;
}
else
{
subResult *= i;
}
result += subResult;
}
return result;
}
}
}
C++
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
#if 1 // optimized for 64-bit architecture
typedef unsigned long usingle;
typedef unsigned long long udouble;
const int word_len = 32;
#else // optimized for 32-bit architecture
typedef unsigned short usingle;
typedef unsigned long udouble;
const int word_len = 16;
#endif
class bignum {
private:
// rep_.size() == 0 if and only if the value is zero.
// Otherwise, the word rep_[0] keeps the least significant bits.
vector<usingle> rep_;
public:
explicit bignum(usingle n = 0) { if (n > 0) rep_.push_back(n); }
bool equals(usingle n) const {
if (n == 0) return rep_.empty();
if (rep_.size() > 1) return false;
return rep_[0] == n;
}
bignum add(usingle addend) const {
bignum result(0);
udouble sum = addend;
for (size_t i = 0; i < rep_.size(); ++i) {
sum += rep_[i];
result.rep_.push_back(sum & (((udouble)1 << word_len) - 1));
sum >>= word_len;
}
if (sum > 0) result.rep_.push_back((usingle)sum);
return result;
}
bignum add(const bignum& addend) const {
bignum result(0);
udouble sum = 0;
size_t sz1 = rep_.size();
size_t sz2 = addend.rep_.size();
for (size_t i = 0; i < max(sz1, sz2); ++i) {
if (i < sz1) sum += rep_[i];
if (i < sz2) sum += addend.rep_[i];
result.rep_.push_back(sum & (((udouble)1 << word_len) - 1));
sum >>= word_len;
}
if (sum > 0) result.rep_.push_back((usingle)sum);
return result;
}
bignum multiply(usingle factor) const {
bignum result(0);
udouble product = 0;
for (size_t i = 0; i < rep_.size(); ++i) {
product += (udouble)rep_[i] * factor;
result.rep_.push_back(product & (((udouble)1 << word_len) - 1));
product >>= word_len;
}
if (product > 0)
result.rep_.push_back((usingle)product);
return result;
}
void divide(usingle divisor, bignum& quotient, usingle& remainder) const {
quotient.rep_.resize(0);
udouble dividend = 0;
remainder = 0;
for (size_t i = rep_.size(); i > 0; --i) {
dividend = ((udouble)remainder << word_len) + rep_[i - 1];
usingle quo = (usingle)(dividend / divisor);
remainder = (usingle)(dividend % divisor);
if (quo > 0 || i < rep_.size())
quotient.rep_.push_back(quo);
}
reverse(quotient.rep_.begin(), quotient.rep_.end());
}
};
ostream& operator<<(ostream& os, const bignum& x);
ostream& operator<<(ostream& os, const bignum& x) {
string rep;
bignum dividend = x;
bignum quotient;
usingle remainder;
while (true) {
dividend.divide(10, quotient, remainder);
rep += (char)('0' + remainder);
if (quotient.equals(0)) break;
dividend = quotient;
}
reverse(rep.begin(), rep.end());
os << rep;
return os;
}
bignum lfact(usingle n);
bignum lfact(usingle n) {
bignum result(0);
bignum f(1);
for (usingle k = 1; k <= n; ++k) {
result = result.add(f);
f = f.multiply(k);
}
return result;
}
int main() {
for (usingle i = 0; i <= 10; ++i) {
cout << "!" << i << " = " << lfact(i) << endl;
}
for (usingle i = 20; i <= 110; i += 10) {
cout << "!" << i << " = " << lfact(i) << endl;
}
for (usingle i = 1000; i <= 10000; i += 1000) {
stringstream ss;
ss << lfact(i);
cout << "!" << i << " has " << ss.str().size()
<< " digits." << endl;
}
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits. !2000 has 5733 digits. !3000 has 9128 digits. !4000 has 12670 digits. !5000 has 16322 digits. !6000 has 20062 digits. !7000 has 23875 digits. !8000 has 27749 digits. !9000 has 31678 digits. !10000 has 35656 digits.
Faster alternative
#include <iostream>
#include <gmpxx.h>
template <typename integer>
class left_factorial_generator {
public:
integer next() {
integer result = next_;
next_ += factorial_;
factorial_ *= n_++;
return result;
}
private:
unsigned int n_ = 1;
integer factorial_ = 1;
integer next_ = 0;
};
int main() {
left_factorial_generator<mpz_class> lf;
int i = 0;
std::cout << "Left factorials 0 through 10:\n";
for (; i <= 10; ++i)
std::cout << "!" << i << " = " << lf.next() << '\n';
std::cout << "Left factorials 20 through 110, by tens:\n";
for (; i <= 110; ++i) {
auto n = lf.next();
if (i % 10 == 0)
std::cout << "!" << i << " = " << n << '\n';
}
std::cout << "Lengths of left factorials 1000 through 10000, by thousands:\n";
for (; i <= 10000; ++i) {
auto n = lf.next();
if (i % 1000 == 0)
std::cout << "length of !" << i << " = " << n.get_str().size() << '\n';
}
return 0;
}
- Output:
Left factorials 0 through 10: !0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 Left factorials 20 through 110, by tens: !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Lengths of left factorials 1000 through 10000, by thousands: length of !1000 = 2565 length of !2000 = 5733 length of !3000 = 9128 length of !4000 = 12670 length of !5000 = 16322 length of !6000 = 20062 length of !7000 = 23875 length of !8000 = 27749 length of !9000 = 31678 length of !10000 = 35656
Clojure
(ns left-factorial
(:gen-class))
(defn left-factorial [n]
" Compute by updating the state [fact summ] for each k, where k equals 1 to n
Update is next state is [k*fact (summ+k)"
(second
(reduce (fn [[fact summ] k]
[(*' fact k) (+ summ fact)])
[1 0] (range 1 (inc n)))))
(doseq [n (range 11)]
(println (format "!%-3d = %5d" n (left-factorial n))))
(doseq [n (range 20 111 10)]
(println (format "!%-3d = %5d" n (biginteger (left-factorial n)))))
(doseq [n (range 1000 10001 1000)]
(println (format "!%-5d has %5d digits" n (count (str (biginteger (left-factorial n)))))))
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Common Lisp
(defun fact (n)
(reduce #'* (loop for i from 1 to n collect i)))
(defun left-fac (n)
(reduce #'+ (loop for i below n collect (fact i))))
(format t "0 -> 10~&")
(format t "~a~&" (loop for i upto 10 collect (left-fac i)))
(format t "20 -> 110 by 10~&")
(format t "~{~a~&~}" (loop for i from 20 upto 110 by 10 collect (left-fac i)))
(format t "1000 -> 10000 by 1000~&")
(format t "~{~a digits~&~}" (loop for i from 1000 upto 10000 by 1000 collect (length (format nil "~a" (left-fac i)))))
- Output:
0 -> 10 (0 1 2 4 10 34 154 874 5914 46234 409114) 20 -> 110 by 10 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 1000 -> 10000 by 1000 2565 digits 5733 digits 9128 digits 12670 digits 16322 digits 20062 digits 23875 digits 27749 digits 31678 digits 35656 digits
D
import std.stdio, std.bigint, std.range, std.algorithm, std.conv;
BigInt leftFact(in uint n) pure nothrow /*@safe*/ {
BigInt result = 0, factorial = 1;
foreach (immutable i; 1 .. n + 1) {
result += factorial;
factorial *= i;
}
return result;
}
void main() {
writeln("First 11 left factorials:\n", 11.iota.map!leftFact);
writefln("\n20 through 110 (inclusive) by tens:\n%(%s\n%)",
iota(20, 111, 10).map!leftFact);
writefln("\nDigits in 1,000 through 10,000 by thousands:\n%s",
iota(1_000, 10_001, 1_000).map!(i => i.leftFact.text.length));
}
- Output:
First 11 left factorials: [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 by thousands: [2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656]
EchoLisp
We use the 'bigint' library and memoization : (remember 'function).
(lib 'bigint)
(define (!n n)
(if (zero? n) 0
(+ (!n (1- n)) (factorial (1- n)))))
(remember '!n)
Output:
(for ((n 11)) (printf "!n(%d) = %d" n (!n n)))
(for ((n (in-range 20 120 10))) (printf "!n(%d) = %d" n (!n n)))
!n(0) = 0
!n(1) = 1
!n(2) = 2
!n(3) = 4
!n(4) = 10
!n(5) = 34
!n(6) = 154
!n(7) = 874
!n(8) = 5914
!n(9) = 46234
!n(10) = 409114
!n(20) = 128425485935180314
!n(30) = 9157958657951075573395300940314
!n(40) = 20935051082417771847631371547939998232420940314
!n(50) = 620960027832821612639424806694551108812720525606160920420940314
!n(60) = 141074930726669571000530822087000522211656242116439949000980378746128920420940314
!n(70) = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314
!n(80) = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314
!n(90) = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314
!n(100) = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314
!n(110) = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
; Compute !n : 5 seconds
(for ((n (in-range 1000 10001 500))) (!n n) (writeln n))
; Display results : 12 seconds
(for ((n (in-range 1000 10001 1000))) (printf "Digits of !n(%d) = %d" n (number-length (!n n))))
Digits of !n(1000) = 2565
Digits of !n(2000) = 5733
Digits of !n(3000) = 9128
Digits of !n(4000) = 12670
Digits of !n(5000) = 16322
Digits of !n(6000) = 20062
Digits of !n(7000) = 23875
Digits of !n(8000) = 27749
Digits of !n(9000) = 31678
Digits of !n(10000) = 35656
Elixir
defmodule LeftFactorial do
def calc(0), do: 0
def calc(n) do
{result, _factorial} = Enum.reduce(1..n, {0, 1}, fn i,{res, fact} ->
{res + fact, fact * i}
end)
result
end
end
Enum.each(0..10, fn i ->
IO.puts "!#{i} = #{LeftFactorial.calc(i)}"
end)
Enum.each(Enum.take_every(20..110, 10), fn i ->
IO.puts "!#{i} = #{LeftFactorial.calc(i)}"
end)
Enum.each(Enum.take_every(1000..10000, 1000), fn i ->
digits = LeftFactorial.calc(i) |> to_char_list |> length
IO.puts "!#{i} has #{digits} digits"
end)
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
F#
The Functıon
// Generate Sequence of Left Factorials: Nigel Galloway, March 5th., 2019.
let LF=Seq.unfold(fun (Σ,n,g)->Some(Σ,(Σ+n,n*g,g+1I))) (0I,1I,1I)
The Tasks
- Display LF 0..10
LF |> Seq.take 11|>Seq.iter(printfn "%A")
- Output:
0 1 2 4 10 34 154 874 5914 46234 409114
- Display LF 20..110 in steps of 10
LF |> Seq.skip 20 |> Seq.take 91 |> Seq.iteri(fun n g->if n%10=0 then printfn "%A" g)
- Output:
128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
- Display the length (in decimal digits) of LF 1000 .. 10000 in steps of 1000
LF |> Seq.skip 1000 |> Seq.take 9001 |> Seq.iteri(fun n g->if n%1000=0 then printfn "%d" (string g).Length)
- Output:
2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
Factor
USING: formatting fry io kernel math math.factorials
math.functions math.parser math.ranges sequences ;
IN: rosetta-code.left-factorials
: left-factorial ( n -- m ) <iota> [ n! ] map-sum ;
: print-left-factorials ( seq quot -- )
'[
dup left-factorial @
[ number>string "!" prepend ] dip
"%6s %-6d\n" printf
] each nl ; inline
: digit-count ( n -- count ) log10 >integer 1 + ;
: part1 ( -- ) 11 <iota> [ ] print-left-factorials ;
: part2 ( -- ) 20 110 10 <range> [ ] print-left-factorials ;
: part3 ( -- )
"Number of digits for" print
1,000 10,000 1,000 <range>
[ digit-count ] print-left-factorials ;
: main ( -- ) part1 part2 part3 ;
MAIN: main
- Output:
!0 0 !1 1 !2 2 !3 4 !4 10 !5 34 !6 154 !7 874 !8 5914 !9 46234 !10 409114 !20 128425485935180314 !30 9157958657951075573395300940314 !40 20935051082417771847631371547939998232420940314 !50 620960027832821612639424806694551108812720525606160920420940314 !60 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Number of digits for !1000 2565 !2000 5733 !3000 9128 !4000 12670 !5000 16322 !6000 20062 !7000 23875 !8000 27749 !9000 31678 !10000 35656
Forth
This solution inspired by the Fortran one.
36000 CONSTANT #DIGITS \ Enough for !10000
CREATE S #DIGITS ALLOT S #DIGITS ERASE VARIABLE S#
CREATE F #DIGITS ALLOT F #DIGITS ERASE VARIABLE F#
1 F C! 1 F# ! \ F = 1 = 0!
\ "Bignums": represented by two cells on the stack:
\ 1) An address pointing to the least-significant unit
\ 2) An integer size representing the number of character-size units
: mod/ /mod swap ;
: B+ ( addr u addr' u' -- u'') \ Add the second "bignum" into the first
over + >R -rot over + >R ( addr' addr R:end' R:end)
swap >R 0 over R> ( addr 0 addr addr' R:end' R:end)
\ 0: Assume second has equal or more digits, as in our problem
BEGIN over R@ < WHILE \ 1: add all digits from S
dup >R C@ swap dup >R C@ ( addr c a a' R:end' R:end R:addr'* R:addr*)
+ + 10 mod/ R@ C! R> 1+ R> 1+
REPEAT R> drop ( addr c addr* addr'* R:end')
BEGIN dup R@ < WHILE \ 2: add any remaining digits from F
dup >R C@ swap >R ( addr c a' R:end' R:addr'* R:addr*)
+ 10 mod/ R@ C! R> 1+ R> 1+
REPEAT R> drop drop ( addr c addr*)
BEGIN over WHILE \ 3: add any carry digits
>R 10 mod/ ( addr m d R:addr*) R@ C! R> 1+
REPEAT rot - nip ; \ calculate travel distance, discard 0 carry
: B* ( addr u u' -- u'') \ Multiply "bignum" inplace by U'
0 2swap over >R dup >R bounds ( u' 0 addr+u addr R:addr R:u)
DO ( u' c) over I C@ * + 10 mod/ I C! LOOP
nip R> BEGIN ( c u) over WHILE \ insert carry, may have multiple digits
>R 10 mod/ R@ swap R> R@ + ( m u d addr+u R:addr) C! 1+
REPEAT nip R> ( u'' addr) drop ;
: .B ( addr u) over + BEGIN 1- \ print bignum
dup C@ [char] 0 + EMIT over over >=
UNTIL drop drop ;
: .!n 0 <# #s [char] ! hold #> 6 over - spaces type space ;
: REPORT ( n)
dup 10 <= over dup 20 111 within swap 10 mod 0= and or
IF .!n [char] = emit space S S# @ .B cr
ELSE dup 1000 mod 0=
IF .!n ." has " S# @ . ." digits" cr
ELSE drop THEN
THEN ;
: GO 0 REPORT
1 BEGIN dup 10000 <=
WHILE
S S# @ F F# @ B+ S# !
dup REPORT
dup F F# @ rot B* F# !
1+ REPEAT drop ;
- Output:
$ gforth left-factorials.fs -e 'GO bye' !0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Fortran
First, to see how far INTEGER*8 arithmetic can reach. This is the largest size likely available, even though the syntax could easily allow INTEGER*2400 or the like. The F90 MODULE protocol is used simply to avoid the tedium of declaring the type of the function FACT(n) in all routines invoking it, though at the cost of typing out the required blather. Otherwise, this would be acceptable to older Fortran compilers, except for the appending of name information on END statements.
The function names are used as ordinary variables within the function while building the result; earlier compilers often did not allow such usage or produced incorrect code in certain cases. Ordinary integer variables are used since it is obvious that their range will not be exercised before the function result overflows, even with sixty-four bit integers for them. With two's complement arithmetic, negative numbers can appear in spite of the mathematics involved only being able to generate positive numbers, but this relies on the "sign bit" happening to become set and cannot be regarded as a definite check. Only a proper test such as the IF OVERFLOW found in First Fortran (1958) will do, but the modernisers have long abandoned this detail.
Because this calculation won't get far, no attempt is made to save intermediate results (such as the factorial numbers) nor develop the results progressively even though they are to be produced in sequence. Each result is computed from the start, as per the specified formulae.
For output, to have the exclamation mark precede the number without a gap, format sequence "!",I0
will do, the I0
format code being standardised in F90. However, this produces varying-length digit sequences, which will mean that the following output changes position likewise. Rather than use say I20
for the result and have a wide gap, code I0
will do, and to start each such number in the same place, the code T6
will start it in column six, far enough along not to clash with the first number on the line, given that it will not be large.
MODULE LAIROTCAF !Calculates "left factorials".
CONTAINS !The usual suspects.
INTEGER*8 FUNCTION FACT(N) !Factorial, the ordinary.
INTEGER N !The number won't ever get far.
INTEGER I !The stepper.
FACT = 1 !Here we go.
DO I = 2,N !Does nothing for N < 2.
FACT = FACT*I !Perhaps this overflows.
IF (FACT.LE.0) STOP "Factorial: Overflow!" !Two's complement arithmetic.
END DO !No longer any IF OVERFLOW tests.
END FUNCTION FACT !Simple enough.
INTEGER*8 FUNCTION LFACT(N) !Left factorial.
INTEGER N !This number won't get far either.
INTEGER K !A stepper.
LFACT = 0 !Here we go.
DO K = 0,N - 1 !Apply the definition.
LFACT = LFACT + FACT(K) !Perhaps this overflows.
IF (LFACT.LE.0) STOP "Lfact: Overflow!" !Unreliable test.
END DO !On to the next step in the summation.
END FUNCTION LFACT !No attempts at saving effort.
END MODULE LAIROTCAF !Just the minimum.
PROGRAM POKE
USE LAIROTCAF
INTEGER I
WRITE (6,*) "Left factorials, from 0 to 10..."
DO I = 0,10
WRITE (6,1) I,LFACT(I)
1 FORMAT ("!",I0,T6,I0)
END DO
WRITE (6,*) "Left factorials, from 20 to 110 by tens..."
DO I = 20,110,10
WRITE (6,1) I,LFACT(I)
END DO
END
Output:
Left factorials, from 0 to 10... !0 0 !1 1 !2 2 !3 4 !4 10 !5 34 !6 154 !7 874 !8 5914 !9 46234 !10 409114 Left factorials, from 20 to 110 by tens... !20 128425485935180314 Factorial: Overflow!
Obviously, one could proceed using the services of some collection of "bignum" routines, and then the code would merely depict their uses for this problem. Since the task is to produce consecutive values, all that need be done is to maintain a S value holding the accumulated sum, and a F value for the successive factorials to be added into S. The only difficulty is to arrange the proper phasing of the starting values so that the calculation will work. Since only one multiply and one addition is needed per step, explicit code might as well be used, as follows:
Calculates "left factorials", in sequence, and shows some.
INTEGER ENUFF,BASE !Some parameters.
PARAMETER (BASE = 10, ENUFF = 40000) !This should do.
INTEGER LF,F(ENUFF),LS,S(ENUFF) !Big numbers in digits F(1:LF), S(1:LS)
INTEGER N !A stepper.
INTEGER L !Locates digits.
INTEGER C !A carry for arithmetic.
INTEGER MSG !I/O unit number.
MSG = 6 !Standard output.
LF = 1; F(1) = 1 !Set F = 1 = 0!
LS = 1; S(1) = 0 !Set S = 0 = !0
WRITE (MSG,1) 0,0 !Pre-emptive first result.
1 FORMAT ("!",I0,T6,666I1) !This will do for reasonable sizes.
10 DO N = 1,10000 !Step away.
Commence the addition of F to S.
20 C = 0 !Clear the carry.
DO L = 1,MIN(LF,LS) !First, both S and F have low-order digits.
C = S(L) + F(L) + C !So, a three-part addition.
S(L) = MOD(C,BASE) !Place the digit.
C = C/BASE !Carry to the next digit up.
END DO !Ends with L and C important.
Careful. L fingers the next digit up, and C is to carry in to that digit.
IF (LF.GT.LS) THEN !Has F more digits than S?
DO L = L,LF !Yes. Continue adding, with leading zero digits from S.
C = F(L) + C !Thus.
LS = LS + 1 !Another digit for S.
S(LS) = MOD(C,BASE) !Place.
C = C/BASE !Carry to the next digit up.
END DO !Continue to the end of F.
END IF !Either way, F has been added in.
Continue carrying, with C for digit L.
DO WHILE(C .GT. 0) !Extend the carry into S.
IF (L.LE.LS) THEN !If F had fewer digits than S,
C = C + S(L) !S digits await.
ELSE !Otherwise,
LS = LS + 1 !Extend S.
END IF !C is ready.
S(L) = MOD(C,BASE) !Place it.
C = C/BASE !The carry for the next digit up.
L = L + 1 !Locate it.
END DO !Perhaps a multi-digit carry.
Contemplate what to do with the current S.
IF (N.LE.10) THEN !First selection: !N for 0 to 10.
WRITE (MSG,1) N,S(LS:1:-1) !Show the value. Digits from the high-order end down.
ELSE IF (20.LE.N .AND. N.LE.110) THEN !Second selection: for 20 to 110,
IF (MOD(N,10).EQ.0) WRITE (MSG,1) N,S(LS:1:-1) !Show only every tenth.
ELSE !Third selection
IF (MOD(N,1000).EQ.0) WRITE (MSG,21) N,LS !Show only the number of digits.
21 FORMAT ("!",I0," has ",I0," digits.") !Which is why BASE is only 10.
END IF !So much for the selection of output.
Calculate the next factorial, ready for the next one up.
C = 0 !Start a multiply.
DO L = 1,LF !Step up the digits to produce N! in F.
C = F(L)*N + C !A digit.
F(L) = MOD(C,BASE) !Place.
C = C/BASE !Extract the carry.
END DO !On to the next digit.
DO WHILE(C .GT. 0) !While any carry remains,
LF = LF + 1 !Add another digit to F.
IF (LF.GT.ENUFF) STOP "F overflow!" !Perhaps not.
F(LF) = MOD(C,BASE) !The digit.
C = C/BASE !Carry to the next digit up.
END DO !If there is one, as when N > BASE.
END DO !On to the next result.
END !Ends with a new factorial that won't be used.
Output: achieved in a few seconds. A larger BASE would give a faster calculation, but would complicate the digit count.
!0 0 !1 1 !2 2 !3 4 !4 10 !5 34 !6 154 !7 874 !8 5914 !9 46234 !10 409114 !20 128425485935180314 !30 9157958657951075573395300940314 !40 20935051082417771847631371547939998232420940314 !50 620960027832821612639424806694551108812720525606160920420940314 !60 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits. !2000 has 5733 digits. !3000 has 9128 digits. !4000 has 12670 digits. !5000 has 16322 digits. !6000 has 20062 digits. !7000 has 23875 digits. !8000 has 27749 digits. !9000 has 31678 digits. !10000 has 35656 digits.
FreeBASIC
' FB 1.05.0 Win64
#include "gmp.bi"
Sub leftFactorial(rop As __mpz_struct, op As ULong)
Dim As __mpz_struct t1
mpz_init_set_ui(@t1, 1)
mpz_set_ui(@rop, 0)
For i As ULong = 1 To op
mpz_add(@rop, @rop, @t1)
mpz_mul_ui(@t1, @t1, i)
Next
mpz_clear(@t1)
End Sub
Function digitCount(op As __mpz_struct) As ULong
Dim As ZString Ptr t = mpz_get_str(0, 10, @op)
Dim As ULong ret = Len(*t)
Deallocate(t)
Return ret
End Function
Dim As __mpz_struct t
mpz_init(@t)
For i As ULong = 0 To 110
If i <= 10 OrElse i Mod 10 = 0 Then
leftFactorial(t, i)
gmp_printf(!"!%u = %Zd\n", i, @t)
End If
Next
Print
For i As ULong = 1000 To 10000 Step 1000
leftFactorial(t, i)
Print "!"; Str(i); " has "; digitCount(t); " digits"
Next
mpz_clear(@t)
Print
Print "Press any key to quit"
Sleep
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Fōrmulæ
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
In this page you can see the program(s) related to this task and their results.
Frink
Frink contains efficient algorithms for calculating and caching factorials and this program will work for arbitrarily-large numbers.
leftFactorial[n] :=
{
sum = 0
for k = 0 to n-1
sum = sum + k!
return sum
}
println["Zero through ten"]
for n = 0 to 10
println["$n\t" + leftFactorial[n]]
println["\n20 through 110"]
for n = 20 to 110 step 10
println["$n\t" + leftFactorial[n]]
println["\nlength of 1000 through 10000"]
for n = 1000 to 10000 step 1000
println["$n has " + length[toString[leftFactorial[n]]] + " digits"]
- Output:
Zero through ten 0 0 1 1 2 2 3 4 4 10 5 34 6 154 7 874 8 5914 9 46234 10 409114 20 through 110 20 128425485935180314 30 9157958657951075573395300940314 40 20935051082417771847631371547939998232420940314 50 620960027832821612639424806694551108812720525606160920420940314 60 141074930726669571000530822087000522211656242116439949000980378746128920420940314 70 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 80 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 90 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 100 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 110 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 length of 1000 through 10000 1000 has 2565 digits 2000 has 5733 digits 3000 has 9128 digits 4000 has 12670 digits 5000 has 16322 digits 6000 has 20062 digits 7000 has 23875 digits 8000 has 27749 digits 9000 has 31678 digits 10000 has 35656 digits
Go
package main
import (
"fmt"
"math/big"
)
func main() {
fmt.Print("!0 through !10: 0")
one := big.NewInt(1)
n := big.NewInt(1)
f := big.NewInt(1)
l := big.NewInt(1)
next := func() { f.Mul(f, n); l.Add(l, f); n.Add(n, one) }
for ; ; next() {
fmt.Print(" ", l)
if n.Int64() == 10 {
break
}
}
fmt.Println()
for {
for i := 0; i < 10; i++ {
next()
}
fmt.Printf("!%d: %d\n", n, l)
if n.Int64() == 110 {
break
}
}
fmt.Println("Lengths of !1000 through !10000 by thousands:")
for i := 110; i < 1000; i++ {
next()
}
for {
fmt.Print(" ", len(l.String()))
if n.Int64() == 10000 {
break
}
for i := 0; i < 1000; i++ {
next()
}
}
fmt.Println()
}
- Output:
!0 through !10: 0 1 2 4 10 34 154 874 5914 46234 409114 !20: 128425485935180314 !30: 9157958657951075573395300940314 !40: 20935051082417771847631371547939998232420940314 !50: 620960027832821612639424806694551108812720525606160920420940314 !60: 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70: 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80: 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90: 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100: 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110: 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Lengths of !1000 through !10000 by thousands: 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
Haskell
leftFact :: [Integer]
leftFact = scanl (+) 0 fact
fact :: [Integer]
fact = scanl (*) 1 [1 ..]
main :: IO ()
main =
mapM_
putStrLn
[ "0 ~ 10:"
, show $ (leftFact !!) <$> [0 .. 10]
, ""
, "20 ~ 110 by tens:"
, unlines $ show . (leftFact !!) <$> [20,30 .. 110]
, ""
, "length of 1,000 ~ 10,000 by thousands:"
, show $ length . show . (leftFact !!) <$> [1000,2000 .. 10000]
, ""
]
- Output:
0 ~ 10: [0,1,2,4,10,34,154,874,5914,46234,409114] 20 ~ 110 by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 length of 1,000 ~ 10,000 by thousands: [2565,5733,9128,12670,16322,20062,23875,27749,31678,35656]
Icon and Unicon
The following works in both languages:
procedure main()
every writes(lfact(0 | !10)," ")
write()
write()
every write(lfact(20 to 110 by 10))
write()
every writes(*lfact(1000 to 10000 by 1000)," ")
write()
end
procedure lfact(n)
r := 0
f := 1
every (i := !n, r +:= .f, f *:= .i)
return r
end
- Output:
->lfact 0 1 2 4 10 34 154 874 5914 46234 409114 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656 ->
J
This could be made more efficient (in terms of machine time), is there a practical application for this? The more efficient machine approach would require a more specialized interface or memory dedicated to caching.
leftFact=: +/@:!@i."0
Task examples:
(,. leftFact) i.11
0 0
1 1
2 2
3 4
4 10
5 34
6 154
7 874
8 5914
9 46234
10 409114
(,. leftFact) 10*2+i.10x
20 128425485935180314
30 9157958657951075573395300940314
40 20935051082417771847631371547939998232420940314
50 620960027832821612639424806694551108812720525606160920420940314
60 141074930726669571000530822087000522211656242116439949000980378746128920420940314
70 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314
80 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314
90 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314
100 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314
110 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
(,. #@":@leftFact) 1000*1+i.10x
1000 2565
2000 5733
3000 9128
4000 12670
5000 16322
6000 20062
7000 23875
8000 27749
9000 31678
10000 35656
Java
import java.math.BigInteger;
public class LeftFac{
public static BigInteger factorial(BigInteger n){
BigInteger ans = BigInteger.ONE;
for(BigInteger x = BigInteger.ONE; x.compareTo(n) <= 0; x = x.add(BigInteger.ONE)){
ans = ans.multiply(x);
}
return ans;
}
public static BigInteger leftFact(BigInteger n){
BigInteger ans = BigInteger.ZERO;
for(BigInteger k = BigInteger.ZERO; k.compareTo(n.subtract(BigInteger.ONE)) <= 0; k = k.add(BigInteger.ONE)){
ans = ans.add(factorial(k));
}
return ans;
}
public static void main(String[] args){
for(int i = 0; i <= 10; i++){
System.out.println("!" + i + " = " + leftFact(BigInteger.valueOf(i)));
}
for(int i = 20; i <= 110; i += 10){
System.out.println("!" + i + " = " + leftFact(BigInteger.valueOf(i)));
}
for(int i = 1000; i <= 10000; i += 1000){
System.out.println("!" + i + " has " + leftFact(BigInteger.valueOf(i)).toString().length() + " digits");
}
}
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
jq
jq currently only has builtin support for IEEE 64-bit numbers, so in this section we will first present the algorithm using the builtin arithmetic operators and then adapt it for use with the BigInt library at https://gist.github.com/pkoppstein/d06a123f30c033195841
Using builtin arithmetic:
def left_factorial:
reduce range(1; .+1) as $i
# state: [i!, !i]
([1,0]; .[1] += .[0] | .[0] *= $i)
| .[1];
Using BigInt.jq:
The BigInt library can be used with jq 1.4, but we will take this opportunity to showcase jq 1.5's support for importing such libraries as modules. If your jq does not have support for modules, add the BigInt.jq file, remove the 'import' statement and strip off the "BigInt::" prefix.
To compute the lengths of the decimal representation without having to recompute !n, we also define left_factorial_lengths(gap) to emit [n, ( !n|length) ] when n % gap == 0.
import "BigInt" as BigInt;
# integer input
def long_left_factorial:
reduce range(1; .+1) as $i
# state: [i!, !i]
( ["1", "0"];
.[1] = BigInt::long_add(.[0]; .[1])
| .[0] = BigInt::long_multiply(.[0]; $i | tostring) )
| .[1];
# input and gap should be integers
def long_left_factorial_lengths(gap):
reduce range(1; .+1) as $i
# state: [i!, !i, gap]
(["1", "0", []];
.[1] = BigInt::long_add(.[0]; .[1])
| .[0] = BigInt::long_multiply(.[0]; $i|tostring)
| (.[1] | tostring | length) as $lf
| if $i % gap == 0 then .[2] += [[$i, $lf]] else . end)
| .[2];
The specific tasks:
((range(0;11), (range(2; 12) * 10)) | "\(.): \(long_left_factorial)"),
(10000 | long_left_factorial_lengths(1000) | .[] | "\(.[0]): length is \(.[1])")
- Output:
(scrollable)
$ jq -r -n -L . -f Long_left_factorial.jq
0: 0
1: 1
2: 2
3: 4
4: 10
5: 34
6: 154
7: 874
8: 5914
9: 46234
10: 409114
20: 128425485935180314
30: 9157958657951075573395300940314
40: 20935051082417771847631371547939998232420940314
50: 620960027832821612639424806694551108812720525606160920420940314
60: 141074930726669571000530822087000522211656242116439949000980378746128920420940314
70: 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314
80: 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314
90: 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314
100: 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314
110: 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
1000: length is 2565
2000: length is 5733
3000: length is 9128
4000: length is 12670
5000: length is 16322
6000: length is 20062
7000: length is 23875
8000: length is 27749
9000: length is 31678
10000: length is 35656
Julia
leftfactorial(n::Integer) = n ≤ 0 ? zero(n) : sum(factorial, 0:n-1)
@show leftfactorial.(0:10)
@show ndigits.(leftfactorial.(big.(1000:1000:10_000)))
- Output:
leftfactorial.(0:10) = [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] ndigits.(leftfactorial.(big.(1000:1000:10000))) = [2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656]
Kotlin
// version 1.0.6
import java.math.BigInteger
fun leftFactorial(n: Int): BigInteger {
if (n == 0) return BigInteger.ZERO
var fact = BigInteger.ONE
var sum = fact
for (i in 1 until n) {
fact *= BigInteger.valueOf(i.toLong())
sum += fact
}
return sum
}
fun main(args: Array<String>) {
for (i in 0..110)
if (i <= 10 || (i % 10) == 0)
println("!${i.toString().padEnd(3)} = ${leftFactorial(i)}")
println("\nLength of the following left factorials:")
for (i in 1000..10000 step 1000)
println("!${i.toString().padEnd(5)} has ${leftFactorial(i).toString().length} digits")
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Length of the following left factorials: !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Lambdatalk
The code can be tested in this wiki page: http://lambdaway.free.fr/lambdawalks/?view=left_factorial
'''1) defining !n'''
{def !n // the main function's name
{def !n.mem {A.new 0 1 2}} // initializing a global array
// memorizing the computed values of !n
{def !n.set // computing and storing the values
{lambda {:n}
{A.set! :n // assign at n
{long_mult :n {A.get {- :n 1} {!n.mem}} } // product of n and computed value at n-1
{!n.mem}}}} // in the global array
{def !n.get // getting a value
{lambda {:n}
{A.get :n {if {W.equal? {A.get :n {!n.mem}} undefined} // if it doesn't exist
then {!n.set :n} // then compute it
else {!n.mem}}}}} // else get it from the global array
{lambda {:n} // the main function's body
{if {< :n 2} // if n=0 and n=1
then :n // then return 0 or 1
else {S.reduce long_add // apply add_long to
1 {S.map !n.get {S.serie 1 {- :n 1}}}}}}} // the sequence of computed values
'''2) the task'''
A) computing !n from 2 to 10 takes about 4ms
{S.map {lambda {:n} {br}!n(:n) = {!n :n}}
{S.serie 0 10}}
->
!n(0) = 0
!n(1) = 1
!n(2) = 2
!n(3) = 4
!n(4) = 10
!n(5) = 34
!n(6) = 154
!n(7) = 874
!n(8) = 5914
!n(9) = 46234
!n(10) = 409114
B) computing !n from 20 to 110 with step 10 takes about 25ms
{S.map {lambda {:n} {br}!n(:n) = {!n :n}}
{S.serie 20 110 10}}
->
!n(20) = 128425485935180314
!n(30) = 9157958657951075573395300940314
!n(40) = 20935051082417771847631371547939998232420940314
!n(50) = 620960027832821612639424806694551108812720525606160920420940314
!n(60) = 141074930726669571000530822087000522211656242116439949000980378746128920420940314
!n(70) = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314
!n(80) = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314
!n(90) = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314
!n(100) = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314
!n(110) = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
C) computing !n from 1000 to 1000 with step 1000 takes about 87 seconds
1) compute n! from 1 to 10000 and store in MEM // about 86 seconds
{def foo {!n 10000}} -> foo
2) take 10 values from MEM // about 1ms
{S.map {lambda {:n}
{br}Digits of !n(:n) = {W.length {A.get {- :n 1} {MEM}}}}
{S.serie 1000 10000 1000}}
->
Digits of !n(1000) = 2565
Digits of !n(2000) = 5733
Digits of !n(3000) = 9128
Digits of !n(4000) = 12670
Digits of !n(5000) = 16322
Digits of !n(6000) = 20062
Digits of !n(7000) = 23875
Digits of !n(8000) = 27749
Digits of !n(9000) = 31678
Digits of !n(10000) = 35656
Lua
Takes about five seconds...
-- Lua bindings for GNU bc
require("bc")
-- Return table of factorials from 0 to n
function facsUpTo (n)
local f, fList = bc.number(1), {}
fList[0] = 1
for i = 1, n do
f = bc.mul(f, i)
fList[i] = f
end
return fList
end
-- Return left factorial of n
function leftFac (n)
local sum = bc.number(0)
for k = 0, n - 1 do sum = bc.add(sum, facList[k]) end
return bc.tostring(sum)
end
-- Main procedure
facList = facsUpTo(10000)
for i = 0, 10 do print("!" .. i .. " = " .. leftFac(i)) end
for i = 20, 110, 10 do print("!" .. i .. " = " .. leftFac(i)) end
for i = 1000, 10000, 1000 do
print("!" .. i .. " contains " .. #leftFac(i) .. " digits")
end
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 contains 2565 digits !2000 contains 5733 digits !3000 contains 9128 digits !4000 contains 12670 digits !5000 contains 16322 digits !6000 contains 20062 digits !7000 contains 23875 digits !8000 contains 27749 digits !9000 contains 31678 digits !10000 contains 35656 digits
Maple
left_factorial := n -> add(k!, k = 1 .. n - 1);
seq(left_factorial(i), i = 1 .. 10);
seq(left_factorial(i), i = 20 .. 110, 10);
seq(length(left_factorial(i)), i = 1000 .. 10000, 1000);
- Output:
0, 1, 3, 9, 33, 153, 873, 5913, 46233, 409113 128425485935180313, 9157958657951075573395300940313, 20935051082417771847631371547939998232420940313, 620960027832821612639424806694551108812720525606160920420940313, 141074930726669571000530822087000522211656242116439949000980378746128920420940313, 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940313, 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940313, 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940313, 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940313, 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940313 2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656
Mathematica /Wolfram Language
left[n_] := left[n] = Sum[k!, {k, 0, n - 1}]
Print["left factorials 0 through 10:"]
Print[left /@ Range[0, 10] // TableForm]
Print["left factorials 20 through 110, by tens:"]
Print[left /@ Range[20, 110, 10] // TableForm]
Print["Digits in left factorials 1,000 through 10,000, by thousands:"]
Print[Length[IntegerDigits[left[#]]] & /@ Range[1000, 10000, 1000] // TableForm]
- Output:
left factorials 0 through 10: 0 1 2 4 10 34 154 874 5914 46234 409114 left factorials 20 through 110, by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in left factorials 1,000 through 10,000, by thousands: 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
Nim
import iterutils, bigints
proc lfact: iterator: BigInt =
result = iterator: BigInt =
yield 0.initBigInt
var
fact = 1.initBigInt
sum = 0.initBigInt
n = 1.initBigInt
while true:
sum += fact
fact *= n
n += 1
yield sum
echo "first 11:\n "
for i in lfact().slice(last = 10):
echo " ", i
echo "20 through 110 (inclusive) by tens:"
for i in lfact().slice(20, 110, 10):
echo " ", i
echo "Digits in 1,000 through 10,000 (inclusive) by thousands:"
for i in lfact().slice(1_000, 10_000, 1_000):
echo " ", ($i).len
- Output:
first 11: 0 1 2 4 10 34 154 874 5914 46234 409114 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 (inclusive) by thousands: 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
Oforth
: leftFact | i | 0 1 rot loop: i [ tuck + swap i * ] drop ;
- Output:
>seqFrom(0, 10) map(#leftFact) println [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114]
>seqFrom(2, 11) apply(#[ 10 * leftFact println ]) 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
>seq(10) map(#[ 1000 * leftFact asString size ]) println [2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656]
PARI/GP
lf(n)=sum(k=0,n-1,k!);
apply(lf, [0..10])
apply(lf, 10*[2..11])
forstep(n=1000,1e4,1000,print1(#digits(lf(n))", "))
- Output:
%1 = [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] %2 = [128425485935180314, 9157958657951075573395300940314, 20935051082417771847631371547939998232420940314, 620960027832821612639424806694551108812720525606160920420940314, 141074930726669571000530822087000522211656242116439949000980378746128920420940314, 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314, 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314, 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314, 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314, 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314] 2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656,
Perl
By caching the last used factorial and left factorial values, I avoid needless recomputation. By only retaining the most recently used values, instead of all past values, I avoid the need to store twenty thousand enormous numbers.
If performance is a concern, this will run over 100x faster by replacing the line "use bigint" with "use Math::GMP qw/:constant/" (after installing that module).
#!perl
use 5.010;
use strict;
use warnings;
use bigint;
sub leftfact {
my ($n) = @_;
state $cached = 0;
state $factorial = 1;
state $leftfact = 0;
if( $n < $cached ) {
($cached, $factorial, $leftfact) = (0, 1, 0);
}
while( $n > $cached ) {
$leftfact += $factorial;
$factorial *= ++$cached;
}
return $leftfact;
}
printf "!%d = %s\n", $_, leftfact($_) for 0 .. 10, map $_*10, 2..11;
printf "!%d has %d digits.\n", $_, length leftfact($_) for map $_*1000, 1..10;
Since I copied the printf format strings from the Raku implementation, the output from the code above is identical to the output of the Raku code.
Phix
with javascript_semantics include mpfr.e sequence lf_list procedure init(integer n) mpz f = mpz_init(1) lf_list = repeat(f,n+1) for i=1 to n do f = mpz_init_set(f) mpz_mul_si(f,f,i) lf_list[i+1] = f end for end procedure function lf(integer n, bool len=false) -- Returns left factorial of n, or it's length, as a string mpz sumf = mpz_init(0) for k=1 to n do mpz_add(sumf,sumf,lf_list[k]) end for return iff(len?sprintf("%d",mpz_sizeinbase(sumf,10)) :shorten(mpz_get_str(sumf))) end function -- Main procedure atom t0 = time() init(10000) for i=0 to 10 do printf(1,"!%d = %s\n",{i,lf(i)}) end for for i=20 to 110 by 10 do printf(1,"!%d = %s\n",{i,lf(i)}) end for for i=1000 to 10000 by 1000 do printf(1,"!%d contains %s digits\n",{i,lf(i,true)}) end for printf(1,"complete (%3.2fs)\n",{time()-t0})
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 62096002783282161263...25606160920420940314 (63 digits) !60 = 14107493072666957100...78746128920420940314 (81 digits) !70 = 17363951180298752669...09216528920420940314 (99 digits) !80 = 90608958798769534653...22336528920420940314 (117 digits) !90 = 16695570072624210767...42336528920420940314 (137 digits) !100 = 94278623976582657916...42336528920420940314 (156 digits) !110 = 14572298106158529700...42336528920420940314 (177 digits) !1000 contains 2565 digits !2000 contains 5733 digits !3000 contains 9128 digits !4000 contains 12670 digits !5000 contains 16322 digits !6000 contains 20062 digits !7000 contains 23875 digits !8000 contains 27749 digits !9000 contains 31678 digits !10000 contains 35656 digits complete (0.45s)
PicoLisp
(de n! (N)
(cache '(NIL) N
(if (> 2 N) 1
(* N (n! (dec N))))))
(de !n (Num)
(if (= Num 0) 1
(sum n! (range 0 (dec Num)))))
(de pril (List) (mapcar 'println List))
(prinl "0-10")
(pril (mapcar '!n (range 0 10)))
(prinl "20 - 110")
(pril (mapcar '!n (range 20 110 10)))
(prinl "length of 1000 - 10000")
(pril (mapcar 'length (mapcar '!n (range 1000 10000 1000))))
- Output:
0-10
1
1
2
4
10
34
154
874
5914
46234
409114
20 - 110
128425485935180314
9157958657951075573395300940314
20935051082417771847631371547939998232420940314
620960027832821612639424806694551108812720525606160920420940314
141074930726669571000530822087000522211656242116439949000980378746128920420940314
173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314
906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314
16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314
942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314
145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
1000 - 10000
2565
5733
9128
12670
16322
20062
23875
27749
31678
35656
PL/I
In PL/I the biggest integer type is fixed decimal(31) i.e. 31 digits. To the best of my knowledge, no big integers exist. Results are shown for the first 11 integers, as required; then for the integers from 20 through 30 only, because factorials for n = 40 and larger are not possible.
lf: procedure (n) returns (fixed decimal (31) );
declare n fixed binary;
declare (s, f) fixed (31);
declare (i, j) fixed;
s = 0;
do i = n-1 to 0 by -1;
f = 1;
do j = i to 1 by -1;
f = f * j;
end;
s = s + f;
end;
return (s);
end lf;
declare n fixed binary;
do n = 0 to 10, 20 to 30;
put skip list ('Left factorial of ' || n || '=' || lf(n) );
end;
end left_factorials;
- Output:
Left factorial of 0= 0 Left factorial of 1= 1 Left factorial of 2= 2 Left factorial of 3= 4 Left factorial of 4= 10 Left factorial of 5= 34 Left factorial of 6= 154 Left factorial of 7= 874 Left factorial of 8= 5914 Left factorial of 9= 46234 Left factorial of 10= 409114 Left factorial of 20= 128425485935180314 Left factorial of 21= 2561327494111820314 Left factorial of 22= 53652269665821260314 Left factorial of 23= 1177652997443428940314 Left factorial of 24= 27029669736328405580314 Left factorial of 25= 647478071469567844940314 Left factorial of 26= 16158688114800553828940314 Left factorial of 27= 419450149241406189412940314 Left factorial of 28= 11308319599659758350180940314 Left factorial of 29= 316196664211373618851684940314 Left factorial of 30= 9157958657951075573395300940314
PowerShell
function left-factorial ([BigInt]$n) {
[BigInt]$k, [BigInt]$fact = ([BigInt]::Zero), ([BigInt]::One)
[BigInt]$lfact = ([BigInt]::Zero)
while($k -lt $n){
if($k -gt ([BigInt]::Zero)) {
$fact = [BigInt]::Multiply($fact, $k)
$lfact = [BigInt]::Add($lfact, $fact)
} else {
$lfact = ([BigInt]::One)
}
$k = [BigInt]::Add($k, [BigInt]::One)
}
$lfact
}
0..9 | foreach{
"!$_ = $(left-factorial $_)"
}
for($i = 10; $i -le 110; $i += 10) {
"!$i = $(left-factorial $i)"
}
for($i = 1000; $i -le 10000; $i += 1000) {
$digits = [BigInt]::Log10($(left-factorial $i))
$digits = [Math]::Floor($digits) + 1
if($digits -gt 1) {"!$i has $digits digits"}
else {"!$i has $digits digit"}
}
Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 9060895879876953465345168046502906376940248300119563651843276746197520942896963148820085319918409223365289204 20940314 !90 = 1669557007262421076703416768839462336073351516357586413634591033592403996240486951022572307223584266878750799 3136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203 520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337 422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Prolog
leftfact(N):-
leftfact(N, 0, 0, 1).
leftfact(N, N, _, _):-
!.
leftfact(N, M, L, F):-
((M =< 10 ; (M =< 110, 0 is M mod 10)) ->
writef("!%w = %w\n", [M, L])
;
(0 is M mod 1000 ->
number_string(L, S),
string_length(S, Len),
writef("length of !%w is %w\n", [M, Len])
;
true)),
L1 is L + F,
M1 is M + 1,
F1 is F * M1,
leftfact(N, M1, L1, F1).
main:-
leftfact(10001).
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 length of !1000 is 2565 length of !2000 is 5733 length of !3000 is 9128 length of !4000 is 12670 length of !5000 is 16322 length of !6000 is 20062 length of !7000 is 23875 length of !8000 is 27749 length of !9000 is 31678 length of !10000 is 35656
Python
from itertools import islice
def lfact():
yield 0
fact, summ, n = 1, 0, 1
while 1:
fact, summ, n = fact*n, summ + fact, n + 1
yield summ
print('first 11:\n %r' % [lf for i, lf in zip(range(11), lfact())])
print('20 through 110 (inclusive) by tens:')
for lf in islice(lfact(), 20, 111, 10):
print(lf)
print('Digits in 1,000 through 10,000 (inclusive) by thousands:\n %r'
% [len(str(lf)) for lf in islice(lfact(), 1000, 10001, 1000)] )
- Output:
first 11: [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 (inclusive) by thousands: [2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656]
Or, sidestepping the use of while and yield, we can directly define left factorials in terms of the scanl abstraction
(a fold or catamorphism, like functools.reduce, but one which returns the whole accumulation of intermediate values – see, for example, The Algebra of Programming, Bird and de Moor, 1997).
scanl in turn, has a natural definition in terms of the itertools functions accumulate and chain.
'''Left factorials'''
from itertools import (accumulate, chain, count, islice)
from operator import (mul, add)
# leftFact :: [Integer]
def leftFact():
'''Left factorial series defined in terms
of the factorial series.
'''
return accumulate(
chain([0], fact()), add
)
# fact :: [Integer]
def fact():
'''The factorial series.
'''
return accumulate(
chain([1], count(1)), mul
)
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''Tests'''
print(
'Terms 0 thru 10 inclusive:\n %r'
% take(11)(leftFact())
)
print('\nTerms 20 thru 110 (inclusive) by tens:')
for x in takeFromThenTo(20)(30)(110)(leftFact()):
print(x)
print(
'\n\nDigit counts for terms 1k through 10k (inclusive) by k:\n %r'
% list(map(
compose(len)(str),
takeFromThenTo(1000)(2000)(10000)(
leftFact()
)
))
)
# ----------------------- GENERIC ------------------------
# compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
def compose(g):
'''Function composition.'''
return lambda f: lambda x: g(f(x))
# scanl :: (b -> a -> b) -> b -> [a] -> [b]
def scanl(f):
'''scanl is like reduce, but defines a succession of
intermediate values, building from the left.
'''
def go(a):
def g(xs):
return accumulate(chain([a], xs), f)
return g
return go
# take :: Int -> [a] -> [a]
# take :: Int -> String -> String
def take(n):
'''The prefix of xs of length n,
or xs itself if n > length xs'''
return lambda xs: (
xs[0:n]
if isinstance(xs, list)
else list(islice(xs, n))
)
# takeFromThenTo :: Int -> Int -> Int -> [a] -> [a]
def takeFromThenTo(a):
'''Values drawn from a series betweens positions a and b
at intervals of size z'''
return lambda b: lambda z: lambda xs: islice(
xs, a, 1 + z, b - a
)
if __name__ == '__main__':
main()
- Output:
Terms 0 thru 10 inclusive: [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114] Terms 20 thru 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digit counts for terms 1k through 10k (inclusive) by k: [2565, 5733, 9128, 12670, 16322, 20062, 23875, 27749, 31678, 35656]
Quackery
[ 1 swap times [ i 1+ * ] ] is ! ( n --> n )
[ 0 swap times [ i ! + ] ] is !n ( n --> n )
say "First 11 left factorials:" cr
11 times [ i^ !n echo sp ] cr
cr
say "20 through 110 (inclusive) by tens:" cr
10 times [ i^ 2 + 10 * !n echo cr ]
cr
say "Digits in 1,000 through 10,000 by thousands:" cr
10 times [ i^ 1+ 1000 * !n number$ size echo cr ]
cr
- Output:
First 11 left factorials: 0 1 2 4 10 34 154 874 5914 46234 409114 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 by thousands: 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
R
Imperative solution
library(gmp)
left_factorial <- function(n) {
if (n == 0) return(0)
result <- as.bigz(0)
adder <- as.bigz(1)
for (k in 1:n) {
result <- result + adder
adder <- adder * k
}
result
}
digit_count <- function(n) {
nchar(as.character(n))
}
for (n in 0:10) {
cat("!",n," = ",sep = "")
cat(as.character(left_factorial(n)))
cat("\n")
}
for (n in seq(20,110,10)) {
cat("!",n," = ",sep = "")
cat(as.character(left_factorial(n)))
cat("\n")
}
for (n in seq(1000,10000,1000)) {
cat("!",n," has ",digit_count(left_factorial(n))," digits\n", sep = "")
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Vectorization solution
Due to vectorization, these sorts of problems are R's bread and butter. The only challenge comes from making sure that R plays nice with objects from the gmp library.
library(gmp)
leftFact <- function(numbs)
{
#As we will never actually use the numeric values of our outputs, we will
#immediately coerce them to characters. For technical reasons to do with
#nchar misbehaving, this also makes task 3 much easier.
#As task 1 will demonstrate, the n=0 special case is covered.
sapply(numbs, function(n) as.character(sum(factorialZ(seq_len(n)-1))))
}
printer <- function(inputs) print(data.frame(Value = leftFact(inputs), row.names = paste0("!", inputs)))
#Task 1
printer(0:10)
#Task 2
printer(seq(20, 110, by = 10))
#Task 3
inputs<-seq(1000, 10000, by = 1000)
print(data.frame(Digits = sapply(leftFact(inputs), nchar), row.names = paste0("!", inputs)))
- Output:
> printer(0:10) Value !0 0 !1 1 !2 2 !3 4 !4 10 !5 34 !6 154 !7 874 !8 5914 !9 46234 !10 409114 > printer(seq(20, 110, by = 10)) Value !20 128425485935180314 !30 9157958657951075573395300940314 !40 20935051082417771847631371547939998232420940314 !50 620960027832821612639424806694551108812720525606160920420940314 !60 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 > print(data.frame(Digits = sapply(leftFact(inputs), nchar), row.names = paste0("!", inputs))) Digits !1000 2565 !2000 5733 !3000 9128 !4000 12670 !5000 16322 !6000 20062 !7000 23875 !8000 27749 !9000 31678 !10000 35656
Racket
#lang racket
(define ! (let ((rv# (make-hash))) (λ (n) (hash-ref! rv# n (λ () (if (= n 0) 1 (* n (! (- n 1)))))))))
(define (!n n)
;; note that in-range n is from 0 to n-1 inclusive
(for/sum ((k (in-range n))) (! k)))
(define (dnl. s) (for-each displayln s))
(dnl
"Display the left factorials for:"
"zero through ten (inclusive)"
(pretty-format (for/list ((i (in-range 0 (add1 10)))) (!n i)))
"20 through 110 (inclusive) by tens"
(pretty-format (for/list ((i (in-range 20 (add1 110) 10))) (!n i)))
"Display the length (in decimal digits) of the left factorials for:"
"1,000, 2,000 through 10,000 (inclusive), by thousands."
(pretty-format (for/list ((i (in-range 1000 10001 1000))) (add1 (order-of-magnitude (!n i))))))
- Output:
Display the left factorials for: zero through ten (inclusive) '(0 1 2 4 10 34 154 874 5914 46234 409114) 20 through 110 (inclusive) by tens '(128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314) Display the length (in decimal digits) of the left factorials for: 1,000, 2,000 through 10,000 (inclusive), by thousands. '(2565 5733 9128 12670 16322 20062 23875 27749 31678 35656)
Raku
(formerly Perl 6)
Implement left factorial as a prefix !. Note that this redefines the core prefix ! (not) function.
sub prefix:<!> ($k) { (constant l = 0, |[\+] 1, (|[\*] 1..*))[$k] }
$ = !10000; # Pre-initialize
.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, !$_ };
.say for (1000, 2000 … 10000).hyper(:4batch).map: { sprintf "!%d has %d digits.", $_, chars !$_ };
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits. !2000 has 5733 digits. !3000 has 9128 digits. !4000 has 12670 digits. !5000 has 16322 digits. !6000 has 20062 digits. !7000 has 23875 digits. !8000 has 27749 digits. !9000 has 31678 digits. !10000 has 35656 digits.
If you would rather not override prefix ! operator and you can live with just defining lazy lists and indexing into them, this should suffice; (and is in fact very slightly faster than the first example since it avoids routine dispatch overhead):
constant leftfact = 0, |[\+] 1, (|[\*] 1..*);
$ = leftfact[10000]; # Pre-initialize
.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, leftfact[$_] };
.say for (1000, 2000 … 10000).hyper(:4batch).map: { sprintf "!%d has %d digits.", $_, chars leftfact[$_] };
Same output.
REXX
Programmer's note: this REXX version automatically adjusts the number of decimal digits (precision) after the factorial is calculated.
This is possible because there will be a number of trailing zeros which allow a floating point number to be converted to an integer.
/*REXX program computes/display the left factorial (or its dec. width) of N (or a range)*/
parse arg bot top inc . /*obtain optional arguments from the CL*/
if bot=='' | bot=="," then bot= 1 /*Not specified: Then use the default.*/
if top=='' | top=="," then top= bot /* " " " " " " */
if inc='' | inc=="," then inc= 1 /* " " " " " " */
tell= bot<0 /*if BOT < 0, only show # of digits. */
bot= abs(bot) /*use the │bot│ for the DO loop. */
w= length(top) /*width of the largest number request. */
do j=bot to top by inc /*traipse through the numbers requested*/
if tell then say 'left ! of ' right(j,w) " ───► " length(L!(j)) ' digits'
else say 'left ! of ' right(j,w) " ───► " L!(j)
end /*j*/ /* [↑] show either L! or # of digits*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
L!: procedure; parse arg x .; if x<3 then return x; $= 4; != 2 /*some shortcuts.*/
do #=3 to x-1; != ! * # /*compute L! for all numbers ─── ► X.*/
if pos(., !)\==0 then numeric digits digits() * 3 % 2 /*bump dec. digs.*/
$= $ + ! /*add the factorial ───► L! sum. */
end /*#*/ /* [↑] handles gihugeic numbers. */
return $ /*return the sum (L!) to the invoker.*/
- output when using the input of: 0 10
left ! of 0 ───► 0 left ! of 1 ───► 1 left ! of 2 ───► 2 left ! of 3 ───► 4 left ! of 4 ───► 10 left ! of 5 ───► 34 left ! of 6 ───► 154 left ! of 7 ───► 874 left ! of 8 ───► 5914 left ! of 9 ───► 46234 left ! of 10 ───► 409114
- output when using the input of: 20 110 10
left ! of 20 ───► 128425485935180314 left ! of 30 ───► 9157958657951075573395300940314 left ! of 40 ───► 20935051082417771847631371547939998232420940314 left ! of 50 ───► 620960027832821612639424806694551108812720525606160920420940314 left ! of 60 ───► 141074930726669571000530822087000522211656242116439949000980378746128920420940314 left ! of 70 ───► 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 left ! of 80 ───► 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 left ! of 90 ───► 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 left ! of 100 ───► 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 left ! of 110 ───► 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314
- output when using the input of: -1000 10000 1000
left ! of 1000 ───► 2565 digits left ! of 2000 ───► 5733 digits left ! of 3000 ───► 9128 digits left ! of 4000 ───► 12670 digits left ! of 5000 ───► 16322 digits left ! of 6000 ───► 20062 digits left ! of 7000 ───► 23875 digits left ! of 8000 ───► 27749 digits left ! of 9000 ───► 31678 digits left ! of 10000 ───► 35656 digits
Ring
a = leftFact(0,10,1)
see "" + a + nl
func leftFact f,t,s
see "------ From " + f + " --To -> " + t +" Step " + s + " -------" + nl
for i = f to t step s
leftFact = 1
fct = 1
for j = 1 to i - 1
fct = fct * j
leftFact = leftFact + fct
next
if i >= 1000 see "" + i + " " + len(string(leftFact)) + " digits" + nl
else see "" + i + " " + leftFact + nl ok
next
Ruby
left_fact = Enumerator.new do |y|
f, lf = 1, 0
1.step do |n|
y << lf #yield left_factorial
lf += f
f *= n
end
end
Test:
tens = 20.step(110, 10)
thousands = 1000.step(10_000, 1000)
10001.times do |n|
lf = left_fact.next
case n
when 0..10, *tens
puts "!#{n} = #{lf}"
when *thousands
puts "!#{n} has #{lf.to_s.size} digits"
end
end
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Run BASIC
a = lftFct(0,10,1)
a = lftFct(20,110,10)
a = lftFct(1000,10000,1000)
function lftFct(f,t,s)
print :print "------ From ";f;" --To-> ";t;" Step ";s;" -------"
for i = f to t step s
lftFct = 1
fct = 1
for j = 1 to i-1
fct = fct * j
lftFct = lftFct + fct
next j
if i >= 1000 then
print i;" ";len(str$(lftFct));" "digits"
else
print i;" ";lftFct
end if
next i
end function
Output:
------ From 0 --To-> 10 Step 1 ------- 0 1 1 1 2 2 3 4 4 10 5 34 6 154 7 874 8 5914 9 46234 10 409114 ------ From 20 --To-> 110 Step 10 ------- 20 128425485935180314 30 9157958657951075573395300940314 40 20935051082417771847631371547939998232420940314 50 620960027832821612639424806694551108812720525606160920420940314 60 141074930726669571000530822087000522211656242116439949000980378746128920420940314 70 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 80 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 90 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 100 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 110 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 ------ From 1000 --To-> 10000 Step 1000 ------- 1000 2565 digits 2000 5733 digits 3000 9128 digits 4000 12670 digits 5000 16322 digits 6000 20062 digits 7000 23875 digits 8000 27749 digits 9000 31678 digits 10000 35656 digits
Rust
#[cfg(target_pointer_width = "64")]
type USingle = u32;
#[cfg(target_pointer_width = "64")]
type UDouble = u64;
#[cfg(target_pointer_width = "64")]
const WORD_LEN: i32 = 32;
#[cfg(not(target_pointer_width = "64"))]
type USingle = u16;
#[cfg(not(target_pointer_width = "64"))]
type UDouble = u32;
#[cfg(not(target_pointer_width = "64"))]
const WORD_LEN: i32 = 16;
use std::cmp;
#[derive(Debug,Clone)]
struct BigNum {
// rep_.size() == 0 if and only if the value is zero.
// Otherwise, the word rep_[0] keeps the least significant bits.
rep_: Vec<USingle>,
}
impl BigNum {
pub fn new(n: USingle) -> BigNum {
let mut result = BigNum { rep_: vec![] };
if n > 0 { result.rep_.push(n); }
result
}
pub fn equals(&self, n: USingle) -> bool {
if n == 0 { return self.rep_.is_empty() }
if self.rep_.len() > 1 { return false }
self.rep_[0] == n
}
pub fn add_big(&self, addend: &BigNum) -> BigNum {
let mut result = BigNum::new(0);
let mut sum = 0 as UDouble;
let sz1 = self.rep_.len();
let sz2 = addend.rep_.len();
for i in 0..cmp::max(sz1, sz2) {
if i < sz1 { sum += self.rep_[i] as UDouble }
if i < sz2 { sum += addend.rep_[i] as UDouble }
result.rep_.push(sum as USingle);
sum >>= WORD_LEN;
}
if sum > 0 { result.rep_.push(sum as USingle) }
result
}
pub fn multiply(&self, factor: USingle) -> BigNum {
let mut result = BigNum::new(0);
let mut product = 0 as UDouble;
for i in 0..self.rep_.len() {
product += self.rep_[i] as UDouble * factor as UDouble;
result.rep_.push(product as USingle);
product >>= WORD_LEN;
}
if product > 0 {
result.rep_.push(product as USingle);
}
result
}
pub fn divide(&self, divisor: USingle, quotient: &mut BigNum,
remainder: &mut USingle) {
quotient.rep_.truncate(0);
let mut dividend: UDouble;
*remainder = 0;
for i in 0..self.rep_.len() {
let j = self.rep_.len() - 1 - i;
dividend = ((*remainder as UDouble) << WORD_LEN)
+ self.rep_[j] as UDouble;
let quo = (dividend / divisor as UDouble) as USingle;
*remainder = (dividend % divisor as UDouble) as USingle;
if quo > 0 || j < self.rep_.len() - 1 {
quotient.rep_.push(quo);
}
}
quotient.rep_.reverse();
}
fn to_string(&self) -> String {
let mut rep = String::new();
let mut dividend = (*self).clone();
let mut remainder = 0 as USingle;
let mut quotient = BigNum::new(0);
loop {
dividend.divide(10, &mut quotient, &mut remainder);
rep.push(('0' as USingle + remainder) as u8 as char);
if quotient.equals(0) { break; }
dividend = quotient.clone();
}
rep.chars().rev().collect::<String>()
}
}
use std::fmt;
impl fmt::Display for BigNum {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}", self.to_string())
}
}
fn lfact(n: USingle) -> BigNum {
let mut result = BigNum::new(0);
let mut f = BigNum::new(1);
for k in 1 as USingle..n + 1 {
result = result.add_big(&f);
f = f.multiply(k);
}
result
}
fn main() {
for i in 0..11 {
println!("!{} = {}", i, lfact(i));
}
for i in 2..12 {
let j = i * 10;
println!("!{} = {}", j, lfact(j));
}
for i in 1..11 {
let j = i * 1000;
println!("!{} has {} digits.", j, lfact(j).to_string().len());
}
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits. !2000 has 5733 digits. !3000 has 9128 digits. !4000 has 12670 digits. !5000 has 16322 digits. !6000 has 20062 digits. !7000 has 23875 digits. !8000 has 27749 digits. !9000 has 31678 digits. !10000 has 35656 digits.
Faster alternative
This solution uses the arbitrary precision integers from the rug crate, which uses GMP under the covers.
// [dependencies]
// rug = "1.9"
fn left_factorials() -> impl std::iter::Iterator<Item = rug::Integer> {
use rug::Integer;
let mut factorial = Integer::from(1);
let mut next = Integer::from(0);
let mut n = 1;
std::iter::from_fn(move || {
let result = next.clone();
next += &factorial;
factorial *= n;
n += 1;
Some(result)
})
}
fn main() {
let mut lf = left_factorials().take(10001).enumerate();
println!("Left factorials 0 through 10:");
for (i, n) in lf.by_ref().take(11) {
println!("!{} = {}", i, n);
}
println!("Left factorials 20 through 110, by tens:");
for (i, n) in lf.by_ref().take(100).skip(9).step_by(10) {
println!("!{} = {}", i, n);
}
println!("Lengths of left factorials 1000 through 10000, by thousands:");
for (i, n) in lf.skip(1000 - 111).step_by(1000) {
println!("length of !{} = {}", i, n.to_string().len());
}
}
- Output:
Left factorials 0 through 10: !0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 Left factorials 20 through 110, by tens: !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Lengths of left factorials 1000 through 10000, by thousands: length of !1000 = 2565 length of !2000 = 5733 length of !3000 = 9128 length of !4000 = 12670 length of !5000 = 16322 length of !6000 = 20062 length of !7000 = 23875 length of !8000 = 27749 length of !9000 = 31678 length of !10000 = 35656
Scala
object LeftFactorial extends App {
// this part isn't really necessary, it just shows off Scala's ability
// to match the mathematical syntax: !n
implicit class RichInt(n:Int) {
def unary_!() = factorial.take(n).sum
}
val factorial: Stream[BigInt] = 1 #:: factorial.zip(Stream.from(1)).map(n => n._2 * factorial(n._2 - 1))
for (n <- (0 to 10) ++
(20 to 110 by 10);
value = !n) {
println(s"!${n} = ${value}")
}
for (n <- 1000 to 10000 by 1000;
length = (!n).toString.length) {
println(s"length !${n} = ${length}")
}
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 length !1000 = 2565 length !2000 = 5733 length !3000 = 9128 length !4000 = 12670 length !5000 = 16322 length !6000 = 20062 length !7000 = 23875 length !8000 = 27749 length !9000 = 31678 length !10000 = 35656
Scheme
This version uses the iota method in the standard lists library. iota takes three values, a count, an optional start value (defaults to 0), and an optional step value (defaults to 1) so (iota 5) produces a list (0 1 2 3 4) and (iota 5 100 2) produces a list (100 102 104 106 108)
(import (scheme base) ;; library imports in R7RS style
(scheme write)
(srfi 1 lists))
(define (factorial n)
(fold * 1 (iota n 1)))
(define (left-factorial n)
(fold + 0 (map factorial (iota n))))
(define (show i r) ; to pretty print the results
(display "!") (display i) (display " ") (display r) (newline))
;; show left factorials for zero through ten (inclusive)
(for-each
(lambda (i) (show i (left-factorial i)))
(iota 11))
;; show left factorials for 20 through 110 (inclusive) by tens
(for-each
(lambda (i) (show i (left-factorial i)))
(iota 10 20 10))
;; number of digits in 1000 through 10000 by thousands:
(for-each
(lambda (i) (show i (string-length (number->string (left-factorial i)))))
(iota 10 1000 1000))
Seed7
$ include "seed7_05.s7i";
include "bigint.s7i";
const func bigInteger: leftFact (in integer: n) is func
result
var bigInteger: leftFact is 0_;
local
var bigInteger: factorial is 1_;
var integer: i is 0;
begin
for i range 1 to n do
leftFact +:= factorial;
factorial *:= bigInteger conv i;
end for;
end func;
const proc: main is func
local
var integer: n is 0;
begin
writeln("First 11 left factorials:");
for n range 0 to 10 do
write(" " <& leftFact(n));
end for;
writeln;
writeln("20 through 110 (inclusive) by tens:");
for n range 20 to 110 step 10 do
writeln(leftFact(n));
end for;
writeln;
writeln("Digits in 1,000 through 10,000 by thousands:");
for n range 1000 to 10000 step 1000 do
writeln(length(str(leftFact(n))));
end for;
writeln;
end func;
- Output:
First 11 left factorials: 0 1 2 4 10 34 154 874 5914 46234 409114 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 by thousands: 2565 5733 9128 12670 16322 20062 23875 27749 31678 35656
Sidef
Built-in:
say 20.of { .left_factorial }
Straightforward:
func left_factorial(n) {
^n -> sum { _! }
}
Alternatively, using Range.reduce():
func left_factorial(n) {
^n -> reduce({ |a,b| a + b! }, 0)
}
A faster approach:
func left_factorial(n) {
static cached = 0
static factorial = 1
static leftfact = 0
if (n < cached) {
cached = 0
factorial = 1
leftfact = 0
}
while (n > cached) {
leftfact += factorial
factorial *= ++cached
}
leftfact
}
Completing the task:
for n in (0..10, 20..110 `by` 10) {
printf("!%d = %s\n", n, left_factorial(n))
}
for n in (1000..10000 `by` 1000) {
printf("!%d has %d digits.\n", n, left_factorial(n).len)
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits. !2000 has 5733 digits. !3000 has 9128 digits. !4000 has 12670 digits. !5000 has 16322 digits. !6000 has 20062 digits. !7000 has 23875 digits. !8000 has 27749 digits. !9000 has 31678 digits. !10000 has 35656 digits.
Standard ML
(* reuse earlier factorial calculations in dfac, apply to listed arguments in cumlfac *)
(* example: left factorial n, is #3 (dfac (0,n-1,1,1) ) *)
(* output list contains (number, factorial, left factorial) *)
(* tested in PolyML *)
val store = ref 0;
val rec dfac = fn
(from,to,acc,cm) => if from = to then (from,acc,cm) else (store:=(from+1)*acc;dfac (from+1,to,!store,!store+cm ) );
val rec cumlfac = fn
(x::y::rm) => x :: cumlfac ( dfac (#1 x, #1 y, #2 x, #3 x) :: rm ) |
rm =>rm ;
val arguments = List.tabulate (10,fn 0=>(0,1,1)|i=>(i,0,0)) @
List.tabulate (10,fn i=> (10*i+19,0,0) ) @
List.tabulate ( 10,fn i=> (1000*i+999,0,0));
val result = (~1,0,0)::(cumlfac arguments);
(* done *)
(* display: *)
List.app (fn triple :int*int*int =>
print(Int.toString (1+ #1 triple ) ^ " : " ^ Int.fmt StringCvt.DEC (#3 triple ) ^" \n" )
) (List.take(result,21) ) ;
List.app (fn triple :int*int*int =>
print( Int.toString (1+ #1 triple ) ^ " : " ^ Int.toString (size(Int.toString (#3 triple ))) ^" \n" ) ) (List.drop(result,21) );
- Output:
time poly --script thisscript 0 : 0 1 : 1 2 : 2 3 : 4 4 : 10 5 : 34 6 : 154 7 : 874 8 : 5914 9 : 46234 10 : 409114 20 : 128425485935180314 30 : 9157958657951075573395300940314 40 : 20935051082417771847631371547939998232420940314 50 : 620960027832821612639424806694551108812720525606160920420940314 60 : 141074930726669571000530822087000522211656242116439949000980378746128920420940314 70 : 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 80 : 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 90 : 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 100 : 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 110 : 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 1000 : 2565 2000 : 5733 3000 : 9128 4000 : 12670 5000 : 16322 6000 : 20062 7000 : 23875 8000 : 27749 9000 : 31678 10000 : 35656 (CPU 2.1Ghz:) 0.36 real 0.29 user 0.08 sys
Swift
import BigInt
func factorial<T: BinaryInteger>(_ n: T) -> T {
guard n != 0 else {
return 1
}
return stride(from: n, to: 0, by: -1).reduce(1, *)
}
prefix func ! <T: BinaryInteger>(n: T) -> T {
guard n != 0 else {
return 0
}
return stride(from: 0, to: n, by: 1).lazy.map(factorial).reduce(0, +)
}
for i in 0...10 {
print("!\(i) = \(!i)")
}
print()
for i in stride(from: BigInt(20), through: 110, by: 10) {
print("!\(i) = \(!i)")
}
print()
print("!1000 = \((!BigInt(1000)).description.count) digit number")
print()
for i in stride(from: BigInt(2000), through: 10_000, by: 1000) {
print("!\(i) = \((!i).description.count) digit number")
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 = 2565 digit number !2000 = 5733 digit number !3000 = 9128 digit number !4000 = 12670 digit number !5000 = 16322 digit number !6000 = 20062 digit number !7000 = 23875 digit number !8000 = 27749 digit number !9000 = 31678 digit number !10000 = 35656 digit number
Tcl
proc leftfact {n} {
set s 0
for {set i [set f 1]} {$i <= $n} {incr i} {
incr s $f
set f [expr {$f * $i}]
}
return $s
}
for {set i 0} {$i <= 110} {incr i [expr {$i>9?10:1}]} {
puts "!$i = [leftfact $i]"
}
for {set i 1000} {$i <= 10000} {incr i 1000} {
puts "!$i has [string length [leftfact $i]] digits"
}
- Output:
!0 = 0 !1 = 1 !2 = 2 !3 = 4 !4 = 10 !5 = 34 !6 = 154 !7 = 874 !8 = 5914 !9 = 46234 !10 = 409114 !20 = 128425485935180314 !30 = 9157958657951075573395300940314 !40 = 20935051082417771847631371547939998232420940314 !50 = 620960027832821612639424806694551108812720525606160920420940314 !60 = 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 = 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 = 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 = 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 = 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 = 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 !1000 has 2565 digits !2000 has 5733 digits !3000 has 9128 digits !4000 has 12670 digits !5000 has 16322 digits !6000 has 20062 digits !7000 has 23875 digits !8000 has 27749 digits !9000 has 31678 digits !10000 has 35656 digits
Wren
import "/fmt" for Fmt
import "/big" for BigInt
var lfacts = List.filled(12, BigInt.zero)
var lfact = BigInt.one
var sum = BigInt.zero
for (i in 1..10) {
sum = sum + lfact
lfacts[i] = sum
lfact = lfact * i
}
System.print("Left factorials from 0 to 10:")
for (i in 0..10) System.write(" %(lfacts[i])")
for (i in 11..110) {
sum = sum + lfact
if (i%10 == 0) lfacts[i/10] = sum
lfact = lfact * i
}
System.print("\n\nLeft factorials from 20 to 110 by tens:")
for (i in 2..11) Fmt.print(" !$-3d -> $s", i * 10, lfacts[i])
for (i in 111..10000) {
sum = sum + lfact
if (i%1000 == 0) lfacts[i/1000] = sum
lfact = lfact * i
}
System.print("\nLengths of left factorals from 1000 to 10000 by thousands:")
for (i in 1..10) Fmt.print(" !$-5d -> $5s", i * 1000, lfacts[i].toString.count)
- Output:
Left factorials from 0 to 10: 0 1 2 4 10 34 154 874 5914 46234 409114 Left factorials from 20 to 110 by tens: !20 -> 128425485935180314 !30 -> 9157958657951075573395300940314 !40 -> 20935051082417771847631371547939998232420940314 !50 -> 620960027832821612639424806694551108812720525606160920420940314 !60 -> 141074930726669571000530822087000522211656242116439949000980378746128920420940314 !70 -> 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 !80 -> 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 !90 -> 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 !100 -> 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 !110 -> 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Lengths of left factorals from 1000 to 10000 by thousands: !1000 -> 2565 !2000 -> 5733 !3000 -> 9128 !4000 -> 12670 !5000 -> 16322 !6000 -> 20062 !7000 -> 23875 !8000 -> 27749 !9000 -> 31678 !10000 -> 35656
zkl
var BN=Import("zklBigNum");
fcn leftFact(n){
[1..n].reduce(fcn(p,n,rf){ p+=rf.value; rf.set(rf.value*n); p },
BN(0),Ref(BN(1)));
}
println("First 11 left factorials:\n", [0..10].apply(leftFact));
lfs:=[20..111,10].apply(leftFact);
println(("\n20 through 110 (inclusive) by tens:\n" +
"%d\n"*lfs.len()).fmt(lfs.xplode()));
println("Digits in 1,000 through 10,000 by thousands:\n",
[0d1_000..0d10_000, 1000].pump(List,fcn(n){leftFact(n).toString().len()}));
- Output:
First 11 left factorials: L(0,1,2,4,10,34,154,874,5914,46234,409114) 20 through 110 (inclusive) by tens: 128425485935180314 9157958657951075573395300940314 20935051082417771847631371547939998232420940314 620960027832821612639424806694551108812720525606160920420940314 141074930726669571000530822087000522211656242116439949000980378746128920420940314 173639511802987526699717162409282876065556519849603157850853034644815111221599509216528920420940314 906089587987695346534516804650290637694024830011956365184327674619752094289696314882008531991840922336528920420940314 16695570072624210767034167688394623360733515163575864136345910335924039962404869510225723072235842668787507993136908442336528920420940314 942786239765826579160595268206839381354754349601050974345395410407078230249590414458830117442618180732911203520208889371641659121356556442336528920420940314 145722981061585297004706728001906071948635199234860720988658042536179281328615541936083296163475394237524337422204397431927131629058103519228197429698252556442336528920420940314 Digits in 1,000 through 10,000 by thousands: L(2565,5733,9128,12670,16322,20062,23875,27749,31678,35656)
- Programming Tasks
- Solutions by Programming Task
- Mathematics
- 11l
- ALGOL 68
- AWK
- BBC BASIC
- Bracmat
- C
- GMP
- C sharp
- C++
- Clojure
- Common Lisp
- D
- EchoLisp
- Elixir
- F Sharp
- Factor
- Forth
- Fortran
- FreeBASIC
- Fōrmulæ
- Frink
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- Jq
- Julia
- Kotlin
- Lambdatalk
- Lua
- Maple
- Mathematica
- Wolfram Language
- Nim
- Oforth
- PARI/GP
- Perl
- Phix
- Phix/mpfr
- PicoLisp
- PL/I
- PowerShell
- Prolog
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- Ruby
- Run BASIC
- Rust
- Scala
- Scheme
- Seed7
- Sidef
- Standard ML
- Swift
- AttaSwift BigInt
- Tcl
- Wren
- Wren-fmt
- Wren-big
- Zkl