Solution

Answer: 345558983

Let

$$F(m,n)=#{(a_1,\dots,a_n)\in \mathbb Z_{>0}^n:\ a_1a_2\cdots a_n\le m}.$$

We are asked for

$$F(10^9,10^9)\pmod{1234567891}.$$

1. Mathematical analysis

For a fixed integer $t$, define

$$d_n(t)=#{(a_1,\dots,a_n)\in \mathbb Z_{>0}^n:\ a_1a_2\cdots a_n=t}.$$

Then clearly

$$F(m,n)=\sum_{t\le m} d_n(t).$$

Step 1: Interpret $d_n(t)$

Suppose

$$t=\prod p_i^{e_i}.$$

To form an ordered $n$-tuple whose product is $t$, we distribute the exponent $e_i$ of each prime $p_i$ among the $n$ positions.

The number of ways to distribute $e_i$ identical objects into $n$ boxes is

$$\binom{n+e_i-1}{e_i}.$$

Therefore

$$d_n(t)=\prod_i \binom{n+e_i-1}{e_i}.$$

This is the generalized divisor function.

Step 2: Remove the 1's

A much more useful viewpoint is:

choose exactly $k$ positions that are $>1$,
all remaining positions are $1$.

Let $T_k(m)$ denote the number of ordered $k$-tuples of integers $>1$ whose product is $\le m$.

Then

$$F(m,n)=\sum_{k\ge0}\binom{n}{k}T_k(m).$$

Why?

choose the $k$ non-1 positions: $\binom nk$,
fill them with a valid ordered $k$-tuple counted by $T_k(m)$.

Since every factor is at least $2$,

$$2^k\le m.$$

For $m=10^9$,

$$k\le \lfloor \log_2(10^9)\rfloor = 29.$$

So only 30 terms are needed.

Step 3: Recurrence for $T_k(m)$

Define

$$T_0(m)=1.$$

For $k\ge1$,

$$T_k(m)=\sum_{a=2}^{m} T_{k-1}!\left(\left\lfloor \frac{m}{a}\right\rfloor\right).$$

This is because the first factor can be any $a\ge2$, and the remaining $k-1$ factors must have product at most $m/a$.

Step 4: Hyperbola optimization

The values of

$$\left\lfloor \frac{m}{a}\right\rfloor$$

change only $O(\sqrt m)$ times.

$$q=\left\lfloor \frac{m}{a}\right\rfloor,$$

then all $a$ in an interval $[i,j]$ give the same quotient $q$.

So we compute

$$T_k(m)=\sum_{\text{blocks }[i,j]} (j-i+1),T_{k-1}(q).$$

With memoization, this becomes extremely fast.

2. Python implementation

import math
from functools import lru_cache

MOD = 1234567891
N = 10**9
M = 10**9

@lru_cache(maxsize=None)
def T(k, x):
    """
    Number of ordered k-tuples of integers > 1
    whose product is <= x, modulo MOD.
    """

    if k == 0:
        return 1

    # minimum possible product is 2^k
    if x < (1 << k):
        return 0

    total = 0

    i = 2
    while i <= x:
        q = x // i
        j = x // q

        # all a in [i, j] give floor(x/a) = q
        total += (j - i + 1) * T(k - 1, q)
        total %= MOD

        i = j + 1

    return total

def solve():
    ans = 0

    # only k <= floor(log2(M)) matter
    for k in range(30):
        ans += math.comb(N, k) % MOD * T(k, M)
        ans %= MOD

    return ans

print(solve())

3. Code walkthrough

Memoized recursion

@lru_cache(maxsize=None)
def T(k, x):

Stores previously computed states.

Base case

if k == 0:
    return 1

There is exactly one empty tuple.

Pruning

if x < (1 << k):
    return 0

Any $k$-tuple with entries $>1$ has product at least $2^k$.

Quotient grouping

q = x // i
j = x // q

All integers in $[i,j]$ produce the same quotient.

This reduces complexity from $O(x)$ to roughly $O(\sqrt x)$.

Final summation

for k in range(30):
    ans += math.comb(N, k) % MOD * T(k, M)

Implements

$$F(M,N)=\sum_{k=0}^{29}\binom Nk T_k(M).$$

4. Verification

The same program gives:

$$F(10,10)=571,$$

matching the statement.

It also gives:

$$F(10^6,10^6)\bmod 1234567891 = 252903833,$$

again matching the problem statement.

So the method is validated.

The computed value for the target case is:

$$F(10^9,10^9)\bmod 1234567891 = 345558983.$$

Answer: 345558983

Project Euler Problem 452