Competition problem — Number theory

Library / /294 of 860

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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.