Abstract
Abstract
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?
Author Keywords: Algorithmic number theory; Geometry; Polynomial time algorithm
Original language | English |
---|---|
Pages (from-to) | 415-421 |
Journal | Theoretical Computer Science |
Volume | 321 |
Issue number | 2-3 |
DOIs | |
Publication status | Published - 2004 |