The Hungarian mathematician Paul Erdös posed the following problem. Consider the set S = {1, 2, ..., n} of integers from 1 to n. If A is a subset of S, then call A good if the sum of any two elements of A is not a perfect square. This includes the sum of an element of A with itself, so if x is in A then x + x cannot be a perfect square. (Recall that a perfect square is a number of the form a2, where a is also an integer. The first five perfect squares are 1, 4, 9, 16, and 25.) How large can a good subset be as a fraction of n? It has been shown that it is always possible to find a good subset of size approximately 11n / 32, and no good subset can be larger than 0.475n. We are concerned with actually finding reasonably large good subsets.
Dr. Les Reid of the Math department has suggested the following randomized method for generating large good subsets. Given n, we will maintain two sets A and C where A is a good subset and C is the set of all candidates that should be considered for inclusion in A. Initially A = {} and C = {1, 2, ..., n}. First remove from C all numbers that are half of a perfect square, e.g., for n = 100 remove 2, 8, 18, 32, 50, 72, and 98. Then repeat the following steps until C = {}: (1) randomly select an element x in C; (2) add x to A; (3) remove x from C; (4) remove from C all elements y such that x + y is a perfect square. The resulting set A is guaranteed to be good, and is likely to be quite large for small values of n.
Write a program that implements this method. The input will consist of one or more lines each of which contains a value of n such that 0 £ n £ 100. A value of 0 signals the end of the input. For each value of n, repeatedly apply the method until you find a good subset of size ceil(n / 3). Then display this good subset in the format shown in the examples.
Input must be read from the file prob43.in. Output must be written to the file prob43.out. All output to the screen will be ignored.
25 49 8 0
10: 1 6 9 12 14 15 16 17 20 25 18: 9 12 17 21 25 26 28 29 31 34 39 40 41 42 43 45 46 49 4: 1 4 6 8
Paul Erdös died on September 20, 1996. He is believed to be the most prolific mathematician in history, having published over 2,000 papers. The exact count is not yet known because he traveled continuously and often was working on as many as 50 research problems simultaneously with mathematicians around the world. Many papers will be completed posthumously by his colleagues.
Dr. Eric Shade