CalmoSoft primes
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.
CalmoSoft primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Definition
- Task
Find and show here the longest sequence of CalmoSoft primes for p(n) < 100.
- Stretch
Show the same for p(n) < fifty million.
Tip: if it takes longer than two seconds, you're doing it wrong.
ALGOL 68
If there are multiple sequences with the maximum length, this will only show the first.
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
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]
C
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool isPrime(int n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
int 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 main() {
int primes[30] = {2}, sIndices[5], eIndices[5], sums[5];
int i, j, k, temp, sum, si, ei, pc = 1, longest = 0, count = 0;
for (i = 3; i < 100; i += 2) {
if (isPrime(i)) primes[pc++] = i;
}
for (i = 0; i < pc; ++i) {
for (j = pc-1; j >= i; --j) {
temp = j - i + 1;
if (temp < longest) break;
sum = 0;
for (k = i; k <= j; ++k) sum += primes[k];
if (isPrime(sum)) {
if (temp > longest) {
longest = temp;
count = 0;
}
sIndices[count] = i;
eIndices[count] = j;
sums[count] = sum;
++count;
break;
}
}
}
printf("The longest sequence(s) of CalmoSoft primes having a length of %d is/are:\n\n", longest);
for (i = 0; i < count; ++i) {
si = sIndices[i];
ei = eIndices[i];
sum = sums[i];
for (j = si; j <= ei; ++j) printf("%d + ", primes[j]);
printf("\b\b= %d which is prime\n", sum);
if (i < count - 1) printf("\n");
}
return 0;
}
- Output:
The longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime
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.
Go
package main
import (
"fmt"
"rcu"
"strconv"
)
func main() {
primes := rcu.Primes(100)
pc := len(primes)
longest := 0
var sIndices, eIndices []int
for i := 0; i < pc; i++ {
for j := pc - 1; j >= i; j-- {
temp := j - i + 1
if temp < longest {
break
}
sum := rcu.SumInts(primes[i : j+1])
if rcu.IsPrime(sum) {
if temp > longest {
longest = temp
sIndices = []int{i}
eIndices = []int{j}
} else {
sIndices = append(sIndices, i)
eIndices = append(eIndices, j)
}
break
}
}
}
fmt.Println("The longest sequence(s) of CalmoSoft primes having a length of", longest, "is/are:\n")
for i := 0; i < len(sIndices); i++ {
cp := primes[sIndices[i] : eIndices[i]+1]
sum := rcu.SumInts(cp)
cps := ""
for i := 0; i < len(cp); i++ {
cps += strconv.Itoa(cp[i])
if i < len(cp)-1 {
cps += " + "
}
}
cps += " = " + strconv.Itoa(sum) + " which is prime"
fmt.Println(cps)
if i < len(sIndices)-1 {
fmt.Println()
}
}
}
- Output:
The longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime
Phix
I'll give you guys a chance to figure out the stretch goal on your own...
- 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 +$_}";
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: 47 7 + 11 + 13 + 17 + 19 + 23...199 + 211 + 223 + 227 + 229, sum: 5,107 11 + 13 + 17 + 19 + 23 + 29...211 + 223 + 227 + 229 + 233, sum: 5,333 For primes up to five hundred: Longest sequence of consecutive primes yielding a prime sum: elements: 81 11 + 13 + 17 + 19 + 23 + 29...419 + 421 + 431 + 433 + 439, sum: 16,823 19 + 23 + 29 + 31 + 37 + 41...433 + 439 + 443 + 449 + 457, sum: 18,131 29 + 31 + 37 + 41 + 43 + 47...443 + 449 + 457 + 461 + 463, sum: 19,013 For primes up to one thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 162 2 + 3 + 5 + 7 + 11 + 13...929 + 937 + 941 + 947 + 953, sum: 70,241 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,757 3 + 5 + 7 + 11 + 13 + 17...24,919 + 24,923 + 24,943 + 24,953 + 24,967, sum: 32,305,799 For primes up to fifty thousand: Longest sequence of consecutive primes yielding a prime sum: elements: 5,125 13 + 17 + 19 + 23 + 29 + 31...49,927 + 49,937 + 49,939 + 49,943 + 49,957, sum: 120,863,297 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,037 5 + 7 + 11 + 13 + 17 + 19...249,871 + 249,881 + 249,911 + 249,923 + 249,943, sum: 2,621,781,299 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
import "./math" for Int, Nums
var primes = Int.primeSieve(100)
var pc = primes.count
var longest = 0
var sIndices = []
var eIndices = []
for (i in 0...pc) {
for (j in pc-1..i) {
var temp = j - i + 1
if (temp < longest) break
var sum = Nums.sum(primes[i..j])
if (Int.isPrime(sum)) {
if (temp > longest) {
longest = temp
sIndices = [i]
eIndices = [j]
} else {
sIndices.add(i)
eIndices.add(j)
}
break
}
}
}
System.print("The longest sequence(s) of CalmoSoft primes having a length of %(longest) is/are:\n")
for (i in 0...sIndices.count) {
var cp = primes[sIndices[i]..eIndices[i]]
var sum = Nums.sum(cp)
var cps = cp.join(" + ") + " = " + sum.toString + " which is prime"
System.print(cps)
if (i < sIndices.count - 1) System.print()
}
- Output:
The longest sequence(s) of CalmoSoft primes having a length of 21 is/are: 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 + 89 = 953 which is prime
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