This site is supported by donations to The OEIS Foundation.
User:M. F. Hasler/A330614
This page is about sequence A330614, the lexico-earliest injection a: N* → N* with no consecutive nonprimes equal to the subsequence of its first differences with indices of primes, (a(n)-a(n+1); a(n) is prime).
Contents
Start of the sequence
A330614 = {1, 5, 4, 11, 6, 13, 9, 19, 8, 29, 23, 10, 31, 22, 37, 18, 41, 33, 43, 14, 47, 24, 59, 49, 61, 30, 67, 45, 53, 16, 73, 55, 79, 38, 83, 50, 71, 28, 89, 75, 101, 54, 109, 85, 103, 44, 97, 48, 107, 46, 149, 119, 127, 60, 113, 68, 131, 78, 137, 121, 139, 66, 151, 96, 163, 84, 167, 129, 157, 74, 173, 123, 179, 108, 181, 153, 191, 102, 193, 118, 199, 98, 197, 143, 223, 114, 211, 126, ...}
Explanation: a(1) = 1 must be followed by a prime a(2) = p, but such that a(2) - a(3) = a(1), i.e., p - a(3) = 1 or p - 1 = a(3), and such that this does not produce a contradiction. Indeed, p = 2 is impossible since this would require a(3) = 1 which already occurred earlier. Also, p = 3 would require a(3) = 2, and then a(3) - a(4) = a(2) or 2 - a(4) = 3, also impossible. Therefore a(2) = 5 is the smallest possible choice.
Since a(2) is prime, a(3) is given by the rule that a(2) - a(3) must reproduce the first term of the sequence, a(1) = 1, whence a(3) = a(2) - 1 = 4.
a(3) = 4 must be followed by a prime, but we see that 2 and 3 are not possible: the first try would be 7, which then ought to be followed by 2, leading again to a "contradiction" (no possible successor), so it turns out that a(4) = 11 is the smallest possible choice.
Computation of the sequence
(1) a prime a(n) = p is always followed by a(n+1) = p - a(N(n)), where N(n) is the number of primes in {a(1), ..., a(n)}. If this a(n+1) > 0 is composite and did not occur earlier, then all terms up to this one are guaranteed to be correct.
(2) a nonprime a(n) is followed by a(n+1) = the next available prime p such that a(n+2) = p - a(N(n+1)) is positive and did not occur earlier. However, the smallest such choice isn't guaranteed to be correct if the resulting a(n+2) is again prime and will subsequently lead to a contradiction, i.e., an illegal successor for the next term imposed by rule (1). In that case, the next larger prime must be chosen.
The "backtracking" introduced in (2) occurs quite often, but in the final sequence, a(11) = 23 is the only known prime to follow an other prime.
Properties
Not a permutation
First, let's note that this sequence is not a permutation: some numbers (2, 3, 7, 12, 15, 17, 20, ...) will never appear. This set comprises primes as well as composites. It is now listed in A330593.
Lower and upper subsequences
The graph of the sequence consists of several "rays" which look like straight lines at a first glance, but their slope increases with the number of terms taken into account. The rays correspond to the following subsets:
- S1 = (5, 11, 13, 19, 29, 31, 37, 41, 43, ...): local maxima (terms smaller than their neighbors) in A330614.
- This is exactly every other term of A330614, except for the point where we have two subsequent primes, a(10) = 29 and a(11) = 23 (are there others?), the second of which is not included here but as first term of S3, below. We could also choose to define S1 as the subsequence of primes, which would only move this term fom S3 to S1 and move the 3rd element of S2, a(12) = 10, to S10.
- The slope of the subgraph of these terms is about Δa(n)/Δn ~ 5 in the range n = 10^3 .. 10^4. (One has a(n)/n ~ 3.6 at n ~ 10^3 and a(n)/n ~ 4.86 at n ~ 10^4. Here n and a(n) still refer to A330614, not to an enumeration of the terms of S1 by indices 1, 2, 3, ...)
- S2 = (1, 8, 10, 18, 14, 30, 16, 38, 28, ...), local minima (smaller than their neighbors) in the remaining terms,
- 1, 4, 6, 9, 8, 23, 10, 22, 18, 33, 14, 24, 49, 30, 45, 16, 55, 38, 50, 28, 75, 54, 85, 44, 48, 46, 119, 60, 68, 78, 121, 66, 96, 84, 129, 74, 123, 108, 153, 102, 118, 98, 143, 114, 126, ...
- The slope of the subgraph of these terms varies from 2.3 to 3.1 in the range 10^3 .. 10^4. (a(n)/n ~ 2.0 at n = 10^3, a(n)/n ~ 2.62 at n = 10^4.)
- S3 = (23, 33, 49, 55, 85, 119, 121, 129, 153, 143, ...), local maxima (larger than their neighbors) in the remaining terms.
- The slope of the subgraph of these terms varies from 3.3 to 4.2 in the range 10^3 .. 10^4. (a(n)/n ~ 2.7 at n = 10^3, a(n)/n ~ 3.65 at n = 10^4.)
- S4 = (4, 48, 118, 138, 190, 208, 236, 314, 318, ...), local minima (smaller than their neighbors) in the remaining terms.
- Here, a(n)/n ~ 2.4 at n = 10^3, ~ 3.18 at n = 10^4.
- S5 = (75, 195, 253, 361, 469, 603, 675, 855, 1227, ...), local maxima (larger than their neighbors) in the remaining terms.
- Here, a(n)/n ~ 2.7 at n ~ 10^3, ~ 3.4 at n = 10^4.
- S6 = (6, 144, 210, 338, 406, 656, 828, 1144, 2052, ...), local minima (smaller than their neighbors) in the remaining terms.
- Here, a(n)/n ~ 2.74 at n ~ 10^3, ~ 3.3 at n = 10^4.
We notice that:
- Each of the subsequences Sk consists roughly (quite precisely, after a few initial terms) in every other of the "remaining" terms, i.e., the terms of the original sequence with those of the preceding subsequences Sj, j < k, removed: the corresponding indices are:
- S1 = a(2, 4, 6, 8, 10, 13, 15, 17, 19, 21, ...): all gaps are 2, except after 10.
- S2 = a(1, 9, 12, 16, 20, 26, 30, 34, 38, 42, ...): most frequent gap is 4. (Only the gaps N° 1, 2, 5, 13, 24 and 31 are ≠ 4.)
- S3 = a(11, 18, 24, 32, 44, 52, 60, 68, 76, ...): most frequent gap is 8. (Only the gaps N° 1, 2, 4, 10, 11, 20, 23 and 33 are ≠ 8.)
- S4 = a(3, 48, 80, 104, 120, 136, 152, 168, 184, ...): most frequent gap is 16. (No gaps after N° 29 and 60 are ≠ 16.)
- S5 = a(40, 100, 128, 176, 208, 272, 304, 400, 528, 560, ...): most frequent gap is 32.
- S6 = a(5, 106, 138, 192, 224, 320, 416, 544, 864, 1120, ...): most frequent gap is 64, etc.
- The subgraph corresponding to the terms of Sk has a slope of quite precisely the average of that of the two preceding ones. This shows that it lies quite precisely in the middle between the two preceding subgraphs.
- The respective subsequences Sk have density 1/2k within the range of the sequence, N* \ A330593.
- However, the slopes are very close for larger k; for these Sk the first few terms appear quite late.
PARI programs
A330614_upto(N=99, show=0/*set to 1 for verbose output*/)={my(i=1, U=[], A=List(i)); for(n=1, N, U=setunion(U, [A[n]]); show&& printf("a(%d) = %d, ", n, A[n]); #A>n || listput(A, 0); /* extend list to index n if needed */ if( isprime(A[n]), if( !setsearch( U, A[n+1] = A[n] - A[i] ) && A[n+1] > 0, i++; next, /* term A[n+1] is OK => A[n] is OK */ show&& print1("no, "); /* we have to backtrack */ until( n==1 || !isprime( A[n] ), /* if A[n] was imposed by a preceding prime, go on */ U=setminus(U, [A[n]]); /* remove A[n] from the list of used terms. */ A[n+1]=0; n--; i-- /* search for subsequent term must start at 0. Decrease indices n & i.*/ ); i++ /* In the end, we did one i-- too much */ )); forprime( k=A[n+1]+1, oo, !setsearch(U, k) && !setsearch(U, k-A[i]) && [A[n+1]=k, break]) /* try next prime (recall, initially A[n+1]=0) */ ); while(!A[#A] || isprime(A[#A]), listpop(A)); Vec(A)} /* discard trailing 0's and primes (unsure) */
Select the indices of local minima / maxima among the subsequence of A = A330614(1..N) with indices in S:
slm(S,s=1/*-1 for maxima*/,A=A330614)={vecextract(S,select(i->(A[S[i+(i<#S)]]-A[S[i]])*s>=0&&(A[S[i-(i>1)]]-A[S[i]])*s>=0,[1..#S]))}
Use this as follows: ("#" in front of assignment to show number of terms, ";" at end of line to suppress output)
#S1 = select(isprime, A, 1) \\ First select indices of primes. We can/will rather use slm(A,-1) to select local maxima. #R1 = setminus([1..#A], Set(S1)) \\ Remaining indices: those of the nonprimes. Set() is needed because select(f,A,1) returns Vecsmall(...) #R1 = select(t->!isprime(t), A, 1) \\ Alternative. (Gives Vecsmall() so Set() is needed around R1 below.) S2 = slm(R1, 1); R2 = setminus(R1, S2); \\ S2 = indices of local minima within the remaining indices R1. R2 = new remaining indices. S3 = slm(R2,-1); R3 = setminus(R2, S3); \\ S3 = indices of local maxima within the remaining indices R2. S4 = slm(R3, 1); R4 = setminus(R3, S4); S5 = slm(R4,-1); R5 = setminus(R4, S5); \\ etc.
EXTract the first n and last m terms of A = A330614(1..N) corresponding to indices S:
xt(S,n=9,m=n,A=A330614)=vecextract(A,concat(S[1..n],S[-m..-1]))
Compute the slope of the k-th subsequence S = Sk between n = a and n = b: (below S = indices relating to A = A330614)
slope(S,a,b,k,A=A330614)=(A[b=S[min(b\/2^k,#S)]]-A[a=S[max(a\/2^k,1)]])/(b-a)
(Use e.g. slope(S2,0,10^4,2)\/1e-3 to get a rounded value of 10^3 x a(n) for some index n of a term of S2 near n = 10^4.)
Authorship
M. F. Hasler, User:M._F._Hasler/A330614. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/User:M._F._Hasler/A330614, initial version: Dec 30 2019