login
Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)*x) * (1 + g(2)*x^2) *(1 + g(3)*x^3) * ... and use a(n) = - g(n).
27

%I #67 Apr 09 2023 08:59:39

%S 1,1,2,3,6,8,18,27,54,84,186,296,630,1008,2106,3711,7710,12924,27594,

%T 48528,97902,173352,364722,647504,1340622,2382660,4918482,9052392,

%U 18512790,33361776,69273666,127198287,258155910,475568220,981288906,1814542704,3714566310

%N Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)*x) * (1 + g(2)*x^2) *(1 + g(3)*x^3) * ... and use a(n) = - g(n).

%C This is the PPE (power product expansion) of A153881 (with offset 0).

%C When p is prime, a(p) = (2^p-2)/p (A064535).

%C From _Petros Hadjicostas_, Oct 04 2019: (Start)

%C This sequence appears as an example in Gingold and Knopfmacher (1995) starting at p. 1223.

%C In Section 3 of Gingold and Knopfmacher (1995), it is proved that, if f(z) = Product_{n >= 1} (1 + g(n))*z^n = 1/(Product_{n >= 1} (1 - h(n))*z^n), then g(2*n - 1) = h(2*n - 1) and Sum_{d|n} (1/d)*h(n/d)^d = -Sum_{d|n} (1/d)*(-g(n/d))^d. The same results were proved more than ten years later by Alkauskas (2008, 2009). [If we let a(n) = -g(n), then Alkauskas works with f(z) = Product_{n >= 1} (1 - a(n))*z^n; i.e., a(2*n - 1) = -h(2*n - 1) etc.]

%C The PPE of 1/(1 - x - x^2 - x^3 - x^4 - ...) is given in A290261, which is also studied in Gingold and Knopfmacher (1995, p. 1234).

%C (End)

%C The number of terms in the Zassenhaus formula exponent of order n, as computed by the algorithm by Casas, Murua & Nadinic, is equal to a(n) at least for n = 2..24. - _Andrey Zabolotskiy_, Apr 09 2023

%H Alois P. Heinz, <a href="/A220418/b220418.txt">Table of n, a(n) for n = 1..2000</a>

%H Giedrius Alkauskas, <a href="http://arxiv.org/abs/0801.0805">One curious proof of Fermat's little theorem</a>, arXiv:0801.0805 [math.NT], 2008.

%H Giedrius Alkauskas, <a href="https://www.jstor.org/stable/40391097">A curious proof of Fermat's little theorem</a>, Amer. Math. Monthly 116(4) (2009), 362-364.

%H Fernando Casas, Ander Murua and Mladen Nadinic, <a href="https://doi.org/10.1016/j.cpc.2012.06.006">Efficient computation of the Zassenhaus formula</a>, Computer Physics Communications, 183 (2012), 2386-2391; arXiv:<a href="https://arxiv.org/abs/1204.0389">1204.0389</a> [math-ph], 2012.

%H H. Gingold, H. W. Gould, and Michael E. Mays, <a href="https://www.researchgate.net/publication/268023169_Power_product_expansions">Power Product Expansions</a>, Utilitas Mathematica 34 (1988), 143-161.

%H H. Gingold and A. Knopfmacher, <a href="http://dx.doi.org/10.4153/CJM-1995-062-9">Analytic properties of power product expansions</a>, Canad. J. Math. 47 (1995), 1219-1239.

%H W. Lang, <a href="/A157162/a157162.txt">Recurrences for the general problem</a>.

%F g(1) = -1 and for k > 1, g(k) satisfies Sum_{d|k} (1/d)*(-g(k/d))^d = (2^k - 1)/k, where a(k) = -g(k). - _Gevorg Hmayakyan_, Jun 05 2016 [Corrected by _Petros Hadjicostas_, Oct 04 2019. See p. 1224 in Gingold and Knopfmacher (1995).]

%F From _Petros Hadjicostas_, Oct 04 2019: (Start)

%F a(2*n - 1) = A290261(2*n - 1) for n >= 1 because A290261 gives the PPE of 1/(1 - x - x^2 - x^3 - ...) = (1 - x)/(1 - 2*x).

%F Define (A(m,n): n,m >= 1) by A(m=1,n) = -1 for n >= 1, A(m,n) = 0 for m > n >= 1 (upper triangular), and A(m,n) = A(m-1,n) - A(m-1,m-1) * A(m,n-m+1) for n >= m >= 2. Then a(n) = A(n,n). [Theorem 3 in Gingold et al. (1988).]

%F (End)

%p b:= proc(n, i) option remember; `if`(n=0 or i<1, 1,

%p b(n, i-1)+a(i)*b(n-i, min(n-i, i)))

%p end:

%p a:= proc(n) option remember; 2^n-b(n, n-1) end:

%p seq(a(n), n=1..40); # _Alois P. Heinz_, Jun 22 2018

%t b[n_, i_] := b[n, i] = If[n == 0 || i < 1, 1, b[n, i - 1] + a[i]*b[n - i, Min[n - i, i]]];

%t a[n_] := a[n] = 2^n - b[n, n - 1] ;

%t Array[a, 40] (* _Jean-François Alcover_, Jul 09 2018, after _Alois P. Heinz_ *)

%o (PARI) a(m) = {default(seriesprecision, m+1); gk = vector(m); pol = 1 + sum(n=1, m, -x^n); gk[1] = polcoeff( pol, 1); for (k=2, m, pol = taylor(pol/(1+gk[k-1]*x^(k-1)), x); gk[k] = polcoeff(pol, k, x);); for (k=1, m, print1(-gk[k], ", "););}

%Y Cf. A064535, A147541, A153881, A157162, A170908, A170909, A170910, A170911, A170912, A170913, A170914, A170915, A170916, A170917, A220420, A273866, A290261.

%K nonn

%O 1,3

%A _Michel Marcus_, Dec 14 2012

%E Name edited by _Petros Hadjicostas_, Oct 04 2019