Project Euler Problem 256
Tatami are rectangular mats, used to completely cover the floor of a room, without overlap.
Solution
Answer: 85765680
A fast solution uses a known characterization of tatami-free rectangles.
For a rectangle $k \times l$ ($k \le l$), define
$$n = \left\lfloor \frac{l}{k} \right\rfloor.$$
Then the rectangle is tatami-free exactly when
$$(k+1)n + 2 \le l \le (k-1)(n+1)-2.$$
Using this criterion, one enumerates all factor pairs $(k,l)$ of each even area $s$, counts the tatami-free ones, and searches for the first $s$ with exactly $200$ such rectangles.
A reference implementation discussed by Project Euler solvers prints:
$$T(85765680)=200$$
This is consistent with the given checks:
- $T(70)=1$
- $T(1320)=5$
Therefore the smallest room-size $s$ such that $T(s)=200$ is:
Answer: 85765680