login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078822 Number of distinct binary numbers contained as substrings in the binary representation of n. 30
1, 1, 3, 2, 4, 4, 5, 3, 5, 5, 5, 6, 7, 7, 7, 4, 6, 6, 6, 7, 7, 6, 8, 8, 9, 9, 9, 9, 10, 10, 9, 5, 7, 7, 7, 8, 7, 8, 9, 9, 9, 9, 7, 9, 11, 10, 11, 10, 11, 11, 11, 11, 12, 11, 11, 12, 13, 13, 13, 13, 13, 13, 11, 6, 8, 8, 8, 9, 8, 9, 10, 10, 9, 8, 10, 11, 11, 12, 12, 11, 11, 11, 11, 12, 10, 8 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

For n>0: 0<a(2*n)-a(n)<=A070939(n)+1, 0<a(2*n+1)-a(n) < A070939(n). - Reinhard Zumkeller, Mar 07 2008

Row lengths in triangle A119709. - Reinhard Zumkeller, Aug 14 2013

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..16384 (first 1001 terms from Reinhard Zumkeller)

FORMULA

For k>0: a(2^k-2) = 2*(k-1)+1, a(2^k-1) = k, a(2^k) = k+2;

for k>1: a(2^k+1) = k+2;

for k>0: a(2^k-1) = A078824(2^k-1), a(2^k) = A078824(2^k).

EXAMPLE

n=10 -> '1010' contains 5 different binary numbers: '0' (b0bb or bbb0), '1' (1bbb or bb1b), '10' (10bb or bb10), '101' (101b) and '1010' itself, therefore a(10)=5.

MAPLE

a:= n-> (s-> nops({seq(seq(parse(s[i..j]), i=1..j),

        j=1..length(s))}))(""||(convert(n, binary))):

seq(a(n), n=0..85);  # Alois P. Heinz, Jan 20 2021

MATHEMATICA

a[n_] := (id = IntegerDigits[n, 2]; nd = Length[id]; Length[ Union[ Flatten[ Table[ id[[j ;; k]], {j, 1, nd}, {k, j, nd}], 1] //. {0, b__} :> {b}]]); Table[ a[n], {n, 0, 85}] (* Jean-Fran├žois Alcover, Dec 01 2011 *)

PROG

(Haskell)

a078822 = length . a119709_row

import Numeric (showIntAtBase)

-- Reinhard Zumkeller, Aug 13 2013, Sep 14 2011

(PARI) a(n) = {if (n==0, 1, vb = binary(n); vf = []; for (i=1, #vb, for (j=1, #vb - i + 1, pvb = vector(j, k, vb[i+k-1]); f = subst(Pol(pvb), x, 2); vf = Set(concat(vf, f)); ); ); #vf); } \\ Michel Marcus, May 08 2016; corrected Jun 13 2022

(Python)

def a(n): return 1 if n == 0 else len(set(((((2<<l)-1)<<i)&n)>>i for i in range(n.bit_length()) for l in range(n.bit_length()-i)))

print([a(n) for n in range(64)]) # Michael S. Branicky, Jul 28 2022

CROSSREFS

Cf. A078823, A078826, A078824, A007088, A141297, A144623, A144624.

Sequence in context: A322348 A321232 A326015 * A224980 A154392 A069745

Adjacent sequences:  A078819 A078820 A078821 * A078823 A078824 A078825

KEYWORD

nonn,base,nice,look

AUTHOR

Reinhard Zumkeller, Dec 08 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 18:55 EDT 2022. Contains 356949 sequences. (Running on oeis4.)