A165418 a(1) = 1. For n >= 2, a(n) = sum a(k), where k is over the distinct values of the substrings in binary n, and where 1 <= k < n.

1, 1, 1, 2, 2, 3, 2, 4, 4, 4, 5, 8, 8, 8, 4, 8, 8, 8, 9, 10, 8, 13, 12, 20, 20, 20, 21, 26, 26, 20, 8, 16, 16, 16, 17, 16, 18, 21, 20, 24, 24, 16, 22, 36, 34, 35, 28, 48, 48, 48, 49, 52, 48, 55, 56, 76, 76, 76, 78, 76, 76, 48, 16, 32, 32, 32, 33, 32, 34, 37, 36, 36, 32, 40, 42, 50, 52

Offset

1,4

Comments

The distinct positive values of the substrings of binary n is row n of table A165416.

a(2^n) = 2^(n-1), for all n >=1.

Links

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

Rémy Sigrist, PARI program for A165418

Example

9 in binary is 1001. The distinct positive integers that occur as substrings in binary 9 are 1, 2 (10 in binary), 4 (100 in binary), and 9 (1001 in binary). So a(9) = a(1)+a(2)+a(4) = 1 + 1 + 2 = 4.

Mathematica

Fold[Function[{a, n}, Append[a, With[{w = IntegerDigits[n, 2]}, Total@ Part[a, Select[Union@ Map[FromDigits[#, 2] &, Apply[Join, Array[Partition[w, #, 1] &, Length@ w]]], Nor[# == 0, # == n] &]]]]], {1}, Range[2, 77]] (* Michael De Vlieger, Dec 31 2017 *)

Prog

(PARI) See Links section.

Crossrefs

A165416, A165417

Sequence in context: A290731 A106289 A332436 * A307797 A233777 A048620

Adjacent sequences: A165415 A165416 A165417 * A165419 A165420 A165421

Keyword

base,nonn

Author

Leroy Quet, Sep 17 2009

Extensions

More terms from Sean A. Irvine, Nov 19 2009

Status

approved