Given a number N how many pairs of numbers have square sum less than or equal to N?

Question

Let's define F(N) as the number of pairs of distinct positive integers (A,B) such that A²+B²≤N and A<B.

If N=5 the only possible such pair is (1,2) for N=10 the pairs are two: (1,2) and (1,3).

Furthermore we have F(13)=3, F(17)=4, F(17)=4, F(20)=5, F(20)=5, F(25)=6, F(100)=31 and so on for every number which is sum of two distinct non-zero squares.

So far I have the following solution:

long long SOLVE(lld n)
{
    long long x=sqrt(n),up=0;
    long long a=x,b=1;
    while(abs(a-(b-1))!=1)
    {

        while(sqr(a)+sqr(b)<=n )
        {
            b++;
        }
        up+=(b-1);
        a--;
    }
    b--;
    up+=(b*(b+1))/2;
    return up;
}
int main()
{
      cout<<number(100);
return 0;
}

Same numbers are not countable, thus (1,1) and (2,2) are invalid tuples. Same combination but different order counts only once. Thus (1,2) and (2,1) count only as once.

But as the range of N is 1, I need a more efficient algorithm or formula to calculate this. Is there any trick to make my code more efficient?

Answer 1

In pseudocode:

int count=0;
for (smaller=1; ;++smaller)
{
    maxlarger = floor(sqrt(N-smaller*smaller));
    if (maxlarger <= smaller)
        break;
    count+=(maxlarger-smaller);
}
return count;

Answer 2

You do not have to calculate the number of B's: you can simply calculate the largest B for which this is possible, which is immediately the number of tuples for that A:

B_max=sqrt(N-A²), and the lower-bound on B is: B_min=A+1.

Now you can do the following:

• iterate for A from 1 to sqrt(n);
• for each such A calculate the amount of B's you can use;
• calculate the sum of these.

So this leads us to the following algorithm:

lld SOLVE(lld n) {
    lld aM=sqrt(n);
    lld a=1;
    lld res = 0;
    for(lld a = 1; a < aM; a++) {
        int nB = sqrt(n-a*a)-a;
        if(nB > 0) {
            res += nB;
        } else {
            break;
        }
    }
    return res;
}

from the moment, no more B values can be found, one can break off the search.

I've written a demo here which seems to work.