A236542 -id:A236542 - 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

A049078 Primes prime(k) for which A049076(k) = 2.

Original entry on oeis.org

3, 17, 41, 67, 83, 109, 157, 191, 211, 241, 283, 353, 367, 401, 461, 509, 547, 563, 587, 617, 739, 773, 797, 859, 877, 967, 991, 1031, 1087, 1171, 1201, 1217, 1409, 1433, 1447, 1471, 1499, 1597, 1621, 1669, 1723, 1741, 1823, 1913, 2027, 2063, 2081, 2099

Offset: 1

Neil Fernandez

nonn

			For these primes S(p) is a prime but S(S(p)) is not. E.g. S(17)=7, S(7)=4.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]

Cf. A049076, A007821, A049079-A049081, A058322, A058324-A058328, A093046, A006450, A018252, A236542.

Let A = primes A000040, B = nonprimes A018252. The 2-level compounds are AA = A006450, AB = A007821, BA = A078782, BB = A102615. The 3-level compounds AAA, AAB, ..., BBB are A038580, A049078, A270792, A102617, A270794, A270795, A270796, A102616.

A049078 := proc(n) ithprime(A007821(n)) ; end proc: # R. J. Mathar, Aug 14 2008

Nest[ Prime, Select[ Range[70], !PrimeQ[ # ] &], 2] (* Robert G. Wilson v, Mar 15 2004 *)

is(n)=my(p=primepi(n)); isprime(p) && !isprime(primepi(p)) && isprime(n) \\ Charles R Greathouse IV, Apr 29 2015

a(n) = prime(A007821(n)). - Juri-Stepan Gerasimov, Aug 11 2008

a(n) ~ A006450(n) ~ n log^2 n. - Charles R Greathouse IV, Apr 29 2015

Edited by N. J. A. Sloane, Aug 29 2008 at the suggestion of R. J. Mathar

Spelling/notation corrections by Charles R Greathouse IV, Mar 18 2010

A135044 a(1)=1, then a(c) = p and a(p) = c, where c = T_c(r,k) and p = T_p(r,k), and where T_p contains the primes arranged in rows by the prime index chain and T_c contains the composites arranged in rows by the order of compositeness. See Formula.

Original entry on oeis.org

1, 4, 9, 2, 16, 7, 6, 13, 3, 19, 26, 17, 8, 23, 41, 5, 12, 67, 10, 29, 59, 37, 14, 83, 179, 11, 43, 331, 20, 47, 39, 109, 277, 157, 53, 431, 22, 1063, 31, 191, 15, 2221, 27, 61, 211, 71, 30, 599, 1787, 919, 241, 3001, 35, 73, 8527, 127, 1153, 79, 21, 19577, 44, 89, 283

Offset: 1

Katarzyna Matylla, Feb 11 2008

nonn

Exchanges primes with composites, primeth primes with composith composites, etc.
Exchange the k-th prime of order j with the k-th composite of order j and vice versa.
Self-inverse permutation of positive integers.
If n is the composite number A236536(r,k), then a(n) is the corresponding prime A236542(r,k) at the same position (r,k). Vice versa, if n is the prime A236542(r,k), then a(n) is the corresponding composite A236536(r,k) at the same position. - Andrew Weimholt, Jan 28 2014
The original name for this entry did not produce this sequence, but instead A236854, which differs from this permutation for the first time at n=8, where A236854(8)=23, while here a(8)=13. - Antti Karttunen, Feb 01 2014

			From _Andrew Weimholt_, Jan 29 2014: (Start)
More generally, takes the primes organized in an array according to the sieving process described in the Fernandez paper:
        Row[1](n) = 2, 7, 13, 19, 23, ...
        Row[2](n) = 3, 17, 41, 67, 83, ...
        Row[3](n) = 5, 59, 179, ...
        Row[4](n) = 11, 277, ...
        Lets call this  T_p (n, k)
Also take the composites organized in a similar manner, except we use "composite" numbered positions in our sieve:
        Row[1](n) = 4, 6, 8, 10, 14, 20, 22, ...
        Row[2](n) = 9, 12, 15, 18, 24, ...
        Row[3](n) = 16, 21, 25, ...
        Lets call this T_c (n, k)
If we now take the natural numbers and swap each number (except for 1) with the number which holds the same spot in the other array, then we get the sequence: 1, 4, 9, 2, 16, 7, 6, 13, with for example a(8) = 13 (13 holds the same position in the 'prime' table as 8 does in the 'composite' table). (End)

R. J. Mathar, Table of n, a(n) for n = 1..197
N. Fernandez, An order of primeness, F(p).
N. Fernandez, An order of primeness [cached copy, included with permission of the author]
Index to permutations of positive integers

Cf. A000040, A007097, A049076, A049078 - A049081, A058322, A058324 - A058328, A093046, A002808, A006508, A059981, A078442, A236854.

A135044 := proc(n)
    if n = 1 then
        1;
    elif isprime(n) then
        idx := -1 ;
        for r from 1 do
            for c from 1 do
                if A236542(r,c) = n then
                    idx := [r,c] ;
                end if;
                if A236542(r,c) >= n then
                    break;
                end if;
            end do:
            if type(idx,list)  then
                break;
            end if;
        end do:
        A236536(r,c) ;
    else
        idx := -1 ;
        for r from 1 do
            for c from 1 do
                if A236536(r,c) = n then
                    idx := [r,c] ;
                end if;
                if A236536(r,c) >= n then
                    break;
                end if;
            end do:
            if type(idx,list)  then
                break;
            end if;
        end do:
        A236542(r,c) ;
    end if;
end proc: # R. J. Mathar, Jan 28 2014

Composite[n_Integer] := Block[{k = n + PrimePi@n + 1}, While[k != n + PrimePi@k + 1, k++ ]; k]; Compositeness[n_] := Block[{c = 1, k = n}, While[ !(PrimeQ@k || k == 1), k = k - 1 - PrimePi@k; c++ ]; c]; Primeness[n_] := Block[{c = 1, k = n}, While[ PrimeQ@k, k = PrimePi@k; c++ ]; c];
ckj[k_, j_] := Select[ Table[Composite@n, {n, 10000}], Compositeness@# == j &][[k]]; pkj[k_, j_] := Select[ Table[Prime@n, {n, 3000}], Primeness@# == j &][[k]]; f[0]=0; f[1] = 1;
f[n_] := If[ PrimeQ@ n, pn = Primeness@n; ckj[ Position[ Select[ Table[ Prime@ i, {i, 150}], Primeness@ # == pn &], n][[1, 1]], pn], cn = Compositeness@n; pkj[ Position[ Select[ Table[ Composite@ i, {i, 500}], Compositeness@ # == cn &], n][[1, 1]], cn]]; Array[f, 64] (* Robert G. Wilson v *)

a(1)=1, a(A236536(r,k))=A236542(r,k), a(A236542(r,k))=A236536(r,k)

Edited, corrected and extended by Robert G. Wilson v, Feb 18 2008

Name corrected by Andrew Weimholt, Jan 29 2014

A236536 Array T(n,k) read along antidiagonals: the composites of order of compositeness n in row n.

Original entry on oeis.org

4, 6, 9, 8, 12, 16, 10, 15, 21, 26, 14, 18, 25, 33, 39, 20, 24, 28, 38, 49, 56, 22, 32, 36, 42, 55, 69, 78, 27, 34, 48, 52, 60, 77, 94, 106, 30, 40, 50, 68, 74, 84, 105, 125, 141, 35, 45, 57, 70, 93, 100, 115, 140, 164, 184, 44, 51, 64, 80, 95, 124, 133, 152, 183, 212, 236, 46, 63, 72, 88, 110, 126, 162, 174, 198, 235, 270, 299

Offset: 1

R. J. Mathar, Jan 28 2014

Row n contains the composites A002808(j) for which A059981(j) = n.
The 1st row contains the composites with a nonprime index, A002808(1)=4, A002808(2)=6, A002808(3)=8, A002808(5)=10, A002808(7)=14,...
The 2nd row contains the composites with an index in the 1st row.
Recursively the followup rows contain the composites that need a higher number of applications of A002808 to reach a nonprime.

			The array starts:
  4,  6,  8, 10, 14, 20, 22, 27, 30, 35,...
  9, 12, 15, 18, 24, 32, 34, 40, 45, 51,...
 16, 21, 25, 28, 36, 48, 50, 57, 64, 72,...
 26, 33, 38, 42, 52, 68, 70, 80, 88, 98,...
 39, 49, 55, 60, 74, 93, 95,110,119,130,...
 56, 69, 77, 84,100,124,126,145,156,170,...
 78, 94,105,115,133,162,165,188,203,218,...
106,125,140,152,174,209,213,242,259,278,...
141,164,183,198,222,266,272,305,326,348,...

Cf. A006508 (column 1), A022449 (row 1), A135044, A236542, A002808.

A236536 := proc(n,k)
    option remember ;
    if n = 1 then
        A022449(k) ;
    else
        A002808(procname(n-1,k)) ;
    end if:
end proc:
for d from 2 to 10 do
     for k from d-1 to  by -1 do
        printf("%3d,",A236536(d-k,k)) ;
     end do:
end do:

Composite[n_] := FixedPoint[n + PrimePi[#] + 1&, n + PrimePi[n] + 1];
T[n_, k_] := T[n, k] = If[n == 1, Composite[If[k == 1, 1, Prime[k - 1]]], Composite[T[n - 1, k]]];
Table[T[n - k + 1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Sep 16 2023 *)

T(1,k) = A022449(k).

T(n,k) = A002808( T(n-1,k) ), n>1 .

A245815 Permutation of natural numbers induced when A245821 is restricted to nonprime numbers: a(n) = A062298(A245821(A018252(n))).

Original entry on oeis.org

1, 2, 5, 3, 4, 7, 9, 59, 11, 6, 20, 125, 18, 25, 15, 10, 16, 26, 32, 31, 103, 8, 12, 35, 41, 50, 13, 39, 85, 64, 43, 164, 29, 38, 17, 66, 19, 24, 21, 45, 132, 37, 105, 139, 82, 33, 65, 27, 507, 52, 14, 180, 161, 96, 46, 22, 190, 141, 87, 1603, 80, 36, 143, 107, 54, 670, 34, 47, 23, 68, 177, 1337, 40

Offset: 1

Antti Karttunen, Aug 02 2014

nonn

This permutation is induced when A245821 is restricted to nonprimes, A018252, the first column of A114537, but equally, when it is restricted to column 2 (A007821), column 3 (A049078), etc. of that square array, or alternatively, to the successive rows of A236542.

The sequence of fixed points f(n) begins as 1, 2, 15, 142, 548, 1694, 54681. A018252(f(n)) gives the nonprime terms of A245823.

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Inverse: A245816.
Related permutations: A245813, A245819, A245821.
Cf. A007821, A018252, A049078, A062298, A114537, A236542, A245823.

allocatemem(234567890);
v014580 = vector(2^18);
v091226 = vector(2^22);
v091242 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < 2^22), if(isA014580(n), i++; v014580[i] = n; v091226[n] = v091226[n-1]+1, j++; v091242[j] = n; v091226[n] = v091226[n-1]); n++);
A002808(n)={my(k); for(k=0, primepi(n), isprime(n++)&&k--); n}; \\ This function from M. F. Hasler
A062298(n) = n-primepi(n);
A018252(n) = if(1==n, 1, A002808(n-1));
A014580(n) = v014580[n];
A091226(n) = v091226[n];
A091242(n) = v091242[n];
A091205(n) = if(n<=1, n, if(isA014580(n), prime(A091205(A091226(n))), {my(irfs, t); irfs=subst(lift(factor(Mod(1, 2)*Pol(binary(n)))), x, 2); irfs[,1]=apply(t->A091205(t), irfs[,1]); factorback(irfs)}));
A245703(n) = if(1==n, 1, if(isprime(n), A014580(A245703(primepi(n))), A091242(A245703(n-primepi(n)-1))));
A245821(n) = A091205(A245703(n));
A245815(n) = A062298(A245821(A018252(n)));
for(n=1, 10001, write("b245815.txt", n, " ", A245815(n)));

(define (A245815 n) (A062298 (A245821 (A018252 n))))

a(n) = A062298(A245821(A018252(n))).
As a composition of related permutations:
a(n) = A245813(A245819(n)).
Also following holds for all n >= 1:
a(n) = A062298(A049084(A245821(A007821(n)))).
a(n) = A062298(A049084(A049084(A245821(A049078(n))))).

A245816 Permutation of natural numbers induced when A245822 is restricted to nonprime numbers: a(n) = A062298(A245822(A018252(n))).

Original entry on oeis.org

1, 2, 4, 5, 3, 10, 6, 22, 7, 16, 9, 23, 27, 51, 15, 17, 35, 13, 37, 11, 39, 56, 69, 38, 14, 18, 48, 78, 33, 120, 20, 19, 46, 67, 24, 62, 42, 34, 28, 73, 25, 103, 31, 206, 40, 55, 68, 92, 300, 26, 76, 50, 99, 65, 157, 281, 165, 184, 8, 121, 134, 277, 423, 30, 47, 36, 223, 70, 514, 75, 101, 116, 236, 139, 74

Offset: 1

Antti Karttunen, Aug 02 2014

nonn

This permutation is induced when A245822 is restricted to nonprimes, A018252, the first column of A114537, but equally, when it is restricted to column 2 (A007821), column 3 (A049078), etc. of that square array, or alternatively, to the successive rows of A236542.

The sequence of fixed points f(n) begins as 1, 2, 15, 142, 548, 1694, 54681. A018252(f(n)) gives the nonprime terms of A245823.

Antti Karttunen, Table of n, a(n) for n = 1..10001
Index entries for sequences that are permutations of the natural numbers

Inverse: A245815.
Related permutations: A245814, A245820, A245822.
Cf. A007821, A018252, A049078, A062298, A114537, A236542, A245823.

allocatemem(123456789);
default(primelimit, 2^22)
A014580 = vector(2^18);
A091226 = vector(2^22);
A002808(n)={my(k); for(k=0, primepi(n), isprime(n++)&&k--); n}; \\ This function from M. F. Hasler, Oct 31 2008
A062298(n) = n-primepi(n);
A018252(n) = if(1==n,1,A002808(n-1));
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < 2^22), if(isA014580(n), i++; A014580[i] = n; A091226[n] = A091226[n-1]+1, A091226[n] = A091226[n-1]); n++)
A091204(n) = if(n<=1, n, if(isprime(n), A014580[A091204(primepi(n))], {my(pfs,t,bits,i); pfs=factor(n); pfs[, 1]=apply(t->Pol(binary(A091204(t))), pfs[, 1]); sum(i=1, #bits=Vec(factorback(pfs))%2, bits[i]<<(#bits-i))}));
A091245(n) = ((n-A091226[n])-1);
A245704(n) = if(1==n, 1, if(isA014580(n), prime(A245704(A091226[n])), A002808(A245704(A091245(n)))));
A245822(n) = A245704(A091204(n));
A245816(n) = A062298(A245822(A018252(n)));
for(n=1, 10001, write("b245816.txt", n, " ", A245816(n)));

(define (A245816 n) (A062298 (A245822 (A018252 n))))

a(n) = A062298(A245822(A018252(n))).
As a composition of related permutations:
a(n) = A245820(A245814(n)).
Also following holds for all n >= 1:
a(n) = A062298(A049084(A245822(A007821(n)))).
a(n) = A062298(A049084(A049084(A245822(A049078(n))))).
etc.

A333353 Primes p whose order of primeness A078442(p) is prime.

Original entry on oeis.org

3, 5, 17, 31, 41, 59, 67, 83, 109, 157, 179, 191, 211, 241, 283, 331, 353, 367, 401, 431, 461, 509, 547, 563, 587, 599, 617, 709, 739, 773, 797, 859, 877, 919, 967, 991, 1031, 1087, 1153, 1171, 1201, 1217, 1297, 1409, 1433, 1447, 1471, 1499, 1523, 1597, 1621

Offset: 1

Alois P. Heinz, Mar 15 2020

nonn

			31 is a term: 31 -> 11 -> 5 -> 3 -> 2 -> 1, five (a prime number of) steps "->" = pi = A000720.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
N. Fernandez, An order of primeness, F(p)
N. Fernandez, An order of primeness [cached copy, included with permission of the author]

Cf. A000040, A000720, A049076, A078442, A236542, A262275, A333364.

b:= proc(n) option remember;
      `if`(isprime(n), 1+b(numtheory[pi](n)), 0)
    end:
a:= proc(n) option remember; local p;
      p:= `if`(n=1, 1, a(n-1));
      do p:= nextprime(p);
         if isprime(b(p)) then break fi
      od; p
    end:
seq(a(n), n=1..55);

b[n_] := b[n] = If[!PrimeQ[n], 0, 1+b[PrimePi[n]]];
okQ[n_] := PrimeQ[n] && PrimeQ[b[n]];
Select[Range[2000], okQ] (* Jean-François Alcover, May 30 2022 *)

{ p in primes : A078442(p) is prime }.

a(n) = prime(A333364(n)).

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

A049078 Primes prime(k) for which A049076(k) = 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A135044 a(1)=1, then a(c) = p and a(p) = c, where c = T_c(r,k) and p = T_p(r,k), and where T_p contains the primes arranged in rows by the prime index chain and T_c contains the composites arranged in rows by the order of compositeness. See Formula.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A236536 Array T(n,k) read along antidiagonals: the composites of order of compositeness n in row n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A245815 Permutation of natural numbers induced when A245821 is restricted to nonprime numbers: a(n) = A062298(A245821(A018252(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A245816 Permutation of natural numbers induced when A245822 is restricted to nonprime numbers: a(n) = A062298(A245822(A018252(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A333353 Primes p whose order of primeness A078442(p) is prime.

Views

Author

Keywords

Examples