A080541 - OEIS

A080541

In binary representation: keep the first digit and left-rotate the others.

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Permutation of natural numbers: let r(n,0)=n, r(n,k)=a(r(n,k-1)) for k>0, then r(n,floor(log_2(n))) = n and for n>1: r(n,floor(log_2(n))-1) = A080542(n).

Discarding their most significant bit, binary representations of numbers present in each cycle of this permutation form a distinct equivalence class of binary necklaces, thus there are A000031(n) separate cycles in each range [2^n .. (2^(n+1))-1] (for n >= 0) of this permutation. A256999 gives the largest number present in n's cycle. - Antti Karttunen, May 16 2015

LINKS

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

Index entries for sequences related to necklaces

Index entries for sequences that are permutations of the natural numbers

FORMULA

From Antti Karttunen, May 16 2015: (Start)

a(1) = 1; for n > 1, a(n) = A053644(n) bitwise_OR (2*A053645(n) + second_most_significant_bit_of(n)). [Here bitwise_OR is a 2-argument function given by array A003986 and second_most_significant_bit_of gives the second most significant bit (0 or 1) of n larger than 1. See A079944.]

Other identities. For all n >= 1:

a(n) = A059893(A080542(A059893(n))).

a(n) = A054429(a(A054429(n))).

(End)

A080542(a(n)) = a(A080542(n)) = n. [A080542 is the inverse permutation.]

From Robert Israel, May 19 2015: (Start)

Let d = floor(log[2](n)). If n >= 3*2^(d-1) then a(n) = 2*n + 1 - 2^(d+1), otherwise a(n) = 2*n - 2^d.

G.f.: 2*x/(x-1)^2 + Sum_{n>=1} x^(2^n)+(2^n-1)*x^(3*2^(n-1)))/(x-1). (End)

EXAMPLE

a(20)=a('10100')='11000'=24; a(24)=a('11000')='10001'=17.

MAPLE

f:= proc(n) local d;

d:= ilog2(n);

if n >= 3/2*2^d then 2*n+1-2^(d+1) else 2*n - 2^d fi

end proc:

map(f, [$1..100]); # Robert Israel, May 19 2015

PROG

(Scheme)

(define (A080541 n) (if (< n 2) n (A003986bi (A053644 n) (+ (* 2 (A053645 n)) (A079944off2 n))))) ;; A003986bi gives the bitwise OR of its two arguments. See A003986.

;; Where A079944off2 gives the second most significant bit of n. (Cf. A079944):

(define (A079944off2 n) (A000035 (floor->exact (/ n (A072376 n)))))

;; Antti Karttunen, May 16 2015

(R)

maxlevel <- 6 # by choice

a <- 1:3

for(m in 1:maxlevel) for(k in 0:(2^(m-1)-1)){

a[2^(m+1) + 2*k ] = 2*a[2^m + k]

a[2^(m+1) + 2*k + 1] = 2*a[2^m + 2^(m-1) + k]

a[2^(m+1) + 2^m + 2*k ] = 2*a[2^m + k] + 1

a[2^(m+1) + 2^m + 2*k + 1] = 2*a[2^m + 2^(m-1) + k] + 1

}