split 2,3,5 into 2 groups: (2,5) and (3) the difference of their products 2x5-3 = 7.
split 2,3,5,7 into 2 groups (3,7) and (2,5) the difference is 11. Note that (2,7) and (3,5) has a difference of 1 so don't go there.
5x11 - 2x3x7 = 13
Is it always possible to create a partition that produces the N+1th prime?
AFAIK this is a problem of my own conjuring, but I also know that most such things already exist and have a name.
Here's a list of results for the first N primes, for different Ns:
I just wrote a script to brute force all combinations here, so the 24th iteration got very slow, but of all those the nonprime ones are n=23, 19, 18, 16, 14, and 13.
So, your rule appears to hold true as long as N is less than the cube of the Nth prime. The actual rule is probably more complex than a simple power, considering 83^5 is far less than the result in N=23.
I think I'll play with this a bit more this evening then ping some mathematician friends about it. They always love playing with weird properties of primes.
Maybe, but the result is obviously guaranteed to not be a multiple of any of the N primes. Since the smallest factor has to be greater than N, that means prime for up to N^2 (or (N+1)^2 I suppose).
I don't recall. I don't think I went beyond the use of 32bit integers (or was it 64) when I first looked at it, so not very large. The intermediate products can get quite big quickly. I do remember using a binary number to represent group membership of each prime, and seeing a pattern that broke down after only a few primes.
His point was: It it simple to prove that those subsets must exist, but it is very hard to compute them. To make his point even more clear, he offered some prize money if anyone found an explicit solution.
A friend told me about that challenge, and I tried. With a lot of conceptual work, programming, optimization and some luck I was finally able find such a solution (and received the prize):
(Sorry, German language, but the solution is readable, I guess :-))
1) There are 90 numbers, so we have 2^90 subsets.
2) All numbers are < 10^25, so the sum of all 90 numbers is < 90 * 10^25 < 10^27. So each sum of a subset is an integer in the range of 0 to 10^27-1. So we have ≤ 10^27 possible sum values.
Since 2^90 > 10^27, we have more subsets than possible sum values. Hence, there are at least two subsets having the same sum.
BTW, this is a beautiful application of the Pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle
Edit: wait I think I've got it:
Each subset implicitly also chooses it's counter subset, e.g. if you choose the subset consisting of the first 45 numbers, you've also therefore said the other subset consists of the last 45 numbers. Since there are more of these "dual subsets" than possible sums, the pigeonhole principle yadda-yadda.
You are not forced to use all numbers. (And in fact, my explicit solution doesn't use all numbers.) There is no restriction that the union of both subsets must be equal to the full set. Note that this restriction would change the question dramatically. See also: https://news.ycombinator.com/item?id=10023098
Also note that it is allowed for both chosen subsets to overlap. In fact, the proof just says that two different (i.e. not entirely equal) subsets with the same sum exist.
However, once you have a pair of different overlapping subsets of the same sum, you can simply remove the intersection from both sets. Both sums decrease by the same amount. You then get a pair of two disjoint sets that have the same sum.
And no, I don't think the proof would not work when requiring the two subsets to form a partition. Also note that for partitions, the number of sums would be one, as the only possible sum is half of the sum of all numbers. (And the problem would be unsolvable if the sum of all numbers was odd, but all numbers were still integers.)
(I didn't realize you were allowed to use each number in both subsets, so I have no idea if I would have figured it out or not on my own.)
Why? (Obviously you wouldn't compute it so what's the "trick"?)
Even though my math muscles haven't been exercised in a decade this article was easy to grasp.