Successive prime differences: Difference between revisions
m →{{header|REXX}}: added a missing statement. |
|||
Line 1,160: | Line 1,160: | ||
if jj>N then != 1 /*indicate skip top part if j > √ N */ |
if jj>N then != 1 /*indicate skip top part if j > √ N */ |
||
do m=jj to N by j+j; @.m=; end /*odd multiples.*/ |
do m=jj to N by j+j; @.m=; end /*odd multiples.*/ |
||
end /* [↑] strike odd multiples ¬ prime. */ |
end /* [↑] strike odd multiples ¬ prime. */ |
||
end /*j*/; return</lang> |
|||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
Revision as of 02:28, 9 April 2020
You are encouraged to solve this task according to the task description, using any language you may know.
The series of increasing prime numbers begins: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
The task applies a filter to the series returning groups of successive primes, (s'primes), that differ from the next by a given value or values.
Example 1: Specifying that the difference between s'primes be 2
leads to the groups:
(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), ...
(Known as Twin primes or Prime pairs)
Example 2: Specifying more than one difference between s'primes leads to groups of size one greater than the number of differences. Differences of 2, 4
leads to the groups:
(5, 7, 11), (11, 13, 17), (17, 19, 23), (41, 43, 47), ...
.
In the first group 7 is two more than 5 and 11 is four more than 7; as well as 5, 7, and 11 being successive primes.
Differences are checked in the order of the values given, (differences of 4, 2
would give different groups entirely).
- Task
- In each case use a list of primes less than 1_000_000
- For the following Differences show the first and last group, as well as the number of groups found:
- Differences of
2
. - Differences of
1
. - Differences of
2, 2
. - Differences of
2, 4
. - Differences of
4, 2
. - Differences of
6, 4, 2
.
- Differences of
- Show output here.
Note: Generation of a list of primes is a secondary aspect of the task. Use of a built in function, well known library, or importing/use of prime generators from other Rosetta Code tasks is encouraged.
- references
AWK
<lang AWK>
- syntax: GAWK -f SUCCESSIVE_PRIME_DIFFERENCES.AWK
BEGIN {
for (i=lo=0; i<=hi=1000000; i++) { if (is_prime(i)) { p_arr[++p] = i } } printf("there are %d primes between %d - %d\n",p,lo,hi) fmt = "%-11s %5s %-15s %s\n" printf(fmt,"differences","count","first group","last group") for (a=1; a<=split("2;1;2,2;2,4;4,2;6,4,2;2,4,6;100;112",diff_arr,";"); a++) { diff_leng = split(diff_arr[a],tmp_arr,",") first_set = last_set = "" count = 0 for (b=1; b<=p; b++) { str = "" for (c=1; c<=diff_leng; c++) { if (p_arr[b+c-1] + tmp_arr[c] == p_arr[b+c]) { str = (str == "") ? (p_arr[b+c-1] "," p_arr[b+c]) : (str "," p_arr[b+c]) } } if (gsub(/,/,"&",str) == diff_leng) { count++ if (first_set == "") { first_set = str } last_set = str } } printf(fmt,diff_arr[a],count,first_set,last_set) } exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} </lang>
- Output:
there are 78498 primes between 0 - 1000000 differences count first group last group 2 8169 3,5 999959,999961 1 1 2,3 2,3 2,2 1 3,5,7 3,5,7 2,4 1393 5,7,11 999431,999433,999437 4,2 1444 7,11,13 997807,997811,997813 6,4,2 306 31,37,41,43 997141,997147,997151,997153 2,4,6 279 17,19,23,29 997097,997099,997103,997109 100 2 396733,396833 838249,838349 112 1 370261,370373 370261,370373
C#
<lang csharp>using System; using System.Collections.Generic; using static System.Linq.Enumerable;
public static class SuccessivePrimeDifferences {
public static void Main() { var primes = GeneratePrimes(1_000_000).ToList(); foreach (var d in new[] { new [] { 2 }, new [] { 1 }, new [] { 2, 2 }, new [] { 2, 4 }, new [] { 4, 2 }, new [] { 6, 4, 2 }, }) { IEnumerable<int> first = null, last = null; int count = 0; foreach (var grp in FindDifferenceGroups(d)) { if (first == null) first = grp; last = grp; count++; } Console.WriteLine($"{$"({string.Join(", ", first)})"}, {$"({string.Join(", ", last)})"}, {count}"); }
IEnumerable<IEnumerable<int>> FindDifferenceGroups(int[] diffs) { for (int pi = diffs.Length; pi < primes.Count; pi++) { if (Range(0, diffs.Length).All(di => primes[pi-diffs.Length+di+1] - primes[pi-diffs.Length+di] == diffs[di])) { yield return Range(pi - diffs.Length, diffs.Length + 1).Select(i => primes[i]); } } } }
}</lang>
- Output:
(3, 5), (999959, 999961), 8169 (2, 3), (2, 3), 1 (3, 5, 7), (3, 5, 7), 1 (5, 7, 11), (999431, 999433, 999437), 1393 (7, 11, 13), (997807, 997811, 997813), 1444 (31, 37, 41, 43), (997141, 997147, 997151, 997153), 306
C++
<lang cpp>#include <iostream>
- include <cstdint>
- include <vector>
- include "sieve_of_eratosthenes.h"
using integer = uint32_t; using vector = std::vector<integer>;
void print_vector(const vector& vec) {
if (!vec.empty()) { auto i = vec.begin(); std::cout << '(' << *i; for (++i; i != vec.end(); ++i) std::cout << ", " << *i; std::cout << ')'; }
}
class diffs { public:
diffs(std::initializer_list<integer> list) : diffs_(list) {} diffs(const vector& vec) : diffs_(vec) {} void test_group(const vector&); size_t size() const { return diffs_.size(); } void print(std::ostream&);
private:
vector diffs_; vector first_; vector last_; integer count_ = 0;
};
void diffs::test_group(const vector& vec) {
if (vec.size() < size() + 1) return; size_t start = vec.size() - size() - 1; for (size_t i = 0, j = start + 1; i < size(); ++i, ++j) { if (vec[j] - vec[j - 1] != diffs_[i]) return; } vector group(vec.begin() + start, vec.end()); if (count_ == 0) first_ = group; last_ = group; ++count_;
}
void diffs::print(std::ostream& out) {
print_vector(diffs_); out << ": first group = "; print_vector(first_); out << ", last group = "; print_vector(last_); out << ", count = " << count_ << '\n';
}
int main() {
const integer limit = 1000000; const size_t max_group_size = 4; sieve_of_eratosthenes sieve(limit); diffs d[] = { {2}, {1}, {2, 2}, {2, 4}, {4, 2}, {6, 4, 2} }; vector group; for (integer p = 0; p < limit; ++p) { if (!sieve.is_prime(p)) continue; if (group.size() >= max_group_size) group.erase(group.begin()); group.push_back(p); for (auto&& diff : d) { diff.test_group(group); } } for (auto&& diff : d) { diff.print(std::cout); } return 0;
}</lang>
Contents of sieve_of_eratosthenes.h: <lang cpp>#ifndef SIEVE_OF_ERATOSTHENES_H
- define SIEVE_OF_ERATOSTHENES_H
- include <vector>
class sieve_of_eratosthenes { public:
explicit sieve_of_eratosthenes(size_t); bool is_prime(size_t) const;
private:
std::vector<bool> is_prime_;
};
inline bool sieve_of_eratosthenes::is_prime(size_t n) const {
return is_prime_[n];
}
inline sieve_of_eratosthenes::sieve_of_eratosthenes(size_t max)
: is_prime_(max, true)
{
is_prime_[0] = is_prime_[1] = false; for (size_t p = 2; p * p < max; ++p) { if (is_prime_[p]) { for (size_t q = p * p; q < max; q +=p) is_prime_[q] = false; } }
}
- endif</lang>
- Output:
(2): first group = (3, 5), last group = (999959, 999961), count = 8169 (1): first group = (2, 3), last group = (2, 3), count = 1 (2, 2): first group = (3, 5, 7), last group = (3, 5, 7), count = 1 (2, 4): first group = (5, 7, 11), last group = (999431, 999433, 999437), count = 1393 (4, 2): first group = (7, 11, 13), last group = (997807, 997811, 997813), count = 1444 (6, 4, 2): first group = (31, 37, 41, 43), last group = (997141, 997147, 997151, 997153), count = 306
D
<lang d>import std.algorithm; import std.array; import std.range; import std.stdio;
immutable PRIMES = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973,
];
bool isPrime(int n) {
if (n < 2) { return false; }
foreach (prime; PRIMES) { if (n == prime) { return true; } if (n % prime == 0) { return false; } if (n < prime * prime) { if (n > PRIMES[$-1] * PRIMES[$-1]) { assert(false, "Out of pre-computed primes."); } break; } }
return true;
}
int[][] successivePrimes(int[] primes, int[] diffs) {
int[][] results; auto dl = diffs.length;
outer: for (int i = 0; i < primes.length - dl; i++) { auto group = uninitializedArray!(int[])(dl + 1); group[0] = primes[i]; for (int j = i; j < i + dl; j++) { if (primes[j + 1] - primes[j] != diffs[j - i]) { continue outer; } group[j - i + 1] = primes[j + 1]; } results ~= group; }
return results;
}
void main() {
auto primeList = iota(2, 1_000_000).filter!isPrime.array; auto diffsList = [[2], [1], [2, 2], [2, 4], [4, 2], [6, 4, 2]]; writeln("For primes less than 1,000,000:-"); foreach (diffs; diffsList) { writefln(" For differences of %s ->", diffs); auto sp = successivePrimes(primeList, diffs); if (sp.length == 0) { writeln(" No groups found"); continue; } writeln(" First group = ", sp[0]); writeln(" Last group = ", sp[$ - 1]); writeln(" Number found = ", sp.length); writeln(); }
}</lang>
- Output:
For primes less than 1,000,000:- For differences of [2] -> First group = [3, 5] Last group = [999959, 999961] Number found = 8169 For differences of [1] -> First group = [2, 3] Last group = [2, 3] Number found = 1 For differences of [2, 2] -> First group = [3, 5, 7] Last group = [3, 5, 7] Number found = 1 For differences of [2, 4] -> First group = [5, 7, 11] Last group = [999431, 999433, 999437] Number found = 1393 For differences of [4, 2] -> First group = [7, 11, 13] Last group = [997807, 997811, 997813] Number found = 1444 For differences of [6, 4, 2] -> First group = [31, 37, 41, 43] Last group = [997141, 997147, 997151, 997153] Number found = 306
F#
This task uses Extensible Prime Generator (F#) <lang fsharp> // Successive primes. Nigel Galloway: May 6th., 2019 let sP n=let sP=pCache|>Seq.takeWhile(fun n->n<1000000)|>Seq.windowed(Array.length n+1)|>Seq.filter(fun g->g=(Array.scan(fun n g->n+g) g.[0] n))
printfn "sP %A\t-> Min element = %A Max element = %A of %d elements" n (Seq.head sP) (Seq.last sP) (Seq.length sP)
List.iter sP [[|2|];[|1|];[|2;2|];[|2;4|];[|4;2|];[|6;4;2|]] </lang>
- Output:
sP [|2|] -> Min element = [|3; 5|] Max element = [|999959; 999961|] of 8169 elements sP [|1|] -> Min element = [|2; 3|] Max element = [|2; 3|] of 1 elements sP [|2; 2|] -> Min element = [|3; 5; 7|] Max element = [|3; 5; 7|] of 1 elements sP [|2; 4|] -> Min element = [|5; 7; 11|] Max element = [|999431; 999433; 999437|] of 1393 elements sP [|4; 2|] -> Min element = [|7; 11; 13|] Max element = [|997807; 997811; 997813|] of 1444 elements sP [|6; 4; 2|] -> Min element = [|31; 37; 41; 43|] Max element = [|997141; 997147; 997151; 997153|] of 306 elements
Factor
<lang factor>USING: formatting fry grouping kernel math math.primes math.statistics sequences ; IN: rosetta-code.successive-prime-differences
- seq-diff ( seq diffs -- seq' quot )
dup [ length 1 + <clumps> ] dip '[ differences _ sequence= ] ; inline
- show ( seq diffs -- )
[ "...for differences %u:\n" printf ] keep seq-diff [ find nip { } like ] [ find-last nip { } like ] [ count ] 2tri "First group: %u\nLast group: %u\nCount: %d\n\n" printf ;
- successive-prime-differences ( -- )
"Groups of successive primes up to one million...\n" printf 1,000,000 primes-upto { { 2 } { 1 } { 2 2 } { 2 4 } { 4 2 } { 6 4 2 } } [ show ] with each ;
MAIN: successive-prime-differences</lang>
- Output:
Groups of successive primes up to one million... ...for differences { 2 }: First group: { 3 5 } Last group: { 999959 999961 } Count: 8169 ...for differences { 1 }: First group: { 2 3 } Last group: { 2 3 } Count: 1 ...for differences { 2 2 }: First group: { 3 5 7 } Last group: { 3 5 7 } Count: 1 ...for differences { 2 4 }: First group: { 5 7 11 } Last group: { 999431 999433 999437 } Count: 1393 ...for differences { 4 2 }: First group: { 7 11 13 } Last group: { 997807 997811 997813 } Count: 1444 ...for differences { 6 4 2 }: First group: { 31 37 41 43 } Last group: { 997141 997147 997151 997153 } Count: 306
Go
<lang go>package main
import "fmt"
func sieve(limit int) []int {
primes := []int{2} c := make([]bool, limit+1) // composite = true // no need to process even numbers > 2 p := 3 for { p2 := p * p if p2 > limit { break } for i := p2; i <= limit; i += 2 * p { c[i] = true } for { p += 2 if !c[p] { break } } } for i := 3; i <= limit; i += 2 { if !c[i] { primes = append(primes, i) } } return primes
}
func successivePrimes(primes, diffs []int) [][]int {
var results [][]int dl := len(diffs)
outer:
for i := 0; i < len(primes)-dl; i++ { group := make([]int, dl+1) group[0] = primes[i] for j := i; j < i+dl; j++ { if primes[j+1]-primes[j] != diffs[j-i] { group = nil continue outer } group[j-i+1] = primes[j+1] } results = append(results, group) group = nil } return results
}
func main() {
primes := sieve(999999) diffsList := [][]int{{2}, {1}, {2, 2}, {2, 4}, {4, 2}, {6, 4, 2}} fmt.Println("For primes less than 1,000,000:-\n") for _, diffs := range diffsList { fmt.Println(" For differences of", diffs, "->") sp := successivePrimes(primes, diffs) if len(sp) == 0 { fmt.Println(" No groups found") continue } fmt.Println(" First group = ", sp[0]) fmt.Println(" Last group = ", sp[len(sp)-1]) fmt.Println(" Number found = ", len(sp)) fmt.Println() }
}</lang>
- Output:
For primes less than 1,000,000:- For differences of [2] -> First group = [3 5] Last group = [999959 999961] Number found = 8169 For differences of [1] -> First group = [2 3] Last group = [2 3] Number found = 1 For differences of [2 2] -> First group = [3 5 7] Last group = [3 5 7] Number found = 1 For differences of [2 4] -> First group = [5 7 11] Last group = [999431 999433 999437] Number found = 1393 For differences of [4 2] -> First group = [7 11 13] Last group = [997807 997811 997813] Number found = 1444 For differences of [6 4 2] -> First group = [31 37 41 43] Last group = [997141 997147 997151 997153] Number found = 306
J
<lang j>
primes_less_than=: i.&.:(p:inv) assert 2 3 5 -: primes_less_than 7 PRIMES=: primes_less_than 1e6
NB. Insert minus `-/' into the length two infixes `\'. NB. Passive `~' swaps the arguments producing the positive differences. SUCCESSIVE_DIFFERENCES=: 2 -~/\ PRIMES assert 8169 -: +/ 2 = SUCCESSIVE_DIFFERENCES NB. twin prime tally
INTERVALS=: 2 ; 1 ; 2 2 ; 2 4 ; 4 2 ; 6 4 2
sequence_index=: [: I. E. end_groups=: PRIMES {~ ({. , {:)@:] +/ i.@:>:@:#@:[
HEAD=: <;._2 'group;tally;end occurrences;'
HEAD , INTERVALS (([ ([ ; #@] ; end_groups) sequence_index)~ >)"1 0~ SUCCESSIVE_DIFFERENCES
┌─────┬─────┬───────────────────────────┐ │group│tally│end occurrences │ ├─────┼─────┼───────────────────────────┤ │2 │8169 │ 3 5 │ │ │ │999959 999961 │ ├─────┼─────┼───────────────────────────┤ │1 │1 │2 3 │ │ │ │2 3 │ ├─────┼─────┼───────────────────────────┤ │2 2 │1 │3 5 7 │ │ │ │3 5 7 │ ├─────┼─────┼───────────────────────────┤ │2 4 │1393 │ 5 7 11 │ │ │ │999431 999433 999437 │ ├─────┼─────┼───────────────────────────┤ │4 2 │1444 │ 7 11 13 │ │ │ │997807 997811 997813 │ ├─────┼─────┼───────────────────────────┤ │6 4 2│306 │ 31 37 41 43│ │ │ │997141 997147 997151 997153│ └─────┴─────┴───────────────────────────┘</lang>
Java
<lang java>import java.util.ArrayList; import java.util.Arrays; import java.util.List;
public class SuccessivePrimeDifferences {
private static Integer[] sieve(int limit) { List<Integer> primes = new ArrayList<>(); primes.add(2); boolean[] c = new boolean[limit + 1];// composite = true // no need to process even numbers > 2 int p = 3; while (true) { int p2 = p * p; if (p2 > limit) { break; } for (int i = p2; i <= limit; i += 2 * p) { c[i] = true; } do { p += 2; } while (c[p]); } for (int i = 3; i <= limit; i += 2) { if (!c[i]) { primes.add(i); } }
return primes.toArray(new Integer[0]); }
private static List<List<Integer>> successivePrimes(Integer[] primes, Integer[] diffs) { List<List<Integer>> results = new ArrayList<>(); int dl = diffs.length; outer: for (int i = 0; i < primes.length - dl; i++) { Integer[] group = new Integer[dl + 1]; group[0] = primes[i]; for (int j = i; j < i + dl; ++j) { if (primes[j + 1] - primes[j] != diffs[j - i]) { continue outer; } group[j - i + 1] = primes[j + 1]; } results.add(Arrays.asList(group)); } return results; }
public static void main(String[] args) { Integer[] primes = sieve(999999); Integer[][] diffsList = {{2}, {1}, {2, 2}, {2, 4}, {4, 2}, {6, 4, 2}}; System.out.println("For primes less than 1,000,000:-\n"); for (Integer[] diffs : diffsList) { System.out.printf(" For differences of %s ->\n", Arrays.toString(diffs)); List<List<Integer>> sp = successivePrimes(primes, diffs); if (sp.isEmpty()) { System.out.println(" No groups found"); continue; } System.out.printf(" First group = %s\n", Arrays.toString(sp.get(0).toArray(new Integer[0]))); System.out.printf(" Last group = %s\n", Arrays.toString(sp.get(sp.size() - 1).toArray(new Integer[0]))); System.out.printf(" Number found = %d\n", sp.size()); System.out.println(); } }
}</lang>
- Output:
For primes less than 1,000,000:- For differences of [2] -> First group = [3, 5] Last group = [999959, 999961] Number found = 8169 For differences of [1] -> First group = [2, 3] Last group = [2, 3] Number found = 1 For differences of [2, 2] -> First group = [3, 5, 7] Last group = [3, 5, 7] Number found = 1 For differences of [2, 4] -> First group = [5, 7, 11] Last group = [999431, 999433, 999437] Number found = 1393 For differences of [4, 2] -> First group = [7, 11, 13] Last group = [997807, 997811, 997813] Number found = 1444 For differences of [6, 4, 2] -> First group = [31, 37, 41, 43] Last group = [997141, 997147, 997151, 997153] Number found = 306
Julia
<lang julia>using Primes
function filterdifferences(deltas, N)
allprimes = primes(N) differences = map(i -> allprimes[i + 1] - allprimes[i], 1:length(allprimes) - 1) println("Diff Sequence Count First Last") for delt in deltas ret = trues(length(allprimes) - length(delt)) for j in 1:length(ret) for (i, d) in enumerate(delt) if differences[j - 1 + i] != d ret[j] = false break end end end count, p1, pn, n = sum(ret), findfirst(ret), findlast(ret), length(delt) println(rpad(string(delt), 16), lpad(count, 4), lpad(string(allprimes[p1:p1 + n]), 18), "...", rpad(allprimes[pn:pn+n], 15)) end
end
filterdifferences([[2], [1], [2, 2], [2, 4], [4, 2], [6, 4, 2]], 1000000)
</lang>
- Output:
Diff Sequence Count First Last [2] 8169 [3, 5]...[999959, 999961] [1] 1 [2, 3]...[2, 3] [2, 2] 1 [3, 5, 7]...[3, 5, 7] [2, 4] 1393 [5, 7, 11]...[999431, 999433, 999437] [4, 2] 1444 [7, 11, 13]...[997807, 997811, 997813] [6, 4, 2] 306 [31, 37, 41, 43]...[997141, 997147, 997151, 997153]
Kotlin
<lang scala>private fun sieve(limit: Int): Array<Int> {
val primes = mutableListOf<Int>() primes.add(2) val c = BooleanArray(limit + 1) // composite = true // no need to process even numbers > 2 var p = 3 while (true) { val p2 = p * p if (p2 > limit) { break } var i = p2 while (i <= limit) { c[i] = true i += 2 * p } do { p += 2 } while (c[p]) } var i = 3 while (i <= limit) { if (!c[i]) { primes.add(i) } i += 2 } return primes.toTypedArray()
}
private fun successivePrimes(primes: Array<Int>, diffs: Array<Int>): List<List<Int>> {
val results = mutableListOf<List<Int>>() val dl = diffs.size outer@ for (i in 0 until primes.size - dl) { val group = IntArray(dl + 1) group[0] = primes[i] for (j in i until i + dl) { if (primes[j + 1] - primes[j] != diffs[j - i]) { continue@outer } group[j - i + 1] = primes[j + 1] } results.add(group.toList()) } return results
}
fun main() {
val primes = sieve(999999) val diffsList = arrayOf( arrayOf(2), arrayOf(1), arrayOf(2, 2), arrayOf(2, 4), arrayOf(4, 2), arrayOf(6, 4, 2) ) println("For primes less than 1,000,000:-\n") for (diffs in diffsList) { println(" For differences of ${diffs.contentToString()} ->") val sp = successivePrimes(primes, diffs) if (sp.isEmpty()) { println(" No groups found") continue } println(" First group = ${sp[0].toTypedArray().contentToString()}") println(" Last group = ${sp[sp.size - 1].toTypedArray().contentToString()}") println(" Number found = ${sp.size}") println() }
}</lang>
- Output:
For primes less than 1,000,000:- For differences of [2] -> First group = [3, 5] Last group = [999959, 999961] Number found = 8169 For differences of [1] -> First group = [2, 3] Last group = [2, 3] Number found = 1 For differences of [2, 2] -> First group = [3, 5, 7] Last group = [3, 5, 7] Number found = 1 For differences of [2, 4] -> First group = [5, 7, 11] Last group = [999431, 999433, 999437] Number found = 1393 For differences of [4, 2] -> First group = [7, 11, 13] Last group = [997807, 997811, 997813] Number found = 1444 For differences of [6, 4, 2] -> First group = [31, 37, 41, 43] Last group = [997141, 997147, 997151, 997153] Number found = 306
Perl
<lang perl>use 5.010; use strict; use warnings; no warnings 'experimental::smartmatch';
use List::EachCons; use ntheory 'primes';
my $limit = 1E6; my @primes = (2, @{ primes($limit) }); my @intervals = map { $primes[$_] - $primes[$_-1] } 1..$#primes;
say "Groups of successive primes <= $limit";
for my $diffs ([2], [1], [2,2], [2,4], [4,2], [6,4,2]) {
my $n = -1; my @offsets = grep {$_} each_cons @$diffs, @intervals, sub { $n++; $n if @_ ~~ @$diffs }; printf "%10s has %5d sets: %15s … %s\n", '(' . join(' ',@$diffs) . ')', scalar @offsets, join(' ', @primes[$offsets[ 0]..($offsets[ 0]+@$diffs)]), join(' ', @primes[$offsets[-1]..($offsets[-1]+@$diffs)]);
}</lang>
- Output:
(2) has 8169 sets: 3 5 … 999959 999961 (1) has 1 sets: 2 3 … 2 3 (2 2) has 1 sets: 3 5 7 … 3 5 7 (2 4) has 1393 sets: 5 7 11 … 999431 999433 999437 (4 2) has 1444 sets: 7 11 13 … 997807 997811 997813 (6 4 2) has 306 sets: 31 37 41 43 … 997141 997147 997151 997153
Phix
Uses primes[] and add_block() from Extensible_prime_generator <lang Phix>procedure test(sequence differences)
sequence res = {} integer ld = length(differences) for i=1 to length(primes)-ld do integer pi = primes[i] for j=1 to ld do pi += differences[j] if pi!=primes[i+j] then pi = 0 exit end if end for if pi!=0 then res = append(res,primes[i..i+ld]) end if end for res = {differences,length(res),res[1],res[$]} printf(1,"%8v : %8d %14v...%v\n",res)
end procedure
while primes[$]<1_000_000 do add_block() end while primes = primes[1..abs(binary_search(1_000_000,primes))-1] constant differences = {{2},{1},{2,2},{2,4},{4,2},{6,4,2}} printf(1,"Differences Count First Last\n") for i=1 to length(differences) do test(differences[i]) end for</lang>
- Output:
Differences Count First Last {2} : 8169 {3,5}...{999959,999961} {1} : 1 {2,3}...{2,3} {2,2} : 1 {3,5,7}...{3,5,7} {2,4} : 1393 {5,7,11}...{999431,999433,999437} {4,2} : 1444 {7,11,13}...{997807,997811,997813} {6,4,2} : 306 {31,37,41,43}...{997141,997147,997151,997153}
Python
Uses the Sympy library.
<lang python># https://docs.sympy.org/latest/index.html from sympy import Sieve
def nsuccprimes(count, mx):
"return tuple of <count> successive primes <= mx (generator)" sieve = Sieve() sieve.extend(mx) primes = sieve._list return zip(*(primes[n:] for n in range(count)))
def check_value_diffs(diffs, values):
"Differences between successive values given by successive items in diffs?" return all(v[1] - v[0] == d for d, v in zip(diffs, zip(values, values[1:])))
def successive_primes(offsets=(2, ), primes_max=1_000_000):
return (sp for sp in nsuccprimes(len(offsets) + 1, primes_max) if check_value_diffs(offsets, sp))
if __name__ == '__main__':
for offsets, mx in [((2,), 1_000_000), ((1,), 1_000_000), ((2, 2), 1_000_000), ((2, 4), 1_000_000), ((4, 2), 1_000_000), ((6, 4, 2), 1_000_000), ]: print(f"## SETS OF {len(offsets)+1} SUCCESSIVE PRIMES <={mx:_} WITH " f"SUCCESSIVE DIFFERENCES OF {str(list(offsets))[1:-1]}") for count, last in enumerate(successive_primes(offsets, mx), 1): if count == 1: first = last print(" First group:", str(first)[1:-1]) print(" Last group:", str(last)[1:-1]) print(" Count:", count)</lang>
- Output:
## SETS OF 2 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 2 First group: 3, 5 Last group: 999959, 999961 Count: 8169 ## SETS OF 2 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 1 First group: 2, 3 Last group: 2, 3 Count: 1 ## SETS OF 3 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 2, 2 First group: 3, 5, 7 Last group: 3, 5, 7 Count: 1 ## SETS OF 3 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 2, 4 First group: 5, 7, 11 Last group: 999431, 999433, 999437 Count: 1393 ## SETS OF 3 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 4, 2 First group: 7, 11, 13 Last group: 997807, 997811, 997813 Count: 1444 ## SETS OF 4 SUCCESSIVE PRIMES <=1_000_000 WITH SUCCESSIVE DIFFERENCES OF 6, 4, 2 First group: 31, 37, 41, 43 Last group: 997141, 997147, 997151, 997153 Count: 306
Raku
(formerly Perl 6)
Categorized by Successive
Essentially the code from the Sexy primes task with minor tweaks.
<lang perl6>use Math::Primesieve; my $sieve = Math::Primesieve.new;
my $max = 1_000_000; my @primes = $sieve.primes($max); my $filter = @primes.Set; my $primes = @primes.categorize: &successive;
sub successive ($i) {
gather { take '2' if $filter{$i + 2}; take '1' if $filter{$i + 1}; take '2_2' if all($filter{$i «+« (2,4)}); take '2_4' if all($filter{$i «+« (2,6)}); take '4_2' if all($filter{$i «+« (4,6)}); take '6_4_2' if all($filter{$i «+« (6,10,12)}) and none($filter{$i «+« (2,4,8)}); }
}
sub comma { $^i.flip.comb(3).join(',').flip }
for (2,), (1,), (2,2), (2,4), (4,2), (6,4,2) -> $succ {
say "## Sets of {1+$succ} successive primes <= { comma $max } with " ~ "successive differences of { $succ.join: ', ' }"; my $i = $succ.join: '_'; for 'First', 0, ' Last', * - 1 -> $where, $ind { say "$where group: ", join ', ', [\+] flat $primes{$i}[$ind], |$succ } say ' Count: ', +$primes{$i}, "\n";
}</lang>
- Output:
## Sets of 2 successive primes <= 1,000,000 with successive differences of 2 First group: 3, 5 Last group: 999959, 999961 Count: 8169 ## Sets of 2 successive primes <= 1,000,000 with successive differences of 1 First group: 2, 3 Last group: 2, 3 Count: 1 ## Sets of 3 successive primes <= 1,000,000 with successive differences of 2, 2 First group: 3, 5, 7 Last group: 3, 5, 7 Count: 1 ## Sets of 3 successive primes <= 1,000,000 with successive differences of 2, 4 First group: 5, 7, 11 Last group: 999431, 999433, 999437 Count: 1393 ## Sets of 3 successive primes <= 1,000,000 with successive differences of 4, 2 First group: 7, 11, 13 Last group: 997807, 997811, 997813 Count: 1444 ## Sets of 4 successive primes <= 1,000,000 with successive differences of 6, 4, 2 First group: 31, 37, 41, 43 Last group: 997141, 997147, 997151, 997153 Count: 306
Precomputed Differences
<lang perl6>use Math::Primesieve;
constant $max = 1_000_000; constant @primes = Math::Primesieve.primes($max); constant @diffs = @primes.skip Z- @primes;
say "Given all ordered primes <= $max, sets with successive differences of:"; for (2,), (1,), (2,2), (2,4), (4,2), (6,4,2) -> @succ {
my $size = @succ.elems;
my @group_start_offsets = @diffs.rotor( $size => 1-$size ) .grep(:k, { $_ eqv @succ });
my ($first, $last) = @group_start_offsets[0, *-1] .map: { @primes.skip($_).head($size + 1) };
say sprintf '%10s has %5d sets: %15s … %s', @succ.gist, @group_start_offsets.elems, $first, $last;
}</lang>
- Output:
Given all ordered primes <= 1000000, sets with successive differences of: (2) has 8169 sets: 3 5 … 999959 999961 (1) has 1 sets: 2 3 … 2 3 (2 2) has 1 sets: 3 5 7 … 3 5 7 (2 4) has 1393 sets: 5 7 11 … 999431 999433 999437 (4 2) has 1444 sets: 7 11 13 … 997807 997811 997813 (6 4 2) has 306 sets: 31 37 41 43 … 997141 997147 997151 997153
REXX
<lang rexx>/*REXX program finds and displays primes with successive differences (up to a limit).*/ parse arg H . 1 . difs /*allow the highest number be specified*/ if H== | H=="," then H= 1000000 /*Not specified? Then use the default.*/ if difs= then difs= 2 1 2.2 2.4 4.2 6.4.2 /* " " " " " " */ call genP H
do j=1 for words(difs) /*traipse through the lists.*/ dif= translate( word(difs, j),,.); dw= words(dif) /*obtain true differences. */ do i=1 for dw; dif.i= word(dif, i) /*build an array of diffs. */ end /*i*/ /* [↑] for optimization. */ say center('primes with differences of:' dif, 50, '─') /*display title.*/ p= 1; c= 0; grp= /*init. prime#, count, grp.*/ do a=1; p= nextP(p+1); if p==0 then leave /*find the next DIF primes*/ aa= p; !.= /*AA: nextP; the group #'s.*/ !.1= p /*assign 1st prime in group.*/ do g=2 for dw /*get the rest of the group.*/ aa= nextP(aa+1); if aa==0 then leave a /*obtain the next prime. */ !.g= aa; _= g-1 /*prepare to add difference.*/ if !._ + dif._\==!.g then iterate a /*determine if fits criteria*/ end /*g*/ c= c+1 /*bump count of # of groups.*/ grp= !.1; do b=2 for dw; grp= grp !.b /*build a list of primes. */ end /*b*/ if c==1 then say ' first group: ' grp /*display the first group. */ end /*a*/ /* [↓] test if group found.*/ if grp== then say " (none)" /*display the last group. */ else say ' last group: ' grp /* " " " " */ say ' count: ' c /* " " group count. */ say end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ nextP: do nxt=arg(1) to H; if @.nxt==. then return nxt; end /*nxt*/; return 0 /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: procedure expose @.; parse arg N; != 0; @.=.; @.1= /*initialize the array.*/
do e=4 by 2 for (N-1)%2; @.e=; end /*treat the even integers > 2 special.*/ /*all primes are indicated with a "." */ do j=1 by 2 for (N-1)%2; k= j /*use odd integers up to N inclusive.*/ if @.j==. then do; if ! then iterate /*Prime? Should skip the top part ? */ jj= j * j /*compute the square of J. ___ */ if jj>N then != 1 /*indicate skip top part if j > √ N */ do m=jj to N by j+j; @.m=; end /*odd multiples.*/ end /* [↑] strike odd multiples ¬ prime. */ end /*j*/; return</lang>
- output when using the default inputs:
──────────primes with differences of: 2─────────── first group: 3 5 last group: 999959 999961 count: 8169 ──────────primes with differences of: 1─────────── first group: 2 3 last group: 2 3 count: 1 ─────────primes with differences of: 2 2────────── first group: 3 5 7 last group: 3 5 7 count: 1 ─────────primes with differences of: 2 4────────── first group: 5 7 11 last group: 999431 999433 999437 count: 1393 ─────────primes with differences of: 4 2────────── first group: 7 11 13 last group: 997807 997811 997813 count: 1444 ────────primes with differences of: 6 4 2───────── first group: 31 37 41 43 last group: 997141 997147 997151 997153 count: 306
Ruby
<lang ruby>require 'prime' PRIMES = Prime.each(1_000_000).to_a difs = [[2], [1], [2,2], [2,4], [4,2], [6,4,2]]
difs.each do |ar|
res = PRIMES.each_cons(ar.size+1).select do |slice| slice.each_cons(2).zip(ar).all? {|(a,b), c| a+c == b} end puts "#{ar} has #{res.size} sets. #{res.first}...#{res.last}"
end </lang>
- Output:
[2] has 8169 sets. [3, 5]...[999959, 999961] [1] has 1 sets. [2, 3]...[2, 3] [2, 2] has 1 sets. [3, 5, 7]...[3, 5, 7] [2, 4] has 1393 sets. [5, 7, 11]...[999431, 999433, 999437] [4, 2] has 1444 sets. [7, 11, 13]...[997807, 997811, 997813] [6, 4, 2] has 306 sets. [31, 37, 41, 43]...[997141, 997147, 997151, 997153]
Scala
<lang scala>object SuccessivePrimeDiffs {
def main(args: Array[String]): Unit = { val d2 = primesByDiffs(2)(1000000) val d1 = primesByDiffs(1)(1000000) val d22 = primesByDiffs(2, 2)(1000000) val d24 = primesByDiffs(2, 4)(1000000) val d42 = primesByDiffs(4, 2)(1000000) val d642 = primesByDiffs(6, 4, 2)(1000000) if(true) println( s"""|Diffs: (First), (Last), Count |2: (${d2.head.mkString(", ")}), (${d2.last.mkString(", ")}), ${d2.size} |1: (${d1.head.mkString(", ")}), (${d1.last.mkString(", ")}), ${d1.size} |2-2: (${d22.head.mkString(", ")}), (${d22.last.mkString(", ")}), ${d22.size} |2-4: (${d24.head.mkString(", ")}), (${d24.last.mkString(", ")}), ${d24.size} |4-2: (${d42.head.mkString(", ")}), (${d42.last.mkString(", ")}), ${d42.size} |6-4-2: (${d642.head.mkString(", ")}), (${d642.last.mkString(", ")}), ${d642.size} |""".stripMargin) } def primesByDiffs(diffs: Int*)(max: Int): LazyList[Vector[Int]] = { primesSliding(diffs.size + 1) .takeWhile(_.last <= max) .filter{vec => diffs.zip(vec.init).map{case (a, b) => a + b} == vec.tail} .to(LazyList) } def primesSliding(len: Int): Iterator[Vector[Int]] = primes.sliding(len).map(_.toVector) def primes: LazyList[Int] = 2 #:: LazyList.from(3, 2).filter(n => !Iterator.range(3, math.sqrt(n).toInt + 1, 2).exists(n%_ == 0))
}</lang>
- Output:
Diffs: (First), (Last), Count 2: (3, 5), (999959, 999961), 8169 1: (2, 3), (2, 3), 1 2-2: (3, 5, 7), (3, 5, 7), 1 2-4: (5, 7, 11), (999431, 999433, 999437), 1393 4-2: (7, 11, 13), (997807, 997811, 997813), 1444 6-4-2: (31, 37, 41, 43), (997141, 997147, 997151, 997153), 306
Sidef
<lang ruby>var limit = 1e6 var primes = limit.primes
say "Groups of successive primes <= #{limit.commify}:"
for diffs in [[2], [1], [2,2], [2,4], [4,2], [6,4,2]] {
var groups = [] primes.each_cons(diffs.len+1, {|*group| if (group.map_cons(2, {|a,b| b-a}) == diffs) { groups << group } })
say ("...for differences #{diffs}, there are #{groups.len} groups, where ", "the first group = #{groups.first} and the last group = #{groups.last}")
}</lang>
- Output:
Groups of successive primes <= 1,000,000: ...for differences [2], there are 8169 groups, where the first group = [3, 5] and the last group = [999959, 999961] ...for differences [1], there are 1 groups, where the first group = [2, 3] and the last group = [2, 3] ...for differences [2, 2], there are 1 groups, where the first group = [3, 5, 7] and the last group = [3, 5, 7] ...for differences [2, 4], there are 1393 groups, where the first group = [5, 7, 11] and the last group = [999431, 999433, 999437] ...for differences [4, 2], there are 1444 groups, where the first group = [7, 11, 13] and the last group = [997807, 997811, 997813] ...for differences [6, 4, 2], there are 306 groups, where the first group = [31, 37, 41, 43] and the last group = [997141, 997147, 997151, 997153]
zkl
GNU Multiple Precision Arithmetic Library
Using GMP ( probabilistic primes), because it is easy and fast to generate primes.
Extensible prime generator#zkl could be used instead.
Treat this as a string search problem. <lang zkl>const PRIME_LIMIT=1_000_000; var [const] BI=Import("zklBigNum"); // libGMP var [const] primeBitMap=Data(PRIME_LIMIT).fill(0x30); // one big string p:= BI(1); while(p.nextPrime()<=PRIME_LIMIT){ primeBitMap[p]="1" } // bitmap of primes
fcn primeWindows(m,deltas){ // eg (6,4,2)
n,r := 0,List(); ds:=deltas.len().pump(List,'wrap(n){ deltas[0,n+1].sum(0) }); // (6,10,12) sp:=Data(Void,"1" + "0"*deltas.sum(0)); foreach n in (ds){ sp[n]="1" } // "1000001000101" while(n=primeBitMap.find(sp,n+1)){ r.append(n) } // (31, 61, 271,...) r.apply('wrap(n){ T(n).extend(ds.apply('+(n))) }) //( (31,37,41,43), (61,67,71,73), (271,277,281,283) ...)
}</lang> <lang zkl>foreach w in (T( T(2), T(1), T(2,2), T(2,4), T(4,2), T(6,4,2) )){
r:=primeWindows(PRIME_LIMIT,w); println("Successive primes (<=%,d) with deltas of %s (%,d groups):" .fmt(PRIME_LIMIT,w.concat(","),r.len())); println(" First group: %s; Last group: %s\n" .fmt(r[0].concat(", "),r[-1].concat(", ")));
}</lang>
- Output:
Successive primes (<=1,000,000) with deltas of 2 (8,169 groups): First group: 3, 5; Last group: 999959, 999961 Successive primes (<=1,000,000) with deltas of 1 (1 groups): First group: 2, 3; Last group: 2, 3 Successive primes (<=1,000,000) with deltas of 2,2 (1 groups): First group: 3, 5, 7; Last group: 3, 5, 7 Successive primes (<=1,000,000) with deltas of 2,4 (1,393 groups): First group: 5, 7, 11; Last group: 999431, 999433, 999437 Successive primes (<=1,000,000) with deltas of 4,2 (1,444 groups): First group: 7, 11, 13; Last group: 997807, 997811, 997813 Successive primes (<=1,000,000) with deltas of 6,4,2 (306 groups): First group: 31, 37, 41, 43; Last group: 997141, 997147, 997151, 997153