OFFSET
0,3
COMMENTS
The partial fraction decomposition (PFD) of any fraction x = A/B (in lowest terms) is PFD(x) = round(x) + Sum_{prime p | B} Sum_{1 <= k <= v_p(B)} c(p,k) / p^k with v_p the p-valuation and integer coefficients |c(p,k)| < p chosen so that the partial sum including only the terms in c(p,j), j >= k, is closest possible to x.
We have a(10^k, k = 0, 1, 2, ...) = (1, 9, 53, 323, 2310, 18094, ...) which is roughly a(10^k) ~ 10^k / k.
LINKS
M. F. Hasler, Table of n, a(n) for n = 0..5000
M. F. Hasler, in reply to H. Baker, Fun with rational integer partial fraction decomposition, math-fun mailing list, June 16, 2023.
Wikipedia, Leibniz formula for π, as of May 7, 2023.
Wikipedia, Partial fraction decomposition: Fractions of integers, as of June 15, 2023.
FORMULA
a(n) ~ c*n/log(n) with c ~ 2.05, thus actually close to a(n) ~ n/log_10(n).
EXAMPLE
For Leibniz's sum L(n) = 1 - 1/3 + 1/5 -+ ... - (-1)^n/(2n-1) and its PFD, we have:
L(0) = 0 = PFD(0): The only term is zero, not counted by definition, so a(0) = 0.
L(1) = 1 = PFD(1): a(1) = 1 term.
L(2) = 1 - 1/3 = PFD(2/3): a(2) = 2 terms.
L(3) = 1 - 1/3 + 1/5 = PFD(13/15): a(2) = 3 terms.
L(4) = 1 - 1/3 + 1/5 - 1/7 = PFD(76/105): a(2) = 3 terms.
L(5) = 1 - 1/3 + 1/5 - 1/7 + 1/9 but PFD(263/315) = 1 - 2/9 + 1/5 - 1/7 with only a(5) = 4 terms. (Recall that vanishing terms in the PDF, as here 0/3, are not counted!)
PROG
(PARI) {A362949(x, PFD=0) = my(L=List(), c, p, e); [p, e]=Vec(factor(denominator(x))); listput(L, c=x\/1); x -= c; for(j = 1, #p, until(! e[j] -= 1, if(c = x*p[j]^e[j] % p[j], if(abs(x -= c/p[j]^e[j] ) > abs(x + p[j]^(1-e[j])), c -= p[j] ; x += p[j]^(1-e[j])); listput(L, c/p[j]^e[j])))); if(PFD, Vec(L), #L-!L[1])} \\ Return only the number of terms by default, but the entire PFD if 2nd arg != 0.
CROSSREFS
KEYWORD
nonn
AUTHOR
M. F. Hasler, Jun 16 2023
STATUS
approved