Left factorials: Difference between revisions

{{trans|D}}

BigInt result = 0

BigInt factorial = 1

print(left_fact(i))

print("\nDigits in 1,000 through 10,000 by thousands:")

{{out}}

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

PR precision 36000 PR

# stores left factorials in an array #

OD

END

{{out}}

<pre>

=={{header|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) {

}

}

{{out}}

<pre>

{{works with|BBC BASIC for Windows}}

Use the 'Mapm' library.

Result$="0" : A$="1"

IF I% > 999 IF I% MOD 1000 = 0 PRINT "!";I% " has " LENFNMAPM_FormatDec(Result$,0) " digits"

NEXT

{{out}}

<pre>

=={{header|Bracmat}}==

{{trans|D}}

= result factorial i

. 0:?result

. (=L.@(!arg:? [?L)&out$!L)

)

{{out}}

<pre>First 11 left factorials:

=={{header|C}}==

{{libheader|GMP}}

#include <stdio.h>

#include <stdlib.h>

return 0;

}

{{out}}

<pre>

=={{header|C sharp|C#}}==

using System;

using System.Numerics;

}

}

{{out}}

<pre>

Faster Implementation

using System;

using System.Numerics;

}

}

=={{header|C++}}==

#include <vector>

#include <string>

}

}

{{out}}

<pre>

===Faster alternative===

{{libheader|GMP}}

#include <gmpxx.h>

}

return 0;

{{out}}

=={{header|Clojure}}==

(:gen-class))

(doseq [n (range 1000 10001 1000)]

(println (format "!%-5d has %5d digits" n (count (str (biginteger (left-factorial n)))))))

{{Output}}

<pre>

=={{header|Common Lisp}}==

(defun fact (n)

(reduce #'* (loop for i from 1 to n collect 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)))))

{{out}}

<pre>

=={{header|D}}==

BigInt leftFact(in uint n) pure nothrow /*@safe*/ {

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));

{{out}}

<pre>First 11 left factorials:

=={{header|EchoLisp}}==

We use the 'bigint' library and memoization : (remember 'function).

(lib 'bigint)

(define (!n n)

(+ (!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)))

Digits of !n(9000) = 31678

Digits of !n(10000) = 35656

=={{header|Elixir}}==

def calc(0), do: 0

def calc(n) do

digits = LeftFactorial.calc(i) |> to_char_list |> length

IO.puts "!#{i} has #{digits} digits"

{{out}}

=={{header|F_Sharp|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")

{{out}}

<pre>

</pre>

;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)

{{out}}

<pre>

</pre>

;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)

{{out}}

<pre>

=={{header|Factor}}==

{{works with|Factor|0.98}}

math.functions math.parser math.ranges sequences ;

IN: rosetta-code.left-factorials

: main ( -- ) part1 part2 part3 ;

{{out}}

<pre>

{{works with|Gforth 0.7.3}}

This solution inspired by the Fortran one.

CREATE S #DIGITS ALLOT S #DIGITS ERASE VARIABLE S#

CREATE F #DIGITS ALLOT F #DIGITS ERASE VARIABLE F#

dup REPORT

dup F F# @ rot B* F# !

{{out}}

<pre>$ gforth left-factorials.fs -e 'GO bye'

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.

CONTAINS !The usual suspects.

INTEGER*8 FUNCTION FACT(N) !Factorial, the ordinary.

WRITE (6,1) I,LFACT(I)

END DO

Output:

</pre>

INTEGER ENUFF,BASE !Some parameters.

PARAMETER (BASE = 10, ENUFF = 40000) !This should do.

END DO !If there is one, as when N > BASE.

END DO !On to the next result.

Output: achieved in a few seconds. A larger BASE would give a faster calculation, but would complicate the digit count.

<pre>

{{trans|C}}

{{libheader|GMP}}

#include "gmp.bi"

Print

Print "Press any key to quit"

{{out}}

Frink contains efficient algorithms for calculating and caching factorials and this program will work for arbitrarily-large numbers.

{

sum = 0

println["\nlength of 1000 through 10000"]

for n = 1000 to 10000 step 1000

{{out}}

<pre>

=={{header|Go}}==

import (

}

fmt.Println()

{{out}}

<pre>

=={{header|Haskell}}==

leftFact = scanl (+) 0 fact

, show $ length . show . (leftFact !!) <$> [1000,2000 .. 10000]

, ""

{{Out}}

<pre>0 ~ 10:

{{trans|D}}

The following works in both languages:

every writes(lfact(0 | !10)," ")

write()

every (i := !n, r +:= .f, f *:= .i)

return r

{{out}}

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.

Task examples:

0 0

1 1

8000 27749

9000 31678

=={{header|Java}}==

public class LeftFac{

}

}

{{out}}

<pre>!0 = 0

'''Using builtin arithmetic''':

reduce range(1; .+1) as $i

# state: [i!, !i]

([1,0]; .[1] += .[0] | .[0] *= $i)

'''Using BigInt.jq''':

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.

# integer input

| (.[1] | tostring | length) as $lf

| if $i % gap == 0 then .[2] += [[$i, $lf]] else . end)

'''The specific tasks''':

{{out}}

(scrollable)

<div style="overflow:scroll; height:200px;">

0: 0

1: 1

8000: length is 27749

9000: length is 31678

</div>

{{works with|Julia|0.6}}

@show leftfactorial.(0:10)

{{out}}

=={{header|Kotlin}}==

import java.math.BigInteger

for (i in 1000..10000 step 1000)

println("!${i.toString().padEnd(5)} has ${leftFactorial(i).toString().length} digits")

{{out}}

The code can be tested in this wiki page: http://lambdaway.free.fr/lambdawalks/?view=left_factorial

'''1) defining !n'''

Digits of !n(10000) = 35656

=={{header|Lua}}==

Takes about five seconds...

require("bc")

for i = 1000, 10000, 1000 do

print("!" .. i .. " contains " .. #leftFac(i) .. " digits")

{{out}}

<pre>!0 = 0

=={{header|Maple}}==

seq(left_factorial(i), i = 1 .. 10);

seq(left_factorial(i), i = 20 .. 110, 10);

{{out}}

<pre>0, 1, 3, 9, 33, 153, 873, 5913, 46233, 409113

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Print["left factorials 0 through 10:"]

Print[left /@ Range[0, 10] // TableForm]

Print[left /@ Range[20, 110, 10] // TableForm]

Print["Digits in left factorials 1,000 through 10,000, by thousands:"]

{{out}}

<pre>left factorials 0 through 10:

=={{header|Nim}}==

{{trans|Python}}

proc lfact: iterator: BigInt =

echo "Digits in 1,000 through 10,000 (inclusive) by thousands:"

for i in lfact().slice(1_000, 10_000, 1_000):

{{out}}

<pre>first 11:

=={{header|Oforth}}==

{{out}}

=={{header|PARI/GP}}==

apply(lf, [0..10])

apply(lf, 10*[2..11])

{{out}}

<pre>%1 = [0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114]

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).

use 5.010;

use strict;

printf "!%d has %d digits.\n", $_, length leftfact($_) for map $_*1000, 1..10;

Since I copied the printf format strings from the Raku implementation,

{{trans|Lua}}

{{libheader|Phix/mpfr}}

<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;">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>

{{out}}

<pre>

=={{header|PicoLisp}}==

(cache '(NIL) N

(if (> 2 N) 1

(prinl "length of 1000 - 10000")

(pril (mapcar 'length (mapcar '!n (range 1000 10000 1000))))

{{out}}

1

1

31678

35656

=={{header|PL/I}}==

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.

declare n fixed binary;

declare (s, f) fixed (31);

end;

{{out}}

<pre>

=={{header|PowerShell}}==

{{works with|PowerShell|4.0}}

function left-factorial ([BigInt]$n) {

[BigInt]$k, [BigInt]$fact = ([BigInt]::Zero), ([BigInt]::One)

else {"!$i has $digits digit"}

}

<b>Output:</b>

<pre>

=={{header|Prolog}}==

{{works with|SWI Prolog}}

leftfact(N, 0, 0, 1).

main:-

{{out}}

=={{header|Python}}==

def lfact():

print(lf)

print('Digits in 1,000 through 10,000 (inclusive) by thousands:\n %r'

{{out}}

{{Trans|Haskell}}

from itertools import (accumulate, chain, count, islice)

if __name__ == '__main__':

{{Out}}

<pre>Terms 0 thru 10 inclusive:

=={{header|Quackery}}==

[ 0 swap times [ i ! + ] ] is !n ( n --> n )

say "Digits in 1,000 through 10,000 by thousands:" cr

10 times [ i^ 1+ 1000 * !n number$ size echo cr ]

{{out}}

=={{header|R}}==

===Imperative solution===

left_factorial <- function(n) {

cat("!",n," has ",digit_count(left_factorial(n))," digits\n", sep = "")

}

{{out}}

<pre>

===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.

leftFact <- function(numbs)

{

#Task 3

inputs<-seq(1000, 10000, by = 1000)

{{out}}

=={{header|Racket}}==

(define ! (let ((rv# (make-hash))) (λ (n) (hash-ref! rv# n (λ () (if (= n 0) 1 (* n (! (- n 1)))))))))

"Display the length (in decimal digits) of the left factorials for:"

"1,000, 2,000 through 10,000 (inclusive), by thousands."

{{out}}

Implement left factorial as a prefix !. Note that this redefines the core prefix ! (not) function.

$ = !10000; # Pre-initialize

.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, !$_ };

{{out}}

<pre>!0 = 0

!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):

$ = leftfact[10000]; # Pre-initialize

.say for ( 0 … 10, 20 … 110 ).hyper(:4batch).map: { sprintf "!%d = %s", $_, leftfact[$_] };

Same output.

This is possible because there will be a number of trailing zeros which allow a floating point number to be converted to an integer.

parse arg bot top inc . /*obtain optional arguments from the CL*/

if bot=='' | bot=="," then bot= 1 /*Not specified: Then use the default.*/

$= $ + ! /*add the factorial ───► L! sum. */

end /*#*/ /* [↑] handles gihugeic numbers. */

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 0 &nbsp; 10 </tt>}}

<pre>

=={{header|Ring}}==

a = leftFact(0,10,1)

see "" + a + nl

else see "" + i + " " + leftFact + nl ok

next

=={{header|Ruby}}==

f, lf = 1, 0

1.step do |n|

f *= n

end

'''Test:'''

thousands = 1000.step(10_000, 1000)

puts "!#{n} has #{lf.to_s.size} digits"

end

{{out}}

<pre>!0 = 0

=={{header|Run BASIC}}==

a = lftFct(20,110,10)

a = lftFct(1000,10000,1000)

end if

next i

<pre>------ From 0 --To-> 10 Step 1 -------

0 1

=={{header|Rust}}==

#[cfg(target_pointer_width = "64")]

type USingle = u32;

}

}

{{out}}

<pre>

This solution uses the arbitrary precision integers from the rug crate,

which uses GMP under the covers.

// rug = "1.9"

println!("length of !{} = {}", i, n.to_string().len());

}

{{out}}

=={{header|Scala}}==

// this part isn't really necessary, it just shows off Scala's ability

}

}

{{out}}

<pre>

and (iota 5 100 2) produces a list (100 102 104 106 108)

(import (scheme base) ;; library imports in R7RS style

(scheme write)

(lambda (i) (show i (string-length (number->string (left-factorial i)))))

(iota 10 1000 1000))

=={{header|Seed7}}==

include "bigint.s7i";

end for;

writeln;

{{out}}

=={{header|Sidef}}==

Built-in:

Straightforward:

^n -> sum { _! }

Alternatively, using ''Range.reduce()'':

^n -> reduce({ |a,b| a + b! }, 0)

A faster approach:

static cached = 0

static factorial = 1

leftfact

Completing the task:

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)

{{out}}

=={{header|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) ) *)

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) );

{{out}}

<pre>

{{libheader|AttaSwift BigInt}}

func factorial<T: BinaryInteger>(_ n: T) -> T {

for i in stride(from: BigInt(2000), through: 10_000, by: 1000) {

print("!\(i) = \((!i).description.count) digit number")

{{out}}

=={{header|Tcl}}==

set s 0

for {set i [set f 1]} {$i <= $n} {incr i} {

for {set i 1000} {$i <= 10000} {incr i 1000} {

puts "!$i has [string length [leftfact $i]] digits"

{{out}}

<pre>

{{libheader|Wren-fmt}}

{{libheader|Wren-big}}

import "/big" for BigInt

}

System.print("\nLengths of left factorals from 1000 to 10000 by thousands:")

{{out}}

=={{header|zkl}}==

{{trans|D}}

fcn leftFact(n){

[1..n].reduce(fcn(p,n,rf){ p+=rf.value; rf.set(rf.value*n); p },

BN(0),Ref(BN(1)));

lfs:=[20..111,10].apply(leftFact);

println(("\n20 through 110 (inclusive) by tens:\n" +

println("Digits in 1,000 through 10,000 by thousands:\n",

{{out}}

<pre>