Detailed mathematical approach

Problem Summary

For even \(n\), let \(P(n)\) be the number of permutations of \(2,3,\dots,n\) in which every adjacent pair is coprime. The target computation is \(P(34)\) modulo \(83456729\). A direct search grows far too quickly, so the implementations convert the problem into an exact count of Hamiltonian cycles in a balanced bipartite graph and then evaluate that count with a determinant/permanent inclusion-exclusion identity.

Mathematical Approach

Write \(n=2m\). Introduce the odd side

$U=\{1,3,5,\dots,2m-1\}$

and the even side

$V=\{2,4,6,\dots,2m\}.$

Define the \(m\times m\) bipartite adjacency matrix \(B\) by

$B_{u,v}=\begin{cases} 1,& \gcd(u,v)=1,\\ 0,& \text{otherwise}. \end{cases}$

The key point is that the original permutations of \(2,\dots,2m\) can be re-expressed as alternating structures in this augmented graph.

Step 1: Parity Forces an Alternating Path

Among the numbers \(2,3,\dots,2m\), there are \(m\) even numbers and \(m-1\) odd numbers. Two even numbers can never be adjacent in a valid permutation, because their gcd is at least \(2\). Therefore every valid permutation must alternate parity. Since the evens are more numerous by one, the parity pattern is forced to be

$E-O-E-O-\dots-O-E.$

So the problem is not counting arbitrary coprime permutations; it is counting alternating even-odd paths whose endpoints are both even.

Step 2: Add \(1\) and Turn the Path into a Cycle

The number \(1\) is coprime to every even number, so adding it on the odd side balances the bipartition. If

$e_0,o_1,e_1,o_2,\dots,o_{m-1},e_{m-1}$

is a valid permutation of \(2,\dots,2m\), then inserting \(1\) between the two endpoints produces the alternating cycle

$1,e_0,o_1,e_1,\dots,o_{m-1},e_{m-1},1.$

Conversely, deleting \(1\) from such a cycle recovers a valid permutation. Thus \(P(2m)\) is exactly the number of Hamiltonian cycles in the balanced bipartite graph \((U,V)\), read from the distinguished vertex \(1\).

Step 3: Hamiltonian Cycles Become Ordered Pairs of Perfect Matchings

Any alternating cycle in a bipartite graph can be colored with two alternating edge colors. That splits the cycle into two perfect matchings, say \(M_1\) and \(M_2\). Conversely, the union of two perfect matchings is a spanning \(2\)-regular bipartite subgraph, so it is a disjoint union of even cycles.

A single Hamiltonian cycle is therefore the special case in which the ordered pair \((M_1,M_2)\) produces exactly one cycle rather than several disconnected cycles. The permanent counts perfect matchings without signs, while the determinant supplies the signs needed to cancel the unwanted multi-cycle decompositions.

Step 4: The Inclusion-Exclusion Identity Used by the Implementations

Let the distinguished odd vertex be \(1\). For subsets \(I\subseteq U\setminus\{1\}\) and \(J\subseteq V\) with \(|I|=|J|=k\), denote by \(B_{I,J}\) the selected \(k\times k\) submatrix and by \(B_{\bar I,\bar J}\) the complementary \((m-k)\times(m-k)\) submatrix, where \(\bar I=U\setminus I\) still contains the distinguished vertex \(1\). The exact identity evaluated by the code is

$P(2m)=\sum_{k=0}^{m-1}\ \sum_{\substack{I\subseteq U\setminus\{1\}\\J\subseteq V\\|I|=|J|=k}} (-1)^k \det(B_{I,J})^2\operatorname{perm}(B_{\bar I,\bar J})^2 \pmod{83456729}.$

The squared permanent counts ordered pairs of perfect matchings on the complementary block. The squared determinant creates the sign-reversing correction that removes disconnected cycle covers and leaves only Hamiltonian cycles through the distinguished row.

Step 5: Compress Equal Neighborhoods

If two selectable odd vertices have identical neighborhoods, then choosing both of them inside a determinant block would create two equal rows, so the determinant would vanish. The same is true for equal columns. That means the determinant part only needs one representative from each row class and each column class, with a multiplicity factor recording how many interchangeable choices exist.

The permanent part is different: repeated columns do not vanish there. Instead, the implementations use a grouped form of Ryser's formula. If a column class has size \(s\) and exactly \(t\) columns from that class are selected in a Ryser subset, then there are

$\binom{s}{t}$

ways to make that choice, and the row sums depend only on \(t\), not on which particular columns were taken.

Worked Example: \(n=4\)

Here \(m=2\), so

$U=\{1,3\},\qquad V=\{2,4\}.$

Every odd-even pair is coprime, hence

$B=\begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix}.$

After anchoring the count at \(1\), only one non-distinguished odd row remains selectable. The formula has two types of contribution:

$k=0:\qquad \operatorname{perm}(B)^2=2^2=4,$

and

$k=1:\qquad -\sum_{|J|=1}\det(B_{\{3\},J})^2\operatorname{perm}(B_{\{1\},V\setminus J})^2=-(1+1)=-2.$

Therefore

$P(4)=4-2=2,$

corresponding to the two valid permutations \((2,3,4)\) and \((4,3,2)\). This is the smallest checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations first build the \(m\times m\) coprimality matrix between \(U\) and \(V\), together with binomial coefficients up to \(m\). They then classify rows by equal support masks, remove one copy of the distinguished row \(1\), and classify columns in the same way by applying the same mask logic to the transpose.

For every \(k\), the implementation enumerates all choices of \(k\) row classes and \(k\) column classes. The determinant block is formed from the chosen representatives; if its determinant is \(0\), that branch is discarded immediately. Otherwise the code squares the determinant, applies the sign \((-1)^k\), and multiplies by the class multiplicities.

The complementary block is then sent to a grouped permanent routine. The determinant is computed with fraction-free elimination modulo \(83456729\). The permanent is computed with Ryser's formula, but columns with identical support masks are grouped: a small prefix of classes is handled by explicit bitmask subsets, and the remaining large classes are handled recursively by choosing only how many columns are selected from each class. Each choice contributes a binomial factor \(\binom{s}{t}\).

Finally the code multiplies

$\text{multiplicity}\times (-1)^k \times \det^2 \times \operatorname{perm}^2$

for each branch and accumulates the result modulo \(83456729\). The implementations include small checkpoints such as \(P(4)=2\) and \(P(10)=576\), and the C++ version also cross-checks tiny cases by brute force.

Complexity Analysis

Let \(m=n/2\). If \(R\) and \(C\) are the numbers of distinct selectable row and column classes, the outer enumeration examines

$\sum_{k=0}^{m-1}\binom{R}{k}\binom{C}{k}$

class pairs. A determinant on a \(k\times k\) block costs \(O(k^3)\). For the complementary block of size \(r=m-k\), naive Ryser would cost \(O(r2^r)\), but grouping identical columns reduces the subset space to roughly

$2^b\prod_i (s_i+1),$

where \(b<10\) is the explicitly enumerated prefix size and the \(s_i\) are the remaining column-class sizes. The permanent stage then spends about \(O\!\left(r^2 2^b\prod_i (s_i+1)\right)\) arithmetic operations. Memory usage is polynomial in the current block size, plus the explicit subset table of size \(2^b\). For the target case \(n=34\), this compression is what makes the exact count practical.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=886
2. Permanent of a matrix: Wikipedia - Permanent (mathematics)
3. Determinant: Wikipedia - Determinant
4. Hamiltonian path and cycle: Wikipedia - Hamiltonian path
5. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
6. Ryser formula: Wikipedia - Ryser formula