Problems & Puzzles: Puzzles

Puzzle No. 49.- “If you are given K numbers of each from 0 to 9, find the maximum quantity of primes that can be formed using those 10K numbers”.

Comments:

It’s obvious that the upper limit to the quantity of primes asked is 4K+2. Less obvious is how many can be effectively obtained for every particular K.

Using a code that materializes a strategy developed by my friend Jaime Ayala, I have gotten the following results:

a)     For K=1 to 6 the primes that can be effectively obtained match the upper limit.

b)     For K>6 the maximum quantity of primes that can be effectively obtained is less than the upper limit.

c)      For any K the set of primes – solution is not unique; that is to say, several distinct sets of primes share the same maximum quantity of primes that can be effectively obtained.

d)     Except for K=8, and according to the Ayala's strategy (and/or my code of it) there are always some numbers (digits) unused.

Examples:

For K= 1, the upper limit is 6 and the set of primes that can be formed is {2, 3, 5, 7, 41, 89} remaining unused two digits, one “0” and one "6".

For K= 2, the upper limit is 10 and the set of primes that can be formed is {2, 3, 5, 7, 23, 41, 47, 59, 61, 89} remaining unused four digits, two “0”, one "6" and one “8”.

The rest of our results are summarized in the following table:

Can you improve the above results, that is to say, can you obtain more primes and/or decrease the digits unused?

Of course that what we are looking for here is not a “hand & eye” procedure but a strategy that may generate a code for PC.

Anurag Sahay wrote (May, 2005):

Today I started working on puzzle 49. I did not use the computer to solve it, because , for this puzzle I cannot think of any algorithm which is more efficient (and quicker!) than the human brain!...I got a better ( 156 primes) count for k=50 (1 digit unused : 1): (I am sure this is not the best: I guess 160 is reachable).

Here is the solution( 156 primes) :

2 3 5 7 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 409
283 383 487 859 197 241 457 281 659 269 277 127 193 593 719 359 107 103 701 167 211 149 347 367 307 389 653 691 643 547 907 461 647 887 229 823 809 509
601 2003 607 827 421 463 503 683 109 863 857 263 523 569 491 2053 853 9001 5009 2039 401 941 967 271 557 467 443 881 829 839 541 2269 2543 2647 2459 2467 2861
2083 1009 3001 3457 2089 4801 4651 4421 4663 5503 4021 4007 4003 4561 4567 4649 5021 5281 5081 5483 5227 5347 5437 6287 6857 6481 6521 6529 6469 6823 6827 6829
7589 7103 8089 8009 8059 8053 8069 8081 8243 8263 4909 8209 8623 8563 8627 8647 5531 4027 4001 4201 6607 5569 2659 521

***

Anurag Sahay requested to describe the strategy used by Jaime Ayala and me to produce the results of the Table above.

Fortunately we lost both the code and the strategy. This gave us the opportunity to rediscover both things (and drink a couple of beers together!). The new strategy is this one:

First one definition.

A prime type "024568" is a number whose decimal digits, except the right-most one, are exclusively one of the following ones: 0, 2, 4, 5, 6, 8.

Startegy/Algorithm:

Given the K value, vary n from 4 to 2*K and do this:

Step 1: from 2 to p(n) accept all these (obliged) primes.

Step 2: from p(n+1) to p(12000) accept all the primes type "024568" without violating the limit of the accumulated digits.

Step 3: from p(n+1) to p(12000) accept all the unused primes without violating the limit of the accumulated digits.

(Step 2 or/and 3 may end before the p(12000) if all the "1", "3", "7", "9" digits accumulated are exactly K.)

Count the total primes (TP) accepted and print the results if you have gotten a larger TP. Otherwise next n until 2*K.

Using a code that reflects this strategy, we have gotten the following results:

Here are our results for K=50 (the slash points out the finish of one step of the strategy and the beginning of the next one):

K= 50; primes max = 202; total primes= 156; n=46
Digits max= 500; digits used= 499; unused digits= 1

2- 3- 5- 7- 11- 13- 17- 19- 23- 29- 31- 37- 41- 43- 47- 53- 59- 61- 67- 71- 73-
79- 83- 89- 97- 101- 103- 107- 109- 113- 127- 131- 137- 139- 149- 151- 157- 163
- 167- 173- 179- 181- 191- 193- 197- 199-/ 223- 227- 229- 241- 251- 257- 263- 269-
281- 283- 401- 409- 421- 443- 449- 457- 461- 463- 467- 487- 503- 509- 521- 523-
541- 547- 557- 563- 569- 587- 601- 607- 641- 643- 647- 653- 659- 661- 683- 809-
821- 823- 827- 829- 853- 857- 859- 863- 881- 883- 887- 2003- 2027- 2029- 2053
- 2063- 2069- 2081- 2083- 2087- 2089- 2203- 2207- 2243- 2267- 2269- 2287- 2423-
4003- 4007- 4049- 4057- 4409- 4447- 4457- 4463- 4483- 4507- 4547- 4549- 4567-
4583- 4603- 4643- 5003- 5009- 5059- 5087- 5503- 5507- 5557- 5563- 5569- 5653- 6007
- 6067- 6089- 6607- 6689- 6803- 6869- 8009- 8069- 8669- 8689- 8867- 8887-/ 6899-
8999- 89899

***

Regarding this strategy & results we don't claim that it will produce the largest total primes for a given K value. At the most we claim that with these very simple rules we can get results very close to the largest possible ones, without too much pain (that is to say, mechanically in a few seconds)

Example 1: while with this strategy for K=20 we find at the most TP=72, Jaime Ayala has found 'by another route' a set of TP=73:

K= 20; primes max= 82; total primes= 72; n=22
digits max= 200 digits used= 196 unused digits= 4

2- 3- 5- 7- 11- 13- 17- 19- 23- 29- 31- 37- 41- 43- 47- 53- 59- 61- 67- 71- 73-
79-/ 83- 89- 223- 227- 229- 241- 251- 257- 263- 269- 281- 283- 401- 409- 421-
443- 449- 457- 461- 463- 467- 487- 503- 509- 521- 523- 541- 547- 557- 563- 569-
587- 601- 607- 641- 643- 653- 659- 661- 683- 809- 827- 857- 887- 6089- 8009- 8069
- 8089- 80809-/ 80909-