Detailed mathematical approach

Problem Summary

The problem asks for the number of ways to choose eight disjoint 5-card poker straights from a standard 52-card deck, under the extra condition that none of the eight straights is a straight flush. The only admissible rank windows are the ten usual poker straights: \(A2345\), \(23456\), \(34567\), \(\dots\), \(TJQKA\).

A direct search through 40-card subsets would be hopeless. The successful strategy is to separate the problem into two layers. First decide how many of the eight straights use each of the ten rank windows. Then, for that fixed rank pattern, count suit assignments that keep all cards distinct and force every straight to use at least two suits. The implementations validate the model with the exact checks \(N_1=10200\) and \(N_2=31832952\).

Mathematical Approach

The mathematics is a clean two-stage count: rank windows determine which ranks are demanded, and a compact dynamic program counts the legal suit histories.

Ten straight windows and a multiplicity vector

Let \(C_0,\dots,C_9\) denote the ten straight windows, ordered as

\[ C_0=A2345,\quad C_1=23456,\quad C_2=34567,\quad \dots,\quad C_9=TJQKA. \]

Instead of selecting eight straights directly, we first choose a multiplicity vector

\[ p=(p_0,p_1,\dots,p_9),\qquad p_s\ge 0,\qquad \sum_{s=0}^{9} p_s=8. \]

Here \(p_s\) records how many of the eight straights use the window \(C_s\).

Rank occupancy is the only rank-level feasibility constraint

For each rank \(r\), define its occupancy by

\[ o_r=\sum_{s:\,r\in C_s} p_s. \]

At rank \(r\) the deck contains exactly four cards, one per suit, so any feasible collection must satisfy \(o_r\le 4\). This condition is also sufficient at the rank level: once the occupancies do not exceed four, the only remaining issue is how to assign distinct suits to the straight copies that need the same rank.

The implementations recursively enumerate exactly those vectors \(p\) with \(\sum p_s=8\) and \(o_r\le 4\) for all 13 ranks. For eight straights there are only \(1599\) feasible multiplicity patterns, so the outer search space is already very small.

Temporarily label equal straight copies

Fix one feasible multiplicity vector. If a certain rank window occurs several times, those copies are temporarily labeled during the count. This is important because two straights with the same ranks can still evolve differently through their suit choices. The counting is therefore done on labeled copies first, and the artificial symmetry is removed only at the end.

Suit assignments at one rank are ordered injections

Process the ranks in the order \(2,3,4,5,6,7,8,9,T,J,Q,K,A\). Suppose \(m\) labeled straights are active at some rank \(r\). Then those \(m\) cards must use \(m\) distinct suits, so the local choice is an ordered injection from the active straight labels into the four suits. The number of possibilities is

\[ P(4,m)=4\cdot 3\cdots (4-m+1)=\frac{4!}{(4-m)!},\qquad 0\le m\le 4. \]

Because the occupancy condition guarantees \(m\le 4\), this completely captures the card-distinctness restriction at a single rank.

A five-state invariant is enough to forbid straight flushes

For each unfinished straight, the full suit history is unnecessary. The future only depends on whether all cards seen so far are still in one common suit and, if so, which suit. That gives exactly five states:

\[ x\in\{0,1,2,3,F\}. \]

The states \(0,1,2,3\) mean "still monochromatic in that suit." The state \(F\) means "already mixed, so a straight flush has become impossible." If a new card of suit \(s\) is appended, the update rule is

\[ T(x,s)= \begin{cases} s, & \text{for the first card of the straight},\\ x, & \text{if }x\in\{0,1,2,3\}\text{ and }x=s,\\ F, & \text{otherwise}. \end{cases} \]

This is the crucial invariant: once two different suits have appeared, no later choices can ever turn the straight back into a straight flush.

The wheel straight needs dormant carry-over state

The window \(A2345\) is the only non-consecutive pattern in the scan order \(2,\dots,A\). After rank \(5\) it disappears for several ranks and returns at rank \(A\). The dynamic program therefore keeps its five-state summary alive even while that straight is temporarily inactive. In other words, "inactive" does not mean "finished"; it only means that the current rank does not contribute a card to that straight.

The rank-by-rank recurrence

After some rank has been processed, suppose the unfinished labeled straights have five-state values \(x_0,\dots,x_{k-1}\). Encode them as a base-5 integer

\[ z=\sum_{i=0}^{k-1} x_i 5^i. \]

A dynamic-programming table stores, for each code \(z\), the number of partial suit assignments that lead to it. At the next rank, every current state branches over all ordered suit injections for the active straights. Each active straight updates its state through \(T\). If that straight ends at the current rank, the branch is accepted only when the updated state is \(F\); ending in one of the four suit states would mean that all five cards share a suit, which is forbidden. The unfinished straights are then re-encoded into the next base-5 state.

Worked example: one wheel and one ordinary straight

Take one copy of \(A2345\) and one copy of \(23456\), with no other straights. Then

\[ o_2=o_3=o_4=o_5=2,\qquad o_6=o_A=1, \]

and every other occupancy is \(0\), so the pattern is feasible. At ranks \(2,3,4,5\) both labeled straights are active, which means each of those ranks contributes an ordered injection of two suits, hence \(P(4,2)=12\) local choices. At rank \(6\) the straight \(23456\) ends and must already be in state \(F\). Meanwhile the wheel straight is inactive from \(6\) through \(K\), but its state is carried unchanged through that gap. Finally the Ace is processed, and the wheel is accepted only if its updated state is also \(F\). This small example shows why the algorithm needs both injective suit assignments and a memory for dormant-but-unfinished straights.

Remove the temporary labels

If a window \(C_s\) occurs \(p_s\) times, then permuting those \(p_s\) identical copies does not change the final unordered collection of straights. Therefore every genuine solution has been counted

\[ \prod_{s=0}^{9} p_s! \]

times in the labeled dynamic program. Dividing by this factor converts the labeled count for the pattern \(p\) into the desired unlabeled count. As a quick check, one straight gives \(10(4^5-4)=10200\), because each of the ten windows has \(4^5\) suitings and exactly four of them are straight flushes.

How the Code Works

Pattern generation and straight metadata

The C++, Python, and Java implementations first generate all feasible multiplicity vectors \(p\). For each one, they build the temporarily labeled straight copies and record which ranks are active for each copy, where it first appears in the scan, and at which rank it finally ends. They also precompute the ordered suit injections for \(m=0,1,2,3,4\).

Per-pattern dynamic programming

For every rank, the implementation knows which labeled straights are active now and which ones remain unfinished afterward. It iterates through the current base-5 states, tries every allowed ordered suit injection at that rank, updates the five-state summaries, rejects branches that would end as straight flushes, and adds the surviving counts to the next state table.

Final aggregation

After the Ace has been processed, only the empty terminal state is valid. Its count is divided by \(\prod p_s!\) to undo the artificial labeling, and that value is added to the global answer. The C++ and Java implementations distribute the independent pattern counts across worker threads; the Python implementation uses worker processes when that is worthwhile and otherwise uses the same serial recurrence.

Complexity Analysis

The outer loop visits only \(1599\) feasible patterns for eight straights. Within one pattern, at most eight labeled straights can be unfinished at the same time, so the encoded state space is bounded by

\[ 5^8=390625, \]

although the reachable portion is much smaller. At any rank, at most four straights can demand a card, so the local branching factor is at most

\[ P(4,4)=24. \]

Memory use is modest: the dynamic program only keeps the current and next state tables for one pattern, together with small metadata about the labeled straight copies. The decisive improvement is conceptual rather than asymptotic: the implementations never enumerate 40-card subsets of the deck, but instead count legal suit histories symbolically over a tiny family of feasible rank patterns.

Footnotes and References

1. Problem page: Project Euler 987
2. Poker straight: Wikipedia - Straight
3. Straight flush: Wikipedia - Straight flush
4. Dynamic programming: Wikipedia - Dynamic programming
5. Injective function: Wikipedia - Injective function