Consecutive Sum

A consecutive sum is a sum of at least two consecutive positive integers. 4+5+6 is a consecutive sum leading to 15, for example. For any given positive integer, you are to determine EVERY consecutive sum leading to that integer. For example, 15 can be attained by 1+2+3+4+5, by 4+5+6, and by 7+8.

Input Specification

The input will contain a series of test cases, followed by a line containing a single 0. Each test case is a line consisting of a single decimal integer between 1 and 1 000 000 inclusive.

Output Specification

The test cases should appear in the output in the order in which they appear in the input. For each input N, every consecutive sum leading to N must be printed. DO NOT print out every number in the sum. Each sum should be printed out in the following manner: the lowest number in the sum, one space, the highest number in the sum, and a newline character. If a test case generates more than one consecutive sum, they must be printed in order of length, starting with the longest sum and ending with the shortest sum. After all consecutive sums for a test case has been printed, an extra newline character should be printed following them. If a number has no consecutive sum, then no consecutive sum can be printed, but the extra newline character described in the previous sentence should still be present.

Sample Input

1. 15
2. 10000
3. 0

download as text file

Output for Sample Input

1. 1 5
2. 4 6
3. 7 8
5. 18 142
6. 297 328
7. 388 412
8. 1998 2002

download as text file

Original Problem

NMU Invitational Programming Contest, 2000