# Number of solutions for $xy<d$, where $x,y>1$

Is there a way we can determine number of solutions for equation

$$xy < d$$

where $d$ is a constant and $x$ and $y$ are positive integers greater than $1$?

I am not interested in actual values, but just number of possible solutions.

EDIT: Would it help if $d$ is represented as two integers $d=d_1 d_2$?

• Is d an integer? Apr 11, 2014 at 8:45
• Yes d is an integer greater than 0 Apr 11, 2014 at 8:47
• Do you have some way I can solve it easily? I want to create a program for that Apr 11, 2014 at 8:48
• Consider the arithmetic function $\sigma_{x}(n):=\sum_{d|n}d^x$, defined for $x\in\mathbb C$. Just take $x=0$ to get what you want. However I know that this is not a full answer; this is just a suggest. So just look to something about that function. However I'm not sure that a closed formula that, given a number $n$, tells you how many divisors of $n$ you have, exists. It seems related with the problem of factorization; and it's well know that is not solved (i.e. doesn't exist no rapid algorithm that allows you to factorize $n$ in acceptable times).
– Joe
Apr 11, 2014 at 9:12

In terms of programming a (probably not efficient way) to do it would be to preset two arrays for $x$ and $y$ that run through all of the values from $(2,...,d)$ write a for loop with an if statement, that multplies $x$ and $y$ together, and the if statement seperates them, so if $xy\lt d$ send tjose values to an array, then when the for loop ends, the size of that array would be your answer.

• This is an obvious way, but i was looking for an efficient way. Thanks anyway Apr 11, 2014 at 8:59
• I don't need the array as well i can use counters. I don't know how you need array? Apr 11, 2014 at 9:02
• Just one way of doing it, Ive never really taken any proper programming classes Apr 11, 2014 at 9:05

I think that if you fix a value for x, then it's easy to know how many y's make xy < d true. it is $\lceil d/x - 1 \rceil$ possible y's. For example, imagine $d = 10$, and fix $x = 3$, so all the possible value to y is 1,2 and 3, i.e., 1 to $\lceil d/x - 1 \rceil$.

The reason that I think it's $\lceil d/x - 1 \rceil$, is that when d/x is not an integer, the floor of this number $\lfloor d/x \rfloor$ is the answer, but if it is an integer, then xy = d if $\lfloor d/x \rfloor$ is in the set of possible y's, so $\lfloor d/x \rfloor$ can't be in the solution set of the y's.

Finally, we need to find this to each x, so the final formula will be $\sum\limits_{x=1}^{d-1}\lceil d/x - 1 \rceil$. I know that it can be computed in $O(d)$, but maybe you can find a closed formula to this summation.

I think this is right, but not sure. If any doubts, just ask.

• I realized now that x and y are supposed to be greater than 1, but it is easy to modify the formula, we just need to take off one element of each parcel of the summation, i.e., $\lceil d/x - 1 \rceil - 1$, and make the summation starts from $2$ instead of $1$. Apr 11, 2014 at 11:32