11
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ OEIS says the problem is NP hard. I'd be willing to see a solution which isn't brute force \$\endgroup\$ Jun 6 at 7:16
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Noodle9
    Jun 6 at 12:39
  • \$\begingroup\$ @Noodle9 Oops, fixed. \$\endgroup\$ Jun 6 at 12:43

12 Answers 12

4
\$\begingroup\$

Wolfram Language (Mathematica), 60 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

J, 24 bytes

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

Try it online!

Straightforward brute force.

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

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.

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

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?
\$\endgroup\$
3
+100
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 13 bytes

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

Try it online or verify all test cases.

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Haskell, 102 bytes

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

Attempt This Online!

\$\endgroup\$

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.