Detailed mathematical approach

Problem Summary

For an admissible area \(s\), every room shape is a factor pair \((a,b)\) with

$ab=s,\qquad a\le b.$

The implementation defines \(T(s)\) as the number of those rectangles that fail the tatami test used by the solver. The task is to find the smallest \(s\) such that

$T(s)=\text{target},$

with \(\text{target}=200\) in the full Project Euler problem. The final numeric answer is intentionally omitted here.

Mathematical Approach

1. Turn the Geometry into a Divisor Problem

Once the area \(s\) is fixed, there is no continuous geometry left to search: every candidate room is determined by a divisor \(a\) of \(s\), and the other side is \(b=s/a\).

Therefore

$T(s)=\sum_{\substack{a\mid s\\a\le \sqrt{s}}}\mathbf{1}_{\neg \mathrm{tileable}(a,s/a)}.$

The condition \(a\le \sqrt{s}\) ensures that each unordered pair is counted exactly once. So the whole problem becomes: for each \(s\), enumerate its divisor pairs and test each pair with the arithmetic predicate from the code.

2. Why the Outer Search Uses Only Even \(s\)

The solver increments \(s\) by 2 and never tests odd areas. This matches the room model encoded by the implementation: the predicate immediately rejects odd area, so the search space is reduced to even \(s\) from the beginning.

That single observation halves the outer search. The difficult part is then no longer parity, but efficiently counting how many divisor pairs of an even \(s\) fail the tatami criterion.

3. The Exact Arithmetic Tatami Test Used by the Code

After ordering the sides so that \(a\le b\), the function is_tatami_tileable applies the following rule.

If \(ab\) is odd, the function returns false immediately.

Otherwise it computes

$g=\left\lfloor\frac{b+\lfloor a/2\rfloor}{a}\right\rfloor,$

and

$d=\lvert ag-b\rvert.$

The room is declared tileable exactly when

$d\le g+1.$

So a divisor pair contributes to \(T(s)\) precisely when

$d>g+1.$

4. Interpreting \(g\) and \(d\)

Write

$b=qa+r,\qquad 0\le r<a.$

Then the quantity \(g\) is the integer that chooses the multiple of \(a\) closest to \(b\) (with the usual upward choice at exact halves when \(a\) is even). More explicitly,

$g=\begin{cases} q, & r<\lceil a/2\rceil,\\ q+1, & r\ge \lceil a/2\rceil, \end{cases}$

and therefore

$d=\begin{cases} r, & r<\lceil a/2\rceil,\\ a-r, & r\ge \lceil a/2\rceil. \end{cases}$

So \(d\) is simply the distance from \(b\) to the nearest multiple of \(a\). The code says the room is tatami-tileable if this mismatch is at most \(g+1\), and tatami-free if it is larger.

5. Worked Example: \(T(70)=1\)

The implementation checks the checkpoint

$T(70)=1.$

The divisor pairs of 70 are

$ (1,70),\ (2,35),\ (5,14),\ (7,10). $

For \((5,14)\),

$g=\left\lfloor\frac{14+\lfloor 5/2\rfloor}{5}\right\rfloor=\left\lfloor\frac{16}{5}\right\rfloor=3,$

$d=\lvert 5\cdot 3-14\rvert=1\le 4,$

so that room passes.

For \((7,10)\), however,

$g=\left\lfloor\frac{10+\lfloor 7/2\rfloor}{7}\right\rfloor=\left\lfloor\frac{13}{7}\right\rfloor=1,$

$d=\lvert 7\cdot 1-10\rvert=3>2=g+1.$

Thus \((7,10)\) is the only tatami-free factor pair, so \(T(70)=1\).

6. Second Checkpoint: \(T(1320)=5\)

The code also verifies

$T(1320)=5.$

The divisor pairs with \(a\le \sqrt{1320}\) are

$ (1,1320),(2,660),(3,440),(4,330),(5,264),(6,220),(8,165),(10,132),(11,120),(12,110),(15,88),(20,66),(22,60),(24,55),(30,44),(33,40). $

The failing ones are exactly

$ (20,66),\ (22,60),\ (24,55),\ (30,44),\ (33,40). $

For instance, for \((20,66)\),

$g=\left\lfloor\frac{66+10}{20}\right\rfloor=3,\qquad d=\lvert 20\cdot 3-66\rvert=6,\qquad 6>4=g+1,$

so it fails. By contrast, \((15,88)\) passes because

$g=\left\lfloor\frac{88+7}{15}\right\rfloor=6,\qquad d=\lvert 15\cdot 6-88\rvert=2\le 7.$

Hence exactly five divisor pairs are tatami-free, giving \(T(1320)=5\).

7. Factorization and Divisor Generation

Testing one area \(s\) efficiently requires fast divisor enumeration. If

$s=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},$

then every divisor has the form

$a=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k},\qquad 0\le f_i\le e_i.$

The function factorize obtains the prime powers using an SPF table in the general search, or a prime list during the fast stepped search. Then a DFS over the exponents \(f_i\) generates all divisors.

The DFS stops whenever the partial divisor already exceeds \(\sqrt{s}\). This matters because once \(a>\sqrt{s}\), the complementary factor \(b=s/a\) would satisfy \(b<a\), so that pair has already been counted in reversed order.

8. Why the Divisor DFS Counts Every Room Exactly Once

Every unordered rectangle with area \(s\) has a unique smaller side \(a\le \sqrt{s}\). Conversely, every divisor \(a\le \sqrt{s}\) determines exactly one rectangle \((a,s/a)\).

So the recursion in count_tatami_free_rooms_for_size is not an approximation and not a sampling step. It is an exact enumeration of all candidate rooms of area \(s\).

9. Global Search Strategy

The full goal is not to evaluate one fixed \(s\), but to find the smallest \(s\) for which \(T(s)\) hits the target.

For general targets, the code performs an exhaustive even scan: it builds an SPF table up to some limit, distributes even values of \(s\) across worker threads, and keeps the smallest hit found so far in an atomic variable.

If nothing is found, the limit is doubled and the process repeats.

For the specific Euler target \(200\), the implementation first tries a faster heuristic pass over multiples of

$55440=2^4\cdot 3^2\cdot 5\cdot 7\cdot 11.$

This is not a logical necessity of the mathematics; it is an optimization. Multiples of such a divisor-rich step are natural places to look first when one wants \(T(s)\) to be large. If that fast pass does not solve the problem, the program falls back to the full even scan.

10. Checkpoints for Correctness

The source validates itself with four checkpoints:

$T(70)=1,\qquad T(1320)=5,$

and the smallest searched sizes satisfy

$\min\{s:T(s)=1\}=70,\qquad \min\{s:T(s)=5\}=1320.$

These checks verify both layers of the solution: the local divisor-pair counter and the global search for the first valid \(s\).

How the Code Works

The helper build_spf(limit) constructs the smallest-prime-factor table. For each candidate area \(s\), the function count_tatami_free_rooms_for_size factors \(s\), runs the divisor DFS, forms each pair \((a,b)\), and applies is_tatami_tileable. The outer routine find_smallest_size_with_t scans even values of \(s\), parallelizes the work across threads, and returns the first area whose count equals the requested target.

The special path for target == 200 uses trial division on stepped candidates before the general fallback. So the implementation combines exact arithmetic testing with practical search engineering.

Complexity Analysis

For one fixed area \(s\), the dominant mathematical cost is divisor enumeration. After factorization, the work is proportional to the number of generated divisors, namely

$O(\tau(s)),$

where \(\tau(s)\) is the divisor-counting function. With SPF support, factorization itself is very fast, so per candidate the practical cost is roughly “factorize plus test all divisor pairs”.

If the first valid answer is \(S^\ast\), then the exhaustive search examines even \(s\le S^\ast\), so the total running time is roughly the sum of these per-\(s\) costs over that range. The memory usage is dominated by the SPF table up to the current limit, hence linear in the search bound. Multithreading improves wall-clock time but not the asymptotic count of arithmetic tests.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=256
2. Divisor function and divisor counting: Wikipedia - Divisor function
3. Smallest prime factor / linear sieve idea: cp-algorithms - Linear sieve
4. Prime factorization and divisor generation: cp-algorithms - Integer factorization
5. Floor and rounding notation: Wikipedia - Floor and ceiling functions