|
%I #7 Mar 11 2014 01:32:51
%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,
%T 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,
%U 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
%N 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.
%e 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.
%p Contribution from _R. J. Mathar_, Mar 17 2010: (Start)
%p 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:
%p rebase := proc(L,b) local i ; add(op(i,L)*b^(i-1),i=1..nops(L)) ; end proc:
%p 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:
%p seq(A175245(n),n=1..120) ; (End)
%Y A175246
%K base,nonn
%O 1,2
%A _Leroy Quet_, Mar 13 2010
%E More terms from _R. J. Mathar_, Mar 17 2010
|
