Задача 462
Перестановки 3-гладких чисел

A 3-гладкое число - это целое число, которое не имеет ни одного простого делителя больше трех. Для целого N, определим S(N) как множество 3-гладких чисел меньше или равных N . Например, S(20) = { 1, 2, 3, 4, 6, 8, 9, 12, 16, 18 }.

Определим F(N) как количество перестановок S(N), в которых каждый элемент следует после всех своих собственных делителей.

Вот одна из возможных перестановок для N = 20.
- 1, 2, 4, 3, 9, 8, 16, 6, 18, 12.
А следующая перестановка не подходит под условия задачи, так как 12 стоит перед его делителем 6.
- 1, 2, 4, 3, 9, 8, 12, 16, 6, 18.

Можно показать, что F(6) = 5, F(8) = 9, F(20) = 450 и F(1000) ≈ 8.8521816557e21.
Найдите F(1018). Дайте ответ в стандартном виде, округленным до десяти знаков после десятичной точки.
При указания ответа используйте латинскую строчную букву "e" для отделения мантиссы от порядка. Например, если ответ равен 112 233 445 566 778 899, тогда он будет выглядеть как 1.1223344557e17.

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