A397619 Number of permutations p of [n] such that p(i)*p(i+1) + 1 is prime for all 1 <= i <= n-1.

1, 1, 2, 2, 8, 4, 40, 40, 56, 88, 1288, 1040, 18200, 17600, 158194, 173100, 2218366, 817516, 45303282, 4998932, 51800326, 59441320, 3931035158, 1206962488, 57085150898, 25000385878, 1011984855438, 696555511396

Offset

0,3

Comments

Since reversals are counted separately, a(n) is even for n>=2. No two odd numbers can be adjacent, as odd * odd + 1 is even and greater than 2. Therefore for odd n the permutation alternates parity. Conjecture: a(n)>0 for all n. Verified up to n = 27. For n>=2, a(n) > 0 implies a prime == 1 mod n, not exceeding n^2 - n + 1.

Links

Table of n, a(n) for n=0..27.

Example

For n = 5, a(5) = 4. The valid permutations are (5,2,1,4,3) and (5,2,3,4,1) plus their reversals. For the permutation (5,2,1,4,3), the adjacent products plus one are 11,3,5, and 13, all prime.

Mathematica

fp[s_]:=Module[{ps={}}, Do[AppendTo[ps, s[[i]]*s[[i+1]]+1], {i, Length[s]-1}]; ps]; a[n_]:=Length[Select[Permutations[Range[n], {n}], AllTrue[fp[#], PrimeQ]&]]; Array[a, 10, 0] (* James C. McMahon, Jul 08 2026 *)

Prog

(Java)
public class Main {
    static int n; static boolean[] used;
    static boolean p(int m) {
        for (int i = 2; i * i <= m; i++) if (m % i == 0) return false;
        return m > 1;
    }
    static long dfs(int last, int depth) {
        if (depth == n) return 1;
        long c = 0;
        for (int v = 1; v <= n; v++)
            if (!used[v] && p(last * v + 1)) {
                used[v] = true; c += dfs(v, depth + 1); used[v] = false;
            }
        return c;
    }
    public static void main(String[] args) {
        for (n = 1; n <= 20; n++) {
            long t = 0; used = new boolean[n + 1];
            for (int s = 1; s <= n; s++) { used[s] = true; t += dfs(s, 1); used[s] = false; }
            System.out.println(n + ", " + t);
        }
    }
}

Crossrefs

Cf. A321597.

Sequence in context: A274449 A333711 A075101 * A075103 A021818 A388232

Adjacent sequences: A397616 A397617 A397618 * A397622 A397623 A397625

Keyword

nonn,more,changed

Author

Ethan Yu, Jul 02 2026

Extensions

a(21)-a(23) from Alois P. Heinz, Jul 02 2026

a(24)-a(27) from Andre Ruiz Loera, Jul 11 2026

Status

approved