I want to write a function that calculate (1 / n!) * (1! + 2! + 3! + ... + n!) with n as the parameter of the function, also the result is truncated to 6 decimals (not rounded). Below is my code:
def going(n):
n1 = n
n2 = n
factorial = 1
back = 1
for i in range(2, n1+1):
factorial *= i
while n2>1:
this = 1
for i in range(2, n2+1):
this*=i
back+=this
n2 = n2-1
this = 1
result = int((1/factorial)*back*1000000)/1000000
return result
When I passed the argument 171 into the function, I got the following traceback:
Traceback (most recent call last):
File "/Users/Desktop/going.py", line 18, in <module>
print(going(171))
File "/Users/Desktop/going.py", line 15, in going
result = int((1/factorial)*back*1000000)/1000000
OverflowError: int too large to convert to float
How can I fix this problem? Thanks a lot for help!
--update-- Sorry that I didn't clarify: I'm doing this problem in Codewars and I don't think I can import any libraries to use. So, I need a solution that can avoid using any libraries.
Original problem from Codewars:
Consider the following numbers (where n! is factorial(n)):
u1 = (1 / 1!) * (1!)
u2 = (1 / 2!) * (1! + 2!)
u3 = (1 / 3!) * (1! + 2! + 3!)
un = (1 / n!) * (1! + 2! + 3! + ... + n!)
Which will win: 1 / n! or (1! + 2! + 3! + ... + n!)?
Are these numbers going to 0 because of 1/n! or to infinity due to the sum of factorials?
Task
Calculate (1 / n!) * (1! + 2! + 3! + ... + n!) for a given n, where n is an integer greater or equal to 1.
To avoid discussions about rounding, return the result truncated to 6 decimal places, for example:
1.0000989217538616 will be truncated to 1.000098 1.2125000000000001 will be truncated to 1.2125
Remark
Keep in mind that factorials grow rather rapidly, and you need to handle large inputs.
@PaSTE's suggestion to use gmpy2 is great, and should work fine.
The library mpmath is built on top of gmpy2 and provides the function ff (falling factorial) that makes the implementation a little more concise:
import mpmath
def going_mp(n):
return sum([1/mpmath.ff(n, k) for k in range(n)])
For example,
In [54]: import mpmath
In [55]: mpmath.mp.dps = 30
In [56]: going_mp(170)
Out[56]: mpf('1.00591736819491744725806951204519')
In [57]: going_mp(171)
Out[57]: mpf('1.00588255770874220729390683925161')
(I left out the truncating of the digits. That's something that you can add as you see fit.)
Another standard technique for handling very large numbers is to work with the logarithms of the numbers instead of the numbers themselves. In this case, you can use math.lgamma to compute k!/n! as exp(lgamma(k+1) - lgamma(n+1)). This will allow you to compute the value using just the standard math library.
import math
def going_l(n):
lognfac = math.lgamma(n + 1)
return sum([math.exp(math.lgamma(k+1) - lognfac) for k in range(1, n+1)])
For example,
In [69]: going_l(170)
Out[69]: 1.0059173681949172
In [70]: going_l(171)
Out[70]: 1.0058825577087422
Finally, if you don't want to use even the standard library, you could avoid the large numbers another way. Rewrite the expression as
1 1 1 1
1 + - + ------- + ------------- + ... + ---
n n*(n-1) n*(n-1)*(n-2) n!
That leads to this implementation:
def going_nolibs(n):
total = 0.0
term = 1.0
for k in range(n, 0, -1):
total += term
term /= k
return total
For example,
In [112]: going_nolibs(170)
Out[112]: 1.0059173681949174
In [113]: going_nolibs(171)
Out[113]: 1.0058825577087422