Problems & Puzzles:
Puzzles
Puzzle 84. Nonprimes
adding up to nonprimes (By TWA)
TWA
sent last week a fine and very interesting puzzle. He defined and proposed
to find the following set:
"The
least nonprime numbers such that the addition of all of them or any of
its subsets, produces only nonprime 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
preexisting 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
currentlyexisting 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.
So, the good new for those of you who are looking for the next
members oof these sets, the Nash's proof assures that there are
enough proper members of these sets out there somewhere (is anybody
going to make a code for putting in action the Nash's
proofalgorithm?) ...
***
Yesterday I wrote to Chris Nash the following:
"For the sake of the whole comprehension of your existence
proof for the amateurs (like me..:), why don't you calculate  let's
say  the 4th term of the sequences using your algorithm, just to see
it in action, and to see how larger the solution are (without any
attempt of optimizing) against the minimal one obtained by trial and
error."
This is his very kind answer:
"I think this is a great idea, so I'll do this right now.
I'll attempt it to all three of the sequences you suggest on the page.
1) 1, 8, 24, ???
First we list the sums of all the subsets: {0, 1, 8, 9, 24, 25,
32, 33}. First take p=2. We note 4 members of this set are equal to 0
modulo 2. So we choose Q=0 mod 2 (so Q plus any of these four members
is divisible by 2). We are left with {1,9,25,33}. Now take p=3. 2
members are 0 modulo 3, 2 are 1 modulo 3. We will choose Q=0 modulo 3,
and are left with {1,25}. For p=5, again we have a choice. 1 member is
0 modulo 5. So choose Q=0 modulo 5. We are left with {1}. Finally for
p=7, the last member is 1 modulo 7. So choose Q=6 modulo 7. Note at
each stage we had many choices and each would produce a different
result. So we solve
Q=0 mod 2
Q=0 mod 3
Q=0 mod 5
Q=6 mod 7
and we have Q=90+210k as a suitable solution. Q=90 works just
fine. (But this not the smallest).
The other two I will do more quickly :)
2) 1, 9, 15, ???. We need an odd answer, so Q=1 mod 2. The list
of sums is {0,1,9,10,15,16,24,25}. We can already eliminate the odd
members. We are left with {0,10,16,24}. p=3: 2 members equal to 0 mod
3. Choose Q=0 mod 3, we are left with {10,16}. p=5. 1 members equal to
0 mod 5. Choose Q=0 mod 5. We are left with {16}. p=7. 1 member equal
to 2 mod 7. Choose Q=5 mod 7. Q=75 works here. (Again not as good as
39, but again we had choices).
3) 1, 8, 24, ???. We need an even answer, Q=0 mod 2. The rest
follows as above and we find the solution Q=90.
***
