Решить способом эйлера сравнение

5++ способов в одну строку на Python решить первую задачу Проекта Эйлера

Однажды меня посетила мысль, а что если попробовать решить первую задачу Проекта Эйлера всевозможными способами, но с условием, что решение должно быть в одну строку. В итоге получилось более пяти однострочных решений с применением Filter, Map, Reduce, Generator Expression и т.д. В этой статье я покажу то, к чему я пришёл.

Это моя первая статья. Стоит отнестись к ней настороженно. Уникальные решения будут оформлены в отдельные пункты. Менее уникальные — в подпункты.

Условие задачи

Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел равна 23.

Найдите сумму всех чисел меньше 1000, кратных 3 или 5.

00 — Базовое решение

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

Перебираем последовательность чисел от 1 до 999. Если перебираемое число делится на 3 или на 5 без остатка от деления, то прибавляем каждое такое число в заранее объявленную переменную result .

01 — Generator Expression. Выражение-генератор

Числа из последовательности от 1 до 999, делящиеся на 3 или на 5 без остатка от деления, собираются в генератор. Затем функция sum() складывает содержимое генератора.

01.a — List Comprehension. Выражение на основе списка

В отличии от предыдущего, здесь выражение дополнительно помещается в список. Стоило упомянуть этот вариант, так как он довольно часто встречается в различных статьях.

01.b — Set Comprehension. Выражение на основе множества

Тоже, что и в предыдущем, но вместо списка здесь множество.

02 — Filter

Функция filter схожа по принципу работы с выражением-генератором. Функция лямбда применяется к каждому элементу последовательности чисел от 1 до 999. Все числа последовательности, делящиеся на 3 или на 5 без остатка от деления, возвращаются, затем суммируются функцией sum() .

03 — Map

Перебираемые числа последовательности от 1 до 999, делящиеся на 3 или 5 без остатка от деления, остаются без изменений, все остальные числа заменяются на ноль. Полученная последовательность суммируется функцией sum() .

04 — Reduce

Из всей подборки, этот вариант «очень не очень». Как по степени реализации, так и по времени выполнения(но об этом попозже).
Если в reduce указан инициализатор(в нашем случае ноль), то он становится накопителем. К нему по очереди прибавляются только те числа из последовательности от 1 до 999, которые делятся на 3 или на 5 без остатка от деления. Если из функции reduce убрать инициализатор ноль, то инициализатором станет крайний левый элемент последовательности.

05 — Однострочное решение на основе множества

Самое элегантное решение, как по красоте написания, так и по времени выполнения.
Последовательность чисел от 1 до 999, кратную трём, помещаем во множество и объединяем со множеством, содержащим в себе последовательность чисел от 1 до 999, кратную пяти. Содержимое, полученного множества суммируем функцией sum() .

05.a — Ещё одно однострочное решение на основе множества

Похожий вариант на предыдущий, но, если использовать фигурные скобки, то последовательность чисел от 1 до 999, кратную трём и последовательность чисел от 1 до 999, кратную пяти, нужно распаковывать.

05.b — И ещё одно однострочное решение на основе множества

Создаём множество, с последовательностью чисел от 1 до 999, кратную трём и присоединяем к нему последовательность чисел от 1 до 999, кратную пяти. Затем функцией sum() суммируем.

05.c И последнее однострочное решение на основе множества

По аналогии с предыдущими. Распаковываем последовательности чисел в списки. Складываем списки. Оборачиваем во множество. Затем суммируем функцией sum() .

Смотрим на скорость выполнения каждого однострочного решения

Если проверить скорость выполнения каждого однострочного решения в командной строке, при помощи timeit, получим следующие значения в микросекундах:

Методика расчёта: python -m timeit «выражение»

Быстрее всего справились с задачей последние четыре варианта.

Заключение

Всего получилось 5 уникальных + 5 не уникальных решений. Благодаря этой задаче у меня появилось более устойчивое понимание работы функций Filter, Map, Reduce. И если раньше я недоумевал, почему функцию Reduce убрали из основного модуля, то теперь я не сомневаюсь в правильности этого решения.

В статье я старался отойти от популярного шаблона повествования «точность на грани бесполезности». Где предложения набиты под завязку «тяжёлыми» терминами, а из знакомого там только союзы и предлоги. Не уверен, что у меня получилось.

Источник

Функция Эйлера. Доказательство

Функция Эйлера, это функция, которая равна количеству натуральных чисел, меньших m и взаимно простых с m. Предполагается, что число 1 взаимно просто со всеми натуральными числами (и с единицею). Обозначается функция Эйлера греческой буквой φ.

Возьмем ряд натуральных чисел до m

1, 2, 3, . m.

Определим, сколько в этом ряду чисел, взаимно простых с m. Так как единица взаимно простое с единицею, то

Далее, число 2 взаимно просто с 1, тогда φ(2)=1, число 3 взаимно просто с 1 и 2, тогда φ(3)=2. Продолжая получим: φ(4)=2, φ(5)=4, и т.д.

Сформулируем следующие задачи.

Задача 1. Пусть a₁, a₂, a₃, . все отличные друг от друга простые множители числа m. Найти число тех чисел, которые не делятся ни на одно из чисел a₁, a₂, a₃, . .

Более общая задача имеет следующий вид:

Задача 2. Пусть a₁, a₂, a₃, . взаимно простые числа, которые входят множителями в m. Найти число всех чисел, которые не делятся ни на одно из чисел a₁, a₂, a₃, . .

Возьмем ряд натуральных чисел до m:

1, 2, 3, . m.

(1)

Исключим из ряда (1) все те числа, которые делятся на a₁. Это следующие числа

Их число равно . Исключим эти числа из ряда (1). Тогда останутся

(2)

числа, которые не делятся на a₁. Обозначим множество этих чисел через A₁.

Из чисел ряда A₁ нужно исключить все те числа, которые кратные a₂. Это те числа из ряда (1), которые делятся на a₂ и не делятся на a₁. Числа ряда (1), которые делятся на a₂ следующие:

.

Их количество равно .

Эти числа можно представить в виде ka₂, где k пробегает натуральные числа

.

(3)

Для того, чтобы ka₂ не делился на a₁ необходимо и достаточно, чтобы k не делился на a₁ (т.к. a₁ и a₂ взаимно простые числа). Нужно найти количество чисел из ряда (1), которые делятся на a₁ и исключить их из ряда (3). делится на a₁ т.к. m делится на a₁, m делится на a₂ и m делится на a₁a₂ (a₁, a₂ входят множителями в m). Задача по отношению числа та же, что и задача по отношению числа m, которое мы решили с помощью формулы (2). Из ряда A₁ нужно исключить числа, которые делятся на a₁. Тогда взяв вместо m число получим

.

(4)

(4) число тех чисел ряда A₁, которые не делятся на a₁ или это число тех чисел ряда (1), которые делятся на a₂ и не делятся на a₁.

Учитывая (2) и (4) получим число тех чисел ряда (1), которые не делятся ни на a₁, ни на a₂:

.

(5)

Обозначим множество этих чисел через A₂. Далее удалим из A₂ те числа, которые делятся на a₃. Это те числа из ряда (1), которые делятся на a₃ и не делятся на a₁ и a₂.

Числа ряда (1), которые делятся на a₃ следующие:

.

Их количество равно .

Эти числа можно представить в виде ka₃, где k пробегает натуральные числа

.

(6)

Для того, чтобы ka₃ не делился на a₁ и a₂ необходимо и достаточно, чтобы k не делился на a₁ и a₂ (т.к. a₃ и a₁ а также a₃ и a₂ числа взаимно простые). Нужно найти количество чисел из ряда (1), которые делятся на a₁ и a₂ и исключить из ряда (6). делится на a₁ и a₂, так как m делится на a₁, m делится на a₂ и m делится на a₁a₂a₃ (a₁, a₂, a₃ входят множителями в m). Задача по отношению числа та же, что и задача по отношению числа m, которое мы решили с помощью уравнения (5). Число тех чисел ряда (6), которые не делятся ни на a₁ ни на a₂ (или число тех чисел ряда (1), которые делятся на a₃ и не делятся ни на a₁, ни на a₂):

.

Тогда число тех чисел ряда (1), которые не делятся ни на a₁, ни на a₂, ни на a₃:

.

Обозначим множество этих чисел через A₃. Рассуждая таким образом, заключим, что число A_i тех чисел ряда (1), которые не делятся на a₁, a₂, . a_i равно

.

(7)

Чтобы найти число тех чисел ряда (1), которые не делятся на a₁, a₂, . a_i+1, нужно из множества (7) исключить числа кратные a_i+1. Это те числа ряда (1), которые не делятся на a₁, a₂, . a_i и делятся на a_i+1.

Все числа ряда (1), которые делятся на a_i+1, следующие:

,

то есть это числа ka_i+1, где k=1, 2, . m/a_i+1 и для того, чтобы ka_i+1 не делилось на a₁, a₂, . a_i необходимо и достаточно, чтобы k не делилось на a₁, a₂, . a_i. Поэтому из ряда A_i нужно исключить столько чисел, сколько существует в ряду

Если исключить эти числа из ряда A_i, то останутся те числа этого ряда, которые не делятся на числа a₁, a₂, . a_i+1. Их число равно

Мы доказали следующую теорему:

Теорема 1. Если a₁, a₂, . a_q, все различные взаимно простые числа, входящие в m, то число чисел, которые не делятся ни на одно из чисел a₁, a₂, . a_q и входящих в ряд m равно:

(8)

Таким образом справедлива и следующая теорема:

Теорема 2. Если a₁, a₂, . a_q, все различные простые числа, входящие в m, то число чисел, взаимно простых с m и входящих в ряд

определяется формулой (8).

Действительно. Всякое число, которое не делится ни на один из простых множителей, входящих в состав m является взаимно простым с m. Тогда учитывая теорему 1, получаем доказательство данной теоремы.

Найденная формула можно переписать и в другом виде. Если a₁, a₂, a₃, . все различные простые числа, входящие множителями в m, то

Рассмотрим численный пример.

Пример. Возьмем число 90. Числа, взаимно простые с 90 и меньше 90 следующие:

1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89.

Таких чисел 24. Учитывая, что 90=2·3 2 ·5, для φ(m) мы находим

Мультипликативность функции Эйлера

Теорема 3. Если m₁ и m₂ числа взаимно простые, то

φ(m1m2)=φ(m1)φ(m2)

a1, a2, a3, . b1, b2, b3, .

(9)

различные простые числа, входящие в состав m₁m₂, так как m₁ и m₂ взаимно простые числа, т.е. они не имеют общих делителей.

Справедливо и обратное. Всякое простое число входящее в произведение m₁m₂ должно совпадать с числом из ряда (9), так как это простое число входит множителем или в m₁, или в m₂.

Таким образом числа ряда (9) представляют множество всех простых чисел, входящих в произведение m₁m₂. Следовательно

С другой стороны

φ(m1m2)=φ(m1)φ(m2).

φ(90)=φ(9·10)=φ(9)φ(10),

φ(90)=φ(9·10)=φ(9)φ(10)=6·4=24.

Эта теорема справедлива и для любого числа сомножителей, если эти сомножители взаимно простые числа.

φ(m1m2m3) = φ(m1)φ(m2m3) = φ(m1)φ(m2)φ(m3).

φ(m1m2m3m4) = φ(m1)φ(m2m3m4) = φ(m1)φ(m2)φ(m3)φ(m4).

и т.д.

Обобщение функции Эйлера

Как мы уже видели, функция Эйлера φ(m) показывает, сколько в ряду

1, 2, . m

(10)

чисел взаимно простых с m.

Более общая задача состоит в следующем:

Задача 3. Дан ряд (10) и требуется найти число тех чисел, этого ряда, которые имеют с m наибольший общий делитель λ, причем m=nλ, т.е. λ является одним из делителей числа m.

Очевидно, что искомые числа находятся среди чисел

λ, 2λ , 3λ , . nλ

(11)

Для того, чтобы λ было наибольшим общим делителем чисел m=nλ и kλ из ряда (11), необходимо и достаточно, чтобы k и n были числами взаимно простыми. Следовательно, т.к. k принимает значения

1, 2, . n

(12)

то искомых чисел столько, сколько найдется чисел из ряда (12) взаимно простых с n. Число таких чисел равно φ(n) (Теорема 2).

Мы доказали следующую теорему:

Теорема 4. Если a₁, a₂, a₃, . все различные простые числа, входящие в m, то число чисел, имеющих с m наибольший общий делитель λ (m=nλ) равен числу

φ(n)=φ(m/λ)

(12)

m=n1λ1=n2λ2=n3λ3=.

1, 2, . m

(13)

Тогда φ(n₁) количество тех чисел, которые с m имеют наибольший общий делитель λ₁, φ(n₂) количество тех чисел, которые с m имеют наибольший общий делитель λ₂, и т.д.

φ(n1)+φ(n2)+φ(n3)+. =m

Мы доказали следующую теорему:

Теорема 5. Пусть n₁, n₂, . n_k все делители числа m. Тогда имеет место следующее равенство:

Пример . Пусть m=90. Делители числа m следующие:

Источник