Jon Maiga, 2018-10-28
After adding bitwise operators (and, or, xor) to sequencedb.net I manually went through new Online Encyclopedia of Integer Sequences matches to see if any interesting sequences or formulas had been found.
By interesting, I mean new formulas that describe a sequence. I am often able to quickly dismiss matches due to coincidence or matching only the first terms etc.
One that I was not certain about was a match on something called the fertility numbers, A317551.
The fertility numbers are 0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30 … (the oeis entry stops here).
The sequencedb.net seemingly matching formula was pkuq41hywvgv
I got a bit curious about the problem itself, specifically how to generate more fertility numbers to verify this formula.
Fertility numbers are found when sorting permutations of strings using an algorithm described in the Julian West 1990 thesis Permutations with restricted subsequences and stack-sortable permutations (which I wasn’t able to find anywhere).
Luckily the algorithm is simple,
I recommend reading the introduction to this paper - the image of how this algorithm works makes it really clear.
Practically this sorting scheme is not very good as it fails to sort some input strings (213). I think this is where the mathematicians get excited and want to be able to answer questions such as:
Given all permutations of length n (n! of them), how many of those can be sorted? It turns out that the nth Catalan numbers tells us this (known since Knuth played around with this in the sixties).
What fertility numbers are is one of those questions.
The oeis entry example says
The preimages of 123 under the stack-sorting map are 123, 132, 213, 312, and 321. This shows that the fertility of 123 is 5, so 5 is a fertility number.
This means that there are 5 input permutations that sorts into the output 123 when run through the stack sorting algorithm described above, hence 5 is a fertility number. There is also 1 input permutation (total ) that does not sort, which means that 1 is a fertility number.
As a side note, since 123 is the sorted output we can verify this with the Catalan numbers that will tell us the number of sortable preimages
Hence, at least, every catalan number is a fertility number.
map<string, unsigned int> fn;
| n | key | value |
|---|---|---|
| 0 | 0 | |
| 1 | 1 | 1 |
| 2 | 12 | 2 |
| 3 | 123 | 5 |
| 3 | 213 | 1 |
| 4 | 1234 | 14 |
| 4 | 1324 | 2 |
| 4 | 2134 | 2 |
| 4 | 2314 | 4 |
| 4 | 3124 | 2 |
| 5 | 12345 | 42 |
| … | … | … |
A few observations:
As mentioned before, the values of the sorted keys, 0, 1, 12, 123, 1234, … etc are the Catalan numbers, 1, 1, 2, 5, 14, 42, 132… A000108
The number of keys per form the sequence 1, 1, 1, 2, 5, 17, 68, 326 … A027361
The union of the values of this map are the encountered fertility numbers, 0, 1, 2, 4, 5, 14, 42, … A317551
Note that we don’t get a complete coverage of the fertility numbers by using this method. In fact, we can never be sure that we have found all fertility numbers no matter how deep we make this search. To be sure you will have to prove that for example 3 or 7 aren’t fertility numbers. However a search can give valuable hints and reveal patterns.
Colin Defant, the author of Fertility Numbers [1] has proven that
Numbers not congruent to 3 modulo 4 are 0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 28, 29, 30, 32, 33, 34, 36, 37, 38, 40, … A004773
The first fertility number that is congruent 3 modulo 4 is 27 and the author conjectured that 95 is the next.
If a sequence is dense it can help to examine the complement - the numbers that are not in the sequence.
Numbers congruent to 3 modulo 4 are 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 67, 71, 75, 79, 83, 87, 91, 95, 99, 103, 107, 111, … A004767
The complement of the conjectured formula is and after removing duplicates: 3, 7, 11, 15, 19, 23, 31, 39, 43, 47, 55, 59, 63, 67, 71, 75, 79, 83, 91, 99, 103, 107, 111, … xrfoc3bwnubfm
All those numbers seems to be congruent 3 modulo 4 - at this point I started to suspect that the matching formula is a coincidence, it it only had matched 6 of the first infertile numbers before the oeis entry ran out of terms (only 25 terms at the time of writing this).
To check how far the discovered formula holds for the fertility numbers I wrote a program that examined all permutations up to and including , using a map similar to the one described above (I had to use a sparse hash map and do some bit fiddling to not run out of my 32GB ram). I have published the c++ repository on bitbucket, west-stack-sort. If you have a 64GB machine you could theoretically complete , let me know if you are willing to help out!
After a few hours of processing, the brute force search found the following fertile numbers. The table below is only showing numbers <= 100, see the appendix for a full list:
| n | fertile numbers |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 1, 5 |
| 4 | 2, 4, 14 |
| 5 | 1, 4, 5, 9, 14, 42 |
| 6 | 2, 4, 6, 10, 14, 20, 24, 34, 48 |
| 7 | 1, 4, 5, 8, 9, 13, 14, 22, 25, 27, 28, 42, 53, 70, 81, 95,… |
| 8 | 2, 4, 6, 8, 10, 14, 18, 20, 24, 28, 34, 48, 52, 62, 70, 76, 84, 96,… |
| 9 | 1, 4, 5, 8, 9, 12, 13, 14, 16, 17, 20, 22, 25, 27, 28, 30, 39, 40, 42, 44, 45, 48, 53, 56, 60, 68, 70, 73, 81, 95, 96, 98,… |
| 10 | 2, 4, 6, 8, 10, 14, 16, 18, 20, 24, 26, 28, 30, 34, 36, 44, 48, 50, 52, 54, 56, 62, 64, 70, 76, 84, 88, 96, 98, 100,… |
| 11 | 1, 4, 5, 8, 9, 12, 13, 14, 16, 17, 20, 21, 22, 24, 25, 27, 28, 30, 36, 38, 39, 40, 42, 44, 45, 48, 51, 53, 56, 60, 65, 68, 70, 73, 76, 80, 81, 84, 93, 95, 96, 98,… |
| 12 | 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 26, 28, 30, 32, 34, 36, 40, 44, 48, 50, 52, 54, 56, 60, 62, 64, 70, 76, 78, 80, 84, 88, 90, 96, 98, 100,… |
| 13 | 1, 4, 5, 8, 9, 12, 13, 14, 16, 17, 20, 21, 22, 24, 25, 27, 28, 30, 32, 36, 38, 39, 40, 42, 44, 45, 46, 48, 51, 52, 53, 56, 60, 63, 65, 68, 70, 72, 73, 76, 80, 81, 84, 85, 88, 90, 92, 93, 95, 96, 98, 100, … |
| 14 | 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 26, 28, 30, 32, 34, 36, 40, 42, 44, 48, 50, 52, 54, 56, 60, 62, 64, 68, 70, 72, 76, 78, 80, 84, 88, 90, 96, 98, 100, … |
0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 53, 54, 56, 60, 62, 63, 64, 65, 68, 70, 72, 73, 76, 78, 80, 81, 84, 85, 88, 90, 92, 93, 95, 96, 98, 100
27, 39, 51, 63, 95
3, 7, 11, 15, 19, 23, 29, 31, 33, 35, 37, 41, 43, 47, 49, 55, 57, 58, 59, 61, 66, 67, 69, 71, 74, 75, 77, 79, 82, 83, 86, 87, 89, 91, 94, 97, 99
0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 56, 57, 58, 60, 61, 62, 63, 64, 65, 66, 68, 69, 70, 72, 73, 74, 76, 77, 78, 80, 81, 82, 84, 85, 86, 88, 89, 90, 92, 93, 94, 95, 96, 97, 98, 100
Dismissal of potential fertility number formula. Finally I was able to dismiss the formula which started all this, since the computer had found that 39 is a fertile number which is not a member of .
Improved conjecture. It seems like the conjecture 4.2 in [1]
The smallest fertility number that is congruent to 3 modulo 4 and is greater than 27 is 95.
can be improved from 95 to 39.
Improved natural density. The author of [1] also calculated a natural density of fertility numbers () that can be improved by adding the computer found fertility numbers that are congruent 3 mod 4. If I understand it correctly it’s calculated something like this for numbers < 100:
Plugging in all 149 fertile numbers congruent 3 mod 4 discovered in the search (see Appendix) we get the density
Examine 31 and 35. It has previously been proven that 3, 7, 15, 19 and 23 are not fertile numbers. The proof used the fact that it was known that 27 is a fertility number and if any of 3, 7, 15, 19, 23 was it would lead to a contradiction [1]. The next two that need to be examined are 31 and 35. I wonder if 39 can be used in the same way as 27 was? I will leave that to the mathematicians.
Finally, I did see some other interesting patterns both related to the fertile numbers and A027361 but I will save that for another day.
[1] C. Defant, 2018, Fertility numbers
I’ve published c++ git repo with the code used to generate the fertility numbers west-stack-sort. If you have >=64GB of RAM it would be interesting to see if we can get it to complete for , let me know if you are willing to help out!
27, 39, 51, 63, 95, 123, 135, 143, 191, 195, 219, 239, 243, 259, 279, 327, 331, 355, 387, 439, 447, 463, 475, 483, 579, 583, 607, 615, 635, 667, 715, 771, 811, 831, 855, 903, 955, 1051, 1079, 1091, 1099, 1107, 1187, 1215, 1247, 1271, 1335, 1431, 1451, 1495, 1523, 1535, 1567, 1655, 1671, 1767, 1935, 1971, 1987, 2047, 2143, 2243, 2263, 2355, 2383, 2667, 2719, 2803, 3143, 3223, 3279, 3307, 3699, 3895, 3971, 4063, 4203, 4331, 4451, 4515, 4643, 4731, 4819, 4839, 4879, 4947, 5055, 5215, 5231, 5395, 5495, 5591, 5611, 5759, 5775, 5983, 6211, 6291, 6599, 6687, 6735, 6927, 7215, 7407, 7539, 7743, 7907, 8095, 8771, 8887, 9303, 9499, 9867, 11587, 11715, 12439, 13307, 13479, 13515, 13743, 14283, 14287, 14443, 14611, 15075, 15199, 15327, 15519, 16375, 17611, 17747, 18687, 19191, 19203, 19675, 20551, 20687, 21359, 22535, 23575, 23679, 25087, 28255, 30475, 34963, 42559, 45727, 50807, 55295
0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 34, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 53, 54, 56, 60, 62, 63, 64, 65, 68, 70, 72, 73, 76, 78, 80, 81, 84, 85, 88, 90, 92, 93, 95, 96, 98, 100, 102, 104, 106, 108, 110, 112, 113, 114, 117, 120, 121, 123, 124, 125, 126, 128, 130, 132, 135, 136, 140, 141, 142, 143, 144, 146, 149, 150, 152, 154, 156, 160, 161, 162, 164, 165, 166, 168, 170, 176, 180, 182, 184, 185, 186, 189, 190, 191, 192, 194, 195, 196, 197, 198, 200, 201, 204, 206, 208, 210, 212, 216, 217, 218, 219, 220, 222, 224, 225, 226, 228, 236, 238, 239, 240, 241, 242, 243, 246, 248, 250, 252, 253, 259, 260, 261, 262, 264, 265, 266, 270, 272, 278, 279, 280, 281, 282, 286, 288, 289, 290, 292, 296, 298, 300, 302, 304, 306, 308, 309, 310, 312, 316, 318, 320, 322, 324, 327, 328, 330, 331, 332, 334, 336, 340, 342, 349, 350, 352, 355, 356, 357, 358, 364, 365, 374, 378, 380, 382, 384, 385, 386, 387, 388, 390, 392, 394, 400, 404, 405, 406, 412, 414, 416, 420, 422, 426, 429, 430, 432, 434, 436, 438, 439, 440, 442, 444, 447, 448, 452, 453, 456, 463, 468, 470, 472, 474, 475, 476, 477, 478, 480, 481, 483, 484, 486, 490, 492, 496, 500, 502, 504, 505, 506, 508, 512, 518, 520, 522, 524, 525, 526, 528, 530, 534, 540, 542, 544, 546, 550, 552, 553, 558, 560, 564, 565, 566, 570, 572, 576, 579, 580, 583, 584, 588, 592, 600, 604, 605, 607, 612, 614, 615, 616, 620, 622, 624, 626, 629, 630, 632, 635, 636, 642, 648, 649, 660, 662, 664, 666, 667, 670, 672, 677, 680, 684, 685, 686, 688, 689, 692, 693, 694, 700, 704, 705, 706, 710, 712, 713, 714, 715, 716, 724, 728, 729, 732, 736, 738, 742, 745, 748, 756, 760, 761, 762, 764, 766, 768, 770, 771, 774, 776, 780, 784, 788, 790, 792, 794, 796, 798, 800, 804, 810, 811, 812, 816, 817, 818, 820, 824, 825, 830, 831, 832, 838, 840, 850, 852, 853, 854, 855, 856, 858, 860, 864, 868, 869, 872, 876, 878, 880, 884, 885, 888, 896, 902, 903, 906, 908, 910, 912, 918, 922, 924, 925, 926, 928, 932, 934, 936, 940, 944, 948, 950, 952, 954, 955, 956, 957, 960, 962, 966, 968, 969, 970, 978, 980, 982, 990, 992, 994, 1000, 1008, 1014, 1020, 1021, 1022, 1026, 1036, 1040, 1042, 1044, 1048, 1050, 1051, 1054, 1056, 1060, 1064, 1065, 1066, 1068, 1072, 1079, 1080, 1084, 1086, 1091, 1092, 1097, 1098, 1099, 1104, 1106, 1107, 1108, 1110, 1112, 1116, 1118, 1120, 1125, 1134, 1140, 1142, 1144, 1148, 1152, 1156, 1158, 1160, 1162, 1165, 1172, 1176, 1178, 1180, 1187, 1188, 1190, 1198, 1200, 1202, 1208, 1215, 1218, 1220, 1221, 1222, 1230, 1232, 1234, 1238, 1240, 1242, 1246, 1247, 1248, 1252, 1254, 1256, 1260, 1265, 1271, 1272, 1284, 1286, 1288, 1296, 1298, 1300, 1301, 1305, 1309, 1310, 1312, 1316, 1320, 1324, 1326, 1328, 1330, 1332, 1334, 1335, 1338, 1340, 1344, 1345, 1346, 1368, 1370, 1372, 1378, 1386, 1388, 1398, 1400, 1401, 1408, 1409, 1414, 1424, 1426, 1428, 1430, 1431, 1442, 1451, 1452, 1454, 1466, 1469, 1472, 1480, 1482, 1485, 1490, 1492, 1495, 1497, 1500, 1506, 1516, 1518, 1523, 1526, 1528, 1532, 1535, 1538, 1540, 1545, 1546, 1548, 1550, 1560, 1562, 1567, 1568, 1573, 1574, 1582, 1590, 1593, 1594, 1612, 1618, 1620, 1622, 1624, 1626, 1632, 1638, 1649, 1650, 1652, 1655, 1656, 1658, 1664, 1668, 1671, 1672, 1678, 1680, 1682, 1690, 1694, 1700, 1704, 1706, 1708, 1712, 1714, 1716, 1718, 1720, 1722, 1730, 1733, 1736, 1745, 1760, 1764, 1767, 1768, 1774, 1776, 1780, 1782, 1786, 1788, 1792, 1802, 1804, 1806, 1820, 1822, 1825, 1834, 1836, 1838, 1840, 1844, 1848, 1862, 1868, 1870, 1884, 1896, 1900, 1901, 1904, 1908, 1914, 1924, 1926, 1932, 1935, 1944, 1956, 1957, 1960, 1964, 1969, 1971, 1974, 1977, 1987, 1992, 2000, 2002, 2004, 2016, 2021, 2025, 2030, 2038, 2042, 2046, 2047, 2054, 2061, 2078, 2080, 2085, 2086, 2088, 2094, 2096, 2104, 2105, 2106, 2110, 2118, 2122, 2124, 2130, 2132, 2143, 2145, 2156, 2165, 2166, 2170, 2180, 2182, 2184, 2186, 2188, 2198, 2200, 2217, 2222, 2226, 2232, 2236, 2243, 2253, 2254, 2263, 2268, 2280, 2282, 2284, 2286, 2288, 2290, 2304, 2310, 2312, 2324, 2338, 2349, 2350, 2352, 2355, 2362, 2366, 2370, 2374, 2376, 2380, 2383, 2386, 2388, 2392, 2394, 2400, 2405, 2410, 2430, 2445, 2446, 2453, 2460, 2464, 2480, 2482, 2486, 2492, 2493, 2494, 2496, 2502, 2516, 2517, 2518, 2520, 2534, 2544, 2548, 2574, 2576, 2602, 2604, 2610, 2613, 2616, 2618, 2629, 2640, 2641, 2646, 2648, 2654, 2656, 2662, 2664, 2667, 2670, 2674, 2676, 2680, 2694, 2706, 2710, 2719, 2726, 2730, 2733, 2734, 2744, 2754, 2760, 2766, 2772, 2780, 2788, 2796, 2803, 2832, 2836, 2850, 2852, 2858, 2860, 2873, 2878, 2880, 2886, 2892, 2904, 2916, 2922, 2938, 2940, 2948, 2952, 2957, 2960, 2978, 2990, 2992, 2994, 2998, 3010, 3012, 3020, 3024, 3032, 3036, 3042, 3046, 3054, 3060, 3068, 3072, 3080, 3086, 3090, 3092, 3105, 3108, 3110, 3117, 3130, 3132, 3136, 3143, 3144, 3146, 3150, 3160, 3168, 3186, 3192, 3204, 3209, 3223, 3229, 3230, 3236, 3240, 3252, 3256, 3276, 3279, 3286, 3300, 3304, 3307, 3324, 3326, 3330, 3332, 3333, 3336, 3342, 3346, 3350, 3354, 3360, 3370, 3372, 3398, 3402, 3424, 3430, 3432, 3433, 3452, 3460, 3465, 3466, 3474, 3476, 3482, 3484, 3500, 3504, 3510, 3514, 3520, 3528, 3536, 3544, 3546, 3564, 3576, 3585, 3588, 3589, 3612, 3614, 3622, 3628, 3650, 3654, 3672, 3676, 3678, 3680, 3682, 3685, 3696, 3699, 3726, 3728, 3750, 3757, 3776, 3780, 3781, 3808, 3812, 3818, 3821, 3824, 3826, 3828, 3830, 3844, 3852, 3860, 3861, 3864, 3865, 3872, 3888, 3895, 3906, 3912, 3918, 3922, 3938, 3942, 3944, 3948, 3960, 3971, 3986, 3990, 3993, 3998, 4002, 4004, 4032, 4034, 4042, 4060, 4063, 4090, 4102, 4118, 4124, 4164, 4170, 4182, 4186, 4190, 4194, 4202, 4203, 4212, 4220, 4250, 4261, 4280, 4290, 4292, 4312, 4320, 4326, 4330, 4331, 4334, 4338, 4344, 4356, 4384, 4396, 4398, 4400, 4418, 4424, 4428, 4434, 4440, 4446, 4451, 4470, 4472, 4488, 4510, 4514, 4515, 4528, 4544, 4552, 4560, 4570, 4576, 4590, 4596, 4598, 4608, 4614, 4620, 4634, 4643, 4670, 4698, 4726, 4731, 4758, 4761, 4772, 4778, 4784, 4788, 4804, 4819, 4836, 4839, 4862, 4866, 4879, 4884, 4890, 4894, 4906, 4910, 4947, 4954, 4960, 4962, 4984, 4992, 4994, 5005, 5040, 5048, 5055, 5060, 5104, 5114, 5124, 5130, 5146, 5148, 5152, 5166, 5170, 5178, 5196, 5214, 5215, 5226, 5231, 5236, 5256, 5268, 5282, 5313, 5330, 5332, 5342, 5346, 5350, 5354, 5362, 5366, 5368, 5374, 5384, 5388, 5395, 5396, 5412, 5418, 5421, 5454, 5460, 5488, 5495, 5506, 5526, 5542, 5544, 5578, 5580, 5588, 5591, 5610, 5611, 5624, 5625, 5628, 5642, 5664, 5670, 5680, 5684, 5702, 5704, 5710, 5720, 5728, 5740, 5748, 5757, 5759, 5775, 5802, 5812, 5822, 5830, 5880, 5886, 5896, 5904, 5946, 5983, 6006, 6022, 6032, 6040, 6042, 6046, 6084, 6090, 6114, 6136, 6138, 6154, 6160, 6172, 6174, 6180, 6182, 6188, 6190, 6211, 6220, 6234, 6240, 6280, 6291, 6292, 6300, 6318, 6322, 6330, 6336, 6340, 6350, 6382, 6388, 6422, 6434, 6452, 6458, 6468, 6500, 6528, 6538, 6545, 6582, 6599, 6600, 6636, 6656, 6668, 6676, 6680, 6682, 6687, 6690, 6708, 6721, 6735, 6736, 6760, 6808, 6820, 6853, 6864, 6874, 6902, 6908, 6914, 6920, 6924, 6927, 6928, 6930, 6936, 6944, 6954, 6961, 6974, 6976, 6996, 7004, 7010, 7066, 7068, 7072, 7088, 7106, 7148, 7150, 7152, 7158, 7180, 7186, 7188, 7215, 7224, 7284, 7330, 7364, 7396, 7402, 7407, 7408, 7432, 7460, 7514, 7530, 7532, 7536, 7539, 7568, 7590, 7605, 7620, 7638, 7714, 7722, 7740, 7743, 7752, 7758, 7770, 7778, 7794, 7812, 7814, 7826, 7844, 7865, 7890, 7907, 7920, 7942, 7986, 8008, 8016, 8040, 8072, 8095, 8102, 8120, 8132, 8142, 8172, 8184, 8190, 8200, 8214, 8232, 8246, 8248, 8253, 8286, 8349, 8356, 8364, 8372, 8382, 8400, 8404, 8424, 8482, 8496, 8506, 8520, 8580, 8617, 8624, 8652, 8694, 8732, 8738, 8771, 8788, 8792, 8874, 8887, 8888, 8890, 8904, 8974, 8990, 8994, 9026, 9034, 9052, 9072, 9092, 9152, 9174, 9180, 9182, 9200, 9212, 9240, 9268, 9286, 9303, 9316, 9320, 9361, 9364, 9380, 9386, 9408, 9434, 9450, 9464, 9476, 9499, 9544, 9562, 9566, 9568, 9654, 9674, 9684, 9702, 9714, 9724, 9746, 9750, 9762, 9764, 9782, 9794, 9867, 9889, 10010, 10014, 10020, 10032, 10058, 10100, 10162, 10164, 10172, 10180, 10220, 10274, 10288, 10296, 10330, 10354, 10398, 10462, 10465, 10512, 10530, 10542, 10582, 10626, 10692, 10706, 10750, 10758, 10850, 10858, 10862, 10894, 10920, 10956, 10988, 10996, 11076, 11082, 11088, 11094, 11108, 11190, 11209, 11214, 11277, 11284, 11286, 11288, 11324, 11326, 11332, 11368, 11380, 11440, 11466, 11500, 11506, 11514, 11518, 11520, 11529, 11550, 11560, 11586, 11587, 11600, 11609, 11630, 11698, 11715, 11726, 11760, 11812, 11934, 12004, 12012, 12034, 12050, 12064, 12070, 12116, 12142, 12180, 12184, 12188, 12320, 12324, 12342, 12354, 12376, 12438, 12439, 12452, 12480, 12524, 12540, 12554, 12610, 12612, 12642, 12710, 12754, 12762, 12774, 12776, 12829, 12870, 12936, 12948, 12974, 13038, 13100, 13112, 13149, 13156, 13204, 13224, 13266, 13286, 13307, 13346, 13434, 13470, 13479, 13502, 13504, 13515, 13544, 13702, 13706, 13743, 13754, 13784, 13788, 13936, 14025, 14042, 14070, 14138, 14144, 14190, 14196, 14204, 14244, 14283, 14287, 14300, 14382, 14443, 14504, 14516, 14518, 14586, 14611, 14616, 14740, 14742, 14754, 14762, 14780, 14864, 14904, 14938, 14952, 14996, 15004, 15075, 15080, 15199, 15210, 15246, 15292, 15326, 15327, 15384, 15386, 15444, 15470, 15504, 15519, 15768, 15814, 15840, 15848, 15853, 15854, 15884, 15894, 15928, 15976, 16016, 16058, 16074, 16076, 16113, 16184, 16234, 16236, 16246, 16284, 16364, 16375, 16404, 16470, 16472, 16588, 16662, 16764, 16770, 16796, 16800, 16874, 16980, 16988, 17092, 17094, 17152, 17166, 17184, 17234, 17308, 17398, 17424, 17446, 17472, 17606, 17611, 17674, 17680, 17747, 17754, 17790, 17804, 17822, 18018, 18062, 18094, 18194, 18234, 18242, 18262, 18264, 18326, 18356, 18364, 18456, 18480, 18650, 18674, 18687, 18700, 18740, 18816, 18846, 18898, 18996, 19048, 19149, 19191, 19203, 19272, 19318, 19322, 19430, 19448, 19496, 19500, 19544, 19564, 19675, 19734, 19782, 19884, 20002, 20020, 20110, 20228, 20288, 20332, 20514, 20551, 20566, 20592, 20620, 20666, 20687, 20694, 20760, 20832, 20872, 20930, 21060, 21076, 21097, 21104, 21226, 21252, 21274, 21296, 21359, 21600, 21714, 21718, 21728, 21780, 21786, 21826, 21858, 21944, 22022, 22048, 22268, 22276, 22380, 22516, 22535, 22576, 22594, 22822, 22836, 22850, 22880, 22924, 23088, 23100, 23170, 23256, 23326, 23430, 23524, 23575, 23628, 23679, 23718, 23848, 23894, 23920, 23936, 23966, 23998, 24024, 24154, 24188, 24244, 24296, 24310, 24318, 24390, 24442, 24466, 24498, 24556, 24948, 24954, 24978, 24992, 25066, 25087, 25194, 25220, 25309, 25506, 25650, 25724, 26214, 26384, 26520, 26572, 26686, 26826, 26854, 26938, 26958, 26984, 27040, 27258, 27280, 27398, 27456, 27492, 27540, 27548, 27764, 28028, 28080, 28090, 28180, 28210, 28255, 28424, 28498, 28698, 28724, 28952, 29070, 29080, 29090, 29114, 29318, 29608, 29614, 29854, 29886, 29986, 30046, 30074, 30250, 30284, 30322, 30400, 30475, 30572, 30654, 30822, 30940, 31008, 31174, 31192, 31284, 31384, 31402, 31616, 31856, 31980, 32062, 32162, 32208, 32890, 33000, 33014, 33074, 33118, 33258, 33278, 33344, 33568, 33582, 33585, 33592, 33670, 33926, 33968, 34020, 34400, 34716, 34756, 34944, 34963, 35360, 35442, 35632, 35758, 36006, 36014, 36186, 36244, 36638, 36912, 37076, 37180, 37262, 37290, 37328, 37330, 37400, 37788, 37862, 37902, 37928, 38038, 38170, 38498, 38569, 38760, 38824, 38928, 39092, 39338, 39394, 39468, 39481, 39644, 39676, 39864, 39900, 39968, 39974, 40502, 40604, 40612, 40664, 40874, 41684, 41896, 41990, 41998, 42130, 42246, 42372, 42559, 42644, 43010, 43692, 43780, 43822, 44330, 44638, 44938, 45088, 45220, 45428, 45460, 45494, 45641, 45727, 45804, 45818, 46292, 46484, 46936, 47124, 47872, 48018, 48224, 49114, 49302, 49348, 49720, 49784, 49828, 50012, 50232, 50248, 50324, 50388, 50764, 50807, 51202, 51274, 51434, 52000, 52052, 53228, 53416, 53460, 53944, 54310, 54448, 54640, 54944, 55295, 55462, 56114, 56264, 56628, 56738, 56770, 56848, 56900, 57154, 57198, 57258, 57280, 57356, 57902, 58012, 58786, 58864, 59156, 59410, 60060, 60324, 60586, 60704, 60904, 61732, 62016, 62172, 62348, 62392, 63264, 63388, 63718, 63920, 64286, 66352, 66396, 66660, 68016, 68068, 68368, 68650, 68712, 68874, 69284, 69380, 69738, 70622, 70714, 70850, 71324, 71896, 72344, 73480, 73644, 73832, 74374, 75004, 76628, 76856, 77190, 77722, 77922, 78004, 78672, 79772, 80034, 80952, 81840, 82348, 83390, 83754, 83884, 83980, 84194, 84948, 85748, 86416, 87184, 87210, 87412, 87424, 87788, 87912, 89114, 90222, 90440, 90896, 91644, 92142, 92378, 93092, 93500, 93918, 94424, 95402, 95940, 97790, 98636, 98864, 99534, 100224, 101434, 104682, 105864, 105944, 108044, 108848, 109192, 109376, 110842, 112404, 113256, 113364, 113776, 114308, 114444, 114978, 116688, 117116, 117572, 117810, 117838, 122128, 122660, 122784, 123430, 124864, 125612, 128128, 129784, 131382, 133892, 135442, 136708, 137800, 140198, 140828, 141110, 142120, 142518, 144682, 148492, 149804, 150688, 151402, 152048, 153068, 154726, 156062, 157072, 159580, 162792, 164540, 168602, 169252, 172150, 173316, 175712, 176188, 178898, 180172, 183020, 184756, 186048, 190168, 199256, 200192, 201552, 204216, 208012, 209304, 210188, 212108, 213842, 219640, 226712, 228240, 233376, 234498, 236436, 241384, 250020, 268090, 268736, 269620, 270612, 290632, 301444, 310080, 325364, 325584, 326876, 329680, 369512, 385424, 386308, 409564, 442936, 453492, 477632, 502996, 537472, 537692, 571064, 594320, 650948, 655044, 711008, 742900, 772616, 779076, 863056, 980628, 1188640, 2674440