You were correct to try
a^2 - b^2 = (a+b)(a-b) venue: take your
n and break it into
q so that
Usually there are several ways of doing it and almost each way defines a pair you need.
a would be
(p + q)/2 and
b would be
(p - q)/2. Thus, you only need pairs where either both
q are even, or they are both odd.
You don't really need calculating
q, just number of pairs.
Thus, break your
n into prime divisors and count distinct ways to divide those divisors into 2 different sets so that either both sets contain at least one 2, or neither do.
Ok, some more math:
Case with n=1 is trivial: no solutions. For all other cases we can assume that n has nonempty set of prime divisors.
Let's start with case when all prime divisors are distinct and 2 is not present.
Each divisor can be placed either in set 1 or in set 2. Since sets will be obviously different, we're guaranteed
q and since we're working with
n's divisors, we can be sure that
p * q = n.
Divisors' placement can be described bijectively by a string of bits with the length as number of divisors. Hence, we'll have
2^(<number of divisors>-1) pairs of
q ( -1 because swapping sets gives same
Now what if some prime divisor (except for 2, which is still not present) is present k>1 times?
For all other divisors, situation is exactly as above, but our special divisor will provide
*(k+1), instead of
*2 to number of pairs. Well, actually,
*2 of other divisors is just a special case with k = 1.
So, if 2 is not present, we go through
n's prime factorisation and for each divisor and its respective
k number of occurences, we multiply our number of placements by
k+1. If result is even - there were odd
ks, meaning that in no placement our 2 sets were equal. We still counted every pair of
q twice (once as set1, set2 and once as set2, set1) so we divide k+1 product by 2 and that's our answer. If result is not even - we have even quantity of every divisor, meaning that
n is a square. That means we counted twice every pair of
q but we've also counted pair of
sqrt(n) once - which we shouldn't have! We would have to substract 1 before dividing by 2.
If 2 is present, things don't get much complicated either. If there's only one
2 we return 0 - because there's no
b that work. If there's more than one - we say that one goes to each set every time so we simply drop 2 twos and stop concerning ourselves with them, repeating steps above.
And now for some code:
from collections import Counter
from functools import reduce
from operator import mul
def product(stuff): return reduce(mul, stuff)
"""Return number of pairs (a,b) so that a*a - b*b = n
(Algo explanation goes here)
if n % 2 == 0 and n % 4 != 0:
return 0 # (a+b) is odd and (a-b) is even (or vice versa)? No way!
factorisation = Counter(prime_factorisation(n))
if factorisation > 1:
# We use 2 '2's to guarantee that both (a+b) and (a-b) are even
factorisation -= 2
factor_count_product = product(k + 1 for k in factorisation.values())
if factor_count_product % 2 == 1:
# n is a square and we counted root-root pair as (a+b) and (a-b), undo that
factor_count_product -= 1
return factor_count_product // 2 # we've counted every pair twice, so //2
Of course, this code could be called comprehensible only in context of all math above. In the wild, most of the code would be a docstring explaining what happens.
Number of divisors grows pretty slowly with growth of
n. It all boils down to how fast you produce them prime factors.
Your idea with "blocks":
You can notice that "block" number
a = c + 1 and all
bs that would give
n > 0 (but not necessarily integer).
If you shift block numbering so that
(2+1)(2-1) is actually block 2 then you will have block number equal to
a used in this block with block 1 being empty. (because no
n would satisfy our needs).
You could iterate through each pair like:
for a in range(2, max_a(n)):
for b in range(1, a):
# test our (a-b)(a+b)
However, that means iterating a lot.
You could notice that each block can produce no more than 1 solution, so we could iterate through blocks instead. However, we'd have to check if a block really produces a solution:
for a in range(2, max_a(n)):
b_squared = a*a - n
# check if b_squared is actually a square
The trick will be in determining
2*a - 1 > n, then
a^2 - (a-1)^2 > n and thus for any
b we're interested in,
a^2 - b^2 > n.That makes our
max_a something like
(n + 1)//2, or
n//2 + 1 for sake of corner cases.
That's too much! we'll have to check around
10^13 blocks, and that's a lot. Well, checking couple hundred thousand primes is not a simple thing either, but it's way faster.
So, unless you can lower the boundary for
a, the code would still take lots of time.
If you are interested in generative solutions, I'd recommend picking some number
N, rewriting equation modulo
N and looking for moduli
b that are possible with given
n. If, for example,
N is around hundred buth there's only 10 possible modulo pairs that work - you would have to iterate only through 10 (a,b) pairs out of 10 000.
For example, if
N = 3 and
n mod 3 = 2 then
a mod 3 = 0 and either
b mod 3 = 1 or
b mod 3 = 2. Of each 9 consecutive possible options for
(a,b) only 2 remain. Of each 3 consecutive possible options for
a only 1 remains.
For example, if
N = 5 and
n mod 5 = 1 then only
a^2 mod 5 = 1, b^2 mod 5 = 0 and
a^2 mod 5 = 0, b^2 mod 5 = 4. Of 25 possible options for
(a,b) pair this leaves only 4. Of 5 possible options for
a, it leaves only 3.
Moreover, if you have calculated allowed modulo pairs for some
M and some
N you can then calculate allowed modulo pairs for
M*N and instead of iterating possible pairs with steps of size
M), go with
Combining 2 examples above, you'll get that you only need to check 3 out of 15 options for
Using these 2 tricks (modulo sieving and combining) you can iterate with ever-increasing steps without missing anything. However, problem does not ask for generating those pairs, only for counting their number, so that's a bit excessive.
If you find that option interesting, take a closer look at sieves and especially wheels part.