Left factorials
You are encouraged to solve this task according to the task description, using any language you may know.
Left factorials, , may refer to either subfactorials or to factorial sums; the same notation can be confusingly seen used for the two different definitions. Sometimes, subfactorials (also known as derangements) use the notations: !n` or or n¡.
This Rosetta Code task will be using this formula 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, 2,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]
D
<lang d>import std.stdio, std.bigint, std.range, std.algorithm, std.conv;
BigInt leftFact(in uint n) pure /*nothrow*/ {
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(1000,10001, 1000).map!(i => i.leftFact.text.length));
}</lang>
- 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]
Go
<lang 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()
}</lang>
- 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
<lang haskell>fact :: [Integer] fact = scanl (*) 1 [1..]
leftFact :: [Integer] leftFact = scanl (+) 0 fact
main = do
putStrLn "0 ~ 10:" putStrLn $ show $ map (\n -> leftFact !! n) [0..10] putStrLn ""
putStrLn "20 ~ 110 by tens:" putStrLn $ unlines $ map show $ map (\n -> leftFact !! n) [20,30..110] putStrLn ""
putStrLn "length of 1,000 ~ 10,000 by thousands:" putStrLn $ show $ map (\n -> length $ show $ leftFact !! n) [1000,2000..10000] putStrLn ""</lang>
- 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: <lang>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</lang>
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.
<lang J>leftFact=: +/@:!@i."0</lang>
Task examples:
<lang J> (,. 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</lang>
PARI/GP
<lang parigp>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))", "))</lang>
- 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 6
Perl 6 doesn't have a built in factorial function, so the first two lines implement postfix ! factorial. The newly implemented factorial function is used to implement left factorial using a prefix ! in the next two lines. Note that this redefines the core prefix ! (not) function. The last two lines are display code for the various sub task requirements.
<lang perl6>multi sub postfix:<!> (0) { 1 }; multi sub postfix:<!> ($n) { [*] 1 .. $n }; multi sub prefix:<!> (0) { 0 }; multi sub prefix:<!> ($k) { [+] (^$k).map: { $_! } }
printf "!%d = %s\n", $_, !$_ for ^11, 20, 30 ... 110; printf "!%d has %d digits.\n", $_, (!$_).chars for 1000, 2000 ... 10000;</lang>
- 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.
While the code above seems like a pretty decent "mathematical" way to write this, it's far from efficient, since it's recalculating every factorial many times for each individual left factorial, not to mention for each subsequent left factorial, so it's something like an O(N^3) algorithm, not even counting the sizes of the numbers as one of the dimensions. In Perl 6, a more idiomatic way is to write these functions as constant "triangular reduction" sequences; this works in O(N)-ish time because the sequences never have to recalculate a prior result: <lang perl6>constant fact = 1, [\*] 1..*; constant leftfact = 0, [\+] fact;
printf "!%d = %s\n", $_, leftfact[$_] for 0 ... 10, 20 ... 110; printf "!%d has %d digits.\n", $_, leftfact[$_].chars for 1000, 2000 ... 10000;</lang> Note that we just use subscripting on the list rather than an explicit function call to retrieve the desired values. If you time these two solutions, the second will run about 280 times faster than the first.
In this case, since we aren't actually interested in the factorials, we could have just written combined the two definitions into one: <lang perl6>constant leftfact = 0, [\+] 1, [\*] 1..*;</lang> (No significant difference in run time.)
Python
<lang 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)] )</lang>
- 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]
REXX
<lang rexx>/*REXX pgm computes/shows the left factorial (or width) of N (or range).*/ parse arg bot top inc . /*obtain optional args from C.L. */ if bot== then bot=1 /*BOT defined? Then use default.*/ td= bot<0 /*if BOT < 0, only show # digs.*/ bot=abs(bot) /*use the |bot| for the DO loop.*/ if top== then top=bot /* " " top " " " " */ if inc= then inc=1 /* " " inc " " " " */ @='left ! of ' /*a literal used in the display. */ w=length(H) /*width of largest number request*/
do j=bot to top by inc /*traipse through #'s requested.*/ if td then say @ right(j,w) " ───► " length(L!(j)) ' digits' else say @ right(j,w) " ───► " L!(j) end /*j*/ /* [↑] show either L! or #digits*/
exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────L! subroutine───────────────────────*/ L!: procedure; parse arg x .; if x<3 then return x; s=4 /*shortcuts.*/ !=2; do f=3 to x-1 /*compute L! for all numbers───►X*/
!=!*f /*compute intermediate factorial.*/ if pos(.,!)\==0 then numeric digits digits()*1.5%1 /*bump digs.*/ s=s+! /*add the factorial ───► L! sum.*/ end /*f*/ /* [↑] handles gi-hugeic numbers*/
return s /*return the sum (L!) to invoker.*/</lang> output when using the input: 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: 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: -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
Ruby
<lang ruby>left_fact = Enumerator.new do |y|
n, f, lf = 0, 1, 0 loop do y << lf #yield left_factorial n += 1 lf += f f *= n end
end
tens = 20.step(110, 10).to_a thousands = 1000.step(10_000, 1000).to_a
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 </lang>
- 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
Tcl
<lang 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"
}</lang>
- 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