Multiply Perfect Numbers less than a given N

Achim Flammenkamp, Department of Mathematics, Universität Bielefeld

created 2007–Nov–26, last updated 2008–Mar–25

Let n ∈ ℕ be a known factor, x ∈ ℕ be an unknown number, p ∈ ℙ a fixed prime, such that gcd(n, p) = gcd(x, p) = gcd(x, n) = 1 holds. Furthermore let N = nxp^{k} for a fixed but arbitrary k ∈ ℕ_{0} hence p^{k}||N. Next restrict N to be a so-called multiply perfect number of multiplicity m, named also a m-perfect number. I.e.

σ(N) = σ(nxp^{k}) = σ(n)σ(x)σ(p^{k}) = mnxp^{k} = mN with m ∈ ℕ

where σ(N) denotes the sum of the divisors of N. Because always σ(p^{k}) ≡ 1 (mod p), the prime-power p^{k} must divide σ(n)σ(x) . Define exponents i and j such that

p^{i}||m and p^{j}||σ(n) with i, j ∈ ℕ_{0}

holds – because n is a known factor, j is also easily to calculate. Then p^{k+i}|p^{j}σ(x) or p^{k+i−j}|σ(x) . If we set h = k + i − j, then trivialy holds

p^{h} ≤ σ(x) = σ(\frac{N}{np^{k}} ) = \frac{σ(\frac{N}{n})}{σ(p^{k})}

because p^{k}||\frac{N}{n} – or

p^{h}p^{k} < p^{h} \frac{p^{k+1} − 1}{p − 1} ≤ σ(\frac{N}{n} )

which is equivalent to

k + i − j + k < \frac{ln σ(\frac{N}{n})}{ln p}

and using

∀ x ∈ ℕ ∃ x_{0} ∈ ℕ ∃ C ∈ ℝ_{+} :  x > x_{0} ⇒ σ(x) < Cx ln ln x (1)

we get finally

k < \frac{ln \frac{CN}{n}}{2 ln p} + \frac{ln ln ln \frac{N}{n}}{2 ln p} − \frac{i}{2} + \frac{j}{2}  with \frac{N}{n} > x_{0}  (2)

Compared to N , the multiplicity m = \frac{σ(N)}{N} grows at most of order O(ln ln N). The possible values of i, which depend on m and p, are really small, at most i_{max} if m ≤ 10, the largest multiplicity we are concerned with:

m 1 2 3 4 5 6 7 8 9 10 i_{max}
p = 2  1  2  1  3  1 3
p = 3  1  1  2  2
p = 5  1  1 1
p = 7  1  1

Table I. No entry for i in this table indicates a value of 0 for i(p, m).

Let us abbreviate \frac{ln ln ln \frac{N}{n}}{2 ln p} − \frac{i}{2} by δ_{p,m}(N). Then holds:

p = 2 and N < 10^{459} ⇒ δ_{2,m}(N) < 1.4
p = 3 and N < 10^{596} ⇒ δ_{3,m}(N) < 0.9
p = 5 and N < 10^{430} ⇒ δ_{5,m}(N) < 0.6
p = 7 and N < 10^{476} ⇒ δ_{7,m}(N) < 0.5
p ≥ 11 and N < 10^{393} ⇒ δ_{p,m}(N) < 0.4

Table II.

and we have goten an upper limit for the to be searched prime-exponent k of p for N by \frac{ln \frac{CN}{n}}{2 ln p} + δ_{p,m}(N) + \frac{j}{2} with j indicating the at least primeexponent from the known factor σ(n) of σ(N). Remark: if the known factor n equals 1, then j must be 0 and we get from (2) the simpler upper bound

k < \frac{ln CN}{2 ln p} + \frac{ln ln ln N}{2 ln p} − \frac{i}{2} with \frac{N}{p^{k}} > x_{0}

In the special case p = 2 we replace σ(2^{k}) by 2^{k+1}(1 − \frac{1}{2^{k+1}} ) to get a slightly sharper bound on k for multiply perfect numbers:

k < \frac{ln σ(N)}{2 ln 2} − \frac{i + 1}{2} + \frac{1}{2^{k+2} ln 2 − 0.77259}

In (1) there are some effective upper bounds C on σ(x) known:

x > 6 ⇒ σ(x) < 2.6x ln ln x
x > 6 , x ∉ {8, 10, 12, 18, 24} ⇒ σ(x) < 2x ln ln x
x > 5 , 2 |̸ x ⇒ σ(x) < 1.835x ln ln x
x > 7 , 2 |̸ x , 3 |̸ x ⇒ σ(x) < 1.25x ln ln x
x > 2520 ⇒ σ(x) < 1.8x ln ln x
x > 4095 , 2 |̸ x ⇒ σ(x) < x ln ln x  (3)

and assuming the correctness of the Riemann Hypothesis

x > 5040 ⇒ σ(x) < e^{γ}x ln ln x

Because \overline{lim_{x→∞}} \frac{σ(x)}{x ln ln x} = e^{γ} = 1.7810724 … the last inequality is by its magnitude best possible if there are no further conditions on x.

We have gcd(x, n) = 1 . Let n = ∏_{p∈L} p^{k_{p}} with L the set of the already known primes of N.

mN = mx ∏_{p∈L} p^{k_{p}} = σ(x)σ(∏_{p∈L} p^{k_{p}}) = σ(N)

Because of the unique prime-factorisation in ℕ this equation holds also for each prime number p ∈ L separately, and therefore for each arbitrary subset L^{⋆} of L, too. If we use for each P ⊂ ℙ the notation of an index {p ∈ P } at an integer parameter which means that only this subproduct of its primefactorization’s value remains whose primes are in P, then it follows

m_{{p∈L^{⋆}}} ∏_{p∈L^{⋆}} p^{k_{p}} = σ(x)_{{p∈L^{⋆}}} ∏_{p∈L^{⋆}} p^{j_{p}}

or equivalently

∏_{p∈L^{⋆}} p^{k_{p}−j_{p}} ≤ m_{\{p∈L^{⋆}\}} ∏_{p∈L^{⋆}} p^{k_{p}−j_{p}} = σ(x)_{\{p∈L^{⋆}\}} = \frac{σ(x)_{\{p∈L^{⋆}\}}}{x} · \frac{N}{n}  (4)

Notice that this inequality holds especially for the subset of all primes with k_{p} − j_{p} > 0 which maximizes its left side. To estimate the right side of (4) by an upper limit well, but also compute it quickly, we use

\frac{σ(x)_{\{p∈L^{⋆}\}}}{x} ≤ \frac{σ(x)}{x} < ∏_{p∈ℙ\L} \frac{p}{p − 1} = ∏_{p∈ℙ\L}(1+\frac{1}{p − 1}) with ∏_{p∈ℙ\L}p ≤ x (5)

Let us consider two sets of numbers who are good upper bounds for \frac{σ(x)}{x}. Historically z ∈ ℕ is called super-abundant if and only if \frac{σ(z)}{z} > \frac{σ(y)}{y} for all y < z. Furthermore z ∈ ℕ is called colossally abundant if and only if there is a positive real number ε such that \frac{σ(z)}{z^{1+ε}} ≥ \frac{σ(y)}{y^{1+ε}} for all y < z. The colossally abundant numbers are a subset of the super-abundant numbers. If the primefactors of any such number is restricted to be in ℙ \ L we use the additive ”L-restricted”. Because \frac{σ(x)}{x} grows so slowly with x, it is sufficient for us to use L-restricted colossally abundant numbers c_{i} which are much easier to be calculated than the super-abundant numbers. Thus we have

∀ L ⊂ ℙ ∀ x ∈ ℕ_{\{p∈ℙ\L\}} ∃ c_{i} ∈ ℕ : \frac{σ(x)}{x} ≤ \frac{σ(c_{i})}{c_{i}} with c_{i} ≥ x

By choosing minimal possible c_{i}, a unique sequence (c_{i})_{i∈ℕ_{0}} for any given set L ⊂ ℙ of strict increasingly ordered L-restricted colossally abundant numbers can be constructed successively as follows: Let

c_{0} = 1 , ∀ i ∈ ℕ : c_{i} = q_{i}c_{i−1} with q_{i} ∈ ℙ \ L such that c_{i} = ∏_{p∈ℙ\L}p^{β_{p,i}}

canonically. Then holds

∃! q_{i} ∈ ℙ \ L : \frac{ln \frac{q_{i}−q_{i}^{−β_{q,i}}}{q_{i}−1}}{ln q_{i}} = max_{p∈ℙ\L} \frac{ln \frac{p−p^{−β_{p,i}}}{p−1}}{ln p}

Because we can now calculate sharp upper bounds on σ(x) easily, we get the following conditions on the multiplicity from the size of a m-perfect number x with certain sets ℙ \ L:

L = {}  L = {2} x=T^{2} ∏_{j=1}^{i} P_{j} L = {2, 3} mx = σ(x)
x <  1.45 ·10^{11}  1.03 ·10^{66} ⇒ m ≤ 2
x < 5.04 ·10^{3} 2.08 ·10^{37} 5.24 ·10^{63} 2.82 ·10^{368} ⇒ m ≤ 3
x < 2.16 ·10^{7} 1.08 ·10^{121} 1.04 ·10^{206} 1.78 ·10^{1988} ⇒ m ≤ 4
x < 9.31 ·10^{12} 6.18 ·10^{371} 4.29 ·10^{685}  ⇒ m ≤ 5
x < 3.71 ·10^{22} 9.01 ·10^{1138}  ⇒ m ≤ 6
x < 4.74 ·10^{41}  ⇒ m ≤ 7
x < 1.28 ·10^{71}  ⇒ m ≤ 8
x < 1.11 ·10^{124}  ⇒ m ≤ 9
x < 4.91 ·10^{214}  ⇒ m ≤ 10
x < 2.53 ·10^{375}  ⇒ m ≤ 11
x < 1.20 ·10^{655}  ⇒ m ≤ 12

Table III. upperlimits on m. The i in colum head is i(2, m) from table I.

Because each odd m-perfect number must be a square if m is odd, every odd tri-perfect must be even > 5.24 · 10^{63}. If we furthermore use the fact that an odd triperfect number must have at least 35 different prime factors, we get a lower limit of 4 · 10^{120}, Finally using that its 2nd largest primefactor is at least 1009 and its largest at least 100109 enable us to rise this limit to

2 · 10^{129}. See also the URL http://hdl.handle.net/2100/275 for a proof

that an odd triperfect number must be > 10^{132}. Any odd multiply perfect number of multiplicity ≥ 5 must be > 10^{206}. Using total different ideas it is known that an odd 2-perfect number must be > 10^{300} – see also the URL

http://www.oddperfect.org/ for current progress.

Now we are able to formulate an algorithm to generate multiply perfect numbers less than a given bound. Its basic idea is: for a wanted multi-perfect number select always the largest already appeared prime which has an unsettled exponent. Then iterate over the range of possible exponent values of this prime and for each so chosen prime-power value to recurse this idea:

MPN generating algorithm up to a given limit

// prime_power is a structur containing 3 integers and 1 real number:
// a prime base p,
// a to-settle exponent >= -1 (0 means unsettled, -1 means settled
//            to 0, else any value indicates settled to this value)
// a to-use exponent (arbitrary integer, initialized to 0)
// ln(p) to check current_number size for bounds quickly
global  current_number;  // forward and backward linked list of
                         // by size of base sorted prime_powers
prime  small_prime_bound;  // fixed to 2 or 3
main
{  define_bound_and_parity_of_wanted_mpns();
   initialize_current_number();
   iterate_small_primes(parity_of_wanted_mpn = 1 ? 3 : 2 );
}
define_bound_and_parity_of_wanted_mpns()
{  // read parity of wanted MPNs
   // read the maximal size of the wanted MPNs
   // compute ln (1 + 1/(p-1)) for all needed prime numbers
}
initialize_current_number()
{  // set empty prime factorisation for current_number and join a few
   // fixed small primes, whose prime-powers have set both exponents 0
   // set the current size to ln(1)
}
iterate_small_primes(prime p)
{  max_j = upper_exponent_bound_of_current_number(p);
   for (j=at_least_exponent(p);j <= max_j; j+=1)

{  update_current_number_by(p,j);
join_prime_factorisation_to_current_number(p,j);
if (multiplicity_not_too_large())
{  if (next_larger_prime(p) < small_prime_bound)
      iterate_small_primes(next_larger_prime(p));
   else
      recurse_large_primes();
}
dejoin_prime_factorisation_to_current_number(p,j);
update_current_number_by(p,-j);
}
}
recurse_large_primes()
{  if (remaining_to_be_satisfied_size_too_large())
return;
p = prime_of_largest_unsettled_exponent_of_current_number();
if (p >= small_prime_bound)
{  max_j = upper_exponent_bound_of_current_number(p);
for (j=at_least_exponent(p); j <= max_j ; j+=1)
{  update_of_current_number_by(p,j);
   join_prime_factorisation_to_current_number(p,j);
   if (multiplicity_not_too_large())
   {  if (j = 0)
         set to-settle exponent of current_number to -1;
      recurse_large_primes();
   }
   dejoin_prime_factorisation_to_current_number(p,j);
   update_current_number_by(p,-j);
}
return;
}
// now all known exponents of current_number are settled
if (all_to-use_exponents_in_current_number_are_non_negative())
print_current_number_as_mpn();
return;
}
upper_exponent_bound_of_current_number(prime p)
{  // trivial bound  ln(x)/ln(p)
// use (2) with (3)
}
at_least_exponent(prime p)
{  // the already known (at least) exponent value decreased by the
// possible multiplicity exponent for this p, (see Table I)
}
join_prime_factorisation_to_current_number(prime p, unsigned j)
{  // factorize sigma(p^j)  and  add it to the to-use exponents

   // the linked list of current_number may increase
}
de_join_prime_factorisation_to_current_number(prime p, unsigned j)
{  // factorize sigma(p^j)  and  remove it from the to-use exponents
   // the linked list of current_number may decrease
}
update_current_number_by(prime p, integer j)
{  // if j is non-negative set the to-settle exponent to j
   // else set the to-settle exponent to 0
   // decrease the to-use exponent by j
   // add j*ln(p) to its current size
}
multiplicity_not_too_large()
{  // calculate which at-least-multiplicity is forced
   // by already known exponents (see Table III)
}
remaining_to_be_satisfied_size_too_large()
{  // sum up ln(p^i) for these known primes p whose to-use exponents i
   // are < 0. Use (4) with (5) and the list of precomputed values
   // ln(1+1/(p-1)) to check whether a MPN is still possible
}
prime_of_largest_unsettled_exponent_of_current_number()
{  // choose from the known-to-occur primes the largest prime
   // with unsettled exponent or 1 if no such prime exists
}

Remark: the prime factorizations of σ(p^{j}) in join prime factorisation ... and dejoin prime factorisation ... were stored in a database and need therefore computed only onetime for each needed p^{j}. These two checks multi

plicity not too large and remaining to be satisfied size too large

can and should be done as early as possible. Therefore they were done

inside join prime factorisation to current number for each new added

prime-power immediately, such in case they indicated a contradiciton the current join of prime-powers could be aborted immediately and the following dejoin prime ...-routine needed to dejoin less prime-powers. Except for those primes < 10^{9} the primability-proving of each prime number p was done by Lucas’s, later by Lehmer and still later by Brillhart & Selfridge improved, classical N-1-test. This used, like the factorization algorithm in join prime factorisation ..., the elliptic-curve factoringroutine zecm from freelip-1.1 for complete factorisation of p − 1. Meanwhile (since Christmas 2007) also the classical N+1-test, which is based on Lucas-sequences, is implemented which should be proper because of the already stored factorisations of σ(p) = p + 1.

Which multiply perfect numbers less than a given bound N can not be generated by this algorithm? Those numbers can’t be divisible by the seeding prime 2 (or 3 in the odd parity case), and must be an integer multiple of a smaller multi-perfect number such that this multiple contains no prime already in the prime-factorisation of the smaller number. Therefore consider two multiply perfect numbers r and rs with gcd(r, s) = 1:

∃ m, n, k ∈ ℕ :  m = \frac{σ(r)}{r} , \frac{n}{k} = \frac{σ(s)}{s}  and k|m , k < n

Because k|s and gcd(r, s) = 1 also gcd(r, k) = 1. I.e. r is a m-perfect number and either k = 1 or m |̸ r. If k = 1 then also s must be a multiply perfect number and because one of r and s must be odd, the only known solution less to the search limit is the trivial solution s = 1 or r = 1. The case k > 1 means: there is a prime-factor of m which divides s, but not r. We will indeed find several multi-perfect numbers r, namely of multiplicity 3 and 5, which are not divisible by 3 resp. 5. But in each single case, the algorithm has checked the total possible range for this prime-exponent as we recognize by the fact that it has discovered also a 3- resp. 5-multiple (which results in a further 4- resp. 6-perfect number) for each of this 3- resp. 5-perfect number. Remark: no 7-perfect number not divisible by 7 nor a 6-perfect or 9-perfect number not divisible by 3 is discovered by our algorithm for any checked search limit.

To restrict the possible prime-exponents effectively in upper exponent bo und of current number we use (2) and for the upper bound in (1) we take a variation of (3), namely σ(x) < x ln ln N with N the search limit, to get rid of

the lower bound x_{0}. Further in remaining to be satisfied size too large

we use (4) with the subset L^{⋆} of L – only these p ∈ L with k_{p} − j_{p} > 0 – together with (5). With a well-tuned version of the above algorithm implemented in C, and using mper-4.1 and freelip-1.1 packages, Achim Flammenkamp succeeded in December 2007 to generate all 645 multiply perfect numbers < e^{310} needing 78 hours cpu-time on a 2 GHz AMD Opteron 146 processor. The database for this run accumulated more than 746000 sigmafactorizations and needed 54 MB RAM. As a side-result he showed that the smallest 8-perfect number is – as conjectured – 8.267 . . . · 10^{132}, which was 1990 discovered by Stephen Gretton.

A historical retrospect of the discovery of smallest m-perfect numbers: It is known since the middle-ages, that m < 4 if N < 30240, the smallest 4-perfect number, and m < 3 if N < 120. Who or when it was shown that N = 14182439040 ∼ 1.4 · 10^{10}, the first discovered 5-perfect number, is also the smallest 5-perfect number discovered by Descartes 1638, this is unknown. Richard Schroeppel has claimed that he proved by an exhaustive computer search in the 80ties of the 20th century that N ∼ 10^{20.189} is the smallest 6-perfect number (which was found by Robert Carmichael in 1907) and N ∼ 10^{56.150} is the smallest 7-perfect number discovered 1911 by T.E. Mason which rises some upper limits in table III for N considerably to their highest possible value. Precisely, Richard Schroeppel stated to have found all 258 multiply perfect numbers < 10^{70} and shown the nonexistence of any odd multiply perfect number < 10^{90}. Considering Rich’s own maintained outdated database of 2094 MPNs from 1995, there are 7 MPNs discovered 1990 by Gretton and by Schroeppel which are < 10^{70}. Therefore one must assume that his exhaustive search was either buggy or took place earliest 1990. Moreover 3 MPNs found by Schroeppel are commented with ’Exhaustive’ in this out-dated database, one from 1983 which is < e^{107} and two from 1990 (the smaller < e^{130}). Thus one may assume that he mixed up two independent searches with different upper limits and perhaps a first exhaustive search was done by him 1983 with an upper limit of 10^{55} and the second 1990. Anyway this uncertainty which Flammenkamp got aware firstly in November 2007 triggered the start of a small project to settle the issue of smallest existing MPNs. As a result, end of the same month Achim Flammenkamp did the firsttime an exhaustive computer search for multiply perfect numbers with a crude implementation of the above presented MPN generating algorithm and constructed all these 443 numbers which are < e^{231} ∼ 2.1 · 10^{100} in a 9 CPU-hours lasting run. Until end of the same year, he had used a well-tuned version of this algorithm to prove that there exist exactly these 691 MPNs < e^{330} ∼ 2 · 10^{143} which were already known since 1993. Finally, on March the 25th 2008, he had showed that there are 730 MPNs < e^{350} ∼ 10^{152} after a 29 CPU-days lasting computation.