# Tchoukaillon hooks

2022-03-19, post № 256

**mathematics**, #discrete, #haskell, #functional-pearl

Ever since watching D. Knuth’s talk “Tchoukaillon numbers”^{ [1]} in the Rutgers experimental mathematics seminar back in January of 2022, I was intrigued by the algorithm he presented to iteratively generate the Tchoukaillon arrays ꚓ⁽ⁿ⁾. Their discrete pointwise limit defines a two-dimensional permutation of the natural numbers, whereby pointwise exactly one value is attained more than once. These properties make calculating the discrete limit expressible as a lazy computation:

tcheInf i j = discreteLimit $ \n -> tche n i j

Despite the seeming simplicity of iteratively taking hooks from an -matrix, two-dimensional problems seem to require extra scrutiny when approached with a linear data model, even more so without arbitrary jumps. To not transpose too often — thereby invalidating the previous computations’ linearity — I took the approach of linearly evaluating a micro-DSL to express each finitely wide `tche n`

as finite chunks of `tcheFlat n :: [Int]`

:

tcheFlat 1 = [1..] tcheFlat n = eval (cycle actions) $ tcheFlat (n-1) where actions = concat [[flat (n-m), grab (n-m-1,m)] | m <- [1..n-1]] tche n i j | j <= n = (chunksOf n $ tcheFlat n) ## i ## j | otherwise = -n

Of course left in the dust by the closed-form formula, D. Knuth’s table’s corner element is computationally viably accessible using this method:

*Main> tcheInf 32 32 2093

Source: tche.hs

## Footnotes

- ▲ D. Knuth:
*Tchoukaillon numbers*. Rutgers experimental mathematics seminar, 2022-01-27. Online: https://sites.math.rutgers.edu/ [accessed 2022-03-19].~zeilberg/ expmath/ archive22.html