Distinct Substrings In Binary n
Ralf Stephan
ralf at ark.in-berlin.de
Mon Jun 23 20:36:17 CEST 2008
You wrote
> b(n) = number of distinct substrings in the
> binary representation of n that each occur
> multiple times.
>
> 0,0,1,1,1,1,2,2,2,3,1,2,1,2,3
>
> Example: The distinct substrings that occur
> multiple times in 1010 are 0,1, and 10. So
> a(10)=3.
Likewise, if the substrings have their zeroes stripped
we would have
0 0 1 1 1 1 2 1 2 3 2 2 1 2 3 1 2 3 3 4
which differs first at a(8)=1 because 0 00 000 are all 0
and so, only 0 appears more than once. Pari:
a(n)=local(b,l,v);
b=binary(n);
l=length(b);
v=vector(2^l);
for(k=1,l,
for(kk=1,l-k+1,
v[sum(i=1,k,if(b[k-i+kk],2^(i-1)))+1]+=1
)
);
sum(i=1,2^l,if(v[i]>1,1,0))
ralf
More information about the SeqFan
mailing list