Strange unique prime triplets
Primes n, m, and p are strange unique primes if n, m, and p are unique and their sum n + m + p is also prime. Assume n < m < p.
- Task
-
- Find all triplets of strange unique primes in which n, m, and p are all less than 30.
- (stretch goal) Show the count (only) of all the triplets of strange unique primes in which n, m, and p are all less than 1,000.
11l
<lang 11l>F primes_upto(limit)
V is_prime = [0B] * 2 [+] [1B] * (limit - 1) L(n) 0 .< Int(limit ^ 0.5 + 1.5) I is_prime[n] L(i) (n * n .< limit + 1).step(n) is_prime[i] = 0B R enumerate(is_prime).filter((i, prime) -> prime).map((i, prime) -> i)
F strange_triplets(Int mx = 30)
[(Int, Int, Int)] r V primes = Array(primes_upto(mx)) V primes3 = Set(primes_upto(3 * mx)) L(n) primes V i = L.index L(m) primes[i + 1 ..] V j = L.index + i + 1 L(p) primes[j + 1 ..] I n + m + p C primes3 r.append((n, m, p)) R r
L(n, m, p) strange_triplets()
print(‘#2: #2+#2+#2 = #.’.format(L.index + 1, n, m, p, n + m + p))
V mx = 1'000 print("\nIf n, m, p < #. finds #.".format(mx, strange_triplets(mx).len))</lang>
- Output:
1: 3+ 5+11 = 19 2: 3+ 5+23 = 31 3: 3+ 5+29 = 37 4: 3+ 7+13 = 23 5: 3+ 7+19 = 29 6: 3+11+17 = 31 7: 3+11+23 = 37 8: 3+11+29 = 43 9: 3+17+23 = 43 10: 5+ 7+11 = 23 11: 5+ 7+17 = 29 12: 5+ 7+19 = 31 13: 5+ 7+29 = 41 14: 5+11+13 = 29 15: 5+13+19 = 37 16: 5+13+23 = 41 17: 5+13+29 = 47 18: 5+17+19 = 41 19: 5+19+23 = 47 20: 5+19+29 = 53 21: 7+11+13 = 31 22: 7+11+19 = 37 23: 7+11+23 = 41 24: 7+11+29 = 47 25: 7+13+17 = 37 26: 7+13+23 = 43 27: 7+17+19 = 43 28: 7+17+23 = 47 29: 7+17+29 = 53 30: 7+23+29 = 59 31: 11+13+17 = 41 32: 11+13+19 = 43 33: 11+13+23 = 47 34: 11+13+29 = 53 35: 11+17+19 = 47 36: 11+19+23 = 53 37: 11+19+29 = 59 38: 13+17+23 = 53 39: 13+17+29 = 59 40: 13+19+29 = 61 41: 17+19+23 = 59 42: 19+23+29 = 71 If n, m, p < 1000 finds 241580
ALGOL 68
which is based on
<lang algol68>BEGIN # find some strange unique primes - triplets of primes n, m, p #
# where n + m + p is also prime and n =/= m =/= p # # we need to find the strange unique prime triplets below 1000 # # so the maximum triplet sum could be roughly 3000 # INT max number = 1000; INT max prime = max number * 3; # sieve the primes to max prime # [ 1 : max prime ]BOOL prime; prime[ 1 ] := FALSE; prime[ 2 ] := TRUE; FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD; FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD; FOR i FROM 3 BY 2 TO ENTIER sqrt( max prime ) DO IF prime[ i ] THEN FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD FI OD; # we need to find the strange unique prime triplets below 1000 # INT s count := 0, c30 := 0; # 2 cannot be one of the primes as the sum would be even otherwise # FOR n FROM 3 BY 2 TO max number - 5 DO IF prime[ n ] THEN FOR m FROM n + 2 BY 2 TO max number- 3 DO IF prime[ m ] THEN FOR p FROM m + 2 BY 2 TO max number DO IF prime[ p ] THEN IF INT s = n + m + p; prime[ s ] THEN # have 3 unique primes whose sum is prime # s count +:= 1; IF p <= 30 AND m <= 30 AND n <= 30 THEN c30 +:= 1; print( ( whole( c30, -3 ), ": " , whole( n, -3 ), " + " , whole( m, -3 ), " + " , whole( p, -3 ), " = " , whole( s, -3 ), newline ) ) FI FI FI OD # p # FI OD # m # FI OD # n # ; print( ( "Found ", whole( c30, -6 ), " strange unique prime triplets up to 30", newline ) ); print( ( "Found ", whole( s count, -6 ), " strange unique prime triplets up to 1000", newline ) )
END</lang>
- Output:
1: 3 + 5 + 11 = 19 2: 3 + 5 + 23 = 31 3: 3 + 5 + 29 = 37 4: 3 + 7 + 13 = 23 5: 3 + 7 + 19 = 29 6: 3 + 11 + 17 = 31 7: 3 + 11 + 23 = 37 8: 3 + 11 + 29 = 43 9: 3 + 17 + 23 = 43 10: 5 + 7 + 11 = 23 11: 5 + 7 + 17 = 29 12: 5 + 7 + 19 = 31 13: 5 + 7 + 29 = 41 14: 5 + 11 + 13 = 29 15: 5 + 13 + 19 = 37 16: 5 + 13 + 23 = 41 17: 5 + 13 + 29 = 47 18: 5 + 17 + 19 = 41 19: 5 + 19 + 23 = 47 20: 5 + 19 + 29 = 53 21: 7 + 11 + 13 = 31 22: 7 + 11 + 19 = 37 23: 7 + 11 + 23 = 41 24: 7 + 11 + 29 = 47 25: 7 + 13 + 17 = 37 26: 7 + 13 + 23 = 43 27: 7 + 17 + 19 = 43 28: 7 + 17 + 23 = 47 29: 7 + 17 + 29 = 53 30: 7 + 23 + 29 = 59 31: 11 + 13 + 17 = 41 32: 11 + 13 + 19 = 43 33: 11 + 13 + 23 = 47 34: 11 + 13 + 29 = 53 35: 11 + 17 + 19 = 47 36: 11 + 19 + 23 = 53 37: 11 + 19 + 29 = 59 38: 13 + 17 + 23 = 53 39: 13 + 17 + 29 = 59 40: 13 + 19 + 29 = 61 41: 17 + 19 + 23 = 59 42: 19 + 23 + 29 = 71 Found 42 strange unique prime triplets up to 30 Found 241580 strange unique prime triplets up to 1000
ALGOL W
Based on
<lang algolw>begin % find some strange unique primes - triplets of primes n, m, p %
% where n + m + p is also prime and n =/= m =/= p % % sets p( 1 :: n ) to a sieve of primes up to n % procedure Eratosthenes ( logical array p( * ) ; integer value n ) ; begin p( 1 ) := false; p( 2 ) := true; for i := 3 step 2 until n do p( i ) := true; for i := 4 step 2 until n do p( i ) := false; for i := 3 step 2 until truncate( sqrt( n ) ) do begin integer ii; ii := i + i; if p( i ) then for pr := i * i step ii until n do p( pr ) := false end for_i ; end Eratosthenes ; % we need to find the strange unique prime triplets below 1000 % integer MAX_PRIME; MAX_PRIME := 1000; begin % the sum of the triplets could be (roughly) 3 x the largest prime % logical array p ( 1 :: MAX_PRIME * 3 ); integer sCount, c30; % construct a sieve of primes up to MAX_PRIME * 3 % Eratosthenes( p, MAX_PRIME * 3 ); % count the nice prime triplets whose members are less than 1000 % % and prime the first 30 % sCount := c30 := 0; % 2 cannot be one of the primes as the sum would be even otherwise % for n := 3 step 2 until MAX_PRIME - 5 do begin if p( n ) then begin for m := n + 2 step 2 until MAX_PRIME - 3 do begin if p( m ) then begin for l := m + 2 STEP 2 until MAX_PRIME do begin if p( l ) then begin integer s; s := n + m + l; if p( s ) then begin sCount := sCount + 1; if l <= 30 and m <= 30 and n <= 30 then begin c30 := c30 + 1; write( i_w := 3, s_w := 0, c30, ": ", n, " + ", m, " + ", l, " = ", s ) end if_l_m_n_le_30 end if_p_s end if_p_l end for_l end if_p_m end for_m end if_p_n end for_n ; write( i_w := 3, s_w := 0, "Found ", c30, " strange unique prime triplets up to 30" ); write( i_w := 3, s_w := 0, "Found ", sCount, " strange unique prime triplets up to 1000" ); end
end.</lang>
- Output:
1: 3 + 5 + 11 = 19 2: 3 + 5 + 23 = 31 3: 3 + 5 + 29 = 37 4: 3 + 7 + 13 = 23 5: 3 + 7 + 19 = 29 6: 3 + 11 + 17 = 31 7: 3 + 11 + 23 = 37 8: 3 + 11 + 29 = 43 9: 3 + 17 + 23 = 43 10: 5 + 7 + 11 = 23 11: 5 + 7 + 17 = 29 12: 5 + 7 + 19 = 31 13: 5 + 7 + 29 = 41 14: 5 + 11 + 13 = 29 15: 5 + 13 + 19 = 37 16: 5 + 13 + 23 = 41 17: 5 + 13 + 29 = 47 18: 5 + 17 + 19 = 41 19: 5 + 19 + 23 = 47 20: 5 + 19 + 29 = 53 21: 7 + 11 + 13 = 31 22: 7 + 11 + 19 = 37 23: 7 + 11 + 23 = 41 24: 7 + 11 + 29 = 47 25: 7 + 13 + 17 = 37 26: 7 + 13 + 23 = 43 27: 7 + 17 + 19 = 43 28: 7 + 17 + 23 = 47 29: 7 + 17 + 29 = 53 30: 7 + 23 + 29 = 59 31: 11 + 13 + 17 = 41 32: 11 + 13 + 19 = 43 33: 11 + 13 + 23 = 47 34: 11 + 13 + 29 = 53 35: 11 + 17 + 19 = 47 36: 11 + 19 + 23 = 53 37: 11 + 19 + 29 = 59 38: 13 + 17 + 23 = 53 39: 13 + 17 + 29 = 59 40: 13 + 19 + 29 = 61 41: 17 + 19 + 23 = 59 42: 19 + 23 + 29 = 71 Found 42 strange unique prime triplets up to 30 Found 241580 strange unique prime triplets up to 1000
AWK
<lang AWK>
- syntax: GAWK -f STRANGE_UNIQUE_PRIME_TRIPLETS.AWK
- converted from Go
BEGIN {
main(29,1) main(999,0) exit(0)
} function main(n,show, count,i,j,k,s) {
for (i=3; i<=n-4; i+=2) { if (is_prime(i)) { for (j=i+2; j<=n-2; j+=2) { if (is_prime(j)) { for (k=j+2; k<=n; k+=2) { if (is_prime(k)) { s = i + j + k if (is_prime(s)) { count++ if (show == 1) { printf("%2d + %2d + %2d = %d\n",i,j,k,s) } } } } } } } } printf("Unique prime triples 2-%d which sum to a prime: %'d\n\n",n,count)
} 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:
3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Unique prime triples 2-29 which sum to a prime: 42 Unique prime triples 2-999 which sum to a prime: 241,580
C
<lang c>#include <stdbool.h>
- include <stdio.h>
- include <string.h>
- define LIMIT 3000
void init_sieve(unsigned char sieve[], int limit) {
int i, j;
for (i = 0; i < limit; i++) { sieve[i] = 1; } sieve[0] = 0; sieve[1] = 0;
for (i = 2; i < limit; i++) { if (sieve[i]) { for (j = i + i; j < limit; j += i) { sieve[j] = 0; } } }
}
void strange_unique_prime_triplets(unsigned char sieve[], int limit, bool verbose) {
int count = 0, sum; int i, j, k, n, p; int pi, pj, pk;
n = 0; for (i = 0; i < limit; i++) { if (sieve[i]) { n++; } }
if (verbose) { printf("Strange unique prime triplets < %d:\n", limit); }
for (i = 0; i + 2 < n; i++) { pi = 2; p = i; while (p > 0) { pi++; if (sieve[pi]) { p--; } }
for (j = i + 1; j + 1 < n; j++) { pj = pi; p = j - i; while (p > 0) { pj++; if (sieve[pj]) { p--; } }
for (k = j + 1; k < n; k++) { pk = pj; p = k - j; while (p > 0) { pk++; if (sieve[pk]) { p--; } }
sum = pi + pj + pk; if (sum < LIMIT && sieve[sum]) { count++; if (verbose) { printf("%2d + %2d + %2d = %d\n", pi, pj, pk, sum); } } } } }
printf("Count of strange unique prime triplets < %d is %d.\n\n", limit, count);
}
int main() {
unsigned char sieve[LIMIT];
init_sieve(sieve, LIMIT);
strange_unique_prime_triplets(sieve, 30, true); strange_unique_prime_triplets(sieve, 1000, false);
return 0;
}</lang>
- Output:
Strange unique prime triplets < 30: 3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Count of strange unique prime triplets < 30 is 42. Count of strange unique prime triplets < 1000 is 241580.
C#
Just for fun, <30 sorted by sum, instead of order generated. One might think one should include the sieve generation time, but it is orders of magnitude smaller than the permute/sum time for these relatively low numbers. <lang csharp>using System; using System.Collections.Generic; using static System.Console; using System.Linq; using DT = System.DateTime;
class Program { static void Main(string[] args) { string s;
foreach (int lmt in new int[]{ 90, 300, 3000, 30000, 111000 }) { var pr = PG.Primes(lmt).Skip(1).ToList(); DT st = DT.Now; int d, f = 0; var r = new List<string>(); int i = -1, m, h = (m = lmt / 3), j, k, pra, prab; while (i < 0) i = pr.IndexOf(h--); k = (j = i - 1) - 1; for (int a = 0; a <= k; a++) { pra = pr[a]; for (int b = a + 1; b <= j; b++) { prab = pra + pr[b]; for (int c = b + 1; c <= i; c++) { if (PG.flags[d = prab + pr[c]]) continue; f++; if (lmt < 100) r.Add(string.Format("{3,5} = {0,2} + {1,2} + {2,2}", pra, pr[b], pr[c], d)); } } } s = "s.u.p.t.s under "; r.Sort(); if (r.Count > 0) WriteLine("{0}{1}:\n{2}", s, m, string.Join("\n", r)); if (lmt > 100) WriteLine("Count of {0}{1,6:n0}: {2,13:n0} {3} sec", s, m, f, (DT.Now - st).ToString().Substring(6)); } } }
class PG { public static bool[] flags;
public static IEnumerable<int> Primes(int lim) { flags = new bool[lim + 1]; int j = 2; for (int d = 3, sq = 4; sq <= lim; j++, sq += d += 2) if (!flags[j]) { yield return j; for (int k = sq; k <= lim; k += j) flags[k] = true; } for (; j <= lim; j++) if (!flags[j]) yield return j; } }</lang>
- Output:
Timings from tio.run
s.u.p.t.s under 30: 19 = 3 + 5 + 11 23 = 3 + 7 + 13 23 = 5 + 7 + 11 29 = 3 + 7 + 19 29 = 5 + 7 + 17 29 = 5 + 11 + 13 31 = 3 + 5 + 23 31 = 3 + 11 + 17 31 = 5 + 7 + 19 31 = 7 + 11 + 13 37 = 3 + 5 + 29 37 = 3 + 11 + 23 37 = 5 + 13 + 19 37 = 7 + 11 + 19 37 = 7 + 13 + 17 41 = 5 + 7 + 29 41 = 5 + 13 + 23 41 = 5 + 17 + 19 41 = 7 + 11 + 23 41 = 11 + 13 + 17 43 = 3 + 11 + 29 43 = 3 + 17 + 23 43 = 7 + 13 + 23 43 = 7 + 17 + 19 43 = 11 + 13 + 19 47 = 5 + 13 + 29 47 = 5 + 19 + 23 47 = 7 + 11 + 29 47 = 7 + 17 + 23 47 = 11 + 13 + 23 47 = 11 + 17 + 19 53 = 5 + 19 + 29 53 = 7 + 17 + 29 53 = 11 + 13 + 29 53 = 11 + 19 + 23 53 = 13 + 17 + 23 59 = 7 + 23 + 29 59 = 11 + 19 + 29 59 = 13 + 17 + 29 59 = 17 + 19 + 23 61 = 13 + 19 + 29 71 = 19 + 23 + 29 Count of s.u.p.t.s under 100: 891 00.0000243 sec Count of s.u.p.t.s under 1,000: 241,580 00.0054753 sec Count of s.u.p.t.s under 10,000: 74,588,542 01.8159964 sec Count of s.u.p.t.s under 37,000: 2,141,379,201 55.0369689 sec
C++
<lang cpp>#include <iomanip>
- include <iostream>
- include <vector>
std::vector<bool> prime_sieve(size_t limit) {
std::vector<bool> sieve(limit, true); if (limit > 0) sieve[0] = false; if (limit > 1) sieve[1] = false; for (size_t i = 4; i < limit; i += 2) sieve[i] = false; for (size_t p = 3; ; p += 2) { size_t q = p * p; if (q >= limit) break; if (sieve[p]) { size_t inc = 2 * p; for (; q < limit; q += inc) sieve[q] = false; } } return sieve;
}
void strange_unique_prime_triplets(int limit, bool verbose) {
std::vector<bool> sieve = prime_sieve(limit * 3); std::vector<int> primes; for (int p = 3; p < limit; p += 2) { if (sieve[p]) primes.push_back(p); } size_t n = primes.size(); size_t count = 0; if (verbose) std::cout << "Strange unique prime triplets < " << limit << ":\n"; for (size_t i = 0; i + 2 < n; ++i) { for (size_t j = i + 1; j + 1 < n; ++j) { for (size_t k = j + 1; k < n; ++k) { int sum = primes[i] + primes[j] + primes[k]; if (sieve[sum]) { ++count; if (verbose) { std::cout << std::setw(2) << primes[i] << " + " << std::setw(2) << primes[j] << " + " << std::setw(2) << primes[k] << " = " << sum << '\n'; } } } } } std::cout << "\nCount of strange unique prime triplets < " << limit << " is " << count << ".\n";
}
int main() {
strange_unique_prime_triplets(30, true); strange_unique_prime_triplets(1000, false); return 0;
}</lang>
- Output:
Strange unique prime triplets < 30: 3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Count of strange unique prime triplets < 30 is 42. Count of strange unique prime triplets < 1000 is 241580.
Delphi
<lang Delphi> program Strange_primes;
{$APPTYPE CONSOLE}
uses
System.SysUtils;
function IsPrime(n: Integer): Boolean; begin
if n < 2 then exit(false);
if n mod 2 = 0 then exit(n = 2);
if n mod 3 = 0 then exit(n = 3);
var d := 5; while d * d <= n do begin if n mod d = 0 then exit(false);
inc(d, 2);
if n mod d = 0 then exit(false);
inc(d, 4); end; Result := true;
end;
function Commatize(value: Integer): string; begin
Result := FloatToStrF(value, ffNumber, 10, 0);
end;
function StrangePrimes(n: Integer; countOnly: Boolean): Integer; begin
var c := 0; var f := '%2d: %2d + %2d + %2d = %2d'#10; var s: Integer := 0;
var i := 3; while i <= n - 4 do begin if IsPrime(i) then begin var j := i + 2; while j <= n - 2 do begin if IsPrime(j) then begin var k := j + 2; while k <= n do begin if IsPrime(k) then begin s := i + j + k; if IsPrime(s) then begin inc(c); if not countOnly then write(format(f, [c, i, j, k, s])); end; end; inc(k, 2); end; end; inc(j, 2); end; end; inc(i, 2); end; Result := c;
end;
begin
Writeln('Unique prime triples under 30 which sum to a prime:'); strangePrimes(29, false); var cs := commatize(strangePrimes(999, true)); writeln('There are ', cs, ' unique prime triples under 1,000 which sum to a prime.'); readln;
end.</lang>
F#
This task uses Extensible Prime Generator (F#).
<lang fsharp>
// Strange unique prime triplets. Nigel Galloway: March 12th., 2021
let sP n=let N=primes32()|>Seq.takeWhile((>)n)|>Array.ofSeq
seq{for n in 0..N.Length-1 do for i in n+1..N.Length-1 do for g in i+1..N.Length-1->(N.[n],N.[i],N.[g])}|>Seq.filter(fun(n,i,g)->isPrime(n+i+g))
sP 30|>Seq.iteri(fun n(i,g,l)->printfn "%2d: %2d+%2d+%2d=%2d") printfn "%d" (Seq.length(sP 1000)) printfn "%d" (Seq.length(sP 10000)) </lang>
- Output:
241580 74588542
Factor
<lang factor>USING: formatting io kernel math math.combinatorics math.primes sequences tools.memory.private ;
- .triplet ( seq -- ) "%2d+%2d+%2d = %d\n" vprintf ;
- strange ( n -- )
primes-upto 3 [ dup sum dup prime? [ suffix .triplet ] [ 2drop ] if ] each-combination ;
- count-strange ( n -- count )
0 swap primes-upto 3 [ sum prime? [ 1 + ] when ] each-combination ;
30 strange 1,000 count-strange commas nl "Found %s strange prime triplets with n, m, p < 1,000.\n" printf</lang>
- Output:
3+ 5+11 = 19 3+ 5+23 = 31 3+ 5+29 = 37 3+ 7+13 = 23 3+ 7+19 = 29 3+11+17 = 31 3+11+23 = 37 3+11+29 = 43 3+17+23 = 43 5+ 7+11 = 23 5+ 7+17 = 29 5+ 7+19 = 31 5+ 7+29 = 41 5+11+13 = 29 5+13+19 = 37 5+13+23 = 41 5+13+29 = 47 5+17+19 = 41 5+19+23 = 47 5+19+29 = 53 7+11+13 = 31 7+11+19 = 37 7+11+23 = 41 7+11+29 = 47 7+13+17 = 37 7+13+23 = 43 7+17+19 = 43 7+17+23 = 47 7+17+29 = 53 7+23+29 = 59 11+13+17 = 41 11+13+19 = 43 11+13+23 = 47 11+13+29 = 53 11+17+19 = 47 11+19+23 = 53 11+19+29 = 59 13+17+23 = 53 13+17+29 = 59 13+19+29 = 61 17+19+23 = 59 19+23+29 = 71 Found 241,580 strange prime triplets with n, m, p < 1,000.
Fermat
<lang fermat>Function IsSUPT(n,m,p) =
if Isprime(n) and Isprime(m) and Isprime(p) and Isprime(n+m+p) then 1 else 0 fi.
for n=3 to 19 do
for m=n+2 to 23 do for p=m+2 to 29 do if IsSUPT(n,m,p) then !!(n,m,p) fi; od; od;
od</lang> I'll leave the stretch goal for someone else.
FreeBASIC
Use the function at Primality by trial division#FreeBASIC as an include; I can't be bothered reproducing it here. <lang freebasic>#include"isprime.bas"
dim as uinteger c = 0
for p as uinteger = 3 to 997
if not isprime(p) then continue for for m as uinteger = p + 1 to 998 if not isprime(m) then continue for for n as uinteger = m + 1 to 999 if not isprime(n) then continue for if isprime(p + n + m) then c = c + 1 if n < 30 then print p;" + ";m;" + ";n;" = "; p + m + n end if next n next m
next p
print "There are ";c;" triples below 1000."</lang>
- Output:
3 + 5 + 11 = 193 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71
There are 241580 triples below 1000.
Forth
<lang forth>: prime? ( n -- ? ) here + c@ 0= ;
- notprime! ( n -- ) here + 1 swap c! ;
- prime_sieve ( n -- )
here over erase 0 notprime! 1 notprime! dup 4 > if dup 4 do i notprime! 2 +loop then 3 begin 2dup dup * > while dup prime? if 2dup dup * do i notprime! dup 2* +loop then 2 + repeat 2drop ;
- print_strange_unique_prime_triplets ( n -- )
dup 8 < if drop exit then dup 3 * prime_sieve dup 4 - 3 do i prime? if dup 2 - i 2 + do i prime? if dup i 2 + do i prime? if i j k + + dup prime? if k 2 .r ." + " j 2 .r ." + " i 2 .r ." = " 2 .r cr else drop then then 2 +loop then 2 +loop then 2 +loop drop ;
- count_strange_unique_prime_triplets ( n -- n )
dup 8 < if drop 0 exit then dup 3 * prime_sieve 0 swap dup 4 - 3 do i prime? if dup 2 - i 2 + do i prime? if dup i 2 + do i prime? if i j k + + prime? if swap 1+ swap then then 2 +loop then 2 +loop then 2 +loop drop ;
." Strange unique prime triplets < 30:" cr 30 print_strange_unique_prime_triplets
." Count of strange unique prime triplets < 1000: " 1000 count_strange_unique_prime_triplets . cr bye</lang>
- Output:
Strange unique prime triplets < 30: 3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Count of strange unique prime triplets < 1000: 241580
Go
Basic
<lang go>package main
import "fmt"
func isPrime(n int) bool {
switch { case n < 2: return false case n%2 == 0: return n == 2 case n%3 == 0: return n == 3 default: d := 5 for d*d <= n { if n%d == 0 { return false } d += 2 if n%d == 0 { return false } d += 4 } return true }
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) if n < 0 { s = s[1:] } le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } if n >= 0 { return s } return "-" + s
}
func strangePrimes(n int, countOnly bool) int {
c := 0 f := "%2d: %2d + %2d + %2d = %2d\n" var s int
for i := 3; i <= n-4; i += 2 { if isPrime(i) { for j := i + 2; j <= n-2; j += 2 { if isPrime(j) { for k := j + 2; k <= n; k += 2 { if isPrime(k) { s = i + j + k if isPrime(s) { c++ if !countOnly { fmt.Printf(f, c, i, j, k, s) } } } } } } } } return c
}
func main() {
fmt.Println("Unique prime triples under 30 which sum to a prime:") strangePrimes(29, false) cs := commatize(strangePrimes(999, true)) fmt.Printf("\nThere are %s unique prime triples under 1,000 which sum to a prime.\n", cs)
}</lang>
- Output:
Unique prime triples under 30 which sum to a prime: 1: 3 + 5 + 11 = 19 2: 3 + 5 + 23 = 31 3: 3 + 5 + 29 = 37 4: 3 + 7 + 13 = 23 5: 3 + 7 + 19 = 29 6: 3 + 11 + 17 = 31 7: 3 + 11 + 23 = 37 8: 3 + 11 + 29 = 43 9: 3 + 17 + 23 = 43 10: 5 + 7 + 11 = 23 11: 5 + 7 + 17 = 29 12: 5 + 7 + 19 = 31 13: 5 + 7 + 29 = 41 14: 5 + 11 + 13 = 29 15: 5 + 13 + 19 = 37 16: 5 + 13 + 23 = 41 17: 5 + 13 + 29 = 47 18: 5 + 17 + 19 = 41 19: 5 + 19 + 23 = 47 20: 5 + 19 + 29 = 53 21: 7 + 11 + 13 = 31 22: 7 + 11 + 19 = 37 23: 7 + 11 + 23 = 41 24: 7 + 11 + 29 = 47 25: 7 + 13 + 17 = 37 26: 7 + 13 + 23 = 43 27: 7 + 17 + 19 = 43 28: 7 + 17 + 23 = 47 29: 7 + 17 + 29 = 53 30: 7 + 23 + 29 = 59 31: 11 + 13 + 17 = 41 32: 11 + 13 + 19 = 43 33: 11 + 13 + 23 = 47 34: 11 + 13 + 29 = 53 35: 11 + 17 + 19 = 47 36: 11 + 19 + 23 = 53 37: 11 + 19 + 29 = 59 38: 13 + 17 + 23 = 53 39: 13 + 17 + 29 = 59 40: 13 + 19 + 29 = 61 41: 17 + 19 + 23 = 59 42: 19 + 23 + 29 = 71 There are 241,580 unique prime triples under 1,000 which sum to a prime.
Faster
<lang go>package main
import "fmt"
var sieved []bool var p = []int{2}
func sieve(limit int) []bool {
limit++ // True denotes composite, false denotes prime. c := make([]bool, limit) // all false by default c[0] = true c[1] = true // no need to bother with even numbers over 2 for this task p := 3 // Start from 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 } } } return c
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) if n < 0 { s = s[1:] } le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } if n >= 0 { return s } return "-" + s
}
func strangePrimes(n int, countOnly bool) int {
c := 0 f := "%2d: %2d + %2d + %2d = %2d\n" var r, s int m := 0 for ; m < len(p) && p[m] <= n; m++ { } for i := 1; i < m-2; i++ { for j := i + 1; j < m-1; j++ { r = p[i] + p[j] for k := j + 1; k < m; k++ { s = r + p[k] if !sieved[s] { c++ if !countOnly { fmt.Printf(f, c, p[i], p[j], p[k], s) } } } } } return c
}
func main() {
const max = 1000 sieved = sieve(3*max) for i := 3; i <= max; i += 2 { if !sieved[i] { p = append(p, i) } } fmt.Println("Unique prime triples under 30 which sum to a prime:") strangePrimes(29, false) cs := commatize(strangePrimes(999, true)) fmt.Printf("\nThere are %s unique prime triples under 1,000 which sum to a prime.\n", cs)
}</lang>
- Output:
Same as 'basic' version.
Java
<lang java>import java.util.*;
public class StrangeUniquePrimeTriplets {
public static void main(String[] args) { strangeUniquePrimeTriplets(30, true); strangeUniquePrimeTriplets(1000, false); }
private static void strangeUniquePrimeTriplets(int limit, boolean verbose) { boolean[] sieve = primeSieve(limit * 3); List<Integer> primeList = new ArrayList<>(); for (int p = 3; p < limit; p += 2) { if (sieve[p]) primeList.add(p); } int n = primeList.size(); // Convert object list to primitive array for performance int[] primes = new int[n]; for (int i = 0; i < n; ++i) primes[i] = primeList.get(i); int count = 0; if (verbose) System.out.printf("Strange unique prime triplets < %d:\n", limit); for (int i = 0; i + 2 < n; ++i) { for (int j = i + 1; j + 1 < n; ++j) { int s = primes[i] + primes[j]; for (int k = j + 1; k < n; ++k) { int sum = s + primes[k]; if (sieve[sum]) { ++count; if (verbose) System.out.printf("%2d + %2d + %2d = %2d\n", primes[i], primes[j], primes[k], sum); } } } } System.out.printf("\nCount of strange unique prime triplets < %d is %d.\n", limit, count); }
private static boolean[] primeSieve(int limit) { boolean[] sieve = new boolean[limit]; Arrays.fill(sieve, true); if (limit > 0) sieve[0] = false; if (limit > 1) sieve[1] = false; for (int i = 4; i < limit; i += 2) sieve[i] = false; for (int p = 3; ; p += 2) { int q = p * p; if (q >= limit) break; if (sieve[p]) { int inc = 2 * p; for (; q < limit; q += inc) sieve[q] = false; } } return sieve; }
}</lang>
- Output:
Strange unique prime triplets < 30: 3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Count of strange unique prime triplets < 30 is 42. Count of strange unique prime triplets < 1000 is 241580.
Julia
<lang julia>using Primes
function prime_sum_prime_triplets_to(N, verbose=false)
a = primes(3, N) prime_sieve_set = primesmask(1, N * 3) len, triplets, n = length(a), Dict{Tuple{Int64,Int64,Int64}, Int}(), 0 for i in eachindex(a), j in i+1:len, k in j+1:len if prime_sieve_set[a[i] + a[j] + a[k]] verbose && (triplets[(a[i], a[j], a[k])] = 1) n += 1 end end if verbose len = (length(string(N)) + 2) * 3 println("\n", rpad("Triplet", len), "Sum\n", "-"^(len+3)) for k in sort(collect(keys(triplets)), lt = (x, y) -> collect(x) < collect(y)) println(rpad(k, len), sum(k)) end end println("\n\n$n unique triplets of 3 primes between 2 and $N sum to a prime.") return triplets
end
prime_sum_prime_triplets_to(30, true) prime_sum_prime_triplets_to(1000) @time prime_sum_prime_triplets_to(10000) @time prime_sum_prime_triplets_to(100000)
</lang>
- Output:
Triplet Sum --------------- (3, 5, 11) 19 (3, 5, 23) 31 (3, 5, 29) 37 (3, 7, 13) 23 (3, 7, 19) 29 (3, 11, 17) 31 (3, 11, 23) 37 (3, 11, 29) 43 (3, 17, 23) 43 (5, 7, 11) 23 (5, 7, 17) 29 (5, 7, 19) 31 (5, 7, 29) 41 (5, 11, 13) 29 (5, 13, 19) 37 (5, 13, 23) 41 (5, 13, 29) 47 (5, 17, 19) 41 (5, 19, 23) 47 (5, 19, 29) 53 (7, 11, 13) 31 (7, 11, 19) 37 (7, 11, 23) 41 (7, 11, 29) 47 (7, 13, 17) 37 (7, 13, 23) 43 (7, 17, 19) 43 (7, 17, 23) 47 (7, 17, 29) 53 (7, 23, 29) 59 (11, 13, 17)41 (11, 13, 19)43 (11, 13, 23)47 (11, 13, 29)53 (11, 17, 19)47 (11, 19, 23)53 (11, 19, 29)59 (13, 17, 23)53 (13, 17, 29)59 (13, 19, 29)61 (17, 19, 23)59 (19, 23, 29)71 42 unique triplets of 3 primes between 2 and 30 sum to a prime. 241580 unique triplets of 3 primes between 2 and 1000 sum to a prime. 74588542 unique triplets of 3 primes between 2 and 10000 sum to a prime. 0.509732 seconds (31 allocations: 25.938 KiB) 28694800655 unique triplets of 3 primes between 2 and 100000 sum to a prime. 224.940756 seconds (35 allocations: 218.156 KiB)
Nim
<lang Nim>import strformat, strutils, sugar
func isPrime(n: Positive): bool =
if n < 2: return false if n mod 2 == 0: return n == 2 if n mod 3 == 0: return n == 3 var d = 5 while d * d <= n: if n mod d == 0: return false inc d, 2 if n mod d == 0: return false inc d, 4 result = true
iterator triplets(primes: openArray[int]): (int, int, int) =
## Yield the triplets. for i in 0..primes.high-2: let n = primes[i] for j in (i+1)..primes.high-1: let m = primes[j] for k in (j+1)..primes.high: let p = primes[k] if (n + m + p).isPrime: yield (n, m, p)
const Primes30 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
echo "List of strange unique prime triplets for n < m < p < 30:"
for (n, m, p) in Primes30.triplets():
echo &"{n:2} + {m:2} + {p:2} = {n+m+p}"
echo() const Primes1000 = collect(newSeq):
for n in 2..999: if n.isPrime: n
var count = 0 for _ in Primes1000.triplets(): inc count echo "Count of strange unique prime triplets for n < m < p < 1000: ", ($count).insertSep()</lang>
- Output:
List of strange unique prime triplets for n < m < p < 30: 3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Count of strange unique prime triplets for n < m < p < 1000: 241_580
Pascal
<lang pascal>program PrimeTriplets; //Free Pascal Compiler version 3.2.1 [2020/11/03] for x86_64fpc 3.2.1 {$IFDEF FPC}
{$MODE DELPHI} {$Optimization ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} const
MAXZAHL = 100000;// > 3 MAXSUM = 3*MAXZAHL;
CountOfPrimes = trunc(MAXZAHL/(ln(MAXZAHL)-1.08))+100;
type
tChkprimes = array[0..MAXSUM] of byte;//prime == 1 , nonprime == 0
var
Chkprimes:tChkprimes; primes : array[0..CountOfPrimes]of Uint32;//here starting with 3 count,primeCount:NativeInt;
procedure InitPrimes; //sieve of eratothenes var
i,j : NativeInt;
begin
fillchar(Chkprimes,SizeOf(tChkprimes),#1); i := 2; j := 2*2; if j> MAXSUM then EXIT; repeat Chkprimes[j]:= 0; inc(j,i); until j> Maxsum; For i := 3 to MAXSUM do Begin if Chkprimes[i] <>0 then Begin j := i*i; if j> MAXSUM then Break; repeat Chkprimes[j]:= 0; inc(j,2*i); until j> Maxsum; end; end; j := 0; For i := 3 to MAXZAHL do IF Chkprimes[i]<>0 then Begin primes[j] := i; inc(j); end; primeCount := j-1; j :=CountOfPrimes -primeCount; IF j <0 then begin writeln(' Need more space for primes ', -j); HALT(-243); end;
end;
function GetMaxPrimeIdx(lmt:NativeInt):NativeInt; begin
if lmt >= Maxzahl then Begin result := primecount; EXIT; end; result := 0; while (result < primecount) AND (primes[result]<lmt) do inc(result); dec(result);
end;
procedure Out_Check(lmt:nativeInt); //simplest version var
i,j,k,s,pc: NativeInt;
Begin
pc:= GetMaxPrimeIdx(lmt); count := 0; For i := 0 to pc do For j := i+1 to pc do For k := j+1 to pc do Begin s := primes[i]+primes[j]+Primes[k]; //if takes the longest time if ChkPrimes[s]<> 0 then begin inc(count); writeln(count:3,': ',primes[i],'+',primes[j],'+',primes[k],' = ',s); end; end; writeln;
end;
procedure Count_Check(pc:nativeInt); // the power of many registers ( 64-Bit ) var
cnt : Uint64; pPrimes : pUint32; pChkPrimes : ^tChkprimes; pi,pij,i,j,k: NativeInt;
Begin
cnt := 0; pPrimes := @primes[0]; pChkPrimes := @Chkprimes[0]; For i := 0 to pc do Begin pi := pPrimes[i]; For j := i+1 to pc do begin pij := pi+pPrimes[j]; For k := j+1 to pc do inc(cnt,pChkPrimes^[pij+pPrimes[k]]); end; end; count := cnt;
end;
procedure Check_Limit(lmt:NativeInt); Begin
If lmt>primes[primecount] then lmt := MaxZahl; write('Limit = ',lmt,' count: '); Count_Check(GetMaxPrimeIdx(lmt)); writeln(count);
end;
BEGIN
InitPrimes; Out_Check(30); Check_Limit(100); Check_Limit(1000); Check_Limit(10000);
//Check_Limit(MAXZAHL); END.</lang>
- Output:
1: 3+5+11 = 19 2: 3+5+23 = 31 3: 3+5+29 = 37 4: 3+7+13 = 23 5: 3+7+19 = 29 6: 3+11+17 = 31 7: 3+11+23 = 37 8: 3+11+29 = 43 9: 3+17+23 = 43 10: 5+7+11 = 23 11: 5+7+17 = 29 12: 5+7+19 = 31 13: 5+7+29 = 41 14: 5+11+13 = 29 15: 5+13+19 = 37 16: 5+13+23 = 41 17: 5+13+29 = 47 18: 5+17+19 = 41 19: 5+19+23 = 47 20: 5+19+29 = 53 21: 7+11+13 = 31 22: 7+11+19 = 37 23: 7+11+23 = 41 24: 7+11+29 = 47 25: 7+13+17 = 37 26: 7+13+23 = 43 27: 7+17+19 = 43 28: 7+17+23 = 47 29: 7+17+29 = 53 30: 7+23+29 = 59 31: 11+13+17 = 41 32: 11+13+19 = 43 33: 11+13+23 = 47 34: 11+13+29 = 53 35: 11+17+19 = 47 36: 11+19+23 = 53 37: 11+19+29 = 59 38: 13+17+23 = 53 39: 13+17+29 = 59 40: 13+19+29 = 61 41: 17+19+23 = 59 42: 19+23+29 = 71 Limit = 100 count: 891 Limit = 1000 count: 241580 Limit = 10000 count: 74588542 //real 0m0,142s Limit = 100000 count: 28694800655 real 1m5,378s
Perl
<lang perl>use strict; use warnings; use List::Util 'sum'; use ntheory <primes is_prime>; use Algorithm::Combinatorics 'combinations';
for my $n (30, 1000) {
printf "Found %d strange unique prime triplets up to $n.\n", scalar grep { is_prime(sum @$_) } combinations(primes($n), 3);
}</lang>
- Output:
Found 42 strange unique prime triplets up to 30. Found 241580 strange unique prime triplets up to 1000.
Phix
with javascript_semantics requires("0.8.4") function create_sieve(integer limit) sequence sieve = repeat(true,limit) sieve[1] = false for i=4 to limit by 2 do sieve[i] = false end for for p=3 to floor(sqrt(limit)) by 2 do integer p2 = p*p if sieve[p2] then for k=p2 to limit by p*2 do sieve[k] = false end for end if end for return sieve end function procedure strange_triplets(integer lim, bool bCountOnly=true) atom t0 = time(), t1 = t0+1 sequence primes = get_primes_le(lim), sieve = create_sieve(lim*3), res = {} atom count = 0 -- -- It is not worth involving 2, ie primes[1], -- since (2 + any other two primes) is even, -- also we may as well leave space for {j,k}, -- {k} in the two outer loops. -- Using a sieve on the inner test is over -- ten times faster than is_prime(), whereas -- using a separate table of primes for the -- two outer loops is about twice as fast as -- scanning the sieve skipping falsies. Also -- interestingly, using nm = n+m is twice as -- fast as nmp = n+m+p. -- for i=2 to length(primes)-2 do integer n = primes[i] for j=i+1 to length(primes)-1 do integer m = primes[j], nm = n+m for k=j+1 to length(primes) do integer p = primes[k], nmp = nm+p if sieve[nmp] then count += 1 if not bCountOnly then res = append(res,sprintf("%2d: %2d+%2d+%2d = %d", {count, n, m, p, nmp})) end if end if if platform()!=JS and time()>t1 then progress("Working... (%,d)\r",{count}) t1 = time()+1 end if end for end for end for if platform()!=JS then progress("") end if string r = iff(bCountOnly?sprintf(" (%s)",{elapsed(time()-t0)}) :sprintf(":\n%s",{join(shorten(res,"",3),"\n")})) printf(1,"%,d strange triplets < %,d found%s\n\n",{count,lim,r}) end procedure strange_triplets(30,false) strange_triplets(1000) strange_triplets(10000)
- Output:
42 strange triplets < 30 found: 1: 3+ 5+11 = 19 2: 3+ 5+23 = 31 3: 3+ 5+29 = 37 ... 40: 13+19+29 = 61 41: 17+19+23 = 59 42: 19+23+29 = 71 241,580 strange triplets < 1,000 found (0.0s) 74,588,542 strange triplets < 10,000 found (11.4s)
Python
Using sympy.primerange.
<lang python>from sympy import primerange
def strange_triplets(mx: int = 30) -> None:
primes = list(primerange(0, mx)) primes3 = set(primerange(0, 3 * mx)) for i, n in enumerate(primes): for j, m in enumerate(primes[i + 1:], i + 1): for p in primes[j + 1:]: if n + m + p in primes3: yield n, m, p
for c, (n, m, p) in enumerate(strange_triplets(), 1):
print(f"{c:2}: {n:2}+{m:2}+{p:2} = {n + m + p}")
mx = 1_000 print(f"\nIf n, m, p < {mx:_} finds {sum(1 for _ in strange_triplets(mx)):_}")</lang>
- Output:
1: 3+ 5+11 = 19 2: 3+ 5+23 = 31 3: 3+ 5+29 = 37 4: 3+ 7+13 = 23 5: 3+ 7+19 = 29 6: 3+11+17 = 31 7: 3+11+23 = 37 8: 3+11+29 = 43 9: 3+17+23 = 43 10: 5+ 7+11 = 23 11: 5+ 7+17 = 29 12: 5+ 7+19 = 31 13: 5+ 7+29 = 41 14: 5+11+13 = 29 15: 5+13+19 = 37 16: 5+13+23 = 41 17: 5+13+29 = 47 18: 5+17+19 = 41 19: 5+19+23 = 47 20: 5+19+29 = 53 21: 7+11+13 = 31 22: 7+11+19 = 37 23: 7+11+23 = 41 24: 7+11+29 = 47 25: 7+13+17 = 37 26: 7+13+23 = 43 27: 7+17+19 = 43 28: 7+17+23 = 47 29: 7+17+29 = 53 30: 7+23+29 = 59 31: 11+13+17 = 41 32: 11+13+19 = 43 33: 11+13+23 = 47 34: 11+13+29 = 53 35: 11+17+19 = 47 36: 11+19+23 = 53 37: 11+19+29 = 59 38: 13+17+23 = 53 39: 13+17+29 = 59 40: 13+19+29 = 61 41: 17+19+23 = 59 42: 19+23+29 = 71 If n, m, p < 1_000 finds 241_580
Raku
(formerly Perl 6) <lang perl6># 20210312 Raku programming solution
for 30, 1000 -> \k {
given (2..k).grep(*.is-prime).combinations(3).grep(*.sum.is-prime) { say "Found ", +$_, " strange unique prime triplets up to ", k }
}</lang>
- Output:
Found 42 strange unique prime triplets up to 30 Found 241580 strange unique prime triplets up to 1000
REXX
<lang rexx>/*REXX program finds/lists triplet strange primes (<HI) where the triplets' sum is prime*/ parse arg hi . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 30 /*Not specified? Then use the default.*/ tell= hi>0; hi= abs(hi); hi= hi - 1 /*use absolute value of HI for limit. */ if tell>0 then say 'list of unique triplet strange primes whose sum is a prime.:' call genP /*build array of semaphores for primes.*/ finds= 0 /*# of triplet strange primes (so far).*/ say
do m=2+1 by 2 to hi; if \!.m then iterate /*just use the odd primes. */ do n=m+2 by 2 to hi; if \!.n then iterate /* " " " " " */ mn= m + n /*partial sum (deep loops).*/ do p=n+2 by 2 to hi; if \!.p then iterate /*just use the odd primes. */ sum= mn + p /*compute sum of 3 primes. */ if \!.sum then iterate /*Is the sum prime? No, then skip it.*/ finds= finds + 1 /*bump # of triplet "strange" primes.*/ if tell then say right(m, w+9) right(n, w) right(p, w) ' sum to:' right(sum, w+2) end /*p*/ end /*n*/ end /*m*/
say say 'Found ' commas(finds) " unique triplet strange primes < " commas(hi+1) ,
" which sum to a prime."
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0; w= length(hi) /*semaphores for primes; width of #'s.*/
@.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */ !.2=1; !.3=1; !.5=1; !.7=1; !.11=1 /* " " " " semaphores. */ #=5; s.#= @.# **2 /*number of primes so far; prime². */ /* [↓] generate more primes ≤ high.*/ do j=@.#+2 by 2 for hi*3%2 /*find odd primes from here on. */ parse var j -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/ if j// 3==0 then iterate /*" " " 3? */ if j// 7==0 then iterate /*" " " 7? */ /* [↑] the above five lines saves time*/ do k=5 while s.k<=j /* [↓] divide by the known odd primes.*/ if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */ end /*k*/ /* [↑] only process numbers ≤ √ J */ #= #+1; @.#= j; s.#= j*j; !.j= 1 /*bump # of Ps; assign next P; P²; P# */ end /*j*/; return</lang>
- output when using the default input:
list of unique triplet strange primes that sum to a prime: prime generation took 0.02 seconds. 3 5 11 sum to: 19 3 5 23 sum to: 31 3 5 29 sum to: 37 3 7 13 sum to: 23 3 7 19 sum to: 29 3 11 17 sum to: 31 3 11 23 sum to: 37 3 11 29 sum to: 43 3 17 23 sum to: 43 5 7 11 sum to: 23 5 7 17 sum to: 29 5 7 19 sum to: 31 5 7 29 sum to: 41 5 11 13 sum to: 29 5 13 19 sum to: 37 5 13 23 sum to: 41 5 13 29 sum to: 47 5 17 19 sum to: 41 5 19 23 sum to: 47 5 19 29 sum to: 53 7 11 13 sum to: 31 7 11 19 sum to: 37 7 11 23 sum to: 41 7 11 29 sum to: 47 7 13 17 sum to: 37 7 13 23 sum to: 43 7 17 19 sum to: 43 7 17 23 sum to: 47 7 17 29 sum to: 53 7 23 29 sum to: 59 11 13 17 sum to: 41 11 13 19 sum to: 43 11 13 23 sum to: 47 11 13 29 sum to: 53 11 17 19 sum to: 47 11 19 23 sum to: 53 11 19 29 sum to: 59 13 17 23 sum to: 53 13 17 29 sum to: 59 13 19 29 sum to: 61 17 19 23 sum to: 59 19 23 29 sum to: 71 Found 42 unique triplet strange primes < 30 which sum to a prime.
- output when using the input of: -1000
Found 241,580 unique triplet strange primes < 1,000 which sum to a prime.
Ring
<lang ring> load "stdlib.ring"
num = 0 limit = 30
see "working..." + nl see "the strange primes are:" + nl
for n = 1 to limit
for m = n+1 to limit for p = m+1 to limit sum = n+m+p if isprime(sum) and isprime(n) and isprime(m) and isprime(p) num = num + 1 see "" + num + ": " + n + "+" + m + "+" + p + " = " + sum + nl ok next next
next
see "done..." + nl </lang>
- Output:
working... the strange primes are: 1: 3+5+11 = 19 2: 3+5+23 = 31 3: 3+5+29 = 37 4: 3+7+13 = 23 5: 3+7+19 = 29 6: 3+11+17 = 31 7: 3+11+23 = 37 8: 3+11+29 = 43 9: 3+17+23 = 43 10: 5+7+11 = 23 11: 5+7+17 = 29 12: 5+7+19 = 31 13: 5+7+29 = 41 14: 5+11+13 = 29 15: 5+13+19 = 37 16: 5+13+23 = 41 17: 5+13+29 = 47 18: 5+17+19 = 41 19: 5+19+23 = 47 20: 5+19+29 = 53 21: 7+11+13 = 31 22: 7+11+19 = 37 23: 7+11+23 = 41 24: 7+11+29 = 47 25: 7+13+17 = 37 26: 7+13+23 = 43 27: 7+17+19 = 43 28: 7+17+23 = 47 29: 7+17+29 = 53 30: 7+23+29 = 59 31: 11+13+17 = 41 32: 11+13+19 = 43 33: 11+13+23 = 47 34: 11+13+29 = 53 35: 11+17+19 = 47 36: 11+19+23 = 53 37: 11+19+29 = 59 38: 13+17+23 = 53 39: 13+17+29 = 59 40: 13+19+29 = 61 41: 17+19+23 = 59 42: 19+23+29 = 71 done...
Rust
<lang rust>fn prime_sieve(limit: usize) -> Vec<bool> {
let mut sieve = vec![true; limit]; if limit > 0 { sieve[0] = false; } if limit > 1 { sieve[1] = false; } for i in (4..limit).step_by(2) { sieve[i] = false; } let mut p = 3; loop { let mut q = p * p; if q >= limit { break; } if sieve[p] { let inc = 2 * p; while q < limit { sieve[q] = false; q += inc; } } p += 2; } sieve
}
fn strange_unique_prime_triplets(limit: usize, verbose: bool) {
if limit < 6 { return; } let mut primes = Vec::new(); let sieve = prime_sieve(limit * 3); for p in (3..limit).step_by(2) { if sieve[p] { primes.push(p); } } if verbose { println!("Strange unique prime triplets < {}:", limit); } let mut count = 0; let n = primes.len(); for i in 0..n - 2 { for j in i + 1..n - 1 { for k in j + 1..n { let sum = primes[i] + primes[j] + primes[k]; if sieve[sum] { count += 1; if verbose { println!( "{:2} + {:2} + {:2} = {:2}", primes[i], primes[j], primes[k], sum ); } } } } } println!( "Count of strange unique prime triplets < {} is {}.", limit, count );
}
fn main() {
strange_unique_prime_triplets(30, true); strange_unique_prime_triplets(1000, false);
}</lang>
- Output:
Strange unique prime triplets < 30: 3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Count of strange unique prime triplets < 30 is 42. Count of strange unique prime triplets < 1000 is 241580.
Swift
<lang swift>import Foundation
func primeSieve(limit: Int) -> [Bool] {
guard limit > 0 else { return [] } var sieve = Array(repeating: true, count: limit) sieve[0] = false if limit > 1 { sieve[1] = false } if limit > 4 { for i in stride(from: 4, to: limit, by: 2) { sieve[i] = false } } var p = 3 while true { var q = p * p if q >= limit { break } if sieve[p] { let inc = 2 * p while q < limit { sieve[q] = false q += inc } } p += 2 } return sieve
}
func strangeUniquePrimeTriplets(limit: Int, verbose: Bool) {
guard limit > 5 else { return; } let sieve = primeSieve(limit: 3 * limit) var primes: [Int] = [] for p in stride(from: 3, to: limit, by: 2) { if sieve[p] { primes.append(p) } } let n = primes.count var count = 0 if verbose { print("Strange unique prime triplets < \(limit):") } for i in (0..<n - 2) { for j in (i + 1..<n - 1) { for k in (j + 1..<n) { let sum = primes[i] + primes[j] + primes[k] if sieve[sum] { count += 1 if verbose { print(String(format: "%2d + %2d + %2d = %2d", primes[i], primes[j], primes[k], sum)) } } } } } print("\nCount of strange unique prime triplets < \(limit) is \(count).")
}
strangeUniquePrimeTriplets(limit: 30, verbose: true) strangeUniquePrimeTriplets(limit: 1000, verbose: false)</lang>
- Output:
Strange unique prime triplets < 30: 3 + 5 + 11 = 19 3 + 5 + 23 = 31 3 + 5 + 29 = 37 3 + 7 + 13 = 23 3 + 7 + 19 = 29 3 + 11 + 17 = 31 3 + 11 + 23 = 37 3 + 11 + 29 = 43 3 + 17 + 23 = 43 5 + 7 + 11 = 23 5 + 7 + 17 = 29 5 + 7 + 19 = 31 5 + 7 + 29 = 41 5 + 11 + 13 = 29 5 + 13 + 19 = 37 5 + 13 + 23 = 41 5 + 13 + 29 = 47 5 + 17 + 19 = 41 5 + 19 + 23 = 47 5 + 19 + 29 = 53 7 + 11 + 13 = 31 7 + 11 + 19 = 37 7 + 11 + 23 = 41 7 + 11 + 29 = 47 7 + 13 + 17 = 37 7 + 13 + 23 = 43 7 + 17 + 19 = 43 7 + 17 + 23 = 47 7 + 17 + 29 = 53 7 + 23 + 29 = 59 11 + 13 + 17 = 41 11 + 13 + 19 = 43 11 + 13 + 23 = 47 11 + 13 + 29 = 53 11 + 17 + 19 = 47 11 + 19 + 23 = 53 11 + 19 + 29 = 59 13 + 17 + 23 = 53 13 + 17 + 29 = 59 13 + 19 + 29 = 61 17 + 19 + 23 = 59 19 + 23 + 29 = 71 Count of strange unique prime triplets < 30 is 42. Count of strange unique prime triplets < 1000 is 241580.
Visual Basic .NET
<lang vbnet>Imports DT = System.DateTime
Module Module1
Iterator Function Primes(lim As Integer) As IEnumerable(Of Integer) Dim flags(lim) As Boolean
Dim j = 2
Dim d = 3 Dim sq = 4 While sq <= lim If Not flags(j) Then Yield j For k = sq To lim Step j flags(k) = True Next End If
j += 1 d += 2 sq += d End While
While j <= lim If Not flags(j) Then Yield j End If j += 1 End While End Function
Sub Main() For Each lmt In {90, 300, 3000, 30000, 111000} Dim pr = Primes(lmt).Skip(1).ToList() Dim st = DT.Now Dim f = 0 Dim r As New List(Of String) Dim i = -1 Dim m = lmt \ 3 Dim h = m While i < 0 i = pr.IndexOf(h) h -= 1 End While Dim j = i - 1 Dim k = j - 1 For a = 0 To k Dim pra = pr(a) For b = a + 1 To j Dim prab = pra + pr(b) For c = b + 1 To i Dim d = prab + pr(c) If Not pr.Contains(d) Then Continue For End If f += 1 If lmt < 100 Then r.Add(String.Format("{3,5} = {0,2} + {1,2} + {2,2}", pra, pr(b), pr(c), d)) End If Next Next Next Dim s = "s.u.p.t.s under " r.Sort() If r.Count > 0 Then Console.WriteLine("{0}{1}:" + vbNewLine + "{2}", s, m, String.Join(vbNewLine, r)) End If If lmt > 100 Then Console.WriteLine("Count of {0}{1,6:n0}: {2,13:n0} {3} sec", s, m, f, (DT.Now - st).ToString().Substring(6)) End If Next End Sub
End Module</lang>
- Output:
Same as C#
Wren
Basic
<lang ecmascript>import "/math" for Int import "/trait" for Stepped import "/fmt" for Fmt
var strangePrimes = Fn.new { |n, countOnly|
var c = 0 var s for (i in Stepped.new(3..n-4, 2)) { if (Int.isPrime(i)) { for (j in Stepped.new(i+2..n-2, 2)) { if (Int.isPrime(j)) { for (k in Stepped.new(j+2..n, 2)) { if (Int.isPrime(k) && Int.isPrime(s = i + j + k)) { c = c + 1 if (!countOnly) Fmt.print("$2d: $2d + $2d + $2d = $2d", c, i, j, k, s) } } } } } } return c
}
System.print("Unique prime triples under 30 which sum to a prime:") strangePrimes.call(29, false) var c = strangePrimes.call(999, true) Fmt.print("\nThere are $,d unique prime triples under 1,000 which sum to a prime.", c)</lang>
- Output:
Unique prime triples under 30 which sum to a prime: 1: 3 + 5 + 11 = 19 2: 3 + 5 + 23 = 31 3: 3 + 5 + 29 = 37 4: 3 + 7 + 13 = 23 5: 3 + 7 + 19 = 29 6: 3 + 11 + 17 = 31 7: 3 + 11 + 23 = 37 8: 3 + 11 + 29 = 43 9: 3 + 17 + 23 = 43 10: 5 + 7 + 11 = 23 11: 5 + 7 + 17 = 29 12: 5 + 7 + 19 = 31 13: 5 + 7 + 29 = 41 14: 5 + 11 + 13 = 29 15: 5 + 13 + 19 = 37 16: 5 + 13 + 23 = 41 17: 5 + 13 + 29 = 47 18: 5 + 17 + 19 = 41 19: 5 + 19 + 23 = 47 20: 5 + 19 + 29 = 53 21: 7 + 11 + 13 = 31 22: 7 + 11 + 19 = 37 23: 7 + 11 + 23 = 41 24: 7 + 11 + 29 = 47 25: 7 + 13 + 17 = 37 26: 7 + 13 + 23 = 43 27: 7 + 17 + 19 = 43 28: 7 + 17 + 23 = 47 29: 7 + 17 + 29 = 53 30: 7 + 23 + 29 = 59 31: 11 + 13 + 17 = 41 32: 11 + 13 + 19 = 43 33: 11 + 13 + 23 = 47 34: 11 + 13 + 29 = 53 35: 11 + 17 + 19 = 47 36: 11 + 19 + 23 = 53 37: 11 + 19 + 29 = 59 38: 13 + 17 + 23 = 53 39: 13 + 17 + 29 = 59 40: 13 + 19 + 29 = 61 41: 17 + 19 + 23 = 59 42: 19 + 23 + 29 = 71 There are 241,580 unique prime triples under 1,000 which sum to a prime.
Faster
The following version uses a prime sieve and is about 17 times faster than the 'basic' version. <lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var max = 1000 var sieved = Int.primeSieve(3*max, false) // includes composites var p = Int.primeSieve(max, true) // primes only
var strangePrimes = Fn.new { |n, countOnly|
var c = 0 var m = 0 while (m < p.count && p[m] <= n) m = m + 1 var r var s for (i in 1...m-2) { for (j in i+1...m-1) { r = p[i] + p[j] for (k in j+1...m) { if (!sieved[s = r + p[k]]) { c = c + 1 if (!countOnly) Fmt.print("$2d: $2d + $2d + $2d = $2d", c, p[i], p[j], p[k], s) } } } } return c
}
System.print("Unique prime triples under 30 which sum to a prime:") strangePrimes.call(29, false) var c = strangePrimes.call(999, true) Fmt.print("\nThere are $,d unique prime triples under 1,000 which sum to a prime.", c)</lang>
- Output:
Same as 'basic' version.