Hexagony, 218 92 58 bytes
Notice: I'll be giving a bounty of 500 rep to the first person who finds a valid solution in a hexagon of side-length 4 (or less?) or a provably optimal solution of side-length 5. If you can't find such a solution but manage to beat my score in a side-length 5 hexagon (by getting more no-ops at the end of the program, which can be omitted from the source code), I'm willing to give out a smaller bounty for that as well.
)}?}.=(..]}}={.=.&~./=}..=.=&{.<......*|>(<..=%....}!\[.&@
The first ever non-trivial (i.e. non-linear) Hexagony program! It is based on the same squared-factorial approach as Sp3000's Labyrinth answer. After starting out with a hexagon of size 10, I managed to compress it down to size 5. However, I was able to reuse some duplicate code and there are still quite a bunch of no-ops in the code, so size 4 might just be possible.
Explanation
To make sense of the code, we first need to unfold it. Hexagony pads any source code to the next centred hexagonal number with no-ops (.), which is 61. It then rearranges the code into a regular hexagon of the corresponding size:
) } ? } .
= ( . . ] }
} = { . = . &
~ . / = } . . =
. = & { . < . . .
. . . * | > ( <
. . = % . . .
. } ! \ [ .
& @ . . .
This is quite heavily golfed with crossing and overlapping execution paths and multiple instruction pointers (IPs). To explain how it works, let's first look at an ungolfed version where control flow doesn't go through the edges, only one IP is used and the execution paths are as simple as possible:
. . . . . . . . . . . . .
. . . . . . . . . . @ . . .
. . . . . . . . . . ! . . . .
. . . . . . . . . . % . . . . .
. . . . . . . . . . = . . . . . .
. . . . . . . . . . { . . . . . . .
. . . . . . . . . . = . . . . . . . .
. . . . . . . . . . & . . . . . . . . .
. . . . . . . . . . { . . . . . . . . . .
. . . . . . . . . . * . . . . . . . . . . .
. . . . . . . . . . = . . . . . . . . . . . .
. . . . . . . . . . } . . . . . . . . . . . . .
) } ? } = & { < . . & . . . . . . . . . . . . . .
. . . . . . . > ( < . . . . . . . . . . . . . .
. . . . . . = . . } . . . . . . . . . . . . .
. . . . . } . . . = . . . . . . . . . . . .
. . . . | . . . . | . . . . . . . . . . .
. . . . * . . . ) . . . . . . . . . . .
. . . . = . . & . . . . . . . . . . .
. . . . > } < . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . .
Side note: the above code starts with executing the first line, which is full of no-ops. Then, when the IP hits the north east edge, it wraps to the left-most corner (the )), where the actual code begins.
Before we start, a word about Hexagony's memory layout. It's a bit like Brainfuck's tape on steroids. In fact, it's not a tape, but it's a hexagonal grid itself (an infinite one), where each edge has an integer value, which is initially 0 (and as opposed to standard Brainfuck, the values are signed arbitrary-precision integers). For this program, we'll be using four edges:
We'll compute the factorial on edge A, count down our input on edge C and store another copy of the input (for the modulo) on edge D. B is used as a temporary edge for computations.
The memory pointer (MP) starts out on edge A and points north (this is important for moving the MP around). Now here is the first bit of the code:
)}?}=&{
) increments edge A to 1 as the basis of the factorial. } makes the MP take a right-turn, i.e. move to edge C (pointing north-east). Here we read the input as an integer with ?. Then we take another right-turn to edge D with }. = reverses the MP, such that it points at the vertex shared with C. & copies the value from C (the input) into D - the value is copied from the left because the current value is non-positive (zero). Finally, we make the MP take a left-turn back to C with {.
Next, < is technically a branch, but we know that the current value is positive, so the IP will always turn right towards the >. A branch hit from the side acts as a mirror, such that the IP moves horizontally again, towards the (, which decrements the value in C.
The next branch, < is actually a branch now. This is how we loop from n-1 down to 1. While the current value in C is positive, the IP takes a right-turn (to execute the loop). Once we hit zero, it will turn left instead.
Let's look at the loop "body". The | are simple mirrors, the > and < are also used as mirrors again. That means the actual loop body boils down to
}=)&}=*}=
} moves the MP to edge B, = reverses its direction to face the vertex ABC. ) increments the value: this is only relevant for the first iteration, where the value of B is still zero: we want to ensure that it's positive, such that the next instruction & copies the right neighbour, i.e. A, i.e. the current value of the factorial computation, into B.
} then moves the MP to A, = reverses it again to face the common vertex. * multiplies both neighbours, i.e. edges B and C and stores the result in A. Finally, we have another }= to return to C, still facing the vertex ABC.
I hope you can see how this computes the factorial of n-1 in A.
So now we've done that, the loop counter in C is zero. We want to square the factorial and then take the modulo with the input. That's what this code does:
&}=*{&={=%!@
Since C is zero, & copies the left neighbour, i.e. the factorial in A. }=* moves to B and stores the product of the two copies of the factorial (i.e. the square) in B. { moves back to C, but doesn't reverse the MP. We know that the current value is now positive, so & copies input from D into C. ={= reverses the MP, moves to A and reverses the MP again. Remember, the square of the factorial is in B and the input is in C. So % computes (n-1)!^2 % n, exactly what we're looking for. ! prints the result as an integer (0 or 1) and @ terminates the program.
Okay, but that was the ungolfed version. What about the golfed version? You need to know two more things about Hexagony:
- The edges wrap around. If the IP hits an edge of the hexagon, it jumps to the opposite edge. This is ambiguous when the IP hits a corner straight on, so hitting a corner also acts as a branch: if the current value is positive, the IP jumps to the grid edge to its right, otherwise to the one to its left.
- There are actually 6 IPs. Each of them starts in a different corner, moving along the edge in the clockwise direction. Only one of them is active at a time, which means you can just ignore the other 5 IPs if you don't want them. You can switch to the next IP (in clockwise order) with
]and to the previous one with[. (You can also choose a specific one with#, but that's for another time.)
There are also a few new commands in it: \ and / are mirrors like |, and ~ multiplies the current value by -1.
So how does the ungolfed version translate to the golfed one? The linear set up code )}?}=&{ and the basic loop structure can be found here:
) } ? } . ->
. . . . . .
. . . . . . .
. . . . . . . .
-> . = & { . < . . .
. . . . . > ( <
. . . . . . .
. . . . . .
. . . . .
Now the loop body crosses the edges a few times, but most importantly, the actual computation is handed off to the previous IP (which starts at the left corner, moving north east):
) . . . .
= . . . ] .
} = . . = . .
~ . / . } . . .
. . . . . . . . .
. . . * . > ( <
. . = . . . .
. } . \ [ .
& . . . .
After bouncing off the branch towards south east, the IP wraps around the edge to the two = in the top left corner (which, together, are a no-op), then bounces off the /. The ~ inverts the sign of the current value, which is important for subsequent iterations. The IP wraps around the same edge again and finally hits [ where control is handed over to the other IP.
The one now executes ~}=)&}=*}= which undoes the negation and then just runs the ungolfed loop body. Finally it hits ] which hands control back to the original IP. (Note that next time, we execute it this IP, it will start from where it left off, so it will first hit the corner. We need the current value to be negative in order for the IP to jump back to the north west edge instead of the south east one.)
Once the original IP resumes control, it bounces off the \ and the > to feed into the next loop iteration.
Now the really crazy part: what happens when the loop terminates?
) . . . .
. ( . . ] }
. . { . = . &
. . . = } . . =
. . . . . . . . .
. . . * | . . <
. . = % . . .
. } ! . . .
& @ . . .
The IP moves north east form the < and wraps around to the north east diagonal. So it ends up on the same execution path as the loop body (&}=*}=]). Which is actually pretty cool, because that is exactly the code we want to execute at this point, at least if we add another } (because }=} is equivalent to {). But how does this not actually enter the earlier loop again? Because ] changes to the next IP which is now the (so far unused) IP which starts in the top right corner, moving south west. From there, the IP continues along the edge, wraps to the top left corner, moves down the diagonal, bounces off the | and terminates at @ while executing the final bit of linear code:
}&=)({=%!@
(The )( is a no-op of course - I had to add the ( because the ) was already there.)
Phew... what a mess...