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

Question

We define F (N) as the number of pairs of different natural numbers (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).

In addition, F (13) = 3, F (17) = 4, F (17) = 4, F (20) = 5, F (20) = 5, F (25) = 6, F (100) = 31 etc. For each number, which is the sum of two different 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; } 

The same numbers are not countable; therefore, (1,1) and (2,2) are invalid tuples. The same combination, but a different order is calculated only once. Thus, (1,2) and (2,1) are counted only once.

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

Answer 1

In pseudo code:

 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 need to calculate the number of B: you can simply calculate the largest B for which it is possible that immediately the number of tuples for that A:

B _max = sqrt (NA ² ), and the lower bound on B: B <sub> minsub> = A + 1.

Now you can do the following:

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

So this brings 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(na*a)-a; if(nB > 0) { res += nB; } else { break; } } return res; } 

from the moment no more B values ​​can be found, you can break the search.

I wrote a demo here that seems to work.