here for a relevant discussion.
Hi, how can one find the number of ways in which an integer can be expressed as a sum of two squares?
E.g for 5 it's 1, as 5 can be represented as : 1^2+2^2.
Here a^a+b^b is same as b^b+a^a.
I know that for an integer to be expressed as such , its prime factorisation should contain no odd powers of primes of the form 4k + 3 . So how do i extend this idea to arrive at the conclusion or is there any other way/formula?
I worked out the problem, as:
factorise the number and count the number of factors which are such that factor%4=3 (call these types d1) and factor%4=1 (call these types as d2).
Then the number of ways of representing the number would be |d1-d3|/2 .
Now this may take some time for factoring large numbers.So is there any other method to get d1(i.e no of factors with property : factor%4=1) and d3(i.e no of factors with property : factor%4=3) for a number?