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

The Circulant Matrix of a Number and its Permanent

In a post on December 15th 2022 titled Numbers and Matrices, I wrote about the circulant matrix of a number and looked at those special numbers where the determinant of the circulant matrix was equal to the number itself. An example of such a number is 494376160 which has the circulant matrix shown in Figure 1:

Figure 1

These sorts of numbers form OEIS A219324 and the initial members are:

1, 2, 3, 4, 5, 6, 7, 8, 9, 247, 370, 378, 407, 481, 518, 592, 629, 1360, 3075, 26027, 26933, 45018, 69781, 80487, 154791, 1920261, 2137616, 2716713, 3100883, 3480140, 3934896, 4179451, 4830936, 5218958, 11955168, 80651025, 95738203, 257059332, 278945612, 456790123, 469135802, 493827160, 494376160

Instead of the determinant, we can use the permanent instead. The latter is not as well known as the former so Figure 2 provides a short explanation:

Figure 2

It's basically the same as the calculation for the determinant except that there are no alternating positive and negative signs. Figure 3 shows the calculations to determine the permanent of a rectangular matrix.

Figure 3

So now we can investigate what numbers have a circulant matrix whose permanent is equal to the number itself. It turns out that there are not that many. Here is the list up to ten million: 1, 2, 3, 4, 5, 6, 7, 8, 9, 261, 370, 407, 52036, 724212. The circulant matrix for 724212 is shown in Figure 4.

Figure 4

We can search for other numbers that the permanent might be equal to. The number 666 came to mind but if we collect the permanents of the first one million numbers, then there are only 269 numbers between 1 and 1000 (permalink). These are:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 16, 17, 18, 20, 24, 25, 26, 27, 28, 29, 32, 33, 34, 35, 36, 37, 38, 40, 41, 44, 45, 48, 49, 50, 52, 53, 54, 58, 61, 64, 65, 68, 72, 73, 74, 78, 79, 80, 81, 82, 84, 85, 89, 90, 91, 97, 98, 100, 106, 113, 116, 117, 120, 121, 125, 126, 128, 130, 132, 133, 136, 142, 144, 145, 152, 154, 155, 162, 164, 165, 168, 169, 171, 177, 178, 185, 189, 194, 198, 200, 201, 216, 217, 224, 226, 232, 233, 236, 243, 244, 250, 256, 257, 261, 265, 272, 273, 275, 280, 281, 289, 298, 299, 304, 305, 306, 314, 317, 324, 326, 337, 341, 343, 344, 349, 351, 353, 359, 361, 364, 366, 369, 370, 373, 384, 388, 389, 393, 394, 395, 396, 397, 400, 404, 407, 408, 409, 413, 416, 418, 420, 425, 432, 433, 434, 440, 443, 466, 468, 472, 481, 484, 486, 492, 493, 502, 504, 512, 513, 514, 520, 523, 526, 529, 530, 538, 539, 541, 544, 548, 559, 569, 574, 576, 577, 583, 586, 606, 612, 614, 624, 625, 626, 632, 633, 637, 638, 641, 656, 665, 673, 674, 676, 686, 691, 697, 706, 720, 728, 729, 730, 737, 745, 750, 753, 756, 757, 758, 765, 769, 772, 776, 782, 783, 784, 792, 793, 801, 807, 809, 810, 819, 824, 825, 833, 834, 838, 841, 850, 853, 854, 855, 872, 873, 877, 881, 882, 884, 885, 891, 896, 902, 907, 916, 926, 927, 928, 937, 945, 952, 953, 962, 964, 978, 980, 988, 990, 1000

As can be seen, 665 is among them but not 666. If we took the permanents of numbers in excess of one million, perhaps more numbers between 1 and 1000 would appear but it's doubtful. If we do the same for the determinants, we find that there are 417 of them between 1 and 1000. Oddly enough, 666 is not among them even though the numbers on either side (665 and 667) are (permalink).