A302439 a(n) is the number of ways of writing the binary expansion of n as a concatenation of nonempty aperiodic substrings (i.e., substrings that are not the concatenation of 2 or more equal parts).

1, 1, 2, 1, 3, 3, 3, 1, 4, 4, 6, 4, 5, 5, 4, 1, 5, 5, 10, 5, 10, 9, 11, 5, 7, 7, 10, 7, 7, 7, 5, 1, 6, 6, 14, 6, 16, 15, 16, 6, 14, 14, 19, 13, 18, 17, 16, 6, 9, 9, 17, 9, 16, 15, 17, 9, 10, 10, 14, 10, 9, 9, 6, 1, 7, 7, 18, 7, 24, 21, 21, 7, 23, 22, 32, 22

Offset

0,3

Comments

Leading zeros in the binary expansion of n are ignored.

The value a(0) = 1 corresponds to the empty concatenation.

See A301453 for similar sequences.

For some odd o = 2*k + 1, is there some k such that for all e > k, a(o * 2^e) = a(o + 2^(e - 1)) + c for some c? - David A. Corneth, Apr 15 2018

Links

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

Index entries for sequences related to binary expansion of n

Formula

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

a(2^n) = n + 1 for any n >= 0.

From David A. Corneth, Apr 15 2018: (Start)

Is a(2^n + i) >= a(2^n) for 0 <= i <= 2^n - 2?

What is the least k(n) such that

a(2^n + i) <= a(2^n + k(n)) for 1 <= i <= 2^n - 2? (End)

Example

For n = 20: the binary expansion of 20, "10100", can be split in 10 ways into aperiodic substrings:
- (10100),
- (101)(0)(0),
- (10)(100),
- (10)(10)(0),
- (10)(1)(0)(0),
- (1)(0100),
- (1)(010)(0),
- (1)(0)(100),
- (1)(0)(10)(0),
- (1)(0)(1)(0)(0).
Hence a(20) = 10.

Prog

(PARI) a(n) = if (n==0, return (1), my (v=0); for (w=1, #binary(n), my (ok=1); fordiv (w, d, if (d<w && #Set(digits(n % (2^w), 2^d))<=1, ok = 0; break)); if (ok, v += a(n \ (2^w)))); return (v))

Crossrefs

Cf. A301453.

Sequence in context: A302291 A300510 A361079 * A331855 A178244 A227532

Adjacent sequences: A302436 A302437 A302438 * A302440 A302441 A302442

Keyword

nonn,base

Author

Rémy Sigrist, Apr 08 2018

Status

approved