Finding and Excluding b-ary Machin-Type Individual Digit Formulae

Borwein, Jonathan M. ; Borwein, David ; Galway, William F.

Canadian journal of mathematics, Tome 56 (2004) no. 5, pp. 897-925

Résumé

Constants with formulae of the form treated by D. Bailey, P. Borwein, and S. Plouffe ( $b$ formulae to a given base $b$ ) have interesting computational properties, such as allowing single digits in their base $b$ expansion to be independently computed, and there are hints that they should be normal numbers, i.e., that their base $b$ digits are randomly distributed. We study a formally limited subset of BBP formulae, which we call Machin-type BBP formulae, for which it is relatively easy to determine whether or not a given constant $K$ has a Machin-type BBP formula. In particular, given $b\,\in \,\mathbb{N},\,b\,>\,2,\,b$ not a proper power, a $b$ -ary Machin-type BBP arctangent formula for $K$ is a formula of the form $k\,=\,{{\Sigma }_{m}}\,{{a}_{m}}\,\arctan \,(-{{b}^{-m}}),\,{{a}_{m}}\,\in \,\mathbb{Q}$ , while when $b\,=\,2$ , we also allow terms of the form ${{a}_{m}}\,\arctan \,(1/1\,-\,{{2}^{m}}))$ . Of particular interest, we show that $\pi$ has no Machin-type BBP arctangent formula when $b\,\ne \,2$ . To the best of our knowledge, when there is no Machin-type BBP formula for a constant then no BBP formula of any form is known for that constant.

Détail

DOI : 10.4153/CJM-2004-041-2

Mots-clés : 11Y99, 11A51, 11Y50, 11K36, 33B1, BBP formulae, Machin-type formulae, arctangents, logarithms, normality, Mersenne primes, Bang's theorem, Zsigmondy's theorem, primitive prime factors, p-adic analysis

Bibliographie

[Bai00] Bailey, David H., A compendium of BBP-type formulas for mathematical constants. Manuscript available at http://www.nersc.gov/∼dhbailey/dhbpapers, March 2004. Google Scholar

[BB98] Borwein, Jonathan M. and Borwein, Peter B., Pi and the AGM, a study in analytic number theory and computational complexity. John Wiley & Sons, New York, 1998. Google Scholar

[BB03] Borwein, Jonathan M. and Bailey, David H., Mathematics by Experiment: Plausible Reasoning in the 21st Century. A K Peters, Nattick, MA, 2003. Google Scholar

[BBP97] Bailey, David, Borwein, Peter, and Plouffe, Simon, On the rapid computation of various polylogarithmic constants. Math. Comp. 66(1997), 903–913. Google Scholar

[BC01] Bailey, David H. and Crandall, Richard E., On the random character of fundamental constant expansions. Experiment. Math. 10(2001), 175–190. Google Scholar

[BHV01] Bilu, Yu., Hanrot, G., and Voutier, P. M., Existence of primitive divisors of Lucas and Lehmer numbers.With an appendix by M. Mignotte. J. Reine Angew. Math. 539(2001), 75–122. Google Scholar

[BLS88] John Brillhart, Lehmer, D. H., Selfridge, J. L., Tuckerman, Bryant, and Wagstaff, S. S. Jr., Factorizations of bn ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers. second ed., American Mathematical Society, Providence, RI, 1988, (Third ed. available at http://www.ams.org/online_bks/conm22). Google Scholar

[Bre93] Brent, Richard P., On computing factors of cyclotomic polynomials. Math. Comp. 61(1993), 131–149. Google Scholar

[Bro98] Broadhurst, D. J., Polylogarithmic ladders, hypergeometric series and the ten millionth digits of ζ(3) and ζ(5). Available at http://xxx.lanl.gov/abs/math/9803067, March 1998. Google Scholar

[Cha] Chamberland, Marc, Binary BBP-forumulas for logarithms, cyclotomic polynomials and Aurifeuillian identities. Draft of circa December, 2001, to appear. Google Scholar

[Coh93] Cohen, Henri, A course in computational algebraic number theory. Graduate Texts in Mathematics, 138, Springer-Verlag, Berlin, 1993. Google Scholar

[FBA99] Ferguson, Helaman R. P., Bailey, David H., and Arno, Steve, Analysis of PSLQ, an integer relation finding algorithm. Math. Comp. 68(1999), 351–369. Google Scholar

[HW79] Hardy, G. H. and Wright, E. M., An introduction to the theory of numbers. Fifth ed., Oxford University Press, Oxford, 1979. Google Scholar

[Knu98] Knuth, Donald E., The art of computer programming. vol. 2: Seminumerical algorithms, third ed., Addison-Wesley, Reading, Mass., 1998. Google Scholar

[Kob84] Koblitz, Neal, p-adic numbers, p-adic analysis, and zeta-functions. Second ed., Graduate Texts in Mathematics, 58, Springer-Verlag, New York, 1984. Google Scholar

[NZM91] Niven, Ivan, Zuckerman, Herbert S., and Montgomery, Hugh L., An introduction to the theory of numbers. Fifth ed., John Wiley & Sons, New York, 1991. Google Scholar

[Per00] Percival, Colin, The quadrillionth bit of pi is ‘0’. See http://www.cecm.sfu.ca/projects/pihex/announce1q.html, September 2000. Google Scholar

[Rib91] Ribenboim, Paulo, The little book of big primes. Springer-Verlag, New York, 1991. Google Scholar

[Rib94] Ribenboim, Paulo, Catalan's conjecture: Are 8 and 9 the only consecutive powers? Academic Press, Boston, MA, 1994. Google Scholar

[Rie94] Riesel, Hans, Prime numbers and computer methods for factorization. Second ed., Birkhäuser, Boston, MA, 1994. Google Scholar

[Roi97] Roitman, Moshe, On Zsigmondy primes. Proc. Amer. Math. Soc. 125(1997), 1913–1919. Google Scholar

[Sch74] Schinzel, A., Primitive divisors of the expression An – Bn in algebraic number fields. J. Reine Angew. Math. 268/269(1974), 27–33. Google Scholar

[Wil98] Williams, Hugh C., Édouard Lucas and primality testing, Canadian Mathematical Society Series of Monographs and Advanced Texts, 22, John Wiley & Sons., New York, 1998. Google Scholar