We investigate a curious problem from additive number theory: Given two positive integers S and Q, does there exist a sequence of positive integers that add up to S and whose squares add up to Q? We show that this problem can be solved in time polynomially bounded in the logarithms of S and Q. As a consequence, also the following question can be answered in polynomial time: For given numbers n and m, do there exist n lines in the Euclidean plane with exactly m points of intersection?
|Number of pages||6|
|Journal||Theoretical computer science|
|Publication status||Published - 2004|
- Algorithmic number theory
- Polynomial time algorithm