A053644 -id:A053644 - cp's OEIS frontend

A122155 Simple involution of natural numbers: List each block of (2^k)-1 numbers (from (2^k)+1 to 2^(k+1) - 1) in reverse order and fix the powers of 2.

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

Offset: 0

Antti Karttunen, Aug 25 2006

nonn

From Kevin Ryde, Dec 29 2020: (Start)
a(n) is n with an 0<->1 complement applied to each bit between, but not including, the most significant and least significant 1-bits.  Dijkstra uses this form and calls the complemented bits the "internal" digits.
The fixed points a(n)=n are n=0 and n=A029744.  These are n=2^k by construction, and the middle of each reversed block is n=3*2^k.  In terms of bit complement, these n have nothing between their highest and lowest 1-bits.
(End)

			From _Kevin Ryde_, Dec 29 2020: (Start)
  n    = 4, 5, 6, 7, 8
  a(n) = 4, 7, 6, 5, 8  between powers of 2
             <----      block reverse
Or a single term by bits,
  n    = 236 = binary 11101100
  a(n) = 148 = binary 10010100  complement between
                       ^^^^     high and low 1's
(End)

Michael De Vlieger, Table of n, a(n) for n = 0..16384
Edsger W. Dijkstra, More about the function ``fusc'', 1976. Reprinted in Edsger W. Dijkstra, Selected Writings on Computing, Springer-Verlag, 1982, pages 230-232.
Index entries for sequences that are permutations of the natural numbers

Cf. A054429, A122198, A122199.

Cf. A029744 (fixed points), A334045 (complement high/low 1's too), A057889 (bit reversal).

Array[(1 + Boole[#1 - #2 != 0]) #2 - #1 + #2 & @@ {#, 2^(IntegerLength[#, 2] - 1)} &, 69] (* Michael De Vlieger, Jan 01 2023 *)

a(n) = bitxor(n,if(n,max(0, 1<Kevin Ryde, Dec 29 2020

def A122155(n): return int(('1'if (m:=len(s:=bin(n)[2:])-(n&-n).bit_length())>0 else '')+''.join(str(int(d)^1) for d in s[1:m])+s[m:],2) if n else 0 # Chai Wah Wu, May 19 2023

def A122155(n): return n^((1<Chai Wah Wu, Mar 10 2025

maxblock <- 5 # by choice
a <- 1
for(m in 1:maxblock){
                      a[2^m    ] <- 2^m
  for(k in 1:(2^m-1)) a[2^m + k] <- 2^(m+1) - k
}
(a <- c(0,a))
# Yosu Yurramendi, Mar 18 2021

(define (A122155 n) (cond ((< n 1) n) ((pow2? n) n) (else (- (* 2 (A053644 n)) (A053645 n)))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))

a(0) = 0; if n=2^k, a(n) = n; if n=2^k + i (with i > 0 and i < 2^k) a(n) = 2^(k+1) - i = 2*A053644(n) - A053645(n).

A002487(a(n)) = A002487(n), n >= 0 [Dijkstra]. - Yosu Yurramendi, Mar 18 2021

A344834 Square array T(n, k), n, k >= 0, read by antidiagonals; T(n, k) = (n * 2^max(0, w(k)-w(n))) AND (k * 2^max(0, w(n)-w(k))) (where AND denotes the bitwise AND operator and w = A070939).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 2, 2, 2, 0, 0, 4, 2, 2, 4, 0, 0, 4, 4, 3, 4, 4, 0, 0, 4, 4, 4, 4, 4, 4, 0, 0, 4, 4, 4, 4, 4, 4, 4, 0, 0, 8, 4, 6, 4, 4, 6, 4, 8, 0, 0, 8, 8, 6, 4, 5, 4, 6, 8, 8, 0, 0, 8, 8, 8, 4, 4, 4, 4, 8, 8, 8, 0, 0, 8, 8, 8, 8, 5, 6, 5, 8, 8, 8, 8, 0

Offset: 0

Rémy Sigrist, May 29 2021

In other words, we right pad the binary expansion of the lesser of n and k with zeros (provided it is positive) so that both numbers have the same number of binary digits, and then apply the bitwise AND operator.

			Array T(n, k) begins:
  n\k|  0  1  2   3  4   5   6   7  8  9  10  11  12  13  14  15
  ---+----------------------------------------------------------
    0|  0  0  0   0  0   0   0   0  0  0   0   0   0   0   0   0
    1|  0  1  2   2  4   4   4   4  8  8   8   8   8   8   8   8
    2|  0  2  2   2  4   4   4   4  8  8   8   8   8   8   8   8
    3|  0  2  2   3  4   4   6   6  8  8   8   8  12  12  12  12
    4|  0  4  4   4  4   4   4   4  8  8   8   8   8   8   8   8
    5|  0  4  4   4  4   5   4   5  8  8  10  10   8   8  10  10
    6|  0  4  4   6  4   4   6   6  8  8   8   8  12  12  12  12
    7|  0  4  4   6  4   5   6   7  8  8  10  10  12  12  14  14
    8|  0  8  8   8  8   8   8   8  8  8   8   8   8   8   8   8
    9|  0  8  8   8  8   8   8   8  8  9   8   9   8   9   8   9
   10|  0  8  8   8  8  10   8  10  8  8  10  10   8   8  10  10
   11|  0  8  8   8  8  10   8  10  8  9  10  11   8   9  10  11
   12|  0  8  8  12  8   8  12  12  8  8   8   8  12  12  12  12
   13|  0  8  8  12  8   8  12  12  8  9   8   9  12  13  12  13
   14|  0  8  8  12  8  10  12  14  8  8  10  10  12  12  14  14
   15|  0  8  8  12  8  10  12  14  8  9  10  11  12  13  14  15

Rémy Sigrist, Table of n, a(n) for n = 0..10010
Rémy Sigrist, Colored representation of the table for n, k < 2^10

Cf. A004198, A053644, A070939.

Cf. A344835 (OR), A344836 (XOR), A344837 (min), A344838 (max), A344839 (absolute difference).

T(n,k,op=bitand,w=m->#binary(m)) = { op(n*2^max(0, w(k)-w(n)), k*2^max(0, w(n)-w(k))) }

T(n, k) = T(k, n).
T(m, T(n, k)) = T(T(m, n), k).
T(n, n) = n.
T(n, 0) = n.
T(n, 1) = A053644(n).

A344837 Square array T(n, k), n, k >= 0, read by antidiagonals; T(n, k) = min(n * 2^max(0, w(k)-w(n)), k * 2^max(0, w(n)-w(k))) (where w = A070939).

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 2, 2, 2, 0, 0, 4, 2, 2, 4, 0, 0, 4, 4, 3, 4, 4, 0, 0, 4, 4, 4, 4, 4, 4, 0, 0, 4, 4, 5, 4, 5, 4, 4, 0, 0, 8, 4, 6, 4, 4, 6, 4, 8, 0, 0, 8, 8, 6, 4, 5, 4, 6, 8, 8, 0, 0, 8, 8, 8, 4, 5, 5, 4, 8, 8, 8, 0, 0, 8, 8, 9, 8, 5, 6, 5, 8, 9, 8, 8, 0

Offset: 0

Rémy Sigrist, May 29 2021

In other words, we right pad the binary expansion of the lesser of n and k with zeros (provided it is positive) so that both numbers have the same number of binary digits, and then take the least value.

			Array T(n, k) begins:
  n\k|  0  1  2   3  4   5   6   7  8  9  10  11  12  13  14  15
  ---+----------------------------------------------------------
    0|  0  0  0   0  0   0   0   0  0  0   0   0   0   0   0   0
    1|  0  1  2   2  4   4   4   4  8  8   8   8   8   8   8   8
    2|  0  2  2   2  4   4   4   4  8  8   8   8   8   8   8   8
    3|  0  2  2   3  4   5   6   6  8  9  10  11  12  12  12  12
    4|  0  4  4   4  4   4   4   4  8  8   8   8   8   8   8   8
    5|  0  4  4   5  4   5   5   5  8  9  10  10  10  10  10  10
    6|  0  4  4   6  4   5   6   6  8  9  10  11  12  12  12  12
    7|  0  4  4   6  4   5   6   7  8  9  10  11  12  13  14  14
    8|  0  8  8   8  8   8   8   8  8  8   8   8   8   8   8   8
    9|  0  8  8   9  8   9   9   9  8  9   9   9   9   9   9   9
   10|  0  8  8  10  8  10  10  10  8  9  10  10  10  10  10  10
   11|  0  8  8  11  8  10  11  11  8  9  10  11  11  11  11  11
   12|  0  8  8  12  8  10  12  12  8  9  10  11  12  12  12  12
   13|  0  8  8  12  8  10  12  13  8  9  10  11  12  13  13  13
   14|  0  8  8  12  8  10  12  14  8  9  10  11  12  13  14  14
   15|  0  8  8  12  8  10  12  14  8  9  10  11  12  13  14  15

Rémy Sigrist, Table of n, a(n) for n = 0..10010
Rémy Sigrist, Colored representation of the table for n, k < 2^10

Cf. A003983, A053644, A070939.

Cf. A344834 (AND), A344835 (OR), A344836 (XOR), A344838 (max), A344839 (absolute difference).

T(n, k, op=min, w=m->#binary(m)) = { op(n*2^max(0, w(k)-w(n)), k*2^max(0, w(n)-w(k))) }

T(n, k) = T(k, n).
T(m, T(n, k)) = T(T(m, n), k).
T(n, n) = n.
T(n, 0) = 0.
T(n, 1) = A053644(n).

A209640 Global ranking function for restricted totally balanced binary strings given in A209641.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5, 0, 6, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Antti Karttunen, Mar 24 2012

nonn

The given Scheme-program implements a ranking function for the terms of A209641, using Khayyam's triangle A007318.

			a(12)=3, as 12 occurs as the 3rd term (zero-based) in A209641.
a(14)=0, as 14 doesn't occur in A209641.

This is an inverse function for A209641 in the sense that a(A209641(n)) = n for all n. The beginning of sequence coincides with A080300, because A209641 is a subsequence of A014486. Used to compute the permutation A209861.

(define (A209640 n) (if (or (zero? n) (not (member_of_A209641? n))) 0 (let* ((w (/ (binwidth n) 2))) (let loop ((rank 0) (row 1) (u (- w 1)) (n (- n (A053644 n))) (i (/ (A053644 n) 2)) (first_0_found? #f)) (cond ((or (zero? row) (zero? u) (zero? n)) (+ (expt 2 (-1+ w)) rank)) ((> i n) (loop rank (- row 1) u n (/ i 2) #t)) (else (loop (+ rank (if first_0_found? (A007318tr (- (+ row u) 1) (- row 1)) (A007318tr (- w 1) (- row 1)))) (+ row 1) (- u 1) (- n i) (/ i 2) first_0_found?)))))))
(define (binwidth n) (let loop ((n n) (i 0)) (if (zero? n) i (loop (floor->exact (/ n 2)) (1+ i)))))

A300725 Möbius transform of A053645(n), distance to the largest power of 2 less than or equal to n.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 3, 0, 0, 1, 3, 2, 5, 3, 5, 0, 1, 0, 3, 2, 1, 3, 7, 4, 8, 5, 10, 6, 13, 5, 15, 0, -3, 1, -1, 0, 5, 3, 1, 4, 9, 1, 11, 6, 6, 7, 15, 8, 14, 8, 17, 10, 21, 10, 19, 12, 21, 13, 27, 10, 29, 15, 26, 0, -5, -3, 3, 2, -3, -1, 7, 0, 9, 5, -4, 6, 7, 1, 15, 8, 6, 9, 19, 2, 19, 11, 9, 12, 25, 6, 19, 14, 13, 15, 27

Offset: 1

Antti Karttunen, Mar 11 2018

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

Cf. A000010, A008683, A053644, A053645, A297111, A297115, A300723, A300724.

With[{s = Array[# - 2^Floor@ Log2@ # &, 95]}, Table[DivisorSum[n, MoebiusMu[n/#] s[[#]] &], {n, Length@ s}]] (* Michael De Vlieger, Mar 13 2018 *)

A053644(n) = { my(k=1); while(k<=n, k<<=1); (k>>1); }; \\ From A053644
A053645(n) = (n-A053644(n));
A300725(n) = sumdiv(n,d,moebius(n/d)*A053645(d));

a(n) = Sum_{d|n} A008683(n/d)*A053645(d).

a(n) + A300724(n) = A000010(n).

A364295 Numbers k such that A292943(k) = A292944(k).

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 45, 48, 64, 72, 90, 96, 128, 144, 165, 180, 189, 192, 256, 288, 330, 360, 378, 384, 512, 576, 660, 720, 756, 768, 1024, 1152, 1320, 1440, 1512, 1536, 2048, 2304, 2640, 2880, 3024, 3072, 4096, 4608, 5280, 5760, 6048, 6144, 8192, 9216, 10560, 11520, 12096, 12288, 16384

Offset: 1

Antti Karttunen, Jul 26 2023

nonn

If n is present, then 2*n is also present, and vice versa.

A007283 is included as a subsequence, because it gives the known fixed points of map n -> A163511(n).

Cf. A163511, A243071, A292943, A292944.
Subsequences: A000079, A007283, A029744, A364296 (odd terms).
Cf. also A364494, A364496.

A004754(n) = (n+(1<<(#binary(n)-1)));
A053644(n) = { my(k=1); while(k<=n, k<<=1); (k>>1); };
A292272(n) = (n - bitand(n,n\2));
A292944(n) = (A292272(A004754(n)) - 2*A053644(n));
A054429(n) = ((3<<#binary(n\2))-n-1);
A156552(n) = { my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A243071(n) = if(n<=2, n-1, A054429(A156552(n)));
A292943(n) = A292944(A243071(n));
isA364295(n) = (A292943(n)==A292944(n));

A366260 Doudna sequence permuted by May code: a(n) = A005940(1+A303767(n)).

Original entry on oeis.org

1, 2, 4, 3, 9, 5, 6, 8, 16, 7, 10, 12, 15, 27, 25, 18, 54, 11, 14, 20, 21, 45, 35, 30, 24, 32, 49, 50, 36, 75, 81, 125, 625, 13, 22, 28, 33, 63, 55, 42, 40, 48, 77, 70, 60, 105, 135, 175, 90, 162, 121, 98, 100, 147, 225, 245, 150, 72, 64, 343, 250, 108, 375, 243, 729, 17, 26, 44, 39, 99, 65, 66, 56, 80, 91, 110

Offset: 0

Antti Karttunen, Oct 05 2023

nonn

Cf. A005940, A303767, A366261, A366262.

Cf. also A243353, A366263.

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t };
A209229(n) = (n && !bitand(n,n-1));
A053644(n) = { my(k=1); while(k<=n, k<<=1); (k>>1); }; \\ From A053644
A303767(n) = if(!n,n,if(A209229(n),n+A303767(n-1),A053644(n)+A303767(n-A053644(n)-1)));
A366260(n) = A005940(1+A303767(n));

A063915 G.f.: (1 + Sum_{ i >= 0 } 2^i*x^(2^(i+1)-1)) / (1-x)^2.

Original entry on oeis.org

1, 3, 5, 9, 13, 17, 21, 29, 37, 45, 53, 61, 69, 77, 85, 101, 117, 133, 149, 165, 181, 197, 213, 229, 245, 261, 277, 293, 309, 325, 341, 373, 405, 437, 469, 501, 533, 565, 597, 629, 661, 693, 725, 757, 789, 821, 853, 885, 917, 949, 981, 1013, 1045, 1077, 1109

Offset: 0

N. J. A. Sloane, Sep 01 2001

First differences are in A053644. Partial sums are in A063916.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 34, 37, 41.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A000523, A053644, A063916.

a:= proc(n) option remember; `if`(n<0, 0, 1+
     (t-> 2*(a(floor(t))+a(ceil(t))))(n/2-1))
    end:
seq(a(n), n=0..55);  # Alois P. Heinz, Jul 10 2019

b[n_] := b[n] = If[EvenQ[n], 2 b[n/2] + 2 b[n/2-1] + 1, 4 b[(n-1)/2] + 1];
b[1] = 1; b[2] = 3;
a[n_] := b[n+1];
a /@ Range[0, 55] (* Jean-François Alcover, Nov 02 2020 *)

a(n) = n+=2; my(k=logint(n,2)); n<Kevin Ryde, Nov 27 2020

a(n) = b(n+1), with b(2n) = 2*b(n)+2*b(n-1)+1, b(2n+1) = 4*b(n)+1.

a(n) = (n+2)*2^k - (2*4^k + 1)/3 where k = floor(log_2(n+2)) = A000523(n+2). - Kevin Ryde, Nov 27 2020

More terms from Ralf Stephan, Sep 15 2003

A092323 2^m - 1 appears 2^m times.

Original entry on oeis.org

0, 1, 1, 3, 3, 3, 3, 7, 7, 7, 7, 7, 7, 7, 7, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63

Offset: 1

Reinhard Zumkeller, Feb 15 2004

Or, write n in binary and change the most significant bit to 0 and all other bits to 1.
a(n) = A053644(n) - 1 = A003817(n) - A053644(n).
a(n) = floor(A003817(n-1)/2). [Reinhard Zumkeller, Jul 18 2010]

Cf. A003817, A053644.

[n le 2 select n-1 else Self(Floor(n/2))*2+1: n in [1..100]]; // Vincenzo Librandi, Jun 27 2016

Table[FromDigits[#, 2] &@ Table[1, {IntegerLength[n, 2] - 1}], {n, 80}] (* Michael De Vlieger, Jun 26 2016 *)
Table[Table[2^m-1,2^m],{m,0,6}]//Flatten (* Harvey P. Dale, May 22 2021 *)
Table[PadRight[{},2^m,2^m-1],{m,0,6}]//Flatten (* Harvey P. Dale, Aug 18 2025 *)

a(n) = if n=1 then 0 else a(floor(n/2))*2 + 1.

a(1)=0, a(2n) = 2*a(n)+1, a(2n+1) = a(2n). - Ralf Stephan, Nov 18 2010

A092754 a(1)=1, a(2n)=2a(n)+1, a(2n+1)=2a(n)+2.

Original entry on oeis.org

1, 3, 4, 7, 8, 9, 10, 15, 16, 17, 18, 19, 20, 21, 22, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 127, 128, 129, 130, 131, 132

Offset: 1

Benoit Cloitre, Apr 13 2004

More generally the sequence b(1)=1, b(2n)=2b(n)+x, b(2n+1)=2b(n)+y is given by the formula b(n)=A053644(n)+x*(n-A053644(n))+y*(A053644(n)-1).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A053644 (x=y=0), A054429(x=-1, y=+1), A062050(x=+1, y=-1).
Cf. A206332 (complement).
Cf. A004754.

a092754 n = if n < 2 then n else 2 * a092754 n' + m + 1
            where (n',m) = divMod n 2
a092754_list = map a092754 [1..]
-- Reinhard Zumkeller, May 07 2012

a(n)=if(n<2,1,if(n%2,a(n-1)+1,a(n/2)*2+1))

PARI
```
a(n) = n + 1<Kevin Ryde, Jun 19 2021
```

a(n) = 2^floor(log(n)/log(2)) + n - 1.

a(n) = A004754(n) - 1. - Rémy Sigrist, May 05 2019

cp's OEIS Frontend

A122155 Simple involution of natural numbers: List each block of (2^k)-1 numbers (from (2^k)+1 to 2^(k+1) - 1) in reverse order and fix the powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Python

R

Scheme

Formula

A344834 Square array T(n, k), n, k >= 0, read by antidiagonals; T(n, k) = (n * 2^max(0, w(k)-w(n))) AND (k * 2^max(0, w(n)-w(k))) (where AND denotes the bitwise AND operator and w = A070939).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A344837 Square array T(n, k), n, k >= 0, read by antidiagonals; T(n, k) = min(n * 2^max(0, w(k)-w(n)), k * 2^max(0, w(n)-w(k))) (where w = A070939).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A209640 Global ranking function for restricted totally balanced binary strings given in A209641.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Scheme

A300725 Möbius transform of A053645(n), distance to the largest power of 2 less than or equal to n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A364295 Numbers k such that A292943(k) = A292944(k).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A366260 Doudna sequence permuted by May code: a(n) = A005940(1+A303767(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A063915 G.f.: (1 + Sum_{ i >= 0 } 2^i*x^(2^(i+1)-1)) / (1-x)^2.

Views

Author

Keywords

Comments

Links