A236854 Self-inverse permutation of natural numbers: a(1)=1, then a(p_n)=c_{a(n)}, a(c_n)=p_{a(n)}, where p_n = n-th prime, c_n = n-th composite.

1, 4, 9, 2, 16, 7, 6, 23, 3, 53, 26, 17, 14, 13, 83, 5, 12, 241, 35, 101, 59, 43, 8, 41, 431, 11, 37, 1523, 75, 149, 39, 547, 277, 191, 19, 179, 27, 3001, 31, 157, 24, 12763, 22, 379, 859, 167, 114, 3943, 1787, 1153, 67, 1063, 10, 103, 27457, 127, 919, 89, 21

Offset

1,2

Comments

Shares with A026239 the property that the prime-positions 2, 3, 5, 7, ... contain only composite values and the composite-positions 4, 6, 8, 9, ..., etc. contain only prime values. However, instead of placing terms in those subsets in monotone order this sequence recursively permutes the order of both subsets with the emerging permutation itself, so this is a kind of "deep" variant of A026239. Alternatively, this can be viewed as yet another "entanglement permutation", where two pairs of complementary subsets of natural numbers are entangled with each other. In this case a complementary pair primes/composites (A000040/A002808) is entangled with a complementary pair composites/primes.

Maps A006508 to A007097 and vice versa.

Links

Chai Wah Wu, Table of n, a(n) for n = 1..735 (n = 1..150 from Alois P. Heinz)

Index entries for sequences that are permutations of the natural numbers

Formula

a(1)=1, a(p_i) = A002808(a(i)) for primes with index i, a(c_j) = A000040(a(j)) for composites with index j (where 4 has index 1, 6 has index 2, and so on).

Example

a(5)=c(a(3))=c(9)=16, because 5=prime(3), and the 9th composite number is c(9)=16.
Thus a(10)=prime(a(5))=prime(16)=53 (since 10 is the 5th composite), a(18)=prime(a(10))=prime(53)=241 (since 18 is the 10th composite), a(28)=prime(a(18))=prime(241)=1523.
A significant record value is a(198) = prime(a(152)) = prime(563167303) since 198=c(152); a(152)=prime(a(115)) since 152=c(115); a(115)=prime(a(84)); a(84)=prime(a(60)); a(60)=prime(a(42)); a(42)=prime(a(28)).

Mathematica

terms = 150; cc = Select[Range[4, 2 terms^2(*empirical*)], CompositeQ]; compositePi[k_?CompositeQ] := FirstPosition[cc, k][[1]]; a[1] = 1; a[p_?PrimeQ] := a[p] = cc[[a[PrimePi[p]]]]; a[k_] := a[k] = Prime[a[ compositePi[k]]]; Array[a, terms] (* Jean-François Alcover, Mar 02 2016 *)

Prog

(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library)
(definec (A236854 n) (cond ((< n 2) n) ((prime? n) (A002808 (A236854 (A000720 n)))) (else (A000040 (A236854 (A065855 n))))))
(PARI) A236854(n)={if(isprime(n), A002808(A236854(primepi(n))), n==1&&return(1); prime(A236854(n-primepi(n)-1)))} \\ without memoization: not much slower. - M. F. Hasler, Feb 03 2014
(PARI) a236854=vector(999); a236854[1]=1; A236854(n)={a236854[n]&&return(a236854[n]); a236854[n]=if(isprime(n), A002808(A236854(primepi(n))), prime(A236854(n-primepi(n)-1)))} \\ Version with memoization. - M. F. Hasler, Feb 03 2014
(Python)
from sympy import primepi, prime, isprime
def a002808(n):
    m, k = n, primepi(n) + 1 + n
    while m != k: m, k = k, primepi(k) + 1 + n
    return m # this function from Chai Wah Wu
def a(n): return n if n<2 else a002808(a(primepi(n))) if isprime(n) else prime(a(n - primepi(n) - 1))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 07 2017

Crossrefs

Differs from A135044 for the first time at n=8, where A135044(8)=13, while here a(8)=23.

Cf. A026239, A135141/A227413, A006508, A007097, A000040, A002808, A000720, A065855.

Sequence in context: A366908 A114578 A135044 * A235491 A256513 A358916

Adjacent sequences: A236851 A236852 A236853 * A236855 A236856 A236857

Keyword

nonn

Author

Antti Karttunen, Feb 01 2014, based on Katarzyna Matylla's original but misplaced definition for A135044 from Feb 11 2008.

Extensions

Values double-checked by M. F. Hasler, Feb 03 2014

Status

approved