Author 
Topic: [RC] Left factorials (Read 526 times) 

tsh73
Moderator
member is offline
Anatoly (real name)
Gender:
Posts: 1732


[RC] Left factorials
« Thread started on: Jun 30^{th}, 2015, 2:22pm » 

[RC] Left factorials Quote:Left factorials, !n, may refer to (...) This Rosetta Code task will be using this formula for left factorial: !n = \sum_{k=0}^{n1} k!
where !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, 2,000 through 10,000 (inclusive), by thousands. 

I admit C# "faster version" gave me some ideas as LB halted at !1000 of my first version ;)
Code:'[RC] Left factorials
'defined as
'!n = \sum_{k=0}^{n1} k!
'where !0 = 0
for i = 0 to 10
print i, leftFact(i)
next
print
for i = 20 to 110 step 10
print i, leftFact(i)
next
print
for i = 1000 to 10000 step 1000
print i, len(str$(leftFact(i)))
next
function leftFact(n)
if n = 0 then exit function
leftFact = 1
fact=1
for k = 1 to n1
fact = fact*k
leftFact = leftFact + fact
next
end function
Output: Code: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

« Last Edit: Jun 30^{th}, 2015, 2:27pm by tsh73 » 
Logged

damned Dog in the Manger



tsh73
Moderator
member is offline
Anatoly (real name)
Gender:
Posts: 1732


Re: [RC] Left factorials
« Reply #1 on: Jul 2^{nd}, 2015, 05:34am » 

Just want to say. We got really lazy with fast computers and things like long integer support. Last number printed  length of !10000  actually involved computing 35656digit number.
But last part of the task Quote:Display the length (in decimal digits) of the left factorials for: 1,000, 2,000 through 10,000 (inclusive), by thousands. 

could be done faster and without long integers.
Her's how. We asked for a length of a number. Length of a number N could be calculated as int(log10(N))+1 (and log10 could be calculated as log(N)/log(10)) Now, our number is actually sum of factorials of numbers <N, N above 1000 So. last (bigger) things in that sum differs in 1000's. That means that number of digits is defined with that last item, that is, (N1)!. Now, main feature of LOG() function is that LOG(a*b)=LOG(a)+LOG(b) So we can calculate LOG((N1)!) in pretty small numbers.
Here we are, Code:for i = 1000 to 10000 step 1000
print i, lenFact(i1)
next
function lenFact(n)
logFact=0
for i = 1 to n
logFact=logFact+log(i)
next
lenFact = int(logFact/log(10))+1
end function
with same result. Code:1000 2565
2000 5733
3000 9128
4000 12670
5000 16322
6000 20062
7000 23875
8000 27749
9000 31678
10000 35656

« Last Edit: Jul 2^{nd}, 2015, 05:35am by tsh73 » 
Logged

damned Dog in the Manger



