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

Author

Leroy Quet, Sep 17 2009

Keywords

• base
• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

A165416, A165417

Programs

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 *)

PARI

See Links section.

Extensions

More terms from Sean A. Irvine, Nov 19 2009