

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.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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^(i1), 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 A259176 A237591
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



