A276735 Number of permutations p of (1..n) such that k+p(k) is a semiprime for 1 <= k <= n.

1, 0, 0, 1, 1, 3, 5, 12, 87, 261, 324, 1433, 5881, 37444, 196797, 708901, 2020836, 12375966, 105896734, 955344450, 11136621319, 95274505723, 590283352231, 4285001635230, 36417581252044, 272699023606314

Offset

0,6

Links

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

Example

a(4) = 1 because the permutation (3,4,1,2) added termwise to (1,2,3,4) yields (4,6,4,6) - both semiprimes - and only that permutation does so. a(5) = 3 because exactly 3 permutations - (3,2,1,5,4), (3,4,1,2,5) & (5,4,3,2,1) - added termwise to (1,2,3,4,5) yield semiprime entries.
From David A. Corneth, Sep 28 2016 (Start):
The semiprimes up to 10 are 4, 6, 9 and 10. To find a(5), we add (1,2,3,4,5) to some p. Therefore, p(1) in {3, 5}, p(2) in {2, 4}, p(3) in {1, 3}, p(4) in {2, 5} and p(5) in {1, 4, 5}.
If p(1) = 3 then p(3) must be 1. Then {p(2), p(4), p(5)} = {2, 4, 5} for which there are two possibilities.
If p(1) = 5 then p(3) = 3 and p(4) = 2. Then p(2) = 4 and p(5) = 1. So there's one permutation for which p(1) = 5.
This exhausts the options for p(1) and we found 3 permutations. Therefore, a(5) = 3. (End)

Maple

with(LinearAlgebra): with(numtheory):
a:= n-> `if`(n=0, 1, Permanent(Matrix(n, (i, j)->
        `if`((s-> bigomega(s)=2)(i+j), 1, 0)))):
seq(a(n), n=0..16);  # Alois P. Heinz, Sep 28 2016

Mathematica

perms[n0_] :=
Module[{n = n0, S, func, T, T2},
  S = Select[Range[2, 2*n], PrimeOmega[#] == 2 &];
  func[k_] := Cases[S, x_ /; 1 <= x - k <= n] - k;
  T = Tuples[Table[func[k], {k, 1, n}]];
  T2 = Cases[T, x_ /; Length[Union[x]] == Length[x]];
  Length[T2]]
Table[perms[n], {n, 0, 12}]
(* Second program (version >= 10): *)
a[0] = 1; a[n_] := Permanent[Table[Boole[PrimeOmega[i + j] == 2], {i, 1, n}, {j, 1, n}]]; Table[an = a[n]; Print[an]; an, {n, 0, 20}] (* Jean-François Alcover, Jul 25 2017 *)

Prog

(PARI) isok(va, vb)=my(v = vector(#va, j, va[j]+vb[j])); #select(x->(bigomega(x) == 2), v) == #v;
a(n) = my(vpo = numtoperm(n, 1)); sum(k=1, n!, vp = numtoperm(n, k); isok(vp, vpo)); \\ Michel Marcus, Sep 24 2016
(PARI) listA001358(lim)=my(v=List()); forprime(p=2, sqrtint(lim\1), forprime(q=p, lim\p, listput(v, p*q))); Set(v)
has(v)=for(k=1, #v, if(!setsearch(semi, v[k]+k), return(0))); 1
a(n)=local(semi=listA001358(2*n)); sum(k=1, n!, has(numtoperm(n, k))) \\ Charles R Greathouse IV, Sep 28 2016
(PARI) matperm(M)=my(n=matsize(M)[1], innerSums=vectorv(n)); if(n==0, return(1)); sum(x=1, 2^n-1, my(k=valuation(x, 2), s=M[, k+1], gray=bitxor(x, x>>1)); if(bittest(gray, k), innerSums+=s, innerSums-=s); (-1)^hammingweight(gray)*factorback(innerSums))*(-1)^n
a(n)=matperm(matrix(n, n, x, y, bigomega(x+y)==2)) \\ Charles R Greathouse IV, Oct 03 2016

Crossrefs

Cf. A073364, A095986, A096904, A097082.

Sequence in context: A293599 A156436 A352145 * A099791 A301901 A351225

Adjacent sequences: A276732 A276733 A276734 * A276736 A276737 A276738

Keyword

nonn

Author

Gary E. Davis, Sep 24 2016

Extensions

More terms from Alois P. Heinz, Sep 28 2016

Status

approved