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

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, 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, 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

Offset: 1

Author

Reinhard Zumkeller, Apr 07 2004

Keywords

• base
• nonn

Examples

			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.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to binary expansion of n.

Crossrefs

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

Programs

Haskell

import Data.List (isInfixOf)
a093640 n  = length [d | d <- [1..n], mod n d == 0,
                         show (a007088 d) `isInfixOf` show (a007088 n)]
-- Reinhard Zumkeller, Jan 22 2012

Mathematica

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

Python

from sympy import divisors
def a(n):
    s = bin(n)[2:]
    return sum(1 for d in divisors(n, generator=True) if bin(d)[2:] in s)
print([a(n) for n in range(1, 102)]) # Michael S. Branicky, Jul 11 2022

Formula

a(n) > 1 for n>1.

a(p) = 2 for primes p.

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

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