Задача 113
Непрыгучие числа

Если, читая число слева направо, ни одна цифра не превышает цифру справа от нее, то такое число называется возрастающим; например, 134468.

Таким же образом, если ни одна цифра не превышает цифру слева от нее, число называется убывающим; например, 66420.

Назовем положительное целое число, не являющеся ни убывающим, ни возрастающим, "прыгучим" числом; например, 155349.

При увеличении n увеличивается пропорция прыгучих чисел меньше n. Таким образом, существует только 12951 непрыгучее число до миллиона, и только 277032 непрыгучих числа до 10^(10).

Сколько чисел меньше гугола (10^(100)) не являются "прыгучими"?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net