Seventeen lines and one-hundred-and-one points

G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)


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 languageEnglish
Pages (from-to)415-421
JournalTheoretical Computer Science
Issue number2-3
Publication statusPublished - 2004


Dive into the research topics of 'Seventeen lines and one-hundred-and-one points'. Together they form a unique fingerprint.

Cite this