Multiplied Combinations of numbers less than N.

From: Nathan McKenzie (SPAMDIEkenzi_x_at_yahoo.com)
Date: 10/13/04 

Date: Wed, 13 Oct 2004 15:44:31 +0000 (UTC)

This might be a repost - my original post seems to have wander off,
never to be seen again, but one never knows.

Anyway, can anyone help me with this? If I want to find out how many
solutions to a * b <= N there are, where a, b, and N are each natural
numbers, and N is a fixed constant, I know I can do this,

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

which is pretty straight-forward, but I also know I can do this

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

which is of course faster to compute, but also more elegant
as well.

My question is, are there any similar compact equations for more
variables? If I want to know how many solutions there are to a * b *
c <= N, I can do this,

Sum( a = 1, a <= N, Sum( b = 1, b <= N / a, Floor( N / (a * b) ) ) )

and that generates correct results, but it seems... off, somehow.
Off in the sense that it's overlooking some deeper patterns, I
guess. It's also not greatly efficient.

Are there more compact forms for these kinds of inequalities? What
about for even more variables? What about for a * b * c * d * e <=
N? It's in cases like that where my brute force approach starts
becoming excrutiating and clearly simple-minded. And, for that
matter, is there a name or area of study attached to what I'm asking?
I'd really like to read more about things like this, but I don't even
know where to look to start.

While I'm at it, if I have an inequality like this, a^2 * b <= N, are
there any more elegant or more compact ways of calculating the
number of solutions to that? Or what about a^3 * b^2 * c^2 <= N?

Sum( a = 1, a <= N^1/2, Floor( N / a^2 ) )

and

Sum( a = 1, a <= N^1/3, Sum( b = 1, b <= (N/a^3)^1/2, Floor( N / ( a^3 * b ^ 2 ) ) ) )

generate correct values for me (or, well, possibly correct, depending
on how I want to handle the permutation / combination issues regarding
whether like-powered entries always stay in their same slots or not),
but, once again, as the number of terms start increasing, the
computation starts really adding up, and it's clear that certain
internal patterns are being overlooked.

Relevant Pages