### 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?

Original language | Undefined |
---|---|

Pages (from-to) | 415-421 |

Number of pages | 6 |

Journal | Theoretical computer science |

Volume | 321 |

Issue number | 2-3 |

DOIs | |

Publication status | Published - 2004 |

### Keywords

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

## Cite this

Woeginger, G. (2004). Seventeen lines and one-hundred-and-one points.

*Theoretical computer science*,*321*(2-3), 415-421. https://doi.org/10.1016/j.tcs.2004.04.006