2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for answering, that gives me a helpful idea. (I added the word "distinct" and wonder if there is an efficient way to guarantee that.) $\endgroup$ – גלעד ברקן Jul 9 '14 at 21:20
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jul 9 '14 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.