Quite some time ago now I used "reverse engineering" to find the seed numbers leading to a given number. For example, take the number 28047. Using this algorithm (permalink), I obtain the following output.
Seed numbers for Fibonacci sequence are 3 and 9
[3, 9, 12, 21, 33, 54, 87, 141, 228, 369, 597, 966, 1563, 2529, 4092, 6621, 10713, 17334, 28047]
I outlined the construction of this algorithm in a post titled Finding Fibonacci and Tribonacci Seed Numbers in July of 2019. The previously applied algorithm relies on the fact that in a Fibonacci sequence the ratio of progressive terms approximates the golden ratio. Let's apply the algorithm once again but this time to the number 28048. The following output is obtained:
Seed numbers for Fibonacci sequence are 32 and 175
[32, 175, 207, 382, 589, 971, 1560, 2531, 4091, 6622, 10713, 17335, 28048]
The difference this time is that the seed numbers are no longer single digits and this is generally the case. What I wanted to know was what numbers in the range up to 40000 can be formed using single digits as seed numbers after applying the Fibonacci algorithm to generate the subsequent numbers. It turns out that there are only 387 such numbers in the range from 10 to 40000. They are (permalink):
10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 60, 61, 63, 64, 65, 66, 68, 69, 71, 72, 73, 74, 76, 77, 78, 79, 81, 82, 84, 86, 87, 89, 91, 92, 94, 97, 99, 102, 104, 105, 107, 110, 112, 115, 117, 118, 120, 123, 125, 126, 128, 131, 133, 136, 139, 141, 144, 147, 149, 152, 157, 160, 165, 168, 170, 173, 178, 181, 186, 189, 191, 194, 199, 202, 204, 207, 212, 215, 220, 225, 228, 233, 238, 241, 246, 254, 259, 267, 272, 275, 280, 288, 293, 301, 306, 309, 314, 322, 327, 330, 335, 343, 348, 356, 364, 369, 377, 385, 390, 398, 411, 419, 432, 440, 445, 453, 466, 474, 487, 495, 500, 508, 521, 529, 534, 542, 555, 563, 576, 589, 597, 610, 623, 631, 644, 665, 678, 699, 712, 720, 733, 754, 767, 788, 801, 809, 822, 843, 856, 864, 877, 898, 911, 932, 953, 966, 987, 1008, 1021, 1042, 1076, 1097, 1131, 1152, 1165, 1186, 1220, 1241, 1275, 1296, 1309, 1330, 1364, 1385, 1398, 1419, 1453, 1474, 1508, 1542, 1563, 1597, 1631, 1652, 1686, 1741, 1775, 1830, 1864, 1885, 1919, 1974, 2008, 2063, 2097, 2118, 2152, 2207, 2241, 2262, 2296, 2351, 2385, 2440, 2495, 2529, 2584, 2639, 2673, 2728, 2817, 2872, 2961, 3016, 3050, 3105, 3194, 3249, 3338, 3393, 3427, 3482, 3571, 3626, 3660, 3715, 3804, 3859, 3948, 4037, 4092, 4181, 4270, 4325, 4414, 4558, 4647, 4791, 4880, 4935, 5024, 5168, 5257, 5401, 5490, 5545, 5634, 5778, 5867, 5922, 6011, 6155, 6244, 6388, 6532, 6621, 6765, 6909, 6998, 7142, 7375, 7519, 7752, 7896, 7985, 8129, 8362, 8506, 8739, 8883, 8972, 9116, 9349, 9493, 9582, 9726, 9959, 10103, 10336, 10569, 10713, 10946, 11179, 11323, 11556, 11933, 12166, 12543, 12776, 12920, 13153, 13530, 13763, 14140, 14373, 14517, 14750, 15127, 15360, 15504, 15737, 16114, 16347, 16724, 17101, 17334, 17711, 18088, 18321, 18698, 19308, 19685, 20295, 20672, 20905, 21282, 21892, 22269, 22879, 23256, 23489, 23866, 24476, 24853, 25086, 25463, 26073, 26450, 27060, 27670, 28047, 28657, 29267, 29644, 30254, 31241, 31851, 32838, 33448, 33825, 34435, 35422, 36032, 37019, 37629, 38006, 38616, 39603
The algorithm can also be used to enter any of the above numbers to find the seed numbers and the resulting sequence. For example, entering the last number in the above sequence (39603) reveals that it can formed by three different pairs of seed numbers: (1, 3), (3, 4) and (4, 7). The resulting sequences are essentially the same from 11 onwards:
1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603
3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603
4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603
Between 10 and 100, the numbers that CANNOT be derived from single digit seed numbers are 59, 62, 67, 70, 75, 80, 83, 85, 88, 90, 93, 95, 96, 98 and 100. The frequency of these numbers increases rapidly as the numbers get larger. For example, between 38616 and 39603 there is a gap of 87 and so there are 85 such numbers in the range.
No comments:
Post a Comment