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:


   



!
n
=

∑

k
=
0


n
−
1


k
!


{\displaystyle !n=\sum _{k=0}^{n-1}k!}




 where


   



!
0
=
0


{\displaystyle !0=0}






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

   permutations/derangements (subfactorials)


 
'''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
 
 