login
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).
2
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
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
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Apr 08 2018
STATUS
approved