Monday 14 December 2015

a brief look at sum of prime factors

OK. A fun one today. Well, I think it is fun, a mathematician would call it trivial. Sum of prime factors. Way back I called these things strange-integers, and they served as an early test of my code. Simply enough define:
strange-int[x] = the sum of the prime factors of x.

Say r has prime factorisation:
r = p1^n1 * p2^n2 * p3^n3 * p4^n4 * ...
Then strange-int[r] = p1*n1 + p2*n2 + p3*n3 + p4*n4 + ...
It has these properties:
strange-int[p] = p if p is prime, or p = 4
strange-int[p] < p otherwise
This has the effect that we can form a tree of integers (for the impatient, here is an image of that tree), where each application of strange-int[] steps one step closer to a final prime.

Here are the first twenty:
-- we need this due to a quirk of my code. 
-- where the strange-int on the right hand side is a function-operator in my functions code.
sa: strange-int |*> #=> strange-int |_self>
sa: table[number,strange-int] range(|number: 2>,|number: 20>)
+--------+-------------+
| number | strange-int |
+--------+-------------+
| 2      | 2           |
| 3      | 3           |
| 4      | 4           |
| 5      | 5           |
| 6      | 5           |
| 7      | 7           |
| 8      | 6           |
| 9      | 6           |
| 10     | 7           |
| 11     | 11          |
| 12     | 7           |
| 13     | 13          |
| 14     | 9           |
| 15     | 8           |
| 16     | 8           |
| 17     | 17          |
| 18     | 8           |
| 19     | 19          |
| 20     | 9           |
+--------+-------------+
Next we can take a look using the strange-int-list operator. This maps an integer to a list of integers down to the final prime. Here are the first 30:
sa: strange-int-list |*> #=> strange-int-list |_self>
sa: how-long-is-strange-int-list |*> #=> how-many strange-int-list |_self>
sa: table[number,strange-int,strange-int-list,how-long-is-strange-int-list] range(|number: 2>,|number: 30>)
+--------+-------------+------------------+------------------------------+
| number | strange-int | strange-int-list | how-long-is-strange-int-list |
+--------+-------------+------------------+------------------------------+
| 2      | 2           | 2                | 1                            |
| 3      | 3           | 3                | 1                            |
| 4      | 4           | 4                | 1                            |
| 5      | 5           | 5                | 1                            |
| 6      | 5           | 6, 5             | 2                            |
| 7      | 7           | 7                | 1                            |
| 8      | 6           | 8, 6, 5          | 3                            |
| 9      | 6           | 9, 6, 5          | 3                            |
| 10     | 7           | 10, 7            | 2                            |
| 11     | 11          | 11               | 1                            |
| 12     | 7           | 12, 7            | 2                            |
| 13     | 13          | 13               | 1                            |
| 14     | 9           | 14, 9, 6, 5      | 4                            |
| 15     | 8           | 15, 8, 6, 5      | 4                            |
| 16     | 8           | 16, 8, 6, 5      | 4                            |
| 17     | 17          | 17               | 1                            |
| 18     | 8           | 18, 8, 6, 5      | 4                            |
| 19     | 19          | 19               | 1                            |
| 20     | 9           | 20, 9, 6, 5      | 4                            |
| 21     | 10          | 21, 10, 7        | 3                            |
| 22     | 13          | 22, 13           | 2                            |
| 23     | 23          | 23               | 1                            |
| 24     | 9           | 24, 9, 6, 5      | 4                            |
| 25     | 10          | 25, 10, 7        | 3                            |
| 26     | 15          | 26, 15, 8, 6, 5  | 5                            |
| 27     | 9           | 27, 9, 6, 5      | 4                            |
| 28     | 11          | 28, 11           | 2                            |
| 29     | 29          | 29               | 1                            |
| 30     | 10          | 30, 10, 7        | 3                            |
+--------+-------------+------------------+------------------------------+
Now, lets sort by strange-int-list length, and find the top 100 of those in the first 100,000 integers.
sa: strange-int |*> #=> strange-int |_self>
sa: strange-int-list |*> #=> strange-int-list |_self>
sa: length-of-strange-int-list |*> #=> how-many strange-int-list |_self>
sa: table[number,strange-int,strange-int-list,length-of-strange-int-list] select[1,100] reverse sort-by[length-of-strange-int-list] range(|number: 2>,|number: 100000>)
+--------+-------------+---------------------------------------------------------+----------------------------+
| number | strange-int | strange-int-list                                        | length-of-strange-int-list |
+--------+-------------+---------------------------------------------------------+----------------------------+
| 55694  | 27849       | 55694, 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5 | 12                         |
| 27933  | 9314        | 27933, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5  | 12                         |
| 99895  | 19984       | 99895, 19984, 1257, 422, 213, 74, 39, 16, 8, 6, 5       | 11                         |
| 97629  | 4659        | 97629, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5        | 11                         |
| 97533  | 10843       | 97533, 10843, 1556, 393, 134, 69, 26, 15, 8, 6, 5       | 11                         |
| 92915  | 18588       | 92915, 18588, 1556, 393, 134, 69, 26, 15, 8, 6, 5       | 11                         |
| 90177  | 30062       | 90177, 30062, 15033, 5014, 134, 69, 26, 15, 8, 6, 5     | 11                         |
| 86696  | 10843       | 86696, 10843, 1556, 393, 134, 69, 26, 15, 8, 6, 5       | 11                         |
| 86662  | 43333       | 86662, 43333, 2566, 1285, 262, 133, 26, 15, 8, 6, 5     | 11                         |
| 84934  | 42469       | 84934, 42469, 6074, 3039, 1016, 133, 26, 15, 8, 6, 5    | 11                         |
| 83718  | 4659        | 83718, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5        | 11                         |
| 74924  | 18735       | 74924, 18735, 1257, 422, 213, 74, 39, 16, 8, 6, 5       | 11                         |
| 74416  | 4659        | 74416, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5        | 11                         |
| 69765  | 4659        | 69765, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5        | 11                         |
| 68653  | 5294        | 68653, 5294, 2649, 886, 445, 94, 49, 14, 9, 6, 5        | 11                         |
| 55686  | 9286        | 55686, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5        | 11                         |
| 46405  | 9286        | 46405, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5        | 11                         |
| 46142  | 23073       | 46142, 23073, 7694, 3849, 1286, 645, 51, 20, 9, 6, 5    | 11                         |
| 36398  | 18201       | 36398, 18201, 6070, 614, 309, 106, 55, 16, 8, 6, 5      | 11                         |
| 30993  | 10334       | 30993, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5     | 11                         |
| 27849  | 9286        | 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5        | 11                         |
| 9314   | 4659        | 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5         | 11                         |
| 99853  | 7694        | 99853, 7694, 3849, 1286, 645, 51, 20, 9, 6, 5           | 10                         |
| 99763  | 1556        | 99763, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 10                         |
| 99482  | 49743       | 99482, 49743, 5533, 514, 259, 44, 15, 8, 6, 5           | 10                         |
| 98422  | 49213       | 98422, 49213, 1726, 865, 178, 91, 20, 9, 6, 5           | 10                         |
| 98386  | 49195       | 98386, 49195, 9844, 134, 69, 26, 15, 8, 6, 5            | 10                         |
| 98284  | 24575       | 98284, 24575, 993, 334, 169, 26, 15, 8, 6, 5            | 10                         |
| 98214  | 16374       | 98214, 16374, 2734, 1369, 74, 39, 16, 8, 6, 5           | 10                         |
| 98151  | 32720       | 98151, 32720, 422, 213, 74, 39, 16, 8, 6, 5             | 10                         |
| 97618  | 48811       | 97618, 48811, 393, 134, 69, 26, 15, 8, 6, 5             | 10                         |
| 97209  | 1556        | 97209, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 10                         |
| 96523  | 13796       | 96523, 13796, 3453, 1154, 579, 196, 18, 8, 6, 5         | 10                         |
| 96467  | 13788       | 96467, 13788, 393, 134, 69, 26, 15, 8, 6, 5             | 10                         |
| 95962  | 47983       | 95962, 47983, 3704, 469, 74, 39, 16, 8, 6, 5            | 10                         |
| 95562  | 5317        | 95562, 5317, 422, 213, 74, 39, 16, 8, 6, 5              | 10                         |
| 94593  | 31534       | 94593, 31534, 15769, 1226, 615, 49, 14, 9, 6, 5         | 10                         |
| 94469  | 5574        | 94469, 5574, 934, 469, 74, 39, 16, 8, 6, 5              | 10                         |
| 94426  | 1556        | 94426, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 10                         |
| 94222  | 47113       | 94222, 47113, 4294, 134, 69, 26, 15, 8, 6, 5            | 10                         |
| 93494  | 46749       | 93494, 46749, 15586, 7795, 1564, 44, 15, 8, 6, 5        | 10                         |
| 93414  | 15574       | 93414, 15574, 614, 309, 106, 55, 16, 8, 6, 5            | 10                         |
| 93382  | 46693       | 93382, 46693, 934, 469, 74, 39, 16, 8, 6, 5             | 10                         |
| 92702  | 46353       | 92702, 46353, 15454, 7729, 190, 26, 15, 8, 6, 5         | 10                         |
| 92654  | 46329       | 92654, 46329, 15446, 7725, 116, 33, 14, 9, 6, 5         | 10                         |
| 92244  | 7694        | 92244, 7694, 3849, 1286, 645, 51, 20, 9, 6, 5           | 10                         |
| 92156  | 23043       | 92156, 23043, 7684, 134, 69, 26, 15, 8, 6, 5            | 10                         |
| 91445  | 18294       | 91445, 18294, 3054, 514, 259, 44, 15, 8, 6, 5           | 10                         |
| 91398  | 15238       | 91398, 15238, 422, 213, 74, 39, 16, 8, 6, 5             | 10                         |
| 91285  | 18262       | 91285, 18262, 422, 213, 74, 39, 16, 8, 6, 5             | 10                         |
| 91213  | 1774        | 91213, 1774, 889, 134, 69, 26, 15, 8, 6, 5              | 10                         |
| 91198  | 45601       | 91198, 45601, 1502, 753, 254, 129, 46, 25, 10, 7        | 10                         |
| 89974  | 44989       | 89974, 44989, 6434, 3219, 69, 26, 15, 8, 6, 5           | 10                         |
| 89702  | 44853       | 89702, 44853, 14954, 7479, 286, 26, 15, 8, 6, 5         | 10                         |
| 89222  | 6382        | 89222, 6382, 3193, 134, 69, 26, 15, 8, 6, 5             | 10                         |
| 89038  | 44521       | 89038, 44521, 422, 213, 74, 39, 16, 8, 6, 5             | 10                         |
| 88870  | 8894        | 88870, 8894, 4449, 1486, 745, 154, 20, 9, 6, 5          | 10                         |
| 87985  | 17602       | 87985, 17602, 692, 177, 62, 33, 14, 9, 6, 5             | 10                         |
| 87938  | 43971       | 87938, 43971, 14660, 742, 62, 33, 14, 9, 6, 5           | 10                         |
| 87554  | 43779       | 87554, 43779, 14596, 134, 69, 26, 15, 8, 6, 5           | 10                         |
| 87222  | 14542       | 87222, 14542, 674, 339, 116, 33, 14, 9, 6, 5            | 10                         |
| 86934  | 14494       | 86934, 14494, 7249, 670, 74, 39, 16, 8, 6, 5            | 10                         |
| 86408  | 1556        | 86408, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 10                         |
| 85983  | 28664       | 85983, 28664, 3589, 134, 69, 26, 15, 8, 6, 5            | 10                         |
| 85686  | 14286       | 85686, 14286, 2386, 1195, 244, 65, 18, 8, 6, 5          | 10                         |
| 85497  | 28502       | 85497, 28502, 14253, 4754, 2379, 77, 18, 8, 6, 5        | 10                         |
| 85317  | 28442       | 85317, 28442, 14223, 445, 94, 49, 14, 9, 6, 5           | 10                         |
| 85299  | 28436       | 85299, 28436, 7113, 2374, 1189, 70, 14, 9, 6, 5         | 10                         |
| 84944  | 5317        | 84944, 5317, 422, 213, 74, 39, 16, 8, 6, 5              | 10                         |
| 84939  | 1257        | 84939, 1257, 422, 213, 74, 39, 16, 8, 6, 5              | 10                         |
| 84684  | 7064        | 84684, 7064, 889, 134, 69, 26, 15, 8, 6, 5              | 10                         |
| 83686  | 41845       | 83686, 41845, 8374, 134, 69, 26, 15, 8, 6, 5            | 10                         |
| 83466  | 4645        | 83466, 4645, 934, 469, 74, 39, 16, 8, 6, 5              | 10                         |
| 83374  | 41689       | 83374, 41689, 934, 469, 74, 39, 16, 8, 6, 5             | 10                         |
| 83282  | 41643       | 83282, 41643, 674, 339, 116, 33, 14, 9, 6, 5            | 10                         |
| 82556  | 20643       | 82556, 20643, 993, 334, 169, 26, 15, 8, 6, 5            | 10                         |
| 81845  | 16374       | 81845, 16374, 2734, 1369, 74, 39, 16, 8, 6, 5           | 10                         |
| 80381  | 11490       | 80381, 11490, 393, 134, 69, 26, 15, 8, 6, 5             | 10                         |
| 80269  | 11474       | 80269, 11474, 5739, 1916, 483, 33, 14, 9, 6, 5          | 10                         |
| 79635  | 5317        | 79635, 5317, 422, 213, 74, 39, 16, 8, 6, 5              | 10                         |
| 79302  | 13222       | 79302, 13222, 614, 309, 106, 55, 16, 8, 6, 5            | 10                         |
| 79146  | 4405        | 79146, 4405, 886, 445, 94, 49, 14, 9, 6, 5              | 10                         |
| 78747  | 26252       | 78747, 26252, 6567, 213, 74, 39, 16, 8, 6, 5            | 10                         |
| 78609  | 26206       | 78609, 26206, 13105, 2626, 116, 33, 14, 9, 6, 5         | 10                         |
| 78502  | 39253       | 78502, 39253, 2326, 1165, 238, 26, 15, 8, 6, 5          | 10                         |
| 78362  | 39183       | 78362, 39183, 393, 134, 69, 26, 15, 8, 6, 5             | 10                         |
| 78038  | 39021       | 78038, 39021, 13010, 1308, 116, 33, 14, 9, 6, 5         | 10                         |
| 77845  | 15574       | 77845, 15574, 614, 309, 106, 55, 16, 8, 6, 5            | 10                         |
| 77709  | 25906       | 77709, 25906, 12955, 2596, 74, 39, 16, 8, 6, 5          | 10                         |
| 77642  | 38823       | 77642, 38823, 12944, 817, 62, 33, 14, 9, 6, 5           | 10                         |
| 77396  | 1774        | 77396, 1774, 889, 134, 69, 26, 15, 8, 6, 5              | 10                         |
| 77391  | 8605        | 77391, 8605, 1726, 865, 178, 91, 20, 9, 6, 5            | 10                         |
| 77289  | 25766       | 77289, 25766, 1006, 505, 106, 55, 16, 8, 6, 5           | 10                         |
| 77109  | 25706       | 77109, 25706, 12855, 865, 178, 91, 20, 9, 6, 5          | 10                         |
| 76870  | 7694        | 76870, 7694, 3849, 1286, 645, 51, 20, 9, 6, 5           | 10                         |
| 76363  | 10916       | 76363, 10916, 2733, 914, 459, 26, 15, 8, 6, 5           | 10                         |
| 76338  | 4249        | 76338, 4249, 614, 309, 106, 55, 16, 8, 6, 5             | 10                         |
| 76165  | 15238       | 76165, 15238, 422, 213, 74, 39, 16, 8, 6, 5             | 10                         |
| 75722  | 37863       | 75722, 37863, 614, 309, 106, 55, 16, 8, 6, 5            | 10                         |
| 74192  | 4645        | 74192, 4645, 934, 469, 74, 39, 16, 8, 6, 5              | 10                         |
+--------+-------------+---------------------------------------------------------+----------------------------+
So it seems, in the first 100,000 integers, 55,694 and 27,933 are in some sense "the least prime", taking 12 steps of strange-int to reach a destination prime. And 91,198 is the only one in the top 100 that has 7 as the final prime instead of 5.

Now, let's upscale to the first 1,000,000 integers (I tried 10,000,000 but python seg-faulted at 1.4 million).
sa: strange-int-list |*> #=> strange-int-list |_self>
sa: length-of-strange-int-list |*> #=> how-many strange-int-list |_self>
sa: table[number,strange-int-list,length-of-strange-int-list] select[1,100] reverse sort-by[length-of-strange-int-list] range(|number: 2>,|number: 1000000>)
+--------+-------------------------------------------------------------------------+----------------------------+
| number | strange-int-list                                                        | length-of-strange-int-list |
+--------+-------------------------------------------------------------------------+----------------------------+
| 334142 | 334142, 167073, 55694, 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5 | 14                         |
| 921327 | 921327, 27933, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5          | 13                         |
| 868022 | 868022, 434013, 144674, 72339, 24116, 6033, 2014, 74, 39, 16, 8, 6, 5   | 13                         |
| 823502 | 823502, 411753, 137254, 5294, 2649, 886, 445, 94, 49, 14, 9, 6, 5       | 13                         |
| 723853 | 723853, 55694, 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5         | 13                         |
| 167073 | 167073, 55694, 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5         | 13                         |
| 999593 | 999593, 142806, 23806, 11905, 2386, 1195, 244, 65, 18, 8, 6, 5          | 12                         |
| 991456 | 991456, 30993, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5             | 12                         |
| 982503 | 982503, 36398, 18201, 6070, 614, 309, 106, 55, 16, 8, 6, 5              | 12                         |
| 959566 | 959566, 479785, 95962, 47983, 3704, 469, 74, 39, 16, 8, 6, 5            | 12                         |
| 945958 | 945958, 36398, 18201, 6070, 614, 309, 106, 55, 16, 8, 6, 5              | 12                         |
| 944206 | 944206, 472105, 94426, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 12                         |
| 929490 | 929490, 30993, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5             | 12                         |
| 922660 | 922660, 46142, 23073, 7694, 3849, 1286, 645, 51, 20, 9, 6, 5            | 12                         |
| 912805 | 912805, 182566, 91285, 18262, 422, 213, 74, 39, 16, 8, 6, 5             | 12                         |
| 904603 | 904603, 129236, 32313, 10774, 5389, 334, 169, 26, 15, 8, 6, 5           | 12                         |
| 896734 | 896734, 448369, 15490, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 12                         |
| 892578 | 892578, 148768, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5               | 12                         |
| 892569 | 892569, 297526, 148765, 29758, 14881, 670, 74, 39, 16, 8, 6, 5          | 12                         |
| 888542 | 888542, 444273, 148094, 74049, 24686, 12345, 831, 280, 18, 8, 6, 5      | 12                         |
| 887613 | 887613, 295874, 147939, 4497, 1502, 753, 254, 129, 46, 25, 10, 7        | 12                         |
| 882202 | 882202, 441103, 33944, 4249, 614, 309, 106, 55, 16, 8, 6, 5             | 12                         |
| 873336 | 873336, 36398, 18201, 6070, 614, 309, 106, 55, 16, 8, 6, 5              | 12                         |
| 866890 | 866890, 86696, 10843, 1556, 393, 134, 69, 26, 15, 8, 6, 5               | 12                         |
| 864627 | 864627, 288212, 72057, 24022, 12013, 334, 169, 26, 15, 8, 6, 5          | 12                         |
| 837277 | 837277, 119618, 59811, 19940, 1006, 505, 106, 55, 16, 8, 6, 5           | 12                         |
| 780437 | 780437, 111498, 18588, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 12                         |
| 774575 | 774575, 30993, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5             | 12                         |
| 745717 | 745717, 106538, 53271, 1982, 993, 334, 169, 26, 15, 8, 6, 5             | 12                         |
| 743815 | 743815, 148768, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5               | 12                         |
| 735006 | 735006, 122506, 61255, 12256, 393, 134, 69, 26, 15, 8, 6, 5             | 12                         |
| 727780 | 727780, 36398, 18201, 6070, 614, 309, 106, 55, 16, 8, 6, 5              | 12                         |
| 723749 | 723749, 55686, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5                | 12                         |
| 719214 | 719214, 119874, 19984, 1257, 422, 213, 74, 39, 16, 8, 6, 5              | 12                         |
| 697062 | 697062, 116182, 5294, 2649, 886, 445, 94, 49, 14, 9, 6, 5               | 12                         |
| 688958 | 688958, 344481, 114830, 11490, 393, 134, 69, 26, 15, 8, 6, 5            | 12                         |
| 674593 | 674593, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                 | 12                         |
| 668958 | 668958, 111498, 18588, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 12                         |
| 650643 | 650643, 30993, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5             | 12                         |
| 645862 | 645862, 46142, 23073, 7694, 3849, 1286, 645, 51, 20, 9, 6, 5            | 12                         |
| 638782 | 638782, 319393, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5            | 12                         |
| 638422 | 638422, 319213, 5294, 2649, 886, 445, 94, 49, 14, 9, 6, 5               | 12                         |
| 631924 | 631924, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                 | 12                         |
| 613628 | 613628, 153411, 51140, 2566, 1285, 262, 133, 26, 15, 8, 6, 5            | 12                         |
| 612505 | 612505, 122506, 61255, 12256, 393, 134, 69, 26, 15, 8, 6, 5             | 12                         |
| 609218 | 609218, 304611, 101540, 5086, 2545, 514, 259, 44, 15, 8, 6, 5           | 12                         |
| 606823 | 606823, 86696, 10843, 1556, 393, 134, 69, 26, 15, 8, 6, 5               | 12                         |
| 601113 | 601113, 200374, 5294, 2649, 886, 445, 94, 49, 14, 9, 6, 5               | 12                         |
| 599345 | 599345, 119874, 19984, 1257, 422, 213, 74, 39, 16, 8, 6, 5              | 12                         |
| 592684 | 592684, 148175, 5937, 1982, 993, 334, 169, 26, 15, 8, 6, 5              | 12                         |
| 587427 | 587427, 195812, 48957, 16322, 8163, 913, 94, 49, 14, 9, 6, 5            | 12                         |
| 580885 | 580885, 116182, 5294, 2649, 886, 445, 94, 49, 14, 9, 6, 5               | 12                         |
| 575422 | 575422, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                 | 12                         |
| 568983 | 568983, 189664, 5937, 1982, 993, 334, 169, 26, 15, 8, 6, 5              | 12                         |
| 568196 | 568196, 142053, 47354, 23679, 886, 445, 94, 49, 14, 9, 6, 5             | 12                         |
| 557465 | 557465, 111498, 18588, 1556, 393, 134, 69, 26, 15, 8, 6, 5              | 12                         |
| 538414 | 538414, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                 | 12                         |
| 533198 | 533198, 266601, 88870, 8894, 4449, 1486, 745, 154, 20, 9, 6, 5          | 12                         |
| 509446 | 509446, 36398, 18201, 6070, 614, 309, 106, 55, 16, 8, 6, 5              | 12                         |
| 496966 | 496966, 248485, 49702, 24853, 886, 445, 94, 49, 14, 9, 6, 5             | 12                         |
| 471633 | 471633, 157214, 78609, 26206, 13105, 2626, 116, 33, 14, 9, 6, 5         | 12                         |
| 458187 | 458187, 152732, 38187, 4249, 614, 309, 106, 55, 16, 8, 6, 5             | 12                         |
| 446466 | 446466, 74416, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                | 12                         |
| 434013 | 434013, 144674, 72339, 24116, 6033, 2014, 74, 39, 16, 8, 6, 5           | 12                         |
| 424113 | 424113, 141374, 70689, 23566, 11785, 2362, 1183, 33, 14, 9, 6, 5        | 12                         |
| 417591 | 417591, 46405, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5                | 12                         |
| 411753 | 411753, 137254, 5294, 2649, 886, 445, 94, 49, 14, 9, 6, 5               | 12                         |
| 401614 | 401614, 200809, 28694, 14349, 4786, 2395, 484, 26, 15, 8, 6, 5          | 12                         |
| 390914 | 390914, 195459, 5937, 1982, 993, 334, 169, 26, 15, 8, 6, 5              | 12                         |
| 372055 | 372055, 74416, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                | 12                         |
| 371192 | 371192, 46405, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5                | 12                         |
| 367509 | 367509, 122506, 61255, 12256, 393, 134, 69, 26, 15, 8, 6, 5             | 12                         |
| 360692 | 360692, 90177, 30062, 15033, 5014, 134, 69, 26, 15, 8, 6, 5             | 12                         |
| 353134 | 353134, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                 | 12                         |
| 343249 | 343249, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                 | 12                         |
| 334086 | 334086, 55686, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5                | 12                         |
| 306818 | 306818, 153411, 51140, 2566, 1285, 262, 133, 26, 15, 8, 6, 5            | 12                         |
| 287773 | 287773, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                 | 12                         |
| 279044 | 279044, 69765, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                | 12                         |
| 278405 | 278405, 55686, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5                | 12                         |
| 268342 | 268342, 134173, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5            | 12                         |
| 260079 | 260079, 86696, 10843, 1556, 393, 134, 69, 26, 15, 8, 6, 5               | 12                         |
| 223239 | 223239, 74416, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                | 12                         |
| 139526 | 139526, 69765, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                | 12                         |
| 55694  | 55694, 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5                 | 12                         |
| 27933  | 27933, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5                  | 12                         |
| 999242 | 999242, 499623, 166544, 1502, 753, 254, 129, 46, 25, 10, 7              | 11                         |
| 998454 | 998454, 166414, 83209, 11894, 334, 169, 26, 15, 8, 6, 5                 | 11                         |
| 995216 | 995216, 62209, 8894, 4449, 1486, 745, 154, 20, 9, 6, 5                  | 11                         |
| 994966 | 994966, 71078, 5086, 2545, 514, 259, 44, 15, 8, 6, 5                    | 11                         |
| 994822 | 994822, 497413, 71066, 35535, 134, 69, 26, 15, 8, 6, 5                  | 11                         |
| 994094 | 994094, 497049, 23679, 886, 445, 94, 49, 14, 9, 6, 5                    | 11                         |
| 993838 | 993838, 496921, 6070, 614, 309, 106, 55, 16, 8, 6, 5                    | 11                         |
| 993189 | 993189, 331066, 165535, 33112, 4145, 834, 144, 14, 9, 6, 5              | 11                         |
| 992778 | 992778, 165468, 13796, 3453, 1154, 579, 196, 18, 8, 6, 5                | 11                         |
| 992202 | 992202, 165372, 13788, 393, 134, 69, 26, 15, 8, 6, 5                    | 11                         |
| 990816 | 990816, 10334, 5169, 1726, 865, 178, 91, 20, 9, 6, 5                    | 11                         |
| 990588 | 990588, 82556, 20643, 993, 334, 169, 26, 15, 8, 6, 5                    | 11                         |
| 989593 | 989593, 89974, 44989, 6434, 3219, 69, 26, 15, 8, 6, 5                   | 11                         |
| 989513 | 989513, 141366, 23566, 11785, 2362, 1183, 33, 14, 9, 6, 5               | 11                         |
+--------+-------------------------------------------------------------------------+----------------------------+
I guess one observation to make here is that length-of-strange-int-list grows rather slowly. And that 334,142 is in some sense the least prime.

Plenty more way's to slice and dice strange-ints. eg, count how many integers map to a given prime. Here is a simple example, making use of strange-int-prime that maps numbers to their primes:
-- show strange-int-prime in use:
sa: strange-int-prime |number: 55694>
|number: 5>
sa: strange-int-prime |number: 91198>
|number: 7>

-- now count the strange-int-primes:
sa: table[number,coeff] strange-int-prime range(|number: 2>,|number: 20>)
+--------+-------+
| number | coeff |
+--------+-------+
| 2      | 1     |
| 3      | 1     |
| 4      | 1     |
| 5      | 9     |
| 7      | 3     |
| 11     | 1     |
| 13     | 1     |
| 17     | 1     |
| 19     | 1     |
+--------+-------+
Now upscale to 100,000 and sort:
sa: table[number,coeff] select[1,100] coeff-sort strange-int-prime range(|number: 2>,|number: 100000>)
+--------+-------+
| number | coeff |
+--------+-------+
| 5      | 27023 |
| 7      | 15753 |
| 13     | 6821  |
| 11     | 6032  |
| 19     | 3837  |
| 17     | 3146  |
| 23     | 2289  |
| 31     | 1497  |
| 29     | 1194  |
| 43     | 1161  |
| 37     | 937   |
| 47     | 792   |
| 41     | 747   |
| 61     | 719   |
| 73     | 658   |
| 53     | 626   |
| 59     | 477   |
| 103    | 463   |
| 109    | 445   |
| 67     | 444   |
| 71     | 444   |
| 83     | 405   |
| 79     | 401   |
| 113    | 354   |
| 89     | 348   |
| 139    | 326   |
| 101    | 325   |
| 107    | 316   |
| 151    | 275   |
| 131    | 247   |
| 97     | 246   |
| 181    | 226   |
| 127    | 218   |
| 137    | 208   |
| 167    | 207   |
| 199    | 207   |
| 149    | 206   |
| 193    | 202   |
| 229    | 190   |
| 173    | 185   |
| 163    | 177   |
| 157    | 175   |
| 197    | 174   |
| 241    | 164   |
| 179    | 157   |
| 191    | 143   |
| 283    | 129   |
| 239    | 127   |
| 271    | 126   |
| 233    | 124   |
| 211    | 121   |
| 257    | 119   |
| 227    | 117   |
| 313    | 116   |
| 281    | 115   |
| 293    | 99    |
| 251    | 97    |
| 263    | 97    |
| 277    | 95    |
| 269    | 94    |
| 317    | 92    |
| 223    | 90    |
| 349    | 86    |
| 383    | 70    |
| 311    | 67    |
| 463    | 66    |
| 307    | 61    |
| 373    | 61    |
| 367    | 60    |
| 421    | 60    |
| 353    | 59    |
| 359    | 58    |
| 401    | 58    |
| 433    | 58    |
| 331    | 56    |
| 523    | 56    |
| 347    | 55    |
| 619    | 55    |
| 397    | 54    |
| 443    | 54    |
| 337    | 53    |
| 389    | 51    |
| 379    | 50    |
| 449    | 50    |
| 467    | 48    |
| 503    | 48    |
| 409    | 46    |
| 457    | 44    |
| 571    | 44    |
| 661    | 44    |
| 431    | 43    |
| 461    | 43    |
| 509    | 42    |
| 601    | 42    |
| 439    | 41    |
| 479    | 41    |
| 617    | 38    |
| 613    | 37    |
| 419    | 35    |
| 491    | 35    |
+--------+-------+
Now, upscale to 500,000:
sa: table[number,coeff] select[1,100] coeff-sort strange-int-prime range(|number: 2>,|number: 500000>)
+--------+--------+
| number | coeff  |
+--------+--------+
| 5      | 133689 |
| 7      | 76847  |
| 13     | 33690  |
| 11     | 29661  |
| 19     | 18500  |
| 17     | 15111  |
| 23     | 11463  |
| 31     | 7730   |
| 29     | 6187   |
| 43     | 5479   |
| 37     | 4444   |
| 47     | 3879   |
| 41     | 3849   |
| 61     | 3503   |
| 73     | 3263   |
| 53     | 3096   |
| 103    | 2308   |
| 67     | 2304   |
| 109    | 2105   |
| 59     | 2097   |
| 71     | 2071   |
| 83     | 1926   |
| 79     | 1925   |
| 113    | 1655   |
| 139    | 1608   |
| 89     | 1607   |
| 107    | 1457   |
| 101    | 1278   |
| 151    | 1155   |
| 97     | 1148   |
| 181    | 1045   |
| 131    | 1022   |
| 199    | 991    |
| 193    | 955    |
| 137    | 903    |
| 229    | 901    |
| 167    | 889    |
| 173    | 852    |
| 157    | 821    |
| 197    | 821    |
| 127    | 795    |
| 163    | 787    |
| 149    | 784    |
| 179    | 771    |
| 241    | 748    |
| 233    | 708    |
| 283    | 686    |
| 191    | 660    |
| 271    | 652    |
| 313    | 650    |
| 281    | 616    |
| 227    | 615    |
| 239    | 591    |
| 263    | 569    |
| 211    | 559    |
| 257    | 558    |
| 251    | 538    |
| 277    | 530    |
| 317    | 516    |
| 269    | 499    |
| 223    | 484    |
| 349    | 467    |
| 293    | 459    |
| 311    | 450    |
| 421    | 412    |
| 463    | 412    |
| 353    | 399    |
| 383    | 397    |
| 359    | 386    |
| 433    | 381    |
| 401    | 375    |
| 307    | 374    |
| 389    | 366    |
| 337    | 359    |
| 373    | 350    |
| 467    | 347    |
| 379    | 346    |
| 619    | 345    |
| 347    | 339    |
| 397    | 330    |
| 331    | 327    |
| 449    | 320    |
| 523    | 316    |
| 367    | 315    |
| 443    | 302    |
| 509    | 298    |
| 461    | 293    |
| 661    | 290    |
| 439    | 288    |
| 419    | 284    |
| 409    | 283    |
| 571    | 272    |
| 601    | 268    |
| 479    | 264    |
| 491    | 263    |
| 431    | 262    |
| 503    | 257    |
| 457    | 256    |
| 643    | 255    |
| 617    | 245    |
+--------+--------+
And I guess we can ask the question, does this ordering of primes (5,7,13,11,19,17,23,31,29,43,37,...) stabilize as n -> infinity? I suspect it just might. OK. I had a closer look with more examples, and it might and it might not. If it does, it would provide a kind of natural ordering of primes. Whatever use that may be.
n from 2 to 100,000 gives this ordering:
5,7,13,11,19,17,23,31,29,43,37,47,41,61,73,53,59,103,109,67,71,83,79,113,89,139,101,107,151,131,97,...

n from 2 to 500,000 gives this ordering:
5,7,13,11,19,17,23,31,29,43,37,47,41,61,73,53,103,67,109,59,71,83,79,113,139,89,107,101,151,97,181,... 

n from 500,000 to 1,000,000 gives this ordering:
5,7,13,11,19,17,23,31,29,43,37,41,47,61,73,53,103,71,109,67,59,83,79,113,139,89,107,101,151,97,181,...

n from 1,000,000 to 1,500,000 gives this ordering:
5,7,13,11,19,17,23,31,29,43,37,47,41,61,73,53,59,103,67,71,109,83,79,113,89,107,139,101,151,181,97,...
Next, we can use strange-int-prime to define an equivalency class:
x is in [p] if strange-int-prime[x] = p
Now, in BKO:
-- find strange-int-primes:
sa: strange-int-prime-op |*> #=> strange-int-prime |_self>
sa: map[strange-int-prime-op,strange-int-prime] range(|number: 2>,|number: 1000>)

-- find inverse-strange-int-primes:
sa: find-inverse[strange-int-prime]

-- find primes:
sa: is-prime-op |*> #=> is-prime |_self>
sa: map[is-prime-op,is-prime] range(|number: 2>,|number: 1000>)

-- find inverse-primes:
sa: find-inverse[is-prime]

-- for display reasons, just want the first 25 inverse-strange-int-primes:
sa: inverse-strange-int-prime-list |*> #=> select[1,25] inverse-strange-int-prime |_self>

-- now our pretty table:
sa: table[prime,inverse-strange-int-prime-list] select[1,75] inverse-is-prime |yes>
+-------+---------------------------------------------------------------------------------------------------------------------------+
| prime | inverse-strange-int-prime-list                                                                                            |
+-------+---------------------------------------------------------------------------------------------------------------------------+
| 2     | 2                                                                                                                         |
| 3     | 3                                                                                                                         |
| 5     | 5, 6, 8, 9, 14, 15, 16, 18, 20, 24, 26, 27, 33, 39, 44, 49, 51, 55, 62, 65, 66, 69, 70, 74, 77                            |
| 7     | 7, 10, 12, 21, 25, 30, 32, 35, 36, 38, 42, 46, 50, 60, 64, 68, 72, 81, 87, 124, 129, 141, 152, 155, 158                   |
| 11    | 11, 28, 40, 45, 48, 54, 86, 111, 115, 138, 164, 187, 215, 218, 226, 249, 258, 266, 287, 319, 329, 338, 380, 391, 407      |
| 13    | 13, 22, 56, 57, 63, 75, 80, 85, 90, 96, 102, 108, 121, 122, 146, 159, 166, 182, 212, 236, 260, 284, 308, 312, 314         |
| 17    | 17, 52, 88, 99, 147, 175, 194, 210, 224, 235, 250, 252, 282, 300, 320, 346, 360, 384, 405, 415, 432, 451, 466, 486, 498   |
| 19    | 19, 34, 93, 104, 117, 145, 165, 174, 176, 198, 245, 253, 289, 294, 303, 326, 350, 356, 420, 448, 452, 494, 500, 502, 504  |
| 23    | 23, 76, 136, 153, 219, 273, 302, 325, 355, 385, 390, 416, 426, 462, 468, 542, 550, 596, 655, 660, 686, 704, 706, 766, 786 |
| 29    | 29, 184, 207, 399, 475, 507, 543, 570, 595, 608, 684, 714, 715, 794, 847, 850, 858, 895                                   |
| 31    | 31, 58, 265, 318, 345, 368, 414, 517, 526, 561, 665, 697, 798, 833, 841, 845, 950                                         |
| 37    | 37, 248, 279, 435, 464, 522, 554, 759, 866, 867                                                                           |
| 41    | 41, 148, 651, 775, 930, 992                                                                                               |
| 43    | 43, 82, 237, 296, 333, 662, 781, 879, 932, 957                                                                            |
| 47    | 47, 172, 328, 369, 734, 777, 835, 925                                                                                     |
| 53    | 53, 376, 423, 842, 903                                                                                                    |
| 59    | 59, 424, 477                                                                                                              |
| 61    | 61, 118, 565, 678, 795, 848, 954                                                                                          |
| 67    | 67, 488, 549, 885, 944                                                                                                    |
| 71    | 71, 268                                                                                                                   |
| 73    | 73, 142, 417, 536, 603, 685, 822                                                                                          |
| 79    | 79, 584, 657                                                                                                              |
| 83    | 83, 316, 939                                                                                                              |
| 89    | 89, 664, 747                                                                                                              |
| 97    | 97                                                                                                                        |
| 101   | 101, 388                                                                                                                  |
| 103   | 103, 202, 597, 776, 873, 985                                                                                              |
| 107   | 107, 412, 808, 909                                                                                                        |
| 109   | 109, 214, 633, 824, 927                                                                                                   |
| 113   | 113, 436, 856, 963                                                                                                        |
| 127   | 127                                                                                                                       |
| 131   | 131, 508                                                                                                                  |
| 137   | 137                                                                                                                       |
| 139   | 139, 274, 813                                                                                                             |
| 149   | 149                                                                                                                       |
| 151   | 151, 298                                                                                                                  |
| 157   | 157                                                                                                                       |
| 163   | 163                                                                                                                       |
| 167   | 167, 652                                                                                                                  |
| 173   | 173                                                                                                                       |
| 179   | 179                                                                                                                       |
| 181   | 181, 358                                                                                                                  |
| 191   | 191                                                                                                                       |
| 193   | 193, 382                                                                                                                  |
| 197   | 197, 772                                                                                                                  |
| 199   | 199, 394                                                                                                                  |
| 211   | 211                                                                                                                       |
| 223   | 223                                                                                                                       |
| 227   | 227, 892                                                                                                                  |
| 229   | 229, 454                                                                                                                  |
| 233   | 233, 916                                                                                                                  |
| 239   | 239                                                                                                                       |
| 241   | 241, 478                                                                                                                  |
| 251   | 251                                                                                                                       |
| 257   | 257                                                                                                                       |
| 263   | 263                                                                                                                       |
| 269   | 269                                                                                                                       |
| 271   | 271, 538                                                                                                                  |
| 277   | 277                                                                                                                       |
| 281   | 281                                                                                                                       |
| 283   | 283, 562                                                                                                                  |
| 293   | 293                                                                                                                       |
| 307   | 307                                                                                                                       |
| 311   | 311                                                                                                                       |
| 313   | 313, 622                                                                                                                  |
| 317   | 317                                                                                                                       |
| 331   | 331                                                                                                                       |
| 337   | 337                                                                                                                       |
| 347   | 347                                                                                                                       |
| 349   | 349, 694                                                                                                                  |
| 353   | 353                                                                                                                       |
| 359   | 359                                                                                                                       |
| 367   | 367                                                                                                                       |
| 373   | 373                                                                                                                       |
| 379   | 379                                                                                                                       |
+-------+---------------------------------------------------------------------------------------------------------------------------+
The interpretation being all elements in the second column are members of the strange-int-prime equivalency class of the prime in the first column.

Finally, let's visualize our sum-of-prime factor tree:
sa: context sum of prime factors
sa: SoPF-op |*> #=> extract-value strange-int merge-labels(|number: > + |_self>)
sa: map[SoPF-op,SoPF] range(|2>,|1000>)
sa: save sum-of-prime-factors.sw
sa: q

$ ./sw2dot-v2.py sw-examples/sum-of-prime-factors.sw
Then open graph-examples/sum-of-prime-factors.dot with graphviz, producing:

NB: the picture is too large to see here, so click on it to see the full, but pretty, tree.

Anyway, the point of this post is not just about strange-ints. It is more about giving some examples of how you can slice and dice knowledge using the knowledge engine.

No comments:

Post a Comment