﻿ Stack sorting and fertility numbers

# Stack sorting and fertility numbers

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 $complement(or(3, prime(n)))$ pkuq41hywvgv

I got a bit curious about the problem itself, specifically how to generate more fertility numbers to verify this formula.

## Variant of Knuths stack sorting

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,

1. Create a stack, an input and output queue.
2. Fill the input queue with a string e.g. “4312”
3. If the stack is empty or the top is greater than the front of the input queue - push input onto the stack, else pop the stack to the output queue.
4. Repeat 3 until the input has moved to the output queue.

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.

## Fertility numbers

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 $3!=6$) 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

$Catalan(3)=5$

Hence, at least, every catalan number is a fertility number.

## A map to capture fertility numbers

To collect fertility numbers we can map every distinct output permutation to the number of occurrences, a histogram if you will. Something like
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 $n$ 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.

## Proven fertility numbers

Colin Defant, the author of Fertility Numbers [1] has proven that

• Every nonnegative integer that is not congruent to 3 modulo 4 is a fertility number.

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.

## Infertile numbers

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 $complement(or(3, p(n)))$ is $or(3, p(n))$ 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).

## Discovering new fertile numbers

To check how far the discovered formula holds for the fertility numbers I wrote a program that examined all permutations up to and including $n=14$, 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 $n=15$ , 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, …

#### Discovered fertile numbers

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

#### Discovered fertile numbers congruent 3 mod 4

27, 39, 51, 63, 95

#### Possibly discovered infertile numbers

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

#### Union of discovered fertile numbers and numbers not congruent 3 mod 4

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

#### Possibly infertile numbers

3, 7, 11, 15, 19, 23, 31, 35, 43, 47, 55, 59, 67, 71, 75, 79, 83, 87, 91, 99

## Conclusions

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 $complement(or(3, prime(n))$.

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 ($\approx0.761793$) 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:

$density=\frac{3}{4} +\frac{1}{4*27}+\frac{1}{4*39}+\frac{1}{4*51}+\frac{1}{4*63}+\frac{1}{4*95}-\frac{1}{4*27*39*51*63*95}\approx0.77717$

Plugging in all 149 fertile numbers congruent 3 mod 4 discovered in the search (see Appendix) we get the density
$density\approx0.80815$

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.

## References

[1] C. Defant, 2018, Fertility numbers

## Appendix

### Code repository

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 $n=15$, let me know if you are willing to help out!

### All discovered fertile numbers congruent 3 mod 4

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

### All discovered fertile numbers

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