A049077 -id:A049077 - cp's OEIS frontend

A049076 Number of steps in the prime index chain for the n-th prime.

1, 2, 3, 1, 4, 1, 2, 1, 1, 1, 5, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 1

Offset: 1

Neil Fernandez

Let p(k) = k-th prime, let S(p) = S(p(k)) = k, the subscript of p; a(n) = order of primeness of p(n) = 1+m where m is largest number such that S(S(..S(p(n))...)) with m S's is a prime.

The record holders correspond to A007097.

			11 is 5th prime, so S(11)=5, 5 is 3rd prime, so S(S(11))=3, 3 is 2nd prime, so S(S(S(11)))=2, 2 is first prime, so S(S(S(S(11))))=1, not a prime. Thus a(5)=4.
Alternatively, a(5) = 4: the 5th prime is 11 and its prime index chain is 11->5->3->2->1->0. a(6) = 1: the 6th prime is 13 and its prime index chain is 13->6->0.

N. Fernandez, Table of n, a(n) for n = 1..500
N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]
N. Fernandez, The Exploring Primeness Project

Cf. A000040, A049077 - A049081, A006450, A049084, A236542.

a049076 = (+ 1) . a078442  -- Reinhard Zumkeller, Jul 14 2013

A049076 := proc(n)
    if not isprime(n) then
        1 ;
    else
        1+procname(numtheory[pi](n)) ;
    end if;
end proc:
seq(A049076(n),n=1..30) ; # R. J. Mathar, Jan 28 2014

A049076 f[n_] := Length[ NestWhileList[ PrimePi, n, PrimeQ]]; Table[ f[n], {n, 105}] (* Robert G. Wilson v, Mar 11 2004 *)
Table[Length[NestWhileList[PrimePi[#]&,Prime[n],PrimeQ[#]&]]-1,{n,110}] (* Harvey P. Dale, May 07 2018 *)

apply(p->my(s=1);while(isprime(p=primepi(p)),s++); s, primes(100)) \\ Charles R Greathouse IV, Nov 20 2012

Let b(n) = 0 if n is nonprime, otherwise b(n) = k where n is the k-th prime. Then a(n) is the number of times you can apply b to the n-th prime before you hit a nonprime.
a(n) = 1 + A078442(n). - R. J. Mathar, Jul 07 2012
a(n) = A078442(A000040(n)). - Alois P. Heinz, Mar 16 2020

Additional comments from Gabriel Cunningham (gcasey(AT)mit.edu), Apr 12 2003

A050436 Third-order composites.

Original entry on oeis.org

16, 21, 25, 26, 28, 33, 36, 38, 39, 42, 48, 49, 50, 52, 55, 56, 57, 60, 64, 68, 69, 70, 72, 74, 77, 78, 80, 84, 87, 88, 90, 93, 94, 95, 98, 100, 104, 105, 106, 110, 111, 115, 117, 118, 119, 121, 122, 124, 125, 126, 130, 133, 135, 138, 140, 141, 145, 146, 147

Offset: 1

Michael Lugo (mlugo(AT)thelabelguy.com), Dec 22 1999

			C(C(C(8))) = C(C(15)) = C(25) = 38. So 38 is in the sequence.

N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]

Cf. A049076, A049077, A049078, A049079, A049080, A049081, A006450, A050435, A050438, ...

C := remove(isprime,[$4..1000]): seq(C[C[C[C[n]]]],n=1..100);

Nest[Values@ KeySelect[MapIndexed[First@ #2 -> #1 &, #], CompositeQ] &, Select[Range@ 150, CompositeQ], 2] (* Michael De Vlieger, Jul 22 2017 *)

Let C(n) be the n-th composite number, with C(1)=4. Then these are numbers C(C(C(n))).

More terms from Asher Auel Dec 15 2000

A057815 a(n) = gcd(n,binomial(n,floor(n/2))).

Original entry on oeis.org

1, 2, 3, 2, 5, 2, 7, 2, 9, 2, 11, 12, 13, 2, 15, 2, 17, 2, 19, 4, 21, 2, 23, 4, 25, 2, 27, 4, 29, 30, 31, 2, 33, 2, 35, 12, 37, 2, 39, 20, 41, 6, 43, 4, 45, 2, 47, 12, 49, 2, 51, 4, 53, 2, 55, 56, 57, 2, 59, 4, 61, 2, 63, 2, 65, 6, 67, 4, 69, 14, 71, 4, 73, 2, 75, 4, 77, 2, 79, 20, 81, 2

Offset: 1

Labos Elemer, Nov 13 2000

nonn

For even n, a(n) is an even divisor of n.

Hugo Pfoertner, Table of n, a(n) for n = 1..10000

Cf. A001405, A049077.

swing := n -> n!/iquo(n,2)!^2: seq(igcd(n,swing(n)), n=1..82); # Peter Luschny, May 17 2013

a[n_] := GCD[n, Binomial[n, Floor[n/2]]]; Array[a, 100] (* Jean-François Alcover, Jun 03 2019 *)

a(n) = gcd(n,binomial(n, n\2)); \\ Michel Marcus, Mar 22 2020

a(2k+1) = 2k+1. a(2k) = A058005(k).

Offset changed to 1 by Peter Luschny, May 17 2013

A064960 The prime then composite recurrence; a(2n) = a(2n-1)-th prime and a(2n+1) = a(2n)-th composite and a(1) = 1.

Original entry on oeis.org

1, 2, 6, 13, 22, 79, 108, 593, 722, 5471, 6290, 62653, 69558, 876329, 951338, 14679751, 15692307, 289078661, 305618710, 6588286337, 6908033000, 171482959009, 178668550322, 5040266614919, 5225256019175, 165678678591359, 171068472492228, 6039923990345039

Offset: 1

Robert G. Wilson v, Oct 29 2001

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..31
Andrew R. Booker, The Nth Prime Page
N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]

Cf. A007097, A006508 & A064961, see also A057450, A057451, A057452, A057453, A057456 & A057457 and A049076, A049077, A049078, A049079, A049080 & A049081.

Composite[n_Integer] := FixedPoint[n + PrimePi[ # ] + 1 &, n + PrimePi[n] + 1]; a = {1}; b = 1; Do[ If[ !PrimeQ[b], b = Prime[b], b = Composite[b]]; a = Append[a, b], {n, 1, 23}]; a

from functools import cache
from sympy import prime, composite
@cache
def A064960(n): return 1 if n == 1 else composite(A064960(n-1)) if n % 2 else prime(A064960(n-1)) # Chai Wah Wu, Jan 01 2022

a(26)-a(28) from Chai Wah Wu, May 07 2018

A064961 Composite-then-prime recurrence; a(2n) = a(2n-1)-th composite and a(2n+1) = a(2n)-th prime and a(1) = 1.

Original entry on oeis.org

1, 4, 7, 14, 43, 62, 293, 366, 2473, 2892, 26317, 29522, 344249, 376259, 5429539, 5831545, 101291779, 107457490, 2198218819, 2310909505, 54720307351, 57128530327, 1543908890351, 1603146693999, 48871886538151, 50527531769529, 1720466016680911, 1772475453490311

Offset: 1

Robert G. Wilson v, Oct 29 2001

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..32
Andrew R. Booker, The Nth Prime Page
N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]

Cf. A007097, A006508 & A064960, see also A057450, A057451, A057452, A057453, A057456 & A057457 and A049076, A049077, A049078, A049079, A049080 & A049081.

Composite[n_Integer] := FixedPoint[n + PrimePi[ # ] + 1 &, n + PrimePi[n] + 1]; a = {1, 4}; b = 4; Do[ If[ !PrimeQ[b], b = Prime[b], b = Composite[b]]; a = Append[a, b], {n, 1, 23}]; a

a(24)-a(26) corrected and a(27)-a(28) added by Chai Wah Wu, Aug 22 2018

A058010 The main diagonal of N. Fernandez's Order of Primeness array.

Original entry on oeis.org

2, 17, 179, 2221, 27457, 506683, 14161729, 368345293, 9672485827, 318083817907, 12695664159413

Offset: 1

Robert G. Wilson v, Nov 13 2000

N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]

Main diagonal of A236542.

Cf. A049077 - A049081, A007097, A057450 - A057453, A057456, A057457.

a = Select[ Range[ 20 ], ! PrimeQ[ # ] & ] Table[ Nest[ Prime, a[ [ n ] ], n ], {n, 1, 11} ]

cp's OEIS Frontend

A049076 Number of steps in the prime index chain for the n-th prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A050436 Third-order composites.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A057815 a(n) = gcd(n,binomial(n,floor(n/2))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A064960 The prime then composite recurrence; a(2n) = a(2n-1)-th prime and a(2n+1) = a(2n)-th composite and a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A064961 Composite-then-prime recurrence; a(2n) = a(2n-1)-th composite and a(2n+1) = a(2n)-th prime and a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions

A058010 The main diagonal of N. Fernandez's Order of Primeness array.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica