Author: Philippe Flajolet at Internet Date: 11/25/95 10:28 AM Subject: Backhouse's Constant ------------------------------- Message Contents ------------------------------- ON THE EXISTENCE AND THE COMPUTATION OF BACKHOUSE'S CONSTANT Philippe Flajolet, Algorithms Project, INRIA November 25, 1995 I. THE PROBLEM Let p(n) be the n-th prime, with p(1)=2, and define infinity ----- \ n P(z) = 1 + ) p(n) z . / ----- n = 1 Nigel Backhouse examines the coefficients q(n) in the series Q(z)=1/P(z): infinity ----- 1 \ n Q(z) = ---- = ) q(n) z . P(z) / ----- n = 0 He notices empirically that the q(n) alternate in sign and that the ratio between successive values tends to a constant equal (up to sign) to 1.45607... and called now ``Backhouse's constant''. See the description in Steven Finch's web pages. II. ANALYSIS Here is what goes on. By the Prime Number Theorem, we have p(n)~nlog(n), and at any rate p(n)<(n+1)^2 for all n. Thus, P(z) is an analytic function in |z|<1. Accordingly, Q(z) is meromorphic in |z|<1 and has only finitely many poles in any subdisk |z|<=1-eps of the unit disk. Since P(0)=1, Q(z) is analytic at 0. Thus, by Cauchy's coefficient formula, / 1 | Q(z) q(n) := (------) | -------- dz 2 i pi | (n + 1) / z where the integration contour is a sufficiently small circle around 0. We observe that P(z) has a unique zero at s0=-0.686 inside the disk of radius 0.75. Thus, integrating along |z|=0.75 and taking into account the residue of Q(z) at z=s0 gives us 1 n (-n) q(n) = (---------) a0 + O(.75 ) s0 P'(s0) where a0=1/s0=-1.45607 is Backhouse's constant. This formula is quite good as its error term is of rate 1/0.75=1.33, hence exponentially smaller than the dominant term. It is possible to go farther by fishing for the next poles. In this way one can find better and better asymptotic expansions of the type n n n q(n) = c[0] a[0] + c[1] a[1] + c[2] a[2] + etc (with suitable modifications if multiple poles were to be encountered), where a[i]=1/s[i] and s[i] is the i-th zero of P(z). There doesn't seem to be real poles apart from s0 nor multiple poles, but I have naturally no proof for this observation. Complex conjugate pairs of poles will make the correction terms fluctuating, as usual. Note that for any collection of zeros given by a numerical process, a corresponding computer-assisted proof could be built. It suffices to use the principle of the argument [Henrici, Complex and Computational Analysis] to make sure that all zeros in a certain disk have indeed been captured. Also, all this proves that the coefficients q(n) eventually alternate in sign. This could be extended to all values of n by using constructive bounds in Cauchy's remainder integral and checking exhaustively the few dozen initial values not covered by the bounds. Finally, there is a general theorem of Polya-Carlson to the effect that a nonrational function with integer coefficients and radius of convergence 1 admits the unit circle has a natural boundary. Thus, as anticipated, P(z) and Q(z) both have the unit circle as a singular line. III. A GENERAL REMARK What we just did is an instance of a general process well known in the analysis of coefficients of meromorphic functions. It is related to methods for coefficient asymptotics, like Darboux's method or singularity analysis, that are especially useful in ``analytic combinatorics''. An example that is close and that I like to use in teaching coefficient asymptotics is the following. A composition of an integer n is a sequence of integers >0 that add up to n. The number of compositions of n is 2^(n-1). Now consider compositions whose parts are restricted to be prime numbers 2,3,5,7,11,... How many are there? Answer: about 0.303655263*1.476228783^n. Proof. Work with the series S(z)=1/(1-R(z)) where R(z)=z^2+z^3+z^5+z^7+z^11+... Philosophy: This discussion shows these questions to be infinitely easier than true arithmetical ones since this type of problem is (exponentially) oblivious of the fine structure of intervening analytic functions. For instance, one could define the ``twin-Backhouse'' constant by restricting P to terms corresponding to twin prime pairs!! Even though we don't know a lot, we could still PROVE existence of the asymptotic form and COMPUTE the new constant to 1,000 digits in a matter of minutes. Similarly for the Fermat-Backhouse and the Mersenne-Backhouse constants!!! Advertisement: A tutorial on these questions (``Complex Asymptotics and Generating Functions'', INRIA Tech. Rep. 2026, Sept 1993) is available from and is going to be part of a forthcoming book by P. Flajolet and R. Sedgewick entitled ``Analytic Combinatorics''. IV. NUMERICAL VALUE OF BACKHOUSE'S CONSTANT Here is in connection with Simon Plouffe's dictionary of real numbers http://www.cecm.sfu.ca/projects/ISC.html the value of Backhouse's constant to some 1300 Digits (determined in 4 minutes of CPU time with a Maple V.3 program on a DEC Alpha 3000 station.) 1.4560749485826896713995953511165435576531783748471315402707024\ 374140015062653898955996453194018603091099251436196347135486077\ 516491312123142920351770128317405369527499880254869230705808528\ 451124053000179297856106749197085005775005438769180068803215980\ 620273634173560481682324390971937912897855009041182006889374170\ 524605523103968123415765255124331292772157858632005469569315813\ 246500040902370666667117547152236564044351398169338973930393708\ 455830836636739542046997815299374792625225091766965656321726658\ 531118262706074545210728644758644231717911597527697966195100532\ 506679370361749364973096351160887145901201340918694999972951200\ 319685565787957715446072017436793132019277084608142589327171752\ 140350669471255826551253135545512621599175432491768704927031066\ 824955171959773604447488530521694205264813827872679158267956816\ 962042960183918841576453649251600489240011190224567845202131844\ 607922804066771020946499003937697924293579076067914951599294437\ 906214030884143685764890949235109954378252651983684848569010117\ 463899184591527039774046676767289711551013271321745464437503346\ 595005227041415954600886072536255114520109115277724099455296613\ 699531850998749774202185343255771313121423357927183815991681750\ 625176199614095578995402529309491627747326701699807286418966752\ 89794974645089663963739786981613361814875; V. THE MAPLE PROGRAM It is just Newton's method applied to P(z) with a close enough starting value, increasing the number of terms in the truncation of P(z) as we proceed. The call to b(7) gives 1357 exact digits in 4 minutes of CPU time. Digits:=16; # must be there because of Maple's idiosyncrasy b:=proc(m) # computes more than 10*2^m digits of Backhouse's Constant local ord, x, i, j, P, DP, t; option remember; Ithprime:=proc(n) option remember; ithprime(n); end; Digits:=15; x:=-1/1.45607494858268967; ord:=72; for i from 1 to m do Digits:=2*Digits; ord:=2*ord; P:=1; DP:=0; xj:=x; for j from 1 to ord do t:=Ithprime(j)*xj; P:=P+t; DP:=DP+t*j; xj:=xj*x; od; x:=x-P*x/DP; od; RETURN(-1/x); end; b(6); # gives 678 exact digits in 70 seconds b(7); # gives 1357 exact digits in < 4 minutes ------------------------------- End of Message --------------------------------