CalmoSoft primes
- Definition
Let p(1), p(2), p(3), ... , p(n) be consecutive prime numbers. If the sum of any consecutive sub-sequence of these numbers is a prime number, then the numbers in such a sub-sequence are called CalmoSoft primes.
- Task
Find and show here the longest sequence of CalmoSoft primes for p(n) < 100.
- Stretch
Show a shortened version (first and last 6 primes) of the same for p(n) < fifty million.
Tip: if it takes longer than twenty seconds, you're doing it wrong.
ALGOL 68
If there are multiple sequences with the maximum length, this will only show the first.
Basic task
BEGIN # find the longest sequence of primes < 100 that sums to a prime #
# called Calmosoft primes #
[]INT prime = ( 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
); # primes up to 100 #
# returns TRUE if n is prime, FALSE otherwise - uses trial division #
PROC is prime = ( INT n )BOOL:
IF n < 3 THEN n = 2
ELIF n MOD 3 = 0 THEN n = 3
ELIF NOT ODD n THEN FALSE
ELSE
BOOL is a prime := TRUE;
FOR f FROM 5 BY 2 WHILE f * f <= n AND ( is a prime := n MOD f /= 0 )
DO SKIP OD;
is a prime
FI # is prime # ;
# calculate the sum of all the primes #
INT seq sum := 0; FOR i FROM LWB prime TO UPB prime DO seq sum +:= prime[ i ] OD;
# find the longest sequence that sums to a prime #
INT max start := -1;
INT max end := -1;
INT max len := -1;
INT max sum := -1;
FOR this start FROM LWB prime TO UPB prime - 1 DO
INT this end := UPB prime;
INT this len := ( this end + 1 ) - this start;
IF this len > max len THEN
INT this sum := seq sum;
BOOL this prime := FALSE;
WHILE this end >= this start
AND NOT ( this prime := is prime( this sum ) )
AND this len > max len
DO
this sum -:= prime[ this end ];
this end -:= 1;
this len -:= 1
OD;
IF this prime AND this len > max len THEN
max len := this len; # found a longer sequence #
max start := this start;
max end := this end;
max sum := this sum
FI
FI;
# the start prime won't be in the next sequence #
seq sum -:= prime[ this start ]
OD;
print( ( "Longest sequence of Calmosoft primes up to ", whole( prime[ UPB prime ], 0 )
, " has sum ", whole( max sum, 0 ), " and length ", whole( max len, 0 )
, newline
)
);
FOR i FROM max start TO max end DO print( ( " ", whole( prime[ i ], 0 ) ) ) OD
END
- Output:
Longest sequence of Calmosoft primes up to 97 has sum 953 and length 21 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89
Stretch
Basically the same algorithm as the Algol 68 Basic task sample.
Uses Algol 68G's LONG LONG INT for the Millar Rabin test.
To run this with Algol 68G version 2, you need -heap 512M
on the command line.
Took about 30 seconds with Algol 68G on the Windows 11 system I'm using, 40-45 seconds on TIO.RUN.
Note Algol 68G is fully interpreted on Windows.
BEGIN # find the longest sequence of primes < 50 000 000 that sums to a prime#
# called Calmosoft primes #
PR read "primes.incl.a68" PR
INT max prime = 50 000 000;
[ 0 : max prime ]BOOL prime;
prime[ 0 ] := 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( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
# count and sum the primes to max prime #
INT p count := 0;
LONG INT p sum := 0;
FOR i TO max prime DO IF prime[ i ] THEN p count +:= 1; p sum +:= i FI OD;
# construct a list of the primes up to max prime #
[ 1 : p count ]INT prime list;
INT p pos := 0;
FOR i WHILE p pos < UPB prime list DO
IF prime[ i ] THEN prime list[ p pos +:= 1 ] := i FI
OD;
LONG INT seq sum := p sum;
# find the longest sequence that sums to a prime #
INT max start := -1;
INT max end := -1;
INT max len := -1;
FOR this start FROM LWB prime list TO UPB prime list - 1 DO
INT this end := UPB prime list;
INT this len := ( this end + 1 ) - this start;
IF this len > max len THEN
LONG INT this sum := seq sum;
BOOL this prime := FALSE;
WHILE IF this end < this start OR this len < max len
THEN FALSE
ELSE NOT ( this prime := is probably prime( this sum ) )
FI
DO
this sum -:= prime list[ this end ];
this end -:= 1;
this len -:= 1
OD;
IF this prime AND this len > max len THEN
max len := this len; # found a longer sequence #
max start := this start;
max end := this end
FI
FI;
# the start prime won't be in the next sequence #
seq sum -:= prime list[ this start ]
OD;
LONG INT max sum := 0; FOR i FROM max start TO max end DO max sum +:= prime list[ i ] OD;
print( ( "Longest sequence of Calmosoft primes up to ", whole( prime list[ UPB prime list ], 0 )
, " has sum ", whole( max sum, 0 ), " and length ", whole( max len, 0 )
, newline
)
);
IF max len < 12 THEN
FOR i FROM max start TO max end DO print( ( " ", whole( prime list[ i ], 0 ) ) ) OD
ELSE
FOR i FROM max start TO max start + 6 DO print( ( " ", whole( prime list[ i ], 0 ) ) ) OD;
print( ( " ... " ) );
FOR i FROM max end - 6 TO max end DO print( ( " ", whole( prime list[ i ], 0 ) ) ) OD
FI
END
- Output:
Longest sequence of Calmosoft primes up to 49999991 has sum 72618848632313 and length 3001117 7 11 13 17 19 23 29 ... 49999693 49999699 49999711 49999739 49999751 49999753 49999757
Arturo
subseqs: function [a :block][
;; description: « returns every contiguous subsequence in a block
;; returns: :block
flatten.once map 0..dec size a'x ->
map x..dec size a'y -> a\[x..y]
]
calmo: 1..100 | select => prime?
| subseqs
| select => [prime? sum &]
| maximum => size
print ~{
The longest sequence of calmo primes < 100
has sum |sum calmo| (prime) and length |size calmo|:
|calmo|
}
- Output:
The longest sequence of calmo primes < 100 has sum 953 (prime) and length 21: [7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89]
BASIC
FreeBASIC
#include "isprime.bas"
Dim As Integer Primes(100), PrimeSums(100)
Dim As Integer i, n, Size, Head, Tail, Longest, Sum, SaveHead, SaveTail
i = 0 'make table of primes
For n = 2 To 100-1
If isPrime(n) Then Primes(i) = n : i += 1
Next
Size = i 'make table of sums
PrimeSums(0) = Primes(0)
For i = 1 To Size-1
PrimeSums(i) = PrimeSums(i-1) + Primes(i)
Next
Longest = 0 'find longest sequence
For Head = Size-1 To 0 Step -1
Sum = PrimeSums(Head)
For Tail = 0 To Head
If Head-Tail > Longest Then
If IsPrime(Sum) Then
Longest = Head-Tail
SaveHead = Head
SaveTail = Tail
End If
Sum -= Primes(Tail)
End If
Next
Next
Print "[";
For i = SaveTail To SaveHead
Print Primes(i); ",";
Next
Print Chr$(8); Chr$(8); " ]"
Sum = 0
For i = SaveTail To SaveHead
Sum += Primes(i)
Print Primes(i);
If i <> SaveHead Then Print " +";
Next
Print Chr$(8); " ="; Sum; " is prime number"
Print "The longest sequence of CalmoSoft primes ="; Longest+1
Sleep
- Output:
[ 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 8 ] 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 8 = 953 is prime number The longest sequence of CalmoSoft primes = 21
Yabasic
//import isprime
dim Primes(100)
dim PrimeSums(100)
i = 1 //make table of primes
for n = 2 to 100-1
if isPrime(n) then Primes(i) = n : i = i + 1 : fi
next
tam = i //make table of sums
PrimeSums(0) = Primes(0)
for i = 1 to tam-1
PrimeSums(i) = PrimeSums(i-1) + Primes(i)
next
Longest = 0 //find longest sequence
for Head = tam-1 to 0 step -1
Sum = PrimeSums(Head)
for Tail = 0 to Head
if Head-Tail > Longest then
if isPrime(Sum) then
Longest = Head-Tail
SaveHead = Head
SaveTail = Tail
end if
Sum = Sum - Primes(Tail)
end if
next
next
print "[ ";
for i = SaveTail to SaveHead
print Primes(i), ", ";
next
print chr$(8), chr$(8), " ]"
Sum = 0
for i = SaveTail to SaveHead
Sum = Sum + Primes(i)
print Primes(i);
if i <> SaveHead print " + ";
next
print chr$(8), " = ", Sum, " is prime number"
print "The longest sequence of CalmoSoft primes = ", Longest+1
end
- Output:
Same as FreeBASIC entry.
C
Run time is 310 milliseconds (GCC -O1) which is slightly slower than Go.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
#include <locale.h>
#define MAX 50000000
typedef uint64_t u64;
bool isPrime(u64 n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
u64 d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
int *primeSieve(int limit, int *length) {
int i, p, *primes;
int j, pc = 0;
limit++;
// True denotes composite, false denotes prime.
bool *c = calloc(limit, sizeof(bool)); // all false by default
c[0] = true;
c[1] = true;
for (i = 4; i < limit; i += 2) c[i] = true;
p = 3; // Start from 3.
while (true) {
u64 p2 = p * p;
if (p2 >= limit) break;
for (i = p2; i < limit; i += 2 * p) c[i] = true;
while (true) {
p += 2;
if (!c[p]) break;
}
}
for (i = 0; i < limit; ++i) {
if (!c[i]) ++pc;
}
primes = (int *)malloc(pc * sizeof(u64));
for (i = 0, j = 0; i < limit; ++i) {
if (!c[i]) primes[j++] = i;
}
free(c);
*length = pc;
return primes;
}
int calmoPrimes(int limit, int *primes, int len, int *sIndices, int *eIndices, u64 *sums, int *ilen) {
int i, j, temp, pc = len, longest = 0, ic = 0;
u64 sum = 0, sum2;
if (limit < MAX) {
for (i = 0; i < len; ++i) {
if (primes[i] > limit) {
pc = i;
break;
}
}
}
for (i = 0; i < pc; ++i) sum += primes[i];
for (i = 0; i < pc; ++i) {
if (pc - i < longest) break;
if (i > 0) sum -= primes[i-1];
sum2 = sum;
for (j = pc - 1; j >= i; --j) {
temp = j - i + 1;
if (temp < longest) break;
if (j < pc - 1) sum2 -= primes[j+1];
if (isPrime(sum2)) {
if (temp > longest) {
longest = temp;
ic = 0;
}
sIndices[ic] = i;
eIndices[ic] = j;
sums[ic] = sum2;
++ic;
break;
}
}
}
*ilen = ic;
return longest;
}
int main() {
int i, j, k, len, ilen, limit, longest;
int *primes = primeSieve(MAX, &len);
int limits[6] = {100, 250, 5000, 10000, 500000, 50000000};
setlocale(LC_NUMERIC, "");
int sIndices[5];
int eIndices[5];
u64 sums[5];
for (i = 0; i < 6; ++i) {
limit = limits[i];
longest = calmoPrimes(limit, primes, len, sIndices, eIndices, sums, &ilen);
printf("For primes up to %'d the longest sequence(s) of CalmoSoft primes\n", limit);
printf("having a length of %'d is/are:\n\n", longest);
for (j = 0; j < ilen; ++j) {
char cps[130] = "";
char buf[20];
int bytes = 0, totalBytes = 0;
for (k = sIndices[j]; k <= sIndices[j]+5; ++k) {
bytes = sprintf(buf, "%d + ", primes[k]);
strcpy(cps + totalBytes, buf);
totalBytes += bytes;
}
strcpy(cps + totalBytes, ".. + ");
totalBytes += 5;
for (k = eIndices[j]-5; k <= eIndices[j]; ++k) {
bytes = sprintf(buf, "%d + ", primes[k]);
strcpy(cps + totalBytes, buf);
totalBytes += bytes;
}
cps[totalBytes-3] = '\0';
printf("%s = %'ld\n", cps, sums[j]);
}
printf("\n");
}
free(primes);
return 0;
}
- Output:
For primes up to 100 the longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 67 + 71 + 73 + 79 + 83 + 89 = 953 For primes up to 250 the longest sequence(s) of CalmoSoft primes having a length of 49 is/are: 11 + 13 + 17 + 19 + 23 + 29 + .. + 223 + 227 + 229 + 233 + 239 + 241 = 5,813 For primes up to 5,000 the longest sequence(s) of CalmoSoft primes having a length of 665 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 4957 + 4967 + 4969 + 4973 + 4987 + 4993 = 1,543,127 For primes up to 10,000 the longest sequence(s) of CalmoSoft primes having a length of 1,223 is/are: 3 + 5 + 7 + 11 + 13 + 17 + .. + 9883 + 9887 + 9901 + 9907 + 9923 + 9929 = 5,686,633 7 + 11 + 13 + 17 + 19 + 23 + .. + 9901 + 9907 + 9923 + 9929 + 9931 + 9941 = 5,706,497 For primes up to 500,000 the longest sequence(s) of CalmoSoft primes having a length of 41,530 is/are: 2 + 3 + 5 + 7 + 11 + 13 + .. + 499787 + 499801 + 499819 + 499853 + 499879 + 499883 = 9,910,236,647 For primes up to 50,000,000 the longest sequence(s) of CalmoSoft primes having a length of 3,001,117 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72,618,848,632,313
Go
package main
import (
"fmt"
"rcu"
"time"
)
var start = time.Now()
const max = 50_000_000
var primes = rcu.Primes(max)
func calmoPrimes(limit int) (int, []int, []int, []int) {
var pc, sum int
if limit < max {
for i := 0; i < len(primes); i++ {
if primes[i] > limit {
pc = i
break
}
}
} else {
pc = len(primes)
}
for i := 0; i < pc; i++ {
sum += primes[i]
}
longest := 0
var sIndices, eIndices, sums []int
for i := 0; i < pc; i++ {
if pc-i < longest {
break
}
if i > 0 {
sum -= primes[i-1]
}
sum2 := sum
for j := pc - 1; j >= i; j-- {
temp := j - i + 1
if temp < longest {
break
}
if j < pc-1 {
sum2 -= primes[j+1]
}
if rcu.IsPrime(sum2) {
if temp > longest {
longest = temp
sIndices = []int{i}
eIndices = []int{j}
sums = []int{sum2}
} else {
sIndices = append(sIndices, i)
eIndices = append(eIndices, j)
sums = append(sums, sum2)
}
break
}
}
}
return longest, sIndices, eIndices, sums
}
func main() {
for _, limit := range []int{100, 250, 5000, 10000, 500000, 50000000} {
longest, sIndices, eIndices, sums := calmoPrimes(limit)
fmt.Println("For primes up to", rcu.Commatize(limit), "the longest sequence(s) of CalmoSoft primes")
fmt.Println("having a length of", rcu.Commatize(longest), "is/are:\n")
for i := 0; i < len(sIndices); i++ {
cp1 := primes[sIndices[i] : sIndices[i]+6]
cp2 := primes[eIndices[i]-5 : eIndices[i]+1]
cps := ""
for _, p := range cp1 {
cps += fmt.Sprintf("%d + ", p)
}
cps += ".. + "
for _, p := range cp2 {
cps += fmt.Sprintf("%d + ", p)
}
fmt.Printf("%s = %s\n", cps[:len(cps)-3], rcu.Commatize(sums[i]))
}
fmt.Println()
}
fmt.Printf("Took %d ms\n", time.Since(start).Milliseconds())
}
- Output:
For primes up to 100 the longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 67 + 71 + 73 + 79 + 83 + 89 = 953 For primes up to 250 the longest sequence(s) of CalmoSoft primes having a length of 49 is/are: 11 + 13 + 17 + 19 + 23 + 29 + .. + 223 + 227 + 229 + 233 + 239 + 241 = 5,813 For primes up to 5,000 the longest sequence(s) of CalmoSoft primes having a length of 665 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 4957 + 4967 + 4969 + 4973 + 4987 + 4993 = 1,543,127 For primes up to 10,000 the longest sequence(s) of CalmoSoft primes having a length of 1,223 is/are: 3 + 5 + 7 + 11 + 13 + 17 + .. + 9883 + 9887 + 9901 + 9907 + 9923 + 9929 = 5,686,633 7 + 11 + 13 + 17 + 19 + 23 + .. + 9901 + 9907 + 9923 + 9929 + 9931 + 9941 = 5,706,497 For primes up to 500,000 the longest sequence(s) of CalmoSoft primes having a length of 41,530 is/are: 2 + 3 + 5 + 7 + 11 + 13 + .. + 499787 + 499801 + 499819 + 499853 + 499879 + 499883 = 9,910,236,647 For primes up to 50,000,000 the longest sequence(s) of CalmoSoft primes having a length of 3,001,117 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72,618,848,632,313 Took 270 ms
Julia
The stretch goal currently asks for the sequence. It's not possible to show the < 50 million sequence in the page, but the totals can be shown.
using Primes
function calmo_prime_sequence(N = 100, showsequence = true)
pri = primes(N)
for window_size in lastindex(pri):-1:2
for i in firstindex(pri):lastindex(pri)-window_size
if isprime(sum(pri[i:i+window_size]))
println("Longest Calmo prime seq (length ", window_size + 1,
") of primes less than $N totals ", sum(pri[i:i+window_size]))
showsequence && println("The sequence is: ", pri[i:i+window_size])
return
end
end
end
end
calmo_prime_sequence()
calmo_prime_sequence(50_000_000, false)
- Output:
Longest Calmo prime seq (length 21) of primes less than 100 totals 953 The sequence is: [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89] Longest Calmo prime seq (length 3001117) of primes less than 50000000 totals 72618848632313
Phix
for lim in {100,5e3,1e4,5e5,5e7} do sequence primes = get_primes_le(lim), starts = {} integer l = length(primes), longest = 1, start = 1 atom t = sum(primes) while start<=l-longest+1 do atom s = t for finish=l to start+longest-1 by -1 do if is_prime(s) then integer len = finish-start+1 if len>longest then longest = len starts = {start} else assert(len==longest) starts &= start end if exit end if s -= primes[finish] end for t -= primes[start] start += 1 end while printf(1,"For primes up to %s:\n",ordinal(lim,true)) string {s,ns} = iff(length(starts)=1?{"","s"}:{"s",""}) printf(1,"The following sequence%s of %,d consecutive primes yield%s a prime sum:\n",{s,longest,ns}) for start in starts do sequence p = primes[start..start+longest-1] string f6 = join(p[1..6]," + ",fmt:="%d"), l6 = join(p[-6..-1]," + ",fmt:="%d") printf(1," %s +..+ %s = %,d\n",{f6,l6,sum(p)}) end for printf(1,"\n") end for
- Output:
For primes up to one hundred: The following sequence of 21 consecutive primes yields a prime sum: 7 + 11 + 13 + 17 + 19 + 23 +..+ 67 + 71 + 73 + 79 + 83 + 89 = 953 For primes up to five thousand: The following sequence of 665 consecutive primes yields a prime sum: 7 + 11 + 13 + 17 + 19 + 23 +..+ 4957 + 4967 + 4969 + 4973 + 4987 + 4993 = 1,543,127 For primes up to ten thousand: The following sequences of 1,223 consecutive primes yield a prime sum: 3 + 5 + 7 + 11 + 13 + 17 +..+ 9883 + 9887 + 9901 + 9907 + 9923 + 9929 = 5,686,633 7 + 11 + 13 + 17 + 19 + 23 +..+ 9901 + 9907 + 9923 + 9929 + 9931 + 9941 = 5,706,497 For primes up to five hundred thousand: The following sequence of 41,530 consecutive primes yields a prime sum: 2 + 3 + 5 + 7 + 11 + 13 +..+ 499787 + 499801 + 499819 + 499853 + 499879 + 499883 = 9,910,236,647 For primes up to fifty million: The following sequence of 3,001,117 consecutive primes yields a prime sum: 7 + 11 + 13 + 17 + 19 + 23 +..+ 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72,618,848,632,313
Python
from sympy import isprime, primerange
pri = list(primerange(1, 100))
lcal = sorted([pri[i:j] for j in range(len(pri), 0, -1)
for i in range(len(pri)) if j > i and isprime(sum(pri[i:j]))], key=len)[-1]
print(f'Longest Calmo prime seq (length {len(lcal)}) of primes less than 100 is:\n{lcal}')
- Output:
Longest Calmo prime seq (length 21) of primes less than 100 is: [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89]
Raku
Longest sliding window prime sums
use Lingua::EN::Numbers;
sub sliding-window(@list, $window) { (^(+@list - $window)).map: { @list[$_ .. $_+$window] } }
for flat (1e2, 1e3, 1e4, 1e5).map: { (1, 2.5, 5) »×» $_ } -> $upto {
my @primes = (^$upto).grep: &is-prime;
for +@primes ... 1 {
my @sums = @primes.&sliding-window($_).grep: { .sum.is-prime }
next unless @sums;
say "\nFor primes up to {$upto.Int.&cardinal}:\nLongest sequence of consecutive primes yielding a prime sum: elements: {comma 1+$_}";
for @sums { say " {join '...', .[0..5, *-5..*]».&comma».join(' + ')}, sum: {.sum.&comma}" }
last
}
}
- Output:
For primes up to one hundred: Longest sequence of consecutive primes yielding a prime sum: elements: 21 7 + 11 + 13 + 17 + 19 + 23...71 + 73 + 79 + 83 + 89, sum: 953 For primes up to two hundred fifty: Longest sequence of consecutive primes yielding a prime sum: elements: 49 11 + 13 + 17 + 19 + 23 + 29...227 + 229 + 233 + 239 + 241, sum: 5,813 For primes up to five hundred: Longest sequence of consecutive primes yielding a prime sum: elements: 85 31 + 37 + 41 + 43 + 47 + 53...467 + 479 + 487 + 491 + 499, sum: 21,407 For primes up to one thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 163 13 + 17 + 19 + 23 + 29 + 31...971 + 977 + 983 + 991 + 997, sum: 76,099 For primes up to two thousand, five hundred: Longest sequence of consecutive primes yielding a prime sum: elements: 359 7 + 11 + 13 + 17 + 19 + 23...2,411 + 2,417 + 2,423 + 2,437 + 2,441, sum: 408,479 For primes up to five thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 665 7 + 11 + 13 + 17 + 19 + 23...4,967 + 4,969 + 4,973 + 4,987 + 4,993, sum: 1,543,127 For primes up to ten thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 1,223 3 + 5 + 7 + 11 + 13 + 17...9,887 + 9,901 + 9,907 + 9,923 + 9,929, sum: 5,686,633 7 + 11 + 13 + 17 + 19 + 23...9,907 + 9,923 + 9,929 + 9,931 + 9,941, sum: 5,706,497 For primes up to twenty-five thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 2,759 7 + 11 + 13 + 17 + 19 + 23...24,967 + 24,971 + 24,977 + 24,979 + 24,989, sum: 32,405,707 For primes up to fifty thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 5,131 5 + 7 + 11 + 13 + 17 + 19...49,943 + 49,957 + 49,991 + 49,993 + 49,999, sum: 121,013,303 For primes up to one hundred thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 9,590 2 + 3 + 5 + 7 + 11 + 13...99,907 + 99,923 + 99,929 + 99,961 + 99,971, sum: 454,196,557 For primes up to two hundred fifty thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 22,041 7 + 11 + 13 + 17 + 19 + 23...249,947 + 249,967 + 249,971 + 249,973 + 249,989, sum: 2,623,031,141 For primes up to five hundred thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 41,530 2 + 3 + 5 + 7 + 11 + 13...499,801 + 499,819 + 499,853 + 499,879 + 499,883, sum: 9,910,236,647
Ring
see "works..." + nl
limit = 100
Primes = []
OldPrimes = []
NewPrimes = []
for p = 1 to limit
if isPrime(p)
add(Primes,p)
ok
next
lenPrimes = len(Primes)
for n = 1 to lenPrimes
num = 0
OldPrimes = []
for m = n to lenPrimes
num = num + Primes[m]
add(OldPrimes,Primes[m])
if isPrime(num)
if len(OldPrimes) > len(NewPrimes)
NewPrimes = OldPrimes
ok
ok
next
next
str = "["
for n = 1 to len(NewPrimes)
if n = len(NewPrimes)
str = str + newPrimes[n] + "]"
exit
ok
str = str + newPrimes[n] + ", "
next
sum = 0
strsum = ""
for n = 1 to len(NewPrimes)
sum = sum + newPrimes[n]
if n = len(NewPrimes)
strsum = strsum + newPrimes[n] + " = " + sum + " is prime number"
exit
ok
strsum = strsum + newPrimes[n] + " + "
next
see str + nl
see strsum + nl
see "The longest sequence of CalmoSoft primes = " + len(NewPrimes) + nl
see "done.." + nl
func isPrime num
if (num <= 1) return 0 ok
if (num % 2 = 0 and num != 2) return 0 ok
for i = 3 to floor(num / 2) -1 step 2
if (num % i = 0) return 0 ok
next
return 1
- Output:
works... [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89] 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 is prime number The longest sequence of CalmoSoft primes = 21 done..
Wren
This runs in about 4.3 seconds (cf. Julia 1.3 seconds) on my Core i7 machine. However, 2.6 seconds of that is needed to sieve for primes up to 50 million.
import "./math" for Int, Nums
import "./fmt"for Fmt
var max = 50000000
var primes = Int.primeSieve(max)
var calmoPrimes = Fn.new { |limit|
var pc = (limit < max) ? primes.count { |p| p <= limit } : primes.count
var sum = (limit < max) ? Nums.sum(primes.take(pc)) : Nums.sum(primes)
var longest = 0
var sIndices = []
var eIndices = []
var sums = []
for (i in 0...pc) {
if (pc - i < longest) break
sum = (i > 0) ? sum - primes[i-1] : sum
var sum2 = sum
for (j in pc-1..i) {
var temp = j - i + 1
if (temp < longest) break
sum2 = (j < pc -1) ? sum2 - primes[j+1] : sum2
if (Int.isPrime(sum2)) {
if (temp > longest) {
longest = temp
sIndices = [i]
eIndices = [j]
sums = [sum2]
} else {
sIndices.add(i)
eIndices.add(j)
sums.add(sum2)
}
break
}
}
}
return [longest, sIndices, eIndices, sums]
}
for (limit in [100, 250, 5000, 10000, 500000, 50000000]) {
var res = calmoPrimes.call(limit)
var longest = res[0]
var sIndices = res[1]
var eIndices = res[2]
var sums = res[3]
Fmt.print("For primes up to $,d the longest sequence(s) of CalmoSoft primes", limit)
Fmt.print("having a length of $,d is/are:\n", longest)
for (i in 0...sIndices.count) {
var cp1 = primes[sIndices[i]..sIndices[i]+5]
var cp2 = primes[eIndices[i]-5..eIndices[i]]
var cps = cp1.join(" + ") + " + .. + " + cp2.join(" + ")
Fmt.print("$s = $,d", cps, sums[i])
}
System.print()
}
- Output:
For primes up to 100 the longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 67 + 71 + 73 + 79 + 83 + 89 = 953 For primes up to 250 the longest sequence(s) of CalmoSoft primes having a length of 49 is/are: 11 + 13 + 17 + 19 + 23 + 29 + .. + 223 + 227 + 229 + 233 + 239 + 241 = 5,813 For primes up to 5,000 the longest sequence(s) of CalmoSoft primes having a length of 665 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 4957 + 4967 + 4969 + 4973 + 4987 + 4993 = 1,543,127 For primes up to 10,000 the longest sequence(s) of CalmoSoft primes having a length of 1,223 is/are: 3 + 5 + 7 + 11 + 13 + 17 + .. + 9883 + 9887 + 9901 + 9907 + 9923 + 9929 = 5,686,633 7 + 11 + 13 + 17 + 19 + 23 + .. + 9901 + 9907 + 9923 + 9929 + 9931 + 9941 = 5,706,497 For primes up to 500,000 the longest sequence(s) of CalmoSoft primes having a length of 41,530 is/are: 2 + 3 + 5 + 7 + 11 + 13 + .. + 499787 + 499801 + 499819 + 499853 + 499879 + 499883 = 9,910,236,647 For primes up to 50,000,000 the longest sequence(s) of CalmoSoft primes having a length of 3,001,117 is/are: 7 + 11 + 13 + 17 + 19 + 23 + .. + 49999699 + 49999711 + 49999739 + 49999751 + 49999753 + 49999757 = 72,618,848,632,313
XPL0
include xpllib; \for IsPrime and Print
int Primes(100), PrimeSums(100);
int I, N, Size, Head, Tail, Longest, Sum, SaveHead, SaveTail;
[I:= 0; \make table of primes
for N:= 2 to 100-1 do
if IsPrime(N) then
[Primes(I):= N; I:= I+1];
Size:= I; \make table of sums
PrimeSums(0):= Primes(0);
for I:= 1 to Size-1 do
PrimeSums(I):= PrimeSums(I-1) + Primes(I);
Longest:= 0; \find longest sequence
for Head:= Size-1 downto 0 do
[Sum:= PrimeSums(Head);
for Tail:= 0 to Head do
[if Head-Tail > Longest then
[if IsPrime(Sum) then
[Longest:= Head-Tail;
SaveHead:= Head;
SaveTail:= Tail;
];
];
Sum:= Sum - Primes(Tail);
];
];
Print( "The longest sequence of CalmoSoft primes < 100 is %d:\n", Longest+1);
Sum:= 0;
for I:= SaveTail to SaveHead do
[Sum:= Sum + Primes(I);
IntOut(0, Primes(I));
if I # SaveHead then ChOut(0, ^+);
];
Print(" = %d\n", Sum);
]
- Output:
The longest sequence of CalmoSoft primes < 100 is 21: 7+11+13+17+19+23+29+31+37+41+43+47+53+59+61+67+71+73+79+83+89 = 953