Счастливые билеты

Мы тут недавно с одним товарищем разговорились про точное количество «счастливых» билетов. В ответ я вспомнил, что как-то очень давно считал их количество на Перле — тогда короткие программы я предпочитал писать на нём. В алгоритмом я не заморачивался — там простой перебор, в комментариях есть указание, что выполняется он за три секунды.

На что товарищ прислал мне ссылку на выписку из статьей о счастливых билетах журнала «Квант». Там, помимо перебора, предлагается несколько методов вычисления, в частности есть даже интеграл:

Вычисление количества шестизначных счастливых билетов через интеграл

Вообще статьи интересные, умели же раньше писать! Кстати, стало интересно насколько сейчас плох старый-добрый перебор на современных мощностях и интерпретаторах. Взял код из своей заметки в блоге, на пятом Перле и ПХП7 — 0,9 и 0,5 секунды соответственно, вместе с запуском интерпретатора.

Вариант на R, который я наскорую написал по мотивам второй статьи из подборки выглядит вот так:

N <- function (n, k) {
    if (n == 1)
        ifelse(k >= 0 & k <= 9, 1, 0)
    else
        sum(sapply(0:9, function (l) N(n-1, k-l)))
}

lucky <- function (n) {
    0 -> s
    for (k in 0:999) {
        N(3, k) -> v

        if (v == 0) {
            break
        }

        s + v * v -> s
    }

    s
}

print (lucky(3))

Выполняется вместе с запуском интерпретатора за треть секунды, если кому-то интересно, чуть медленнее интеграла. Можно было бы переписать его аккуратнее — накапливать значение N, а не вычислять заново каждый раз.