1
\$\begingroup\$

It is known that any natural number can be decomposed into the sum of three triangular numbers (assuming 0 is triangular), according to Fermat's Polygonal Number Theorem. Your task is to come up with an algorithm of decomposing number into 3 triangular numbers that has the best asymptotic complexity. As an input you are given a number N. Output should contain three numbers, they must be triangular(or 0) and sum of them must be equal to number given in the input.


The difference between this question and mine is that my question isn't code-golf.

\$\endgroup\$
2
  • 12
    \$\begingroup\$ The problem is equivalent to finding a 3-square decomposition because $$a(a+1)/2 + b(b+1)/2 + c(c+1)/2 = n \iff (2a+1)^2 + (2b+1)^2 + (2c+1)^2 = 8n + 3$$ and I point to a paper that shows some of the fastest known algorithms that can solve that. But note that time complexity analyses of these algorithms are extremely high-level, and without assuming a long-standing conjecture, the time bound is simply not known (other than it being polynomial in the number of bits of the input). \$\endgroup\$
    – Bubbler
    Aug 1 at 0:19
  • 13
    \$\begingroup\$ So, while I do think it is an interesting problem in itself, I don't think it fits well with our site under the contest type fastest-algorithm - as we can't prove the time complexity of the best known algorithms, we can't decide which one wins. \$\endgroup\$
    – Bubbler
    Aug 1 at 0:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.