Python теорема эйлера

admin

Программирование, Алгоритмы, Математика

Рекомендация: подборка платных и бесплатных курсов Python — https://katalog-kursov.ru/

image

FizzBuzz — это известная задачка на программирование, которую обычно дают в технической части собеседований. Она формулируется примерно так:

Напишите функцию, выводящую список целых чисел от 1 до 100, но вместо каждого числа, кратного 3, она должна выводить «Fizz», а вместо каждого числа, кратного 5, выводить «Buzz». Вместо чисел, кратных и 3, 5, программа должна выводить «FizzBuzz»; все остальные числа должны выводиться без изменений.

Можно написать функцию, вообще не использующую условную логику и вместо этого разделяющую целые числа на 4 возможные категории (обычное решение оставим в качестве упражнения заинтересованному читателю):

  1. Имеющие делитель 3, но не 5
  2. Имеющие делитель 5, но не 3
  3. Имеющие делитель и 3, и 5
  4. Не имеющие делитель 3 и 5

Нам нужна функция, которая будет возвращать:

Рассмотрим реализацию такой функции на Python:

[(lambda n: { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15])(n+1) for n in range(100)]

Та же функция на Ruby:

(1..100).map{|n| {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] }

Как мы и ожидали, каждая из этих функций возвращает список целых чисел от 1 до 100 с подставленными в нужные места «Fizz», «Buzz» и «FizzBuzz».

Но почему? Откуда взялись постоянные значения 0, 6, 10 и 1? Почему

$n^4 mod 15$ возвращает 6 для чисел, кратных 3, но не 5, 10 для чисел, кратных 5, но не 3, 0 для чисел, кратных 5 и 3 и 1 во всех остальных случаях? И самое важное — справедливо ли это для любого

$n$, которое мы выберем?

I. n^4 mod 15 решает FizzBuzz

Доказательство таково:

$n^4 mod {15} = begin{cases} 0, & text{if $n$ is divisible by 3 and 5} newline 6, & text{if $n$ is divisible by 3 and coprime to 5} newline 10, & text{if $n$ is divisible by 5 and coprime to 3} newline 1, & text{if $n$ is coprime to 3 and 5} end{cases}$

Первый случай тривиален; если n делится и на 3, и на 5, то после возведения n в любую степень возвращаемый

$mod 15$ результат всегда будет равен 0, та как любое целое число с делителями 3 и 5 будет также кратным 15

$(3 * 5)$.

Во втором случае у нас есть 3 как делитель некой константы c:

$3c^4 equiv 6 pmod{15}$

или

$3c^4 mod 15 = 6$

для каждой константы c > 0, если c является взаимно простым с 5. (Если c не является взаимно простым с 5, то у нас возник первый случай, который вернёт 0.)

Для начала предположим, что

$c = 1$. Это даёт

$3^4 mod 15$ или

$81 mod 15$, что вернёт 6:

$15 * 5 = 75$, с остатком 6 от 81.

Предположим, что c является целым > 1. Применим степень к каждому множителю и воспользуемся равенством

$(ab) = (a + a(b - 1))$:

$begin{aligned} 3^4c^4 & mod 15 newline 81c^4 & mod 15 newline (81 + 81(c^4 - 1)) & mod 15 end{aligned}$

Давайте рассмотрим отдельно выражение

$c^4$. Из теоремы Эйлера в теории чисел мы знаем, что поскольку

$c$ является взаимно простым с 5, то

$c^4 mod 5$ равно 1; если

$c^4 / 5$ имеет остаток 1, то это должен быть случай, когда

$c^4 - 1$ ровно делится на 5; то есть, вне зависимости от значения

$c$, если оно является взаимно простым с 5, то

$(c^4 - 1)$ имеет делитель 5. Другой делитель не важен, поэтому давайте перепишем

$(c^4 - 1)$ как

$5x$.

Теорема Эйлера в теории чисел

Теорема Эйлера заключается в том, что

$a^{?(n)} equiv 1 (mod n)$, где

$a$ является взаимно простым с

$n$, а

$?$ — это пси-функция Эйлера; пси-функция

$n$ возвращает количество целых чисел меньше

$n$, являющихся взаимно простыми с

$n$. Для каждого простого числа

$p$,

$?(p)$ равна

$p - 1$.

Леонард Эйлер

$begin{align} (81 + 81(5x)) &mod 15 newline (81 mod 15 + 81(5x) mod 15) &mod 15 newline (6 + 81(5x) mod 15) &mod 15 newline 6 mod 15 end{align}$

Мы можем переписать это во вторую строку благодаря следующему свойству модулярных выражений:

$(a + b) mod n = (a mod n + b mod n) mod n$. В третьей строке выражение

$81(5x)$ имеет делители и 3, и 5, поэтому

$81(5x) mod 15 = 0$, что даёт нам

$6 mod 15$, то есть 6.

То есть для любого

$c$, являющегося взаимно простым с 5 и > 1, выражение

$3c^4 mod 15$ вернёт 6.

Благодаря тому же процессу мы выясним, что

$5c^4 mod 15$ всегда возвращает 10; при

$c = 1$ мы имеем

$625 mod 15$, что равно 10. Для

$c > 1$ (взаимно простое с 3) мы можем записать

$(625 + 625(c^4 - 1)) mod 15$

Теорема Эйлера говорит нам, что если

$c$ является взаимно простым с 3, то

$c^2 equiv 1 mod 3$; но у нас есть

$c^4$. Однако

$c^4$ — это

$c^2c^2$, а поскольку

$ab mod n = ((a mod n)( b mod n)) mod n$, то

$c^4 mod 3$ также равно 1.

Опять же, если

$c^4 equiv 1 (mod 3)$, то

$(c^4 - 1)$ нацело делится на 3 и имеет делитель 3. Это снова сокращает второй член до 0, оставляя

$625 mod 15$, что снова равно 10.

У нас остаётся случай, в котором есть некое число

$c$, являющееся взаимно простым с 3 и 5. Если

$c$ равно 1, то получаем

$1 mod 15$, то есть 1.

Если

$c$ > 1, мы снова можем записать это как

$(1 + (c^4 - 1)) mod 15$. Так как мы знаем, что если

$c$ является взаимно простым с 3 и 5,

$c^4 equiv 1 (mod 3)$ и

$c^4 equiv 1 (mod 5)$, то

$(c^4 - 1)$ имеет делители 3 и 5.

Поэтому снова:

$begin{aligned} (1 + (c^4 - 1)) &mod 15 newline (1 mod 15 + (c^4 - 1) mod 15) &mod 15 newline (1 + 0) &mod 15 newline 1 &mod 15 newline 1 end{aligned}$

То есть

$n^4 mod 15$ всегда будет возвращать 0, если и 3, и 5 являются делителями

$n$, возвращать 6, если делителем является 3, но не 5, возвращать 10, если делителем является 5, но не 3, и 1, если

$n$ является взаимно простым и с 3, и с 5, а функция вида ->(n){ {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] } всегда будет возвращать правильный результат FizzBuzz для каждого

$n$ (до того, как

$n^4$ не переполнит тип integer, используемый в компьютере).

II. Решение любой задачи категории FizzBuzz

Схожую функцию можно создать для любой похожей задачи, которые я буду называть задачами категории FizzBuzz. (Задачи категории FizzBuzz: например, выводить «Foo» вместо чисел, кратных 2, «Bar» вместо чисел, кратных трём, «Baz» вместо чисел, кратных 5 и выполнить конкатенацию каждого слова для чисел, имеющих больше одного из делителей 2,3 и 5). Выбираемые в качестве делителей числа не обязаны быть простыми, но если одно из них имеет в качестве делителя другое, то некоторые группы не существуют. Например, если мы решили изменить FizzBuzz так, чтобы кратные 2 возвращали «Fizz», а кратные 4 возвращали «Buzz» (вместо традиционных 3 и 5), то увидим «Fizz» для каждого кратного 2, «FizzBuzz» для кратного 2 и 4, но никогда не увидим «Buzz», потому что не существует числа, кратного 4, являющегося взаимно простым с 2.

Представленное ниже обобщённое решение не такое уж и общее, как я сказал: существует множество пар чисел, для которого оно не сработает; поэтому делители нужно выбирать гораздо тщательнее. Оно сработает для уникальных простых чисел, но не всегда хорошо для составных чисел. Хочу поблагодарить автора этого очень подробного поста, объясняющего подробности того, почему общая формула не будет работать для составных чисел.

Написанное выше уравнение для решения FizzBuzz можно также записать в виде

$n^{LCM(?(3),?(5))} mod (3 cdot 5)$

где

$?$ — это пси-функция Эйлера, а

$LCM$ — наименьшее общее кратное.

В общем виде для любого множества из

$k$ делителей

$n_1,n_2,..n_k$, для которого нам нужна функция типа FizzBuzz, можно использовать формулу:

$n^{LCM(?(n_1),?(n_2),..?(n_k))} mod prod_{i=1}^k n_i$

Для функции типа FizzBuzz, возвращающей «Foo» вместо чисел, кратных 7, и «Bar» вместо чисел, кратных 11, найдём:

$n^{LCM(?(7),?(11))} mod (7 cdot 11)$

$?(7)$ равно 6, а

$?(11)$ равно 10, и

$LCM$ (наименьшее общее кратное) для 6 и 10 равно 30. То есть уравнение примет вид:

$n^{30} mod 77$

Реализация на Python:

[(lambda n: { 1: n, 7**30%77: "Foo", 11**30%77: "Bar", 0: "FooBar" }[n**30%77])(n+1) for n in range(100)]

Это даст нам ожидаемый результат:

[1, 2, 3, 4, 5, 6, 'Foo', 8, 9, 10, 'Bar', 12, 13, 'Foo', 15, 16, 17, 18, 19, 20, 'Foo', 'Bar', 23, 24, 25, 26, 27, 'Foo', 29, 30, 31, 32, 'Bar', 34, 'Foo', 36, 37, 38, 39, 40, 41, 'Foo', 43, 'Bar', 45, 46, 47, 48, 'Foo', 50, 51, 52, 53, 54, 'Bar', 'Foo', 57, 58, 59, 60, 61, 62, 'Foo', 64, 65, 'Bar', 67, 68, 69, 'Foo', 71, 72, 73, 74, 75, 76, 'FooBar', 78, 79, 80, 81, 82, 83, 'Foo', 85, 86, 87, 'Bar', 89, 90, 'Foo', 92, 93, 94, 95, 96, 97, 'Foo', 'Bar', 100]

Вывод

Итак,

$$display$$a^{LCM(?(n_1),?(n_2),..?(n_k))} equiv begin{cases} 0pmod {prod_{i=1}^k n_i}, & text{if $n$ is divisible by every $n_1,n_2,..n_k$} newline r_1,r_2,..r_kpmod {prod_{i=1}^k n_i}, & text{a distinct result for every other combination of factors in $n_1,n_2,..n_k$} newline 1pmod {prod_{i=1}^k n_i}, & text{if $n$ is coprime to every $n_1,n_2,..n_k$} end{cases}$$display$$

… если числа

$n_1, n_2,.. n_k$ являются уникальными простыми числами. Снова благодарю автора этого поста за столь наглядную иллюстрацию этого.

Я не делаю никаких предположений о том, что существует какое-то иное практическое применение этой формулы, кроме как для решения задач категории FizzBuzz с выбранными в качестве кандидатов произвольными числами.

Источник

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 убрали из основного модуля, то теперь я не сомневаюсь в правильности этого решения.

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

Метод Эйлера в Python

Метод Эйлера для дифференциального уравнения с программированием на Python

Я пытаюсь реализовать метод Эйлера для приближения значения e в python. Вот что у меня есть на данный момент:

Однако, когда я пытаюсь вызвать функцию, я получаю ошибку «ValueError: shape Euler . Не могли бы вы дополнить свой вопрос этой информацией? Тиа

Формула, которую вы пытаетесь использовать, – это не метод Эйлера, а точное значение e при приближении n к бесконечности wiki,

Метод Эйлера используется для решения дифференциальных уравнений первого порядка.

Вот два руководства, которые показывают, как реализовать метод Эйлера для решения простой тестовой функции: руководство для новичков и руководство по числовому ODE.

Чтобы ответить на заголовок этого поста, а не на вопрос, который вы задаете, я использовал метод Эйлера для решения обычного экспоненциального распада:

У которого есть решение,

Код:

Выход:

Примечание: я не уверен, как правильно отобразить LaTeX.

Вы уверены, что не пытаетесь реализовать метод Ньютона? Потому что для аппроксимации корней используется метод Ньютона.

Если вы решите использовать метод Ньютона, вот немного измененная версия вашего кода, которая приближается к квадратному корню из 2. Вы можете изменить f(x) а также fp(x) с функцией и ее производной, которые вы используете в своем приближении к тому, что вы хотите.

[ 1. 1.5 1.41666667 1.41421569 1.41421356 1.41421356 1.41421356 1.41421356 1.41421356 1.41421356 1.41421356]

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

Помимо этого большой проблемой было использование ^ вместо того ** для полномочий, что является законной, но совершенно другой (побитовой) операцией в python.

  • Я определенно имел в виду метод Эйлера, но да . ** определенно проблема. Благодарность

Метод эйлера дифференциальные уравнения python

Variant 19 (Sukach Maxim, BS17-03)

Найдем

В итоге, наше решение принимает вид:

Метод Эйлера дает возможность приближенно выразить функцию теоретически с любой наперед заданной точностью. Суть метода Эйлера в пошаговом вычислении значений решения y=y(x) дифференциального уравнения вида y’=f(x,y) с начальным условием (x0;y0). Метод Эйлера является методом 1-го порядка точности и называется методом ломаных.

Для вычисления используются следующие формулы:

Метод Эйлера и точное решение при x0 = 0, xf = 9, y0 = 1, h = 0.1

Метод Эйлера и точное решение при x0 = 0, xf = 3, y0 = 1, h = 0.1

Метод Эйлера и точное решение при x0 = 0, xf = 1, y0 = 1, h = 0.1

Усовершенствованный метод Эйлера

Суть усовершенствованного метода Эйлера в пошаговом вычислении значений решения y=y(x) дифференциального уравнения вида y’=f(x,y) с начальным условием (x0;y0). Усовершенствованный метод Эйлера является методом 2-го порядка точности и называется модифицированным методом Эйлера.

Разница между данным методом и методом Эйлера минимальна и заключается в использовании следующих формул:

Усовершенствованный Метод Эйлера и точное решение при
x0 = 0, xf = 9, y0 = 1, h = 0.1

Усовершенствованный Метод Эйлера и точное решение при
x0 = 0, xf = 3, y0 = 1, h = 0.1

Усовершенствованный Метод Эйлера и точное решение при
x0 = 0, xf = 1, y0 = 1, h = 0.1

Классический метод Рунге-Кутты

Суть метода Рунге-Кутты в пошаговом вычислении значений решения y=y(x) дифференциального уравнения вида y’=f(x,y) с начальным условием (x0;y0). Классический метод Рунге-Кутты является методом 4-го порядка точности и называется методом Рунге-Кутты 4-го порядка точности.

Ну и как обычно, формулы:

Классический метод Рунге-Кутты и точное решение при x0 = 0, xf = 9, y0 = 1, h = 0.1

Классический метод Рунге-Кутты и точное решение при x0 = 0, xf = 3, y0 = 1, h = 0.1

Классический метод Рунге-Кутты и точное решение при x0 = 0, xf = 1, y0 = 1, h = 0.1

Сравнение методов для заданной задачи

Размер ошибки всех методов на промежутке [0, 9] с шагом 0.1

Размер ошибки всех методов на промежутке [0, 3] с шагом 0.1

Размер ошибки всех методов на промежутке [0, 1] с шагом 0.1

Очевидно что, классический метод Рунге-Кутты справляется с задачей аппроксимации в случае данного уравнения намного лучше чем Метод Эйлера и Усовершенствованный метод Эйлера.

График глобальной средней ошибки

Глобальная ошибка в зависимости от размера шага H на промежутке от 0.01 до 0.91 для x0 = 1, xf = 9

источники:

http://rus.graditasmayas.com/949958-eulers-method-in-python-YQNARF

http://github.com/mdmxfry/DE-methods

Источник

Функция Эйлера
Дано натуральное число n, определите количество натуральных чисел, меньших n и взаимно простых с n.

Входные данные
Дано натуральное число n≤109.

Выходные данные
Выведите φ(n).

ввод
10
вывод
4

Dmitry's user avatar

Dmitry

7,33410 золотых знаков22 серебряных знака51 бронзовый знак

задан 10 июн 2020 в 21:04

fox_price's user avatar

1

Ну, есть тупой способ — перебором 🙂 Для небольших n вполне годится. Для больших я бы находил простые делители n, дальше методом включения-исключения искал бы количество не взаимно простых и вычитал бы из n…

Вот, я даже на Python ухитрился написать 🙂

def fi(n):
    f = n;
    if n%2 == 0:
        while n%2 == 0:
            n = n // 2;
        f = f // 2;
    i = 3
    while i*i <= n:
        if n%i == 0:
            while n%i == 0:
                n = n // i;
            f = f // i;
            f = f * (i-1);
        i = i + 2;
    if n > 1:
        f = f // n;
        f = f * (n-1);
    return f;


print(fi(int(input())));

ответ дан 11 июн 2020 в 9:47

Harry's user avatar

HarryHarry

212k15 золотых знаков116 серебряных знаков226 бронзовых знаков

Если задача не на алгоритмы, то можно воспользоваться модулем math и методом gcd — наибольший общий делитель.
Если наибольший общий делитель для числа в последовательности и общего количества натуральных чисел равен 1, то кладем его в список.
После чего возвращаем длину этого списка.

import math

def phi(n):
    result = [i for i in range(1, n + 1) if math.gcd(n, i) == 1]
    return len(result)

print(phi(10))

# OUT
# 4

ответ дан 29 июн 2022 в 4:54

Dmitry's user avatar

DmitryDmitry

7,33410 золотых знаков22 серебряных знака51 бронзовый знак

Другое оформление способа со списком без, собственно, самого списка и с не библиотечным вычислением НОД методом Евклида, вдруг кому пригодится

def Euclid(a, b): # функция Евклида
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
return max(a, b)

def EulerFunction_Euclid(n): # функция Эйлера через Евклида
result = 0
for i in range (1,n):
    if Euclid(n,i) == 1:
        result+=1
return result

n = int(input("Enter N"))
print(EulerFunction_Euclid(n))'

ответ дан 6 окт 2022 в 23:36

Александр's user avatar

Источник

image

FizzBuzz — это известная задачка на программирование, которую обычно дают в технической части собеседований. Она формулируется примерно так:

Напишите функцию, выводящую список целых чисел от 1 до 100, но вместо каждого числа, кратного 3, она должна выводить «Fizz», а вместо каждого числа, кратного 5, выводить «Buzz». Вместо чисел, кратных и 3, 5, программа должна выводить «FizzBuzz»; все остальные числа должны выводиться без изменений.

Можно написать функцию, вообще не использующую условную логику и вместо этого разделяющую целые числа на 4 возможные категории (обычное решение оставим в качестве упражнения заинтересованному читателю):

  1. Имеющие делитель 3, но не 5
  2. Имеющие делитель 5, но не 3
  3. Имеющие делитель и 3, и 5
  4. Не имеющие делитель 3 и 5

Нам нужна функция, которая будет возвращать:

Рассмотрим реализацию такой функции на Python:

[(lambda n: { 1: n, 6: "Fizz", 10: "Buzz", 0: "FizzBuzz" }[n**4%15])(n+1) for n in range(100)]

Та же функция на Ruby:

(1..100).map{|n| {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] }

Как мы и ожидали, каждая из этих функций возвращает список целых чисел от 1 до 100 с подставленными в нужные места «Fizz», «Buzz» и «FizzBuzz».

Но почему? Откуда взялись постоянные значения 0, 6, 10 и 1? Почему

$n^4 mod 15$ возвращает 6 для чисел, кратных 3, но не 5, 10 для чисел, кратных 5, но не 3, 0 для чисел, кратных 5 и 3 и 1 во всех остальных случаях? И самое важное — справедливо ли это для любого

$n$, которое мы выберем?

I. n^4 mod 15 решает FizzBuzz

Доказательство таково:

$n^4 mod {15} = begin{cases} 0, & text{if $n$ is divisible by 3 and 5} newline 6, & text{if $n$ is divisible by 3 and coprime to 5} newline 10, & text{if $n$ is divisible by 5 and coprime to 3} newline 1, & text{if $n$ is coprime to 3 and 5} end{cases}$

Первый случай тривиален; если n делится и на 3, и на 5, то после возведения n в любую степень возвращаемый

$mod 15$ результат всегда будет равен 0, та как любое целое число с делителями 3 и 5 будет также кратным 15

$(3 * 5)$.

Во втором случае у нас есть 3 как делитель некой константы c:

$3c^4 equiv 6 pmod{15}$

или

$3c^4 mod 15 = 6$

для каждой константы c > 0, если c является взаимно простым с 5. (Если c не является взаимно простым с 5, то у нас возник первый случай, который вернёт 0.)

Для начала предположим, что

$c = 1$. Это даёт

$3^4 mod 15$ или

$81 mod 15$, что вернёт 6:

$15 * 5 = 75$, с остатком 6 от 81.

Предположим, что c является целым > 1. Применим степень к каждому множителю и воспользуемся равенством

$(ab) = (a + a(b - 1))$:

$begin{aligned} 3^4c^4 & mod 15 newline 81c^4 & mod 15 newline (81 + 81(c^4 - 1)) & mod 15 end{aligned}$

Давайте рассмотрим отдельно выражение

$c^4$. Из теоремы Эйлера в теории чисел мы знаем, что поскольку

$c$ является взаимно простым с 5, то

$c^4 mod 5$ равно 1; если

$c^4 / 5$ имеет остаток 1, то это должен быть случай, когда

$c^4 - 1$ ровно делится на 5; то есть, вне зависимости от значения

$c$, если оно является взаимно простым с 5, то

$(c^4 - 1)$ имеет делитель 5. Другой делитель не важен, поэтому давайте перепишем

$(c^4 - 1)$ как

$5x$.

Теорема Эйлера в теории чисел

Теорема Эйлера заключается в том, что

$a^{ϕ(n)} equiv 1 (mod n)$, где

$a$ является взаимно простым с

$n$, а

$ϕ$ — это пси-функция Эйлера; пси-функция

$n$ возвращает количество целых чисел меньше

$n$, являющихся взаимно простыми с

$n$. Для каждого простого числа

$p$,

$ϕ(p)$ равна

$p - 1$.

Леонард Эйлер

$begin{align} (81 + 81(5x)) &mod 15 newline (81 mod 15 + 81(5x) mod 15) &mod 15 newline (6 + 81(5x) mod 15) &mod 15 newline 6 mod 15 end{align}$

Мы можем переписать это во вторую строку благодаря следующему свойству модулярных выражений:

$(a + b) mod n = (a mod n + b mod n) mod n$. В третьей строке выражение

$81(5x)$ имеет делители и 3, и 5, поэтому

$81(5x) mod 15 = 0$, что даёт нам

$6 mod 15$, то есть 6.

То есть для любого

$c$, являющегося взаимно простым с 5 и > 1, выражение

$3c^4 mod 15$ вернёт 6.

Благодаря тому же процессу мы выясним, что

$5c^4 mod 15$ всегда возвращает 10; при

$c = 1$ мы имеем

$625 mod 15$, что равно 10. Для

$c > 1$ (взаимно простое с 3) мы можем записать

$(625 + 625(c^4 - 1)) mod 15$

Теорема Эйлера говорит нам, что если

$c$ является взаимно простым с 3, то

$c^2 equiv 1 mod 3$; но у нас есть

$c^4$. Однако

$c^4$ — это

$c^2c^2$, а поскольку

$ab mod n = ((a mod n)( b mod n)) mod n$, то

$c^4 mod 3$ также равно 1.

Опять же, если

$c^4 equiv 1 (mod 3)$, то

$(c^4 - 1)$ нацело делится на 3 и имеет делитель 3. Это снова сокращает второй член до 0, оставляя

$625 mod 15$, что снова равно 10.

У нас остаётся случай, в котором есть некое число

$c$, являющееся взаимно простым с 3 и 5. Если

$c$ равно 1, то получаем

$1 mod 15$, то есть 1.

Если

$c$ > 1, мы снова можем записать это как

$(1 + (c^4 - 1)) mod 15$. Так как мы знаем, что если

$c$ является взаимно простым с 3 и 5,

$c^4 equiv 1 (mod 3)$ и

$c^4 equiv 1 (mod 5)$, то

$(c^4 - 1)$ имеет делители 3 и 5.

Поэтому снова:

$begin{aligned} (1 + (c^4 - 1)) &mod 15 newline (1 mod 15 + (c^4 - 1) mod 15) &mod 15 newline (1 + 0) &mod 15 newline 1 &mod 15 newline 1 end{aligned}$

То есть

$n^4 mod 15$ всегда будет возвращать 0, если и 3, и 5 являются делителями

$n$, возвращать 6, если делителем является 3, но не 5, возвращать 10, если делителем является 5, но не 3, и 1, если

$n$ является взаимно простым и с 3, и с 5, а функция вида ->(n){ {1 => n, 6 => "Fizz", 10 => "Buzz", 0 => "FizzBuzz"}[n**4%15] } всегда будет возвращать правильный результат FizzBuzz для каждого

$n$ (до того, как

$n^4$ не переполнит тип integer, используемый в компьютере).

II. Решение любой задачи категории FizzBuzz

Схожую функцию можно создать для любой похожей задачи, которые я буду называть задачами категории FizzBuzz. (Задачи категории FizzBuzz: например, выводить «Foo» вместо чисел, кратных 2, «Bar» вместо чисел, кратных трём, «Baz» вместо чисел, кратных 5 и выполнить конкатенацию каждого слова для чисел, имеющих больше одного из делителей 2,3 и 5). Выбираемые в качестве делителей числа не обязаны быть простыми, но если одно из них имеет в качестве делителя другое, то некоторые группы не существуют. Например, если мы решили изменить FizzBuzz так, чтобы кратные 2 возвращали «Fizz», а кратные 4 возвращали «Buzz» (вместо традиционных 3 и 5), то увидим «Fizz» для каждого кратного 2, «FizzBuzz» для кратного 2 и 4, но никогда не увидим «Buzz», потому что не существует числа, кратного 4, являющегося взаимно простым с 2.

Представленное ниже обобщённое решение не такое уж и общее, как я сказал: существует множество пар чисел, для которого оно не сработает; поэтому делители нужно выбирать гораздо тщательнее. Оно сработает для уникальных простых чисел, но не всегда хорошо для составных чисел. Хочу поблагодарить автора этого очень подробного поста, объясняющего подробности того, почему общая формула не будет работать для составных чисел.

Написанное выше уравнение для решения FizzBuzz можно также записать в виде

$n^{LCM(ϕ(3),ϕ(5))} mod (3 cdot 5)$

где

$ϕ$ — это пси-функция Эйлера, а

$LCM$ — наименьшее общее кратное.

В общем виде для любого множества из

$k$ делителей

$n_1,n_2,..n_k$, для которого нам нужна функция типа FizzBuzz, можно использовать формулу:

$n^{LCM(ϕ(n_1),ϕ(n_2),..ϕ(n_k))} mod prod_{i=1}^k n_i$

Для функции типа FizzBuzz, возвращающей «Foo» вместо чисел, кратных 7, и «Bar» вместо чисел, кратных 11, найдём:

$n^{LCM(ϕ(7),ϕ(11))} mod (7 cdot 11)$

$ϕ(7)$ равно 6, а

$ϕ(11)$ равно 10, и

$LCM$ (наименьшее общее кратное) для 6 и 10 равно 30. То есть уравнение примет вид:

$n^{30} mod 77$

Реализация на Python:

[(lambda n: { 1: n, 7**30%77: "Foo", 11**30%77: "Bar", 0: "FooBar" }[n**30%77])(n+1) for n in range(100)]

Это даст нам ожидаемый результат:

[1, 2, 3, 4, 5, 6, 'Foo', 8, 9, 10, 'Bar', 12, 13, 'Foo', 15, 16, 17, 18, 19, 20, 'Foo', 'Bar', 23, 24, 25, 26, 27, 'Foo', 29, 30, 31, 32, 'Bar', 34, 'Foo', 36, 37, 38, 39, 40, 41, 'Foo', 43, 'Bar', 45, 46, 47, 48, 'Foo', 50, 51, 52, 53, 54, 'Bar', 'Foo', 57, 58, 59, 60, 61, 62, 'Foo', 64, 65, 'Bar', 67, 68, 69, 'Foo', 71, 72, 73, 74, 75, 76, 'FooBar', 78, 79, 80, 81, 82, 83, 'Foo', 85, 86, 87, 'Bar', 89, 90, 'Foo', 92, 93, 94, 95, 96, 97, 'Foo', 'Bar', 100]

Вывод

Итак,

$$display$$a^{LCM(ϕ(n_1),ϕ(n_2),..ϕ(n_k))} equiv begin{cases} 0pmod {prod_{i=1}^k n_i}, & text{if $n$ is divisible by every $n_1,n_2,..n_k$} newline r_1,r_2,..r_kpmod {prod_{i=1}^k n_i}, & text{a distinct result for every other combination of factors in $n_1,n_2,..n_k$} newline 1pmod {prod_{i=1}^k n_i}, & text{if $n$ is coprime to every $n_1,n_2,..n_k$} end{cases}$$display$$

… если числа

$n_1, n_2,.. n_k$ являются уникальными простыми числами. Снова благодарю автора этого поста за столь наглядную иллюстрацию этого.

Я не делаю никаких предположений о том, что существует какое-то иное практическое применение этой формулы, кроме как для решения задач категории FizzBuzz с выбранными в качестве кандидатов произвольными числами.

Источник

Improve Article

Save Article

Like Article

  • Read
  • Discuss

    • Improve Article

    Save Article

    Like Article

    According to Euclid Euler Theorem, a perfect number which is even, can be represented in the form (2^n - 1)*(2^n / 2) )) where n is a prime number and 2^n - 1 is a Mersenne prime number. It is a product of a power of 2 with a Mersenne prime number. This theorem establishes a connection between a Mersenne prime and an even perfect number.
     

    Some Examples (Perfect Numbers) which satisfy Euclid Euler Theorem are:

6, 28, 496, 8128, 33550336, 8589869056, 137438691328

Explanations:
1) 6 is an even perfect number.
So, it can be written in the form 
(22 - 1) * (2(2 - 1)) = 6
where n = 2 is a prime number and 2^n - 1 = 3 is a Mersenne prime number.

2) 28 is an even perfect number.
So, it can be written in the form 
(23 - 1) * (2(3 - 1)) = 28
where n = 3 is a prime number and 2^n - 1 = 7 is a Mersenne prime number.

3) 496 is an even perfect number.
So, it can be written in the form 
(25 - 1) * (2(5 - 1)) = 496
where n = 5 is a prime number and 2^n - 1 = 31 is a Mersenne prime number.

    Approach(Brute Force):
    Take each prime number and form a Mersenne prime with it. Mersenne prime =  where n is prime. Now form the number (2^n – 1)*(2^(n – 1)) and check if it is even and perfect. If the condition satisfies then it follows Euclid Euler Theorem. 
     

    C++

    #include <bits/stdc++.h>

    using namespace std;

    #define show(x) cout << #x << " = " << x << "n";

    bool isprime(long long n)

    {

        for (int i = 2; i * i <= n; i++)

            if (n % i == 0)

                return false;

        return true;

    }

    bool isperfect(long long n)

    {

        long long s = -n;

        for (long long i = 1; i * i <= n; i++) {

            if (n % i == 0) {

                long long factor1 = i, factor2 = n / i;

                s += factor1 + factor2;

                if (factor1 == factor2)

                    s -= i;

            }

        }

        return (n == s);

    }

    int main()

    {

        vector<long long> power2(61);

        for (int i = 0; i <= 60; i++)

            power2[i] = 1LL << i;

        cout << "Generating first few numbers "

                "satisfying Euclid Euler's theoremn";

        for (long long i = 2; i <= 25; i++) {

            long long no = (power2[i] - 1) * (power2[i - 1]);

            if (isperfect(no) and (no % 2 == 0))

                cout << "(2^" << i << " - 1) * (2^(" << i

                     << " - 1)) = " << no << "n";

        }

        return 0;

    }

    Java

    class GFG

    {

        static boolean isprime(long n)

        {

            for (int i = 2; i * i <= n; i++)

            {

                if (n % i == 0)

                {

                    return false;

                }

            }

            return false;

        }

        static boolean isperfect(long n)

        {

            long s = -n;

            for (long i = 1; i * i <= n; i++)

            {

                if (n % i == 0)

                {

                    long factor1 = i, factor2 = n / i;

                    s += factor1 + factor2;

                    if (factor1 == factor2)

                    {

                        s -= i;

                    }

                }

            }

            return (n == s);

        }

        public static void main(String[] args)

        {

            long power2[] = new long[61];

            for (int i = 0; i <= 60; i++)

            {

                power2[i] = 1L << i;

            }

            System.out.print("Generating first few numbers " +

                             "satisfying Euclid Euler's theoremn");

            for (int i = 2; i <= 25; i++)

            {

                long no = (power2[i] - 1) * (power2[i - 1]);

                if (isperfect(no) && (no % 2 == 0))

                {

                    System.out.print("(2^" + i + " - 1) * (2^(" +

                                     i + " - 1)) = " + no + "n");

                }

            }

        }

    }

    Python3

    def isprime(n):

        i = 2

        while(i * i <= n):

            if (n % i == 0):

                return False;

            i += 1

        return False;

    def isperfect(n):

        s = -n;

        i =1

        while(i * i <= n):

            if (n % i == 0):

                factor1 = i

                factor2 = n // i;

                s += factor1 + factor2;

                if (factor1 == factor2):

                    s -= i;   

            i += 1

        return (n == s);

    if __name__=='__main__':

        power2 = [1<<i for i in range(61)]

        print("Generating first few numbers satisfying Euclid Euler's theorem");

        for i in range(2, 26):  

            no = (power2[i] - 1) * (power2[i - 1]);

            if (isperfect(no) and (no % 2 == 0)):

                print("(2^{} - 1) * (2^({} - 1)) = {}".format(i, i, no))

    C#

    using System;

    using System.Collections.Generic;

    class GFG

    {

        static Boolean isprime(long n)

        {

            for (int i = 2; i * i <= n; i++)

            {

                if (n % i == 0)

                {

                    return false;

                }

            }

            return false;

        }

        static Boolean isperfect(long n)

        {

            long s = -n;

            for (long i = 1; i * i <= n; i++)

            {

                if (n % i == 0)

                {

                    long factor1 = i, factor2 = n / i;

                    s += factor1 + factor2;

                    if (factor1 == factor2)

                    {

                        s -= i;

                    }

                }

            }

            return (n == s);

        }

        public static void Main(String[] args)

        {

            long []power2 = new long[61];

            for (int i = 0; i <= 60; i++)

            {

                power2[i] = 1L << i;

            }

            Console.Write("Generating first few numbers " +

                          "satisfying Euclid Euler's theoremn");

            for (int i = 2; i <= 25; i++)

            {

                long no = (power2[i] - 1) * (power2[i - 1]);

                if (isperfect(no) && (no % 2 == 0))

                {

                    Console.Write("(2^" + i + " - 1) * (2^(" +

                                    i + " - 1)) = " + no + "n");

                }

            }

        }

    }

    PHP

    <?php

    function isprime($n)

    {

        for ($i = 2; $i * $i <= $n; $i++)

            if ($n % $i == 0)

                return false;

        return false;

    }

    function isperfect($n)

    {

        $s = -$n;

        for ($i = 1;

             $i * $i <= $n; $i++)

        {

            if ($n % $i == 0)

            {

                $factor1 = $i;

                $factor2 = $n / $i;

                $s += $factor1 + $factor2;

                if ($factor1 == $factor2)

                    $s -= $i;

            }

        }

        return ($n == $s);

    }

    $power2 = array();

    for ($i = 0; $i <= 60; $i++)

        $power2[$i] = 1<< $i;

    echo "Generating first few numbers " .

         "satisfying Euclid Euler's theoremn";

    for ($i = 2; $i <= 25; $i++)

    {

        $no = ($power2[$i] - 1) *

              ($power2[$i - 1]);

        if (isperfect($no) &&

                     ($no % 2 == 0))

            echo "(2^" . $i . " - 1) * (2^(" .

                         $i . " - 1)) = " .

                         $no . "n";

    }

    ?>

    Javascript

    <script>

        function isprime(n)

        {

            for (let i = 2; i * i <= n; i++)

            {

                if (n % i == 0)

                {

                    return false;

                }

            }

            return false;

        }

        function isperfect(n)

        {

            let s = -n;

            for (let i = 1; i * i <= n; i++)

            {

                if (n % i == 0)

                {

                    let factor1 = i, factor2 = n / i;

                    s += factor1 + factor2;

                    if (factor1 == factor2)

                    {

                        s -= i;

                    }

                }

            }

            return (n == s);

        }

            let power2 = [];

            for (let i = 0; i <= 60; i++)

            {

                power2[i] = 1 << i;

            }

            document.write("Generating first few numbers " +

                             "satisfying Euclid Euler's theorem" + "<br/>");

            for (let i = 2; i <= 25; i++)

            {

                let no = (power2[i] - 1) * (power2[i - 1]);

                if (isperfect(no) && (no % 2 == 0))

                {

                    document.write("(2^" + i + " - 1) * (2^(" +

                                     i + " - 1)) = " + no + "<br/>");

                }

            }

    </script>

    Output:

    Generating first few numbers satisfying Euclid Euler's theorem
(2^2 - 1) * (2^(2 - 1)) = 6
(2^3 - 1) * (2^(3 - 1)) = 28
(2^5 - 1) * (2^(5 - 1)) = 496
(2^7 - 1) * (2^(7 - 1)) = 8128
(2^13 - 1) * (2^(13 - 1)) = 33550336
(2^17 - 1) * (2^(17 - 1)) = 8589869056
(2^19 - 1) * (2^(19 - 1)) = 137438691328

    Time Complexity: O(sqrt(n))
    Auxiliary Space: O(1) 

    Like Article

    Save Article

    Источник

    Полное решение урока 7.8 из курса «Поколение python: курс для начинающих» с сайта stepik.org на питоне. (Предыдущий модуль 7.7)

    Установите в каком порядке, указанный вложенный цикл выведет пары чисел (i, j). 
    for i in range(1, 4):
    for j in range(3, 6):
    print(i, j)

    1 3
1 4
1 5
2 3
2 4
2 5
3 3
3 4
3 5

    Что покажет приведенный ниже фрагмент кода?
    for i in range(1, 4):
    for j in range(3, 5):
    print(i + j, end=»)

    455667

    Что покажет приведенный ниже фрагмент кода?
    counter = 0
    for i in range(99, 102):
    temp = i
    while temp > 0:
    counter += 1
    temp //= 10
    print(counter)

    8

    Таблица-1

    Дано натуральное число n(n≤ 9). Напишите программу, которая печатает таблицу размером n×3 состоящую из данного числа (числа отделены одним пробелом).

    Формат входных данных
    На вход программе подается одно натуральное число.

    Формат выходных данных
    Программа должна вывести таблицу размером n×3 состоящую из данного числа.

    Примечание. В конце строки может быть пробел.

    n = int(input())
for _ in range(n):
    for _ in range(2):         # чтобы не выводить лишний пробел в конце строки, 
        print(n, end=' ')      # во вложенном цикле выводим только два столбика,
    print(n)                   # а третий столбик выводим здесь, во внешнем цикле

    Таблица-2

    Дано натуральное число n (n≤ 9). Напишите программу, которая печатает таблицу размером n ×5, где в i-ой строке указано число i (числа отделены одним пробелом).

    Формат входных данных
    На вход программе подается одно натуральное число.

    Формат выходных данных
    Программа должна вывести таблицу размером n ×5 в соответствии с условием.

    Примечание. В конце строки может быть пробел.

    n = int(input())

for i in range(1, n+1):    # диапазон от 1 до n включительно
    for j in range(5):     # повторяем 5 раз
        print(i, end=' ')  # печатаем i и пробел в end=
    print()

    Таблица-3

    Дано натуральное число n(n≤ 9). Напишите программу, которая печатает таблицу сложения для всех чисел от 1 до n в соответствии с примером.

    Формат входных данных
    На вход программе подается одно натуральное число.

    Формат выходных данных
    Программа должна вывести таблицу сложения для всех чисел от 1 до n.

    Примечание. В конце строки может быть пробел.

    n = int(input())    
for i in range(1, n+1):            # каждый новый цикл будет выводиться следущее число i
    for g in range(1,10):          # выводим последовательность от 1 до 9 
        print(i, '+', g, '=', g+i)  # выводим таблицу сложения
    print()                        # переходим на новую строку

    Звездный треугольник ?️?️

    Дано нечетное натуральное число n. Напишите программу, которая печатает равнобедренный звездный треугольник с основанием, равным n в соответствии с примером:
    *
    **
    ***
    **
    *

    Формат входных данных
    На вход программе подается одно нечетное натуральное число.

    Формат выходных данных
    Программа должна вывести треугольник в соответствии с условием.

    Примечание. Используйте вложенный цикл for.

    n = int(input())
centr = n // 2 + 1          # находим середину
count = 0                   # кол-во звезд в строке 
for i in range(1, n + 1):
    if i > centr:           
        count -= 1          # если перешли за середину то убавляем кол-во звезд
    else:
        count += 1          # иначе прибавляем кол-во звезд
    
    for _ in range(count):  # выполняем цикл сколько нужно звезд
        print('*', end='')
    print()

    Численный треугольник 1

    Дано натуральное число n. Напишите программу, которая печатает численный треугольник в соответствии с примером:
    1
    22
    333
    4444
    55555
    …
    Формат входных данных
    На вход программе подается одно натуральное число.

    Формат выходных данных
    Программа должна вывести треугольник в соответствии с условием.

    Примечание. Используйте вложенный цикл for.

    n = int(input())
for i in range(1, n+1):    # строки n
    for j in range(i):     # столбцы 
        print(i, end='')
    print()

    12 месяцев

    Решите уравнение в натуральных числах 28n + 30k + 31m = 365.

    Примечание. Используйте вложенный цикл for. В первую очередь запишите решение с наименьшим значением n.

    n = 1
k = 4
m = 7
или
n = 2
k = 1
m = 9

    Старинная задача

    Имеется 100 рублей. Сколько быков, коров и телят можно купить на все эти деньги, если плата за быка – 10 рублей, за корову – 5 рублей, за теленка – 0.5 рубля и надо купить 100 голов скота?

    Примечание. Используйте вложенный цикл for.

    Количество быков: 
1
Количество коров: 
9
Количество телят: 90

    Гипотеза Эйлера о сумме степеней

    В 1769 году Леонард Эйлер сформулировал обобщенную версию Великой теоремы Ферма, предполагая, что по крайней мере n энных степеней необходимо для получения суммы, которая сама является энной степенью для n > 2. Напишите программу для опровержения гипотезы Эйлера (продержавшейся до 1967 года), и найдите четыре положительных целых числа, сумма 5-х степеней которых равна 5-й степени другого положительного целого числа.

    Таким образом, найдите пять натуральных чисел a,b,c,d,e удовлетворяющих условию:a5+b5+c5+d5=e5. В ответе укажите сумму a+b+c+d+e.

    Примечание 1. Используйте вложенный цикл for.

    Примечание 2. Считайте, что числа a, b, c, d, e не превосходят 150.

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

    498

    Источник

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *