2018-09-30 23:01:58 +01:00
---
id: 5900f5241000cf542c510037
title: 'Problem 440: GCD and Tiling'
2020-11-27 19:02:05 +01:00
challengeType: 5
2019-08-05 09:17:33 -07:00
forumTopicId: 302112
2021-01-13 03:31:00 +01:00
dashedName: problem-440-gcd-and-tiling
2018-09-30 23:01:58 +01:00
---
2020-11-27 19:02:05 +01:00
# --description--
2021-07-29 20:14:09 +02:00
We want to tile a board of length $n$ and height 1 completely, with either 1 × 2 blocks or 1 × 1 blocks with a single decimal digit on top:
2018-09-30 23:01:58 +01:00
2021-07-29 20:14:09 +02:00
< img class = "img-responsive center-block" alt = "ten blocks 1x1 with single decimal digit on top, and 1x2 block" src = "https://cdn.freecodecamp.org/curriculum/project-euler/gcd-and-tiling-1.png" style = "background-color: white; padding: 10px;" >
2018-09-30 23:01:58 +01:00
2021-07-29 20:14:09 +02:00
For example, here are some of the ways to tile a board of length $n = 8$:
2018-09-30 23:01:58 +01:00
2021-07-29 20:14:09 +02:00
< img class = "img-responsive center-block" alt = "examples of ways to tile a board of length n = 8" src = "https://cdn.freecodecamp.org/curriculum/project-euler/gcd-and-tiling-2.png" style = "background-color: white; padding: 10px;" >
2018-09-30 23:01:58 +01:00
2021-07-29 20:14:09 +02:00
Let $T(n)$ be the number of ways to tile a board of length $n$ as described above.
2018-09-30 23:01:58 +01:00
2021-07-29 20:14:09 +02:00
For example, $T(1) = 10$ and $T(2) = 101$.
Let $S(L)$ be the triple sum $\sum_{a, b, c} gcd(T(c^a), T(c^b))$ for $1 ≤ a, b, c ≤ L$.
For example:
$$\begin{align}
& S(2) = 10\\,444 \\\\
& S(3) = 1\\,292\\,115\\,238\\,446\\,807\\,016\\,106\\,539\\,989 \\\\
& S(4)\bmod 987\\,898\\,789 = 670\\,616\\,280.
\end{align}$$
Find $S(2000)\bmod 987\\,898\\,789$.
2018-09-30 23:01:58 +01:00
2020-11-27 19:02:05 +01:00
# --hints--
2018-09-30 23:01:58 +01:00
2021-07-29 20:14:09 +02:00
`gcdAndTiling()` should return `970746056` .
2018-09-30 23:01:58 +01:00
2020-11-27 19:02:05 +01:00
```js
2021-07-29 20:14:09 +02:00
assert.strictEqual(gcdAndTiling(), 970746056);
2018-09-30 23:01:58 +01:00
```
2020-11-27 19:02:05 +01:00
# --seed--
2018-09-30 23:01:58 +01:00
2020-11-27 19:02:05 +01:00
## --seed-contents--
2018-09-30 23:01:58 +01:00
```js
2021-07-29 20:14:09 +02:00
function gcdAndTiling() {
2020-09-15 09:57:40 -07:00
2018-09-30 23:01:58 +01:00
return true;
}
2021-07-29 20:14:09 +02:00
gcdAndTiling();
2018-09-30 23:01:58 +01:00
```
2020-11-27 19:02:05 +01:00
# --solutions--
2018-09-30 23:01:58 +01:00
```js
// solution required
```