← Back to maths posts

Self-Fibonacci Numbers

For which n does n divide the nth Fibonacci number?

Here’s a seemingly simple question that lacks a clean solution:

For what positive integers \(n\) does \(n\) divide \(F_n\), where \(F_n\) denotes the \(n^{\text{th}}\) Fibonacci number?

According to the On-Line Encyclopedia of Integer Sequences (OEIS), such numbers are called “Self-Fibonacci numbers”: https://oeis.org/A023172. The sequence begins:

1, 5, 12, 24, 25, 36, 48, 60, 72, 96, 108, 120, 125, 144, 168, 180, 192, 216, 240, 288, 300, 324, 336, 360, 384, 432, 480, 504, 540, 552, 576, 600, 612, 625, 648, 660, 672, 684, 720, 768, 840, 864, 900, 960, 972, 1008, 1080, 1104, 1152, 1176, 1200, 1224, 1296, 1320

One approach to this question is as follows:

Let \(\alpha(n)\) be the smallest positive integer \(k\) such that \(n \mid F_k\). Note that if \(n \mid F_k\), then \(n \mid F_{mk}\) for all positive integers \(m\). Therefore, the self-Fibonacci numbers are exactly those for which \(\alpha(n) \mid n\).

This sequence is fascinating, with apparently no simple formula! I explored the following related question:

For what positive integers \(n\) does \(\alpha(n) = n\)?

Here’s the list of such numbers up to 10,000.

vmTheme = Generators.observe(notify => VM.plotting.onThemeChange(notify))
chartColors = VM.plotting.colors(vmTheme)
fibCyclePlot = VM.plotting.persistentPlot({height: "560px"})
fibRatioPlot = VM.plotting.persistentPlot({height: "420px"})

function fibonacciCycle(n) {
  if (n === 1) return 1
  let prev = 0
  let curr = 1
  for (let k = 1; k <= 6 * n; k++) {
    if (curr % n === 0) return k
    const next = (prev + curr) % n
    prev = curr
    curr = next
  }
  return -1
}

fibN = 10000
fibM = 1000

// fibCycles[n - 1] is α(n), for n = 1, ..., fibN.
fibCycles = {
  const cycles = []
  for (let n = 1; n <= fibN; n++) cycles.push(fibonacciCycle(n))
  return cycles
}

fibEqualPoints = {
  const points = []
  for (let n = 1; n <= fibN; n++) {
    if (fibCycles[n - 1] === n) points.push(n)
  }
  return points
}

html`<p><strong>Values of n where α(n) = n (up to ${fibN.toLocaleString()}):</strong><br>${fibEqualPoints.join(", ")}</p>`

This is a much simpler question, and the sequence appears to consist of all numbers that are powers of 5 or 12 times a power of 5. The OEIS entry for this sequence is https://oeis.org/A289586.

ImportantConjecture

The only integers \(n\) such that \(\alpha(n) = n\) are of the form \(5^k\) or \(12 \cdot 5^k\) for some non-negative integer \(k\).

I’m not certain this is true, but it holds for all integers up to 10,000. I’m also interested in understanding the distribution of \(n / \alpha(n)\). When plotting \(n / \alpha(n)\), most values fall above 1, though some are less than or equal to 1.

Below is a table of \(n / \alpha(n)\) for all integers \(n\) up to 10,000. Surprisingly, the most common value is not 1 but \(4/3\).

I wonder what patterns exist in the ratios \(n / \alpha(n)\)…

NoteQuestions

• What is the distribution of the ratios \(n / \alpha(n)\)?

• For every integer \(k\), is there some integer \(n\) such that \(n / \alpha(n) = k\)?

• Can we exploit the fact that

  \[ F_k = \dfrac{1}{\sqrt{5}} \left( \phi^k - \psi^k \right) \]

  where \(\phi = \frac{1 + \sqrt{5}}{2}\) and \(\psi = \frac{1 - \sqrt{5}}{2}\), to find a closed form for \(\alpha(n)\)? We know that \(\mathbb{Z}[\phi]\) is a Euclidean domain so we can have access to number theoretic tools such as divisibility and the Euclidean algorithm.

{
  const xs = []
  const ys = []
  for (let n = 1; n <= fibM; n++) {
    xs.push(n)
    ys.push(fibCycles[n - 1])
  }
  const equal = []
  for (const n of fibEqualPoints) {
    if (n <= fibM) equal.push(n)
  }
  const traces = [
    {x: xs, y: ys, type: "scatter", mode: "markers", name: "α(n)",
      marker: {color: VM.plotting.alpha("fn", 0.35), size: 5}},
    {x: [1, fibM], y: [1, fibM], type: "scatter", mode: "lines", name: "α(n) = n line",
      line: {color: chartColors.muted, width: 1, dash: "dash"}},
    {x: equal, y: equal, type: "scatter", mode: "markers", name: "α(n) = n",
      marker: {color: chartColors.alt, size: 8, line: {color: chartColors.halo, width: 1}}}
  ]
  return VM.plotting.plotWithLegend(fibCyclePlot, traces, {
    title: {text: "Smallest k where F_k ≡ 0 (mod n)"}, margin: {t: 40},
    xaxis: {title: "n"}, yaxis: {title: "First k such that n | F_k", range: [-50, 1200]}
  })
}

function gcd(a, b) {
  while (b !== 0) {
    const t = a % b
    a = b
    b = t
  }
  return a
}

// Groups n = 1, ..., fibN by the ratio n / α(n), kept as an exact fraction
// so that 4/3 and 1.3333... can't drift apart.
fibRatios = {
  const groups = new Map()
  for (let n = 1; n <= fibN; n++) {
    const a = fibCycles[n - 1]
    const g = gcd(n, a)
    const num = n / g
    const den = a / g
    const key = `${num}/${den}`
    if (!groups.has(key)) {
      let label = key
      if (den === 1) label = String(num)
      groups.set(key, {label, num, den, value: num / den, ns: []})
    }
    groups.get(key).ns.push(n)
  }
  return Array.from(groups.values())
}

{
  // The ratios shared by more than seven n, in increasing order.
  const common = []
  for (const r of fibRatios) {
    if (r.ns.length > 7) common.push(r)
  }
  common.sort((a, b) => a.value - b.value)
  const labels = []
  const counts = []
  const colors = []
  for (const r of common) {
    labels.push(r.label)
    counts.push(r.ns.length)
    let color = chartColors.muted
    if (r.label === "1") color = chartColors.alt
    if (r.label === "4/3") color = chartColors.ok
    colors.push(color)
  }
  return fibRatioPlot([{x: labels, y: counts, type: "bar", marker: {color: colors}}], {
    title: {text: "Count of the most common ratios n / α(n)"}, margin: {t: 40},
    showlegend: false,
    xaxis: {title: "n / α(n)", type: "category", tickangle: -90}, yaxis: {title: "count"}
  })
}

{
  // The 30 most common ratios, by count.
  const sorted = fibRatios.slice()
  sorted.sort((a, b) => b.ns.length - a.ns.length || a.value - b.value)
  const rows = []
  for (const r of sorted.slice(0, 30)) {
    rows.push(html`<tr><td class="text-nowrap">${r.label}</td><td class="text-end">${r.ns.length}</td><td>${r.ns.join(", ")}</td></tr>`)
  }
  return html`<table class="table table-sm small">
    <thead><tr><th>n / α(n)</th><th class="text-end">count</th><th>n values</th></tr></thead>
    <tbody>${rows}</tbody>
  </table>`
}