\input amstex

\documentstyle{amsppt}

\magnification=\magstephalf

\pagewidth{6.25truein}

\pageheight{9.25truein}

\parskip=10pt

\voffset=0pt

\font\smallit=cmti10

\font\smalltt=cmtt9

\font\smallrm=cmr8

\NoBlackBoxes




\topmatter

\leftheadtext{\hskip 8pt \smalltt INTEGERS: \smallrm Electronic Journal of Combinatorial Number Theory \smalltt 6 (2006), \#A41 }

\rightheadtext{\smalltt INTEGERS: \smallrm Electronic Journal of Combinatorial Number Theory \smalltt 6 (2006), \#A41 \hskip 8pt}

\endtopmatter

\document
\vskip -40pt
\centerline{\smalltt INTEGERS: \smallrm ELECTRONIC
JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 6 (2006), \#A41 }
\vskip 40pt



\centerline{\bf ON A VARIATION OF PERFECT NUMBERS}

\vskip 20pt
\centerline{\bf Douglas E. Iannucci}

\centerline{\smallit University of the Virgin Islands, St. Thomas, VI 00802}

\centerline{\tt diannuc\@uvi.edu} 

\vskip 30pt

\centerline{\smallit Received: 3/17/06, Revised: 11/5/06,
 Accepted:  12/4/06, Published: 12/20/06}

\vskip 30pt

\centerline{\bf Abstract}





\noindent

We define a positive integer $n$ to be $k$-imperfect if $k\rho(n)=kn$ for some integer $k\ge2$. Here, $\rho$ is a multiplicative arithmetic function defined by $\rho(p^a)=p^a-p^{a-1}+p^{a-2}-\cdots+(-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.



\baselineskip=15pt

\vskip 30pt 





\subhead \nofrills{\bf 1. Introduction}\endsubhead



\noindent

The arithmetic function $\sigma$ is called the sum-of-divisors
 function because $\sigma(n)$ gives the sum of the positive divisors of a
natural number $n$. Since $\sigma$ is multiplicative, it may be defined
by $\sigma(1)=1$ and 
$$\sigma(p^a)=p^a+p^{a-1}+p^{a-2}+\cdots+1$$
for a prime $p$ and integer $a\ge1$. 

Analogously, we define a multiplicative arithmetic function $\rho$ by $\rho(1)=1$ and
$$\rho(p^a)=p^a-p^{a-1}+p^{a-2}-\cdots+(-1)^a\tag1$$
for a prime $p$ and integer $a\ge1$. 



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





Martin~\cite{1} introduced the function $\rho$ at the 1999 Western Number Theory Conference, and raised three questions (see Guy~\cite{7}, p.72):

\roster

\item Are there any $k$-imperfect numbers with $k\ge4$?

\item Are there infinitely many $k$-imperfect numbers?

\item Are there any odd 3-imperfect numbers?

\endroster



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

\vskip 30pt 

%

%

%

%

%

\subhead \nofrills{\bf 2. Preliminaries}\endsubhead



\noindent

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$, $\alpha$, and $\beta$. We shall let $\gamma$ represent a nonnegative integer. If $p\nmid a$ we let $e_p(a)$ denote the exponent to which $a$ belongs, modulo~$p$. We write $p^a\|n$ if $p^a\mid n$ and $p^{a+1}\nmid 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}{\rho(n)}\,.$$
Therefore $n$ is $k$-imperfect if $H(n)=k$. Note that $H$ is multiplicative. Note that
$$\frac1{H(p^a)}=1-\frac1{p}+\frac1{p^2}-\cdots+\frac{(-1)^a}{p^a}\,.$$
Therefore
$$\frac{p^2}{p^2-p+1}\le H(p^{2a})<\frac{p+1}{p}\,.\tag2$$

If $a<b$ then
$$H(p^{2a})<H(p^{2b})\,.\tag3$$

If $p<q$ then $(q+1)/q<p^2/(p^2-p+1)$, and so for any $a$, $b$, we have
$$H(q^b)<H(p^a)\,.\tag4$$



From~(1) we have
$$\rho(p^{2a})=\frac{p^{2a+1}+1}{p+1}\,.\tag5$$

We denote the $n^{\text{th}}$ cyclotomic polynomial, evaluated at $x$, by $\Phi_n(x)$. From~(5), and from the identity
$$x^n-1=\prod_{d|n}\Phi_d(x)\,,$$
we have
$$\rho(p^{2a})=\prod\Sb d\mid 2a+1\\d>1\endSb\Phi_{2d}(p)\,.\tag6$$

From Theorems 94 and 95 in Nagell~\cite{16}, we have the following

\proclaim{Lemma 1}
Let $h=e_q(p)$. Then $q\mid\Phi_m(p)$ if and only if $m=hq^{\gamma}$. If $\gamma>0$ then $q\|\Phi_{hq^{\gamma}}(p)$.

\endproclaim

Letting $h=e_q(p)$, it follows from (6) and Lemma~1 that
$$v_q(\rho(p^{2a})=\cases v_q(\Phi_h(p))+v_q(2a+1),&\text{if $h>2$, $h\mid2(2a+1)$, $h\nmid2a+1$,}\\
                              v_q(2a+1),           &\text{if $h=2$,}\\
                                     0,            &\text{otherwise.}\endcases\tag7$$

Another direct consequence of Lemma~1 is

\proclaim{Lemma 2}
If $q\mid\Phi_a(p)$, $r\mid\Phi_b(p)$, $a\ne b$, $q\equiv1\pmod{a}$, and $r\equiv1\pmod{b}$, then $q\ne r$.

\endproclaim

Bang~\cite{2} (and subsequently several other authors) proved

\proclaim{Lemma 3}
If $m\ge3$ then $\Phi_m(p)$ has a prime divisor $q$ such that $q\equiv1\pmod{m}$.

\endproclaim

%

%

%    Table 1

%

%

\topinsert

\topcaption{{\smc Table 1}\quad\rm $k$-imperfect numbers up to $10^9$.}
\endcaption

\settabs 13\columns

\+$H(n)$&$n$&& & & &$H(n)$&$n$&& & & &\cr

\+1&      1&&  & & &2&75852&&$2^2\cdot3^2\cdot7^2\cdot43$\cr

\+2&      2&&2 & & &3&685440&&$2^7\cdot3^2\cdot5\cdot7\cdot17$\cr

\+3& 6&&$2\cdot3$&&&3&758520&&$2^3\cdot3^2\cdot5\cdot7^2\cdot43$\cr
\+2&12&&$2^2\cdot3$&&&3&831600&&$2^4\cdot3^3\cdot5^2\cdot7\cdot11$\cr
\+2&40&&$2^3\cdot5$&&&3&2600640&&$2^6\cdot3^3\cdot5\cdot7\cdot43$\cr
\+3&120&&$2^3\cdot3\cdot5$&&&3&5533920&&$2^5\cdot3^4\cdot5\cdot7\cdot61$\cr
\+3&126&&$2\cdot3^2\cdot7$&&&3&6917400&&$2^3\cdot3^4\cdot5^2\cdot7\cdot61$\cr
\+2&252&&$2^2\cdot3^2\cdot7$&&&3&9102240&&$2^5\cdot3^3\cdot5\cdot7^2\cdot43$\cr
\+2&880&&$2^4\cdot5\cdot11$&&&3&10281600&&$2^7\cdot3^3\cdot5^2\cdot7\cdot17$\cr
\+3&2520&&$2^3\cdot3^2\cdot5\cdot7$&&&3&11377800&&$2^3\cdot3^3\cdot5^2\cdot7^2\cdot11\cdot43$\cr
\+3&2640&&$2^4\cdot3\cdot5\cdot11$&&&3&16687440&&$2^4\cdot3^2\cdot5\cdot7^2\cdot11\cdot43$\cr
\+2&10880&&$2^7\cdot5\cdot17$&&&3&152182800&&$2^4\cdot3^4\cdot5^2\cdot7\cdot11\cdot61$\cr
\+3&30240&&$2^5\cdot3^3\cdot5\cdot7$&&&3&206317440&&$2^7\cdot3^2\cdot5\cdot7^2\cdot17\cdot43$\cr
\+3&32640&&$2^7\cdot3\cdot5\cdot17$&&&3&250311600&&$2^4\cdot3^3\cdot5^2\cdot7^2\cdot11\cdot43$\cr
\+3&37800&&$2^3\cdot3^3\cdot5^2\cdot7$&&&3&475917120&&$2^6\cdot3^4\cdot5\cdot7\cdot43\cdot61$\cr
\+3&37926&&$2\cdot3^2\cdot7^2\cdot43$&&&2&715816960&&$2^{15}\cdot5\cdot17\cdot257$\cr
\+3&55440&&$2^4\cdot3^2\cdot5\cdot7\cdot11$&&&3&866829600&&$2^5\cdot3^5\cdot5^2\cdot7^3\cdot13$\cr 
\endinsert
\vskip 30pt 
%
%
%
%
%
\subhead \nofrills{\bf 3. The First Two Questions}\endsubhead

\noindent
Consider the sequence of primes $p_k$ ($p_1=2$, $p_2=3$, \dots) and denote the sequence of partial products by $P_n=\prod_{k=1}^np_k$. Then
$$H(P_n)=\prod_{k=1}^nH(p_k)=\prod_{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~\cite{10}), and so we have
$$\lim_{n}\,\sup{H(n)}=+\infty\,.$$
In spite of this, however, no $k$-imperfect numbers for $k\ge4$ are known. This compares to the problem of perfect and multiply perfect numbers. We say $n$ is perfect if $\sigma(n)=2n$ and we say $n$ is multiply perfect of index $k$ (or $k$-perfect) if $\sigma(n)=kn$ for some integer $k\ge3$. Multiply perfect numbers of all indices up to~11 have been found.

Martin~\cite{1} observed the following: Suppose $n=p^{2k-1}m$, $\rho(p^{2k})=q$, and $(m,pq)=1$. Note that $q-1=p\cdot\rho(p^{2k-1})$. Then
$$H(npq)=H(p^{2k}qm)=\frac{p^{2k}}{q}\cdot\frac{q}{q-1}\cdot 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\cdot3^3\cdot5^2\cdot7\cdot17\longrightarrow2^7\cdot3^4\cdot5^2\cdot7\cdot17\cdot61\longrightarrow2^7\cdot3^4\cdot5^2\cdot7^2\cdot17\cdot43\cdot61\,.$$
Thirteen new 3-imperfect numbers were found in this way, along with one imperfect number. Martin found $2^9\cdot3^3\cdot5^3\cdot11\cdot13\cdot31$ (not in Table~1) to be 3-imperfect. Using $\rho(2^{10})=683$, $\rho(3^4)=61$, $\rho(5^4)=521$, and $\rho(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\ge3$). It has also been conjectured that infinitely many Mersenne primes exist, which, if true, would imply the infinitude of perfect numbers. 
\vskip 30pt 
%
%
%
%
\subhead \nofrills{\bf 4. The Shape of an Odd 3-Imperfect Number}\endsubhead



\noindent

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\rho(N)$, and so $H(N)=3$. 



For an odd prime $p$, it is clear from~(1) that $\rho(p^a)$ is odd if and only if $a$ is even. Therefore $N$ is a square, and we may assume
$$N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_k^{2\beta_k}\,.\tag8$$

Furthermore, recalling~(6), we have
$$N=3\prod_{i=1}^{k}\prod\Sb d\mid 2\beta_i+1\\d>1\endSb\Phi_{2d}(p_i)\,.\tag9$$

Many results concerning the values $\beta_i$ in~(8) can be obtained. In this section, we present five such results.

\proclaim{Theorem 1}
If $N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_k^{2\beta_k}$ is an odd 3-imperfect number then we cannot have $\beta_i=1$ for all $i$, $1\le i\le k$.

\endproclaim

\smallskip\noindent{\it Proof.}\quad
Suppose $\beta_i=1$ for all $i$, $1\le i\le k$. Since $3^2\| N$, we have $3\|\rho(N)$. Thus $3\|\rho(q^2)$ for some prime $q$ dividing $N$, and $3\nmid\rho(p^2)$ for all other primes $p$ dividing $N$. By~(7) we must have $q\equiv2\pmod3$, and $p\equiv1\pmod3$ for all other primes $p$ dividing $N$. But then $q\mid\rho(N)$, and so $q\mid\rho(p^2)$ for some other prime $p$ dividing $N$ (we can't have $q\mid\rho(3^2)=7$). But by Lemma~1, it is impossible to have $q\mid\Phi_6(p)=\rho(p^2)$.
\qed

\proclaim{Theorem 2}
If $N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_k^{2\beta_k}$ is an odd 3-imperfect number then $\beta_i\equiv1\pmod3$ for at least one $i$, $1\le i\le k$. \qed

\endproclaim

\smallskip\noindent{\it Proof.}\quad
Suppose $\beta_i\not\equiv1\pmod3$ for all $i$, $1\le i\le k$. Then $3^2\mid N$ so that $3\mid\rho(N)$. Hence $3\mid\rho(p^{2\beta})$ for some prime $p$ where $p^{2\beta}\|N$. But $3\nmid2\beta+1$, and thus $3\nmid\rho(p^{2\beta})$ by~(7).\hfill \qed

\proclaim{Theorem 3}
If $N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_k^{2\beta_k}$ is an odd 3-imperfect number then we cannot have $\beta_i=4$ for all $i$, $1\le i\le k$.

\endproclaim

\smallskip\noindent{\it Proof.}\quad
Suppose $\beta_i=4$ for all $i$, $1\le i\le k$. Since $3^8\|N$ we have $3^7\|\rho(N)$. Suppose $3\mid\rho(p^8)$ for some prime $p$ dividing $N$. Then by~(7), $p\equiv2\pmod3$ and $3^2\|\rho(p^8)$. This implies $v_3(\rho(N))$ is even.\hfill \qed

\proclaim{Theorem 4}
If $N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_k^{2\beta_k}$ is an odd 3-imperfect number then we cannot have $\beta_1=2\alpha$ for $2\le\alpha\le10$ and $\beta_i=1$ for all $i$, $2\le i\le k$.

\endproclaim
\smallskip\noindent{\it Proof.}\quad
Suppose $\beta_1=\alpha$ where $2\le\alpha\le10$, and $\beta_i=1$ for $2\le i\le k$. If $3^{2\alpha}\|N$, then $3^{2\alpha-1}\|\rho(N)$. By~(7), there are exactly $2\alpha-1$ primes (say $p_2$, $p_3$, \dots, $p_{2\alpha}$) such that $p_i\equiv2\pmod3$. By Lemma~1, for $2\le i\le2\alpha$, it is impossible for $p_i$ to divide $\Phi_6(q)=\rho(q^2)$ for any prime $q$; therefore $\prod_{i=2}^{2\alpha}p_i^2\mid\rho(3^{2\alpha})$. Inspection of the factorizations of $\rho(3^{2\alpha})$ for $2\le\alpha\le10$ shows that this is impossible (as the factorizations of $\rho(3^{2\alpha})$ are all squarefree). 

Otherwise $3^2\|N$, and therefore $3\|\rho(N)$. We first show it is impossible to have $3\mid\rho(p_1^{2\alpha})$. For, by~(7) we have $p_1\equiv2\pmod3$. But then $p_1\mid\rho(p_i^2)$ for some $i$, and this is impossible by Lemma~1 since $\rho(p_i^2)=\Phi_6(p_i)$. Therefore (say) $p_2=3$ and $3\mid\rho(p_3^2)$; by~(7) we have $p_3\equiv2\pmod3$ and $p_i\equiv1\pmod3$ for $4\le i\le k$. Furthermore, $p_3^2\mid\rho(p_1^{2\alpha})$ (since it is impossible by Lemma~1 to have $p_3\mid\Phi_6(q)=\rho(q^2)$ for any prime $q$).

Now $\rho(3^2)=7$ and hence $7\mid N$. Inspection shows that it is impossible to have $p_3^2\mid\rho(7^{2\alpha})$ for $2\le\alpha\le10$ (as the factorizations of $\rho(7^{2\alpha})$ are all squarefree), so we must have $7^2\|N$. As $\rho(7^2)=43$, we must have $43\mid N$. Similarly (inspection) we cannot have $43^{2\alpha}\|N$ and so $43^2\|N$. Then $\rho(43^2)=13\cdot139$, and so $13\cdot139\mid N$. Again, by inspection we must have $13^2\cdot139^2\|N$. Then $\rho(13^2\cdot139^2)=157\cdot19183$, and by inspection we have $\rho(157^2\cdot19183^2)\mid N$. But $7^3\mid\rho(3^2\cdot157^2\cdot19183^2)$,  giving $7^3\mid N$, contradicting $7^2\|N$.\hfill \qed
\proclaim{Theorem 5}
If $N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_k^{2\beta_k}$ is an odd 3-imperfect number then we cannot have $\beta_1=\beta_2=2$ and $\beta_i=1$ for all $i$, $3\le i\le k$.
\endproclaim
\smallskip\noindent{\it Proof.}\quad
First, suppose that $3^4\|N$. Then (as we cannot have $3\mid\Phi_5(q)=\rho(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\equiv2\pmod3$ (and thus $3\|\rho(p_i^2)$); furthermore (letting $p_1=3$) we have $p_3^2p_4^2p_5^2\mid\rho(p_2^4)$ as it is impossible by Lemma~1 to have $p_i\mid\Phi_3(q)=\rho(q^2)$ for any prime $q$, $3\le i\le5$ (and, $\rho(3^4)=61$). Now the factorizations of $\rho(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 $\rho(3^4)=61$, we see that $61\mid N$ and hence $61^2\|N$. Then $\rho(61^2)=7\cdot523$ so that $7^2\cdot523^2\|N$, $\rho(7^2\cdot523^2)=7\cdot43^2\cdot907$ so that $43^2\|N$, $\rho(43^2)=13\cdot139$ so that $13^2\|N$, $\rho(13^2)=157$ so that $157^2\|N$, and $\rho(157^2)=7\cdot3499$. But $7^3\mid\rho(61^2\cdot523^2\cdot157^2)$ implies $7^3\mid 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\equiv2\pmod3$, so that $3\|\rho(p_4^2)$. Then $p_4\mid\rho(p_1^4p_2^4)$, and $\rho(p_1^4p_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\mid\rho(p_2^4)$ or $p_2\mid\rho(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: $\rho(3^2)=7$, $\rho(7^2)=43$, $\rho(43^2)=13\cdot139$, $\rho(13^2\cdot139^2)=157\cdot19183$, so we have $7^3\mid\rho(3^2\cdot157^2\cdot19183^2)$, implying $7^3\mid N$, and yet $7^2\|N$. This contradiction completes the proof.\hfill \qed
\smallskip
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^{\alpha}p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_k^{2\beta_k}$, where $q\equiv\alpha\equiv1\pmod4$. Steuerwald~\cite{18} showed that we cannot have $\beta_i=1$ for $1\le i\le k$. McDaniel~\cite{15} showed that we cannot have $\beta_i\equiv1\pmod3$ for $1\le i\le k$. Cohen and Williams~\cite{6} showed that we cannot have $\beta_1=5$ or~6 with $\beta_i=1$ for $2\le i\le k$. Brauer~\cite{3} showed that we cannot have $\beta_1=2$ and $\beta_i=1$ for $2\le i\le k$. Kanold~\cite{13} showed that we cannot have $\beta_1=3$, $\beta_2=2$, and $\beta_i=1$ for $3\le i\le k$. Iannucci and Sorli~\cite{11} showed that if $\beta_i\equiv1\pmod3$ or $2\pmod5$ for all $i$ then $3\nmid n$. 
\vskip 30pt 
%
%
%   omega(N)\ge18 . . . 
%
%
\subhead \nofrills{\bf 5. The Number of Distinct Prime Divisors of an Odd 3-Imperfect Number}\endsubhead

\noindent
With $N$ given as in (8), we say that $\omega(N)=k$. It is immediate from~(2) and~(4) that $\omega(N)\ge16$ since
$$\frac43\cdot\frac65\cdot\frac87\cdot\frac{12}{11}\cdot\frac{14}{13}\cdot\frac{18}{17}\cdot\frac{20}{19}\cdot\frac{24}{23}\cdot\frac{30}{29}\cdot\frac{32}{31}\cdot\frac{38}{37}\cdot\frac{42}{41}\cdot\frac{44}{43}\cdot\frac{48}{47}\cdot\frac{54}{53}<3\,.$$
In this section we increase this lower bound of~16:
\proclaim{Theorem 6}
An odd 3-imperfect number contains at least 18 distinct prime divisors.
\endproclaim
\smallskip\noindent{\it Proof.}\quad
Suppose $\omega(N)=16$. Write
$$N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_{16}^{2\beta_{16}}\,,\qquad p_1<p_2<\cdots<p_{16}\,.$$
It is obvious that $p_1=3$ (as $N=3\rho(N)$). From (2) and (4) it follows that $p_2=5$, $p_3=7$, \dots, $p_{10}=31$, since
$$\frac43\cdot\frac65\cdot\frac87\cdot\frac{12}{11}\cdot\frac{14}{13}\cdot\frac{18}{17}\cdot\frac{20}{19}\cdot\frac{24}{23}\cdot\frac{30}{29}\cdot\frac{38}{37}\cdot\frac{42}{41}\cdot\frac{44}{43}\cdot\frac{48}{47}\cdot\frac{54}{53}\cdot\frac{60}{59}\cdot\frac{62}{61}<3\,.$$
Similarly $p_{11}$ is either 37 or 41 because
$$\frac43\cdot\frac65\cdot\frac87\cdot\frac{12}{11}\cdot\frac{14}{13}\cdot\frac{18}{17}\cdot\frac{20}{19}\cdot\frac{24}{23}\cdot\frac{30}{29}\cdot\frac{32}{31}\cdot\frac{44}{43}\cdot\frac{48}{47}\cdot\frac{54}{53}\cdot\frac{60}{59}\cdot\frac{62}{61}\cdot\frac{68}{67}<3\,.$$
The same type of argument then yields $41\le p_{12}\le43$, $43\le p_{13}\le53$, $47\le p_{14}\le61$, $53\le p_{15}\le83$, and $59\le p_{16}\le 257$. In particular, no prime divisor of $N$ exceeds 257.

Since $17\mid N$, we have by~(9) that $17\mid\Phi_{2d}(p_i)$ for some $i$, where $d\mid2\beta_i+1$. By Lemma~1, we have $d=17^{\gamma}$, where $\gamma>0$ (as $d>1$), and $p_i\equiv-1\pmod{17}$. Since $2\cdot17^{\gamma}\mid2\beta_i+1$, we have by~(6) that $\Phi_{34}(p_i)\mid N$. There are only two primes not exceeding 257 which are congruent to $-1$ modulo~17, namely 67 and 101. But $\Phi_{34}(67)$ and $\Phi_{34}(101)$ each contain a prime divisor which exceeds 257. This contradiction shows that $\omega(N)\ge17$.

Now suppose that $\omega(N)=17$. Write
$$N=p_1^{2\beta_1}p_2^{2\beta_2}\cdots p_{17}^{2\beta_{17}}\,,\qquad p_1<p_2<\cdots<p_{17}\,.$$
Applying (2) and (4) as above, we may deduce that $p_1=3$, $p_2=5$, \dots, $p_7=19$, and that $p_{16}\le521$. Hence at most one prime divisor of $N$ may exceed 521.

Again, we have $17\mid N$, so as above we have $17\mid\rho(p_i^{2\beta_i})$ for some $i$, where $p_i\equiv-1\pmod{17}$, and we also have $\Phi_{34}(p_i)\mid N$. There are exactly five primes $q\le521$ for which $q\equiv-1\pmod{17}$: 67, 101, 271, 373, and 509. In each case, $\Phi_{34}(q)$ contains at least two prime divisors which exceed 521. Therefore we must have $p_{17}\equiv-1\pmod{17}$ and (since $N$ is a square) $17^2\mid\rho(p_{17}^{2\beta_{17}})$; by~(7) this implies $17^2\mid2\beta_{17}+1$. Thus by~(6) we have $\Phi_{578}(p_{17})\mid N$, and hence by Lemma~3 we have a prime $q\mid N$ such that $q\equiv1\pmod{578}$. Since $q\ne p_{17}$, we have two prime divisors of $N$ exceeding 521. This contradiction completes the proof of the theorem.\hfill \qed
\smallskip
Analogously, Hagis~\cite{8} and Chein~\cite{4} independently showed that if $n$ is an odd perfect number then $\omega(n)\ge8$. Reidlinger~\cite{17}, Kishore~\cite{14}, and Hagis~\cite{9} independently showed that an odd 3-perfect number must have at least~12 distinct prime factors.
\vskip 30pt 
%
%
%
%   Algorithm
%
%
%
\subhead \nofrills{\bf 6. The Largest Prime Divisor of an Odd 3-Imperfect Number}\endsubhead

\noindent
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:
\proclaim{Theorem 7}
The largest prime divisor of an odd 3-imperfect number exceeds $10^9$.
\endproclaim
\smallskip\noindent{\it Proof.}\quad
First we describe the algorithm by which the proof is carried out. For a natural number $M$, let ${\Cal P}(M)$ denote the statement, ``The largest prime divisor of $N$ exceeds $M$.'' We assume, for the sake of contradiction, that $p\le M$ for all prime divisors $p$ of $N$. Then (say) $3^{2\beta}\|N$ and so by~(9), $\Phi_{2r}(3)\mid N$ for all prime divisors $r$ of $2\beta+1$ (all such $r$ being odd). By Lemma~3, we must have $r<M/2$ for all such $r$ (otherwise $\Phi_{2r}(3)$ is divisible by a prime exceeding $M$). Therefore it suffices to show that the assumption $\Phi_{2r}(3)\mid N$ leads to a contradiction for all odd primes $r<M/2$. Let $L_m(p)$ denote the largest prime divisor of $\Phi_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\mid N$ before we can finish disproving $\Phi_{2r}(3)\mid N$.

In disproving $\Phi_{2r}(3)\mid N$, we take the odd primes $r<M/2$ in ascending order, beginning with $r=3$. Thus we begin by assuming $\Phi_6(3)\mid N$. Since $L_6(3)=7$, we must then disprove $7\mid N$ before proceeding to $r=5$. To disprove $7\mid N$, we must show that $\Phi_{2r}(7)\mid 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\mid N$, and so on.

In this way we generate a tree. At the root of the tree is the supposition $3\mid 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\mid 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\mid N$, where $p=L_{2r}(q)$, and so forth.

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

We illustrate this for the proof of ${\Cal P}(10^3)$:
\vskip 12pt
\settabs 13\columns
\+ 0: &&&&$ 3 \overset 3 \to\longrightarrow 7 $\cr
\+ 1: &&&&&$ 7 \overset 3 \to\longrightarrow 43 $\cr
\+ 2: &&&&&&$ 43 \overset 3 \to\longrightarrow 139 $\cr
\+ 3: &&&&&&&$ 139 \nmid N$\cr
\+ 2: &&&&&&$ 43 \nmid N$\cr
\+ 1: &&&&&$ 7 \overset 5 \to\longrightarrow 191 $\cr
\+ 2: &&&&&&$ 191 \nmid N$\cr
\+ 1: &&&&&$ 7 \overset 7 \to\longrightarrow 911 $\cr
\+ 2: &&&&&&$ 911 \nmid N$\cr
\+ 1: &&&&&$ 7 \nmid N$\cr
\+ 0: &&&&$ 3 \overset 5 \to\longrightarrow 61 $\cr
\+ 1: &&&&&$ 61 \nmid N$\cr
\+ 0: &&&&$ 3 \overset 7 \to\longrightarrow 547 $\cr
\+ 1: &&&&&$ 547 \nmid N$\cr
\+ 0: &&&&$ 3 \overset 11 \to\longrightarrow 661 $\cr
\+ 1: &&&&&$ 661 \nmid N$\cr
\+ 0: &&&&$ 3 \nmid N$\cr
\vskip 12pt\noindent
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 $\Phi_{97}(3)$ has any prime divisors $q>10^3$. By Lemma~1, $q\equiv1\pmod{194}$, so it suffices merely to test all such primes $q<10^3$ to see if $3^{97}\equiv1\pmod q$. Thus we obtain the product, say $R$, of all primes less than $10^3$ which divide $\Phi_{97}(3)$. If $\ln R<96\ln3$, then $\Phi_{97}(3)$ must contain a prime divisor greater than $10^3$. 

We then generated the proof of ${\Cal P}(10^9)$, which produced 139 lines of output (as compared to the 17 lines above taken above for ${\Cal 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 ${\Cal P}(10^9)$:
\vskip 12pt
\settabs 13\columns
\+ 0: &&$ 3 \overset 3 \to\longrightarrow 7 $\cr
\+ 1: &&&$ 7 \overset 3 \to\longrightarrow 43 $\cr
\+ 2: &&&&$ 43 \overset 3 \to\longrightarrow 139 $\cr
\+ 3: &&&&&$ 139 \overset 3 \to\longrightarrow 19183 $\cr
\+ 4: &&&&&&$ 19183 \overset 3 \to\longrightarrow 2766679 $\cr
\+ 5: &&&&&&&$ 2766679 \nmid N$\cr
\+ 4: &&&&&&$ 19183 \nmid N$\cr
\+ 3: &&&&&$ 139 \overset 5 \to\longrightarrow 1201 $\cr
\+ 4: &&&&&&$ 1201 \overset 3 \to\longrightarrow 1441201 $\cr
\+ 5: &&&&&&&$ 1441201 \overset 3 \to\longrightarrow 14623159 $\cr
\+ 6: &&&&&&&&$ 14623159 \overset 3 \to\longrightarrow 5800159 $\cr
\+ 7: &&&&&&&&&$ 5800159 \nmid N$\cr
\+ $\vdots$ &&&&$\vdots$&&&&&$\vdots$\cr
\+ $\vdots$ &&&&$\vdots$&&&&&$\vdots$\cr

\+\cr

\+ 3: &&&&&$ 116243551 \overset 3 \to\longrightarrow 75833059 $\cr

\+ 4: &&&&&&$ 75833059 \nmid N$\cr

\+ 3: &&&&&$ 116243551 \nmid N$\cr

\+ 2: &&&&$ 1041421 \nmid N$\cr

\+ 1: &&&$ 1021 \nmid N$\cr

\+ 0: &&$ 3 \overset 19 \to\longrightarrow 101917 $\cr

\+ 1: &&&$ 101917 \nmid N$\cr

\+ 0: &&$ 3 \overset 29 \to\longrightarrow 5385997 $\cr

\+ 1: &&&$ 5385997 \nmid N$\cr

\+ 0: &&$ 3 \overset 37 \to\longrightarrow 56737873 $\cr

\+ 1: &&&$ 56737873 \nmid N$\cr

\+ 0: &&$ 3 \nmid N$\cr

\smallskip\noindent

As the desired contradiction has been obtained, the proof is complete.\hfill \qed

\smallskip

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

\vskip 30pt 

%

%

%

%   Upper bound on v_3(N)

%

%

%

\subhead \nofrills{\bf 7. A General Result}\endsubhead



\noindent

In this section we give an upper bound on $v_3(N)$
which depends only on $\omega(N)$: 

\proclaim{Theorem 8}
If $N$ is an odd 3-imperfect
number then 
$$v_3(N)\le1+\left({{\omega(N)-1}\over2}\right)^2.$$

\endproclaim

\smallskip\noindent{\it Proof.}\quad
We may write
$$N=3^{2\alpha}\prod_{i=1}^{\mu}p_i^{2a_i}\prod_{j=1}^{\nu}q_j^{2b_j},\tag{10}$$
where $p_i\equiv1\pmod3$ for all $i$ and $q_j\equiv2\pmod3$ for
all $j$. Neither of the products $\prod_{i=1}^{\mu}p_i^{2a_i}$ nor
$\prod_{j=1}^{\nu}q_j^{2b_j}$ are empty: in other words $\mu>0$
and $\nu>0$. For, $3\mid\rho(N)$, and by (7)
$v_3(\rho(N))=v_3(\prod_{j=1}^{\nu}q_j^{2b_j})$, and so $\nu>0$.

Since $3\mid\rho(q_j^{2b_j})$ for some $q_j^{2b_j}\|N$, we have by
(7) $3\mid2b_j+1$. Thus by (6)
$\Phi_{2\cdot3^{\gamma}}(q_j)\mid\rho(N)$ for some $\gamma>0$. By
Lemma~3 $\Phi_{2\cdot3^{\gamma}}(q_j)\mid\rho(N)$ is divisible by a
prime which is congruent to~1 modulo~3, and so $\mu>0$.



As in the preceding paragraph, we apply (7) and obtain
$$v_3(\rho(N))=\sum_{j=1}^{\nu}v_3(2b_j+1).$$

Let
$$\gamma=\max_{1\le j\le\nu}v_3(2b_j+1).$$
Then by (6), for some $j$ we have
$$\Phi_{2\cdot3}(q_j)\Phi_{2\cdot3^{2}}(q_j)\cdots\Phi_{2\cdot3^{\gamma}}(q_j)\mid\rho(N),\tag{11}$$
and by Lemmas~2 and~3 the product above in (11) contains at
least $\gamma$ distinct primes all congruent to~1 modulo~3.
Therefore $\mu\ge\gamma$.



Suppose $\omega(N)=k$. Then as in (10) we have $k=1+\mu+\nu$.
Since $\mu\ge\gamma$ we have
$$\nu\le k-1-\gamma.\tag{12}$$
Now
$$2\alpha-1=v_3(\rho(N))=\sum_{j=1}^{\nu}v_3(2b_j+1)\le\nu\gamma.$$
Combining this with (12) yields
$$2\alpha\le 1+\gamma(k-1-\gamma).\tag{13}$$

The right-hand side of (13) is maximized when $\gamma=(k-1)/2$ and so we have
$$2\alpha\le 1+\left({{k-1}\over2}\right)^2,$$
and this completes the proof.\hfill \qed

\vskip 30pt 

%

%

%

%   Conclusion

%

%

%

\subhead \nofrills{\bf 8. Concluding Remarks}\endsubhead



\noindent
Martin obviously considered $\rho$ as a variation of $\sigma$; he actually used the symbol $\widetilde{\sigma}$ by which to refer to $\rho$ (this is also mentioned in Guy~\cite{7}, p.72). However, it may be more precise to think of $\rho$ as a generalization of Euler's totient function $\phi$, since
$$\rho(n)=\sum\Sb 1\le k\le n\\(k,n)\in S\endSb1,$$
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 $\sigma$ 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 ${\Cal 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\nmid n$.\vskip 30pt 
%\subhead \nofrills{\bf References}

\Refs 
\ref\no 1
\paper Problem 99:08 from the Western Number Theory Conference.
\by Compiled by G. Myerson, Macquarie University, Sydney
\endref
\ref\no 2
\by A. Bang
\paper Taltheoretiske Unders\o gelser
\jour Tidsskrift Math.
\vol 5\issue IV
\pages 70--80, 130--137
\yr 1886
\endref
\ref\no 3
\by A. Brauer
\paper On the nonexistence of odd perfect numbers of the form $p^{\alpha}q_1^2q_2^2\cdots q_{t-1}^2q_t^4$
\jour Bull. Amer. Math. Soc.
\vol 49
\pages 712--718
\yr 1943
\endref
\ref \no 4 \by E. Z. Chein\jour Ph.D. Thesis,
Pennsylvania State University \yr 1979\endref
\ref\no 5
\by G.L. Cohen and P. Hagis
\paper Results concerning odd multiperfect numbers
\jour Bull. Maylaysian Math. Soc.
\vol 8 \yr 1985 \pages 23--26
\endref
\ref\no 6
\by G. Cohen and R. Williams
\paper Extensions of some results concerning odd perfect numbers
\jour J. Fibonacci Quart.
\vol 23
\pages 70--76
\yr 1985
\endref
\ref\no 7
\by R. Guy
\book Unsolved Problems in Number Theory (Third Edition)
\publ Springer-Verlag
\yr 2004
\endref
\ref \no 8 
\by P. Hagis \pages 1027--1032
\paper Outline of a proof that every odd perfect number has at
least eight prime factors \yr 1980 \vol 35
\jour Math. Comp. 
\endref
\ref\no 9
\by P. Hagis
\paper A new proof that every odd triperfect number has at least twelve prime factors
\jour Contemp. Math.
\vol 143
\yr 1993 
\pages 445--450
\endref
\ref\no 10
\by G. Hardy and E. Wright
\book An Introduction to the Theory of Numbers
\publ Oxford University Press
\yr 1979
\pages 111--118
\endref
\ref\no 11
\by D. Iannucci and R. Sorli
\paper On the total number of prime factors of an odd perfect number
\jour Math. Comp.
\vol 72
\yr 2003
\pages 2077--2084
\endref
\ref\no 12
\by P. Jenkins
\paper Odd perfect numbers have a prime factor exceeding $10^7$
\jour Math. Comp.
\vol 72
\yr 2003
\pages 1549--1554
\endref
\ref\no 13
\by H.-J. Kanold \pages 129--146
\paper S\"atze \"uber kreisteilungspolynome und ihre andwendungen
auf einiger zahlentheoretische problem II
\yr 1950 \vol 188
\jour J. Reine Angew. Math.
\endref
\ref\no 14
\by M. Kishore
\paper Odd triperfect numbers are divisible by twelve distinct prime factors
\jour J. Austral. Math. Soc.
\vol 42
\yr 1987
\pages 173--182
\endref
\ref\no 15
\by W. McDaniel \pages 52--53
\paper The nonexistence of odd perfect numbers of a certain form
\yr 1970\vol 21
\jour Arch. Math. 
\endref
\ref\no 16
\by T. Nagell
\book Introduction to Number Theory
\publ AMS Chelsea Publishing
\publaddr Providence, RI
\yr 1981
\endref
\ref\no 17
\by H. Reidlinger
\paper \"{U}ber ungerademehrfach volkommene Zahlen
\jour Osterreichische Akad. Wiss.\break Math.-Natur.
\vol 192 \yr 1983 \pages 237--266
\endref
\ref \no 18 
\by R. Steuerwald \pages 68--73
\paper Versch\"{a}rfung einer notwendigen Bedingung f\"{u}r die
Existenz einer ungeraden vollkommenen Zahl
\yr 1937
\jour S.-B. Math.-Nat. Abt. Bayer. Akad. Wiss. 
\endref
\endRefs

\enddocument





