A196168 In binary representation of n: replace each 0 with 1, and each 1 with 10.

1, 2, 5, 10, 11, 22, 21, 42, 23, 46, 45, 90, 43, 86, 85, 170, 47, 94, 93, 186, 91, 182, 181, 362, 87, 174, 173, 346, 171, 342, 341, 682, 95, 190, 189, 378, 187, 374, 373, 746, 183, 366, 365, 730, 363, 726, 725, 1450, 175, 350, 349, 698, 347, 694, 693, 1386

Offset: 0

Author

Reinhard Zumkeller, Oct 28 2011

Keywords

• nonn

Comments

All terms are numbers with no two adjacent zeros in binary representation, cf. A003754;

a(odd) = even and a(even) = odd;

A023416(a(n)) <= A000120(a(n)), equality iff n = 2^k - 1 for k > 0;

A055010(n+1) = A196168(A000079(n));

A000120(a(n)) = A070939(n);

A023416(a(n)) = A000120(n);

A070939(a(n)) = A070939(n) + A000120(n).

Examples

			n =  7 ->  111 ->  101010 ->  a(7) = 42;
n =  8 -> 1000 ->   10111 ->  a(8) = 23;
n =  9 -> 1001 ->  101110 ->  a(9) = 46;
n = 10 -> 1010 ->  101101 -> a(10) = 45;
n = 11 -> 1011 -> 1011010 -> a(11) = 90;
n = 12 -> 1100 ->  101011 -> a(12) = 43.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A179888, A005614.

Programs

Haskell

import Data.List (unfoldr)
a196168 0 = 1
a196168 n = foldl (\v b -> (2 * v + 1)*(b + 1)) 0 $ reverse $ unfoldr
   (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2) n
   where r v b = (2 * v + 1)*(b+1)

Mathematica

Table[FromDigits[Flatten[IntegerDigits[n,2]/.{{0->1,1->{1,0}}}],2],{n,0,120}] (* Harvey P. Dale, Dec 12 2017 *)

Python

def a(n):
    b = bin(n)[2:]
    return int(b.replace('1', 't').replace('0', '1').replace('t', '10'), 2)
print([a(n) for n in range(56)]) # Michael S. Branicky, Oct 28 2021

Formula

n = Sum_{i=0..1} b(i)*2^i with 0 <= b(i) <= 1, L >= 0, then a(n) = h(0,L) with h(v,i) = if i > L then v, otherwise h((2*v+1)*(b(i)+1),i-1).

From Jeffrey Shallit, Oct 28 2021: (Start)

a(n) satisfies the recurrences:

a(2n+1) = 2*a(2n)

a(4n) = -2*a(n) + 3*a(2n)

a(8n+2) = -8*a(n) + 8*a(2n) + a(4n+2)

a(8n+6) = -4*a(2n) + 5*a(4n+2)

which shows that a(n) is a 2-regular sequence. (End)