Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Finite connected components of the aliquot graph

Author: Andrew R. Booker
Journal: Math. Comp.
MSC (2010): Primary 11A25
Published electronically: February 20, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Conditional on a strong form of the Goldbach conjecture, we determine all finite connected components of the aliquot graph containing a number less than $ 10^9$, as well as those containing an amicable pair below $ 10^{14}$ or one of the known perfect or sociable cycles below $ 10^{17}$. Along the way we develop a fast algorithm for computing the inverse image of an even number under the sum-of-proper-divisors function.

References [Enhancements On Off] (What's this?)

  • [1] D. J. Bernstein, How to find small factors of integers, 2002,
  • [2] A. R. Booker, Web page with extended data,
  • [3] S. Chernykh, Amicable pairs list,
  • [4] J.-P. Delahaye, Nombres amiables et suites aliquotes, Pour la Science (2002), no. 292, 98-103.
  • [5] P. Erdős, A. Granville, C. Pomerance, and C. Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 165-204. MR 1084181,
  • [6] Jan Feitsma, Pseudoprimes,
  • [7] Jean-Luc Garambois, Les suites aliquotes,
  • [8] Wen Chao Lu, Exceptional set of Goldbach number, J. Number Theory 130 (2010), no. 10, 2359-2392. MR 2660899,
  • [9] David Moews, A list of aliquot cycles of length greater than $ 2$,
  • [10] Tomás Oliveira e Silva, Siegfried Herzog, and Silvio Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $ 4\cdot10^{18}$, Math. Comp. 83 (2014), no. 288, 2033-2060. MR 3194140,
  • [11] Paul Pollack and Carl Pomerance, Some problems of Erdős on the sum-of-divisors function, Trans. Amer. Math. Soc. Ser. B 3 (2016), 1-26. MR 3481968,
  • [12] C. Pomerance, The first function and its iterates, Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham (S. Butler, J. Cooper, and G. Hurlbert, eds.), Cambridge University Press, 2017,
  • [13] J. Sesiano, Two problems of number theory in Islamic times, Arch. Hist. Exact Sci. 41 (1991), no. 3, 235-238. MR 1107382,
  • [14] The PARI Group, Bordeaux, PARI/GP version 2.8.0, 2016, available from

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11A25

Retrieve articles in all journals with MSC (2010): 11A25

Additional Information

Andrew R. Booker
Affiliation: School of Mathematics, University of Bristol, University Walk, Bristol, BS8 1TW, United Kingdom

Received by editor(s): October 24, 2016
Received by editor(s) in revised form: February 15, 2017, May 3, 2017, and May 27, 2017
Published electronically: February 20, 2018
Additional Notes: The author was partially supported by EPSRC Grant EP/K034383/1.
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society