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

A266195 Match-making permutation: start with a(1) = 1, then always choose for a(n) the least unused number such that multiplying a(n) by a(n-1) does not produce any carries when performed in base 2.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 7, 9, 10, 12, 16, 11, 17, 13, 32, 14, 18, 20, 19, 33, 15, 34, 22, 64, 21, 24, 36, 28, 65, 23, 66, 25, 40, 35, 72, 42, 48, 37, 68, 26, 128, 27, 129, 29, 130, 30, 132, 31, 256, 38, 80, 49, 73, 56, 136, 41, 96, 69, 144, 67, 84, 97, 137, 112, 145, 134, 160, 50, 133, 76, 161, 100, 257, 39, 258, 43, 260, 44

Offset: 1

Antti Karttunen, Dec 26 2015

More formally: the lexicographically earliest injection of natural numbers such that for any n > 1, A061858(a(n), a(n-1)) = 0; a(1) = 1. By necessity also surjective on N (see below for why), thus a bijection.
Less formally:
In this context we say that two positive natural numbers x and y "match", when they will not produce any carries when multiplied in binary system (see the Examples). The purpose of this sequence is with a simple greedy algorithm to form pairs of natural numbers that "match to each other" according to that criterion. Note that each number after 1 will satisfy the matching condition both with its predecessor and its successor.
For the sake of this discussion, we call a natural number n "dense" if the density of 1-bits in its binary representation (cf., e.g., A265917) is over a certain threshold, whose exact value we leave undefined, but can be subjectively gauged. In contrast, we call a number "ethereal" if its base-2 representation consists mostly of zeros. E.g., 258 = 100000010_2 is clearly one of the "ethereals", while 43 = 101011_2, is definitely on the denser side.
When running the algorithm, we note that after a while, for long stretches of time, it mostly matches "dense" numbers with "ethereal" numbers, like 258 and 43, which occur next to each other in the sequence as a(76) and a(77), and also a(49)=31 and a(50)=256, which are the most dense and most ethereal members of their respective binary sizes (see the Example section).
Also, it should be obvious that each number of the form 2^k (terms of A000079, the "super-ethereals") occur as the first representative of the numbers of the same binary length, and any number of the form (2^k)-1 (A000225, "super-dense") comes as the last of the numbers of binary length k.
No matter how dense some number might look to us, there is always a sufficiently ethereal number with which it can be mated (that is, the algorithm is never stuck, because it can always try the next unused super-ethereal 2^k if everything else fails). Moreover, whenever that next 2^k has appeared, it also always immediately picks up from the backlog of (more or less dense) numbers the least unmatched number so far, which proves that no number is left out, and the sequence is indeed a permutation of the natural numbers.
However, certain numbers intuitively feel to be much better matches to each other, like 10 and 12 (cf. Examples), because they are not so distant from each other. We define "good matches" to be such pairs that the binary length (A070939) of the numbers is equal. As 10 and 12 are both four bits long, they are one instance of such a good match. Note that 10 is also a good match with the immediately preceding number in the sequence, 9 = 1001_2.
Sequence A266197 gives the positions of these good matches, and A265748 & A265749 give their first and second members respectively. It is an open question whether the algorithm generates an infinite number of good matches or not.

			For n=11, we first note that a(10) = 10, and the least unused number after a(1) .. a(10) is 11. Trying to multiply 10 (= 1010_2) and 11 (= 1011_2), in the binary system results in
     1011
  *  1010
  -------
   c1011
  1011
  -------
  1101110 = 110,
and we see that there's a carry-bit (marked c) affecting the result, thus A048720(10,11) < 10*11 and A061858(10,10) > 0, thus we cannot select 11 for a(11).
The next unused number is 12, and indeed, for numbers 10 and 12 (= 1100_2), the binary multiplication results in
     1100
  *  1010
  -------
    1100
  1100
  -------
  1111000 = 120,
which is a clean product without carries (i.e., A061858(10,12) = 0), thus 12 is selected to be a match for 10, and we set a(11) = 12.
For a(49) = 31 (= 11111_2) and a(50) = 256 (= 100000000_2) the multiplication results in
      100000000
    *     11111
  -------------
      100000000
     100000000
    100000000
   100000000
  100000000
  -------------
  1111100000000 = 7936,
and we see that the carryless product is this time obtained almost trivially, as the other number is so much larger and more spacious than the other that they can easily avoid any clashing bits that would produce carries.

Antti Karttunen, Table of n, a(n) for n = 1..2694
Eric Angelini, a(n)*a(n+1) shows at least twice the same digit, Posting on SeqFan-list Dec 21 2015. [Source of inspiration for this sequence.]
Rémy Sigrist, Logarithmic scatterplot of the first 500000 terms
Index entries for sequences that are permutations of the natural numbers

Inverse permutation: A266196.
Cf. A000079, A000225, A048720, A061858, A070939, A265917.
Cf. A266194 (products of these pairs).
Cf. A266197 (indices of good matches),
Cf. A265748, A265749 (give the first and second members of good matches).
Cf. A266186 (when 2^n appears), A266187 (when (2^n)-1 appears).
Cf. A266191, A266351 (similar permutations).
Cf. also A235034, A235035.

A266405 Start with a(1) = 1, then always choose for a(n) the least unused number such that A002487(a(n)a(n-1)) = A002487(a(n)) A002487(a(n-1)), where A002487 is Stern-Brocot sequence.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 6, 9, 10, 14, 16, 11, 17, 13, 12, 18, 15, 26, 24, 23, 19, 32, 20, 28, 34, 22, 27, 33, 29, 31, 25, 45, 49, 36, 30, 52, 48, 35, 64, 21, 69, 42, 128, 37, 256, 38, 46, 66, 54, 41, 83, 82, 108, 44, 39, 88, 68, 56, 40, 55, 65, 47, 130, 59, 96, 51, 192, 70, 72, 60, 104, 71, 80, 57, 63, 61, 126, 98, 90, 50, 62, 58, 124, 100, 121, 127

Offset: 1

Antti Karttunen, Dec 29 2015

nonn

This is a permutation of natural numbers for the same reason that A266195 and A266351 are. If nothing else works for the value of next a(n), then at least the next unused power of 2 will save the sequence from dying, and will also immediately pick up as its succeeding pair the least term not used so far. This follows because A002487(2^m) = 1 and A002487(2^m * n) = A002487(n) for all n and m.

Still, it would be nice to know when 149 will appear in the sequence.

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

Inverse: A266406.
Cf. A002487.
Cf. A266195, A266351, A265405 (for sequences with similar definitions).

A265405 Start with a(1) = 1, then always choose for a(n) the least unused number such that A193231(a(n)a(n-1)) = A193231(a(n)) A193231(a(n-1)), where A193231 is an involution of natural numbers called Blue code.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 16, 7, 17, 8, 15, 32, 12, 10, 18, 20, 19, 256, 9, 14, 34, 48, 40, 50, 33, 60, 257, 11, 97, 258, 13, 101, 209, 65536, 21, 259, 64, 30, 65, 51, 80, 24, 84, 36, 85, 66, 260, 22, 4352, 26, 4368, 28, 4369, 37, 768, 41, 770, 42, 771, 68, 90, 272, 45, 273, 56, 1200, 952, 4096, 23, 4097, 27, 4098, 86, 512, 54

Offset: 1

Antti Karttunen, Dec 29 2015

Does this sequence die after a(144) = 46 ?
No, a(145) = 16777216, but whether the sequence is finished remains open. - Rémy Sigrist, Feb 15 2019
The next unused number of the form 2^2^k is always a valid choice, so this sequence is infinite. - Charlie Neder, Apr 14 2019

Rémy Sigrist, Table of n, a(n) for n = 1..183 (first 144 terms from Antti Karttunen) [More terms needed for b-file.]
Rémy Sigrist, PARI program for A265405

Inverse: A265406.
Cf. A193231.
Cf. A266195, A266351, A266405 (sequences with similar definitions, of which at least the first two are known to be infinite and also bijective).

PARI
```
See Links section.
```

A266194 Products of pairs made by match-making permutation: a(n) = A266195(n) * A266195(n+1).

Original entry on oeis.org

2, 6, 12, 20, 30, 48, 56, 63, 90, 120, 192, 176, 187, 221, 416, 448, 252, 360, 380, 627, 495, 510, 748, 1408, 1344, 504, 864, 1008, 1820, 1495, 1518, 1650, 1000, 1400, 2520, 3024, 2016, 1776, 2516, 1768, 3328, 3456, 3483, 3741, 3770, 3900, 3960, 4092, 7936, 9728, 3040, 3920, 3577, 4088, 7616, 5576, 3936, 6624, 9936, 9648, 5628, 8148, 13289

Offset: 1

Antti Karttunen, Dec 26 2015

Antti Karttunen, Table of n, a(n) for n = 1..2693

Cf. A048720, A057889, A266195, A266351.

a(n) = A266195(n) * A266195(n+1).
a(n) = A048720(A266195(n), A266195(n+1)).
a(n) = A057889(A057889(A266195(n)) * A057889(A266195(n+1))). [See the comment in A266351.]

A379126 a(1) = 1; for n > 1, a(n) is the least number k such that A325567(k) = n, or 0 if no such number exists.

Original entry on oeis.org

1, 4, 9, 8, 35, 18, 49, 16, 135, 70, 33, 36, 65, 98, 225, 32, 527, 270, 133, 140, 651, 66, 161, 72, 775, 130, 837, 196, 899, 450, 961, 64, 2079, 1054, 525, 540, 259, 266, 273, 280, 2583, 1302, 129, 132, 2835, 322, 705, 144, 3087, 1550, 3213, 260, 3339, 1674, 385, 392, 1539, 1798, 3717, 900, 3843, 1922, 3969, 128

Offset: 1

Antti Karttunen, Dec 21 2024

nonn

By definition, sequence is injective (apart from possible 0's) and each a(n) is a multiple of n.

Cf. A048720, A065621, A277320, A325567, A379128 (odd bisection), A379228 [= a(n)/n].

Cf. also A115872, A266195, A266351.

A048720(b, c) = fromdigits(Vec(Pol(binary(b))*Pol(binary(c)))%2, 2);
A065621(n) = bitxor(n-1, n+n-1);
memoA325567 = Map();
A325567(n) = if(1==n,1,my(v); if(mapisdefined(memoA325567,n,&v), v, fordiv(n, d, if((d>1)&&A048720(A065621(n/d), d)==n, v = (n/d); break)); mapput(memoA325567,n,v); (v)));
A379126(n) = for(k=1,oo,if(A325567(k)==n, return(k)));

a(n) = n * A379228(n).

cp's OEIS Frontend

A266352 Inverse permutation to A266351.

Views

Author

Keywords

Links

Crossrefs

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

A266195 Match-making permutation: start with a(1) = 1, then always choose for a(n) the least unused number such that multiplying a(n) by a(n-1) does not produce any carries when performed in base 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A266405 Start with a(1) = 1, then always choose for a(n) the least unused number such that A002487(a(n)*a(n-1)) = A002487(a(n)) * A002487(a(n-1)), where A002487 is Stern-Brocot sequence.

Views

Author

Keywords

Comments

Links

Crossrefs

A265405 Start with a(1) = 1, then always choose for a(n) the least unused number such that A193231(a(n)*a(n-1)) = A193231(a(n)) * A193231(a(n-1)), where A193231 is an involution of natural numbers called Blue code.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A266194 Products of pairs made by match-making permutation: a(n) = A266195(n) * A266195(n+1).

Views

Author

Keywords

Links

Crossrefs

Formula

A379126 a(1) = 1; for n > 1, a(n) is the least number k such that A325567(k) = n, or 0 if no such number exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A266405 Start with a(1) = 1, then always choose for a(n) the least unused number such that A002487(a(n)a(n-1)) = A002487(a(n)) A002487(a(n-1)), where A002487 is Stern-Brocot sequence.

A265405 Start with a(1) = 1, then always choose for a(n) the least unused number such that A193231(a(n)a(n-1)) = A193231(a(n)) A193231(a(n-1)), where A193231 is an involution of natural numbers called Blue code.