2
$\begingroup$

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$?

$\endgroup$
4
  • $\begingroup$ Is d an integer? $\endgroup$
    – Ellya
    Apr 11, 2014 at 8:45
  • $\begingroup$ Yes d is an integer greater than 0 $\endgroup$ Apr 11, 2014 at 8:47
  • $\begingroup$ Do you have some way I can solve it easily? I want to create a program for that $\endgroup$ Apr 11, 2014 at 8:48
  • 1
    $\begingroup$ 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). $\endgroup$
    – Joe
    Apr 11, 2014 at 9:12

2 Answers 2

1
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ Apr 11, 2014 at 11:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .