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
    Commented 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$ Commented Nov 14, 2021 at 23:24
  • $\begingroup$ @MichaelHardy Yes. Poor phrasing on my part. $\endgroup$
    – JoshuaZ
    Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 25, 2021 at 4:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .