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

A340632 a(n) in binary is a run of 1-bits from the most significant 1-bit of n down to the least significant 1-bit of n, inclusive.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 6, 7, 8, 15, 14, 15, 12, 15, 14, 15, 16, 31, 30, 31, 28, 31, 30, 31, 24, 31, 30, 31, 28, 31, 30, 31, 32, 63, 62, 63, 60, 63, 62, 63, 56, 63, 62, 63, 60, 63, 62, 63, 48, 63, 62, 63, 60, 63, 62, 63, 56, 63, 62, 63, 60, 63, 62, 63, 64, 127, 126

Offset: 0

Kevin Ryde, Jan 13 2021

			n    = 172 = binary 10101100;
a(n) = 252 = binary 11111100.

Kevin Ryde, Table of n, a(n) for n = 0..8192

Cf. A023758 (distinct terms).

Cf. A006519, A062383, A142151.

PARI
```
a(n) = if(n, 2<
				
```
Python
```
def a(n): return (1<
				
```

a(n) = A062383(n) - A006519(n) for n>=1.
a(n) = A003817(n) - A135481(n-1).
a(n) = n + A334045(n) (filling in 0-bits, including n=0 by taking A334045(0)=0).
a(n) = A142151(n-1) + 1.
G.f.: x/(1-x) + Sum_{k>=0} 2^k*x^(2^k)*(1/(1-x) - 1/(1-x^(2^(k+1)))).

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

A340632 a(n) in binary is a run of 1-bits from the most significant 1-bit of n down to the least significant 1-bit of n, inclusive.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula