# The number of distinct multiples of composites greater than $n$ that can be factored into two naturals less than or equal to $n$

Given a list of composites between $n$ and $\lfloor \frac{n^2}{2} \rfloor$:

What would be the most efficient way to count, for each composite, the number of its distinct multiples that can be factored into two naturals less than or equal to $n$?

For example, $n = 6$:

For the composite 8, there are 3:
$8 \times 1$, factors $4 \times 2$
$8 \times 2$, factors $4 \times 4$
$8 \times 3$, factors $4 \times 6$
The multiple $8 \times 4$ cannot be factored into two naturals less than or equal to 6.

For the composite 9, there are 3:
$9 \times 1$, factors $3 \times 3$
$9 \times 2$, factors $6 \times 3$
$9 \times 4$, factors $6 \times 6$
The multiple $9 \times 3$ cannot be factored into two naturals less than or equal to 6.

Let the composite be $m$. Factor $m$, then find all factorizations with no factor greater than $n$. For each one, see how much room you have. I'll take the larger example $n=25, m=144=2^43^2$ From the prime factorization we can find $144=6\cdot 24=8 \cdot 18 = 9 \cdot 16 = 12 \cdot 12$ are possible, while $1 \cdot 144, 2 \cdot 72, 3 \cdot 48, 4 \cdot 36$ have a factor too large. Now find what you can multiply each factor by while staying below $25$. The $6$ can be multiplied by $1,2,3,4$, while the $24$ cannot be multiplied by anything. You can get this by computing $\lfloor \frac {25}6 \rfloor$ In this case, that is all you can get. Both of the $12$'s can be multiplied by $1,2$, but that doesn't give anything new, so there you are.
• In this example, $1,2,3,4$ are all distinct and that is all you can get. You can just use the most unbalanced factorization and see what fits. I can see the sketch of a proof. – Ross Millikan Jul 9 '14 at 21:51