login
Number of divisors of n whose binary representation is contained in that of n.
6

%I #31 Jul 16 2022 07:09:35

%S 1,2,2,3,2,4,2,4,2,4,2,6,2,4,3,5,2,4,2,6,2,4,2,8,2,4,3,6,2,6,2,6,2,4,

%T 2,6,2,4,3,8,2,4,2,6,4,4,2,10,2,4,3,6,2,6,4,8,3,4,2,9,2,4,4,7,2,4,2,6,

%U 2,4,2,8,2,4,4,6,2,6,2,10,2,4,2,6,3,4,3,8,2,8,3,6,3,4,3,12,2,4,3,6,2

%N Number of divisors of n whose binary representation is contained in that of n.

%H Reinhard Zumkeller, <a href="/A093640/b093640.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.

%F a(n) > 1 for n>1.

%F a(p) = 2 for primes p.

%F a(A093641(n)) = A000005(A093641(n)).

%F a(A093642(n)) < A000005(A093642(n)).

%e n = 18: divisors of 18: 1 = '1', 2 = '10', 3 = '11', 6 = '110', 9 = '1001' and 18 = '10010': four of them are binary substrings of '10010', therefore a(18) = 4.

%t a[n_] := DivisorSum[n, 1 &, StringContainsQ @@ IntegerString[{n, #}, 2] &]; Array[a, 100] (* _Amiram Eldar_, Jul 16 2022 *)

%o (Haskell)

%o import Data.List (isInfixOf)

%o a093640 n = length [d | d <- [1..n], mod n d == 0,

%o show (a007088 d) `isInfixOf` show (a007088 n)]

%o -- _Reinhard Zumkeller_, Jan 22 2012

%o (Python)

%o from sympy import divisors

%o def a(n):

%o s = bin(n)[2:]

%o return sum(1 for d in divisors(n, generator=True) if bin(d)[2:] in s)

%o print([a(n) for n in range(1, 102)]) # _Michael S. Branicky_, Jul 11 2022

%Y Cf. A000005, A078822, A007088, A093641, A093642.

%K base,nonn

%O 1,2

%A _Reinhard Zumkeller_, Apr 07 2004