A362949 - OEIS

%I #23 Jul 25 2023 22:41:49

%S 0,1,2,3,4,4,5,6,7,8,9,9,10,11,12,13,14,13,14,15,14,15,16,15,16,17,17,

%T 18,19,19,20,21,21,21,22,21,22,23,24,23,24,24,25,25,24,25,27,27,27,28,

%U 28,29,30,30,31,32,31,32,32,33,33,34,35,35,36

%N Number of nonzero terms in the partial fraction decomposition of Leibniz's sum Sum_{k=1..n} (-1)^k/(1-2k).

%C 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.

%C We have a(10^k, k = 0, 1, 2, ...) = (1, 9, 53, 323, 2310, 18094, ...) which is roughly a(10^k) ~ 10^k / k.

%H M. F. Hasler, <a href="/A362949/b362949.txt">Table of n, a(n) for n = 0..5000</a>

%H M. F. Hasler, in reply to H. Baker, <a href="https://mailman.xmission.com/hyperkitty/list/math-fun@mailman.xmission.com/message/PEZ34ZSZFFAYLQIAAZLL6DJBVT62MP2U/">Fun with rational integer partial fraction decomposition</a>, math-fun mailing list, June 16, 2023.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80">Leibniz formula for π</a>, as of May 7, 2023.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partial_fraction_decomposition#Fractions_of_integers">Partial fraction decomposition: Fractions of integers</a>, as of June 15, 2023.

%F a(n) ~ c*n/log(n) with c ~ 2.05, thus actually close to a(n) ~ n/log_10(n).

%e For Leibniz's sum L(n) = 1 - 1/3 + 1/5 -+ ... - (-1)^n/(2n-1) and its PFD, we have:

%e L(0) = 0 = PFD(0): The only term is zero, not counted by definition, so a(0) = 0.

%e L(1) = 1 = PFD(1): a(1) = 1 term.

%e L(2) = 1 - 1/3 = PFD(2/3): a(2) = 2 terms.

%e L(3) = 1 - 1/3 + 1/5 = PFD(13/15): a(2) = 3 terms.

%e L(4) = 1 - 1/3 + 1/5 - 1/7 = PFD(76/105): a(2) = 3 terms.

%e 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!)

%o (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.

%K nonn

%O 0,3

%A _M. F. Hasler_, Jun 16 2023