No prime sums
No prime sums 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.
Suppose you have a sequence of integers, starting with 1. Each integer that gets added to the sequence must be lexicographically later, and must have the property that when added, there is no subsequence that will sum to a prime number.
- Note
for the purposes of this task, "lexicographically later" means "greater than" - see the Mathematical discussion of ordering link below.
- E.G.
Sequence starts with: (1) testing integers... 1 - is not lexicographically later 2 - 2 + 1 is 3, a prime 3 - is prime ( a sum can be of a single element ) 4 - 4 + 1 is 5, a prime 5 - is prime 6 - 6 + 1 is 7, a prime 7 - is prime 8 - 8 is later than 1, is not prime and 8 + 1 is not prime, so 8 is added to the sequence and so on...
There are variations of this sequence that have some further constraints.
- Same premise except that each added integer must also be odd.
- Same premise except that each added integer must also be even.
- Task
Find the first eight elements of each variation, starting with 1, where each added element is:
- Lexicographically later, and yields no non-prime subsequence sum.
- Lexicographically later, yields no non-prime subsequence sum, and is odd.
- Lexicographically later, yields no non-prime subsequence sum, and is even.
- Stretch
The numbers grow quite large very quickly. Find the first ten elements of each sequence, with an approximate elapsed time.
- See also
- OEIS A052349 - Lexicographically earliest sequence of distinct positive integers such that no subsequence sums to a prime
- OEIS A128687 - Smallest odd nonprime such that every subset sums to a nonprime
- OEIS A128688 - a(1)=1. For n>1, a(n) is the smallest even number such that every subset sums to a nonprime
- Mathematical discussion of Ordering
Ballerina
The runtime is around 35 seconds on my Core-i7 8565U machine.
import ballerina/io;
function getPrimes(int n) returns int[] {
if n < 2 { return []; }
if n == 2 { return [2]; }
int k = (n - 3) / 2 + 1;
boolean[] marked = [];
marked.setLength(k);
foreach int i in 0..<k { marked[i] = true; }
float f = (<float>n).sqrt().floor();
int lim = (<int>f - 3) / 2 + 1;
foreach int i in 0..<lim {
if marked[i] {
int p = 2 * i + 3;
int s = (p * p - 3) / 2;
int j = s;
while j < k {
marked[j] = false;
j += p;
}
}
}
int[] primes = [2];
foreach int i in 0..<k {
if marked[i] { primes.push(2 * i + 3); }
}
return primes;
}
function areComposite(int n) returns boolean[] {
int[] primes = getPrimes(n);
boolean[] c = [];
c.setLength(n + 1);
foreach int i in 0...n { c[i] = true; }
foreach int p in primes { c[p] = false; }
return c;
}
const BOTH = 0;
const ODD = 1;
const EVEN = 2;
string[] kinds = ["", "odd ", "even "];
boolean[] c = areComposite(<int>1e8);
function noPrimeSums(int begin, int lim, int kind) returns int[] {
int step = kind == BOTH ? 1 : 2;
int k = kind == EVEN ? 2 : 3;
int[] sums = [0, begin];
int[] res = [begin];
while res.length() < lim {
while sums.some(s => !c[k + s]) { k += step; }
if kind == BOTH ||
kind == ODD && k % 2 == 1 ||
kind == EVEN && k % 2 == 0 {
int[] extra = sums.map(s => k + s);
foreach int e in extra {
if sums.indexOf(e) == () { sums.push(e); }
}
res.push(k);
}
k += step;
}
return res;
}
public function main() {
final int lim = 10;
io:println("Sequence, starting with 1, then:");
foreach int k in [BOTH, ODD, EVEN] {
io:println("\nlexicographically earliest ", kinds[k], "integer such that no subsequence sums to a prime:");
io:println(re `,`.replaceAll(noPrimeSums(1, lim, k).toString(), ", "));
}
}
- Output:
Sequence, starting with 1, then: lexicographically earliest integer such that no subsequence sums to a prime: [1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660] lexicographically earliest odd integer such that no subsequence sums to a prime: [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795, 78060135] lexicographically earliest even integer such that no subsequence sums to a prime: [1, 8, 24, 86, 90, 780, 5940, 52350, 278460, 40768260]
C++
The runtime is approximately 2 minutes 40 seconds on my modest laptop.
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
std::vector<uint32_t> primes;
template <typename T>
void print_vector(const std::vector<T>& vec) {
std::cout << "[";
for ( uint32_t i = 0; i < vec.size() - 1; ++i ) {
std::cout << vec[i] << ", ";
}
std::cout << vec.back() << "]" << std::endl << std::endl;
}
void list_prime_numbers(const uint32_t& limit) {
primes.emplace_back(2);
const uint32_t half_limit = ( limit + 1 ) / 2;
std::vector<bool> composite(half_limit, false);
for ( uint32_t i = 1, p = 3; i < half_limit; p += 2, ++i ) {
if ( ! composite[i] ) {
primes.emplace_back(p);
for ( uint32_t a = i + p; a < half_limit; a += p ) {
composite[a] = true;
}
}
}
}
enum Parity { BOTH, EVEN, ODD };
std::vector<uint32_t> no_prime_sums(const uint32_t& start, const uint32_t& limit, const Parity& parity) {
const uint32_t step = ( parity == Parity::BOTH ) ? 1 : 2;
uint32_t k = ( parity == Parity::EVEN ) ? 2 : 3;
std::vector<uint32_t> sums = { 0, start };
std::vector<uint32_t> result = { start };
while ( result.size() < limit ) {
do {
bool valid = true;
for ( const uint32_t& sum : sums ) {
if ( std::binary_search(primes.begin(), primes.end(), sum + k) ) {
valid = false;
break; // for-next loop
}
}
if ( valid ) {
break; // do-while loop
}
k += step;
} while ( true );
if ( ( parity == Parity::EVEN && k % 2 == 0 ) ||
( parity == Parity::ODD && k % 2 == 1 ) ||
parity == Parity::BOTH ) {
const uint32_t size = sums.size();
for ( uint32_t i = 0; i < size; ++i ) {
sums.emplace_back(sums[i] + k);
}
result.emplace_back(k);
}
k += step;
}
return result;
}
int main() {
list_prime_numbers(100'000'000);
constexpr uint32_t limit = 10;
const std::vector<std::string> text = { "", "odd ", "even " };
std::cout << "Sequence, starting with 1, then:" << std::endl << std::endl;
for ( const Parity& parity : { Parity::BOTH, Parity::EVEN, Parity::ODD } ) {
std::cout << "lexicographically earliest " << text[parity]
<< "integer such that no subsequence sums to a prime: " << std::endl;
print_vector(no_prime_sums(1, limit, parity));
}
}
- Output:
Sequence, starting with 1, then: lexicographically earliest integer such that no subsequence sums to a prime: [1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660] lexicographically earliest odd integer such that no subsequence sums to a prime: [1, 8, 24, 86, 90, 780, 5940, 52350, 278460, 40768260] lexicographically earliest even integer such that no subsequence sums to a prime: [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795, 78060135]
EasyLang
kind$[] = [ "both" "odd" "even" ]
len sieve[] 100000
proc init .
for i = 2 to sqrt len sieve[]
if sieve[i] = 0
j = i * i
while j <= len sieve[]
sieve[j] = 1
j += i
.
.
.
.
init
#
func[] noprimesums kind .
step = 2
if kind = 1 : step = 1
k = 2
if kind = 2 : k = 3
sums[] = [ 0 1 ]
res[] = [ 1 ]
while len res[] < 8
repeat
s = -1
for s in sums[]
if sieve[k + s] = 0 : break 1
.
until s = -1
k += step
.
if kind = 1 or kind = 2 and k mod 2 = 1 or kind = 3 and k mod 2 = 0
res[] &= k
for s in sums[] : sums[] &= s + k
.
k += step
.
return res[]
.
for k to 3 : print kind$[k] & ": " & noprimesums k- Output:
both: [ 1 8 24 25 86 1260 1890 14136 ] odd: [ 1 9 15 39 105 731 2805 59535 ] even: [ 1 8 24 86 90 780 5940 52350 ]
F#
// Generate No prime sums. Nigel Galloway: April 18th., 2025
let fG n (g:uint64)=n|>List.forall((+)g>>Open.Numeric.Primes.Number.IsPrime>>not)
let noPS()=let rec noPS n g=seq{match fG n g with false->yield! noPS n (g+1uL) |_->yield g; yield! noPS (n@(n|>List.map((+)g))) (g+1uL)} in noPS [0uL] 1uL
let noPSodd()=let rec noPS n g=seq{match fG n g with false->yield! noPS n (g+2uL) |_->yield g; yield! noPS (n@(n|>List.map((+)g))) (g+2uL)} in noPS [0uL] 1uL
let noPSeven()=let rec noPS n g=seq{match fG n g with false->yield! noPS n (g+2uL) |_->yield g; yield! noPS (n@(n|>List.map((+)g))) (if g=1uL then 2uL else g+2uL)} in noPS [0uL] 1uL
noPS()|>Seq.take 10|>Seq.iter(printfn "%d ")
noPSodd()|>Seq.take 10|>Seq.iter(printfn "%d ");;
noPSeven()|>Seq.take 10|>Seq.iter(printfn "%d ");;
- Output:
1 8 24 25 86 1260 1890 14136 197400 10467660 Real: 00:00:28.954, CPU: 00:00:26.937 1 9 15 39 105 731 2805 59535 2658795 78060135 Real: 00:04:53.710, CPU: 00:04:39.656 1 8 24 86 90 780 5940 52350 278460 40768260 Real: 00:01:47.244, CPU: 00:01:43.859
FreeBASIC
Const LIMITE = 10
Const MAX_SUM = 1e9
' Const MAX_SUM = 1+9+15+39+105+731+2805+59535+2658795+78060135 ' is much faster
Dim Shared As Boolean sieve(MAX_SUM)
Sub InitSieve()
sieve(0) = True
sieve(1) = True
For i As Ulongint = 2 To Sqr(MAX_SUM)
If Not sieve(i) Then
For j As Ulongint = i * i To MAX_SUM Step i
sieve(j) = True
Next
End If
Next
End Sub
Sub GenerateSequence(start As Ulongint, limit As Integer, kind As Integer, result() As Ulongint)
Dim As Ulongint k = start
Dim As Ulongint sumas()
Redim sumas(1)
sumas(0) = 0
sumas(1) = start
Dim As Integer numSumas = 2
result(0) = start
Dim As Integer cnt = 1
While cnt < limit
Do
Dim As Boolean valido = True
For i As Integer = 0 To numSumas - 1
If sumas(i) + k > MAX_SUM Then Continue For
If Not sieve(sumas(i) + k) Then
valido = False
Exit For
End If
Next
If valido Then Exit Do
k += 1
Loop
If cnt > 0 Then
If (kind = 1 Andalso (k Mod 2 = 0)) Orelse (kind = 2 Andalso (k Mod 2 = 1)) Then
k += 1
Continue While
End If
End If
result(cnt) = k
cnt += 1
Dim As Integer oldCount = numSumas
numSumas += oldCount
Redim Preserve sumas(numSumas - 1)
For i As Integer = 0 To oldCount - 1
sumas(oldCount + i) = sumas(i) + k
Next
k += 1
Wend
End Sub
InitSieve()
Dim As Ulongint resultados(LIMITE - 1)
Dim As String tipos(2) = {"", "odd ", "even "}
Print "Sequence, starting with 1, then:"
For ft As Integer = 0 To 2
GenerateSequence(1, LIMITE, ft, resultados())
Print !"\nlexicographically earliest " & tipos(ft) & "integer such that no subsequence sums to a prime:"
Print "[";
For i As Integer = 0 To LIMITE - 1
Print Str(resultados(i));
If i < LIMITE - 1 Then Print ", ";
Next
Print "]"
Next
Sleep
- Output:
Sequence, starting with 1, then: lexicographically earliest integer such that no subsequence sums to a prime: [1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660] lexicographically earliest odd integer such that no subsequence sums to a prime: [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795, 78060135] lexicographically earliest even integer such that no subsequence sums to a prime: [1, 8, 24, 86, 90, 780, 5940, 52350, 278460, 40768260]
Java
The runtime is approximately 45 seconds on my modest laptop.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public final class NoPrimeSums {
public static void main(String[] args) {
createListOfPrimes(100_000_000);
final int limit = 10;
System.out.println("Sequence, starting with 1, then:" + System.lineSeparator());
for ( Parity parity : Parity.values() ) {
System.out.print("lexicographically earliest " + parity.text
+ "integer such that no subsequence sums to a prime: " + System.lineSeparator());
System.out.println(noPrimeSums(1, limit, parity) + System.lineSeparator());
}
}
private static List<Integer> noPrimeSums(int start, int limit, Parity parity) {
final int step = ( parity == Parity.BOTH ) ? 1 : 2;
int k = ( parity == Parity.EVEN ) ? 2 : 3;
List<Integer> sums = Stream.of( 0, start ).collect(Collectors.toList());
List<Integer> result = Stream.of( start ).collect(Collectors.toList());
while ( result.size() < limit ) {
do {
boolean valid = true;
for ( int sum : sums ) {
if ( Collections.binarySearch(primes, sum + k) >= 0 ) {
valid = false;
break; // for-next loop
}
}
if ( valid ) {
break; // do-while loop
}
k += step;
} while ( true );
if ( ( parity == Parity.EVEN && k % 2 == 0 ) ||
( parity == Parity.ODD && k % 2 == 1 ) ||
parity == Parity.BOTH ) {
final int size = sums.size();
for ( int i = 0; i < size; i++ ) {
sums.addLast(sums.get(i) + k);
}
result.addLast(k);
}
k += step;
}
return result;
}
private static void createListOfPrimes(int limit) {
primes = new ArrayList<Integer>();
primes.add(2);
final int halfLimit = ( limit + 1 ) / 2;
boolean[] composite = new boolean[halfLimit];
for ( int i = 1, p = 3; i < halfLimit; p += 2, i++ ) {
if ( ! composite[i] ) {
primes.add(p);
for ( int a = i + p; a < halfLimit; a += p ) {
composite[a] = true;
}
}
}
}
private enum Parity {
BOTH(""), EVEN("even "), ODD("odd ");
private Parity(String aText) {
text = aText;
}
private String text;
}
private static List<Integer> primes;
}
- Output:
Sequence, starting with 1, then: lexicographically earliest integer such that no subsequence sums to a prime: [1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660] lexicographically earliest even integer such that no subsequence sums to a prime: [1, 8, 24, 86, 90, 780, 5940, 52350, 278460, 40768260] lexicographically earliest odd integer such that no subsequence sums to a prime: [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795, 78060135]
Julia
""" rosettacode.org/wiki/No_prime_sums """
using Primes
@enum Parity BOTH = 1 EVEN ODD
const KINDS = ["", "odd ", "even "]
const primesieve = primesmask(100_000_000)
function noprimesums(start, limit, kind)
step = kind == BOTH ? 1 : 2
k = kind == EVEN ? 2 : 3
sums = [0, start]
res = [start]
while length(res) < limit
while any(s -> primesieve[k+s], sums)
k += step
end
if kind == BOTH || kind == ODD && isodd(k) || kind == EVEN && iseven(k)
append!(sums, sums .+ k)
push!(res, k)
end
k += step
end
return res
end
function testnoprimesums(limit = 10)
Threads.@threads for kind in (BOTH, ODD, EVEN)
@time a = noprimesums(1, limit, kind)
println("lexicographically earliest $(KINDS[Int(kind)])",
"integer such that no subsequence sums to a prime:\n$a\n")
end
end
testnoprimesums()
- Output:
4.832083 seconds (541.75 M allocations: 8.073 GiB, 15.34% gc time) lexicographically earliest integer such that no subsequence sums to a prime: [1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660] 11.513322 seconds (1.02 G allocations: 15.274 GiB, 14.54% gc time) lexicographically earliest odd integer such that no subsequence sums to a prime: [1, 8, 24, 86, 90, 780, 5940, 52350, 278460, 40768260] 21.573850 seconds (1.43 G allocations: 21.365 GiB, 11.67% gc time) lexicographically earliest even integer such that no subsequence sums to a prime: [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795, 78060135]
Phix
atom t0 = time()
constant BOTH = 0, ODD = 1, EVEN = 2
sequence c = repeat(false,1e8)
for p in get_primes_le(1e8) do c[p] = true end for
function some(sequence sums, integer k)
for s in sums do
if c[s+k] then return true end if
end for
return false
end function
function no_prime_sums(integer limit, kind)
integer step = iff(kind == BOTH ? 1 : 2),
k = iff(kind == EVEN ? 2 : 3)
sequence sums = {0,1},
res = {1}
while length(res)<limit do
while some(sums,k) do k += step end while
if (kind == BOTH)
or (kind == ODD and odd(k))
or (kind == EVEN and even(k)) then
sums = unique(sums&sq_add(sums,k))
res &= k
end if
k += step
end while
return res
end function
constant limit = 10
for kind = BOTH to EVEN do
printf(1,"%s: %v\n",{{"both","odd","even"}[kind+1],no_prime_sums(limit,kind)})
end for
?elapsed(time()-t0)
- Output:
both: {1,8,24,25,86,1260,1890,14136,197400,10467660}
odd: {1,9,15,39,105,731,2805,59535,2658795,78060135}
even: {1,8,24,86,90,780,5940,52350,278460,40768260}
"13.7s" -- limit of 10, if 9: "1.0s", if 8: "0.8s"
Raku
This version is multi-threaded to take advantage of multicore processors. When run on a Ryzen 5950 16 core processor, it takes a little under 1 second total to produce the first 8 elements of all three sequences. Stepping up to 10 elements of each takes just over 31 minutes total. :-( The timing will scale inversely with the number of cores available.
Attempt This Online! (8 elements only)
say "Sequence, starting with 1, then:";
for '', (*), 'odd ', (* % 2), 'even ', (* %% 2) -> $label, $filter {
my @check = 0, 1;
my @seq = 1, |lazy gather loop {
state $last = 1;
take $last = ($last^..Inf).grep($filter).hyper.grep({ none (@check.grep({.defined}) »+» $_)».is-prime })[0];
@check.append: @check »+» $last;
}
say "\nlexicographically earliest {$label}integer such that no subsequence sums to a prime:\n",
@seq[^10];
}
- Output:
Sequence, starting with 1, then: lexicographically earliest integer such that no subsequence sums to a prime: (1 8 24 25 86 1260 1890 14136 197400 10467660) lexicographically earliest odd integer such that no subsequence sums to a prime: (1 9 15 39 105 731 2805 59535 2658795 78060135) lexicographically earliest even integer such that no subsequence sums to a prime: (1 8 24 86 90 780 5940 52350 278460 40768260)
Rust
/// Our powerset grows very slowly, and at one element at a time, so I've decided to move
/// bookkeeping into a separate class to simplify the logic
pub struct Powerset {
elements: Vec<Vec<u64>>,
}
impl Powerset {
pub fn new(n: u64) -> Powerset {
Powerset {
elements: vec![vec![], vec![n]],
}
}
/// Returns only the values inserted that generated the powerset
pub fn ones(&self) -> impl Iterator<Item = &u64> {
self.sets().filter(|inner| inner.len() == 1).flatten()
}
pub fn sets(&self) -> impl Iterator<Item = &[u64]> {
self.elements.iter().map(Vec::as_slice)
}
/// Add a copy of our list to our original list with `n` added to each set
pub fn add(&mut self, n: u64) {
let new = self.elements.clone().into_iter().map(|mut x| {
x.push(n);
x
});
self.elements.extend(new);
}
}
#[cfg(feature = "stretch_goal")]
mod consts {
pub const ELEMS: usize = 10;
pub const SIEVE: u64 = 99_999_999;
}
#[cfg(not(feature = "stretch_goal"))]
mod consts {
pub const ELEMS: usize = 8;
pub const SIEVE: u64 = 99_999;
}
static PRIME_SIEVE: std::sync::LazyLock<Vec<bool>> = std::sync::LazyLock::new(|| {
let n = consts::SIEVE;
let mut b = vec![true; n];
b[0] = false;
b[1] = false;
for i in 2..n.isqrt() {
if b[i] {
for j in (i * i..n).step_by(i) {
b[j] = false;
}
}
}
b
});
/// To test all subsequences, we initially create a powerset starting with `1` which creates the
/// powerset `[[], [1]]`. If any sum of subsequences plus the next number in the sequence is
/// composite, we add that number to the powerset which doubles it, and finally return sets that
/// contain exactly one element.
fn seq(seq_type: SeqType) -> Vec<u64> {
let seq = match seq_type {
SeqType::Both => (2..).step_by(1),
SeqType::Even => (2..).step_by(2),
SeqType::Odds => (3..).step_by(2),
};
let mut powerset = Powerset::new(1); // [[], [1]]
'next: for i in seq {
for set in powerset.sets() {
// Note: [].sum() == 0
if PRIME_SIEVE[i + set.iter().sum::<u64>() as usize] {
continue 'next;
}
}
powerset.add(i as u64); // [[], [1], [i], [1, i]]
if powerset.ones().count() == consts::ELEMS {
break 'next;
}
}
powerset.ones().cloned().collect() // [[1], [i], [j], ...]
}
#[cfg(feature = "stretch_goal")]
fn run_time(s: SeqType) -> (Vec<u64>, core::time::Duration) {
let start_time = std::time::Instant::now();
let ret = seq(s);
(ret, start_time.elapsed())
}
enum SeqType {
Both,
Even,
Odds,
}
const OUT: [(&str, SeqType); 3] = [
(" ", SeqType::Both),
(" odd ", SeqType::Odds),
(" even ", SeqType::Even),
];
fn main() {
// Populate the sieve now
std::sync::LazyLock::force(&PRIME_SIEVE);
println!("Sequence, starting with 1, then:\n");
for (what, seq_type) in OUT {
println!(
"lexicographically earliest{what}integer such that no subsequence sums to a prime:"
);
#[cfg(not(feature = "stretch_goal"))]
println!("{:?}\n", seq(seq_type));
#[cfg(feature = "stretch_goal")]
{
let (seq, elapsed) = run_time(seq_type);
println!("{seq:?} (took {elapsed:?})\n");
}
}
}
- Output:
Sequence, starting with 1, then: lexicographically earliest integer such that no subsequence sums to a prime: [1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660] (took 273.101ms) lexicographically earliest odd integer such that no subsequence sums to a prime: [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795, 78060135] (took 1.1004691s) lexicographically earliest even integer such that no subsequence sums to a prime: [1, 8, 24, 86, 90, 780, 5940, 52350, 278460, 40768260] (took 563.329ms)
Wren
This is based on the Python code in the first OEIS link which I've modified to deal with the 'odd' and 'even' only cases. However, rather than check primality in a piece-meal fashion, I've sieved initially for primes up to 100 million which uses a lot of memory but is much quicker.
The runtime is around 2 minutes 16 seconds on my Core-i7 8565U machine. Although this CPU has 4 cores, Wren's VM is single threaded and so can only use one of them.
import "./math" for Int
import "./ordered" for OrderedSet
var BOTH = 0
var ODD = 1
var EVEN = 2
var kinds = ["", "odd ", "even "]
var c = Int.primeSieve(1e8, false)
var noPrimeSums = Fn.new { |start, limit, kind|
var step = kind == BOTH ? 1 : 2
var k = kind == EVEN ? 2 : 3
var sums = OrderedSet.new()
sums.add(0)
sums.add(start)
var res = [start]
while (res.count < limit) {
while (sums.any { |s| !c[k + s] }) k = k + step
if (kind == BOTH ||
(kind == ODD && k % 2 == 1) ||
(kind == EVEN && k % 2 == 0) ){
var extra = sums.map { |s| k + s }.toList
sums.addAll(extra)
res.add(k)
}
k = k + step
}
return res
}
var LIMIT = 10
System.print("Sequence, starting with 1, then:")
for (kind in [BOTH, ODD, EVEN]) {
System.print("\nlexicographically earliest %(kinds[kind])integer such that no subsequence sums to a prime:")
System.print(noPrimeSums.call(1, LIMIT, kind))
}
- Output:
Sequence, starting with 1, then: lexicographically earliest integer such that no subsequence sums to a prime: [1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660] lexicographically earliest odd integer such that no subsequence sums to a prime: [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795, 78060135] lexicographically earliest even integer such that no subsequence sums to a prime: [1, 8, 24, 86, 90, 780, 5940, 52350, 278460, 40768260]
XPL0
The nine elements shown here take 5.5 seconds on a Raspberry Pi 4. Adding one more element, for ten, took almost 15 minutes. Perhaps a sieve should have been used.
include xpllib; \for IsPrime
define Limit = 9;
proc Task(Start, Step);
int Start, Step;
int Seq(Limit);
int N, Count;
func NoPrimeSums; \Return 'true' if N has no prime sums in Seq
int Combo, Sum, I;
[for Combo:= 0 to 1<<Count - 1 do
[Sum:= N;
for I:= 0 to Count-1 do
if Combo & 1<<I then
Sum:= Sum + Seq(I);
if IsPrime(Sum) then return false;
];
return true;
];
[Seq(0):= 1; Count:= 1;
Text(0, "[1, ");
N:= Start;
loop [if NoPrimeSums(N) then
[Seq(Count):= N;
Count:= Count+1;
IntOut(0, N);
if Count >= Limit then quit;
Text(0, ", ");
];
N:= N+Step;
];
Text(0, "]^m^j");
];
[Task(2, 1);
Task(3, 2); \must be odd
Task(2, 2); \must be even
]- Output:
[1, 8, 24, 25, 86, 1260, 1890, 14136, 197400] [1, 9, 15, 39, 105, 731, 2805, 59535, 2658795] [1, 8, 24, 86, 90, 780, 5940, 52350, 278460]