# Prove that if $F_n$ is highly abundant, then so is $n$.

Define $F_n$ to be the $n$th Fibonacci number, define $\sigma(n)$ to be the sum of the divisors of $n$, and call $n$ highly abundant if and only if $\sigma(n)>\sigma(m) \hspace{3mm} \forall m<n$.

Prove that if $F_q$ is highly abundant, then so is $q$ - analogous to the property that whenever $F_p$ is prime, $p$ is prime or $4$ - or find a counterexample.

The sequence of highly abundant Fibonacci numbers begins

$1, 1, 2, 3, 8, 144$

and the sequence of their indices begins

$1, 2, 3, 4, 6, 12$

These are the only terms that I know of, but there may be others. Our search will be greatly aided by the fact that the Fibonacci numbers are a divisibility sequence - meaning that $F_a \mid F_b$ if and only if $a \mid b$ - if various things are true of the highly abundant numbers. I don't wish to make the proof of any of the following the point of this post, but information on highly abundant numbers seems to be highly deficient, so if upon further inspection I don't find recorded proofs or counterexamples and none are presented in the comments here, then I may make them the topic of a future question.

(1) - Every highly abundant number greater than $3$ is even

If true, then the index of every highly abundant Fibonacci number greater than $3$ must be divisible by $3$, since $F_3=2$.

(2) - Every highly abundant number greater than $16$ is divisible by $6$ or $10$

If true, then the index of every highly abundant Fibonacci number greater than $16$ is divisible by $12$ or $15$, since $F_{12}=144$ and $F_{15}=610$ are the smallest Fibonacci numbers that are divisible by $6$ and $10$ respectively.

Update: @Daniel Fischer has posted a proof below of (1) and the stronger statement than (2) that every highly abundant number greater than $20$ is divisible by $6$. (3) probably wouldn't give us a better restriction on the index than this without considerably more work outside the scope of this problem, but stronger statements such as $\forall k > 3024$ such that $k$ is highly abundant, $60 \mid k$, seem within reach, which, for example, would imply that any highly abundant Fibonacci number not in the list above (since I've checked every value below this limit) is divisible by $F(60)=1548008755920$, the first Fibonacci number divisible by $60$.

(3) - Every highly abundant number other than $3$ and $10$ is also practical (every smaller number can be represented as a sum of distinct divisors of the number)

If true, then the index of every highly abundant Fibonacci number greater than $10$ is divisible by $6$, since every practical number is divisible by $4$ or $6$, and $F_6=8$ and $F_{12}=144$ are the smallest Fibonacci numbers divisible by these two numbers respectively.

If any further values are found I'll add them to the sequences.

I'm still working on the practicality, but here are proofs of (1) and a stronger form of (2):

We will often use the

Lemma: For all $m,\,n$, we have $\sigma(m)\cdot\sigma(n) \geqslant \sigma(m\cdot n)$ (with equality if and only if $m$ and $n$ are coprime).

Proof: We assume the coprime case known, so it remains to see that $\sigma(p^k)\sigma(p^r) > \sigma(p^{k+r})$ for $k,\,r > 0$. But

\begin{align} (p-1)^2\left(\sigma(p^k)\sigma(p^r) - \sigma(p^{k+r})\right) &= (p^{k+1}-1)(p^{r+1}-1) - (p^{k+r+1}-1)(p-1)\\ &= p^{k+r+2}-p^{k+1}-p^{r+1}+1-p^{k+r+2}+p^{k+r+1}+p-1\\ &= p^{k+r+1}-p^{k+1}-p^{r+1}+p\\ &= p(p^k-1)(p^r-1)\\ &> 0. \end{align}

Now we start investigating highly abundant numbers:

Lemma: Let $n > 3$ be an odd number. Then $n$ is not highly abundant.

Proof: Let $p > 3$ prime. Then $$\sigma(p-1) \geqslant (p-1) + \frac{p-1}{2} + 1 = p + \frac{p-1}{2} \geqslant p + 2 > p+1 = \sigma(p),$$ hence $p$ is not highly abundant.

Further, $$\sigma(p^2-1) \geqslant (p^2-1) + \frac{p^2-1}{2} + 2 + 1 = p^2 + \frac{p^2+1}{2} + 1 > p^2+p+1 = \sigma(p^2)$$ and hence $p^2$ is not abundant either.

Let $3 \leqslant p < q$ with distinct primes $p,q$. Then \begin{align} \sigma(pq-1) &\geqslant (pq-1) + \frac{pq-1}{2} + 2 + 1\\ &= pq + \frac{pq+1}{2} +1\\ &= pq+p+q+1 + \frac{pq-2p-2q+1}{2}\\ &= pq+p+q+1 + \frac{(p-2)(q-2)-3}{2}\\ &\geqslant pq+p+q+1 = \sigma(pq). \end{align}

If $5 \mid n$, then $m = 4\frac{n}{5} < n$ and $\sigma(m) = 7\sigma(n/5) > 6\sigma(n/5) \geqslant \sigma(n)$, hence $n$ is not highly abundant. If $9\mid n$, then $m = 8\frac{n}{9} < n$ and $\sigma(m) = 15\sigma(n/9) > 13\sigma(n/9) \geqslant \sigma(n)$, so $n$ is not highly abundant.

So only numbers with at least two prime factors $\geqslant 7$ and at most one factor $3$ remain. Let $p > 5$ a prime dividing $n$. Let $2^a < p < 2^{a+1}$. If $p < 2^{a+1}-1$, then $m = 2^a\frac{n}{p} < n$ and $\sigma(m) = (2^{a+1}-1)\sigma(n/p) \geqslant (p+1)\sigma(n/p) \geqslant \sigma(n)$, so $n$ is not highly abundant. If $p = 2^{a+1}-1$, then $m = 2^{a-1}\cdot 3\cdot\frac{n}{p} < n$, and

\begin{align} \sigma(m) &= (2^a-1)\cdot 4\cdot \sigma(n/p)\\ &= (2^{a+2}-4)\sigma(n/p)\\ &> 2^{a+1}\sigma(n/p)\\ &\geqslant (p+1)\sigma(n/p) \geqslant \sigma(n) \end{align}

if $3\not\mid n$, and for $n = 3\cdot k$, we have

\begin{align} \sigma(m) &= (2^a-1)\cdot 13 \cdot \sigma(k/p)\\ &= (2^{a+3} + 5\cdot 2^a - 13)\sigma(k/p)\\ &\geqslant 2^{a+3}\sigma(k/p)\\ &= 4(p+1)\sigma(k/p)\\ &\geqslant \sigma(n). \end{align}

By similar methods we prove the next

Lemma: Let $n > 20$ be highly abundant. Then $n \equiv 0 \pmod{6}$.

Proof: First we note that $2^k$ is highly abundant if and only if $k \leqslant 4$. For if $k \geqslant 5$, then $\sigma(2^{k-4}\cdot 15) = (2^{k-3}-1)\cdot 24 = 3\cdot 2^k - 24 = (2^{k+1}-1) + 2^k-23 > \sigma(2^k)$.

So let $n = 2^k\cdot m > 20$ with $k\geqslant 1$, odd $m > 1$, and $m \not\equiv 0\pmod{3}$. We show that $n$ is not highly abundant.

Now if $n$ has a prime factor $p > 5$, let $3^a < p < 3^{a+1}$. Since $p$ and $3^{a+1}$ are both odd, we have $3^{a+1}-1 \geqslant p+1$. If $p/3 < 3^a < p/2$, then

\begin{align} \sigma(2^{k+1}3^am/p) &= (2^{k+2}-1)\frac{3^{a+1}-1}{2}\sigma(m/p)\\ &> (2^{k+1}-1)(p+1)\sigma(m/p)\\ &\geqslant \sigma(2^km) = \sigma(n). \end{align} If $3^a = \frac{p+1}{2}$, then $a \geqslant 2$, $p \geqslant 17$, $3^{a-1}5n/p < n$ and \begin{align} \sigma(3^{a-1}5n/p) &\geqslant \frac{3^a-1}{2}\cdot 5\cdot\sigma(n/p)\\ &= 5\frac{p-1}{4}\sigma(n/p)\\ &\geqslant (p+1)\sigma(n/p) \geqslant \sigma(n). \end{align}

If $(p+1)/2 < 3^a < 3p/4$, then $a \geqslant 2$, and \begin{align} \sigma(2^{k+2}3^{a-1}m/p) &= (2^{k+3}-1)\frac{3^a-1}{2}\sigma(m/p)\\ &\geqslant (2^{k+3}-1)\frac{p+1}{4}\sigma(m/p)\\ &> (2^{k+1}-1)(p+1)\sigma(m/p)\\ &\geqslant (2^{k+1}-1)\sigma(m) = \sigma(n). \end{align}

If $\frac{3p}{4} < 3^a < p$, then $p \geqslant 11$ and \begin{align} \sigma(3^an/p) &= \frac{3^{a+1}-1}{2}\sigma(n/p)\\ &\geqslant \frac{9p-1}{8}\sigma(n/p)\\ &> (p+1)\sigma(n/p) \geqslant \sigma(n). \end{align}

So the case $n = 2^k\cdot 5^m$ remains. If $m \geqslant 2$, then \begin{align} \sigma(2^{k+3}\cdot 3\cdot 5^{m-2}) &= (2^{k+4}-1)\cdot 4 \cdot \sigma(5^{m-2})\\ &= \left(32(2^{k+1}-1) + 28\right)\sigma(5^{m-2})\\ &> (2^{k+1}-1)31\sigma(5^{m-2}) \geqslant \sigma(2^k5^m). \end{align}

Finally, for $n = 2^k\cdot 5$ with $k \geqslant 3$, we have $$\sigma(2^{k-1}\cdot 3^2)-\sigma(2^k\cdot 5) = 13(2^k-1) - 6(2^{k+1}-1) = 2^k - 7 > 0,$$

and the proof is complete.

Next we will prove the

Lemma: If $n > 630$ is highly abundant, then $n \equiv 0 \pmod{12}$.

Proof: We already know that $n$ is not highly abundant if $n \not\equiv 0 \pmod{6}$, so let $n \equiv 6 \pmod{12}$. Let $n = 2\cdot 3^a\cdot m$, with $\gcd(m,6) = 1$. We have, for $a \geqslant 2$,

\begin{align} 31\cdot \frac{3^{a-1}-1}{2} &> 3\cdot\frac{3^{a+1}-1}{2}\\ \iff 31\cdot 3^{a-1} - 31 &> 27\cdot 3^{a-1} - 3\\ \iff 4\cdot 3^{a-1} &> 28\\ \iff 3^{a-1} &> 7, \end{align}

so if $a \geqslant 3$, then $n$ is not highly abundant, since $\sigma(2^4\cdot 3^{a-2}m) > \sigma(2\cdot 3^am)$, hence in the following we assume $a \in \lbrace 1,\, 2\rbrace$.

If $5^2 \mid m$, then

\begin{align} \sigma(2^43^{a+1}m/5^2) &= 31\frac{3^{a+2}-1}{2}\sigma(m/5^2)\\ &> 3\frac{3^{a+1}-1}{2}\cdot 31\sigma(m/5^2)\\ &\geqslant 3\frac{3^{a+1}-1}{2}\sigma(m) = \sigma(2\cdot 3^am) = \sigma(n), \end{align} so $n$ is not highly abundant. If $7^2 \mid m$, then \begin{align} \sigma(2^53^{a+1}m/7^2) &= 63\frac{3^{a+2}-1}{2}\sigma(m/7^2)\\ &> 3\frac{3^{a+1}-1}{2}\cdot 63\sigma(m/7^2)\\ &> 3\frac{3^{a+1}-1}{2}\cdot 57\sigma(m/7^2)\\ &\geqslant 3\frac{3^{a+1}-1}{2}\sigma(m) = \sigma(n), \end{align} so $n$ is not highly abundant.

It remains to show that if $n$ has a prime divisor $p > 7$, then $n$ is not highly abundant, where we can assume that neither $5^2$ nor $7^2$ divides $n$.

Let $2^c < p < 2^{c+1}$. If $2^c > \frac{3p+4}{4}$, then

$$\sigma(2p) = 3(p+1) \leqslant 2^{c+2}-1 = \sigma(2^{c+1}),$$ hence $\sigma(n) \leqslant \sigma(2^cn/p)$, and $n$ is not highly abundant.

If $\frac{2p}{3} < 2^c \leqslant \frac{3p+4}{4}$, and $p > 15$, then $2^{c-2}\cdot 5 < p$ and writing $m = 5^b\cdot r$ with $r \not\equiv 0 \pmod{5}$, we obtain \begin{align} \sigma(2^{c-1}5^{b+1}) - \sigma(2\cdot5^bp) &= (2^c-1)\frac{5^{b+2}-1}{4} - 3\frac{5^{b+1}-1}{4}(p+1)\\ &\geqslant \frac{2p-1}{3}\cdot\frac{5^{b+2}-1}{4} - 3\frac{5^{b+1}-1}{4}p - 3\frac{5^{b+1}-1}{4}\\ &= \left(\frac{2(5^{b+2}-1)}{12} -\frac{9(5^{b+1}-1)}{12}\right)p\\ &\qquad - \left(\frac{9(5^{b+1}-1)}{12}+\frac{5^{b+2}-1}{12}\right)\\ &= \frac{5^{b+1}+7}{12}p - \frac{14\cdot 5^{b+1}-10}{12} > 0, \end{align} hence $\sigma(n) \leqslant \sigma(2^{c-2}5n/p)$, and $n$ is not highly abundant.

If $\frac{p}{2} < 2^c < \frac{2p}{3}$, and $2^{c+1}-1 \geqslant p+1$, we have

$$\sigma(2^c\cdot 3^{a+1}) = (2^{c+1}-1)\frac{3^{a+2}-1}{2} > (p+1)\cdot 3 \frac{3^{a+1}-1}{2} = \sigma(2\cdot3^ap),$$ and if $2^{c+1}-1 = p$, then \begin{align} \sigma(2^c\cdot 3^{a+1}) -\sigma(2\cdot3^ap) &= (2^{c+1}-1)\frac{3^{a+2}-1}{2} - 3\frac{3^{a+1}-1}{2}(p+1)\\ &= p - 3\frac{3^{a+1}-1}{2}\\ &\geqslant p - 39. \end{align}

The remaining cases are $p = 31$, when $\sigma(30n/31) > \sigma(n)$ is easily verified, and $p = 11$, when $\sigma(10n/11) > \sigma(n)$ because $n$ is not divisile by $5^2$.

The maximal highly abundant number $\equiv 6 \pmod{12}$ is hence $2\cdot 3^2\cdot 5\cdot 7 = 630$.

• Thanks for working all this out. I believe the general statement holds that $\forall k \in \Bbb Z^+ \hspace{1mm} \exists A; \hspace{1mm} k|a(n) \hspace{2mm} \forall a(n)>A$, where $a(n)$ is the $n$th highly abundant number and $A$ is highly abundant. This is based on the first 10,000 values, from which it appears that when $k=5,10,20,30,$ or $60, A=3024$. $10$ and $30$ would follow from your lemmas and proof of the case $k=5$, while $20$ and $60$ follow by also proving that for $k=4,A=630$. Can your proof be adapted for larger primes and prime powers? – Jaycob Coleman Aug 17 '13 at 6:47
• I think it can be shown in pretty much the same way that all highly abundant numbers larger than $630$ are divisible by $12$, and all larger than 3024 divisible by $5$. It gets messier for each prime factor you add, of course, and I don't think it would be feasible to prove the general statement that for each $k$ all large enough highly abundant numbers are multiples of $k$ in that way (if that is true, which I'm not sure about). I don't have much time today, but I'll look about $12$ and $5$ tomorrow. – Daniel Fischer Aug 17 '13 at 9:13
• Likely pairs $(k,A)$ for some small powers of primes are $(8,540540)$,$(16,1164544781400)$,$(9,8168160)$,$(27,31672512601329600)$,$(25,1226737062541710720)$,$(7,47520)$,$(11,46781280)$,$(13,37067738400)$,$(17,23016885091200)$,$(19,761980038019200)$. Supposing that $k=16,9,5,7,11,$ and $13$ are all correct, any further highly abundant Fibonacci numbers must be divisible by $F_{840}$ since these $A$ are less than $F(60)$ and $840$ is the least common multiple of the indices of the smallest Fibonacci numbers divisible by their respective $k$. – Jaycob Coleman Aug 17 '13 at 12:44
• I've added the proof that all highly abundant numbers $> 630$ are divisible by $4$ (hence by $12$). Working on the others, well, at least some. Not sure how far I'm willing to go. – Daniel Fischer Aug 18 '13 at 20:24

I do not have enough reputation to comment, therefore I put this comment into an answer. 'whenever Fp is prime, so is p' should be 'if $F_p$ is prime, then $p$ is prime or $4$'.