Euler 50

[kaipa]

Хотя я и собирался перейти на J для разминки ума при помощи ProjectEuler, но на Скале мне пока нравится больше. 50я задача, три вечера, между делом:
- в первый, видимо, правильно, но медленно -- слишком сложная рекурсия, хотел все в одну функцию вложить, и она никак не оптимизировалась под хвостовую рекурсию.
- во второй, быстро, но не правильно
- в третий, наконец, и быстро и правильно, разложилось на два очень простых метода в две строчки каждый (генератор простых чисел сюда не входит)

Да, на J это можно написать в три понятные строчки точно, я видел вариант. А значит, и в одну, так как любую J-программу можно "свернуть" в одну емкую (но не всегда понятную) строчку.

P.S. Попутно оказалось, что разные варианты генераторов случайных чисел не являются tail-рекурсивными (в том числе и тот, который в качестве примера приведен в документации Scala класса Stream).

Comments

[fregimus.livejournal.com]

А как подтверждается, что последовательность самая длинная? Там надо или доказывать, или все перебирать?

[ushastyi.livejournal.com]

Перебором. Большинство утверждений о простых числах очень плохо доказываются, как Вы знаете. В большинстве этих задачах, кроме самых простых, смысл в том, чтобы придумать оптимальный алгоритм, который бы не перебирал и не вычислял лишнего. Иногда удается аналитическое решение найти, но редко.

[fregimus.livejournal.com]

Ой, плохо. За мильон — и то не доказываются.

[fregimus.livejournal.com]

Презанятная задачка. “The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.” Интересно, что никто не обещал, что из 19 обязательно сложится хотя бы одно простое меньше 1000 (хотя на самом деле и складывается). Так что это надо или доказать (но я не знаю, как), или пробовать разной длины суммы до победного конца, не останавливаясь на первой длине, для которой простой суммы не нашлось.

[ushastyi.livejournal.com]

До победного конца. Мое неправильное решение второго дня останавливалось на первой непростой сумме. Так что приходится перебирать суммы до максимальной длины. Но перебор там можно существенно сократить, по мере продвижения к концу. Правильное решение на средней машине работает в пределах пары секунд на более-менее любом языке.

[fregimus.livejournal.com]

Да, я уже понял. Надо сначала взять максимальную возможную длину (наибольшая длина ряда первых простых с суммой < 1000000) и затем уменьшать на 1 с каждой итерацией. Поскольку мы ожидаем, что результат найдется на одной из первых итераций (а такова ситуация для 1000, и, на самом деле, для миллиона он находится на самой первой!), когда длина еще велика, то перебор последовательностей данной длины следует начинать с начала ряда простых, и останавливать когда сумма превысит 1000000.

Последовательное суммирование тоже оптимизируется: прибавил следующий за наибольшим, вычел наименьший.

Интересно, что для решения задачи требуется найти всего 4 суммы длины 500 с чем-то, не считая вышеупомянутой оптимизации. Это микросекунды. Но это, конечно, просто случайное везение, что она так быстро решается.

[ushastyi.livejournal.com]

Ну способов есть несколько. С учетом вашего, я уже знаю три :)