number of solutions of x*y

Question

How many solutions (unique pairs (x,y) ) exist for equation $xy < N$ ?
constraints : $x >1 , y>1 , N<=50000$

I tried following method , but it fails for say N=24 , in which i calculate many pairs like (2,3) , (3,2) twice .

Code :

p=0;
for(j=1;j<=sqrt(N);j++,p++)
{
    if(j*j==N)
        continue; // we want <N

    a=N/j;
    if(j*a==N)
        a--;
        a-=p; // don't add (2,1) as (1,2) was already added
    ans+=2*a-1; //(a,b) and (b,a) but don't calculate (a,a) twice
}

EDIT : By unique i mean (1,1) should not be counted twice .
for 24 pairs are :

(1,1)(1,2)(1,3)........(1,22)(1,23)  
(2,1)(2,2)(2,3)........(2,11)
(3,1)(3,2)(3,3)........(3,7)
(4,1)(4,2)...........(4,5)

I have updated code and added comments

I do not know how to compute efficiently and exactly. he number is approximately $n\log n+(2\gamma-1)n$, where $\gamma$ is the Euler-Mascheroni constant. There has been a lot of work on the error term. — André Nicolas, Apr 05 '14 at 07:10
@AndréNicolas: the OP seems to count $(2,3)$ and $(3,2)$ as the same. That formula counts each separately, does it not? — robjohn, Apr 05 '14 at 07:55
@aseem: do you want to count pairs like $(3,3)$? If I am reading your question right, you do not want to count $(1,3)$ and $(3,1)$ separately, correct? — robjohn, Apr 05 '14 at 07:57

Yiyuan Lee · Answer 1 · 2014-04-05T08:11:07.723

2

Try this:

int count = 0;
for(int x = 2; x <= N / 2; x++)
{
    for(int y = 2; x*y < N; y++)
    {
        count++;
    }
}

This is more efficient as it does not require the square root function.

The final value of the variable 'count' is now the number of unique pairs ($(3,2)$ and $(2,3)$ are different).

edited Apr 05 '14 at 08:11

answered Apr 05 '14 at 07:26

Yiyuan Lee

14,435

1

+1. Also I agree with your comment on the question. Voted to close. – Guy Apr 05 '14 at 07:34

score 1 · Answer 2 · answered Apr 05 '14 at 07:51

1

The number of non-ordered pair solutions is $$ \frac12\left(\left\lfloor\sqrt{N-1}\right\rfloor+\sum_{k=1}^{N-1}\left\lfloor\frac {N-1}k\right\rfloor\right) $$ The summation counts all the ordered pairs and divides by $2$. However, this divides the pairs $(k,k)$ by two, and they should not be, so the term with the square root should take care of that.

answered Apr 05 '14 at 07:51

robjohn

345,667

can you explain how you get that? I'm looking for an analytical solution to this problem myself. Thanks. – abalter Jun 13 '14 at 21:36
The number of $y$ so that $xy\lt N$ is $\left\lfloor\frac{N-1}{x}\right\rfloor$. This counts all "unique" pairs twice ($x\lt y$ and $x\gt y$) except those where $x=y$ which it counts once. To add the number where $x=y$ back in, we add the number of pairs $(x,x)$ where $x^2\lt N$ which is $\left\lfloor\sqrt{N-1}\right\rfloor$. Now that all pairs are counted twice, we divide by $2$. – robjohn Jun 14 '14 at 03:33

number of solutions of x*y

2 Answers2

Linked