HMMT February

Number theory Difficulty 5.0 AIME, harder Find the answer

(Lucas Numbers) The Lucas numbers are defined by $L_{0}=2, L_{1}=1$ , and $L_{n+2}=L_{n+1}+L_{n}$ for every $n \geq 0$ . There are $N$ integers $1 \leq n \leq 2016$ such that $L_{n}$ contains the digit 1 . Estimate $N$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

```
Answer: 1984
lucas_ones n = length . filter (elem '1') $take (n + 1) lucas_strs where lucas = 2 : 1 : zipWith (+) lucas (tail lucas) lucas_strs = map show lucas main = putStrLn . show$ lucas_ones 2016
```

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.