/
prog.pl
54 lines (34 loc) · 9.39 KB
/
prog.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#!/usr/bin/perl
# a(n) is the smallest x such that prime(x) mod composite(x) = n, where prime(j) is the j-th prime, composite(j) is the j-th composite number.
# https://oeis.org/A073324
use 5.014;
use ntheory qw(:all);
use experimental qw(signatures);
#~ a(n) = my(p=2); forcomposite(c=4, oo, if(p % c == n, return(primepi(p))); p = nextprime(p+1));
sub a ($n) {
my $p = 2;
foreach my $c(4..1e12) {
if (!is_prime($c)) {
if ($p % $c == $n) {
return prime_count($p);
}
$p = next_prime($p);
}
}
}
# a(51) = 129
# a(52) = 1434
# a(53) = 38
# a(55) = 1411
local $| = 1;
foreach my $n(1..23) {
print(a($n), ", ");
#say "$n ", a($n);
}
__END__
# Terms for n = 1..257:
5, 1, 2, 8, 3, 242, 4, 245, 100, 8313, 10, 50190, 23, 8338, 3390, 12, 24, 308926, 13, 49, 25, 15, 26, 12556637, 112, 55, 117, 58, 56, 1400, 59, 265, 122, 267, 31, 12556641, 603, 270, 33, 12556639, 126, 272, 65, 66, 127, 63, 35, 50270, 37, 1413, 129, 1434, 38, 1411, 39, 280, 134, 68, 620, 50424, 136, 1440, 281, 70, 69, 1443, 138, 1430, 139, 73, 76, 283, 74, 77, 141, 50261, 79, 50243, 78, 1445, 142, 285, 146, 50376, 82, 81, 50326, 84, 83, 50287, 85, 86, 147, 50248, 87, 297, 644, 50333, 155, 88, 89, 50320, 157, 308, 50340, 305, 306, 50337, 158, 92, 1475, 300, 159, 1473, 93, 94, 162, 310, 96, 1514, 95, 97, 164, 317, 165, 313, 99, 325, 1491, 1476, 167, 1488, 168, 320, 1497, 8383, 660, 82013133, 655, 8414, 169, 1523, 171, 327, 174, 1520, 173, 8423, 176, 82012985, 3506, 308965, 183, 308973, 182, 1525, 186, 330, 181, 1527, 331, 1532, 328, 1954049, 1528, 50499, 691, 334, 333, 308963, 335, 332, 191, 12556671, 190, 344, 3543, 1954094, 192, 1547, 349, 336, 193, 355, 1537, 358, 348, 360, 194, 1556, 195, 352, 196, 346, 3559, 50486, 361, 82013089, 202, 50507, 198, 365, 200, 82013373, 201, 50517, 20623, 1560, 204, 82013143, 705, 1558, 1557, 1567, 205, 1565, 707, 8446, 3577, 12556692, 212, 50523, 207, 8450, 209, 374, 375, 50521, 206, 1573, 369, 1571, 372, 82013167, 1574, 370, 3615, 8462, 371, 309010, 3581, 8460, 378, 8458, 3613, 377, 1584, 1583, 218, 1578, 219, 309004, 220, 379, 3631, 381, 380
# The corresponding primes prime(x), are:
11, 2, 3, 19, 5, 1531, 7, 1553, 541, 85411, 29, 614483, 83, 85667, 31511, 37, 89, 4393511, 41, 227, 97, 47, 101, 228346931, 613, 257, 643, 271, 263, 11657, 277, 1697, 673, 1709, 127, 228347011, 4441, 1733, 137, 228346981, 701, 1747, 313, 317, 709, 307, 149, 615509, 157, 11789, 727, 11959, 163, 11779, 167, 1811, 757, 337, 4583, 617369, 769, 12011, 1823, 349, 347, 12043, 787, 11933, 797, 367, 383, 1847, 373, 389, 811, 615427, 401, 615187, 397, 12071, 821, 1867, 839, 616799, 421, 419, 616219, 433, 431, 615749, 439, 443, 853, 615269, 449, 1951, 4789, 616307, 907, 457, 461, 616157, 919, 2029, 616391, 2011, 2017, 616361, 929, 479, 12347, 1987, 937, 12329, 487, 491, 953, 2053, 503, 12671, 499, 509, 971, 2099, 977, 2081, 523, 2153, 12491, 12373, 991, 12473, 997, 2129, 12539, 86239, 4937, 1654333729, 4903, 86531, 1009, 12763, 1019, 2179, 1033, 12739, 1031, 86629, 1049, 1654330663, 32687, 4394191, 1093, 4394297, 1091, 12791, 1109, 2213, 1087, 12809, 2221, 12853, 2203, 31659119, 12821, 618377, 5189, 2243, 2239, 4394183, 2251, 2237, 1153, 228347659, 1151, 2311, 33049, 31659853, 1163, 12983, 2351, 2267, 1171, 2389, 12911, 2411, 2347, 2423, 1181, 13063, 1187, 2377, 1193, 2339, 33203, 618253, 2437, 1654332877, 1231, 618521, 1213, 2467, 1223, 1654338659, 1229, 618637, 232357, 13109, 1249, 1654333991, 5323, 13099, 13093, 13171, 1259, 13159, 5347, 86951, 33403, 228348079, 1301, 618719, 1279, 86993, 1289, 2551, 2557, 618703, 1277, 13229, 2521, 13217, 2543, 1654334509, 13241, 2531, 33757, 87133, 2539, 4394903, 33457, 87119, 2593, 87103, 33749, 2591, 13337, 13331, 1361, 13291, 1367, 4394837, 1373, 2609, 33911, 2621, 2617
# Terms for n = 1..1000, with zeros where unknown:
5, 1, 2, 8, 3, 242, 4, 245, 100, 8313, 10, 50190, 23, 8338, 3390, 12, 24, 308926, 13, 49, 25, 15, 26, 12556637, 112, 55, 117, 58, 56, 1400, 59, 265, 122, 267, 31, 12556641, 603, 270, 33, 12556639, 126, 272, 65, 66, 127, 63, 35, 50270, 37, 1413, 129, 1434, 38, 1411, 39, 280, 134, 68, 620, 50424, 136, 1440, 281, 70, 69, 1443, 138, 1430, 139, 73, 76, 283, 74, 77, 141, 50261, 79, 50243, 78, 1445, 142, 285, 146, 50376, 82, 81, 50326, 84, 83, 50287, 85, 86, 147, 50248, 87, 297, 644, 50333, 155, 88, 89, 50320, 157, 308, 50340, 305, 306, 50337, 158, 92, 1475, 300, 159, 1473, 93, 94, 162, 310, 96, 1514, 95, 97, 164, 317, 165, 313, 99, 325, 1491, 1476, 167, 1488, 168, 320, 1497, 8383, 660, 82013133, 655, 8414, 169, 1523, 171, 327, 174, 1520, 173, 8423, 176, 82012985, 3506, 308965, 183, 308973, 182, 1525, 186, 330, 181, 1527, 331, 1532, 328, 1954049, 1528, 50499, 691, 334, 333, 308963, 335, 332, 191, 12556671, 190, 344, 3543, 1954094, 192, 1547, 349, 336, 193, 355, 1537, 358, 348, 360, 194, 1556, 195, 352, 196, 346, 3559, 50486, 361, 82013089, 202, 50507, 198, 365, 200, 82013373, 201, 50517, 20623, 1560, 204, 82013143, 705, 1558, 1557, 1567, 205, 1565, 707, 8446, 3577, 12556692, 212, 50523, 207, 8450, 209, 374, 375, 50521, 206, 1573, 369, 1571, 372, 82013167, 1574, 370, 3615, 8462, 371, 309010, 3581, 8460, 378, 8458, 3613, 377, 1584, 1583, 218, 1578, 219, 309004, 220, 379, 3631, 381, 380, 0, 397, 1593, 399, 1595, 222, 398, 741, 395, 394, 392, 223, 0, 387, 383, 386, 385, 8482, 408, 226, 8485, 224, 8487, 406, 0, 229, 405, 50530, 8496, 233, 413, 237, 8531, 235, 415, 234, 50529, 766, 1625, 1624, 1606, 240, 50527, 781, 1623, 3651, 417, 1607, 1611, 418, 0, 1619, 1627, 1626, 419, 420, 421, 3661, 8553, 422, 1616, 424, 0, 3647, 0, 782, 1641, 1648, 429, 426, 425, 428, 1643, 1636, 1639, 1634, 1954119, 785, 0, 784, 0, 3659, 0, 786, 0, 787, 0, 1650, 431, 794, 1649, 430, 0, 432, 309032, 434, 433, 798, 0, 20681, 1655, 799, 309042, 436, 435, 1652, 437, 804, 1657, 803, 1651, 3718, 1661, 438, 439, 441, 442, 1660, 8561, 818, 309036, 440, 1663, 309039, 8567, 805, 50603, 124288, 309121, 3728, 8565, 443, 50583, 445, 0, 3730, 444, 8562, 309060, 446, 309056, 50580, 50590, 124286, 50575, 20727, 1667, 1666, 309054, 3750, 1665, 838, 50605, 1668, 50585, 837, 449, 841, 50596, 448, 447, 842, 0, 450, 451, 3744, 1671, 3741, 456, 455, 453, 454, 8571, 852, 0, 850, 461, 50612, 50615, 460, 309081, 844, 309068, 462, 1954251, 459, 309070, 847, 458, 3764, 8578, 846, 0, 470, 472, 466, 467, 3758, 474, 465, 476, 473, 1681, 464, 0, 856, 463, 1708, 478, 858, 0, 477, 1707, 3775, 1693, 480, 50649, 875, 8590, 479, 8609, 874, 50617, 871, 1690, 3778, 1688, 870, 1704, 879, 481, 487, 8686, 872, 486, 485, 1712, 1711, 1726, 882, 1735, 482, 1722, 484, 483, 1720, 499, 1742, 488, 491, 494, 489, 1741, 490, 492, 503, 1753, 891, 508, 504, 510, 1749, 1750, 1754, 0, 905, 8654, 3795, 8597, 909, 309239, 511, 8735, 20754, 514, 513, 0, 914, 512, 516, 8713, 518, 0, 515, 8690, 20785, 519, 912, 0, 520, 521, 522, 8751, 915, 50705, 916, 1770, 1775, 1758, 1759, 1762, 525, 8747, 1765, 1760, 529, 1783, 917, 523, 524, 527, 921, 50709, 920, 8759, 531, 8765, 1804, 530, 1781, 532, 1806, 1780, 534, 50726, 536, 1831, 3813, 1829, 533, 309260, 539, 309202, 538, 537, 544, 543, 933, 541, 540, 547, 934, 1822, 1817, 50733, 1835, 1840, 1823, 1838, 938, 1842, 3840, 8771, 1841, 549, 1834, 8773, 50738, 1954351, 8770, 1833, 124489, 50779, 556, 557, 554, 555, 939, 50785, 553, 552, 550, 309266, 551, 560, 1854, 1848, 1858, 50768, 3859, 309264, 558, 50759, 942, 1850, 561, 562, 1849, 50818, 20862, 564, 565, 1859, 563, 8783, 943, 50820, 949, 8791, 309292, 569, 568, 309363, 946, 567, 1864, 573, 952, 0, 572, 571, 3874, 8797, 970, 309287, 969, 309357, 1875, 1876, 574, 1879, 972, 1871, 3864, 1865, 1870, 1873, 982, 309285, 1872, 1869, 984, 50824, 575, 8799, 582, 578, 1883, 576, 577, 583, 579, 8817, 581, 50841, 588, 589, 1882, 8819, 590, 309300, 986, 1881, 1885, 1884, 1880, 0, 8812, 1888, 50829, 8825, 988, 50830, 3942, 8811, 3938, 8823, 991, 309306, 996, 8847, 309298, 8834, 995, 309397, 993, 0, 3983, 309308, 1000, 0, 1001, 8851, 3980, 309394, 3984, 1893, 3947, 0, 3954, 8857, 3950, 1895, 1894, 1899, 1896, 0, 3949, 0, 1900, 1897, 1908, 50866, 3961, 0, 1007, 1907, 1911, 1910, 1905, 50862, 1009, 0, 3970, 1954511, 1008, 0, 1904, 1903, 20904, 8872, 1902, 1901, 3968, 1954460, 1913, 8874, 1011, 1914, 1019, 1919, 1916, 1917, 1020, 0, 1012, 1954456, 3995, 8876, 1014, 50854, 8927, 0, 50938, 8928, 1023, 0, 8932, 1933, 3997, 1921, 1026, 0, 1024, 8925, 1922, 1954465, 3998, 1927, 1029, 1923, 3999, 8878, 1030, 1925, 1036, 1938, 1934, 8882, 1040, 50847, 1039, 8910, 4002, 8880, 4007, 50901, 4009, 8952, 4017, 8908, 8940, 50879, 1939, 8950, 4018, 8893, 8919, 50875, 1046, 8899, 20947, 1943, 1047, 50873, 1049, 8901, 1942, 8992, 1050, 1940, 4012, 9021, 20933, 1968, 1941, 309524, 1055, 1948, 1947, 9032, 1054, 1956, 1056, 1960, 1959, 1958, 1053, 1945, 1052, 8986, 1957, 1964, 4024, 51000, 1961, 50989, 1963, 1962, 1971, 1970, 4027, 1974, 1973, 50991, 4031, 309436, 4028, 9025, 1975, 309487, 4042, 309542, 4026, 309440, 20981, 51010, 1060, 309548, 21003, 51013, 20956, 0, 1061, 1976, 1062, 309451, 309450, 1980, 1064, 1982, 21017, 9044, 1979, 1978, 1095, 0, 1067, 1954813, 776819, 1984, 1068, 0, 1069, 9069, 4056, 309446, 1074, 0, 1073, 9071, 309447, 1986, 1070, 2014, 1107, 9074, 51033, 2000, 1994, 2012, 2011, 1995, 1996, 9066, 1993, 1989, 1988, 9051, 4943428, 9078, 1111, 309578, 1110, 1991, 2017, 51028, 1113, 0, 1109, 2018, 2020, 2026, 1114, 2023, 4085, 2030, 4086, 9087, 4064, 0, 1121, 9056, 309587, 309594, 1120, 2038, 1118, 309575, 4081, 1955076, 1117, 0, 1124, 2035, 2036, 9091, 1123, 51038, 1127, 1954650, 4098, 2043