login
a(n) is the number of divisors d of n such that the product d * (n/d) can be computed without carries in binary.
2

%I #12 Apr 25 2021 15:14:36

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

%T 2,6,2,4,2,8,2,4,2,6,4,4,2,10,2,4,4,6,2,8,2,8,2,4,2,12,2,4,6,7,2,4,2,

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

%N a(n) is the number of divisors d of n such that the product d * (n/d) can be computed without carries in binary.

%C See A343651 for the corresponding divisors.

%H Rémy Sigrist, <a href="/A343650/b343650.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>

%H <a href="/index/Di#divisors">Index entries for sequences related to divisors</a>

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

%F a(2^n) = n + 1 for any n >= 0.

%F a(2^n - 1) = A067824(n) for any n > 0.

%F A001511(n) divides a(n).

%e For n = 18:

%e - we have the following divisors:

%e d 18/d bin(d) bin(18/d) Requires carries?

%e -- ---- ------ --------- -----------------

%e 1 18 1 10010 No

%e 2 9 10 1001 No

%e 3 6 11 110 Yes

%e 6 3 110 11 Yes

%e 9 2 1001 10 No

%e 18 1 10010 1 No

%e - so a(18) = #{1, 2, 9, 18} = 4.

%o (PARI) a(n, h=hammingweight) = my (hn=h(n)); sumdiv(n, d, hn==h(d)*h(n/d))

%Y Cf. A000005, A001511, A067824, A266195, A343651.

%K nonn,base

%O 1,2

%A _Rémy Sigrist_, Apr 24 2021