A175245 Let S be the set of distinct positive integers whose binary representations are substrings in the binary representation of n. a(n) = the number of elements of S that are coprime to all other elements of S.

1, 2, 2, 1, 3, 1, 3, 1, 2, 1, 5, 1, 3, 1, 2, 1, 2, 1, 2, 1, 2, 2, 7, 1, 2, 1, 4, 1, 4, 1, 3, 1, 2, 1, 4, 1, 3, 1, 3, 1, 3, 1, 3, 2, 2, 3, 6, 1, 3, 1, 3, 1, 2, 3, 4, 1, 2, 1, 6, 1, 4, 1, 2, 1, 2, 1, 2, 1, 3, 2, 4, 1, 2, 1, 3, 1, 4, 2, 4, 1, 3, 1, 4, 1, 1, 1, 4, 2, 2, 1, 1, 3, 5, 3, 7, 1, 2, 1, 2, 1, 3, 2, 5, 1, 2

Offset

1,2

Links

Table of n, a(n) for n=1..105.

Example

27 in binary is 11011. S = (1 (1 in binary), 2 (10 in binary), 3 (11 in binary), 5 (101 in binary), 6 (110 in binary), 11 (1011 in binary), 13 (1101 in binary), 27 (11011 in binary)). Note that all of the binary representations of the elements of S are substrings in 11011. 1 is coprime to all other elements of S. 2 is not coprime to 6. 3 is not coprime to 6 or 27. 5 is coprime to all other elements of S. 6 is not coprime to 2, 3 or 27. 11 is coprime to all other elements. 13 is coprime to all other elements. And 27 is not coprime to 3 or 6. So there are 4 elements that are each coprime to all other elements, thus a(27) = 4.

Maple

Contribution from R. J. Mathar, Mar 17 2010: (Start)
iscopr := proc(n, L) for i in L do if i<> n and gcd(n, i) <> 1 then return 0; end if; end do: return 1; end proc:
rebase := proc(L, b) local i ; add(op(i, L)*b^(i-1), i=1..nops(L)) ; end proc:
A175245 := proc(n) ndgs := convert(n, base, 2) ; S := {} ; for dig1 from 1 to nops(ndgs) do for dig2 from dig1 to nops(ndgs) do if op(dig2, ndgs) <> 0 then S := S union { [op(dig1..dig2, ndgs)] } ; fi ; end do: end do: Sl := [] ; for subd in S do Sl := [op(Sl), rebase(subd, 2) ] ; end do: a := 0 ; for subd in Sl do a := a+ iscopr(subd, Sl); end do: a ; end proc:
seq(A175245(n), n=1..120) ; (End)

Crossrefs

A175246

Sequence in context: A117500 A297626 A206441 * A167413 A373198 A340985

Adjacent sequences: A175242 A175243 A175244 * A175246 A175247 A175248

Keyword

base,nonn

Author

Leroy Quet, Mar 13 2010

Extensions

More terms from R. J. Mathar, Mar 17 2010

Status

approved