A080542 In binary representation: keep the first digit and rotate right the others.

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

Offset: 1

Author

Reinhard Zumkeller, Feb 20 2003

Keywords

• nonn
• base

Comments

Permutation of natural numbers with inverse = A080541: A080541(a(n)) = a(A080541(n)) = n;

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) = A080541(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

Examples

			a(20) = a('10100') = '10010' = 18.
a(25) = a('11001') = '11100' = 28.
		

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

Crossrefs

Inverse: A080541.

Cf. A000031, A000035, A000523, A004526, A007088, A053644, A053645, A054429, A072376, A080414, A080544, A256999, A257250.

The set of permutations {A059893, A080541, A080542} generates an infinite dihedral group.

Programs

Mathematica

kfd[n_]:=Module[{a,b},{a,b}=TakeDrop[IntegerDigits[n,2],1];FromDigits[ Join[a,RotateRight[b]],2]]; Array[kfd,80] (* The program uses the TakeDrop function from Mathematica version 10 *) (* Harvey P. Dale, Feb 12 2016 *)

Python

def A080542(n): return (1+(n&1))*(1<>1) if n > 1 else n # Chai Wah Wu, Jan 22 2023

R

nmax <- 31 # by choice
a <- 1:3
for(n in 1:nmax) for(k in 0:3)
a[4*n + k] = 2*a[2*n + (k == 1 | k == 3)] + (k == 2 | k == 3)
a
# Yosu Yurramendi, Sep 05 2020

Scheme

(define (A080542 n) (if (< n 2) n (+ (A053644 n) (+ (* (A000035 n) (A072376 n)) (A004526 (A053645 n))))))  ;; Antti Karttunen, May 16 2015

Formula

a(n) = 2^log2(n) + floor((n-2^log2(n))/2) + (n mod 2)*2^(log2(n)-1), where log2(n) is the integer part of base-2 logarithm.

From Antti Karttunen, May 16 2015: (Start)

a(1) = 1; for n > 1, a(n) = A053644(n) + (A000035(n)*A072376(n)) + A004526(A053645(n)). [Essentially the same formula but represented with A-numbers.]

Other identities. For all n >= 1:

a(n) = A059893(A080541(A059893(n))).

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

(End)