INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A41

ON A VARIATION OF PERFECT NUMBERS

Douglas E. Iannucci University of the Virgin Islands, St. Thomas, VI 00802

                                diannuc@uvi.edu

Received: 3/17/06, Revised: 11/5/06, Accepted: 12/4/06, Published: 12/20/06

Abstract

We define a positive integer n to be k-imperfect if kρ(n) = kn for some integer k ≥ 2. Here, ρ is a multiplicative arithmetic function defined by ρ(p^{a}) = p^{a} − p^{a−1} + p^{a−2} − ⋯ + (−1)^{a} for a prime power p^{a}. We address three questions regarding k-imperfect numbers; in particular we find several necessary conditions for the existence of odd 3-imperfect numbers.

1. Introduction

The arithmetic function σ is called the sum-of-divisors function because σ(n) gives the sum of the positive divisors of a natural number n. Since σ is multiplicative, it may be defined by σ(1) = 1 and

σ(p^{a}) = p^{a} + p^{a−1} + p^{a−2} + ⋯ + 1

for a prime p and integer a ≥ 1.

Analogously, we define a multiplicative arithmetic function ρ by ρ(1) = 1 and

(1)  ρ(p^{a}) = p^{a} − p^{a−1} + p^{a−2} − ⋯ + (−1)^{a}

for a prime p and integer a ≥ 1.

It follows that ρ(n) ≤ n with equality only for n = 1. We say that n is imperfect if 2ρ(n) = n, and we shall say n is k-imperfect if kρ(n) = n for a natural number k. In Table 1 is given all k-imperfect numbers up to 10^{9}.

Typeset by AMS-TEX

Martin [1] introduced the function ρ at the 1999 Western Number Theory Conference, and raised three questions (see Guy [7], p.72):

(1) Are there any k-imperfect numbers with k ≥ 4?

(2) Are there infinitely many k-imperfect numbers?

(3) Are there any odd 3-imperfect numbers?

In this paper we address these questions, paying most attention to the third.

2. Preliminaries

For the remainder of this paper, p, q, and r, with or without subscripts, shall represent odd primes. We shall represent positive integers by h, k, m, n, a, b, α, and β. We shall let γ represent a nonnegative integer. If p ∤ a we let e_{p}(a) denote the exponent to which a belongs, modulo p. We write p^{a}∥n if p^{a} | n and p^{a+1} ∤ n. We write v_{p}(n) = a if p^{a}∥n.

We consider the function H, defined for natural numbers n, by

H(n) = \frac{n}{ρ(n)} .

Therefore n is k-imperfect if H(n) = k. Note that H is multiplicative. Note that

\frac{1}{H(p^{a})} = 1 − \frac{1}{p} + \frac{1}{p^{2}} − ⋯ + \frac{(−1)^{a}}{p^{a}} .

Therefore

(2)  \frac{p^{2}}{p^{2} − p + 1} ≤ H(p^{2a}) < \frac{p + 1}{p} .

If a < b then

(3)  H(p^{2a}) < H(p^{2b}) .

If p < q then (q + 1)/q < p^{2}/(p^{2} − p + 1), and so for any a, b, we have

(4)  H(q^{b}) < H(p^{a}) .

From (1) we have

(5)  ρ(p^{2a}) = \frac{p^{2a+1} + 1}{p + 1} .

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A41 3

We denote the n^{th} cyclotomic polynomial, evaluated at x, by Φ_{n}(x). From (5), and from the identity

x^{n} − 1 = ∏_{d|n} Φ_{d}(x) ,

we have

(6)  ρ(p^{2a}) = ∏_{\begin{matrix}d|2a+1 \\ d>1 \end{matrix}} Φ_{2d}(p) .

From Theorems 94 and 95 in Nagell [16], we have the following Lemma 1. Let h = e_{q}(p). Then q | Φ_{m}(p) if and only if m = hq^{γ}. If γ > 0 then q∥Φ_{hq^{γ}} (p).

Letting h = e_{q}(p), it follows from (6) and Lemma 1 that

(7)  v_{q}(ρ(p^{2a}) = \{ \begin{matrix}v_{q}(Φ_{h}(p)) + v_{q}(2a + 1), & if h > 2, h | 2(2a + 1), h ∤ 2a + 1, \\ v_{q}(2a + 1), & if h = 2, \\ 0, & otherwise. \end{matrix}

Another direct consequence of Lemma 1 is Lemma 2. If q | Φ_{a}(p), r | Φ_{b}(p), a ≠ b, q ≡ 1 (mod a), and r ≡ 1 (mod b), then q ≠ r.

Bang [2] (and subsequently several other authors) proved Lemma 3. If m ≥ 3 then Φ_{m}(p) has a prime divisor q such that q ≡ 1 (mod m).

3. The First Two Questions Consider the sequence of primes p_{k} (p_{1} = 2, p_{2} = 3, …) and denote the sequence of partial products by P_{n} = ∏_{k=1}^{n} p_{k}. Then

H(P_{n}) = ∏_{k=1}^{n} H(p_{k}) = ∏_{k=1}^{n} \frac{p_{k}}{p_{k} − 1} .

It is well known that the right-hand product diverges to infinity (see, for example, Theorem 429 in Hardy and Wright [10]), and so we have

lim_{n} sup H(n) = +∞ .

4 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A41

Table 1 k-imperfect numbers up to 10^{9}.

H(n) n  H(n) n
1  1  2  75852  2^{2} · 3^{2} · 7^{2} · 43
2  2  2  3  685440  2^{7} · 3^{2} · 5 · 7 · 17
3  6  2 · 3  3  758520  2^{3} · 3^{2} · 5 · 7^{2} · 43
2  12  2^{2} · 3  3  831600  2^{4} · 3^{3} · 5^{2} · 7 · 11
2  40  2^{3} · 5  3  2600640  2^{6} · 3^{3} · 5 · 7 · 43
3  120  2^{3} · 3 · 5  3  5533920  2^{5} · 3^{4} · 5 · 7 · 61
3  126  2 · 3^{2} · 7  3  6917400  2^{3} · 3^{4} · 5^{2} · 7 · 61
2  252  2^{2} · 3^{2} · 7  3  9102240  2^{5} · 3^{3} · 5 · 7^{2} · 43
2  880  2^{4} · 5 · 11  3  10281600  2^{7} · 3^{3} · 5^{2} · 7 · 17
3  2520  2^{3} · 3^{2} · 5 · 7  3  11377800  2^{3} · 3^{3} · 5^{2} · 7^{2} · 11 · 43
3  2640  2^{4} · 3 · 5 · 11  3  16687440  2^{4} · 3^{2} · 5 · 7^{2} · 11 · 43
2  10880  2^{7} · 5 · 17  3  152182800 2^{4} · 3^{4} · 5^{2} · 7 · 11 · 61
3  30240  2^{5} · 3^{3} · 5 · 7  3  206317440 2^{7} · 3^{2} · 5 · 7^{2} · 17 · 43
3  32640  2^{7} · 3 · 5 · 17  3  250311600 2^{4} · 3^{3} · 5^{2} · 7^{2} · 11 · 43
3  37800  2^{3} · 3^{3} · 5^{2} · 7  3  475917120 2^{6} · 3^{4} · 5 · 7 · 43 · 61
3  37926  2 · 3^{2} · 7^{2} · 43  2  715816960 2^{15} · 5 · 17 · 257
3  55440  2^{4} · 3^{2} · 5 · 7 · 11  3  866829600 2^{5} · 3^{5} · 5^{2} · 7^{3} · 13

In spite of this, however, no k-imperfect numbers for k ≥ 4 are known. This compares to the problem of perfect and multiply perfect numbers. We say n is perfect if σ(n) = 2n and we say n is multiply perfect of index k (or k-perfect) if σ(n) = kn for some integer k ≥ 3. Multiply perfect numbers of all indices up to 11 have been found.

Martin [1] observed the following: Suppose n = p^{2k−1}m, ρ(p^{2k}) = q, and (m, pq) = 1. Note that q − 1 = p · ρ(p^{2k−1}). Then

H(npq) = H(p^{2k}qm) = \frac{p^{2k}}{q} · \frac{q}{q − 1} · H(m) = H(p^{2k−1})H(m) = H(n) .

In particular if n is k-imperfect then so is npq.

Because of Martin’s result, Table 1 can be expanded considerably. Many chains of 3-imperfect numbers can be generated, such as

2^{7} · 3^{3} · 5^{2} · 7 · 17 ⟶ 2^{7} · 3^{4} · 5^{2} · 7 · 17 · 61 ⟶ 2^{7} · 3^{4} · 5^{2} · 7^{2} · 17 · 43 · 61 .

Thirteen new 3-imperfect numbers were found in this way, along with one imperfect number. Martin found 2^{9} · 3^{3} · 5^{3} · 11 · 13 · 31 (not in Table 1) to be 3-imperfect. Using ρ(2^{10}) = 683, ρ(3^{4}) = 61, ρ(5^{4}) = 521, and ρ(13^{2}) = 157, Martin generated 15 more 3-imperfect numbers. Nonetheless, the question of the infinitude of k-imperfect numbers remains open. This compares to perfect and k-perfect numbers: the question of infinitude remains open here as well, although it has been conjectured that only finitely many k-perfect numbers exist (for index k ≥ 3). It has also been conjectured that infinitely many Mersenne primes exist, which, if true, would imply the infinitude of perfect numbers.

4. The Shape of an Odd 3-Imperfect Number

It is obvious that an imperfect number be even, but there is no apparent reason why a 3-imperfect number should be even. Despite this, all known 3-imperfect numbers are even. Analogously, all known perfect and k-perfect numbers are even.

For the remainder of this paper, let N denote an odd 3-imperfect number. Then N = 3ρ(N), and so H(N) = 3.

For an odd prime p, it is clear from (1) that ρ(p^{a}) is odd if and only if a is even. Therefore N is a square, and we may assume

(8)  N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{k}^{2β_{k}} .

Furthermore, recalling (6), we have

(9)  N = 3 ∏_{i=1}^{k} ∏_{\begin{matrix}d|2β_{i}+1 \\ d>1 \end{matrix}} Φ_{2d}(p_{i}) .

Many results concerning the values β_{i} in (8) can be obtained. In this section, we present five such results.

Theorem 1. If N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{k}^{2β_{k}} is an odd 3-imperfect number then we cannot have β_{i} = 1 for all i, 1 ≤ i ≤ k.

Proof. Suppose β_{i} = 1 for all i, 1 ≤ i ≤ k. Since 3^{2}∥N, we have 3∥ρ(N). Thus 3∥ρ(q^{2}) for some prime q dividing N, and 3 ∤ ρ(p^{2}) for all other primes p dividing N. By (7) we must have q ≡ 2 (mod 3), and p ≡ 1 (mod 3) for all other primes p dividing N. But then q | ρ(N), and so q | ρ(p^{2}) for some other prime p dividing N (we can’t have q | ρ(3^{2}) = 7). But by Lemma 1, it is impossible to have q | Φ_{6}(p) = ρ(p^{2}). □

Theorem 2. If N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{k}^{2β_{k}} is an odd 3-imperfect number then β_{i} ≡ 1 (mod 3) for at least one i, 1 ≤ i ≤ k. □

Proof. Suppose β_{i} ≢ 1 (mod 3) for all i, 1 ≤ i ≤ k. Then 3^{2} | N so that 3 | ρ(N). Hence 3 | ρ(p^{2β}) for some prime p where p^{2β}∥N. But 3 ∤ 2β + 1, and thus 3 ∤ ρ(p^{2β}) by (7). □

Theorem 3. If N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{k}^{2β_{k}} is an odd 3-imperfect number then we cannot have β_{i} = 4 for all i, 1 ≤ i ≤ k.

Proof. Suppose β_{i} = 4 for all i, 1 ≤ i ≤ k. Since 3^{8}∥N we have 3^{7}∥ρ(N). Suppose 3 | ρ(p^{8}) for some prime p dividing N. Then by (7), p ≡ 2 (mod 3) and 3^{2}∥ρ(p^{8}). This implies v_{3}(ρ(N)) is even. □

Theorem 4. If N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{k}^{2β_{k}} is an odd 3-imperfect number then we cannot have β_{1} = 2α for 2 ≤ α ≤ 10 and β_{i} = 1 for all i, 2 ≤ i ≤ k.

Proof. Suppose β_{1} = α where 2 ≤ α ≤ 10, and β_{i} = 1 for 2 ≤ i ≤ k. If 3^{2α}∥N, then 3^{2α−1}∥ρ(N). By (7), there are exactly 2α − 1 primes (say p_{2}, p_{3}, …, p_{2α}) such that p_{i} ≡ 2 (mod 3). By Lemma 1, for 2 ≤ i ≤ 2α, it is impossible for p_{i} to divide Φ_{6}(q) = ρ(q^{2}) for any prime q; therefore ∏_{i=2}^{2α} p_{i}^{2} | ρ(3^{2α}). Inspection of the factorizations of ρ(3^{2α}) for 2 ≤ α ≤ 10 shows that this is impossible (as the factorizations of ρ(3^{2α}) are all squarefree).

Otherwise 3^{2}∥N, and therefore 3∥ρ(N). We first show it is impossible to have 3 | ρ(p_{1}^{2α}). For, by (7) we have p_{1} ≡ 2 (mod 3). But then p_{1} | ρ(p_{i}^{2}) for some i, and this is impossible by Lemma 1 since ρ(p_{i}^{2}) = Φ_{6}(p_{i}). Therefore (say) p_{2} = 3 and 3 | ρ(p_{3}^{2}); by (7) we have p_{3} ≡ 2 (mod 3) and p_{i} ≡ 1 (mod 3) for 4 ≤ i ≤ k. Furthermore, p_{3}^{2} | ρ(p_{1}^{2α}) (since it is impossible by Lemma 1 to have p_{3} | Φ_{6}(q) = ρ(q^{2}) for any prime q).

Now ρ(3^{2}) = 7 and hence 7 | N. Inspection shows that it is impossible to have p_{3}^{2} | ρ(7^{2α}) for 2 ≤ α ≤ 10 (as the factorizations of ρ(7^{2α}) are all squarefree), so we must have 7^{2}∥N. As ρ(7^{2}) = 43, we must have 43 | N. Similarly (inspection) we cannot have 43^{2α}∥N and so 43^{2}∥N. Then ρ(43^{2}) = 13 · 139, and so 13 · 139 | N. Again, by inspection we must have 13^{2} · 139^{2}∥N. Then ρ(13^{2} · 139^{2}) = 157 · 19183, and by inspection we have ρ(157^{2} · 19183^{2}) | N. But 7^{3} | ρ(3^{2} · 157^{2} · 19183^{2}), giving 7^{3} | N, contradicting 7^{2}∥N. □

Theorem 5. If N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{k}^{2β_{k}} is an odd 3-imperfect number then we cannot have β_{1} = β_{2} = 2 and β_{i} = 1 for all i, 3 ≤ i ≤ k.

Proof. First, suppose that 3^{4}∥N. Then (as we cannot have 3 | Φ_{5}(q) = ρ(q^{4}) for any prime q by Lemma 1) then there exist exactly three primes (say p_{3}, p_{4}, p_{5}) such that p_{i} ≡ 2 (mod 3) (and thus 3∥ρ(p_{i}^{2})); furthermore (letting p_{1} = 3) we have p_{3}^{2}p_{4}^{2}p_{5}^{2} | ρ(p_{2}^{4}) as it is impossible by Lemma 1 to have p_{i} | Φ_{3}(q) = ρ(q^{2}) for any prime q, 3 ≤ i ≤ 5 (and, ρ(3^{4}) = 61). Now the factorizations of ρ(q^{4}) for q = 61, 7, 523, 43, 907, 13, and 157 are all squarefree, so p_{2} cannot be any of these primes. As ρ(3^{4}) = 61, we see that 61 | N and hence 61^{2}∥N. Then ρ(61^{2}) = 7 · 523 so that 7^{2} · 523^{2}∥N, ρ(7^{2} · 523^{2}) = 7 · 43^{2} · 907 so that 43^{2}∥N, ρ(43^{2}) = 13 · 139 so that 13^{2}∥N, ρ(13^{2}) = 157 so that 157^{2}∥N, and ρ(157^{2}) = 7·3499. But 7^{3} | ρ(61^{2} ·523^{2} ·157^{2}) implies 7^{3} | N, while we have 7^{2}∥N. Therefore we cannot have 3^{4}∥N.

The case when 3^{2}∥N is handled similarly. Letting p_{3} = 3, there is exactly one prime (say p_{4}) such that p_{4} ≡ 2 (mod 3), so that 3∥ρ(p_{4}^{2}). Then p_{4} | ρ(p_{1}^{4}p_{2}^{4}), and ρ(p_{1}^{4}p_{2}^{4}) has no other prime divisors which are congruent to 2 modulo 3 except for at most two, but this is only if p_{1} | ρ(p_{2}^{4}) or p_{2} | ρ(p_{1}^{4}). With this in mind, it is not difficult to show that neither p_{1} nor p_{2} can be one of 7, 43, 13, 139, 157, or 19183. We then proceed as above: ρ(3^{2}) = 7, ρ(7^{2}) = 43, ρ(43^{2}) = 13 · 139, ρ(13^{2} · 139^{2}) = 157 · 19183, so we have 7^{3} | ρ(3^{2} · 157^{2} · 19183^{2}), implying 7^{3} | N, and yet 7^{2}∥N. This contradiction completes the proof. □

Similar results have been obtained for the shape of odd perfect numbers. It is well known that an odd perfect number n must have the form n = q^{α}p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{k}^{2β_{k}}, where q ≡ α ≡ 1 (mod 4). Steuerwald [18] showed that we cannot have β_{i} = 1 for 1 ≤ i ≤ k. McDaniel [15] showed that we cannot have β_{i} ≡ 1 (mod 3) for 1 ≤ i ≤ k. Cohen and Williams [6] showed that we cannot have β_{1} = 5 or 6 with β_{i} = 1 for 2 ≤ i ≤ k. Brauer [3] showed that we cannot have β_{1} = 2 and β_{i} = 1 for 2 ≤ i ≤ k. Kanold [13] showed that we cannot have β_{1} = 3, β_{2} = 2, and β_{i} = 1 for 3 ≤ i ≤ k. Iannucci and Sorli [11] showed that if β_{i} ≡ 1 (mod 3) or 2 (mod 5) for all i then 3 ∤ n.

5. The Number of Distinct Prime Divisors of an Odd 3-Imperfect Number

With N given as in (8), we say that ω(N) = k. It is immediate from (2) and (4) that ω(N) ≥ 16 since

\frac{4}{3} · \frac{6}{5} · \frac{8}{7} · \frac{12}{11} · \frac{14}{13} · \frac{18}{17} · \frac{20}{19} · \frac{24}{23} · \frac{30}{29} · \frac{32}{31} · \frac{38}{37} · \frac{42}{41} · \frac{44}{43} · \frac{48}{47} · \frac{54}{53} < 3 .

In this section we increase this lower bound of 16:

Theorem 6. An odd 3-imperfect number contains at least 18 distinct prime divisors.

Proof. Suppose ω(N) = 16. Write

N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{16}^{2β_{16}} , p_{1} < p_{2} < ⋯ < p_{16} .

It is obvious that p_{1} = 3 (as N = 3ρ(N)). From (2) and (4) it follows that p_{2} = 5, p_{3} = 7, …, p_{10} = 31, since

\frac{4}{3} · \frac{6}{5} · \frac{8}{7} · \frac{12}{11} · \frac{14}{13} · \frac{18}{17} · \frac{20}{19} · \frac{24}{23} · \frac{30}{29} · \frac{38}{37} · \frac{42}{41} · \frac{44}{43} · \frac{48}{47} · \frac{54}{53} · \frac{60}{59} · \frac{62}{61} < 3 .

Similarly p_{11} is either 37 or 41 because

\frac{4}{3} · \frac{6}{5} · \frac{8}{7} · \frac{12}{11} · \frac{14}{13} · \frac{18}{17} · \frac{20}{19} · \frac{24}{23} · \frac{30}{29} · \frac{32}{31} · \frac{44}{43} · \frac{48}{47} · \frac{54}{53} · \frac{60}{59} · \frac{62}{61} · \frac{68}{67} < 3 .

The same type of argument then yields 41 ≤ p_{12} ≤ 43, 43 ≤ p_{13} ≤ 53, 47 ≤ p_{14} ≤ 61, 53 ≤ p_{15} ≤ 83, and 59 ≤ p_{16} ≤ 257. In particular, no prime divisor of N exceeds 257.

Since 17 | N, we have by (9) that 17 | Φ_{2d}(p_{i}) for some i, where d | 2β_{i} + 1. By Lemma 1, we have d = 17^{γ}, where γ > 0 (as d > 1), and p_{i} ≡ −1 (mod 17). Since 2 · 17^{γ} | 2β_{i} + 1, we have by (6) that Φ_{34}(p_{i}) | N. There are only two primes not exceeding 257 which are congruent to −1 modulo 17, namely 67 and 101. But Φ_{34}(67) and Φ_{34}(101) each contain a prime divisor which exceeds 257. This contradiction shows that ω(N) ≥ 17.

Now suppose that ω(N) = 17. Write

N = p_{1}^{2β_{1}}p_{2}^{2β_{2}} ⋯ p_{17}^{2β_{17}} , p_{1} < p_{2} < ⋯ < p_{17} .

Applying (2) and (4) as above, we may deduce that p_{1} = 3, p_{2} = 5, …, p_{7} = 19, and that p_{16} ≤ 521. Hence at most one prime divisor of N may exceed 521.

Again, we have 17 | N, so as above we have 17 | ρ(p_{i}^{2β_{i}}) for some i, where p_{i} ≡ −1 (mod 17), and we also have Φ_{34}(p_{i}) | N. There are exactly five primes q ≤ 521 for which q ≡ −1 (mod 17): 67, 101, 271, 373, and 509. In each case, Φ_{34}(q) contains at least two prime divisors which exceed 521. Therefore we must have p_{17} ≡ −1 (mod 17) and (since N is a square) 17^{2} | ρ(p_{17}^{2β_{17}}); by (7) this implies 17^{2} | 2β_{17} + 1. Thus by (6) we have Φ_{578}(p_{17}) | N, and hence by Lemma 3 we have a prime q | N such that q ≡ 1 (mod 578). Since q ≠ p_{17}, we have two prime divisors of N exceeding 521. This contradiction completes the proof of the theorem. □

Analogously, Hagis [8] and Chein [4] independently showed that if n is an odd perfect number then ω(n) ≥ 8. Reidlinger [17], Kishore [14], and Hagis [9] independently showed that an odd 3-perfect number must have at least 12 distinct prime factors.

6. The Largest Prime Divisor of an Odd 3-Imperfect Number

In this section we prove that the largest prime divisor of an odd 3-imperfect number must exceed 10^{9} by constructing an algorithm which is then carried out with a computer:

Theorem 7. The largest prime divisor of an odd 3-imperfect number exceeds 10^{9}.

Proof. First we describe the algorithm by which the proof is carried out. For a natural number M, let P(M) denote the statement, “The largest prime divisor of N exceeds M.” We assume, for the sake of contradiction, that p ≤ M for all prime divisors p of N. Then (say) 3^{2β}∥N and so by (9), Φ_{2r}(3) | N for all prime divisors r of 2β + 1 (all such r being odd). By Lemma 3, we must have r < M/2 for all such r (otherwise Φ_{2r}(3) is divisible by a prime exceeding M). Therefore it suffices to show that the assumption Φ_{2r}(3) | N leads to a contradiction for all odd primes r < M/2. Let L_{m}(p) denote the largest prime divisor of Φ_{m}(p). If L_{2r}(3) > M then the contradiction is immediate. Otherwise (say) q = L_{2r}(3) and q < M, and so we must disprove q | N before we can finish disproving Φ_{2r}(3) | N.

In disproving Φ_{2r}(3) | N, we take the odd primes r < M/2 in ascending order, beginning with r = 3. Thus we begin by assuming Φ_{6}(3) | N. Since L_{6}(3) = 7, we must then disprove 7 | N before proceeding to r = 5. To disprove 7 | N, we must show that Φ_{2r}(7) | N leads to a contradiction for all odd primes r < M/2, the primes r to be considered in ascending order beginning with r = 3. Since L_{6}(7) = 43, we must then disprove 43 | N, and so on.

In this way we generate a tree. At the root of the tree is the supposition 3 | N. Every edge from the root corresponds to an odd prime r < M/2 for which L_{2r}(3) < M; thus the vertex at the end of such an edge corresponds to the supposition q | N, where q = L_{2r}(3). Then, from this vertex, each edge corresponds to an odd prime r < M/2 for which L_{2r}(q) < M, and the vertex at the other end of such an edge corresponds to the supposition p | N, where p = L_{2r}(q), and so forth.

A given supposition p | N is false if, for all r < M/2, either L_{2r}(p) > M or q | Φ_{2r}(p) for an odd prime q which has already been disproved as a divisor of N.

We illustrate this for the proof of P(10^{3}):

0:  3 ⟶^{3} 7
1:  7 ⟶^{3} 43
2:  43 ⟶^{3} 139
3:  139 ∤ N
2:  43 ∤ N
1:  7 ⟶^{5} 191
2:  191 ∤ N
1:  7 ⟶^{7} 911
2:  911 ∤ N
1:  7 ∤ N
0:  3 ⟶^{5} 61
1:  61 ∤ N
0:  3 ⟶^{7} 547
1:  547 ∤ N
0:  3 ⟶^{11} 661

1:  661 ∤ N
0:  3 ∤ N

The numbers along the left margin indicate the number of edges between the root of the tree and the particular vertex at the beginning of that line. Each of the 9 indicated primes were disproved as divisors of N by computation. It is a simple matter, say, to test whether or not Φ_{97}(3) has any prime divisors q > 10^{3}. By Lemma 1, q ≡ 1 (mod 194), so it suffices merely to test all such primes q < 10^{3} to see if 3^{97} ≡ 1 (mod q). Thus we obtain the product, say R, of all primes less than 10^{3} which divide Φ_{97}(3). If ln R < 96 ln 3, then Φ_{97}(3) must contain a prime divisor greater than 10^{3}.

We then generated the proof of P(10^{9}), which produced 139 lines of output (as compared to the 17 lines above taken above for P(10^{3})), and 70 primes in all had to be disproved as divisors of N. The computations were carried out using the UBASIC software package. We present the first 12 lines and the last 12 lines of the output for the proof of P(10^{9}):

0:  3 ⟶^{3} 7
1:  7 ⟶^{3} 43
2:  43 ⟶^{3} 139
3:  139 ⟶^{3} 19183
4:  19183 ⟶^{3} 2766679
5:  2766679 ∤ N
4:  19183 ∤ N
3:  139 ⟶^{5} 1201
4:  1201 ⟶^{3} 1441201
5:  1441201 ⟶^{3} 14623159
6:  14623159 ⟶^{3} 5800159
7:  5800159 ∤ N
⋮  ⋮  ⋮
⋮  ⋮  ⋮
3:  116243551 ⟶^{3} 75833059
4:  75833059 ∤ N
3:  116243551 ∤ N
2:  1041421 ∤ N
1:  1021 ∤ N
0:  3 ⟶^{19} 101917
1:  101917 ∤ N
0:  3 ⟶^{29} 5385997

1:  5385997 ∤ N
0:  3 ⟶^{37} 56737873
1:  56737873 ∤ N
0:  3 ∤ N

As the desired contradiction has been obtained, the proof is complete. □

An analogous result on odd perfect numbers was given by Jenkins [12], who showed that the largest prime divisor must exceed 10^{7}. Cohen and Hagis [5] showed that if n is an odd k-perfect number (k ≥ 3) then its largest prime divisor is at least 100129.

7. A General Result

In this section we give an upper bound on v_{3}(N) which depends only on ω(N):

Theorem 8. If N is an odd 3-imperfect number then

v_{3}(N) ≤ 1 + (\frac{ω(N) − 1}{2})^{2} .

Proof. We may write

(10)  N = 3^{2α} ∏_{i=1}^{μ} p_{i}^{2a_{i}} ∏_{j=1}^{ν} q_{j}^{2b_{j}},

where p_{i} ≡ 1 (mod 3) for all i and q_{j} ≡ 2 (mod 3) for all j. Neither of the products ∏_{i=1}^{μ} p_{i}^{2a_{i}} nor ∏_{j=1}^{ν} q_{j}^{2b_{j}} are empty: in other words μ > 0 and ν > 0. For, 3 | ρ(N), and by (7) v_{3}(ρ(N)) = v_{3}(∏_{j=1}^{ν} q_{j}^{2b_{j}}), and so ν > 0.

Since 3 | ρ(q_{j}^{2b_{j}}) for some q_{j}^{2b_{j}}∥N, we have by (7) 3 | 2b_{j} + 1. Thus by (6) Φ_{2·3^{γ}} (q_{j}) | ρ(N) for some γ > 0. By Lemma 3 Φ_{2·3^{γ}} (q_{j}) | ρ(N) is divisible by a prime which is congruent to 1 modulo 3, and so μ > 0.

As in the preceding paragraph, we apply (7) and obtain

v_{3}(ρ(N)) = ∑_{j=1}^{ν} v_{3}(2b_{j} + 1).

Let

γ = max_{1≤j≤ν} v_{3}(2b_{j} + 1).

Then by (6), for some j we have

(11)  Φ_{2·3}(q_{j})Φ_{2·3^{2}}(q_{j}) ⋯ Φ_{2·3^{γ}} (q_{j}) | ρ(N),

and by Lemmas 2 and 3 the product above in (11) contains at least γ distinct primes all congruent to 1 modulo 3. Therefore μ ≥ γ.

Suppose ω(N) = k. Then as in (10) we have k = 1 + μ + ν. Since μ ≥ γ we have

(12)  ν ≤ k − 1 − γ.

Now

2α − 1 = v_{3}(ρ(N)) = ∑_{j=1}^{ν} v_{3}(2b_{j} + 1) ≤ νγ.

Combining this with (12) yields

(13)  2α ≤ 1 + γ(k − 1 − γ).

The right-hand side of (13) is maximized when γ = (k − 1)/2 and so we have

2α ≤ 1 + (\frac{k − 1}{2})^{2} ,

and this completes the proof. □

8. Concluding Remarks

Martin obviously considered ρ as a variation of σ; he actually used the symbol σ̃ by which to refer to ρ (this is also mentioned in Guy [7], p.72). However, it may be more precise to think of ρ as a generalization of Euler’s totient function ϕ, since

ρ(n) = ∑_{\begin{matrix}1≤k≤n \\ (k,n)∈S \end{matrix}} 1,

where S denotes the set of square integers.

It is clear that the problems posed by Martin are every bit as intractable as those analogously pertaining to the σ function. The methods used here are parallel to those that have been applied to the odd perfect number and odd k-perfect number problems. As an added note, the author slightly modified the algorithm which produced P(10^{9}) in section 6 and applied it to show that if n is an odd triperfect number, no prime divisor of which exceeds 10^{9}, then 3 ∤ n.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A41 13

References

1. Compiled by G. Myerson, Macquarie University, Sydney, Problem 99:08 from the Western Number Theory Conference..

2. A. Bang, Taltheoretiske Undersøgelser, Tidsskrift Math. 5 (1886), no. IV, 70–80, 130–137.

3. A. Brauer, On the nonexistence of odd perfect numbers of the form p^{α}q_{1}^{2}q_{2}^{2} ⋯ q_{t−1}^{2}q_{t}^{4}, Bull. Amer. Math. Soc. 49 (1943), 712–718.

4. E. Z. Chein, Ph.D. Thesis, Pennsylvania State University (1979).

5. G.L. Cohen and P. Hagis, Results concerning odd multiperfect numbers, Bull. Maylaysian Math. Soc. 8 (1985), 23–26.

6. G. Cohen and R. Williams, Extensions of some results concerning odd perfect numbers, J. Fibonacci Quart. 23 (1985), 70–76.

7. R. Guy, Unsolved Problems in Number Theory (Third Edition), Springer-Verlag, 2004.

8. P. Hagis, Outline of a proof that every odd perfect number has at least eight prime factors, Math. Comp. 35 (1980), 1027–1032.

9. P. Hagis, A new proof that every odd triperfect number has at least twelve prime factors, Contemp. Math. 143 (1993), 445–450.

10. G. Hardy and E. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1979, pp. 111– 118.

11. D. Iannucci and R. Sorli, On the total number of prime factors of an odd perfect number, Math. Comp. 72 (2003), 2077–2084.

12. P. Jenkins, Odd perfect numbers have a prime factor exceeding 10^{7}, Math. Comp. 72 (2003), 1549–1554.

13. H.-J. Kanold, Sätze über kreisteilungspolynome und ihre andwendungen auf einiger zahlentheoretische problem II, J. Reine Angew. Math. 188 (1950), 129–146.

14. M. Kishore, Odd triperfect numbers are divisible by twelve distinct prime factors, J. Austral. Math. Soc. 42 (1987), 173–182.

15. W. McDaniel, The nonexistence of odd perfect numbers of a certain form, Arch. Math. 21 (1970), 52–53.

16. T. Nagell, Introduction to Number Theory, AMS Chelsea Publishing, Providence, RI, 1981.

17. H. Reidlinger, Über ungerademehrfach volkommene Zahlen, Osterreichische Akad. Wiss. Math.-Natur. 192 (1983), 237–266.

18. R. Steuerwald, Verschärfung einer notwendigen Bedingung für die Existenz einer ungeraden vollkommenen Zahl, S.-B. Math.-Nat. Abt. Bayer. Akad. Wiss. (1937), 68–73.