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

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.

• So we have to output an infinite list ? All programs will be non-terminating then and for most of them, you won't be even able to see the output as the output will be provided on program termination only. May 25, 2015 at 10:46
• I'd suggest first N elements of the list... May 25, 2015 at 10:47
• I like non-terminating in this case, it's a little different to normal. May 25, 2015 at 10:49
• Do we have to print the results as we calculate them ? Or we are good if we can print them in one shot at the end of the program .. (which is most probably due to crashing by out of memory error) May 25, 2015 at 12:57
• They should be printed as they are calculated. May 25, 2015 at 13:38

# Pyth - 3532 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

• @Optimizer if you run it locally. Instant and infinite output are both obviously impossible online. May 25, 2015 at 18:01
• @Optimizer nope, its a built-in prime factorization function. :) May 25, 2015 at 18:03
• @Optimizer ok, i'll change it. May 25, 2015 at 18:06
• @Jakube shoot, Pyth has an infinite map, did not realize that. I'm feeling pretty stupid now. May 25, 2015 at 19:13
• @Jakube the .V really helped, but yours seems not to be working. You seem to be doing permutations on a urange instead of n+1...2n. May 25, 2015 at 20:27

# 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!

• Upvote for sanity. I think that time will end before you get an integer overflow though ;) May 25, 2015 at 11:11

# 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.

# 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