Aliquot sum

In number theory, the aliquot sum s(n) of a positive integer n is the sum of all proper divisors of n, that is, all divisors of n other than n itself. It can be used to characterize the prime numbers, perfect numbers, deficient numbers, abundant numbers, and untouchable numbers, and to define the aliquot sequence of a number.

Examples

For example, the proper divisors of 15 (that is, the positive divisors of 15 that are not equal to 15) are 1, 3 and 5, so the aliquot sum of 15 is 9 i.e. (1 + 3 + 5).

The values of s(n) for n = 1, 2, 3, ... are:

0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13, 28, 1, 42, 1, 31, 15, 20, 13, 55, 1, 22, 17, 50, 1, 54, 1, 40, 33, 26, 1, 76, 8, 43, ... (sequence A001065 in the OEIS)

Characterization of classes of numbers

Pollack & Pomerance (2016) write that the aliquot sum function was one of Paul Erdős's "favorite subjects of investigation". It can be used to characterize several notable classes of numbers:

  • 1 is the only number whose aliquot sum is 0. A number is prime if and only if its aliquot sum is 1.[1]
  • The aliquot sums of perfect, deficient, and abundant numbers are equal to, less than, and greater than the number itself respectively.[1] The quasiperfect numbers (if such numbers exist) are the numbers n whose aliquot sums equal n + 1. The almost perfect numbers (which include the powers of 2, being the only known such numbers so far) are the numbers n whose aliquot sums equal n  1.
  • The untouchable numbers are the numbers that are not the aliquot sum of any other number. Their study goes back at least to Abu Mansur al-Baghdadi (circa 1000 AD), who observed that both 2 and 5 are untouchable.[1][2] Erdős proved that their number is infinite.[3] The conjecture that 5 is the only odd untouchable number remains unproven, but would follow from a form of Goldbach's conjecture together with the observation that, for a semiprime number pq, the aliquot sum is p + q + 1.[1]

Iteration

Iterating the aliquot sum function produces the aliquot sequence n, s(n), s(s(n)), ... of a nonnegative integer n (in this sequence, we define s(0) = 0). It remains unknown whether these sequences always converge (the limit of the sequence must be 0 or a perfect number), or whether they can diverge (i.e. the limit of the sequence does not exist).[1]

gollark: Is that a vector of vectors or what?
gollark: For those you want it to be very slow and best done on general purpose CPUs, to stop bruteforcing.
gollark: They don't entirely succeed in having these properties, SHA-*1* is semibroken now, but SHA-2 fixes the relevant mistakes in that apparently.
gollark: And fancy chemical whatever.
gollark: No, the output is a totally different value.

See also

  • Divisor Function : The sum of the (xth powers of the) positive divisors of a number

References

  1. Pollack, Paul; Pomerance, Carl (2016), "Some problems of Erdős on the sum-of-divisors function", Transactions of the American Mathematical Society, Series B, 3: 1–26, doi:10.1090/btran/10, MR 3481968
  2. Sesiano, J. (1991), "Two problems of number theory in Islamic times", Archive for History of Exact Sciences, 41 (3): 235–238, doi:10.1007/BF00348408, JSTOR 41133889, MR 1107382
  3. Erdős, P. (1973), "Über die Zahlen der Form und " (PDF), Elemente der Mathematik, 28: 83–86, MR 0337733
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.