login
A sequence S describing the position of its prime terms.
22

%I #90 Dec 20 2024 02:15:35

%S 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,

%T 27,61,30,67,71,73,33,79,35,83,38,89,97,40,101,103,44,107,109,46,113,

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

%N A sequence S describing the position of its prime terms.

%C S reads like this:

%C "At position 2, there is a prime in S" [indeed, this is 3]

%C "At position 3, there is a prime in S" [indeed, this is 5]

%C "At position 5, there is a prime in S" [indeed, this is 7]

%C "At position 1, there is a prime in S" [indeed, this is 2]

%C "At position 7, there is a prime in S" [indeed, this is 11]

%C "At position 8, there is a prime in S" [indeed, this is 13]

%C "At position 11, there is a prime in S" [indeed, this is 19]

%C "At position 13, there is a prime in S" [indeed, this is 23]

%C "At position 10, there is a prime in S" [indeed, this is 17], etc.

%C 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.

%C 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]

%C So start S with 2 and the rest follows smoothly.

%C S contains all the primes and they appear in their natural order.

%C Does the ratio primes/composites in S tend to a limit?

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

%C Comments from _N. J. A. Sloane_, Nov 14 2024 (Start)

%C 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).

%C The proof will be added later (see reference).

%C The theorem implies that the sequence consists of the primes and the odd-subscripted composite numbers.

%C All of _Dean Hickerson_'s comments below follow from this theorem. (End)

%C Comments from _Dean Hickerson_, Aug 11 2006: (Start)

%C In the limit, exactly half of the terms are primes. Here's a formula, found empirically, for a(n) for n >= 5:

%C Let pi(n) be the number of primes <= n and p(n) be the n-th prime. Then for n >= 5:

%C - if n is prime or (n is composite and n+pi(n) is even) then a(n) = p(floor((n+pi(n))/2));

%C - if n is composite and n+pi(n) is odd and n+1 is composite then a(n) = n+1;

%C - if n is composite and n+pi(n) is odd and n+1 is prime then a(n) = n+2.

%C Also, for n >= 5, n is in the sequence iff either n is prime or n+pi(n) is even.

%C (This could all be proved by induction on n.)

%C 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)

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

%H N. J. A. Sloane, <a href="/A121053/b121053.txt">Table of n, a(n) for n = 1..20000</a> [First 1000 terms from Kerry Mitchell]

%H Eric Angelini, <a href="http://www.cetteadressecomportecinquantesignes.com/PrimePos.htm">A sequence describing the position of its prime terms</a>, Blog Post, August 2006.

%H E. Angelini, <a href="/A121053/a121053.png">A sequence describing the position of its prime terms</a> [Cached copy, with permission]

%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 9.

%H N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=3RAYoaKMckM">A Nasty Surprise in a Sequence and Other OEIS Stories</a>, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; <a href="https://sites.math.rutgers.edu/~zeilberg/expmath/sloane85BD.pdf">Slides</a> [Mentions this sequence]

%p chi := proc(n) if n <= 3 then 0 else n - numtheory:-pi(n) - 1; fi; end; # A065855, number of composites <= n

%p 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;

%p A121053 := proc(n) local init,t1;

%p init := [2,3,5,1,7];

%p if n<=5 then return(init[n]); fi;

%p if isprime(n) or (not isprime(n) and ((chi(n) mod 2) = 1))

%p then ithprime(floor((n+numtheory:-pi(n))/2));

%p else t1 := chi(n); A002808(t1+1);

%p fi; end;

%p [seq(A121053(n),n=1..120)]; # _N. J. A. Sloane_, Nov 14 2024

%t 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 *)

%o (Python)

%o from sympy import isprime, prime, primepi, composite, compositepi

%o 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)

%o print([a(n) for n in range(1, 81)]) # _Michael S. Branicky_, Nov 29 2024

%o (Python) # faster for initial segment of sequence

%o from sympy import isprime, sieve

%o from itertools import count, islice

%o def nextcomposite(n): return next(k for k in count(n+1) if k not in sieve)

%o def agen(): # generator of terms

%o alst, chin, pin, nextc = [2, 3, 5, 1, 7], 1, 3, 6

%o yield from alst

%o for n in count(6):

%o if isprimen:=n < nextc: pin += 1

%o else: chin, nextc = chin + 1, nextcomposite(nextc)

%o yield sieve[(n+pin)>>1] if isprimen or chin&1 else nextc

%o print(list(islice(agen(), 80))) # _Michael S. Branicky_, Nov 29 2024

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

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

%K nonn,nice

%O 1,1

%A _Eric Angelini_, Aug 10 2006