# Permutations summing to permutations

Given an integer $$\N\$$ consider a permutation $$\p=p_1,p_2,p_3,\ldots\$$ of $$\1,\ldots,N-1\$$. Let $$\P = p_1 , p_1+p_2 \bmod N, p_1+p_2+p_3 \bmod N, \ldots\$$ be its prefix sums modulo $$\N\$$. Sometimes $$\P\$$ will be a permutation of $$\1,\ldots,N-1\$$ itself.

For example, $$\N=4: p=3,2,1 \rightarrow P=3,1,2\$$

Negative examples: $$\p=2,3,1 \rightarrow P=2,1,2\$$ is not a permutation ; $$\p=3,1,2 \rightarrow P=3,0,2\$$ is a permutation but not of $$\1,\ldots,3\$$

Your task is to write a program or function that takes $$\N\$$ and returns the number of permutations $$\p\$$ of $$\1,\ldots,N-1\$$ such that $$\P\$$ is also a permutation of $$\1,\ldots,N-1\$$.

Rules:

You may return integers or integer-valued numbers.

You may return the $$\N\$$-th term, the first $$\N\$$ terms or the entire series.

You may ignore/skip odd $$\N\$$. If you choose to do so you may take $$\N\$$ or $$\N/2\$$ as the input.

Other than that default rules and loopholes for integer sequences apply.

This is code-golf, so shortest code in bytes wins. Different languages compete independently.

First few terms:

\ \begin{align} 2 &\rightarrow 1 \\ 4 &\rightarrow 2 \\ 6 &\rightarrow 4 \\ 8 &\rightarrow 24 \\ 10 &\rightarrow 288 \end{align}\

OEIS has more.

• OEIS says the problem is NP hard. I'd be willing to see a solution which isn't brute force Jun 6 at 7:16
• Given an integer 1,…,N−1 doesn't make any sense. Perhaps you mean: Given an integer N consider 1,…,N−1. Also the next sentence talks about p1, p2 etc without any definition as what they represent. Jun 6 at 12:39
• @Noodle9 Oops, fixed. Jun 6 at 12:43

# Wolfram Language (Mathematica), 60 bytes

Count[Sort/@Mod[Accumulate/@Permutations[r=Range@#-1],#],r]&


Try it online!

# J, 24 bytes

1#.!(=&#[:=#|+/\)@A.&i.]


Try it online!

Straightforward brute force.

# JavaScript (ES7), 88 bytes

f=(n,m=z=2**n-2,p=o=0,x,g=i=>(q=1<<++i)>m?o+=x==z:g(i,m&q&&f(n,m^q,i+=p,x|1<<i%n)))=>g


Try it online!

### How?

We compute the bitmask $$\z=2^n-2\$$ where the bits $$\1\$$ to $$\n-1\$$ are set (e.g. $$\n=4\$$ gives $$\z=14=1110_2\$$).

We start with $$\m=z\$$ and $$\x=0\$$. We recursively clear the bits of $$\m\$$ in all possible orders while keeping track of the sum of said bit indices in $$\p\$$ and setting the bits $$\p \bmod n\$$ in $$\x\$$. (Note that we do not need to keep track of the permutation itself.)

We have a solution whenever we end up with $$\x=z\$$, in which case the output value $$\o\$$ is incremented.

# Husk, 13 bytes

S#omȯOm%¹∫Ptŀ


Try it online!

           t   # tail: all except the first element of
ŀ  # the sequence 0..N-1;
S#o            # now, how many times does this occur among
P    #  get all permutations of this
mȯ          #  and for each of them
∫     #   get the cumulative sums
m%¹      #   each modulo the input
O         #   and sort the results


Alternative, also 13 bytes

LSnm(†%¹∫)Pḣ←


Try it online!

            ←  # decrement the input by 1
ḣ   # get the sequence 1..N
P    # and get all permutations of this;
Sn            # now get all common elements between this and
m(    )     #  for each permutation
∫      #   get the cumulative sums
†%¹       #   each modulo the input
L              # how long is the resulting list of common elements?


# Vyxal, 11 bytes

ɽ:Ṗv¦⁰%vs^O


Try it Online!

## How?

ɽ:Ṗv¦⁰%vs^O
ɽ           # exclusive range from 0; range(1, N)
:          # duplicate top of stack
Ṗ         # get permutations
v¦       # vectorized cumulative sum
⁰      # push N to top of stack
%     # modulo (vectorizes)
vs   # vectorized sort
^  # flip stack (so range(1, N) is now on top)
O # count number of instances


# Jelly, 9 bytes

’Œ!ðÄ%f⁸L


A monadic Link that accepts an integer and yields the count of permutations summing to permutations.

Try it online!

### How?

’Œ!ðÄ%f⁸L - Link: integer, N
’         - decrement -> N-1
Œ!       - all permutations of [1..N-1]
ð      - start a new dyadic chain, f(permutations, N)
Ä     - cumulative sums (of each of the permutations)
%    - modulo N
f⁸  - filter keep if in (the permutations)
L - length


# Factor + math.combinatorics math.unicode, 71 bytes

[| n | n [1,b) <permutations> [ dup cum-sum [ n mod ] map ⊂ ] count ]


Try it online!

• n [1,b) <permutations> Get all the permutations of [1..n) as a virtual sequence.
• [ ... ] count Count how many of them...
• dup cum-sum [ n mod ] map ⊂ ...are supersets of their cumulative sum modulo n.

# Burlesque, 30 bytes

J-.ror@Jbcjm{q++pa}x/.%q~[Z]++


Try it online!

J      # Dup
-.     # Decrement
ro     # Range 1..N-1
r@     # Permutations
J      # Dup
bc     # Infinite cycle
j      # Swap
m{     # Map
q++   # Sum
pa    # Partial
}
x/     # Reorder stack
.%     # Modulo
q~[Z]  # Zip with contained in permutations
++     # Sum (count)


# 05AB1E, 13 bytes

L¨œεηOI%{āQ}O


Explanation:

L           # Push a list in the range [1, (implicit) input]
¨          # Remove the last item to make the range [1,input)
œ         # Get all its permutations
ʒ        # Filter the permutations by:
η       #  Get all prefixes of the current permutation
O      #  Sum each prefix
I%    #  Modulo the input
{   #  Sort it
ā  #  Push a list in the range [1,length] (without popping)
Q #  Check if both lists are the same
}g       # After the filter: pop and push the length
# (which is output implicitly as result)


# K (ngn/k), 23 bytes

{+/~^a?x!+\'a:?>'+!x#x}


Try it online!

+!x#x All length x combinations of 0 1 ... x-1.
a:?>' The unique results of grading up each combination. This gives all permutation, assign these to a:.
x!+\' Cumulative sum of each permutation, modulo x.
a? Find each row in the result in the list of permutations. This gives nulls for non-permutations.
+/~^ Count the non-null values.

# Python, 116 bytes

from itertools import*
f=lambda n:(r:=set(range(1,n)))and sum({sum(x[:i])%n for i in r}==r for x in permutations(r))

Attempt This Online!

import Data.List
f n=length\$filter((elemp).tail.map(modn).scanl(+)0)p where p=permutations[1..n-1]