A337225 a(n) is the number of distinct integers k that can be obtained by starting from the binary expansion of n and repeatedly replacing some square XX by X.

1, 1, 1, 2, 2, 1, 2, 3, 3, 2, 2, 2, 4, 2, 3, 4, 4, 3, 3, 4, 4, 2, 3, 3, 6, 4, 4, 4, 6, 3, 4, 5, 5, 4, 4, 6, 6, 4, 5, 6, 6, 4, 3, 4, 6, 3, 4, 4, 8, 6, 6, 8, 8, 4, 6, 6, 9, 6, 6, 6, 8, 4, 5, 6, 6, 5, 5, 8, 8, 6, 7, 9, 9, 6, 5, 8, 10, 6, 7, 8, 8, 6, 5, 8, 6, 3, 5

Offset

0,4

Comments

Leading zeros in binary expansions are ignored.

The least possible k is:

- 0 for n = 0,

- 1 for n = 2^m-1 for some m > 0,

- 2 for n = 2*m for some m > 0,

- 5 otherwise.

Links

Rémy Sigrist, Table of n, a(n) for n = 0..8192

Rémy Sigrist, PARI program for A337225

Index entries for sequences related to binary expansion of n

Formula

a(2^k-1) = k for any k > 0.

Example

The first terms, alongside the binary expansions of n and of the corresponding k's, are:
  n   a(n)  bin(n)  {bin(k)}
  --  ----  ------  -------------------
   0     1       0  {0}
   1     1       1  {1}
   2     1      10  {10}
   3     2      11  {1, 11}
   4     2     100  {10, 100}
   5     1     101  {101}
   6     2     110  {10, 110}
   7     3     111  {1, 11, 111}
   8     3    1000  {10, 100, 1000}
   9     2    1001  {101, 1001}
  10     2    1010  {10, 1010}
  11     2    1011  {101, 1011}
  12     4    1100  {10, 100, 110, 1100}
  13     2    1101  {101, 1101}
  14     3    1110  {10, 110, 1110}
  15     4    1111  {1, 11, 111, 1111}
  16     4   10000  {10, 100, 1000, 10000}

Prog

(PARI) See Links section.

Crossrefs

Cf. A337222.

Sequence in context: A284579 A167489 A256790 * A256478 A356245 A106638

Adjacent sequences: A337222 A337223 A337224 * A337226 A337227 A337228

Keyword

nonn,base

Author

Rémy Sigrist, Aug 19 2020

Status

approved