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

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

Links

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

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} (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)

Example

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.

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 *)

Prog

(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
(PARI) a(n)=sumdiv(n, d, bitor(d, n)==n) \\ Charles R Greathouse IV, Sep 29 2014

Crossrefs

Cf. A000005, A000120, A046801, A246601.

Sequence in context: A254315 A080942 A099812 * A068068 A193523 A092505

Adjacent sequences: A246597 A246598 A246599 * A246601 A246602 A246603

Keyword

nonn,base

Author

N. J. A. Sloane, Sep 06 2014

Status

approved