1

A few years ago I found an interesting programming problem:
"To find number of partition of n into sum of three squares with n < 10^9 and 1 second time limit."

Question: Does anyone know how to solve this problem with given constraints?
I think it can be do purely with asymptotic time complexity faster than O(n) only? Is there some clever math approach or it is code optimization engineering problem?

I found some info on https://oeis.org/A000164, but there are an O(n)-algo in FORMULA section
(because we need to find all divisors of each n-k^2 number for compute e(n-k^2)) and O(n)-algo in MAPLE section.

Rory Daulton
  • 21,934
  • 6
  • 42
  • 50
Dmitry Pyatin
  • 419
  • 1
  • 7
  • 17

1 Answers1

2

Yes. First factor the number, n - z^2, into primes, decompose the primes into Gaussian conjugates and find different expressions to expand and simplify to get a + bi, which can be then raised, a^2 + b^2. We can rule out any candidate n - z^2 that contains a prime of form 4k + 3 with an odd power.

This is based on expressing numbers as Gaussian integer conjugates. (a + bi)*(a - bi) = a^2 + b^2. See https://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares and https://stackoverflow.com/a/54839035/2034787

גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
  • Are you proposing to factorize each of the 'sqrt(n)' numbers 'n - z^2' ? But if I factorize sqrt(n) numbers each in average of sqrt(n) operations I will get O(n) time, or not? – Dmitry Pyatin Apr 19 '19 at 17:18
  • @DmitryPyatin What if we precomputed the relevant primes and only tested each candidate for divisibility by those? On the SO question I referenced, there may be other optimisations to candidate generation. – גלעד ברקן Apr 19 '19 at 17:23
  • @DmitryPyatin the formula in oeis is interesting. – גלעד ברקן Apr 19 '19 at 17:35
  • The problem solved by this way with factorization on only primes 4k+1, 4k+3 less than 'n-z^2' and heuristic primality test for remainder. – Dmitry Pyatin Apr 20 '19 at 11:00