Variant of a theorem of Erdős on the sum-of-proper-divisors function

Pomerance, Carl; Yang, Hee-Sung

doi:10.1090/S0025-5718-2013-02775-5

Variant of a theorem of Erdős on the sum-of-proper-divisors function
HTML articles powered by AMS MathViewer

by Carl Pomerance and Hee-Sung Yang;

Math. Comp. 83 (2014), 1903-1913

DOI: https://doi.org/10.1090/S0025-5718-2013-02775-5

Published electronically: October 29, 2013

PDF | Request permission

Abstract:

In 1973, Erdős proved that a positive proportion of numbers are not of the form $\sigma (n)-n$, the sum of the proper divisors of $n$. We prove the analogous result where $\sigma$ is replaced with the sum-of-unitary-divisors function $\sigma ^*$ (which sums divisors $d$ of $n$ such that $(d, n/d) = 1$), thus solving a problem of te Riele from 1976. We also describe a fast algorithm for enumerating numbers not in the form $\sigma (n)-n$, $\sigma ^*(n)-n$, and $n-\varphi (n)$, where $\varphi$ is Euler’s function.

References

Jack David Alanen, EMPIRICAL STUDY OF ALIQUOT SERIES, ProQuest LLC, Ann Arbor, MI, 1972. Thesis (Ph.D.)–Yale University. MR 2622250
J. Browkin and A. Schinzel, On integers not of the form $n-\phi (n)$, Colloq. Math. 68 (1995), no. 1, 55–58. MR 1311762, DOI 10.4064/cm-68-1-55-58
Yong-Gao Chen and Xue-Gong Sun, On Romanoff’s constant, J. Number Theory 106 (2004), no. 2, 275–284. MR 2059075, DOI 10.1016/j.jnt.2003.11.009
Yong-Gao Chen and Qing-Qing Zhao, Nonaliquot numbers, Publ. Math. Debrecen 78 (2011), no. 2, 439–442. MR 2796778, DOI 10.5486/PMD.2011.4820
A. de Polignac, Six propositions arithmologiques déduites du crible de d’Èratosthéne, Nouv. Ann. Math. 8 (1849), 423–429.
P. Erdős, On the normal number of prime factors of $p-1$ and some related problems concerning Euler’s $\varphi$-function, Quart. J. Math. 6 (1935), 205–213.
P. Erdös, On integers of the form $2^k+p$ and some related problems, Summa Brasil. Math. 2 (1950), 113–123. MR 44558
P. Erdös, Über die Zahlen der Form $\sigma (n)-n$ und $n-\varphi (n)$, Elem. Math. 11 (1973), 83–86.
A. Flammenkamp and F. Luca, Infinite families of noncototients, Colloq. Math. 86 (2000), no. 1, 37–41. MR 1799887, DOI 10.4064/cm-86-1-37-41
Kevin Ford, The distribution of totients, Ramanujan J. 2 (1998), no. 1-2, 67–151. Paul Erdős (1913–1996). MR 1642874, DOI 10.1023/A:1009761909132
Aleksander Grytczuk and Barbara Mędryk, On a result of Flammenkamp-Luca concerning noncototient sequence, Tsukuba J. Math. 29 (2005), no. 2, 533–538. MR 2177025, DOI 10.21099/tkbjm/1496164969
Laurent Habsieger and Xavier-François Roblot, On integers of the form $p+2^k$, Acta Arith. 122 (2006), no. 1, 45–50. MR 2217322, DOI 10.4064/aa122-1-4
Guangshi Lü, On Romanoff’s constant and its generalized problem, Adv. Math. (China) 36 (2007), no. 1, 94–100 (English, with English and Chinese summaries). MR 2344675
D. Moews and P. C. Moews, A search for aliquot cycles and amicable pairs, Acta Arith. 122 (2006), 45–50.
H. L. Montgomery and R. C. Vaughan, The exceptional set in Goldbach’s problem, Acta Arith. 27 (1975), 353–370. MR 374063, DOI 10.4064/aa-27-1-353-370
T. Oliveira e Silva, Goldbach conjecture verification, last updated April 2012, accessed 5 June 2012. http://www.ieeta.pt/~tos/goldbach.html.
J. Pintz, A note on Romanov’s constant, Acta Math. Hungar. 112 (2006), no. 1-2, 1–14. MR 2251126, DOI 10.1007/s10474-006-0060-6
N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 109 (1934), no. 1, 668–678 (German). MR 1512916, DOI 10.1007/BF01449161
E. J. Scourfield, Non-divisibility of some multiplicative functions, Acta Arith. 22 (1972/73), 287–314. MR 316407, DOI 10.4064/aa-22-3-287-314
H. J. J. te Riele, A theoretical and computational study of generalized aliquot sequences, Mathematical Centre Tracts, No. 74, Mathematisch Centrum, Amsterdam, 1976. MR 556033
J. G. van der Corput, On de Polignac’s conjecture, Simon Stevin 27 (1950), 99–105 (Dutch). MR 35298