cp's OEIS Frontend

A332088 Primes which yield again a prime when the digits are taken according to the lexicographically first superpermutation of corresponding order and of minimal length.

%I A332088 #20 Jan 15 2023 19:50:01
%S A332088 2,3,5,7,13,19,31,37,79,109,113,139,193,317,331,911,991,1453,1481,
%T A332088 1669,1831,1901,7127,7561,7589,7687,9343,9413,9811,11369,13397,19759,
%U A332088 19961,31397,33181,33809,37567,39089,41017,41257,41399,49633,59921,61651,67409,77573,81131,83621,87011,91837,93493,97127
%N A332088 Primes which yield again a prime when the digits are taken according to the lexicographically first superpermutation of corresponding order and of minimal length.
%C A332088 See A180632 for more about superpermutations, i.e., strings over a finite alphabet, say {1, ..., n}, that contain all permutations thereof as a substring. "Digits taken according to ..." means the number whose i-th digit is d[s[i]], 1 <= i <= A180632(#d), where d and s are the sequences of digits of the prime and of the superpermutation, respectively.
%C A332088 In March 2014, Ben Chaffin showed that minimal superpermutations of order n = 5 have length 153, and found all 8 distinct superpermutations of this kind (the lexicographically first being non-palindromic), so the 5-digit terms are known. For n = 6, Robin Houston has found a few months later several superpermutations of length 872 (one less than the previously conjectured minimal length), but we still don't know which is the shortest (and/or lexico-first) superpermutation for that case.
%C A332088 This is a variant of A244311, which (by definition) lacks single-digit terms and which uses the easily computed palindromic superpermutations produced by the classical recursive algorithm (see PARI code there), of non-minimal length A007489(n) for n > 5 and non-minimal lex order for n = 5. The lexico-first minimal-length superpermutations aren't palindromic, and therefore the corresponding primes aren't so here, in contrast to A244311.
%H A332088 Robin Houston, <a href="http://arxiv.org/abs/1408.5108">Tackling the Minimal Superpermutation Problem</a>, arXiv:1408.5108 [math.CO], 2014.
%H A332088 Nathaniel Johnston, <a href="http://arxiv.org/abs/1303.4150">Non-uniqueness of minimal superpermutations</a>, arXiv:1303.4150 [math.CO], 2013; Discrete Math., 313 (2013), 1553-1557.
%H A332088 Wikipedia, <a href="http://en.wikipedia.org/wiki/Superpermutation">Superpermutation</a>
%e A332088 The superpermutations with minimal length of less than 5 objects are unique (up to the choice of the symbols), the one for 3 objects is "123121321".
%e A332088 The prime p = 109 is in this sequence since under the above superpermutation (i.e., taking the 1st, 2nd, 3rd, 1st, 2nd, 1st, 3rd, 2nd and 1st digit) it yields the number 109101901 which is also prime.
%e A332088 The minimal superpermutation of order 5 is the first one to be not palindromic, it reads "1234512...3254312". Correspondingly, when this "acts on" the 5-digit prime p = 11369, we get a non-palindromic 153 digit prime P = 1136911...3196311 whose 7th digit from the left is p's 2nd digit, '1', but whose 7th digit from the right is p's 3rd digit, '3'.
%o A332088 (PARI) SP=[digits(p) | p <- [1, 121, 123121321, 123412314231243121342132413214321, fromdigits( [d-37| d<-Vecsmall( "&<R1G4<N>G1HN<3Y2OXG:ZO2[:GY3H:RE3YDOZ3<XOD[<1RD=H1P4=D>P:[EXP>NER2=4ENH=2>P1")], 100)]] /* minimal superperms up to n=5, in custom base100 encoding for n=5 for lack of algorithm and to avoid the 153-digit decimal number */
%o A332088 is_A332088(n)=ispseudoprime(fromdigits(vecextract(n=digits(n),SP[#n])))
%o A332088 (A332088_upto(N)=select( is_A332088, primes([1,N])))(10^5)
%Y A332088 Cf. A180632 (length of the superpermutations and primes related to n-digit terms), A007489 (upper bound and corresponding lengths in A244311), A244311 (a variant of this sequence), A224986 (related to the difference between A180632 and A007489).
%K A332088 nonn,hard,base
%O A332088 1,1
%A A332088 _M. F. Hasler_, Jul 28 2020