This site is supported by donations to The OEIS Foundation.
User:M. F. Hasler/Prime sums from neighboring terms
Contents
Prime sums from neighboring terms
Introduction
This page discusses a family (or rather two families) of sequences of the form:
For all n ≥ o, there are exactly N primes among the sums a(n+i) + a(n+j), 0 ≤ i < j < M: S(N, M; o) is the lexicographic first such sequence of distinct numbers ≥ a(o) = o.
Depending on o = 0 or 1, we get a "nonnegative variant" starting with a(0) = 0 or a "positive variant" starting with a(1) = 1.
Both appear to be permutations (cf. section Surjectivity below) of the corresponding sets N = {0, 1, 2, ...} resp. N* = {1, 2, 3, ...}, for all compatible values of N and M, see the next subsection.
The restriction of the "nonnegative" variant to N* (i.e., positive indices & values) is then a permutation of N*, but not necessarily the lexicographic first: only for some particular (N,M) we do have S(N, M; 1) = S(N, M; 0) \ {0} (with slight abuse of notation):
- S(2,3;1) = S(2,3;0) \ {0} = A329411 ; S(4,4,0) = S(4,4,1) U {0} = A329449 ; S(6,5;0) = S(6,5;1) U {0} = A329425.
Interestingly, these are exactly the cases where N = Nmax(M), the largest possible value (cf. next subsection). However, for M = 6 and N = 9 = Nmax(6), the sequences S(N,M;0) and S(N,M;1) are very different.
When this is not the case (i.e., S(N,M;0) and S(N,M;1) differ "right from the beginning"), then the two variants usually do no merge at any later point, which is quite surprising at first sight. We know only two exceptions, namely:
- A329333 \ {0} = S(1,3;1) = (1, 2, 7, 3, 6, 4, ...) equals S(1,3;0) = (0, 1, 3, 6, 2, 7, 4, ...) on N* \ {1, 2, 3, 4, 5}.
- S(7,6;0) equals S(7,6;1) on N* \ {5, 6; 11, 12}:
n | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, ... ------------+------------------------------------------------------------------------------------------------------------ S(7,6;0)(n) | 0, 1, 2, 3, 4, 8, 5, 11, 26, 15, 9, 32, 14, 17, 20, 21, 27, 10, 16, 19, 7, 12, 13, 24, 6, 23, 35, 25, ... S(7,6;1)(n) | - 1, 2, 3, 4, 5, 8, 11, 26, 15, 9, 14, 32, 17, 20, 21, 27, 10, 16, 19, 7, 12, 13, 24, 6, 23, 35, 25, ...
Compatible (N, M)
Using M consecutive values, we have M(M+1)/2 pairwise sums. However, terms with the same parity can't yield a prime sum. Working out the details, we find that we can have at most Nmax ≤ floor(M/2)·ceiling(M/2) prime sums. Depending on M, this yields the following maximal values for N and corresponding sequences:
M Nmax o = 0 o = 1 2 1 A128280 A055265 Simpler definition: a(n)+a(n+1) is prime for all n. 3 2 A329411 U {0} A329411 4 4 A329449 A329449 \ {0} 5 6 A329425 A329425 \ {0} 6 9 A329569 A329568 In contrast to the two above, here S(9,6;1) is very different from S(9,6;0)! 7 12 A329572 A329573 8 16 ? ? known are A329581 (N=11), A329580 (N=10).
The sequences
Table as square array
N | M = 2 3 4 5 6 7 8 9 10 = M | N -----+-----------+----------+----------+----------+----------+----------+----------+----------+----------+--------+----- 12 | # A329572* 12 12 | # A329573* 12 11 | - A329581° 11 10 | (Here N > Nmax: ----------- A329580° 10 9 | impossible.) - - # A329569° A329579° 9 9 | - - # A329568* 9 8 | - - 8 7 | ° means o=0 - ----------- A329567° A329577° 7 6 | * means o=1 - # A329425² A329566° *S(7,7,1)=(1..6,89,8,7,9..11,...) 6 5 | ² means both - A329564° A329565° 5 5 | # means Nmax ----------- A329563* 5 4 | - # A329449² A329456° 4 3 | - A329454° A329455° 3 3 | - ----------- A329417* 3 2 | - # A329411² A329452° A329453° 2 2 | -----------# A329411² A329412* A329413* A329414* A329415* A329416* 2 1 | # A128280° A329333² 1 1 | # A055265* A329333² A329406* A329407* A329408* A329409* A329410* 1 0 | A253074° A329450° (to do?) (to do?) (to do?) (to do?) ... ... ... 0 0 | A055266* A329405* (to do?) (to do?) (to do?) (to do?) 0 -----+-----------+----------+----------+----------+----------+----------+----------+----------+----------+--------+----- N | M = 2 3 4 5 6 7 8 9 10 = M | N
Table as list
Here we sort the sequences by decreasing values of N (number of prime sums), then by increasing M (number of consecutive terms). This means in some sense the "least trivial" ones first: sequences with high number of prime sums are less simple to compute, but as the number of consecutive terms grows, they are more and more easily computed (and "smooth").
A329574 (N=12, M=7; 1), (Nmax for M=7; the o=0 variant is not yet known) A329581 (N=11, M=8; 0), for other M the greedy computation blocks at n = ... A329580 (N=10, M=8; 0), -- // -- A329569 (N=9, M=6; 0), A329568 (N=9, M=6; 1), (Nmax for M=6), A329579 (N=9, M=7; 0) - (N=8, M=6; 0), A329577 (N=7, M=7; 0), A329425 (N=6, M=5; 0 and 1) (Nmax for M=5), A329566 (N=6, M=6; 0), A329564 (N=5, M=5; 0), A329563 (N=5, M=5; 1), A329565 (N=5, M=6; 0), A329449 (N=4, M=4; 0), (Nmax for M=4), A329456 (N=4, M=5, 0), A329417 (N=3, M=4; 1), A329454 (N=3, M=4, 0), A329455 (N=3, M=5, 0), A329411 (N=2, M=3; 1 and 0) A329452 (N=2, M=4; 0), A329412 (N=2, M=4; 1), A329453 (N=2, M=5; 0), A329413 (N=2, M=5; 1), A329414 (2, M=6; 1), A329415 (2, M=7; 1), A329416 (2, M=10; 1), A128280 (N=1, M=2; 0), A055265 (N=1, M=2; 1), A329333 (N=1, M=3; 0 and 1): S(1, 3; 0) = (0, 1, 3, 6, 2, 7, 4, ...) unless one adds "odd" in front of "prime": then one gets 0 followed by S(1, 3; 1) = (1, 2, 7, 3, 6, 4, ...). From a(6..) = (4, 5, 8, 10, 11, 9, 12, ...) on, both are equal. A329406 (N=1, M=4; 1), A329407 (1, 5; 1), A329408 (1, 6; 1), A329409 (1, 7; 1), A329410 (1, 10; 1); A253074 (N=0, M=2; 0) = 0,A055266 (0, 2; 1); A329450 (0, 3; 0), A329405 (0, 3; 1): here no primes must occur!
Alternate table: by A-number
A055265 (N=1, M=2; 1), A055266 (N=0, M=2; 1); A128280 (N=1, M=2; 0), A253074 (N=0, M=2; 0); A329333 (N=1, M=3; 0/1); . A329405 (0, 3; 1), A329406 (1, 4; 1), A329407 (1, 5; 1), A329408 (1, 6; 1), A329409 (1, 7; 1), A329410 (1, 10; 1); A329411 (2, 3; 1/0), A329412 (2, 4; 1), A329413 (2, 5; 1), A329414 (2, 6; 1), A329415 (2, 7; 1), A329416 (2, 10; 1); A329417 (3, 4; 1), --- (recycled) A329425 (6, 5; 0/1); . A329449 (4, 4; 0), A329450 (0, 3; 0), (-51: recycled) A329452 (2, 4; 0), A329453 (2, 5; 0), A329454 (3, 4, 0), A329455 (3, 5, 0), A329456 (4, 5, 0). [end of this range!] . A329563 (5, 5; 1), A329564 (5, 5, 0); A329565 (5, 6, 0) A329566 (6, 6; 0), A329567 (7, 6, 0), A329568 (8, 6; 0), A329569 (9, 6; 0), -70/-71: Ramanujan A329572 (10, 7, 0) A329573 (11, 7, 0) A329574 (12, 7, 1), A329575 (9, 6; 1), A329576 (7, 6; 1), A329577 (7, 7; 0), A329578: recycled! A329579 (9, 7; 0), A329580 (10, 8; 0), A329581 (11, 8; 0),
About existence etc
Do the sequences exist for all n ≥ o?
If the sequence is to be computed in a greedy manner, this means that for given n, we assume given
- P(n) := {a(n-1), ..., a(n-M+1)} and thus N(n) := #{ (x,y) in P(n)² | x < y and x + y is prime }
which may take a value in {0, ..., N}. We have to find a(n) such that we have exactly N - N(n) primes in a(n) + P(n). (P(n) has M-1 distinct elements, so the same is true for a(n) + P(n), even though the sums x + y are not necessarily distinct, and some of the primes in a(n) + P(n) may be the same than those already counted in N(n).)
It is easy to prove that this is always possible when N - N(n) = 0 or 1. When a larger number of primes is needed, it is not unconditionally known whether an a(n) as specified above does exist. This would, e.g., require (and/or imply) the Twin Prime Conjecture or an analog, depending on the prime constellations compatible with the given P(n). However, if n ≥ M, then at least we know that P(n) is an "admissible" constellation in the sense that we have already obtained the required number of N primes using the same set P(n) and, previously, the additional number a(n-M).
However, the sequence need not be computable in greedy manner. That is, if for given P(n) no a(n) would exist such that a(n) + P(n) contains N - N(n) primes, this simply means that the considered value of a(n-1) (an maybe a(n-2) etc) was incorrect, and the next larger choice has to be made. Given this freedom, well-definedness of these sequence up to infinity seems more than highly probable.
Not greedily computable variants
With larger M and N close to Nmax, it becomes more and more frequent that the greedy choice of a term is incorrect in that it prevents from continuing the sequence indefinitely. Usually,
- this happens very early, mostly within the M initial terms,
- the construction will block immediately after the incorrect choice, or right after the M initial values.
- Once the initial terms are passed, the greedy choices are correct for all terms, or at least several hundreds.
List of choices that must be excluded
Here is the list of choices that must be excluded ("by hand" or using backtracking) in order to compute the respective sequence.
(They are given as a(i) ≠ {...} or simply as [i,xi] for a(i) ≠ xi.)
- S(5,5;0): [5, 4], while S(5,5;1) is straightforward.
- S(8,6;0): [5, 5].
- S(9,7;1): [7, 7], while S(9,7;0) is straightforward.
- S(10,7;0): a(6) ∉ {6, 7}, a(37) ≠ 19, a(58) ≠ 46, ... [This need for late backtracking is exceptional!]
- S(11,7,0): a(5) ∉ {5, 6}.
- S(12,7,1): a(5), a(6) ∉ {5..8}.
- S(12,7,0): a(3) ∉ {3, 4} (=> a(3) = 5), a(4) ∉ {3, 4} (=> a(4) = 6), a(5) ∉ {3, 4, 7..10}.
[To compute the sequence it is enough to know the final value of the respective a(i), but the list of choices that would be made if not excluded contains more information.]
Some worked out examples
We actually do have examples of such sequences that are not greedily computable, right at the start. For example,
- S(5,5;1) = (1, 2, 3, 4, 5, 8, 9, 14, 6, 23, 17, 7, 12, 24, 10, 13, 19, 16, 18, 25, 22, 15, 28, 21, 26, 32, 75, ...)
is greedily computable. However, if we try to start with o=0, then we correctly find a(0..4) = (0, 1, 2, 3, 6), but would use 4 for the next term a(5). Indeed, {1, 2, 3, 6, 4} has exactly 5 pairs {x, y} which sum to a prime. Then, however, a(6) must give 3 additional primes when added to {2, 3, 6, 4}, having already two pairs {2, 3} and {3, 4} with prime sum. But this is obviously impossible. So we must use the larger a(5) = 5 instead, to get
- S(5,5;0) = (0, 1, 2, 3, 6, 5, 8, 11, 7, 12, 29, 18, 19, 4, 13, 9, 22, 10, 21, 14, 57, 16, 15, 17, ...)
without further problems. [We have highlighted two large values occurring relatively early, and the '4' coming quite late.]
Let us remark that the existence of S(N,M;0) implies existence of S(N,M;1) and an "upper limit" for it, since the restriction of the former to positive indices yields a possible (not necessarily lexicographic minimal) solution. But conversely it is usually not possible to "prefix" a zero to S(N,M;1) and have the required number of primes among pairwise sums using the first M terms.
Similarly (but the converse concerning the offset), we have
- S(9,7;0) = A329579 = (0, 1, 2, 3, 4, 5, 20, 9, 10, 8, 33, 11, 6, 50, 21, 17, 56, 12, 47, 14, 26, 7, 125, 15, 24, ...)
straightforwardly, but if we start at o=1, we get blocked at
- 1,2,3,4,5,6,7,?
and have to use a(7) = 8 instead, after which the computation goes on without known problem, to get
- S(9,7;1) = 1, 2, 3, 4, 5, 6, 8, 9, 14, 15, 11, 23, 18, 218, 20, 21, 10, 33, 51, 12, 38, 46, 7, 76, 25, 55, 16, 17, 24, 13, 28, 19, 43, ...)
(Note the quite large a(14) = 214 and the late a(23) = 7.)
There are more examples like these. [TO DO: "complete" list? e.g.:
- S(12,7,1): need to impose a(5) > 8, a(6) > 8.
However, in most of these, once the initial terms are fixed, the greedy computation will work indefinitely or at least for hundreds of terms. [Make this more precise: where does it stop for examples other than the one below?]
One notable exception is the sequence
- S(10,7,0) = (0, 1, 2, 3, 4, 5, 8, 9, 10, 14, 33, 15, 20, 27, 26, 11, 32, 16, 41, 21, 57, 116, 22, 51, 38, 23, 50, 63, 86, 6, 17, ...)
Here, not only (i, x(i)) = {(6, 6), (6, 7)} but also {(37, 19), (58, 46), ...} must be excluded to continue the computation.
Surjectivity
It appears that the sequences are actually permutations of their respective domain, {0, 1, 2, ...} resp. {1, 2, 3, ...}, i.e., all positive integers eventuallay appear. So far we don't have a formal proof for this, but at least the following argument:
If a number m would never appear, this would mean that for all n beyond some n* (see below), the sets P(n) = {a(n-1), ..., a(n-M+1}} are never such that m + P(n) would contain the required number of N - N(n) primes, although for each of these P(n), as well a(n-M) + P(n) as a(n) + P(n) do have exactly that number of primes. This appears extremely unlikely, insofar more as the same prime producing patterns in these P(n) will repeat infinitely often according to the k-tuple conjecture.
(If m is the smallest number which never appears, then the above mentioned n* is the point where all n < m have appeared. Before that point it is normal that m does not appear when there is a smaller number a(n) such that a(n) + P(n) has the required number of primes.)
Programs
PARI code to compute the sequence
The following computes n terms of the sequence S(N,M;o) [note the first argument n in front of the parameters N,M;o !], starting with a(o) = o; thus, up to a(n−1+o). Additional optional arguments (p, u, ...) are explained below.
S(n, N=3, M=4, o=0, p=[], u=o, U=vecsum([1<<(p-u)|p<-p]))={vector(n,n, if(n>#p+1 /* normal case: beyond initial values */
, if( o>u,/*a hole remains*/ U+=1<<(o-u),/*else*/ U>>=-u+u+=valuation(U+2, 2)); /* bookkeeping of used values */
p=concat( if( #p >= M-1, p[^1], p), o); /* append o to the list of previous terms, delete the oldest one if vector full */
my( c=N-sum(i=2, #p, sum(j=1, i-1, isprime(p[i]+p[j])))); /* count number of prime sums, resp. how many are needed */
if( #p<M-1 /* not yet M-1 past values: any number of <= c additional primes is acceptable, we'll complete... */
, for(k=u, oo, bittest(U, k-u) || vecsum([isprime(p+k)|p<-p])>c || [o=k,break]) /* ...with the next term(s). */
, for(k=u, oo, bittest(U, k-u) || vecsum([isprime(p+k)|p<-p])!=c || [o=k, break]) /* else we need exactly c primes */
)
, #p, n>1 || p=concat(p,o); o=p[n]; n<#p || p=p[^n] /* p had been given (otherwise, nothing to do: o is already set) */
)/*end if n>#p+1. Put " ;print(o",") " here to show progress if the function doesn't return (infinite k-loop at some n). */
;o) /*end vector*/+print([u])} /* print smallest unused number at end of computation */
Additional optional arguments which can be used to tweak the computation:
- The vector p holds the M−1 past values, so a computation can be started with o, following the values given in p. The program will initialize the bitmap U of used values accordingly, see below. [Note: The program can not be given more than M-1 initial values in p (plus the value o =: a(n)).]
- This option can be used to resume a computation at a given point with a known value a(n) = o, preceded by the M-1 terms p = (a(n-M+1), ..., a(n-1)). But if other larger values have appeared earlier, then U (cf. below) must be initialized by hand.
- The variable u equals the smallest unused value so far (after the values possibly given in p, but prior to using o). Only terms ≥ u will be considered in the search for a solution, smaller values are "forbidden".
- U stores the bitmask of values ≥ u which have been used earlier and are thus excluded. Here bit j ≥ 0 corresponds to the value u + j, cf.
bittest(...)in code.
A variant
The parameters p, U and u allow to bypass a point where the greedy computation would block. But as the examples below illustrate, this is slightly cumbersome. Therefore we have also implemented a different mechanism to avoid given values at given indices, through an "exclusion list" X = {(i, xi)}. For example, X = { (2,3), (3,4) } would mean that the value a(n)=3 is forbidden for the 2nd term, and the value a(n)=4 is forbidden for the 3rd term. [Since PARI vectors start at index 1 and we forget about the offset, we have to use i = n+1 when the sequence starts at offset 0.]
Furthermore we can replace vecsum([isprime(x+k)|x<-p]) by the slightly shorter and faster #[0|x<-p,isprime(x+k)].
We can also combine the two central lines which only differ in ">" vs "!=" depending on the general case of large n or the special case of n < M or rather #p < M-1, i.e., when still within the initial terms where the total number of prime sums may be smaller than the target value N. To do so, we notice that the condition N(...) ≤ c can be written N(...) - c ≤ 0 or c - N(...) ≥ 0, but it must never be negative. To allow the inequality for #p < M-1 we can take the minimum of c - N(...) and (0 if #p < M-1, or 1 if #p >= M-1): This is
- negative if c < N(...),
- zero when either c = N(...) or c > N(...) and #p < M-1,
- and strictly positive if c > N(...) and #p >= M-1.
So we need exactly that this is always zero, and the number "0 or 1 if ..." is simply the Iverson bracket of #p >= M-1:
SX(n, N=3, M=4, o=0, X=[], p=[], u=o, U=vecsum([1<<(x-u)|x<-p]), LIM=199/*or: oo*/)={vector(n,n,
if( n>#p+1 /* normal case: beyond initial values */
, if( o>u,/*a hole remains*/ U+=1<<(o-u), /*else*/ U>>=-u+u+=valuation(U+2, 2)); /* bookkeeping of used values */
p=concat( if( #p >= M-1, p[^1], p), o); /* append o to the list of previous terms, delete the oldest one if vector full */
my( c=N-sum(i=2,#p, sum(j=1,i-1, isprime(p[i]+p[j]))), T= #p>=M-1); /* count number of prime sums, and how many are needed */
for(k=u, u+exponent(U+1)+LIM, bittest(U, k-u)|| min(c - #[0|x<-p, isprime(x+k)], T)|| setsearch(X,[n,k])|| [o=k,break]);
o==p[#p]&& p=[u=o=LIM=U=-3] /* Term not found: These settings will fill the rest of the vector with -3. */
, #p, n>1 || p=concat(p,o); o=p[n]; n<#p || p=p[^n] /* p had been given (otherwise, nothing to do: o is already set) */
)/*end if n>#p+1. Put " ;print(o",") " here to show progress if the function doesn't return (infinite k-loop at some n). */
;o)/*end vector*/+print([u])} /* print smallest unused number (ignoring the last term) at end of computation */
TO DO: implement backtracking in case the loop would block. A simple(?) approach could consist in the following:
- Fix a search limit LIM larger than usual "gaps" => DONE!
- Do the "for(k=...)" loop only up to LIM + the largest value used so far, exponent(U)+u. => DONE!
- If nothing is found up to there, increment the previous value p[#p] = a(n-1) to the next possible value,
- [That's a bit complicated! need to reconstruct earlier value of u, U and also p (how to...??!!);
- - use "the same loop" to find now the replacement of the previous term;
- - need to make this visible in the vector, e.g., use [.] around the replacement value for a(n-1)...
- => must abandon the current structure S(...)=vector(n,n, ...): trials for a(n-1) may quickly fill the vector.]
- In case no replacement value is found within LIM, go back one step further, etc...
Example usage
The program will usually fill the vector p with the correct initial values, so that the requirement of N prime sums is fulfilled for the first M terms. But the default greedy computation may block thereafter if an apparently possible value is chosen for a(n) which later turns out to make continuation impossible, cf. the above not greedily computable example S(5,5;0). In this case, one can impose the correct value of a(n) through the 4th argument o, and give the preceding M-1 values in p, as well as the correct value (smallest unused number) for u. For example, to avoid getting stuck when trying to compute S(5,5;0):
S(30,5,5,5,[1,2,3,6],4) \\ the 4th arg o = 5 forces a(4) = 5 instead of the smaller possibility 4 which would block.
We must give here a(1..4) to get to index 5 (but can not give a(0..4)!), even though these value are computed correctly by default. This returns
[1, 2, 3, 6, 5, 8, 11, 7, 12, 29, 18, 19, 4, 13, 9, 22, 10, 21, 14, 57, 16, 15, 17,...],
which is the sequence S(5,5;0) without its initial 0.
In the above we have put p = a(1..4) "by hand". To get these initial values computed by S(.), ask for just n = M+1 terms:
S(6,5,5) \\ = [0, 1, 2, 3, 6, 4]
This is so far "correct" (i.e., satisfies the constraints), as can be verified using
vector(#%-4,n,N(%[n..n+4])) \\ with function N() given in subsection #Miscellaneous code below
and we can be sure that the program has made the smallest possible choice, so we know that a(4) ≥ 6 and we have to try to find a solution with p = [1,2,3,6] and u = 4, but some larger o = a(5). In case this would not have been possible, we'd need to try with some larger a(4) > 6 as last element in p.
With the second variant of our program, we get the same result including the initial a0 = 0 a bit simpler as
SX(30,5,5,0,[[6,4]]) \\where X=[[6,4]] means "forbid the value 4 for the 6th term" (= a(5) but PARI vectors start at index 1).
Together with the additional improvement that the program doesn't get stuck (but fills the vector with dummy values) when no term is found, this makes it quite a bit easier to find solutions in the non-greedy cases by trial and error.
Second worked example: S(8,7;0) and S(8,7;1)
Let us compute S(8,7;0), i.e., 8 prime sums from 7 terms. The greedy approach gives
P = S(7,8,7) \\ = [0, 1, 2, 3, 4, 5, 90]N(P) \\ = 8
i.e., (0, 1, 2, 3, 4, 5, 90, ...), where {0, ..., 5} already has 8 prime sums and 90 does not give any additional prime sum.
But then it is not possible to continue, which would amount to replace the 0 by another term to keep the same count:
for(n=6,9999, P[1]=n; N(P)==8 && return(n)) \\ gives no result
Indeed, without the 0 we have 5 prime sums in {1, 2, 3, 4, 5, 90} (N(P[^1]) /* = 5 */), and it is impossible to get 3 more by adding a term x:
- If it is an even number x, then x+1, x+3 and x+5 must yield a prime, which is impossible for x ≠ 2: if x+3 is not divisible by 3, then either x+1 or x+5 is divisible by 3.
- It is also impossible to get three prime sums x+2, x+4 and x+90 with an odd x: the first two would imply that {x+2, x+4} = {5, 7} (mod 6), i.e., x = 3 (mod 6) but then x+90 is divisible by 3.
Therefore 90 isn't possible, but we find that 91 is also a solution:
P[1]=0; for(n=6,199, P[7]=n; N(P)==8 && print1(n",")) \\ => 90, 91, 114, 115, 116, 117, ...
and allows to continue:
S(8, 8,7, 91, [0..5], 6) \\ = [0, 1, 2, 3, 4, 5, 91, 6]
but it blocks when we try to get beyond 8 terms. We can "cheat" to see the next larger choice (> 6) for the term following 91:
S(8, 8,7, 91, [0..5], 7) \\ = [0, 1, 2, 3, 4, 5, 91, 10]
and actually can use a larger n, e.g., S(88, 8,7, 91, [0..5], 7), to get the nice surprise that the computations does not block any more beyond that. (But these terms are incorrect since we have illegally forbidden the term 6.)
We can also find this 10 and larger choices with a loop as above,
P[7]=91; for(n=7,199, P[1]=n; N(P)==8 && print1(n",")) \\ => 10, 12, 16, 18, 36, 40, 58, 66, 100, ...
Now to get the correct continuation,
S(99, 8,7, 10, [1,2,3,4,5,91], 6) \\ = [1, 2, 3, 4, 5, 91, 10, 9, 8, 33, 6, 7, 11, 20, 12, 23, 13, 30, 24, 29, 16, 15, 14, 17, 26, ...]
We already know that [0..5, 91] was OK and double-check the rest:
vector(#%-6,n,N(%[n..n+6])) \\ only 8's !
Note that this is the sequence starting at 0 without the initial 0! The sequence starting at 1 would go:
P = S(7, 8,7, 1) \\ = [1, 2, 3, 4, 5, 6, 19]
This also blocks beyond n=7: we double check that there's no possible continuation.
for(n=7,999,P[1]=n;N(P)==8&&return(n)) \\ no result! so let's forbid 19:S(7, 8,7, 6, [1..5], 0, 2^19) \\ = [1, 2, 3, 4, 5, 6, 20] \\ and let's try with this 20:S(77, 8,7, 20, [1..6], 7) \\ = [1, 2, 3, 4, 5, 6, 20, 9, 8, 11, 7, 10, 12, 19, 18, 16, 21, 13, ...]
which is the minimal solution for o = 1, as we can check again with vector(#%-6,n,N(%[n..n+6])).
Remark on use of vecsum vs sum()
These are equivalent: vecsum([...p...|p<-p]) = sum(i=1,#p,...p[i]...). The former allocates an auxiliary vector but is nonetheless rather faster in practice. Side note: both use exactly the same number of characters if p appears only once inside ..., else vecsum is shorter. But since OEIS inserts spaces after each "," in sum(...), vecsum() will give shorter code, anyway.
If we just sum of binary/boolean values {0,1}, it may be even faster to count only the number of (nonzero) terms by crating a vector which has only these. (Side note: a nonzero element in a normal vector takes up lots of space! Consider sizebyte(Vec(0,100)) vs sizebyte([1|x<-[0..99]]) for a (not so nice) surprise!) Thus:
sum(i=1,#p,isprime(p[i])) => better: vecsum([isprime(p),p<-p]) => better: #[0|p<-p,isprime(p)]
Miscellaneous code
The following function (used in the above) computes the number of pairs {x,y} ⊂ P which sum to a prime, for a given set P:
N(P) = sum(i=2,#P, sum(j=1,i-1, isprime(P[i]+P[j])))
(By "pairs {x,y} ⊂ P" we mean "(x,y) ∈ P × P and x < y", i.e., x ≠ y and not counting twice a prime sum x + y = y + x. (In case of x = y, only x = y = 1 could give a prime, but we want to explicitly exclude all such pathologies.). In the above code, P may be a non-ordered list or vector, but it should not have duplicate elements; otherwise, if such elements contribute prime sums, they are counted with the corresponding multiplicity, e.g., N([1,1,2,2]) = 5 for 1 + 1 = 2 and 2 × 2 = 4 times 1 + 2 = 3. But of course if a prime sum arises in two ways, we do want to count it twice, as for 17 = 3 + 14 = 5 + 12 in [3, 5, 12, 14].)
References
- Eric Angelini, Prime sums from neighbouring terms, personal blog "Cinquante signes" (and post to the SeqFan list), Nov. 11, 2019.
- Éric Angelini, Prime sums from neighbouring terms, SeqFan list, Nov. 11, 2019.
Authorship
M. F. Hasler, User:M._F._Hasler/Prime_sums_from_neighboring_terms. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/User:M._F._Hasler/Prime_sums_from_neighboring_terms.
