7
\$\begingroup\$

Let n > 0. Let X = [1..n] and Y = [n+1 .. 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]

p0(Y) = [3,4] => X + p0(Y) = [4,6] => No
p1(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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Optimizer May 25 '15 at 10:46
  • \$\begingroup\$ I'd suggest first N elements of the list... \$\endgroup\$ – Optimizer May 25 '15 at 10:47
  • \$\begingroup\$ I like non-terminating in this case, it's a little different to normal. \$\endgroup\$ – alexander-brett May 25 '15 at 10:49
  • \$\begingroup\$ 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) \$\endgroup\$ – Optimizer May 25 '15 at 12:57
  • \$\begingroup\$ They should be printed as they are calculated. \$\endgroup\$ – alexander-brett May 25 '15 at 13:38
4
\$\begingroup\$

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%h.!J++hbd@TdhJb.pb

Try first n here online

\$\endgroup\$
  • \$\begingroup\$ @Optimizer if you run it locally. Instant and infinite output are both obviously impossible online. \$\endgroup\$ – Maltysen May 25 '15 at 18:01
  • \$\begingroup\$ @Optimizer nope, its a built-in prime factorization function. :) \$\endgroup\$ – Maltysen May 25 '15 at 18:03
  • \$\begingroup\$ @Optimizer ok, i'll change it. \$\endgroup\$ – Maltysen May 25 '15 at 18:06
  • \$\begingroup\$ @Jakube shoot, Pyth has an infinite map, did not realize that. I'm feeling pretty stupid now. \$\endgroup\$ – Maltysen May 25 '15 at 19:13
  • \$\begingroup\$ @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. \$\endgroup\$ – Maltysen May 25 '15 at 20:27
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Upvote for sanity. I think that time will end before you get an integer overflow though ;) \$\endgroup\$ – alexander-brett May 25 '15 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.