A394909 a(n) is the number of products x*y of two integers 2^(n-1) <= x <= y < 2^n such that the Hamming weight of this product is maximized.

1, 2, 1, 1, 1, 1, 7, 1, 1, 3, 10, 6, 2, 8, 18, 18, 9, 1, 54, 1, 35, 2, 2, 1, 94, 31, 23, 3, 44, 27, 274, 2, 1, 37, 37, 61, 408, 2, 45, 41, 1, 29, 1, 1, 121, 178, 1, 2, 237, 2, 361, 81, 18, 46, 448, 1, 1, 1, 10, 1, 1743, 20, 4, 180, 141, 67, 689, 7, 114, 57, 1

Offset

1,2

Comments

Number of products of two n-bit integers x<=y with maximum Hamming weight A394988(n).

Links

Chai Wah Wu, Table of n, a(n) for n = 1..90

Example

a(2) = 2: the 2 pairs of 2-bit numbers with A394988(2)=2 are 2*3=6=110_2 and 3*3=9=1001_2;
a(7) = 7: the 7 pairs of 7-bit numbers, whose product has the maximum Hamming weight of A394988(7)=12 are 65*126=8190=1111111111110_2, 69*115=7935=1111011111111_2, 70*117=8190, 75*109=8175=1111111101111_2, 78*105=8190, 90*91=8190, 105*117=12285=10111111111101_2.

Prog

(Python)
from sympy.utilities.iterables import multiset_permutations
from sympy import divisors
def A394909(n):
    a = 1<<n-1
    b = a<<1
    k = (n<<1)-1
    for l in range(k, 0, -1):
        c = 0
        for s in multiset_permutations('0'*(k+1-l)+'1'*l):
            m = int(''.join(s), 2)
            for d in divisors(m):
                if d**2>m:
                    break
                if a<=d<b and a*d<=m<b*d:
                    c += 1
        if c:
            return c # Chai Wah Wu, Apr 10 2026

Crossrefs

Cf. A000120, A029837, A394988.

Sequence in context: A364457 A305567 A134744 * A260875 A351350 A176250

Adjacent sequences: A394906 A394907 A394908 * A394910 A394911 A394912

Keyword

nonn,base

Author

Hugo Pfoertner, Apr 09 2026

Extensions

a(24)-a(64) from Chai Wah Wu, Apr 10 2026

a(65)-a(71) from Chai Wah Wu, Apr 13 2026

Status

approved