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

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, 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, 6, 2, 4, 2, 8, 2, 4, 2, 6, 2, 4, 2, 10, 2, 4, 2, 6, 4, 4

Offset: 1

Author

Rémy Sigrist, Apr 24 2021

Keywords

• nonn
• base

Comments

See A343651 for the corresponding divisors.

Examples

			For n = 18:
- we have the following divisors:
     d   18/d  bin(d)  bin(18/d)  Requires carries?
     --  ----  ------  ---------  -----------------
      1    18       1      10010  No
      2     9      10       1001  No
      3     6      11        110  Yes
      6     3     110         11  Yes
      9     2    1001         10  No
     18     1   10010          1  No
- so a(18) = #{1, 2, 9, 18} = 4.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to binary expansion of n
• Index entries for sequences related to divisors

Crossrefs

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

Programs

PARI

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

Formula

a(n) <= A000005(n).

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

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

A001511(n) divides a(n).