A377901 -id:A377901 - cp's OEIS frontend

A121053 A sequence S describing the position of its prime terms.

2, 3, 5, 1, 7, 8, 11, 13, 10, 17, 19, 14, 23, 29, 16, 31, 37, 20, 41, 43, 22, 47, 53, 25, 59, 27, 61, 30, 67, 71, 73, 33, 79, 35, 83, 38, 89, 97, 40, 101, 103, 44, 107, 109, 46, 113, 127, 49, 131, 51, 137, 54, 139, 149, 56, 151, 58, 157, 163, 62, 167, 173, 64, 179, 66, 181, 191, 69, 193, 72, 197, 199, 211, 75, 223, 77, 227, 80, 229

Offset: 1

Eric Angelini, Aug 10 2006

S reads like this:
"At position 2, there is a prime in S" [indeed, this is 3]
"At position 3, there is a prime in S" [indeed, this is 5]
"At position 5, there is a prime in S" [indeed, this is 7]
"At position 1, there is a prime in S" [indeed, this is 2]
"At position 7, there is a prime in S" [indeed, this is 11]
"At position 8, there is a prime in S" [indeed, this is 13]
"At position 11, there is a prime in S" [indeed, this is 19]
"At position 13, there is a prime in S" [indeed, this is 23]
"At position 10, there is a prime in S" [indeed, this is 17], etc.
S is built with this rule: when you are about to write a term of S, always use the smallest integer not yet present in S and not leading to a contradiction.
Thus one cannot start with 1; this would read: "At position 1, there is a prime number in S" [no, 1 is not a prime]
So start S with 2 and the rest follows smoothly.
S contains all the primes and they appear in their natural order.
Does the ratio primes/composites in S tend to a limit?
The definition and the comments above are Eric Angelini's original submission. A more formal definition would be "Lexicographically earliest sequence of distinct positive numbers such that k is a term of the sequence iff a(k) is a prime". However, to honor Eric Angelini's memory, we will retain his enigmatic definition. - N. J. A. Sloane, Dec 20 2024
Comments from N. J. A. Sloane, Nov 14 2024 (Start)
Theorem. Let p(k) = k-th prime, c(k) = k-th composite number. For n >= 5, if n is a prime or n = c(2*t+1) for some t, then a(n) = p(k) where k = floor((n+PrimePi(n))/2); otherwise, n = c(2*t) for some t and a(n) = c(2*t+1).
The proof will be added later (see reference).
The theorem implies that the sequence consists of the primes and the odd-subscripted composite numbers.
All of Dean Hickerson's comments below follow from this theorem. (End)
Comments from Dean Hickerson, Aug 11 2006: (Start)
In the limit, exactly half of the terms are primes. Here's a formula, found empirically, for a(n) for n >= 5:
Let pi(n) be the number of primes <= n and p(n) be the n-th prime. Then for n >= 5:
- if n is prime or (n is composite and n+pi(n) is even) then a(n) = p(floor((n+pi(n))/2));
- if n is composite and n+pi(n) is odd and n+1 is composite then a(n) = n+1;
- if n is composite and n+pi(n) is odd and n+1 is prime then a(n) = n+2.
Also, for n >= 5, a(n) is in the sequence iff either n is prime or n+pi(n) is even.
(This could all be proved by induction on n.)
It follows from this that, for n >= 4, the number of primes among a(1), ..., a(n) is exactly floor((n+pi(n))/2). Since pi(n)/n -> 0 as n -> infinity, this is asymptotic to n/2. (End)

N. J. A. Sloane, The Remarkable Sequences of Éric Angelini, MS in preparation, December 2024.

N. J. A. Sloane, Table of n, a(n) for n = 1..20000 [First 1000 terms from Kerry Mitchell]
Eric Angelini, A sequence describing the position of its prime terms, Blog Post, August 2006.
E. Angelini, A sequence describing the position of its prime terms [Cached copy, with permission]
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 9.
N. J. A. Sloane, A Nasty Surprise in a Sequence and Other OEIS Stories, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; Slides [Mentions this sequence]

Cf. A000720, A002808, A065855, A073783, A099861, A105753, A377899.

See A377901 for the analogous sequence if 1 is regarded as a prime.

chi := proc(n) if n <= 3 then 0 else n - numtheory:-pi(n) - 1; fi; end; # A065855, number of composites <= n
A002808 := proc(n) option remember ; local a ; if n = 1 then 4; else for a from procname(n-1)+1 do if not isprime(a) then return a; end if; end do ; end if; end proc;
A121053 := proc(n) local init,t1;
init := [2,3,5,1,7];
if n<=5 then return(init[n]); fi;
if isprime(n) or (not isprime(n) and ((chi(n) mod 2) = 1))
   then ithprime(floor((n+numtheory:-pi(n))/2));
else t1 := chi(n); A002808(t1+1);
fi; end;
[seq(A121053(n),n=1..120)]; # N. J. A. Sloane, Nov 14 2024

a[1]=2; a[2]=3; a[3]=5; a[4]=1; a[n_ /; PrimeQ[n] || !PrimeQ[n] && EvenQ[n+PrimePi[n]]] := Prime[Floor[(n+PrimePi[n])/2]]; a[n_ /; !PrimeQ[n] && OddQ[n+PrimePi[n]]] := If[!PrimeQ[n+1], n+1, n+2]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Mar 21 2011, based on Dean Hickerson's formulas *)

from sympy import isprime, prime, primepi, composite, compositepi
def a(n): return [2, 3, 5, 1, 7][n-1] if n < 6 else prime(n+primepi(n)>>1) if isprime(n) or (c:=compositepi(n))&1 else composite(c+1)
print([a(n) for n in range(1, 81)]) # Michael S. Branicky, Nov 29 2024

# faster for initial segment of sequence
from sympy import isprime, sieve
from itertools import count, islice
def nextcomposite(n): return next(k for k in count(n+1) if k not in sieve)
def agen(): # generator of terms
    alst, chin, pin, nextc = [2, 3, 5, 1, 7], 1, 3, 6
    yield from alst
    for n in count(6):
        if isprimen:=n < nextc: pin += 1
        else: chin, nextc = chin + 1, nextcomposite(nextc)
        yield sieve[(n+pin)>>1] if isprimen or chin&1 else nextc
print(list(islice(agen(), 80))) # Michael S. Branicky, Nov 29 2024

A379051 Lexicographically earliest infinite sequence of distinct positive numbers with the property that n is a member of the sequence iff a(n) is composite.

Original entry on oeis.org

2, 4, 5, 6, 8, 9, 10, 12, 14, 15, 7, 16, 17, 18, 20, 21, 22, 24, 23, 25, 26, 27, 28, 30, 32, 33, 34, 35, 31, 36, 38, 39, 40, 42, 44, 45, 41, 46, 48, 49, 50, 51, 47, 52, 54, 55, 56, 57, 58, 60, 62, 63, 59, 64, 65, 66, 68, 69, 70, 72, 67, 74, 75, 76, 77, 78, 80

Offset: 1

N. J. A. Sloane, Dec 17 2024

nonn

The sequence tells you exactly which terms of the sequence are composite: the second, fourth, fifth, sixth, etc. terms are composite, and this is the lexicographically earliest sequence with this property.
Let P be a property of the nonnegative integers, such as being a prime.
The OEIS contains many entries whose definitions have the following form.
"The sequence is the lexicographically earliest infinite sequence of distinct positive (or sometimes nonnegative) integers with the property that n is a term of the sequence iff a(n) has property P."
That is, the terms of the sequence tell you which terms of the sequence have the property. A121053 is the classical example.
Since these are lists, the offset is usually 1.
There are two versions, one where the sequence is required to be strictly increasing, and an unrestricted version which is not required to be increasing.
Examples:
  Property P    Unrestricted    Increasing
  ----------------------------------------
  Prime         A121053         A079254, A334067 (offset 0)
  Even          A080032         A079253
  Odd           A079313         A079000
  Composite     A379051         A099797
  Not composite A377901         A099798
  Not prime     A379053         A085925

Michael De Vlieger, Table of n, a(n) for n = 1..65536 [Terms 1 to 10000 from Scott R. Shannon]

Cf. A079000, A079253, A079254, A079313, A080032, A085925, A099797, A099798, A121053, A334067, A377901, A379053.

A379053 Lexicographically earliest infinite sequence of distinct positive numbers with the property that n is a member of the sequence iff a(n) is not a prime.

Original entry on oeis.org

1, 3, 4, 6, 7, 8, 9, 10, 12, 14, 13, 15, 16, 18, 20, 21, 19, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 23, 36, 37, 38, 39, 40, 42, 44, 45, 46, 48, 49, 43, 50, 51, 52, 54, 55, 53, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 61, 70, 72, 74, 75, 76, 77, 78, 71

Offset: 1

N. J. A. Sloane, Dec 17 2024

nonn

The sequence tells you exactly which terms of the sequence are either 1 or composite.

See the Comments in A379051 for further information.

Michael De Vlieger, Table of n, a(n) for n = 1..65536 [Terms 1 to 10000 from Scott R. Shannon]

Cf. A079000, A079253, A079254, A079313, A080032, A085925, A099797, A099798, A121053, A334067, A377901, A379051.

nn = 120; u = 3; v = {}; w = {}; c = 4;
{1}~Join~Reap[Do[
  If[MemberQ[w, n],
    k = c; w = DeleteCases[w, n],
    m = Min[{c, u, v}]; If[And[CompositeQ[m], n < m],
      AppendTo[v, n]];
      If[Length[v] > 0,
        If[v[[1]] == m,
        v = Rest[v]]]; k = m];
    AppendTo[w, k]; If[k == c, c++; While[PrimeQ[c], c++]]; Sow[k];
If[n + 1 >= u, u++; While[CompositeQ[u], u++]], {n, 2, nn}] ][[-1, 1]] (* Michael De Vlieger, Dec 17 2024 *)

When sorted, this appears to be the complement of [2, 5, 11, 17, 29, and prime(2*t+1), t >= 35]. - Scott R. Shannon, Dec 18 2024

More terms from Michael De Vlieger, Dec 17 2024

cp's OEIS Frontend

A121053 A sequence S describing the position of its prime terms.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

A379051 Lexicographically earliest infinite sequence of distinct positive numbers with the property that n is a member of the sequence iff a(n) is composite.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A379053 Lexicographically earliest infinite sequence of distinct positive numbers with the property that n is a member of the sequence iff a(n) is not a prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A379786 a(n) = A379059(n) - 2*n.

Views

Author

Keywords

Comments

Links

Crossrefs

A382716 a(n) = n - A382715(n).

Views

Author

Keywords

Comments

Links

Crossrefs

A379787 a(n) = A379060(n) - 2*n.

Views

Author

Keywords

Links

Crossrefs