A341691 a(0) = 0, and for any n > 0, a(n) = n - a(k) where k is the greatest number < n such that n AND a(k) = a(k) (where AND denotes the bitwise AND operator).

0, 1, 2, 1, 4, 1, 2, 5, 8, 1, 2, 9, 4, 9, 10, 5, 16, 1, 2, 17, 4, 17, 18, 5, 8, 17, 18, 9, 20, 9, 10, 21, 32, 1, 2, 33, 4, 33, 34, 5, 8, 33, 34, 9, 36, 9, 10, 37, 16, 33, 34, 17, 36, 17, 18, 37, 40, 17, 18, 41, 20, 41, 42, 21, 64, 1, 2, 65, 4, 65, 66, 5, 8, 65

Offset: 0

Author

Rémy Sigrist, Feb 17 2021

Keywords

• nonn
• base

Comments

This sequence is a binary variant of A341679; here we look for a term whose binary 1's match those of n, there we look for a term that divides n.

Examples

			The first terms, alongside the corresponding value of k, are:
  n   a(n)  k
  --  ----  ---
   0     0  N/A
   1     1    0
   2     2    0
   3     1    2
   4     4    0
   5     1    4
   6     2    4
   7     5    6
   8     8    0
   9     1    8
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8191
• Rémy Sigrist, C program for A341691

Crossrefs

Cf. A006519, A295989, A341679.

Programs

C

See Links section.

Formula

a(n) = n iff n = 0 or n is a power of 2.

a(2*n) = 2*a(n).

Apparently, a(n) = n - a(n - A006519(n)).