Prove that all practical numbers not of the form $2^n$ are pseudoperfect

204 Views Asked by At

Prove that all practical numbers not of the form $2^n$ are pseudoperfect.

  • practical - $n$ such that every smaller integer is expressible as a sum of distinct divisors of $n$

  • pseudoperfect - $n$ such that $n$ is expressible as a sum of distinct proper divisors of itself

  • almost perfect - $n$ such that the sum of divisors of $n$ is $2n-1$

Srinivasan says that every practical number greater than $2$ is divisible by $4$ or $6$, and this is easy to see, since no subset of divisors will sum to $4$ unless $4$ or $3$ is a divisor, and clearly $2$ divides every practical number $>1$.

It seems that his statement can be generalized with the introduction of a particular subset of the pseudoperfect numbers. Namely, those of the form $2^{\lfloor\log_2p\rfloor}p$ for an odd prime $p$. The generalized statement would be that every practical number greater than $2^k$ is divisible by one of $2^{k+1},2^{\lfloor\log_2p_2\rfloor}p_2,2^{\lfloor\log_2p_3\rfloor}p_3,...,2^{\lfloor\log_2p_{\pi(2^{k+1})}\rfloor}p_{\pi(2^{k+1})} \hspace{2mm}\forall k \in \Bbb N$, where $p_2,p_3,...,p_{\pi(2^{k+1})}$ are the odd primes $\leq 2^{k+1}$. However, in every case, the only exceptions $\leq 2^k$ have been precisely the powers of two up to and including $2^k$. Noting that every multiple of a pseudoperfect number is also pseudoperfect, if both of the previous statements are true in general then it follows that every practical number that isn't a power of two is pseudoperfect. I imagine the proof of the first will involve showing that every sufficiently large (as in $>2^k$) value not dividing one of the corresponding numbers fails to satisfy Stewart's structure theorem.

I define almost perfect numbers above because they are relevant to this result, though to what extent I'm not certain. The only known almost perfect numbers are the powers of two, so every known almost perfect number is practical. While I've seen no evidence that this should be true in general, our result says that if there existed almost perfect numbers of any other form then they could not be practical because a number cannot be both pseudoperfect and almost perfect.

1

There are 1 best solutions below

0
On BEST ANSWER

We prove the

Lemma: Every practical number is either a power of $2$ or pseudoperfect.

by induction on the number of distinct odd prime divisors of $n$.

The first nontrivial case is

$$n = 2^a\cdot p^m$$

with an odd prime $p$ and $a > 0$. By Stewart's structure theorem, we have $p \leqslant \sigma(2^a)+1 = 2^{a+1}$, and since $p$ is odd, $p \leqslant 2^{a+1}-1$, which means we have a representation

$$p = \sum_{j=0}^r 2^{\nu_j}$$

with $0 = \nu_0 < \nu_1 < \dotsc < \nu_r \leqslant a$. Then

$$\begin{align} n &= (2^a-1)\cdot p^m + p\cdot p^{m-1}\\ &= \sum_{k=0}^{a-1} 2^k\cdot p^m + \sum_{j=0}^r 2^{\nu_j}p^{m-1} \end{align}$$

is a representation of $n$ as a sum of distinct proper divisors of $n$.

Now, in the induction step, we can write, when $p$ is the largest prime dividing $n$,

$$n = m\cdot p^k,$$

where $m$ is a practical number that is not a power of $2$, hence pseudoperfect, thus

$$m = \sum_{j=0}^r d_j$$

with distinct proper divisors of $m$. But then

$$n = \sum_{j=0}^r d_j\cdot p^k$$

is a representation of $n$ as the sum of distinct proper divisors of $n$.