Problems & Puzzles: Puzzles

Puzzle 790. Prime Langford pairing

Let's start for the definitions.

I will use these found in the Wikipedia article related to this issue, "Langford pairing":

"In combinatorial mathematics, a Langford pairing, also called a Langford sequence, is a permutation of the sequence of 2n numbers 1, 1, 2, 2, ..., n, n in which the two ones are one unit apart, the two twos are two units apart, and more generally the two copies of each number k are k units apart. Langford pairings are named after C. Dudley Langford, who posed the problem of constructing them in 1958. Langford's problem is the task of finding Langford pairings for a given value of n.

The closely related concept of a Skolem sequence is defined in the same way, but instead permutes the sequence 0, 0, 1, 1, ...,n − 1, n − 1."

If we restrict to base 10 this last, the Skolem sequence (n<=10), sometimes called Skolem-Langford sequence, the quantity of solutions is finite and are the solutions are completely published in two versions, "weak" and "strong", in the OEIS site. "Strong" means here that all the digits from 0 to n-1 are present; while "weak" means here that some of these digits may be absent.
 

As a matter of fact there are 20120 weak solutions and 2820 strong solutions. From these, I have detected the following interesting prime solutions:

Category Prime
The smallest weak Skolem-Langford prime number 2742300437
The largest weak Skolem-Langford prime number (and EMIRP too!!!) 973006384792642181
The smallest strong Skolem-Langford prime number 2412134003
The largest strong Skolem-Langford prime number 7005264275346131

 

For the Langford sequence only strong version is generally accepted and no restriction to base 10 is present here. For example, from A014552 a solution for n=16: [16, 14, 12, 10, 13, 5, 6, 4, 15, 11, 9, 5, 4, 6, 10, 12, 14, 16, 13, 8, 9, 11, 7, 1, 15, 1, 2, 3, 8, 2, 7, 3] which provides the integer 1614121013564151195461012141613891171151238273, which unfortunately is not prime :-(

Q1. Find the smallest prime Langford sequence.
Q2. Find the smallest EMIRP Langford sequence.

 


Contribution cam from Emmanuel Vantieghem

***

Emmanuel wrote:

The Langford sequence which gives the smallest prime is :
10, 1, 11, 1, 12, 13, 14, 4, 6, 15, 5, 10, 4, 16, 11, 6, 5, 12, 9, 13, 8, 14, 3, 7, 2, 15, 3, 2, 9, 8, 16, 7
(the prime is 1011111213144615510416116512913814372153298167 but this is not an emirp).

The Langford sequence which gives the smallest emirp is :
10, 1, 11, 1, 12, 13, 5, 14, 16, 8, 4, 10, 5, 15, 11, 4, 9, 12, 8, 13, 3, 6, 14, 7, 3, 16, 9, 2, 6, 15, 2, 7.
 
I produced these sequences with a Mathematica program.  I can produce many sequences.  For instance, I made a list of 187 sequences all beginning with 10, 1, 11, 1, 12  that give primes when concatenated (and thus I believe will be the 187 smallest primes).  Of these primes, twelve of them are emirps. 

****


 

Records   |  Conjectures  |  Problems  |  Puzzles