from math import exp, log def divnr(p, q): """ Integer division p/q using Newton-Raphson Division. Assumes p > q > 0. """ sp = p.bit_length()-1 sq = q.bit_length()-1 sr = sp - sq + 1 s = [] t = sr while t > 15: s = [t] + s t = (t>>1) + 1 # Base-case division r = (1 << (t<<1)) / (q >> sq-t) for u in s: r = (r << u-t+1) - (r*r * (q >> sq-u) >> (t<<1)) t = u return (r * (p >> sq)) >> sr def pibs(a, b): if a == b: if a == 0: return (1, 1, 1123) p = a*(a*(32*a-48)+22)-3 q = a*a*a*24893568 t = 21460*a+1123 return (p, -q, p*t) m = (a+b) >> 1 p1, q1, t1 = pibs(a, m) p2, q2, t2 = pibs(m+1, b) return (p1*p2, q1*q2, q2*t1 + p1*t2) def ebs(a, b): if a == b: if a == 0: return (1, 1) return (1, a) m = (a+b) >> 1 p1, q1 = ebs(a, m) p2, q2 = ebs(m+1, b) return (p1*q2+p2, q1*q2) if __name__ == '__main__': n = input() pi_terms = int(n*0.16975227728583067) # 10^n == e^p p = n*2.3025850929940457 # Lambert W_0(p/e) a la Newton k = log(p) - 1 w = k - (k-1)/(k+1) while k > w: k = w w -= (k - p*exp(-k-1))/(k+1) # InverseGamma(e^p) approximation e_terms = int(p / w) pp, pq, pt = pibs(0, pi_terms) ep, eq = ebs(0, e_terms) z = 10**n p = 3528*z*ep*abs(pq) q = eq*abs(pt) pie = divnr(p, q) print pie,