Finding Fibonacci

The Fibonacci numbers are few and far between. Up to a little over two million, the Fibonacci numbers are:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309

However, we can find Fibonacci numbers in all sorts of places. For example, I recently turned 27034 days old and this number is a member of OEIS A272412:

A272412

Numbers \(n\) such that \( \sigma_1(n)\) is a Fibonacci number.

It so happens that \( \sigma_1(27034) = 46368 \) which is a Fibonacci number. There are only 41 such numbers in the range up to one million. They are (permalink):

1, 2, 7, 9, 66, 70, 94, 115, 119, 2479, 18084, 19180, 19290, 22060, 23156, 23178, 24934, 24956, 25756, 26715, 27034, 28678, 28965, 29578, 30094, 32253, 32793, 34113, 35365, 38635, 39319, 40963, 42493, 44413, 45223, 45653, 322032, 429424, 503175, 624027, 670975

The sum of the aliquot parts of a number is the sum of its proper divisors and so Fibonacci numbers will show up here as well. We have to exclude prime numbers in our search because their only proper divisor is 1 and so they would need to be included. It turns out that there are 175 composite numbers up to one million whose sum of proper divisors are a Fibonacci number. They are:

1, 4, 10, 18, 27, 35, 36, 49, 51, 62, 90, 91, 171, 329, 415, 473, 533, 629, 687, 713, 902, 1119, 1135, 1207, 1214, 1605, 1711, 1927, 2936, 2949, 3436, 6083, 6103, 6845, 7831, 8119, 9487, 10063, 10207, 12367, 12531, 13231, 17069, 18373, 18703, 20283, 20579, 24319, 26843, 28783, 29719, 32743, 33823, 35263, 45443, 53121, 57683, 61573, 66779, 71653, 72803, 80785, 81779, 90949, 95593, 95611, 99937, 109093, 111179, 130153, 134149, 145403, 153779, 156613, 159323, 162083, 167579, 169699, 173353, 194251, 196393, 199883, 200543, 208723, 210649, 215603, 218731, 225923, 227173, 228649, 230053, 233579, 235993, 238643, 240133, 242149, 242495, 243013, 246179, 275603, 287617, 306179, 313043, 325726, 346415, 356963, 364099, 365363, 372359, 378646, 381779, 395723, 401579, 405443, 408883, 411979, 424283, 433403, 435811, 444083, 451043, 456179, 459179, 461243, 464579, 485483, 488443, 503579, 510779, 512749, 525119, 527243, 530419, 535043, 540083, 547403, 549779, 553283, 558815, 573803, 578723, 581579, 587963, 592283, 597203, 602579, 604763, 612779, 617483, 619459, 622163, 628883, 630563, 632579, 633323, 633779, 635123, 635963, 636179, 636683, 646840, 649869, 670171, 686083, 693211, 716179, 724429, 761899, 825143, 830183, 842899, 919651, 935821, 975143, 986179

Take 51 as an example. It's proper divisors are 1, 3 and 17. These add to 21 which is a Fibonacci number. There is no associated OEIS sequence for these numbers.

Let's look at the totients of numbers. The totient of a number \(n\) is a count of how many numbers \(1 \leq k \leq n \) have the property that \( \text{gcd}(n,k)=1\) where gcd stands for greatest common divisor. The totient of 6 is 2 because 1 and 5 have this property. These numbers form OEIS A280592: 

A280592

Numbers \(n\)  such that \( \phi(n)\) is a Fibonacci number.

 Here is the list of the 134 sequence members up to one million.

1, 2, 3, 4, 6, 15, 16, 20, 24, 30, 185, 219, 273, 285, 292, 296, 304, 315, 364, 370, 380, 432, 438, 444, 456, 468, 504, 540, 546, 570, 630, 3235, 5176, 6470, 7764, 46843, 47423, 47693, 48053, 50431, 52403, 56231, 57965, 59555, 62855, 67655, 67865, 70735, 72123, 72297, 73473, 75387, 77691, 78819, 81207, 84651, 85869, 86985, 89535, 89655, 89817, 90945, 92744, 93686, 94846, 95288, 95386, 95504, 95632, 96106, 96164, 97964, 100516, 100568, 100862, 101535, 102165, 103588, 103635, 104806, 105092, 108248, 108304, 108584, 108976, 112462, 112868, 113176, 115930, 119110, 119380, 119540, 119756, 125710, 135310, 135380, 135730, 136220, 139116, 139176, 139212, 139248, 141470, 142932, 143256, 143448, 144246, 144594, 145116, 145512, 146946, 147204, 150774, 150852, 155382, 157638, 162372, 162414, 162456, 162876, 163464, 165816, 169302, 169764, 171738, 173970, 174060, 179070, 179310, 179634, 181890, 203070, 204330, 207270

Why are there no numbers from 207271 up to one million that are members of the sequence? If we extend the range to two million, there are some additional members, namely 1040075, 1304859, 1372899, 1739812 and 1830532.

Of course, we don't need to confine ourselves to the Fibonacci numbers. We could consider the Lucas numbers instead which begin with 2, 1 rather than 0, 1 like the Fibonacci. The initial Lucas numbers are:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196

Up to one million, there are only nine numbers that qualify and they are 1, 2, 3, 4, 10, 17, 688, 1075 and 103681.

If we consider the sum of the aliquot parts however, we get 151 in the range up to one million. These are:

4, 8, 9, 21, 48, 72, 92, 115, 129, 146, 165, 187, 205, 289, 493, 965, 999, 1143, 1337, 1417, 1495, 1749, 1957, 2517, 2527, 2722, 3077, 3397, 3401, 5177, 5599, 6437, 6609, 7097, 8201, 8357, 8551, 8777, 9017, 9485, 9701, 9797, 10777, 14239, 15637, 17549, 19639, 24751, 25141, 27199, 31879, 37499, 38359, 38825, 39149, 42319, 46241, 46715, 48946, 50959, 52471, 53627, 53851, 55505, 56137, 56693, 58951, 60031, 65387, 66511, 67159, 67519, 67591, 75605, 76117, 79897, 81581, 102689, 102707, 104341, 109709, 109869, 114109, 119641, 127957, 130721, 133141, 138037, 140377, 144689, 144841, 151661, 154741, 175477, 177097, 186401, 207149, 224593, 248429, 270251, 275789, 283453, 287033, 340513, 344507, 350369, 357101, 362833, 370541, 377249, 390641, 449233, 459709, 470321, 486476, 500893, 535841, 555341, 560509, 577197, 598813, 606989, 613409, 621827, 648569, 658667, 663073, 664481, 670829, 698209, 704737, 708749, 746381, 748753, 758861, 796109, 798869, 802289, 826489, 833069, 851441, 863773, 869041, 869741, 887969, 894029, 931453, 950353, 956509, 962593, 988787

As for totients, there are 21 numbers in the range up to one million whose totient is a member of the Lucas sequence. These numbers are:

1, 2, 3, 4, 5, 6, 8, 10, 12, 19, 27, 38, 54, 2049, 2732, 4098, 5779, 11558, 36717, 48956, 73434

Another approach is to look at the determinant formed by the circulant matrix of a number. For example, 27255 has a circulant matrix as shown in Figure 1.

Figure 1

This matrix has a determinant of 21 which is a Fibonacci number. It turns out that there are 59500 numbers in the range up to one million that have this property (permalink).

Instead of the determinant, the permanent of the matrix could be considered. For example, 19140 has the circulant matrix shown in Figure 2.

Figure 2

In the range up to one million, there are only 68 such numbers (as opposed to the 59500 for the determinant). Here are the numbers:

[1, 2, 3, 5, 8, 10, 11, 12, 21, 22, 23, 32, 35, 53, 58, 85, 100, 101, 110, 200, 1000, 1001, 1021, 1100, 1102, 1120, 1201, 1222, 2011, 2022, 2110, 2122, 2202, 2212, 2220, 2221, 10000, 10001, 10010, 10011, 10100, 10101, 10110, 10419, 10941, 11000, 11001, 11010, 11094, 11100, 11490, 14019, 14901, 19104, 19140, 40191, 41109, 41910, 49011, 90114, 91041, 91401, 94110, 100000, 100001, 100100, 110000, 1000000]

Here are the Fibonacci numbers associated with each of these numbers:

1 --> 1

2 --> 2

3 --> 3

5 --> 5

8 --> 8

10 --> 1

11 --> 2

12 --> 5

21 --> 5

22 --> 8

23 --> 13

32 --> 13

35 --> 34

53 --> 34

58 --> 89

85 --> 89

100 --> 1

101 --> 2

110 --> 2

200 --> 8

1000 --> 1

1001 --> 2

1021 --> 34

1100 --> 2

1102 --> 34

1120 --> 34

1201 --> 34

1222 --> 233

2011 --> 34

2022 --> 144

2110 --> 34

2122 --> 233

2202 --> 144

2212 --> 233

2220 --> 144

2221 --> 233

10000 --> 1

10001 --> 2

10010 --> 2

10011 --> 13

10100 --> 2

10101 --> 13

10110 --> 13

10419 --> 75025

10941 --> 75025

11000 --> 2

11001 --> 13

11010 --> 13

11094 --> 75025

11100 --> 13

11490 --> 75025

14019 --> 75025

14901 --> 75025

19104 --> 75025

19140 --> 75025

40191 --> 75025

41109 --> 75025

41910 --> 75025

49011 --> 75025

90114 --> 75025

91041 --> 75025

91401 --> 75025

94110 --> 75025

100000 --> 1

100001 --> 2

100100 --> 8

110000 --> 2