A245702 -id:A245702 - cp's OEIS frontend

A135141 a(1)=1, a(p_n)=2a(n), a(c_n)=2a(n)+1, where p_n = n-th prime, c_n = n-th composite number.

1, 2, 4, 3, 8, 5, 6, 9, 7, 17, 16, 11, 10, 13, 19, 15, 12, 35, 18, 33, 23, 21, 14, 27, 39, 31, 25, 71, 34, 37, 32, 67, 47, 43, 29, 55, 22, 79, 63, 51, 20, 143, 26, 69, 75, 65, 38, 135, 95, 87, 59, 111, 30, 45, 159, 127, 103, 41, 24, 287, 70, 53, 139, 151, 131, 77, 36, 271, 191

Offset: 1

Katarzyna Matylla, Feb 13 2008

A permutation of the positive integers, related to A078442.
a(p) is even when p is prime and is divisible by 2^(prime order of p).
From Robert G. Wilson v, Feb 16 2008: (Start)
What is the length of the cycle containing 10? Is it infinite? The cycle begins 10, 17, 12, 11, 16, 15, 19, 18, 35, 29, 34, 43, 26, 31, 32, 67, 36, 55, 159, 1055, 441, 563, 100, 447, 7935, 274726911, 1013992070762272391167, ... Implementation in Mmca: NestList[a(AT)# &, 10, 26] Furthermore, it appears that any non-single-digit number has an infinite cycle.
Records: 1, 2, 4, 8, 9, 17, 19, 35, 39, 71, 79, 143, 159, 287, 319, 575, 639, 1151, 1279, 2303, 2559, 4607, 5119, 9215, 10239, 18431, 20479, 36863, 40959, 73727, 81919, 147455, 163839, 294911, 327679, 589823, 655359, ..., . (End)

			a(20) = 33 = 2*16 + 1 because 20 is 11th composite and a(11)=16. Or, a(20)=33=100001(bin). In other words it is a composite number, its index is a prime number, whose index is a prime....

Robert G. Wilson v, Table of n, a(n) for n = 1..10000
Antti Karttunen, Entanglement Permutations, 2016-2017
Index entries for sequences computed from indices in prime factorization
Index entries for sequences that are permutations of the natural numbers

Cf. A000720, A007814, A010051, A026238, A078442.
Cf. A246346, A246347 (record positions and values).
Cf. A227413 (inverse).
Cf. A071574, A245701, A245702, A245703, A245704, A246377, A236854, A237427 for related and similar permutations.

import Data.List (genericIndex)
a135141 n = genericIndex a135141_list (n-1)
a135141_list = 1 : map f [2..] where
   f x | iprime == 0 = 2 * (a135141 $ a066246 x) + 1
       | otherwise   = 2 * (a135141 iprime)
       where iprime = a049084 x
-- Reinhard Zumkeller, Jan 29 2014

a[1] = 1; a[n_] := If[PrimeQ@n, 2*a[PrimePi[n]], 2*a[n - 1 - PrimePi@n] + 1]; Array[a, 69] (* Robert G. Wilson v, Feb 16 2008 *)

/* Let pc = prime count (which prime it is), cc = composite count: */
pc[1]:0;
cc[1]:0;
pc[2]:1;
cc[4]:1;
pc[n]:=if primep(n) then 1+pc[prev_prime(n)] else 0;
cc[n]:=if primep(n) then 0 else if primep(n-1) then 1+cc[n-2] else 1+cc[n-1];
a[1]:1;
a[n]:=if primep(n) then 2*a[pc[n]] else 1+2*a[cc[n]];

A135141(n) = if(1==n, 1, if(isprime(n), 2*A135141(primepi(n)), 1+(2*A135141(n-primepi(n)-1)))); \\ Antti Karttunen, Dec 09 2019

from sympy import isprime, primepi
def a(n): return 1 if n==1 else 2*a(primepi(n)) if isprime(n) else 2*a(n - 1 - primepi(n)) + 1 # Indranil Ghosh, Jun 11 2017, after Mathematica code

a(n) = 2*A135141((A049084(n))*chip + A066246(n)*(1-chip)) + 1 - chip, where chip = A010051(n). - Reinhard Zumkeller, Jan 29 2014
From Antti Karttunen, Dec 09 2019: (Start)
A007814(a(n)) = A078442(n).
A070939(a(n)) = A246348(n).
A080791(a(n)) = A246370(n).
A054429(a(n)) = A246377(n).
A245702(a(n)) = A245703(n).
a(A245704(n)) = A245701(n). (End)

A245703 Permutation of natural numbers: a(1) = 1, a(p_n) = A014580(a(n)), a(c_n) = A091242(a(n)), where p_n = n-th prime, c_n = n-th composite number and A014580(n) and A091242(n) are binary codes for n-th irreducible and n-th reducible polynomials over GF(2), respectively.

Original entry on oeis.org

1, 2, 3, 4, 7, 5, 11, 6, 8, 12, 25, 9, 13, 17, 10, 14, 47, 18, 19, 34, 15, 20, 31, 24, 16, 21, 62, 26, 55, 27, 137, 45, 22, 28, 42, 33, 37, 23, 29, 79, 59, 35, 87, 71, 36, 166, 41, 58, 30, 38, 54, 44, 61, 49, 32, 39, 99, 76, 319, 46, 91, 108, 89, 48, 200, 53, 97, 75, 40, 50, 203, 70, 67, 57, 78, 64, 43, 51

Offset: 1

Antti Karttunen, Aug 02 2014

All the permutations A091202, A091204, A106442, A106444, A106446, A235041 share the same property that primes (A000040) are mapped bijectively to the binary representations of irreducible GF(2) polynomials (A014580) but while they determine the mapping of composites (A002808) to the corresponding binary codes of reducible polynomials (A091242) by a simple multiplicative rule, this permutation employs index-recursion also in that case.

Inverse: A245704.
Cf. A000040, A002808, A000720, A007097, A010051, A014580, A065855, A091225, A091230, A091242.
Similar or related permutations: A091202, A091204, A106442, A106444, A106446, A235041, A135141, A245701, A245702, A245821, A245822, A244987, A245450.

allocatemem(123456789);
a014580 = vector(2^18);
a091242 = 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++; a014580[i] = n, j++; a091242[j] = n); n++)
A245703(n) = if(1==n, 1, if(isprime(n), a014580[A245703(primepi(n))], a091242[A245703(n-primepi(n)-1)]));
for(n=1, 10001, write("b245703.txt", n, " ", A245703(n)));

;; With memoization-macro definec.
(definec (A245703 n) (cond ((= 1 n) n) ((= 1 (A010051 n)) (A014580 (A245703 (A000720 n)))) (else (A091242 (A245703 (A065855 n))))))

a(1) = 1, a(p_n) = A014580(a(n)) and a(c_n) = A091242(a(n)), where p_n is the n-th prime, A000040(n) and c_n is the n-th composite, A002808(n).
a(1) = 1, after which, if A010051(n) is 1 [i.e. n is prime], then a(n) = A014580(a(A000720(n))), otherwise a(n) = A091242(a(A065855(n))).
As a composition of related permutations:
a(n) = A245702(A135141(n)).
a(n) = A091204(A245821(n)).
Other identities. For all n >= 1, the following holds:
a(A007097(n)) = A091230(n). [Maps iterates of primes to the iterates of A014580. Permutation A091204 has the same property]
A091225(a(n)) = A010051(n). [Maps primes to binary representations of irreducible GF(2) polynomials, A014580, and nonprimes to union of {1} and the binary representations of corresponding reducible polynomials, A091242. The permutations A091202, A091204, A106442, A106444, A106446 and A235041 have the same property.]

A245701 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = 2a(n), a(A091242(n)) = 2a(n)+1, where A014580(n) = binary code for n-th irreducible polynomial over GF(2), A091242(n) = binary code for n-th reducible polynomial over GF(2).

Original entry on oeis.org

1, 2, 4, 3, 5, 9, 8, 7, 11, 19, 6, 17, 10, 15, 23, 39, 13, 35, 18, 21, 31, 47, 79, 27, 16, 71, 37, 43, 63, 95, 14, 159, 55, 33, 143, 75, 22, 87, 127, 191, 38, 29, 319, 111, 67, 287, 12, 151, 45, 175, 255, 383, 77, 59, 34, 639, 223, 135, 20, 575, 30, 25, 303, 91, 351, 511, 46, 767, 155, 119, 69, 1279, 78, 447, 271, 41, 1151, 61, 51

Offset: 1

Antti Karttunen, Aug 02 2014

Antti Karttunen, Table of n, a(n) for n = 1..10001
Antti Karttunen, Entanglement Permutations, 2016-2017
Index entries for sequences related to polynomials in ring GF(2)[X]
Index entries for sequences that are permutations of the natural numbers

Inverse: A245702.
Cf. A000035, A014580, A091242, A091225, A091226, A091245.
Similar entanglement permutations: A135141, A193231, A237427, A243287, A245703, A245704.

allocatemem(123456789);
A091226 = vector(2^22);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
n=2; while((n < 2^22), if(isA014580(n), A091226[n] = A091226[n-1]+1, A091226[n] = A091226[n-1]); n++)
A091245(n) = ((n-A091226[n])-1);
A245701(n) = if(1==n, 1, if(isA014580(n), 2*(A245701(A091226[n])), 1 + 2*(A245701(A091245(n)))));
for(n=1, 10001, write("b245701.txt", n, " ", A245701(n)));

;; With memoizing definec-macro.
(definec (A245701 n) (cond ((= 1 n) n) ((= 1 (A091225 n)) (* 2 (A245701 (A091226 n)))) (else (+ 1 (* 2 (A245701 (A091245 n)))))))

a(1) = 1, and for n > 1, if n is in A014580, a(n) = 2*a(A091226(n)), otherwise a(n) = 1 + 2*a(A091245(n)).
As a composition of related permutations:
a(n) = A135141(A245704(n)).
Other identities:
For all n >= 1, 1 - A000035(a(n)) = A091225(n). [Maps binary representations of irreducible GF(2) polynomials (= A014580) to even numbers and the corresponding representations of reducible polynomials to odd numbers].

A246202 Permutation of natural numbers: a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)), where A091242(n) = binary code for n-th reducible polynomial over GF(2) and A014580(n) = binary code for n-th irreducible polynomial over GF(2).

Original entry on oeis.org

1, 4, 2, 8, 11, 5, 3, 14, 31, 17, 47, 9, 13, 6, 7, 21, 61, 42, 185, 24, 87, 62, 319, 15, 37, 20, 59, 10, 19, 12, 25, 29, 109, 78, 425, 54, 283, 222, 1627, 33, 131, 108, 647, 79, 433, 373, 3053, 22, 67, 49, 229, 28, 103, 76, 415, 16, 41, 27, 97, 18, 55, 34, 137, 39, 167, 134, 859, 98, 563, 494, 4225, 70, 375, 331, 2705, 264, 2011, 1832, 19891, 44

Offset: 1

Antti Karttunen, Aug 19 2014

This sequence can be represented as a binary tree. Each left hand child is produced as A091242(n), and each right hand child as A014580(n), when the parent contains n:
                                     |
                  ...................1...................
                 4                                       2
       8......../ \.......11                   5......../ \........3
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  14       31         17       47          9       13          6       7
21  61   42  185    24  87   62  319     15 37   20  59      10 19   12 25
etc.
Because 2 is the only even term in A014580, it implies that, apart from a(3)=2, all other odd positions contain an odd number. There are also odd numbers in the even bisection, precisely all the terms of A246156 in some order, together with all even numbers larger than 2 that are also there. See also comments in A246201.

Inverse: A246201.
Similar or related permutations: A245702, A246162, A246164, A246204, A237126, A003188, A054429, A193231, A260422, A260426.
Cf. A014580, A091242, A091225, A246156.

allocatemem((2^31)+(2^30));
uplim = (2^25) + (2^24);
v014580 = vector(2^24);
v091242 = vector(uplim);
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
i=0; j=0; n=2; while((n < uplim), if(isA014580(n), i++; v014580[i] = n, j++; v091242[j] = n); n++)
A246202(n) = if(1==n, 1, if(0==(n%2), v091242[A246202(n/2)], v014580[A246202((n-1)/2)]));
for(n=1, 638, write("b246202.txt", n, " ", A246202(n)));
\\ Works with PARI Version 2.7.4. - Antti Karttunen, Jul 25 2015
(Scheme, with memoization-macro definec)
(definec (A246202 n) (cond ((< n 2) n) ((odd? n) (A014580 (A246202 (/ (- n 1) 2)))) (else (A091242 (A246202 (/ n 2))))))

a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)).
As a composition of related permutations:
a(n) = A245702(A054429(n)).
a(n) = A246162(A003188(n)).
a(n) = A193231(A246204(n)).
a(n) = A246164(A193231(n)).
a(n) = A260426(A260422(n)).
Other identities:
For all n > 1, A091225(a(n)) = A000035(n). [After 1, maps even numbers to binary representations of reducible GF(2) polynomials and odd numbers to the corresponding representations of irreducible polynomials, in some order. A246204 has the same property].

A246164 Permutation of natural numbers: a(1) = 1, a(A065621(n)) = A014580(a(n-1)), a(A048724(n)) = A091242(a(n)), where A065621(n) and A048724(n) are the reversing binary representation of n and -n, respectively, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Original entry on oeis.org

1, 2, 4, 11, 8, 5, 3, 7, 6, 9, 13, 17, 47, 31, 14, 61, 21, 42, 185, 24, 87, 319, 62, 12, 25, 19, 10, 59, 20, 15, 37, 229, 49, 22, 67, 76, 415, 103, 28, 18, 55, 137, 34, 41, 16, 27, 97, 78, 425, 109, 29, 1627, 222, 54, 283, 433, 79, 373, 3053, 33, 131, 647, 108, 847, 133, 745, 6943, 44, 193, 1053, 160, 504, 4333, 587, 99

Offset: 1

Antti Karttunen, Aug 19 2014

nonn

This is an instance of entanglement permutation, where the two complementary pairs to be entangled with each other are A065621/A048724 and A014580/A091242 (binary codes for irreducible and reducible polynomials over GF(2)).
The former are themselves permutations of A000069/A001969 (odious and evil numbers), which means that this permutation shares many properties with A246162.
For the comments about the cycle structure, please see A246163.

Inverse: A246163.
Similar or related permutations: A246206, A246202, A193231, A245702, A234025, A246162, A234612, A246204.
Cf. A010060, A014580, A048724, A065620, A065621, A091242, A246159, A246160.

a(1) = 1, and for n > 1, if A010060(n) = 1 [i.e. when n is an odious number], a(n) = A014580(a(A065620(n)-1)), otherwise a(n) = A091242(a(- (A065620(n)))). [A065620 Converts sum of powers of 2 in binary representation of n to an alternating sum].
As a composition of related permutations:
a(n) = A246202(A193231(n)).
a(n) = A245702(A234025(n)).
a(n) = A246162(A234612(n)).
a(n) = A193231(A246204(A193231(n))).
For all n > 1, A091225(a(n)) = A010060(n). [Maps odious numbers to binary representations of irreducible GF(2) polynomials (A014580) and evil numbers to the corresponding representations of reducible polynomials (A091242), in some order. A246162 has the same property].

A091230 Iterates of A014580, starting with a(0) = 1, a(n) = A014580^(n)(1). [Here A014580^(n) means the n-th fold application of A014580].

Original entry on oeis.org

1, 2, 3, 7, 25, 137, 1123, 13103, 204045, 4050293, 99440273

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

Cf. A000079, A007097, A091238, A091204-A091205, A245701-A245702, A245703-A245704.

isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
prev=1; i=0; print1(1, ", "); for(n=1, 123456789, if(isA014580(n), i++; if((i == prev), print1(n, ", "); prev=n))) \\ Antti Karttunen, Aug 02 2014

a(0)=1, a(n) = A014580(a(n-1)). [The defining recurrence].
From Antti Karttunen, Aug 03 2014: (Start)
Other identities. For all n >= 0, the following holds:
A091238(a(n)) = n+1.
a(n) = A091204(A007097(n)) and A091205(a(n)) = A007097(n).
a(n) = A245703(A007097(n)) and A245704(a(n)) = A007097(n).
a(n) = A245702(A000079(n)) and A245701(a(n)) = A000079(n).
(End)

Terms a(8)-a(10) computed by Antti Karttunen, Aug 02 2014

A246162 Permutation of natural numbers: a(1) = 1, a(A000069(n)) = A014580(a(n-1)), a(A001969(n)) = A091242(a(n-1)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Original entry on oeis.org

1, 2, 4, 3, 5, 8, 11, 7, 6, 9, 13, 14, 31, 47, 17, 25, 12, 10, 19, 15, 37, 59, 20, 21, 61, 185, 42, 319, 62, 24, 87, 137, 34, 18, 55, 16, 41, 97, 27, 22, 67, 229, 49, 415, 76, 28, 103, 29, 109, 425, 78, 1627, 222, 54, 283, 3053, 373, 79, 433, 33, 131, 647, 108, 1123, 166, 45, 203, 26, 91, 379, 71, 23

Offset: 1

Antti Karttunen, Aug 17 2014. Erroneous comment corrected Aug 20 2014

nonn

This is an instance of entanglement-permutation, where the two complementary pairs to be entangled with each other are A000069/A001969 (odious and evil numbers) and A014580/A091242 (binary codes for irreducible and reducible polynomials over GF(2)).

Because 3 is the only evil number in A014580, it implies that, apart from a(4)=3, all other odious positions contain an odious number. There are also odious numbers in some of the evil positions, precisely all the terms of A246158 in some order, together with all evil numbers larger than 3. (Permutation A246164 has the same property, except there a(7)=3.) See comments in A246161 for more details how this affects the cycle structure of these permutations.

Inverse: A246161.
Related permutations: A006068, A233279, A234612, A237427, A245702, A246202, A246164.
Cf. A010060, A014580, A091242, A115384, A245710.

a(1) = 1, and for n > 1, if A010060(n) = 1 [i.e. n is one of the odious numbers, A000069], a(n) = A014580(a(A115384(n)-1)), otherwise, a(n) = A091242(a(A245710(n))).
As a composition of related permutations:
a(n) = A245702(A233279(n)).
a(n) = A246202(A006068(n)).
a(n) = A246164(A234612(n)).
For all n > 1, A091225(a(n)) = A010060(n). [Maps odious numbers to binary representations of irreducible GF(2) polynomials (A014580) and evil numbers to the corresponding representations of reducible polynomials (A091242), in some order].

A246206 Permutation of natural numbers: a(1) = 1, if A117966(n) < 0, a(n) = A014580(a(-(A117966(n)))), otherwise a(n) = A091242(a(A117966(n)-1)).

Original entry on oeis.org

1, 2, 5, 9, 4, 13, 3, 37, 49, 64, 6, 10, 16, 81, 8, 20, 15, 351, 229, 451, 59, 11, 7, 41, 19, 73, 92, 114, 27, 36, 48, 140, 12, 53, 17, 24, 33, 69, 86, 107, 44, 170, 18, 63, 22, 410, 28, 524, 76, 271, 101, 14, 23, 687, 529, 895, 253, 25, 97, 213, 145, 333, 3413, 67, 2091, 31, 607, 103, 415, 4531, 47, 131, 87, 193, 55

Offset: 1

Antti Karttunen, Aug 19 2014

nonn

Compare to the formula for A246164. However, instead of reversing binary representation, we employ here balanced ternary enumeration of integers (see A117966).

Inverse: A246205.
Similar or related entanglement permutations: A246164, A245702, A246202, A246208, A246210.
Cf. A014580, A091242, A117966.

a(1) = 1, and for n > 1, if A117966(n) < 0, then a(n) = A014580(a(-(A117966(n)))), otherwise a(n) = A091242(a(A117966(n)-1)).
As a composition of related permutations:
a(n) = A245702(A246208(n)).
a(n) = A246202(A246210(n)).

cp's OEIS Frontend

A135141 a(1)=1, a(p_n)=2*a(n), a(c_n)=2*a(n)+1, where p_n = n-th prime, c_n = n-th composite number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Maxima

PARI

Python

Formula

A245703 Permutation of natural numbers: a(1) = 1, a(p_n) = A014580(a(n)), a(c_n) = A091242(a(n)), where p_n = n-th prime, c_n = n-th composite number and A014580(n) and A091242(n) are binary codes for n-th irreducible and n-th reducible polynomials over GF(2), respectively.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A245701 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = 2*a(n), a(A091242(n)) = 2*a(n)+1, where A014580(n) = binary code for n-th irreducible polynomial over GF(2), A091242(n) = binary code for n-th reducible polynomial over GF(2).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A246202 Permutation of natural numbers: a(1) = 1, a(2n) = A091242(a(n)), a(2n+1) = A014580(a(n)), where A091242(n) = binary code for n-th reducible polynomial over GF(2) and A014580(n) = binary code for n-th irreducible polynomial over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A091230 Iterates of A014580, starting with a(0) = 1, a(n) = A014580^(n)(1). [Here A014580^(n) means the n-th fold application of A014580].

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A246162 Permutation of natural numbers: a(1) = 1, a(A000069(n)) = A014580(a(n-1)), a(A001969(n)) = A091242(a(n-1)), where A000069 and A001969 are the odious and evil numbers, and A014580 resp. A091242 are the binary coded irreducible resp. reducible polynomials over GF(2).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A246206 Permutation of natural numbers: a(1) = 1, if A117966(n) < 0, a(n) = A014580(a(-(A117966(n)))), otherwise a(n) = A091242(a(A117966(n)-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A135141 a(1)=1, a(p_n)=2a(n), a(c_n)=2a(n)+1, where p_n = n-th prime, c_n = n-th composite number.

A245701 Permutation of natural numbers: a(1) = 1, a(A014580(n)) = 2a(n), a(A091242(n)) = 2a(n)+1, where A014580(n) = binary code for n-th irreducible polynomial over GF(2), A091242(n) = binary code for n-th reducible polynomial over GF(2).