9
$\begingroup$

It is not known if there are infinitely many prime Fibonacci numbers. But can one assert that there is no Fibonacci number >2 that is also highly composite (https://en.wikipedia.org/wiki/Highly_composite_number) - or that there are only finitely many such numbers?

Remarks: As given in http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html, every Fibonacci number bigger than 1 [except F(6)=8 and F(12)=144] has at least one prime factor that is not a factor of any earlier Fibonacci number. So, Fibonacci numbers tend to have large prime factors and it is quite conceivable that none of them are highly composite. However, a few are seen to be semiprimes (https://en.wikipedia.org/wiki/Semiprime). Not sure if the question of whether there are infinitely many Fibonacci semiprimes has been answered.

$\endgroup$
3
  • 2
    $\begingroup$ Highly composite numbers are extremely restricted in their factorization. Every highly composite number $c$ satisfies that its distinct prime factors are the first $k$ distinct prime factors for some $k$. (If a prime $p$ is skipped and the next prime is $q^a$ in the factorization of $c$, then $c\frac{p^a}{q^a}$ has the same number of divisors and is a smaller number.) It seems very likely that 1, 2, 8 and 144 are the only Fibonacci numbers with this property. $\endgroup$
    – JoshuaZ
    Nov 13, 2021 at 13:31
  • $\begingroup$ @JoshuaZ : By "the first $k$ distinct prime factors" do you mean the first $k$ distinct prime numbers? $\endgroup$ Nov 14, 2021 at 23:24
  • $\begingroup$ @MichaelHardy Yes. Poor phrasing on my part. $\endgroup$
    – JoshuaZ
    Nov 14, 2021 at 23:52

1 Answer 1

22
$\begingroup$

The largest highly composite Fibonacci number is $F_{3} = 2$.

If $p$ is a prime number, then either $p \mid F_{p-1}$ (if $p \equiv \pm 1 \pmod{5}$), $p \mid F_{p}$ (if $p = 5$), or $p \mid F_{p+1}$ (if $p \equiv \pm 2 \pmod{5}$). It follows that if $n > 12$ and $p$ is a prime that divides $F_{n}$ and no previous Fibonacci number, then $p \geq n-1$. Assuming $F_{n}$ is highly composite implies that all primes $\leq n-1$ divide $F_{n}$. It follows that $F_{n} \geq \prod_{p \leq n-1} p$. This will lead to a contradiction for $n$ sufficiently large (which boils down to the fact that $\frac{1+\sqrt{5}}{2} < e$).

Let $\theta(x) = \sum_{p \leq x} \log(p)$. The prime number theorem is equivalent to $\theta(x) \sim x$ and Rosser and Schoenfeld showed (see page 70 of their 1962 Illinois Journal of Mathematics paper) that for $x \geq 41$, $\theta(x) \geq x \left(1 - \frac{1}{\log(x)}\right)$. This implies that for $n \geq 42$, we have $$ \log\left(\frac{1}{\sqrt{5}}\right) + n \log\left(\frac{1 + \sqrt{5}}{2}\right) \geq \log(F_{n}) \geq \theta(n-1) \geq (n-1) - \frac{n-1}{\log(n-1)}. $$ For $n \geq 22$, we have $(n-1) - \frac{(n-1)}{\log(n-1)} \geq \frac{2}{3} (n-1)$, which implies that the right hand side of the centered inequality above is greater than the left.

It suffices to check the prime factorization of $F_{n}$ for $n \leq 42$ to verify that $F_{n}$ is not highly composite for $4 \leq n \leq 42$. This can be done easily using the table of Brillhart, Montgomery, and Silverman.

$\endgroup$
7
  • $\begingroup$ Thank you very much Prof Rouse. Hope you could also clarify how many Fibonacci numbers are semiprimes - or have 3 prime factors. $\endgroup$ Nov 14, 2021 at 10:23
  • 4
    $\begingroup$ The question of Fibonacci numbers with few prime factors is much more difficult. Given that the number of positive integers with $k$ prime factors $\leq x$ is asymptotic to $\frac{x (\log \log x)^{k-1}}{(k-1)! \log x}$, it's natural to conjecture that for a fixed positive integer $k$, there are infinitely many primes $p$ so that $F_{p}$ is a product of $k$ distinct primes. Proving anything about this is probably not possible with current technology however. $\endgroup$ Nov 14, 2021 at 21:12
  • $\begingroup$ I know this is a bit imprecise but it would be nice to know some series in this ballpark that is both provably finite AND with a large highest number - the 'series' of highly composite fibonacci numbers is finite but has only 1 entry and that too 2. $\endgroup$ Nov 24, 2021 at 8:51
  • 1
    $\begingroup$ Define $a_{n}$ by $a_{0} = 1$, $a_{1} = 1$ and $a_{n} = 9a_{n-1} + 29a_{n-2}$ for $n \geq 2$. It should be possible to show that the largest highly composite number in the sequence is $a_{6} = 166320$. (None of the terms in this sequence are multiples of $29$.) Theorems (like the 2001 result of Bilu, Hanrot and Voutier) put restrictions on how far out in a Lucas sequence one can find a term without a primitive prime divisor. These theorems simultaneously make it possible to prove there are finitely many highly composite numbers, while also putting a limit on where they can appear. $\endgroup$ Nov 24, 2021 at 23:29
  • $\begingroup$ Thanks again Prof Rouse. I guess sequences like "highly composites sandwiched between twin primes" would be a lot harder to decide. $\endgroup$ Nov 25, 2021 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.