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

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

Title of host publication | Algorithms - ESA 2003 |

Subtitle of host publication | 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings |

Editors | G. Di Battista, U. Zwick |

Publisher | Springer |

Pages | 527-531 |

ISBN (Electronic) | 978-3-540-39658-1 |

ISBN (Print) | 978-3-540-20064-2 |

DOIs | |

Publication status | Published - 2003 |

Event | 11th Annual European Symposium on Algorithms, ESA 2003 - Budapest, Hungary Duration: 16 Sep 2003 → 19 Sep 2003 Conference number: 11 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 2832 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 11th Annual European Symposium on Algorithms, ESA 2003 |
---|---|

Abbreviated title | ESA |

Country | Hungary |

City | Budapest |

Period | 16/09/03 → 19/09/03 |

## Keywords

- METIS-213364