Al Zimmermann's Programming Contests

Prime Sums

Additive and Substractive Sets Generating Primes

suggested by James J. Youlton Jr
variant suggested by Joe Zbiciak

Introduction

Submit sets of positive integers so that their combination by addition and substraction generates the most distinct primes.

The Problem

Find n positive integers such that the 3n-1 sums made from all combinations sum ai*ci yield as many distinct primes as possible.
ci may assume any of the 3 values -1,0,1.

Alternative formulation:
Maximize the number of distinct primes within the 3n-1 sums
sum_i=1,..,n (ai*ci,k) where the coefficients ci,k run over all possible combinations of -1,0,1.

There are 12 separate problems n=3,4, ..., 14.

Your result has to be submitted as a list of numbers separated by spaces.
Note: all characters other than digits will be replaced by spaces.

The Scoring System

The "value" of a submission is the number of distinct primes among the 3n-1 sums.
0 and 1 are not primes.
Your score for a given n is computed by:
R = the current record for the given N
S = your result for the given N
Q = log10(1-(S/R))
Score = Q/(Q-1)

There are 12 separate problems n=3,4, ..., 14. Therefore the maximum achievable score is 12.

Submitting

You may submit as many solutions as you want, for any n within the range 3<=n<=14.
The number of submissions has no influence on the score.
The sum of all the numbers must not exceed 232-1.
Submissions containing less than 3 or more than 14 numbers are rejected by the scorer.
The entries of a solution may be submited in any order, i.e. "10 20 31 50" or "50 10 31 20" are both valid and equivalent submissions for n=4.
The numbers in the submission have to be separated by at least one non-digit character.
Any non-digit character will be converted into a space.

When you submit a solution that produces less prime sums than a previous solution you had submitted before for the same n, your score remains unchanged.
If more than one team has the same total score based on the score sum computed with high precision at the end of the contest, the ranking for this score will be done based on the time when the affected teams submitted the last solution improving their score (earlier is better).
The ranking is always based on high precision scores, although scores are only displayed with 4 decimal digits.

Whenever a participant submits a solution that is better than the current best solution for a given n, the corresponding scores of all participants are recomputed and adjusted immediately.

Scoring example:
Let us assume that the best submission for n=4 is "8, 41, 52, 78" producing 16 distinct primes, submitted by participant B.
Participant A makes his first submission for the category n=4.
He submits the 4 numbers "18, 23, 27, 43" thus producing 10 distinct primes among the 80 possible sums.
Then A's score for n=4 is computed by Q=log10(1-10/16)=-0.425969, Score=Q/(Q-1)=-0.425969/(-0.425969-1)=0.2987
Later participant C submits "24,30,36,77" producing a new record with 17 distinct primes.
C gets a score of 1.0 for n=4.
A's score for n=4 drops from 0.2987 to 0.2782, i.e. A will see a reduction of his total score by 0.0196.
The total score of the previous record holder B will drop significantly by 0.4483, because the updated score for his 16 primes submission becomes 0.5517, computed by Q=log10(1-16/17)=-1.230449, Score=-1.230449/-2.230449=0.5517.

Example for determining the "value" of a solution:

For n=3 it is sufficient to check the following sums if an ordered submission with a1>=a2>=a3 is assumed:
a1, a2, a3,
a1+a2, a1-a2, a1+a3, a1-a3, a2+a3, a2-a3,
a1+a2+a3, a1+a2-a3, a1-a2+a3, abs(a1-a2-a3)

For n=4, the submission "10 29 82 106" produces 9 distinct primes:

5 = 106 + 10 - 82 - 29
19 = 29 - 10
29 = 29
43 = 82 - 29 - 10
53 = 82 - 29
67 = 106 - 29 - 10
101 = 82 + 29 - 10
149 = 106 + 82 - 29 -10
227 = 106 + 82 + 29 + 10

Total Scoring

Your score is the sum of all single problem scores.
Since there are 12 problems, the best total score you can get is 12.
If you do not submit for a particular N, you will receive a 0 for that N.

Prizes

Sculptures by the renowned artist Bathsheba Grossman.
Those of you who have access to American television may have seen one of her sculptures, the 4-dimensional analog of the dodecahedron projected onto 3-space, on "Numb3rs".

The contest winner will be able to choose any sculpture from either of these two pages:

The second place contestant will select from these two pages:
All sculptures will rest on a wooden base with an appropriately inscribed plaque.

Organization

As the organizers, we may change the rules during this contest.

Thanks

Special thanks to:

Questions ?
Return to the index