# More on the total number of prime factors of an odd perfect number

MATHEMATICS OF COMPUTATION Volume 74, Number 250, Pages 1003–1008 S 0025-5718(04)01683-7 Article electronically published on June 29, 2004

MORE ON THE TOTAL NUMBER OF PRIME FACTORS OF AN ODD PERFECT NUMBER
KEVIN G. HARE Abstract. Let σ(n) denote the sum of the positive divisors of n. We say that n is perfect if σ(n) = 2n. Currently there are no known odd perfect numbers. It is known that if an odd perfect number exists, then it must be 2β of the form N = pα k qj j , where p, q1 , . . . , qk are distinct primes and j=1 p ≡ α ≡ 1 (mod 4). De?ne the total number of prime factors of N as ?(N ) := α + 2 k βj . Sayers showed that ?(N ) ≥ 29. This was later extended by j=1 Iannucci and Sorli to show that ?(N ) ≥ 37. This paper extends these results to show that ?(N ) ≥ 47.

1. Introduction Here and throughout, n is any natural number, and N is a hypothetical odd perfect number. Let σ(n) denote the sum of the positive divisors of n. We say that n is perfect if σ(n) = 2n. It is known that if σ(n) = 2n and n is even, then n = 2k?1 (2k ? 1) where 2k ? 1 is a Mersenne prime. Currently there are no known odd perfect numbers. First shown by Euler, it is well known that if an odd perfect number exists, then it must be of the form
k

(1.1)

N = pα
j=1

qj j ,

where p, q1 , . . . , qk are distinct primes and p ≡ α ≡ 1 (mod 4). Based on (1.1), we de?ne the total number of prime factors of an odd perfect number as
k

(1.2)

?(N ) := α + 2
j=1

βj ,

and we de?ne the total number of distinct prime factors of N as (1.3) ω(N ) := 1 + k. A number of bounds have been derived for ?(N ) and ω(N ). Cohen showed that ?(N ) ≥ 23 [2]. Sayers showed that ?(N ) ≥ 29 [11]. This was later extended by Iannucci and Sorli to show that ?(N ) ≥ 37 [7]. This paper extends these results to give
Received by the editor October 24, 2003 and, in revised form, December 2, 2003. 2000 Mathematics Subject Classi?cation. Primary 11A25, 11Y70. Key words and phrases. Perfect numbers, divisor function, prime numbers. This research was supported, in part, by NSERC of Canada.
c 2004 by the author

1003

1004

K. G. HARE

Theorem 1.1. If N is an odd perfect number, then ?(N ) ≥ 47. As a result of the calculations made to prove Theorem 1.1, we get Theorem 1.2. If ω(N ) > 8, then ?(N ) ≥ 49. If ω(N ) > 9, then ?(N ) ≥ 51. 2. Definitions and notation We de?ne the function σ?1 (n) as (2.1) σ?1 (n) :=
d|n

d?1 =

σ(n) . n

A number of simple results concerning σ?1 (n) are summarized below. Lemma 2.1. Let n be any natural number. Then ? σ?1 (n) is a multiplicative function, i.e., if (n, m) = 1, then σ?1 (n · m) = σ?1 (n)σ?1 (m). ? σ?1 (n) > 1 for all n > 1. ? σ?1 (n) = 2 if and only if n is perfect. p ? p+1 ≤ σ?1 (pa ) < σ?1 (pa+1 ) < p?1 for all primes p and integers a > 1. p Lemma 2.2. Let N be an odd perfect number. Then ? ω(N ) ≥ 8 [1, 4]. ? if 3 N , then ω(N ) ≥ 11 [5, 8]. ? if 3 N and 5 N , then ω(N ) ≥ 15 [10]. ? if 3 N , 5 N and 7 N , then ω(N ) ≥ 27 [10]. We adopt and modify the notation of [7]
2β De?nition 2.3. Let N be an odd perfect number of the form N = pα qi i , where N has at most aj of the βi equal to bj . The statement [x : α : b1 (a1 ), . . . , bm (am )] means ? if x = 1, then N cannot be of the form; ? if x ≥ 3 and N is of this form, then P N for all primes 3 ≤ P ≤ x. If aj = ?, then we can have an arbitrary number of the βi being bj . If the α is not explicitly mentioned, then this statement is assumed to hold for all α ≡ 1 (mod 4).

For example, the statement [17 : 5 : 1(2), 2(3)] would say that if
2 2 4 4 N = p5 q1 · · · qk r1 · · · rl ,

is an odd perfect number where p, q1 , . . . , rl are distinct primes, with k ≤ 2 and l ≤ 3, then P n for P = 3, 5, 7, 11, 13, 17. Of course this is vacuously true as this N has at most 6 distinct prime factors, and it is known that ω(N ) ≥ 8 for all odd perfect numbers. The statement [17 : 1(2), 2(3)] instead would say that if 2 2 4 4 N = pα q1 · · · qk r1 · · · rl , is an odd perfect number, then the same conclusion holds, regardless of the value of α. Lemma 2.4. Using the notation of De?nition 2.3, ? [1 : 5(1), 1(?)], ? [1 : 6(1), 1(?)], ? [1 : 3(1), 2(1), 1(?)]. Proof. These are exactly as stated in [7].

PRIME FACTORS OF AN ODD PERFECT NUMBER

1005

3. The algorithm and proof of Theorem 1.1
2β Suppose N = pα qi i , as before. To prove that ?(N ) ≥ 47, we assume that ?(N ) = α + 2βi ≤ 45 and obtain a contradiction for every combination of α and βi . First select every partition

B = {α, 2β1 , . . . , 2β1 , . . . , 2βm , . . . , 2βm }
a1 times am times

of 45 such that (1) α ≡ 1 (mod 4), n (2) ω(N ) ≥ 8. (i.e., 1 + i=1 ai ≥ 8), and (3) the existence of such a partition does not violate any result in Lemma 2.4. The statement [x : B] is to be taken as the same as [x : α : b1 (a1 ), . . . , bm (am )]. It should be noted that we do not need to consider corresponding partitions 37, 39, 41 or 43, because if α + 2ai bi < 45, then this case is proven by appending 45 ? α ? 2ai bi to this partition, which does sum to 45. For example, the partition [1, 2, . . . , 2]
19 times

of 39 is shown to give a contradiction if the partition [1, 2, . . . , 2, 6]
19 times

is shown to give a contradiction. There are 2539 partitions that satisfy condition (1). We have only 1310 of these which satisfy condition (2). Of these, 1268 satisfy condition (3). Using the results of [7], we could have reduced this list even more. Based on Lemma 2.2, ? by proving [3 : B] for all B with 8 ≤ 1 + that ω(N ) ≥ 11, which is a contradiction; ? by proving [5 : B] for all B with 11 ≤ 1 + that ω(N ) ≥ 15, which is a contradiction; ? by proving [7 : B] for all B with 15 ≤ 1 + that ω(N ) ≥ 27, which is a contradiction. ai ≤ 10, we will have shown ai ≤ 14, we will have shown ai ≤ 26, we will have shown

By (1.1) it is then clear that ?(N ) ≥ 47. For example, as a small subset of these 1268 cases, we prove the following. [3 : 1 : 1(4), 6(3)] [7 : 1 : 1(13), 2(1), 7(1)] [3 : 13 : 1(3), 2(1), 3(1), 4(2)] [5 : 1 : 1(9), 2(3), 7(1)] [3 : 13 : 1(5), 3(1), 4(2)] [5 : 1 : 1(10), 2(1), 3(1), 7(1)] [7 : 1 : 1(15), 7(1)] [3 : 5 : 1(5), 2(1), 13(1)] [5 : 1 : 1(6), 2(2), 3(1), 4(1), 5(1)] We prove any given result by contradiction. For example, to prove the statement [3 : 13 : 1(5), 3(1), 4(2)], we assume 3|N . The case 313 ||N yields an immediate contradiction as 3 ≡ 1 (mod 4). Here pa ||N means pa |N and pa+1 N . The next case would be 32 ||N (after which we try 36 and ?nally 38 ). Assuming that 32 ||N implies σ(32 )|N , which implies 13|N (see Table 1). Next we assume that 13|N and consider the cases in order 1313 ||N , 132 ||N , 136 ||N and ?nally 138 ||N . We keep descending in this manner until such time as we derive a contradiction. As in [7], we consider the primes in the order from smallest to largest.

1006

K. G. HARE

Table 1. Beginning of proof of [3 : 13 : 1(5), 3(1), 4(2)] 3^13 => 2^2 547 1093 xs=2 3^2 => 13 13^13 => 2 7^2 29 5229043 22079 7^2 => 3 19 19^2 => 3 127 S=2.005554070 19^6 => 701 70841 29^2 => 13 67 xs=prime 29^8 => 13 67 14437 41203 xs=prime 19^8 => 3^2 127 523 29989 xs=3 7^6 => 29 4733 29^2 => 13 67 67^2 => 3 7^2 31 31^2 => 3 331 xs=prime 31^8 => 3^2 331 81343 3637 xs=3 67^8 => 3^2 7^2 31 30152894311 xs=prime 29^8 => 13 67 14437 41203 xs=prime 7^8 => 3^2 19 37 1063 S=2.052904805 13^2 => 3 61 61^13 => 2 31 52379047267 50689400581 31^2 => 3 331 331^2 => 3 7 5233 xs=3 331^6 => 2180921 604842197 2180921^2 => 1478526139 3217 xs=prime 2180921^8 => 19 653977 12583 3217 9883 c_33 xs=prime ... As in [7], we only partially factor large numbers, unless it becomes necessary to completely factor them. In the output these are denoted as “c n” where n is the number of digits of the unfactored number. There are four particular contradictions that we test for. (1) Excess of a given prime: By assuming pk ||N we derive the contradiction that pk+1 |N . This is denoted in the output by “xs=p” where p is the prime in question. (2) Excess of the number of primes: We have more primes than we are allowed, given the restrictions on ω(N ) for this case. This is denoted in the output by “xs=prime”. Incompletely factored numbers are counted as contributing two primes, even though this may be too low. (Incompletely factored numbers are known not to be perfect powers.) (3) Partition cannot be satis?ed: The factors that must divide N , along with their powers, cannot satisfy the partition. For example, if we ?nd two primes, p and q, that must divide N at least 3 times, (p3 |N and q 3 |N ), but the partition allows only one prime to divide N with a power greater than 2, we would have this contradiction. This is denoted in the output by “exponent bounds exceeded”. This contradiction is extremely rare, and was only used 6 times for the 1268 tests.

PRIME FACTORS OF AN ODD PERFECT NUMBER

1007

(4) Excess of σ?1 : A ?oating point lower bound for σ?1 (N ) using known factors gives σ?1 (N ) > 2. This is denoted in the code by “S=σ?1 (N )”, giving a ?oating point approximation for σ?1 (N ). It should be noted that when we start with a prime p other than 3, and we have already proven a contradiction for all primes between 3 and p, then we may assume that P N for all 3 ≤ P < p. This is taken into account in contradiction (1). This procedure is done on all of the 1268 tests to prove the results. The tests and the code are available at [6]. When an incompletely factored number needed to be factored, the following methods were used: ? A search was done of the online tables of factorizations of σ(pa ) [12]. ? If this failed, ecm was used to ?nd a factor, using the code of T. Granlund, found at [13]. After ecm found a factor, further factorization was not always needed. 4. Comments on Theorem 1.2 This paper proved that ?(N ) ≥ 47. There is only one test that blocked a proof that ?(N ) = 47, but this requires the factorization of a 301-digit number. In particular, in attempting to prove ?(N ) = 47 we need to prove: ? [3 : 1 : 1(4), 2(1), 8(1), 9(1)], which requires a factor of σ(σ(1118 )16 ), a 301digit number. There are four tests that blocked the proof that ?(N ) = 49. They are: ? [3 : 1 : 1(5), 2(1), 8(1), 9(1)] and [3 : 1 : 1(3), 2(2), 8(1), 9(1)], which both require a factor of σ(σ(1118 )16 ), a 301-digit number. ? [3 : 1 : 1(4), 3(1), 8(1), 9(1)], which requires a factor of σ(σ(54718 )16 ), a 789-digit number. ? [3 : 1 : 1(3), 2(2), 6(1), 11(1)], which requires a factor of σ(σ(322112 )22 ), a 927-digit number. It is worth noting that these are the only tests which we could not prove computationally, and for each either ω(N ) = 8 or 9. This proves Theorem 1.2. 5. Conclusions and comments Each time that we descend a level of the algorithm, we must choose a prime to work with. Currently the algorithm will take the smallest available prime. This is not always the best choice. If a better choice could be made, some calculations may become feasible which currently are not. In particular, a number of results of the form [739 : 1(?), 2(?)] (see [3, 9]), could be shown which are currently infeasible, due to time considerations. 6. Acknowledgments I am indebted to both Douglas E. Iannucci and Ronald M. Sorli for introducing me to this problem, and for providing many useful suggestions while writing this paper. They also provided me with factorizations for many of the large numbers that they needed for their proof that ?(N ) ≥ 37. I would also like to acknowledge the unknown referee, who pointed me to [10], and who also made a number of useful suggestions and comments.

1008

K. G. HARE

References
1. E. Z. Chein, An odd perfect number has at least 8 prime factors, Ph.D. thesis, Pennsylvania State University, 1979. 2. Graeme L. Cohen, Generalised quasiperfect numbers Ph.D. thesis, University of New South Wales, 1982. , On the largest component of an odd perfect number, J. Austral. Math. Soc. Ser. A 3. 42 (1987), no. 2, 280–286. MR 87m:11005 4. Peter Hagis, Jr., Outline of a proof that every odd perfect number has at least eight prime factors, Math. Comp. 35 (1980), no. 151, 1027–1032. MR 81k:10004 , Sketch of a proof that an odd perfect number relatively prime to 3 has at least eleven 5. prime factors, Math. Comp. 40 (1983), no. 161, 399–404. MR 85b:11004 6. K. G. Hare, Home page, http://www.math.berkeley.edu/?kghare, 2002. 7. D. E. Iannucci and M. Sorli, On the total number of prime factors of an odd perfect number, Math. Comp. 72 (2003), no. 244, 2077–2084. MR 2004b:11008 8. Masao Kishore, Odd perfect numbers not divisible by 3. II, Math. Comp. 40 (1983), no. 161, 405–411. MR 84d:10009 9. Wayne L. McDaniel, On the divisibility of an odd perfect number by the sixth power of a prime, Math. Comp. 25 (1971), 383–385. MR 45:5074 10. Karl K. Norton, Remarks on the number of factors of an odd perfect number, Acta Arith. 6 (1960/1961), 365–374. MR 26:4950 11. M. Sayers, An improved lower bound for the total number of prime factors of an odd perfect number, Master’s thesis, New South Wales Institute of Technology, 1986. 12. R.M. Sorli, Factorization tables, http://www-staff.maths.uts.edu.au/?rons/fact/fact. htm, 1999. 13. Paul Zimmermann, The ECMNET project, http://www.loria.fr/?zimmerma/records/ ecmnet.html, 2003. Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1 E-mail address: kghare@math.uwaterloo.ca

### More on the total number of prime factors of an odd perfect ....pdf

More on the total number of prime factors of an odd perfect number_专业资料。Abstract. Let σ(n) denote the sum of the positive divisors of n. We...

### 数学考点黄金80题.doc

。 。那所以答案 159 (a1+an)*n/2=79*80......n has odd numbers of different prime factors (2...【解释】 T店 H P total 0.8x+2.2y=2(x+...

### A Proof of the Odd Perfect Number Conjecture.pdf

A Proof of the Odd Perfect Number Conjecture It is sufficient to prove that there is an excess of prime factors in the product of repunits with odd...

### Even perfect polynomials over \$F_2\$ with four prime factors_....pdf

polynomials over \$F_2\$ with four prime factors_...number of minimal primes dividing a perfect ...Rahavandrainy, Odd perfect polynomials over F2 ,...

### On the number of co-prime-free sets. by.pdf

those x=log 3x] odd integers x, with the most distinct prime factors....On the number of gener... 14页 免费 An Investigation of th... 12...

### Aspects of mutually unbiased bases in odd prime power ....pdf

where p is an odd prime, in terms of the ...rst factor on the rhs and suspend mod p ...More on the total numb... 6页 免费 ...

### GMAT数学数论知识点讲解-智课教育.pdf

set of negative ,is the total number of integers in M an odd number?...(2)Four different prime numbers are factors of n2. 正整数N有多少个不同...

### BUILDING PSEUDOPRIMES WITH A LARGE NUMBER OF PRIME FACTORS_....pdf

BUILDING PSEUDOPRIMES WITH A LARGE NUMBER OF PRIME FACTORS_专业资料。We ...pr be the prime factorization of an odd, squarefree number N prime to c...

### gre数学考试关于算术的重点试题(4)-智课教育旗下智课教育.pdf

31.The number of different prime factors of 48 ...is not the sum of three consecutive odd integers...total of \$540,400 and each of the terminals ...

### 关于指数丢番图方程\$x^2+(3a^2-1)^m=(4a^2-1)^n\$.pdf

Lemma 1[12] For any odd positive integer n (5 ≤ n ≤ 30), all ...an integer, and ω(P ) denotes the number of distinct prime factors of ...

### Some non-normal Cayley digraphs of the generalized quaternion....pdf

number of (not necessarily distinct) prime factors of the order of the ...Let p ≥ 5 be an odd prime. Then GL(2, p) acts on the set F2 ,...

### The distribution of spacings between quadratic resi....pdf

composite, in the limit as the number of prime factors of q goes to in...an odd prime, the number of squares modulo p is (p + 1)/2 and for...

### On cycles in the coprime graph of integers 1.pdf

the number of distinct prime factors of n and ...rst l ? 1 odd primes, then obviously C2l ? ...We take an arbitrary 1 ≤ l ≤ c2 n positive...

### GMAT强化数学一_图文.ppt

Negative number Multiple Factor/divisor arithmetic ...of a prime (E) the square of an odd integer...

### 【天道】GRE数学重点试题-答案版.doc

the square of an odd integer 答案:D 30.What ...31.The number of different prime factors of 48 ...The ration of the total farmland acreage in 1910...

### factors and multiples 习题.doc

number of distinct prime factors of 14 and the ...If each of the resulting segments has an integer...16. Set A is the set of all positive odd ...

### THE DISTRIBUTION OF SPACINGS BETWEEN QUADRATIC RESIDUES.pdf

Let q be an odd, square-free number with !(q) prime factors, and I ...The total number of points in L \ sC is by the Lipschitz principle (...

### ...THE DISTRIBUTION OF GENERALIZED FERMAT PRIME NUMBERS.pdf

factors of the generalized Fermat numbers [3], Harvey Dubner and the ...nite product Cn = p odd prime (1 ? (1 an (p) p ) 1 ? p) = ...

### Some questions on the class group of cyclotomic fields.pdf

eld K = Q(ζp ) for p an odd prime number, starting from Stickel...precisely in my preprint entitled On prime factors of class group of ...

### Mis-representation of identities in e-cash schemes and how to....pdf

1. This last step guarantees that N has an odd number of prime factors ...The total opening protocol requires many (more than 50) executions of the ...