Rosetta Code

Fermat pseudoprimes: Difference between revisions

Page Discussion

Fermat pseudoprimes (view source)

Revision as of 11:23, 17 August 2022

7,911 bytes removed ,  1 year ago
→‎{{header|Wren}}: More efficient, tidier output.
m (→‎{{header|F_Sharp|F#}}: Change O -> 0. Didn't really matter but bothered me)
(→‎{{header|Wren}}: More efficient, tidier output.)
Line 221:
}
 
System.print("First 20 Fermat pseudoprimes:")
for (limit in [12000, 25000, 50000, 100000]) {
for (a in 1..20) {
var count = 0
var first20x = List.filled(20, 0)2
var first20 = for List.filled(x20, in 2..limit0) {
while (count < 20) {
if (isFermatPseudoprime.call(x, a)) {
if (countisFermatPseudoprime.call(x, < 20a)) first20[count] = x{
first20[count] = count + 1x
}count = count + 1
}
x = x + 1
Fmt.print("Base $2d - Up to $d: $5d First 20: $n", a, limit, count, first20)
}
Fmt.print("Base $2d: $5d", a, first20)
}
var limits = [12000, 25000, 50000, 100000]
var heading = Fmt.swrite("\nCount <= $6d", limits)
System.print(heading)
System.print("-" * (heading.count - 1))
for (a in 1..20) {
Fmt.write("Base $2d: ", a)
var x = 2
var count = 0
for (limit in limits) {
while (x <= limit) {
if (isFermatPseudoprime.call(x, a)) count = count + 1
x = x + 1
}
Fmt.write("$6d ", count)
}
System.print()
Line 238 ⟶ 255:
{{out}}
<pre>
First 20 Fermat pseudoprimes:
Base 1 - Up to 12000: 10561 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32]
Base 1: 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32
Base 2 - Up to 12000: 25 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321]
Base 32: - Up to341 12000: 561 25 645 First 20:1105 [91, 121,1387 286, 671,1729 703, 949,1905 1105, 1541,2047 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367,3277 3751, 4961,4033 4369 4371 4681 5461 5551, 6601] 7957 8321
Base 43: - Up to 12000:91 121 50 First286 20: [15, 85,671 91, 341, 435,703 451, 561, 645,949 703, 1105, 1247, 1271,1541 1387, 1581, 1695, 1729, 1891, 1905, 2047,2465 2665 2701 2821 3281 3367 3751 4961 5551 2071]6601
Base 4: 15 85 91 341 435 451 561 645 703 1105 1247 1271 1387 1581 1695 1729 1891 1905 2047 2071
Base 5 - Up to 12000: 22 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881]
Base 65: - Up to 12000: 4 31124 First 20:217 [35, 185, 217,561 301, 481, 1105,781 1111, 1261,1541 1333, 1729, 2465, 2701,1891 2821, 3421, 3565,4123 3589, 3913,5461 4123, 4495,5611 5662 5731 6601 7449 7813 8029 8911 5713]9881
Base 76: - Up to 12000:35 185 21 First217 20: [6, 25,301 325, 561, 703,481 817, 1105, 1825, 2101,1111 1261 1333 1729 2353, 2465, 3277, 4525,2701 2821 3421 3565 3589 4825,3913 6697, 8321,4123 10225, 10585,4495 10621, 11041]5713
Base 87: - Up to 12000: 6 76 25 First 20: [9,325 21, 45, 63,561 65, 105, 117,703 133, 153, 231,817 273, 341,1105 481, 511,1825 2101 2353 2465 3277 4525 4825 6697 561, 585,8321 645,10225 651,10585 861,10621 949]11041
Base 8: 9 - Up to 12000:21 5545 First 20: [4,63 8, 28, 52, 91,65 121, 205, 286,105 117 133 153 231 273 341 481 364, 511, 532, 616, 671,561 697, 703, 946,585 949, 1036, 1105,645 1288] 651 861 949
Base 10 -9: Up to 12000: 4 35 First 20:8 28 52 [9, 33, 91, 99, 259, 451,121 481, 561, 657,205 286 364 511 532 616 671 697 703, 909, 1233, 1729,946 2409,949 2821, 2981,1036 3333, 3367,1105 4141, 4187]1288
Base 1110: - Up to 12000: 9 30 33 First 20: [10, 15,91 70, 133, 190, 99 259, 305, 451 481, 645, 561 657 703, 793, 1105, 1330,909 1233 1729, 2047, 2257,2409 2465, 2821, 4577, 4921]2981 3333 3367 4141 4187
Base 1211: - Up to 12000:10 3515 First 20: [65,70 91, 133, 143, 145, 247,190 259 305 481 645 377, 385, 703, 1045, 1099, 793 1105, 1649, 1330 1729, 1885, 1891,2047 2041, 2233,2257 2465, 2701] 2821 4577 4921
Base 1312: - Up to 12000:65 3191 First 20:133 [4, 6, 12,143 21, 85, 105,145 231, 244, 276,247 357, 427, 561,377 385 703 1045 1099, 1785, 1105 1649 1729 1885 1891, 2465, 2806,2041 3605, 5028,2233 2465 5149]2701
Base 1413: - Up to 12000: 4 33 First6 20: [15, 39, 65,12 195, 481, 561, 781,21 793, 841, 985, 1105,85 1111, 1541, 105 231 244 276 357 427 561 1099 1785 1891, 2257, 2465, 2561, 2665,2806 3605 5028 2743, 3277]5149
Base 14: 15 - Up to 12000:39 2265 First 20:195 [14, 341, 742,481 946, 1477, 1541,561 1687, 1729, 781 793 841 985 1105 1111 1541 1891, 1921, 2821,2257 3133, 3277,2465 4187, 6541,2561 6601, 7471,2665 8701, 8911,2743 9073] 3277
Base 15: 14 341 742 946 1477 1541 1687 1729 1891 1921 2821 3133 3277 4187 6541 6601 7471 8701 8911 9073
Base 16 - Up to 12000: 69 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687]
Base 16: 15 51 85 91 255 341 435 451 561 595 645 703 1105 1247 1261 1271 1285 1387 1581 1687
Base 17 - Up to 12000: 31 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187]
Base 17: 4 8 9 16 45 91 145 261 781 1111 1228 1305 1729 1885 2149 2821 3991 4005 4033 4187
Base 18 - Up to 12000: 46 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921]
Base 1918: - Up to 12000:25 4849 First 20: [6,65 9, 15, 18, 45,85 49, 153, 169,133 221 323 325 343, 561, 425 451 637, 889, 905, 906,931 1035, 1105, 1629, 1661,1225 1369 1387 1649 1729 1849, 1891]1921
Base 2019: - Up to 12000: 6 35 First9 20: [21, 57, 133,15 18 45 49 153 169 343 231, 399, 561, 671, 861, 637 889, 1281, 1653, 1729,905 1891, 2059, 2413,906 2501, 2761,1035 2821, 2947,1105 3059] 1629 1661 1849 1891
Base 20: 21 57 133 231 399 561 671 861 889 1281 1653 1729 1891 2059 2413 2501 2761 2821 2947 3059
 
Base 1 - Up to 25000: 22237 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32]
Base 2 - Up to 25000: 38 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321]
Base 3 - Up to 25000: 38 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601]
Base 4 - Up to 25000: 75 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071]
Base 5 - Up to 25000: 35 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881]
Base 6 - Up to 25000: 46 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713]
Base 7 - Up to 25000: 32 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041]
Base 8 - Up to 25000: 110 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949]
Base 9 - Up to 25000: 83 First 20: [4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288]
Base 10 - Up to 25000: 53 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187]
Base 11 - Up to 25000: 41 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921]
Base 12 - Up to 25000: 60 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701]
Base 13 - Up to 25000: 51 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149]
Base 14 - Up to 25000: 51 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277]
Base 15 - Up to 25000: 31 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073]
Base 16 - Up to 25000: 102 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687]
Base 17 - Up to 25000: 44 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187]
Base 18 - Up to 25000: 69 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921]
Base 19 - Up to 25000: 70 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891]
Base 20 - Up to 25000: 49 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059]
 
Base 1 - Up to 50000: 44866 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32]
Base 2 - Up to 50000: 55 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321]
Base 3 - Up to 50000: 53 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601]
Base 4 - Up to 50000: 111 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071]
Base 5 - Up to 50000: 54 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881]
Base 6 - Up to 50000: 74 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713]
Base 7 - Up to 50000: 49 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041]
Base 8 - Up to 50000: 150 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949]
Base 9 - Up to 50000: 113 First 20: [4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288]
Base 10 - Up to 50000: 65 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187]
Base 11 - Up to 50000: 61 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921]
Base 12 - Up to 50000: 91 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701]
Base 13 - Up to 50000: 68 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149]
Base 14 - Up to 50000: 69 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277]
Base 15 - Up to 50000: 42 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073]
Base 16 - Up to 50000: 145 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687]
Base 17 - Up to 50000: 63 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187]
Base 18 - Up to 50000: 98 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921]
Base 19 - Up to 50000: 93 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891]
Base 20 - Up to 50000: 66 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059]
 
Count <= 12000 25000 50000 100000
Base 1 - Up to 100000: 90407 First 20: [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32]
------------------------------------
Base 2 - Up to 100000: 78 First 20: [341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321]
Base 1: 10561 22237 44866 90407
Base 3 - Up to 100000: 78 First 20: [91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601]
Base 2: 25 38 55 78
Base 4 - Up to 100000: 153 First 20: [15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071]
Base 3: 25 38 53 78
Base 5 - Up to 100000: 73 First 20: [4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881]
Base 4: 50 75 111 153
Base 6 - Up to 100000: 104 First 20: [35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713]
Base 5: 22 35 54 73
Base 7 - Up to 100000: 73 First 20: [6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041]
Base 6: 31 46 74 104
Base 8 - Up to 100000: 218 First 20: [9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949]
Base 9 - Up to 1000007: 164 First 20: [4, 8, 28, 52,21 91, 121, 205, 286, 364,32 511, 532, 616, 671, 697,49 703, 946, 949, 1036, 1105,73 1288]
Base 8: 76 110 150 218
Base 10 - Up to 100000: 90 First 20: [9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187]
Base 9: 55 83 113 164
Base 11 - Up to 100000: 89 First 20: [10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921]
Base 10: 35 53 65 90
Base 12 - Up to 100000: 127 First 20: [65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701]
Base 11: 30 41 61 89
Base 13 - Up to 100000: 91 First 20: [4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149]
Base 12: 35 60 91 127
Base 14 - Up to 100000: 96 First 20: [15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277]
Base 13: 31 51 68 91
Base 15 - Up to 100000: 70 First 20: [14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073]
Base 14: 33 51 69 96
Base 16 - Up to 100000: 200 First 20: [15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687]
Base 15: 22 31 42 70
Base 17 - Up to 100000: 83 First 20: [4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187]
Base 16: 69 102 145 200
Base 18 - Up to 100000: 134 First 20: [25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921]
Base 17: 31 44 63 83
Base 19 - Up to 100000: 121 First 20: [6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891]
Base 18: 46 69 98 134
Base 20 - Up to 100000: 101 First 20: [21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059]
Base 19: 48 70 93 121
Base 20: 35 49 66 101
</pre>
PureFox
9,485

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/322082"