2
\$\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.

Improve this question
\$\endgroup\$
3
  • 15
    \$\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
    Commented Aug 1, 2022 at 0:19
  • 15
    \$\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
    Commented Aug 1, 2022 at 0:21
  • 4
    \$\begingroup\$ I’m voting to close this question based on my comments above: we can't decide the winner for this challenge under the given winning criterion. \$\endgroup\$
    – Bubbler
    Commented Aug 8, 2023 at 0:26

0

Reset to default