A302395 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A302395

a(n) is the number of ways of writing the binary expansion of n as a concatenation of distinct nonempty substrings.

1, 1, 2, 1, 3, 3, 3, 3, 6, 6, 6, 5, 5, 5, 6, 3, 9, 10, 10, 9, 9, 8, 10, 9, 9, 9, 9, 7, 9, 9, 9, 5, 14, 19, 19, 17, 17, 16, 18, 17, 19, 16, 17, 16, 17, 16, 19, 13, 15, 17, 17, 14, 15, 16, 17, 12, 18, 17, 19, 12, 15, 13, 14, 11, 25, 31, 30, 29, 27, 29, 31, 30

(list; graph; refs; listen; history; text; internal format)

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.

LINKS

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

Rémy Sigrist, Scatterplot of the second ordinal transform of the first 750000 terms

Index entries for sequences related to binary expansion of n

FORMULA

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

EXAMPLE

For n = 7: the binary expansion of 7, "111", can be split in 3 ways into distinct nonempty substrings:

- (111),

- (11)(1),

- (1)(11).

Hence a(7) = 3.

For n = 42: the binary expansion of 42, "101010", can be split in 17 ways into distinct nonempty substrings:

- (101010),

- (10101)(0),

- (1010)(10),

- (1010)(1)(0),

- (101)(010),

- (101)(01)(0),

- (101)(0)(10),

- (10)(1010),

- (10)(101)(0),

- (10)(1)(010),

- (10)(1)(01)(0),

- (1)(01010),

- (1)(0101)(0),

- (1)(010)(10),

- (1)(01)(010),

- (1)(01)(0)(10),

- (1)(0)(1010).

Hence a(42) = 17.

PROG

(PARI) a(n{, s=Set()}) = if (n==0, return (1), my (v=0, p=1); while (n, p=(p*2) + (n%2); n\=2; if (!setsearch(s, p), v+=a(n, setunion(s, Set(p))))); return (v))

CROSSREFS

Cf. A032020, A301453.

Sequence in context: A239619 A085599 A299966 * A110425 A174257 A105637

Adjacent sequences: A302392 A302393 A302394 * A302396 A302397 A302398

KEYWORD

nonn,base

AUTHOR

Rémy Sigrist, Apr 07 2018

STATUS

approved