Problems & Puzzles: Puzzles

Puzzle 678 Find the least vector of integers such that... Vicente Felipe Izquierdo Gamez sent the following nice puzzle. Find the vector of minimal lenght L such that you can find all the prime numbers from p(1) to p(n) concatenating contiguous elements of the asked vector. For n=20, the solution found by Felipe is L=25: {2, 3, 5, 3, 6, 1, 7, 1, 4, 1, 1, 3, 1, 9, 2, 9, 4, 3, 7, 4, 7, 5, 9, 6, 7} Q1. Verify the solution for n=20 or send a shorter one for n=20 (L<25). Q2. Find the solutions for n=30, 40, 50, ... or simply send your largest one solution.

---

Contributions came from Giovanni Resta, J. K. Andersen, Alexandre Patarot & Hakan Summakglu.

***

Giovanni wrote

Puzzle 678 is almost identical to puzzle 408.

***

Andersen wrote

The smallest solution for n = 1 to 17 is in http://oeis.org/A054261

***

Alexandre wrote

My largest solution is n=125 with L=263:
2,1,1,0,1,0,3,0,7,2,2,3,1,1,2,2,7,2,2,9,2,3,3,1,3,1,7,2,3,9,2,4,1,0,7,2,5,1,0,9,2,5,7,2,6,3,3,1,2,6,9,2,7,1,1,3,3,
7,2,7,7,2,8,1,2,7,2,8,3,4,7,2,9,3,4,9,4,0,1,3,1,3,7,4,0,9,4,1,9,4,2,1,3,9,4,3,1,4,9,4,3,3,5,3,5,9,4,3,9,4,4,3,6,7,
4,4,9,4,5,7,4,6,1,5,1,5,7,4,6,3,7,3,7,9,4,6,7,4,7,9,4,8,7,4,9,1,6,3,8,3,8,9,4,9,9,5,0,3,9,7,5,0,9,5,2,1,6,7,5,2,3,
5,4,1,7,3,5,4,7,5,5,7,5,6,3,5,6,9,5,7,1,7,9,5,7,7,5,8,7,5,9,3,5,9,9,6,0,1,8,1,9,1,9,3,6,0,7,6,1,3,6,1,7,6,1,9,6,3,
1,9,7,6,4,1,9,9,6,4,3,6,4,7,6,5,3,6,5,9,6,6,1,6,7,3,6,7,7,6,8,3,6,9,1

Later he added:

In the file attached are the solutions I found for all n between 1 and 1000, as well as a graph representing L as a function of n.

***

Hakan wrote

Q1: For n=20, smallest length is 25.Because;

First 4 prime (2,3,5,7) are located in other primes.

There isn't prime beginning with 2,4,6.

So 23,29,41,43,47,53,59,61,67 are incompressible and need 18 digits.

There are other 7 primes (11,13,17,19,31,37,71) need at least 7 new digits, each of one digit.

(example; 11: 41-1, 31:43-1, 71: 67-1)

Therefore smallest L=18+7=25.
 

Q2:

For n=30, L=42:

{1,7,9,1,9,2,3,4,1,0,3,7,3,4,3,4,7,5,3,6,1,1,3,1,0,9,7,1,0,1,0,7,6,7,8,3,8,9,2,9,5,9}

For n=40, L=66:

{1,7,1,9,1,1,3,1,2,7,1,3,7,1,3,9,1,4,9,1,5,7,1,6,3,1,6,7,1,7,3,2,3,4,1,0,1,3,1,5,1,0,

3,4,3,4,7,5,3,6,1,0,7,1,0,9,8,3,8,9,7,9,2,9,5,9}

For n=50, L=87:

{1,7,1,9,1,2,7,1,3,7,1,3,9,1,4,9,1,5,7,1,6,3,1,6,7,1,7,3,1,7,9,1,9,3,1,9,7,1,9,9,

2,2,3,2,2,7,2,2,9,4,1,1,0,1,3,1,5,1,8,1,9,1,0,3,4,3,4,7,5,3,6,1,0,7,1,0,9,2,1,1,

3,8,3,8,9,5,9}

***