Splitting 2018 into primes

Here is an algorithm to generate the minimal set $A_n$ that generates positive integers less than or equal to $n \in \mathbb{N}$ , in a sense asked by the question. From now on, when we say a set $A$ generates $n$ , it means that $A$ generates all integers less than or equal to $n$ .

Also define $S(A)$ of a set $A$ to be the sum of all the elements in $A$ .

obviously, $A_3=\{1,2\}$ is the minimal set that generates $3$ . Here is a recursive way of defining the minimal sets $A_{t}$

$A_{t+1}=A_{t} \ if \ S(A_{t}) \geq t+1$

$A_{t+1}=A_{t} \cup \{d\} \ , \ d=max\{p \ prime | p \leq t+1\} \ if \ S(A_{t}) < t+1$

it is not hard to see why the algorithm works (I am too lazy to write)!

But we are not interested in the sets, but their cardinality is of interest. So, we have:

$|A_3|=2$

$|A_{t+1}|=|A_{t}| \ if \ S(A_{t}) \geq t+1$

$|A_{t+1}|=|A_{t}| +1 \ if \ S(A_{t}) < t+1$

One can pass the algorithm to computer and realise that $11$ primes are enough.

---

Edit: As requested by @Otto Bretscher, I have added a part explaining why $10$ primes would not be enough.

Assume that there is a set of different primes $\{p_1,p_2, \dots , p_{10}\}$ that would generate $2018$ . We can, algebraically, write the possible numbers, generated by $\{p_1,p_2, \dots , p_{10}\}$ , as below

$x_0+x_1p_1+\dots + x_{10}p_{10}$

where $x_i \ \forall i$ is either zero or one. There would be a maximum of $2^{11}=2048$ possible numbers, generated by the above expression, when $x_i \ \forall i$ are changed. of course, some of the combinations amount to the same sum. Also, note that $\{2,3\}$ are inevitably in the set that generates $2018$ , otherwise numbers $2,3$ cannot be made. Finally pay attention to the two combinations below.

$x_0+x_1p_1+\dots + x_{10}p_{10}=1(1)+1(2)+0(3)+x_3p_3+ \dots + x_{10}p_{10}=3+x_3p_3+ \dots + x_{10}p{10}$

$x_0+x_1p_1+\dots + x_{10}p_{10}=0(1)+0(2)+1(3)+x_3p_3+ \dots + x_{10}p_{10}=3+x_3p_3+ \dots + x_{10}p{10}$

in the first one, coefficients $x_0,x_1,x_2$ are set to $1,1,0$ and the rest of the coefficients are free to vary. In a similar way, for the second one, coefficients $x_0,x_1,x_2$ are set to $0,0,1$ , while others are free. If we choose the same coefficients for the free variables, in both expressions, they both sum up to the same number. It means that there are at least $2^8=256$ (8 for 8 free variables) combinations that give a same sum that already exists. Therefore, there should be less than $2048-256=1792$ distinct sum, when $\{p_1,p_2, \dots , p_{10}\}=(2,3,p_3,\dots,p_{10})$ is taken as the generator. But we need it to generate $2018$ distinct numbers.

Beginning at 1 add integers to the set to enable every possible number that is less than or equal to 2018.

The integers 1 and 2 must be in the set as they are the only possible positive integers that can be used in any summation that will equal to 1 or 2. The sum of that very limited subset (1,2) is 3. Using elements from that subset (1,2) 1,2 or 3 can added to any other number to increase the total value by 1 ,2, or 3. The integer 3 would not be required in the full set to arrive at the value 3, but 4 is not a prime number and therefore cannot be included in the full. Set The largest prime number that is less than 4 is 3. 3 must be included in the full set of prime numbers to allow a total of 4 using prime numbers at most once in the sum.

Making successive additions to the full set of integers by including the largest possible qualifying integer (prime numbers only) to the set. Include the largest prime number that is less than or equal to the total sum of the integers in the subset of lesser integers. When the total of all the integers in the set is 2018 or greater that is all that is required. This process increases the range of the set by including the largest prime number that will allow all values to be reached using subsets of the previously include prime numbers combined with the additional larger prime..

determine the largest prime number that is less than or equal to 3 +1 =4

determine the largest prime number that is less than or equal to 6 +1 =7 ...

The most time consuming portion of this is finding the largest prime numbers that are smaller than or equal to the total set sums +1.