nexoncn.com

文档资料共享网 文档搜索专家

文档资料共享网 文档搜索专家

当前位置：首页 >> >> 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 ,

2β

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

赞助商链接

更多相关文档:

To fill a *number* *of* vacancies, *an* employer must hire 3 programmers from ...*odd* *number* parallelogram perimeter point positive integer *prime* *factor* *prime* ...

b are both even integers, which *of* *the* following must be *an* *odd* integer...*number* nonzero *odd* *number* positive *number* *prime* *factor* *prime* *number* quotient ...

(2) *The* *total* *number* *of* shovels and rakes ...*prime* *numbers* are *factors* *of* *the* positive integer...(2) x + 3 is *an* *odd* *number*. ---------...

A. a *prime* *number*B. *an* *odd* integerC. divisible by 8D. a multiple *of* 2nE. a positive integer 正确答案及相关解析 正确答案 C 解析 若n是奇数,...

A.2 B.3 C.4 D.8 E.12 2.if n is any *prime* *number* greater than ...If n is *an* *odd* integer, which *of* *the* following is *the* square *of* *the* ...

So far, 46 *perfect* *numbers* have been found, and they are all Even ...Z. *An* *odd* *perfect* *number* has a least 8 *prime* *factors* [J].Notices Math...

更多相关标签:

文档资料共享网 nexoncn.com
copyright ©right 2010-2020。

文档资料共享网内容来自网络，如有侵犯请联系客服。email:zhit325@126.com