Problems & Puzzles: Puzzles

Puzzle 84.- Non-primes adding up to non-primes (By TWA)

TWA sent last week a fine and very interesting puzzle. He defined and proposed to find the following set:

"The least non-prime numbers such that the addition of all of them or any of its subsets, produces only non-prime numbers".

TWA and myself have found the first 10 members of this set: 1, 8, 24, 25, 86, 1260, 1890, 14136, 197400, 10467660,…?

I have added one more condition to the members of the before set: to be odd numbers; and these are the first members of the new set: 1, 9, 15, 39, 105, 731, 2805, 59535, …?

Finally, if the condition is that all the members are even, except the first one (1), the first members are: 1, 8, 24, 86, 90, 780, 5940, …  

1)    Can you extend these sequences?

2)    Can you argue if these sequences are finite or infinite?

Solution

Chris Nash has solved the part 2) of this puzzle, demonstrating that all thes sets asked contain infinite members. It's "existence" proof also serves as a tool for calculating at least other member to a pre-existing set. This is his proof (but before please use your reinforced glass lenses...:-)

"We will show that given a set S, with n elements, such that the sum of elements in all subsets is composite, the set can be extended by the addition of another element preserving the same property.

S has 2^n subsets, including the empty set. Let the sums of these subsets be s_0=0, s_1, s_2, s_3... and so on. We construct a list of congruences as follows.

Let T={s_0, s_1, s_2, s_3, s_4.......} be the set of all the currently-existing sums. while T is not empty choose an odd prime p. The primes chosen at this stage are all distinct. Find x_p suct that x_p+s_i=0 mod p has some solutions for s_i in T. (Choosing x_p so the most s_i are in T may be efficient, but will not necessarily find the smallest solution). Write down Q=x_p mod p, and remove those s_i from T.

Since at least one element is removed from T at every step, the algorithm  terminates with a set of congruences Q=x_p mod p for several distinct primes p. By the Chinese Remainder Theorem, these congruences have an infinite number of solutions in arithmetic progression, and an infinity of these solutions are composite. If you require odd solutions, add Q=1 mod 2 to the set of equations.

To prove this works, note that the new set S has all the original subsets, plus 2^n new subsets formed by adding Q to an original subset. Since each s_i was eliminated in the algorithm for some prime p, Q+s_i is divisible by p and hence is composite. (if Q+s_i=p, simply choose the next solution for Q).

Note this is only an existence proof, but it shows a means of finding a solution (not necessarily the smallest one).

For instance, consider 1, 8, 24, 86, 90, 780, 5940. There are 64 subsets. Choose p=3. We may choose x_3 to eliminate at least 1/3 of the elements in T. So at least 22 elements are eliminated, and we are left with 42. For p=5, we eliminate at least 9 more from the 42. So we are left with 33. For p=7, we eliminate at least 5 more, leaving 28. For p=11, we eliminate at least 3, leaving 25. p=13,17,19 each eliminate at least 2, leaving 19. At most the next 19 primes are needed to finish the construction.

The solutions for Q are in arithmetic progression. The first term is less than the product of these primes, the difference is the product of these primes. If the product is P, a composite solution Q exists that is less than P^2 (if a+nP is an arithmetic progression, put n=a to get a composite term). Note that P^2 is extremely large, so I'm sure people will find much smaller solutions! (I am not attempting that part as this is only the first day of the new puzzle).

Note the problem can in fact be made MUCH harder, and there will still be infinite sequences. For instance, you may add the condition not only do all the sums of subsets need to be composite, but they can have no factor in common - simply choose a prime and a value x in the construction above that only has one solution to x+s_i=0 mod p.