Number of ways to sum [1..n] with [n+1..2n] such that each sum is prime

Question

Let \$n > 0\$. Let \$X = 1, 2,...,n\$ and \$Y = n+1, n+2, ..., 2n\$. Define \$a(n)\$ as the number of permutations \$p\$ of \$Y\$ such that every element of \$X + p(Y)\$ is prime. For example:

n = 2
X = [1,2]
Y = [3,4]
p_0(Y) = [3,4] => X + p0(Y) = [4,6] => No
p_1(Y) = [4,3] => X + p1(Y) = [5,5] => Yes
a(2) = 1

In as few bytes as possible, write a program or function which produces this sequence (A070897), either as an infinite list on STDOUT, or in your interpreter of choice.

The output should start at \$n=1\$, and each entry should be on a newline and undecorated, i.e.:

1
1
1
1
2
...

Examples

\$a(1)=1\$ because each list [1], [2] has only 1 element

\$a(5)=2\$ because there are two permutations: [(1,10),(2,9),(3,8),(4,7),(5,6)] and [(1,6),(2,9),(3,10),(4,7),(5,8)]

Rules

No built-in primality tests. No lookup table ;). No standard loopholes.

Answer 1

Pyth - 35 32 27 bytes

The obvious approach. The while loop logic is taking a lot of bytes. Thanks to @Jakube for telling me about .V and saving a lot of bytes. Explanation coming soon.

.V1lf!sm%[email protected]

Try first n here online

Answer 2

CJam, 38 35 32 bytes

0{)_e!{ee{1b1$+)_m!)\)%},!},,p}h

This is an infinite list version. If you run it using the Java compiler, you will keep on getting result for increasing n on each line until the program crashes (if it does. Did not test).

For sanity, run the finite version using this link. You can change the number in the input to see a longer list.

How it works:

0{                            }h  e# This acts as an infinite do-while loop here
  )_                              e# Starting from 0, increment the number and copy it
                                  e# Lets call this number at each iteration as N
    e!                            e# Get all possible permutations of the array 0..N-1
      {                   },      e# Filter the list of permutations based on this code block
       ee                         e# Convert the permutation array into an [index value]
                                  e# pair array. For ex. [5 2]ee gives [[0 5] [1 2]]
         {             },         e# Pass each index value pair through this filter
          1b1$+)                  e# Sum the index and value and add current N + 1 to it
                                  e# At this point, we have something equivalent to
                                  e# pairwise addition of [1 .. n] and [n .. 2n - 1]
                _m!)\)%           e# Now we do ((N - 1)! + 1)%N to see if N is prime
                                  e# This is Wilson's theorem and will give 0 for primes
                         !        e# Now we have a filtered index-value pairs which all
                                  e# correspond to non-prime numbers. If the list is empty,
                                  e# Then all numbers are prime. Thus we do a ! on empty list
                                  e# to get truthy.
                            ,p    e# Take the total permutations where X + pN(Y) are all
                                  e# primes and print the number to STDOUT immediately
                                  e# We are left with the initial incremented N on stack
                                  e# which is always non-zero, so the loop continues
                                  e# infinitely 

UPDATE: 2 bytes saved, thanks to Martin!

Answer 3

Python 2, 147 bytes

from itertools import*
n=1;R=range
while n:print sum(all(x%d for x in map(sum,zip(R(n),c))for d in R(2,x))for c in permutations(R(n+2,2*n+2)));n+=1

The import itertools rule of thumb tells me there's probably a better way...

A few bytes are saved by summing [0 ... n-1] with [n+2 ... 2n+1] instead.

Answer 4

Jelly, 20 bytes

+RŒ!+€RÆḍỊP€SṄ¬
1Ç1#

Try it online!

This gets exponentially slower for each new \$n\$ it calculates, so times out on TIO after having printed \$a(9) = 40\$. Given enough time/memory however, it will eventually print all the elements in the sequence.

How it works

1Ç1# - Main link. No arguments
1    - Starting from n = 1...
   # - ...count up n = 1, 2, ...
  1  - ...until 1 n returns true when...
 Ç   - ...run over the helper link.
       As the helper link ends with ¬ (logical NOT), no n will return true

+RŒ!+€RÆḍỊP€SṄ¬ - Helper link. Takes n on the left
 R              - [1, 2, ..., n]
+               - [n+1, n+2, ..., 2n]
  Œ!            - All permutations
      R         - [1, 2, ..., n]
     €          - For each perumation:
    +           -   Add [1, 2, ..., n] elementwise
       Æḍ       - Proper divisor counts
         Ị      - Equal to 1?
           €    - For each:
          P     -   All true?
            S   - Count the true permutations
             Ṅ  - Print
              ¬ - Logical NOT to continue the infinite loop