Combinations of multiplied natural numbers less than N.

[Nathan McKenzie]

If I take the expression a * b <= N, where a, b, and N are all
natural numbers, I know that the number of answers can be expressed
as

Sum( i = 1, i <= N, Floor( N / i ) )

but I can also express this value as

2 * Sum( i = 1, i <= N ^ 1/2, Floor( N / i ) ) - ( Floor( N ^ 1/2 ) )^2

which is much quicker to compute. So this works for combinations of
two numbers.

Are there any similar quick formulas for more than 2 numbers?

If I have a * b * c <= N, is there any way to express this cleanly?
I know that I can generate the correct answer like this:

Sum( i = 1, i <= N, Sum( j = 1, j <= N / i, Floor( N / (i*j) ) ) )

But I can already tell that there are all sorts of deeper patterns
that aren't being exploited that way, and that this isn't especially
effecient, especially as I keep adding more terms.

Are there any quicker formulas? Are there ones for even larger
values (like a * b * c * d * e <= N, for example)? Is there a name
for this kind of thing? I don't even know where to look or what to
search for to learn more about this kind of thing.

And, while on the subject, are there any compact formulas for
calculating how many values there are for something like a^2 * b <=
N, where a, b, and N are all natural numbers? Or for a^3 * b^2 * c^2
<= N? Once again, I can write out nested sums that generate correct
answers, but I can't help feeling like I'm overlooking deeper
patterns here, and I have no idea where to turn to to learn more.

Nathan McKenzie

[Gerry Myerson]

In article <200410130327...@proapp.mathforum.org>,
REMOVE...@yahoo.com (Nathan McKenzie) wrote:

> If I take the expression a * b <= N, where a, b, and N are all
> natural numbers, I know that the number of answers can be expressed
> as

<snip!>

Didn't you (or somebody) just post exactly this question
a week or two ago? Do you think the answers have changed?

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

[Nathan McKenzie]

I posted a while ago, and then it didn't show up for about a day, so I thought that my post must have been unceremoniously eaten. A day later, I went ahead and reposted my question (leading with the statement "Sorry if this is a repeat - my first post seems to have disappeared), and that repost was the one that was replied to. I guess I'll wait longer in the future to repost things that don't seem to be showing up.

Odd.

Nathan McKenzie