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 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
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
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
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