A245450 -id:A245450 - cp's OEIS frontend

A057889 Bijective bit-reverse of n: keep the trailing zeros in the binary expansion of n fixed, but reverse all the digits up to that point.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 12, 11, 14, 15, 16, 17, 18, 25, 20, 21, 26, 29, 24, 19, 22, 27, 28, 23, 30, 31, 32, 33, 34, 49, 36, 41, 50, 57, 40, 37, 42, 53, 52, 45, 58, 61, 48, 35, 38, 51, 44, 43, 54, 59, 56, 39, 46, 55, 60, 47, 62, 63, 64, 65, 66, 97, 68, 81, 98, 113

Offset: 0

Marc LeBrun, Sep 25 2000

The original name was "Bit-reverse of n, including as many leading as trailing zeros." - Antti Karttunen, Dec 25 2024
A permutation of integers consisting only of fixed points and pairs. a(n)=n when n is a binary palindrome (including as many leading as trailing zeros), otherwise a(n)=A003010(n) (i.e. n has no axis of symmetry). A057890 gives the palindromes (fixed points, akin to A006995) while A057891 gives the "antidromes" (pairs). See also A280505.
This is multiplicative in domain GF(2)[X], i.e. with carryless binary arithmetic. A193231 is another such permutation of natural numbers. - Antti Karttunen, Dec 25 2024

			a(6)=6 because 0110 is a palindrome, but a(11)=13 because 1011 reverses into 1101.

N. J. A. Sloane, Table of n, a(n) for n = 0..16384, May 30 2016 [First 8192 terms from _Ivan Neretin_, Jul 09 2015]
Index entries for sequences related to binary expansion of n
Index entries for sequences related to polynomials in ring GF(2)[X]
Index entries for sequences that are permutations of the natural numbers

Cf. A030101, A000265, A006519, A006995, A057890, A057891, A280505, A280508, A331166 [= min(n,a(n))], A366378 [k for which a(k) = k (mod 3)], A369044 [= A014963(a(n))].
Similar permutations for other bases: A263273 (base-3), A264994 (base-4), A264995 (base-5), A264979  (base-9).
Other related (binary) permutations: A056539, A193231.
Compositions of this permutation with other binary (or other base-related) permutations: A264965, A264966, A265329, A265369, A379471, A379472.
Compositions with permutations involving prime factorization: A245450, A245453, A266402, A266404, A293448, A366275, A366276.
Other derived permutations: A246200 [= a(3*n)/3], A266351, A302027, A302028, A345201, A356331, A356332, A356759, A366389.
See also A235027 (which is not a permutation).

Table[FromDigits[Reverse[IntegerDigits[n, 2]], 2]*2^IntegerExponent[n, 2], {n, 71}] (* Ivan Neretin, Jul 09 2015 *)

A030101(n) = if(n<1,0,subst(Polrev(binary(n)),x,2));
A057889(n) = if(!n,n,A030101(n/(2^valuation(n,2))) * (2^valuation(n, 2))); \\ Antti Karttunen, Dec 25 2024

def a(n):
    x = bin(n)[2:]
    y = x[::-1]
    return int(str(int(y))+(len(x) - len(str(int(y))))*'0', 2)
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 11 2017

def A057889(n): return int(bin(n>>(m:=(~n&n-1).bit_length()))[-1:1:-1],2)<Chai Wah Wu, Dec 25 2024

a(n) = A030101(A000265(n)) * A006519(n), with a(0)=0.

Clarified the name with May 30 2016 comment from N. J. A. Sloane, and moved the old name to the comments - Antti Karttunen, Dec 25 2024

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.]

A245704 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.

Original entry on oeis.org

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, 30, 34, 39, 49, 23, 55, 36, 20, 42, 45, 37, 50, 56, 69, 47, 35, 77, 52, 32, 60, 17, 64, 54, 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

Offset: 1

Antti Karttunen, Aug 02 2014

nonn

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.

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

Inverse: A245703.
Cf. A000040, A002808, A007097, A010051, A014580, A091225, A091226, A091230, A091242, A091245.
Similar or related permutations: A245701, A245822, A227413, A091203, A091205, A106443, A106445, A106447, A235042, A244987, A245450.

allocatemem(123456789);
default(primelimit, 2^22)
A091226 = vector(2^22);
A002808(n)={ my(k=-1); while( -n + n += -k + k=primepi(n), ); n}; \\ This function from M. F. Hasler
isA014580(n)=polisirreducible(Pol(binary(n))*Mod(1, 2)); \\ This function from Charles R Greathouse IV
j=0; 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);
A245704(n) = if(1==n, 1, if(isA014580(n), prime(A245704(A091226[n])), A002808(A245704(A091245(n)))));
for(n=1, 10001, write("b245704.txt", n, " ", A245704(n)));

;; With memoization-macro definec.
(definec (A245704 n) (cond ((= 1 n) n) ((= 1 (A091225 n)) (A000040 (A245704 (A091226 n)))) (else (A002808 (A245704 (A091245 n))))))

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))).
As a composition of related permutations:
a(n) = A227413(A245701(n)).
a(n) = A245822(A091205(n)).
Other identities. For all n >= 1, the following holds:
a(A091230(n)) = A007097(n). [Maps iterates of A014580 to the iterates of primes. Permutation A091205 has the same property].
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].

A244987 Self-inverse permutation of natural numbers, A245703-conjugate of Blue code: a(n) = A245704(A193231(A245703(n))).

Original entry on oeis.org

1, 3, 2, 6, 5, 4, 13, 8, 21, 15, 23, 16, 7, 25, 10, 12, 41, 18, 19, 64, 9, 22, 11, 49, 14, 26, 77, 39, 37, 34, 263, 105, 38, 30, 88, 70, 29, 33, 28, 133, 17, 54, 73, 126, 51, 462, 53, 60, 24, 66, 45, 74, 47, 42, 78, 94, 156, 81, 239, 48, 97, 62, 100, 20, 155, 50, 79, 98, 84, 36, 167, 141, 43, 52, 129, 164, 27, 55

Offset: 1

Antti Karttunen, Aug 07 2014

nonn

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

Cf. A000040, A002808, A010051, A193231, A245703, A245704, A234747, A234748, A245450, A245454.

allocatemem(234567890);
default(primelimit, 2^22);
A014580 = vector(2^18);
A091226 = vector(2^22);
A091242 = vector(2^22);
A002808(n)={ my(k=-1); while( -n + n += -k + k=primepi(n), ); n}; \\ This function from M. F. Hasler
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, j++; A091242[j] = n; A091226[n] = A091226[n-1]); n++);
A091245(n) = ((n-A091226[n])-1);
A245703(n) = if(1==n, 1, if(isprime(n), A014580[A245703(primepi(n))], A091242[A245703(n-primepi(n)-1)]));
A245704(n) = if(1==n, 1, if(isA014580(n), prime(A245704(A091226[n])), A002808(A245704(A091245(n)))));
A193231(n) = {my(x='x); subst(lift(Mod(1, 2)*subst(Pol(binary(n), x), x, 1+x)), x, 2)};
A244987(n) = A245704(A193231(A245703(n)));
for(n=1, 10001, write("b244987.txt", n, " ", A244987(n)));

(define (A244987 n) (A245704 (A193231 (A245703 n))))

a(n) = A245704(A193231(A245703(n))).
Other identities. For all n >= 1, the following holds:
A010051(a(n)) = A010051(n). [Maps primes to primes and composites to composites].

A245453 Self-inverse and multiplicative permutation of natural numbers, A235041-conjugate of balanced bit-reverse: a(n) = A235042(A057889(A235041(n))).

Original entry on oeis.org

0, 1, 2, 3, 4, 19, 6, 7, 8, 9, 38, 13, 12, 11, 14, 57, 16, 59, 18, 5, 76, 21, 26, 53, 24, 361, 22, 27, 28, 109, 114, 31, 32, 39, 118, 133, 36, 41, 10, 33, 152, 37, 42, 103, 52, 171, 106, 61, 48, 49, 722, 177, 44, 23, 54, 247, 56, 15, 218, 17, 228, 47, 62, 63, 64

Offset: 0

Antti Karttunen, Aug 07 2014

a(n) has the same prime signature as n: The permutation maps primes to primes, squares to squares, cubes to cubes, and so on. Permutation A234748 shares the same property.

			Example of multiplicativity:
a(5)=19, a(11)=13, a(55) = a(5*11) = a(5) * a(11) = 19*13 = 247.

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

Cf. A057889, A235041, A235042, A234748, A245450, A235027.

(define (A245453 n) (A235042 (A057889 (A235041 n))))

a(n) = A235042(A057889(A235041(n))).

cp's OEIS Frontend

A057889 Bijective bit-reverse of n: keep the trailing zeros in the binary expansion of n fixed, but reverse all the digits up to that point.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Scheme

Formula

A244987 Self-inverse permutation of natural numbers, A245703-conjugate of Blue code: a(n) = A245704(A193231(A245703(n))).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A245453 Self-inverse and multiplicative permutation of natural numbers, A235041-conjugate of balanced bit-reverse: a(n) = A235042(A057889(A235041(n))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Scheme

Formula