Seventeen lines and one-hundred-and-one points

Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)


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?
Original languageUndefined
Pages (from-to)415-421
Number of pages6
JournalTheoretical computer science
Issue number2-3
Publication statusPublished - 2004


  • Algorithmic number theory
  • IR-76359
  • Polynomial time algorithm
  • METIS-219741
  • Geometry

Cite this