login
Largest k such that there exists a decimal string of length n containing each of the first k primes as a subsequence.
1

%I #25 Feb 23 2018 11:27:36

%S 1,2,3,4,4,7,12,17,20,22,25,29,46,58,63,85

%N Largest k such that there exists a decimal string of length n containing each of the first k primes as a subsequence.

%H Carlos Rivera, <a href="http://www.primepuzzles.net/puzzles/puzz_896.htm">Puzzle 896: Optimal packing of a set of integers</a>

%e For n=1, "2" contains the first 1 prime as a subsequence, so a(1)=1.

%e For n=2, "23" contains each of the first 2 primes as a subsequence, so a(2)=2.

%e For n=3, "235" contains each of the first 3 primes as a subsequence, so a(3)=3.

%e For n=4, "2357" contains each of the first 4 primes as a subsequence, so a(4)=4.

%e For n=5, we cannot add any new primes as the 5th prime (11) requires two extra digits, so a(5)=a(4)=4.

%e For n=6, "112357" contains each of the first 7 primes (2 to 17) as a subsequence, so a(6)=7.

%e For n=7, "1231579" contains each of the first 12 primes (2 to 37) as a subsequence, so a(7)=12.

%Y Smallest strings are in A294268.

%K nonn,base,more

%O 1,2

%A _Dmitry Kamenetsky_, Feb 11 2018