Chapter 4: Systems Based on Numbers

Section 4: The Sequence of Primes

Properties [of number theoretic sequences]

(a) The number of divisors of n is given by DivisorSigma[0, n], equal to Length[Divisors[n]]. For large n this number is on average of order Log[n]+2 EulerGamma -1.

(b) (Aliquot sums) The quantity that is plotted is DivisorSigma[1,n]-2n, equal to Apply[Plus,Divisors[n]]-2n. This quantity was considered of great significance in antiquity, particularly by the Pythagoreans. Numbers were known as abundant, deficient or perfect depending on whether the quantity was positive, negative or zero. (See notes on perfect numbers below.) For large n, DivisorSigma[1, n] is known to grow at most like Log[Log[n]] n Exp[EulerGamma], and on average like Pi^2/6 n (see page 1093). As discovered by Srinivasa Ramanujan in 1918 its fluctuations (see below) can be obtained from the formula

Pi^2/6 n Sum[Apply[Plus, Cos[2Pi n Select[ Range[s], GCD[s, #] == 1 &]/s]]/s^2, {s, Infinity}]

(c) Squares are taken to be of positive or negative integers, or zero. The number of ways of expressing an integer n as the sum of two such squares is 4 Apply[Plus, Im[I^Divisors[n]]]. This is nonzero when all prime factors of n of the form 4k+3 appear with even exponents. There is no known simple formula for the number of ways of expressing an integer as a sum of three squares, although part of the condition in the main text for integers to be expressible in this way was established by René Descartes in 1638 and the rest by Adrien Legendre in 1798. Note that the total number of integers less than n which can be expressed as a sum of three squares increases roughly like 5n/6, with fluctuations related to IntegerDigits[n, 4]. It is known that the directions of all vectors {x, y, z} for which x^2+y^2+z^2==n are uniformly distributed in the limit of large n.

The total number of ways that integers less than n can be expressed as a sum of d squares is equal to the number of integer lattice points that lie inside a sphere of radius Sqrt[n] in d-dimensional space. For d=2, this approaches Pi n for large n, with an error of order n^c, where 1/4 <c \[LessTilde] 0.315.

(d) All numbers n can be expressed as the sum of four squares, in exactly 8 Apply[Plus, Select[Divisors[n], (Mod[#, 4]!=0)&]] ways, as established by Carl Jacobi in 1829. Edward Waring stated in 1770 that any number can be expressed as a sum of at most 9 cubes and 19 fourth powers. Seven cubes appear to suffice for all but 17 numbers, the last of which is 455; four cubes may suffice for all but 113936676 numbers, the last of which is 7373170279850. (See also page 1166.)

(e) Goldbach's Conjecture has been verified for all even numbers up to 4×10^14. In 1973 it was proved that any even number can be written as the sum of a prime and a number that has at most two prime factors, not necessarily distinct. The number of ways of writing an integer n as a sum of two primes can be calculated explicitly as Length[Select[n - Table[ Prime[i], {i, PrimePi[n]}], PrimeQ]].

This quantity was conjectured by G. H. Hardy and John Littlewood in 1922 to be proportional to

2n/Log[n]^2 Apply[Times, Map[(#-1)/(#-2)&,Map[First,Rest[FactorInteger[n]]]]]

It was proved in 1937 by Ivan Vinogradov that any large odd integer can be expressed as a sum of three primes.

From Stephen Wolfram: A New Kind of Science [citation]