A245704 - OEIS

%I #25 Jun 16 2015 06:17:11

%S 1,2,3,4,6,8,5,9,12,15,7,10,13,16,21,25,14,18,19,22,26,33,38,24,11,28,

%T 30,34,39,49,23,55,36,20,42,45,37,50,56,69,47,35,77,52,32,60,17,64,54,

%U 70,78,94,66,51,29,105,74,48,41,84,53,27,88,76,95,106,73,125,91,72,44,140,97,100,68,58,115,75,40

%N Permutation of natural numbers: a(1) = 1, a(A014580(n)) = A000040(a(n)), a(A091242(n)) = A002808(a(n)), where A000040(n) = n-th prime, A002808(n) = n-th composite number, and A014580(n) and A091242(n) are binary codes for n-th irreducible and n-th reducible polynomial over GF(2), respectively.

%C All the permutations A091203, A091205, A106443, A106445, A106447, A235042 share the same property that the binary representations of irreducible GF(2) polynomials (A014580) are mapped bijectively to the primes (A000040) but while they determine the mapping of corresponding reducible polynomials (A091242) to the composite numbers (A002808) by a simple multiplicative rule, this permutation employs index-recursion also in that case.

%H Antti Karttunen, <a href="/A245704/b245704.txt">Table of n, a(n) for n = 1..10001</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(1) = 1, after which, if A091225(n) is 1 [i.e. n is in A014580], then a(n) = A000040(a(A091226(n))), otherwise a(n) = A002808(a(A091245(n))).

%F As a composition of related permutations:

%F a(n) = A227413(A245701(n)).

%F a(n) = A245822(A091205(n)).

%F Other identities. For all n >= 1, the following holds:

%F a(A091230(n)) = A007097(n). [Maps iterates of A014580 to the iterates of primes. Permutation A091205 has the same property].

%F A010051(a(n)) = A091225(n). [After a(1)=1, maps binary representations of irreducible GF(2) polynomials (= A014580) to primes and the corresponding representations of reducible polynomials to composites].

%o (PARI)

%o allocatemem(123456789);

%o default(primelimit, 2^22)

%o A091226 = vector(2^22);

%o A002808(n)={ my(k=-1); while( -n + n += -k + k=primepi(n), ); n}; \\ This function from _M. F. Hasler_

%o isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from _Charles R Greathouse IV_

%o j=0; n=2; while((n < 2^22), if(isA014580(n), A091226[n] = A091226[n-1]+1, A091226[n] = A091226[n-1]); n++)

%o A091245(n) = ((n-A091226[n])-1);

%o A245704(n) = if(1==n, 1, if(isA014580(n), prime(A245704(A091226[n])), A002808(A245704(A091245(n)))));

%o for(n=1, 10001, write("b245704.txt", n, " ", A245704(n)));

%o (Scheme, with memoization-macro definec)

%o (definec (A245704 n) (cond ((= 1 n) n) ((= 1 (A091225 n)) (A000040 (A245704 (A091226 n)))) (else (A002808 (A245704 (A091245 n))))))

%Y Inverse: A245703.

%Y Cf. A000040, A002808, A007097, A010051, A014580, A091225, A091226, A091230, A091242, A091245.

%Y Similar or related permutations: A245701, A245822, A227413, A091203, A091205, A106443, A106445, A106447, A235042, A244987, A245450.

%K nonn

%O 1,2

%A _Antti Karttunen_, Aug 02 2014