Values of n where α(n) = n (up to 10000):
[1, 5, 12, 25, 60, 125, 300, 625, 1500, 3125, 7500]Self-Fibonacci Numbers
number theory
research
open
fibonacci
exploration
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.
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.
Conjecture
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)\)…
Questions
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.
| n / α(n) | count | n values |
|-----------:|--------:|:--------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1.33333 | 31 | 8, 16, 32, 40, 64, 80, 128, 160, 200, 256, 320, 400, 512, 640, 800, 1000, 1024, 1280, 1600, 2000, 2048, 2560, 3200, 4000, 4096, 5000, 5120, 6400, 8000, 8192, 10000 |
| 2.625 | 29 | 21, 63, 105, 147, 189, 315, 441, 525, 567, 735, 945, 1029, 1323, 1575, 1701, 2205, 2625, 2835, 3087, 3675, 3969, 4725, 5103, 5145, 6615, 7203, 7875, 8505, 9261 |
| 12 | 27 | 144, 288, 432, 576, 720, 864, 1152, 1296, 1440, 1728, 2160, 2304, 2592, 2880, 3456, 3600, 3888, 4320, 4608, 5184, 5760, 6480, 6912, 7200, 7776, 8640, 9216 |
| 0.75 | 25 | 3, 9, 15, 27, 45, 75, 81, 135, 225, 243, 375, 405, 675, 729, 1125, 1215, 1875, 2025, 2187, 3375, 3645, 5625, 6075, 6561, 9375 |
| 1.39286 | 20 | 39, 117, 195, 351, 507, 585, 975, 1053, 1521, 1755, 2535, 2925, 3159, 4563, 4875, 5265, 6591, 7605, 8775, 9477 |
| 4 | 19 | 48, 96, 192, 240, 384, 480, 768, 960, 1200, 1536, 1920, 2400, 3072, 3840, 4800, 6000, 6144, 7680, 9600 |
| 2.47619 | 18 | 104, 208, 416, 520, 832, 1040, 1352, 1664, 2080, 2600, 2704, 3328, 4160, 5200, 5408, 6656, 6760, 8320 |
| 1.5 | 16 | 18, 54, 90, 162, 270, 450, 486, 810, 1350, 1458, 2250, 2430, 4050, 4374, 6750, 7290 |
| 7.55556 | 16 | 136, 272, 544, 680, 1088, 1360, 2176, 2312, 2720, 3400, 4352, 4624, 5440, 6800, 8704, 9248 |
| 9.33333 | 15 | 224, 448, 896, 1120, 1568, 1792, 2240, 3136, 3584, 4480, 5600, 6272, 7168, 7840, 8960 |
| 8.44444 | 15 | 152, 304, 608, 760, 1216, 1520, 2432, 2888, 3040, 3800, 4864, 5776, 6080, 7600, 9728 |
| 1.2381 | 15 | 26, 52, 130, 260, 338, 650, 676, 1300, 1690, 3250, 3380, 4394, 6500, 8450, 8788 |
| 5.25 | 14 | 126, 378, 630, 882, 1134, 1890, 2646, 3150, 3402, 4410, 5670, 6174, 7938, 9450 |
| 3 | 14 | 36, 108, 180, 324, 540, 900, 972, 1620, 2700, 2916, 4500, 4860, 8100, 8748 |
| 1.85714 | 13 | 13, 65, 156, 169, 325, 780, 845, 1625, 2028, 2197, 3900, 4225, 8125 |
| 3.77778 | 13 | 34, 68, 170, 340, 578, 850, 1156, 1700, 2890, 4250, 5780, 8500, 9826 |
| 0.875 | 13 | 7, 35, 49, 175, 245, 343, 875, 1225, 1715, 2401, 4375, 6125, 8575 |
| 3.10714 | 12 | 87, 261, 435, 783, 1305, 2175, 2349, 2523, 3915, 6525, 7047, 7569 |
| 6 | 12 | 72, 216, 360, 648, 1080, 1800, 1944, 3240, 5400, 5832, 9000, 9720 |
| 5.52381 | 12 | 232, 464, 928, 1160, 1856, 2320, 3712, 4640, 5800, 6728, 7424, 9280 |
| 2.93333 | 11 | 88, 176, 352, 704, 968, 1408, 1936, 2816, 3872, 5632, 7744 |
| 5.5 | 11 | 55, 275, 330, 605, 1375, 1650, 3025, 3630, 6655, 6875, 8250 |
| 8.25 | 11 | 165, 495, 825, 1485, 1815, 2475, 4125, 4455, 5445, 7425, 9075 |
| 1.46053 | 11 | 111, 333, 555, 999, 1665, 2775, 2997, 4107, 4995, 8325, 8991 |
| 1 | 11 | 1, 5, 12, 25, 60, 125, 300, 625, 1500, 3125, 7500 |
| 0.583333 | 11 | 14, 70, 98, 350, 490, 686, 1750, 2450, 3430, 4802, 8750 |
| 1.65 | 11 | 33, 99, 297, 363, 891, 1089, 2673, 3267, 3993, 8019, 9801 |
| 0.666667 | 11 | 2, 4, 10, 20, 50, 100, 250, 500, 1250, 2500, 6250 |
| 10.5 | 10 | 252, 756, 1260, 1764, 2268, 3780, 5292, 6300, 6804, 8820 |
| 1.16667 | 10 | 28, 140, 196, 700, 980, 1372, 3500, 4900, 6860, 9604 |
| 14.6667 | 10 | 440, 880, 1760, 2200, 3520, 4400, 4840, 7040, 8800, 9680 |
| 2.07143 | 10 | 29, 145, 174, 725, 841, 870, 3625, 4205, 4350, 5046 |
| 2.59649 | 10 | 296, 592, 1184, 1480, 2368, 2960, 4736, 5920, 7400, 9472 |
| 2.93182 | 10 | 129, 387, 645, 1161, 1935, 3225, 3483, 5547, 5805, 9675 |
| 8.625 | 9 | 207, 621, 1035, 1863, 3105, 4761, 5175, 5589, 9315 |
| 8.8125 | 9 | 141, 423, 705, 1269, 2115, 3525, 3807, 6345, 6627 |
| 2.78571 | 9 | 234, 702, 1170, 2106, 3042, 3510, 5850, 6318, 9126 |
| 1.29825 | 9 | 74, 148, 370, 740, 1850, 2738, 3700, 5476, 9250 |
| 4.875 | 8 | 273, 819, 1365, 2457, 3549, 4095, 6825, 7371 |
| 28 | 8 | 672, 1344, 2688, 3360, 4704, 5376, 6720, 9408 |
| 1.47973 | 8 | 219, 657, 1095, 1971, 3285, 5475, 5913, 9855 |
| 1.05556 | 8 | 19, 95, 361, 475, 1805, 2375, 6859, 9025 |
| 2.71264 | 8 | 472, 944, 1888, 2360, 3776, 4720, 7552, 9440 |
| 7.42857 | 8 | 624, 1248, 2496, 3120, 4992, 6240, 8112, 9984 |
| 1.94737 | 8 | 37, 185, 444, 925, 1369, 2220, 4625, 6845 |
| 5.775 | 8 | 231, 693, 1617, 2079, 2541, 4851, 6237, 7623 |
| 7.85185 | 8 | 424, 848, 1696, 2120, 3392, 4240, 6784, 8480 |
| 1.88889 | 8 | 17, 85, 289, 425, 1445, 2125, 4913, 7225 |
| 2.95588 | 8 | 201, 603, 1005, 1809, 3015, 5025, 5427, 9045 |
| 2.33333 | 8 | 56, 280, 392, 1400, 1960, 2744, 7000, 9800 |
| 1.75 | 8 | 42, 210, 294, 1050, 1470, 2058, 5250, 7350 |
| 1.52586 | 8 | 177, 531, 885, 1593, 2655, 4425, 4779, 7965 |
| 1.01724 | 8 | 59, 295, 354, 1475, 1770, 3481, 7375, 8850 |
| 4.46053 | 7 | 339, 1017, 1695, 3051, 5085, 8475, 9153 |
| 8.26667 | 7 | 248, 496, 992, 1984, 3968, 7688, 7936 |
| 1.48469 | 7 | 291, 873, 1455, 2619, 4365, 7275, 7857 |
| 6.06818 | 7 | 267, 801, 1335, 2403, 4005, 6675, 7209 |
| 1.84722 | 7 | 133, 665, 931, 2527, 3325, 4655, 6517 |
| 1.65278 | 7 | 119, 595, 833, 2023, 2975, 4165, 5831 |
| 3.92593 | 7 | 106, 212, 530, 1060, 2650, 5300, 5618 |
| 2.63063 | 7 | 584, 1168, 2336, 2920, 4672, 5840, 9344 |
| 1.97297 | 7 | 73, 365, 876, 1825, 4380, 5329, 9125 |
| 2.97115 | 7 | 309, 927, 1545, 2781, 4635, 7725, 8343 |
| 6.70833 | 7 | 161, 805, 1127, 3703, 4025, 5635, 7889 |
| 22.6667 | 6 | 816, 1632, 3264, 4080, 6528, 8160 |
| 0.928571 | 6 | 78, 390, 1014, 1950, 5070, 9750 |
| 10.7879 | 6 | 712, 1424, 2848, 3560, 5696, 7120 |
| 1.70395 | 6 | 259, 1295, 1813, 6475, 9065, 9583 |
| 1.31532 | 6 | 146, 292, 730, 1460, 3650, 7300 |
| 2.63946 | 6 | 776, 1552, 3104, 3880, 6208, 7760 |
| 1.41667 | 6 | 51, 255, 867, 1275, 4335, 6375 |
| 1.91667 | 6 | 46, 230, 1058, 1150, 5290, 5750 |
| 3.30556 | 6 | 238, 1190, 1666, 4046, 5950, 8330 |
| 2.11111 | 6 | 38, 190, 722, 950, 3610, 4750 |
| 5.57143 | 6 | 468, 1404, 2340, 4212, 6084, 7020 |
| 8.10256 | 6 | 632, 1264, 2528, 3160, 5056, 6320 |
| 30.6667 | 6 | 736, 1472, 2944, 3680, 5888, 7360 |
| 1.925 | 6 | 77, 539, 847, 3773, 5929, 9317 |
| 1.31973 | 6 | 194, 388, 970, 1940, 4850, 9700 |
| 8.09091 | 6 | 89, 445, 1068, 2225, 5340, 7921 |
| 4.66667 | 6 | 112, 560, 784, 2800, 3920, 5488 |
| 6.15 | 6 | 123, 369, 1107, 3321, 5043, 9963 |
| 1.38095 | 6 | 58, 290, 1450, 1682, 7250, 8410 |
| 7.01587 | 6 | 442, 884, 2210, 4420, 5746, 7514 |
| 3.69444 | 6 | 266, 1330, 1862, 5054, 6650, 9310 |
| 8.8 | 6 | 528, 1056, 2112, 4224, 5808, 8448 |
| 7.92982 | 6 | 904, 1808, 3616, 4520, 7232, 9040 |
| 1.97959 | 6 | 97, 485, 1164, 2425, 5820, 9409 |
| 5.21212 | 6 | 688, 1376, 2752, 3440, 5504, 6880 |
| 3.3 | 6 | 198, 594, 1782, 2178, 5346, 6534 |
| 25.3333 | 6 | 912, 1824, 3648, 4560, 7296, 9120 |
| 1.1 | 6 | 11, 66, 121, 726, 1331, 7986 |
| 21 | 6 | 504, 1512, 2520, 3528, 4536, 7560 |
| 4.22222 | 6 | 76, 380, 1444, 1900, 7220, 9500 |
| 3.5 | 6 | 84, 420, 588, 2100, 2940, 4116 |
| 5.39394 | 6 | 178, 356, 890, 1780, 4450, 8900 |
| 0.977273 | 6 | 43, 215, 1075, 1849, 5375, 9245 |
| 2.875 | 6 | 69, 345, 1587, 1725, 7935, 8625 |
| 16.1481 | 6 | 872, 1744, 3488, 4360, 6976, 8720 |
| 7 | 6 | 168, 840, 1176, 4200, 5880, 8232 |