# Distinct Substrings In Binary n

Jonathan Post jvospost3 at gmail.com
Mon Jun 23 19:46:51 CEST 2008

```The distinct substrings (including null string) in binary
representation of trinary (A007089  Numbers in base 3):
n      n(base 3) a(n) comment
0               0       2
1		1       2
2		2       2
3		10     4 = #{{},0,1,10}
4		11     3
5		12     4
6		20     4
7		21     4
8		22     3
9		100   6 = #{{},0,1,00,10,100}
10	       101   6
11		102   7 = {{},0,1,2,10,02,102}
12		110   6
13		111   4 = {{},1,11,111}
14		112   6
15		120   7
16		121   6
17		122   6
18		200   6
19		201   7
20		202   6
21		210   7
22		211   6
23		212   6
24		220   6
25		221   6
26		222   4
27		1000  8 = {{},0,1,00,10,000,100,1000} etcetera
28		1001
29		1002
30		1010
31		1011
32		1012
33		1020
34		1021
35		1022
36		1100
37		1101
38		1102
39		1110
40		1111
41		1112
42		1120
43		1121
44		1122
45		1200

lq> From seqfan-owner at ext.jussieu.fr  Mon Jun 23 19:22:52 2008
lq> Date: Mon, 23 Jun 2008 10:21:38 -0700 (PDT)
lq> From: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>
lq> Subject: Distinct Substrings In Binary n
lq> To: seqfan at ext.jussieu.fr
lq> Cc: q1qq2qqq3qqqq at yahoo.com, qq-quet at mindspring.com
lq
lq> I am having a hard time believing that at least
lq> the first sequence listed below isn't in the
lq> database yet. Have I made an error with any of
lq> these sequences? I am waiting to submit them.
lq>
lq> (Including the empty substring does not return a
lq> result for the first sequence, all terms +1,
lq> either.)
lq>
lq> My terminology may be off.
lq>
lq> --
lq>
lq> a(n) = number of distinct (nonempty) substrings
lq> in the binary representation of n. (Leading
lq> zeroes are stripped.)
lq>
lq> Offset = 1.
lq>
lq> 1,3,2,5,5,5,3,7,8,7,...
lq>
lq> For example:
lq> The distinct substrings in binary representation
lq> (1010) of decimal 10:
lq> 0,1,10,01,101,010,1010.

The variant A122953 is in the OEIS. This sequence here continues

1,3,2,5,5,5,3,7,8,7,8,8,8,7,4,9,11,11,12,11,9,11,11,11,12,11,11,11,11,
9,5,11,14,15,16,14,15,16,16,15,15,11,14,16,14,15,14,14,16,16,16,16,14,14,15,
15,16,15,15,14,14,11,6,13,17,19,20,19,20,21,21,19,17,19,21,20,21,21,20,19,

Constructed with the Maple program

A := proc(n)
end:

for n from 1 to 80 do
od:

Richard

```