K	4K + 2	Num Primes	% of upper bound
1	6	6	100.00%
2	10	10	100.00%
3	14	14	100.00%
4	18	18	100.00%
5	22	22	100.00%
6	26	26	100.00%
7	30	29	96.67%
8	34	33	97.06%
9	38	36	94.74%
10	42	39	92.86%
20	82	73	89.02%
50	202	159	78.71%
100	402	295	73.38%
150	602	423	70.27%
200	802	543	67.71%
250	1002	659	65.77%
300	1202	776	64.56%
350	1402	893	63.69%
400	1602	1008	62.92%
450	1802	1117	61.99%
500	2002	1226	61.24%
550	2202	1335	60.63%
600	2402	1444	60.12%
650	2602	1553	59.68%
700	2802	1662	59.31%
750	3002	1769	58.93%
800	3202	1875	58.56%
850	3402	1980	58.20%
900	3602	2084	57.86%
950	3802	2185	57.47%
1000	4002	2285	57.10%

and this:

I did some work about Puzzle 49 / Puzzle 1276, addressing two aspects: 

1) reliable automated search of "optimal" solutions;
2) derivation of "sharp" upper bounds.
This message is about improved solutions and search algorithms, answering questions mainly from puzzle 49.

I plan to write another message about upper bounds.

For K = 1 to 10, 20, and 50, I could only match the Quantity of primes obtained from previous solutions.
But I was always able to build solutions with no Unused digits, a further task which was asked within Puzzle 49.
Here are such solutions for K = 1 to 6, where the upper bound Q = 4*K+2 was reached.

K = 1, Q = 6, U = 0:
2, 3, 5, 67, 89, 401.

K = 2, Q = 10, U = 0:
2, 5, 7, 59, 61, 67, 83, 283, 401, 409.

K = 3, Q = 14, U = 0:
2, 3, 5, 7, 59, 61, 67, 89, 263, 281, 401, 409, 487, 503.

K = 4, Q = 18, U = 0:
2, 3, 5, 7, 29, 41, 61, 67, 83, 89, 263, 281, 401, 409, 467, 503, 509, 587.

K = 5, Q = 22, U = 0:
2, 3, 5, 7, 23, 29, 41, 47, 61, 67, 83, 89, 281, 283, 401, 409, 467, 503, 509, 569, 587, 601.

K = 6, Q = 26, U = 0:
2, 3, 5, 7, 23, 29, 41, 47, 53, 59, 61, 67, 83, 89, 269, 281, 283, 401, 409, 461, 487, 503, 509, 587, 601, 607.

I  wish to submit the following updated/new results:
K     Q    (Qold)
30    103  (102)
40    131  (129)
100   295  (285)
150   423  (420)
200   543  (new)
Again, for each claimed Quantity of primes, I built a solution with no Unused digits (see attached file Pu1276solsOV.txt).

Search strategy.
Formulation of the search as an integer linear programming (ILP) problem, and use of existing ad-hoc software capable of solving such family of problems; I chose GNU Octave.

Pick some upper bound pmax; candidate solutions will only include primes p <= pmax.
For every prime p <= pmax, count the occurrences of each digit from 0 to 9, obtaining a counting vector C = [c0,c1,...,c9].
For compactness, primes with the same counting vector are grouped together, obtaining m sets S_1, S_2, ..., S_m.
Let t_i be the cardinality of set S_i, and C_i = [c0_i,...,c9_i] be its shared counting vector.
As an example, we may have set {113,131,311}, with cardinality 3 and counting vector [0,2,0,1,0,0,0,0,0,0].
A solution is obtained by assigning permitted values to m integer variables x_1, x_2, ..., x_m.
Variable x_i specifies how many distinct primes must be picked from set S_i, so inequality 0 <= x_i <= t_i holds.
The cumulative occurrences of each digit from 0 to 9 are also constrained:
c0_1*x_1 + c0_2*x_2 + ... + c0_m*x_m <= K,
c1_1*x_1 + c1_2*x_2 + ... + c1_m*x_m <= K,
...
c9_1*x_1 + c9_2*x_2 + ... + c9_m*x_m <= K.
The objective function to maximize is the Quantity of primes obtained:
Q = x_1 + x_2 + ... + x_m.
Objective and constraints are all linear functions of the integer variables x_i.
Existing specialized ILP software receives the coefficients of objective and constraints as imput, then it computes values x_i which maximize Q.
Note: the output will be the best value Q under the current choice of bound pmax, maybe larger bounds would provide better solution.

All solutions mentioned above were obtained by using pmax=10^5; increasing pmax to 10^6 resulted in no improvement.

Once an interesting quantity of primes Q was found to be achievable, I searched for solutions with the largest possible quantity of used digits D by solving an "extended" ILP problem.

Additional constraint:

x_1 + x_2 + ... + x_m = Q.

New objective function to maximize:

D = d_1*x_1 + d_2*x_2 + ... + d_m*x_m,

where coefficient d_i = c0_i + c1_i + ... + c9_i  is the shared total digit count of primes from set S_i.

About question Q2 of puzzle 1276, I claim that the upper bound 4*K+2 is far too optimistic: the fraction of primes that can actually be formed asymptotically drops to zero as K increases.

It's simpler to reverse the question and to find the minimum quantity of arbitrary digits needed to form N distinct primes; the lower bound is clearly obtained by choosing the N smallest possible primes 2, 3, ..., prime(N).

Therefore, ratio  Bound2(K)/Bound1(K)  converges to 1 asymptotically.

Similarly, ratios Bound1(K)/(4*K+2) and Bound2(K)/(4*K+2) have the same asymptotic behaviour. In particular, they both decrease as  a/ln(a*k), so they converge to zero.

Comparison between new bounds and best solutions found so far:

K     Bound1    Bound2   Q
1     7     7.341     6
2     12    12.025    10
3     17    16.310    14
4     22    20.364    18
5     26    24.258    22
6     29    28.033    26
7     33    31.713    29 
8     36    35.315    33 
9     39    38.852    36 
10    43    42.333    39 
20    76    75.096    73 
30    109   105.658   103 
40    143   134.940   131
50    174   163.335   159 
100   299   297.423   295 
150   424   423.932   423 
200   549   545.964   543 

200                                          802                                                          543                                                          67.7057%

300                                        1202                                                          776                                                          64.5591%

500                                        2002                                                        1226                                                          61.2388%

1000                                      4002                                                        2285                                                          57.0965%

2000                                      8002                                                        4285                                                          53.5491%

5000                                    20002                                                        9895                                                          49.4701%

10000                                  40002                                                      18503                                                          46.2552%

20000                                  80002                                                      35168                                                          43.9589%

30000                                120002                                                      51515                                                          42.9285%

40000                                160002                                                      67251                                                          42.0313%

50000                                200002                                                      82709                                                          41.3541%

100000                              400002                                                    155645                                                          38.9111%     

All prime sets can be found in the attached txt file.