# Seventeen lines and one-hundred-and-one points

Woeginger, Gerhard J.
(2004)
*Seventeen lines and one-hundred-and-one points.*
Theoretical Computer Science, 321
(2-3).
pp. 415-421.
ISSN 0304-3975

PDF
Restricted to UT campus only : Request a copy 182kB |

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

Item Type: | Article |

Copyright: | © 2004 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/76359 |

Official URL: | https://doi.org/10.1016/j.tcs.2004.04.006 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 219741