A246600 Number of divisors d of n with property that the binary representation of d can be obtained from the binary representation of n by changing any number of 1's to 0's.

1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 4, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 4, 2, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 4, 2, 2, 4, 3, 2, 2, 2, 2, 4, 2, 2, 6, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 4, 2, 3, 2, 2, 4, 2

Offset: 1

Author

N. J. A. Sloane, Sep 06 2014

Keywords

• nonn
• base

Comments

Equivalently, the number of divisors d of n such that the bitwise OR of n and d is equal to n. - Chai Wah Wu, Sep 06 2014

Equivalently, the number of divisors d of n such that the bitwise AND of n and d is equal to d. - Amiram Eldar, Dec 15 2022

The sums of the first 10^k terms for k = 1, 2, ..., are 16, 224, 2580, 26920, 273407, 2745100, 27440305, 274127749, 2738936912, 27373288534, 273631055291, 2735755647065, ... . Conjecture: The asymptotic mean of this sequence is 1 + Sum_{k>=1} 1/(k*2^A000120(k)) = 2.7351180693... . - Amiram Eldar, Apr 07 2023

Examples

			12 = 1100_2; only the divisors 4 = 0100_2 and 12 = 1100_2 satisfy the condition, so(12)=2.
15 = 1111_2; all divisors 1,3,5,15 satisfy the condition, so a(15)=4.
		

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A000120, A046801, A246601, A047999.

Programs

Maple

A246600:=proc(n)
    local a, d, s, t, i, sw;
    a:=0;
    s:=convert(n, base, 2);
    for d in numtheory[divisors](n) do
        sw:= false;
        t:=convert(d, base, 2);
        for i from 1 to nops(t) do
            if t[i]>s[i] then
                sw:= true;
            fi;
        od:
        if not sw then
            a:=a+1;
        fi;
    od;
    a;
end;
seq(A246600(n), n=1..100);

Mathematica

a[n_] := DivisorSum[n, Boole[BitOr[#, n] == n]&]; Array[a, 100] (* Jean-François Alcover, Dec 02 2015, adapted from PARI *)

PARI

a(n)=sumdiv(n,d,bitor(d,n)==n) \\ Charles R Greathouse IV, Sep 29 2014

Python

from sympy import divisors
def A246600(n):
    return sum(1 for d in divisors(n) if n|d == n)
# Chai Wah Wu, Sep 06 2014

Formula

a(2^i) = 1.

a(odd prime) = 2.

a(n) <= 2^wt(n)-1, where wt(n) = A000120(n).

a(n) = Sum_{d|n} A047999(n,d), where A047999(n,d) = binomial(n,d) mod 2. - Ridouane Oudra, May 03 2019

From Amiram Eldar, Dec 15 2022: (Start)

a(2*n) = a(n), and therefore a(m*2^k) = a(m) for m odd and k>=0.

a(2^n-1) = A000005(2^n-1) = A046801(n). (End)