|
%I #34 Jan 20 2021 16:52:26
%S 1,2,2,3,3,4,3,4,4,4,5,6,6,6,4,5,5,5,6,6,5,7,7,8,8,8,8,9,9,8,5,6,6,6,
%T 7,6,7,8,8,8,8,6,8,10,9,10,9,10,10,10,10,11,10,10,11,12,12,12,12,12,
%U 12,10,6,7,7,7,8,7,8,9,9,8,7,9,10,10,11,11,10,10,10,10,11,9,7,11,11,13,13,12
%N a(n) = number of distinct positive integers represented in binary which are substrings of binary expansion of n.
%C a(n) = A078822(n) if n is of the form 2^k - 1. Otherwise, a(n) = A078822(n) - 1.
%C First occurrence of k: 1, 2, 4, 6, 11, 12, 22, 24, 28, 44, 52, 56, 88, 92, 112, 116, 186, 184, 220, 232, 244, 368, 376, 440, 472, ... (See A292924 for the corresponding sequence. - _Rémy Sigrist_, Mar 09 2018)
%C Last occurrence of k: 2^k - 1.
%C a(n) = sum (A057427(A213629(n,k): k = 1 .. n). - _Reinhard Zumkeller_, Jun 17 2012
%C Length of n-th row in triangle A165416. - _Reinhard Zumkeller_, Jul 17 2015
%H Jeremy Gardiner, <a href="/A122953/b122953.txt">Table of n, a(n) for n = 1..2000</a>
%e Binary 1 = 1, binary 2 = 10, binary 4 = 100 and binary 9 = 1001 are all substrings of binary 9 = 1001. So a(9) = 4.
%p a:= n-> (s-> nops({seq(seq(parse(s[i..j]), i=1..j),
%p j=1..length(s))} minus {0}))(""||(convert(n, binary))):
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Jan 20 2021
%t f[n_] := Length@ Select[ Union[ FromDigits /@ Flatten[ Table[ Partition[ IntegerDigits[n, 2], i, 1], {i, Floor[ Log[2, n] + 1]}], 1]], # > 0 &]; Array[f, 90]
%o (Haskell)
%o a122953 = length . a165416_row
%o -- _Reinhard Zumkeller_, Jul 17 2015, Jan 22 2012
%o (PARI) a(n) = my (v=0, s=0, x=Set()); while (n, my (r=n); while (r, if (r < 100 000, if (bittest(s,r), break, s+=2^r), if (setsearch(x,r), break, x=setunion(x, Set(r)))); v++; r \= 2); n -= 2^(#binary(n)-1)); v \\ _Rémy Sigrist_, Mar 08 2018
%o (Python)
%o def a(n):
%o b = bin(n)[2:]
%o m = len(b)
%o return len(set(int(b[i:j]) for i in range(m) for j in range(i+1,m+1))-{0})
%o print([a(n) for n in range(1, 91)]) # _Michael S. Branicky_, Jan 20 2021
%Y Cf. A078822, A292924.
%Y Cf. A057427, A213629, A165416.
%K nonn,base
%O 1,2
%A _Leroy Quet_, Oct 25 2006
%E More terms from _Robert G. Wilson v_, Nov 01 2006
%E Keyword base added by _Rémy Sigrist_, Mar 08 2018
|
