Эйлер

Перевод Решение Fizzbuzz при помощи теоремы Эйлера

22.03.2021 10:20:41 |

Автор: admin

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

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

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

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

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

Fizz, если $n \equiv 0 \pmod 3$ и $inline$ является взаимно простым с 5
Buzz, если $n \equiv 0 \pmod 5$ и $inline$ является взаимно простым с 3
FizzBuzz, если $n \equiv 0 \pmod 3$ и $n \equiv 0 \pmod 5$
$inline$ во всех остальных случаях.

Рассмотрим реализацию такой функции на 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 во всех остальных случаях? И самое важное справедливо ли это для любого $inline$ , которое мы выберем?

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 $inline$ .

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

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

или

$3c^4 \mod 15 = 6$

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

Для начала предположим, что $inline$ . Это даёт $3^4 \mod 15$ или $81 \mod 15$ , что вернёт 6: $inline$ , с остатком 6 от 81.

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

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

Давайте рассмотрим отдельно выражение $inline$ . Из теоремы Эйлера в теории чисел мы знаем, что поскольку $inline$ является взаимно простым с 5, то $c^4 \mod 5$ равно 1; если $inline$ имеет остаток 1, то это должен быть случай, когда $inline$ ровно делится на 5; то есть, вне зависимости от значения $inline$ , если оно является взаимно простым с 5, то $inline$ имеет делитель 5. Другой делитель не важен, поэтому давайте перепишем $inline$ как $inline$ .

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

Теорема Эйлера заключается в том, что $a^{(n)} \equiv 1 (\mod n)$ , где $inline$ является взаимно простым с $inline$ , а $inline$ это пси-функция Эйлера; пси-функция $inline$ возвращает количество целых чисел меньше $inline$ , являющихся взаимно простыми с $inline$ . Для каждого простого числа $inline$ , $inline$ равна $inline$ .

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

$\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$ . В третьей строке выражение $inline$ имеет делители и 3, и 5, поэтому $81(5x) \mod 15 = 0$ , что даёт нам $6 \mod 15$ , то есть 6.

То есть для любого $inline$ , являющегося взаимно простым с 5 и > 1, выражение $3c^4 \mod 15$ вернёт 6.

Благодаря тому же процессу мы выясним, что $5c^4 \mod 15$ всегда возвращает 10; при $inline$ мы имеем $625 \mod 15$ , что равно 10. Для $inline$ (взаимно простое с 3) мы можем записать

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

Теорема Эйлера говорит нам, что если $inline$ является взаимно простым с 3, то $c^2 \equiv 1 \mod 3$ ; но у нас есть $inline$ . Однако $inline$ это $inline$ , а поскольку $ab \mod n = ((a \mod n)( b \mod n)) \mod n$ , то $c^4 \mod 3$ также равно 1.

Опять же, если $c^4 \equiv 1 (\mod 3)$ , то $inline$ нацело делится на 3 и имеет делитель 3. Это снова сокращает второй член до 0, оставляя $625 \mod 15$ , что снова равно 10.

У нас остаётся случай, в котором есть некое число $inline$ , являющееся взаимно простым с 3 и 5. Если $inline$ равно 1, то получаем $1 \mod 15$ , то есть 1.

Если $inline$ > 1, мы снова можем записать это как $(1 + (c^4 - 1)) \mod 15$ . Так как мы знаем, что если $inline$ является взаимно простым с 3 и 5, $c^4 \equiv 1 (\mod 3)$ и $c^4 \equiv 1 (\mod 5)$ , то $inline$ имеет делители 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 являются делителями $inline$ , возвращать 6, если делителем является 3, но не 5, возвращать 10, если делителем является 5, но не 3, и 1, если $inline$ является взаимно простым и с 3, и с 5, а функция вида

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

всегда будет возвращать правильный результат FizzBuzz для каждого $inline$ (до того, как $inline$ не переполнит тип 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)$

где $inline$ это пси-функция Эйлера, а $inline$ наименьшее общее кратное.

В общем виде для любого множества из $inline$ делителей $inline$ , для которого нам нужна функция типа 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)$

$inline$ равно 6, а $inline$ равно 10, и $inline$ (наименьшее общее кратное) для 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} 0\pmod {\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_k\pmod {\prod_{i=1}^k n_i}, & \text{a distinct result for every other combination of factors in $n_1,n_2,..n_k$} \newline 1\pmod {\prod_{i=1}^k n_i}, & \text{if $n$ is coprime to every $n_1,n_2,..n_k$} \end{cases}$$display$$

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

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

Подробнее..

Категории: Программирование , Fizzbuzz , Алгоритмы , Математика , Эйлер , Модулярная функция

Перевод Математики открыли новый фронт в битве с древней числовой задачей

24.09.2020 14:19:46 |

Автор: admin

Не одно тысячелетие математиков интересовал вопрос существования нечётных совершенных чисел. В процессе его изучения они составили невероятный список ограничений для этих гипотетических объектов. Но новые идеи на этот счёт могут появиться благодаря изучению иных близких к ним объектов.

Если нечётные совершенные числа и существуют, им придётся удовлетворять абсурдно большому списку ограничений

Будучи ещё старшеклассником, Пэйс Нильсен в середине 90-х столкнулся с математическим вопросом, над которым бьётся и по сей день. Но он не расстраивается: очаровавшая его задача, гипотеза о нечётных совершенных числах, остаётся открытой уже более 2000 лет, что делает её одной из старейших нерешённых задач математики.

Частично таким долгоживущим шармом она обязана простоте формулировки. Число называется совершенным, если это положительное целое, n, сумма делителей которого даёт удвоенное число, 2n. Первый и самый простой пример это 6, делители которого, 1, 2, 3 и 6, в сумме дают 12, или 2*6. Затем идёт 28, с делителями 1, 2, 4, 7, 14 и 28, дающими в сумме 56. Следующие примеры 496 и 8128.

Леонард Эйлер формализовал это определение в XVIII веке, введя свою сигма-функцию, обозначающую сумму делителей числа. Таким образом, для совершенных чисел (n) = 2n.

Леонард Эйлер сформулировал множество формальных правил, касающихся работы с совершенными числами

Однако Пифагор знал о совершенных числах ещё в 500 году до н.э., а два столетия спустя Евклид вывел формулу для получения чётных простых чисел. Он показал, что если p и 2^p 1 простые числа (делители которых только 1 и само это число), тогда 2^p1 * (2^p 1) будет совершенным числом. К примеру, если p = 2, то формула даёт 2¹ * (2² 1), или 6. Если p = 3, то формула даёт 2² * (2³ 1), или 28 два первых совершенных числа. 2000 лет спустя Эйлер доказал, что эта формула выдаёт все чётные совершенные числа, хотя до сих пор неизвестно, конечно или бесконечно множество совершенных чисел.

Нильсен, сегодня работающий профессором в Университете Бригама Янга, увлёкся связанным с этим вопросом: существуют ли нечётные совершенные числа? Греческий математик Никомах Герасский около 100 года н.э. заявил, что все совершенные числа должны быть чётными, но никто не доказал этого утверждения.

Как и многие его коллеги из XXI века, Нильсен считает, что совершенные числа существует не особенно много. И, вместе с ними он считает, что доказательство этой гипотезы будет получено нескоро. Однако в июне он наткнулся на новый подход к этой задаче, возможно, способный продвинуть её далее. И он связан с ближайшим к нечётным совершенным числам объектом из всех пока обнаруженных.

Сжимающаяся сеть

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

Я в своей наивности решил, что я могу сделать что-то в этой области, если в ней вообще возможен прогресс, сказал Нильсен. Это вдохновило меня на изучение теории чисел в колледже, и попытки развить прогресс. Его первая работа по нечётным совершенным числам, опубликованная в 2003 году, наложила дополнительные ограничения на эти гипотетические числа. Он показал, что не только количество нечётных совершенных чисел с k различными простыми делителями конечно, как доказал в 1913 году Леонард Диксон, но и что размер этого числа не должен превышать 2^{4^k}.

И это было не первым и не последним ограничением, наложенным на гипотетические нечётные совершенные числа. К примеру, в 1888 году Джеймс Сильвестер доказал, что нечётное совершенное число не может делиться на 105. В 1960 году Карл К. Нортон доказал, что, если нечётное совершенное число не делится на 3, 5 или 7, у него должно быть не менее 27 простых делителей. Пол Дженкинс в 2003 году доказал, что крупнейший простой делитель нечётного совершенного числа должен быть больше 10 000 000. Паскаль Очем и Михаёль Рао после этого обнаружили, что нечётное совершенное число должно быть больше 10¹⁵⁰⁰, а потом отодвинули эту границу до 10²⁰⁰⁰. Нильсен в 2015 году показал, что нечётное совершенное число должно иметь не менее 10 различных простых делителей.

Пэйс Нильсен, математик из Университета Бригама Янга

Даже в XIX веке количество ограничений было таким, что Сильвестер сделал вывод, что появление нечётного совершенного числа этакий побег от сложной сети условий, окружающих его со всех сторон будет практически чудом. Спустя более ста лет подобного развития событий существование таких чисел вызывает ещё больше сомнений.

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

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

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

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

Разбираемся в совершенных числах

Сигма-функция обозначает сумму делителей числа. (n) = 2n, если это совершенное число.

Примеры:

(20) = 1 + 2 + 4 + 5 + 10 + 20 = 42; 2 * 20 42, поэтому 20 не совершенное число.
(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56; 2 * 28 = 56, поэтому 28 совершенное число.

Правила Эйлера

1. (a b) = (a) (b) в том, и только в том случае, если a и b взаимно простые.
2. (p^a) = 1 + p + p² + + p^a для любого простого p с положительной целой степенью a.

Примеры:

(20) = (2² 5) = (2²) (5) [по первому правилу] = (1 + 2 + 2²)(1+5) [по второму правилу] = 42

(28) = (2² 7) = (2²) (7) [по первому правилу] = (1 + 2 + 2²)(1+7) [по второму правилу] = 56

Новые соблазнительные промахи

Первую имитацию нечётного совершенного числа нашёл в 1638 году Рене Декарт и он был одним из первых выдающихся математиков, посчитавших возможным существование нечётных совершенных чисел. Я считаю, что Декарт пытался найти нечётные совершенные числа, и его вычисления привели его к первой имитации, сказал Уильям Бэнкс, специалист по теории чисел из Университета Миссури. Судя по всему, Декарт надеялся, что созданное им число можно изменить, получив настоящее нечётное совершенное число.

Но прежде чем углубиться в декартовскую имитацию, полезно будет немного разобраться в том, как математики описывают совершенные числа. Теорема времён Евклида утверждает, что любое целое число, большее 1, можно выразить в виде произведения простых чисел, возведённых в определённые степени. К примеру, 1260 можно так разложить на множители: 1260 = 2² 3² 5¹ 7¹, и не перечислять все 36 множителей по отдельности.

Если число принимает такую форму, вычислять сигма-функцию Эйлера, суммирующую его делители, становится гораздо проще благодаря двум формулам, которые тоже доказал Эйлер. Во-первых, он продемонстрировал, что (a b) = (a) (b), тогда, и только тогда, когда a и b взаимно простые то есть, у них нет общих простых делителей. К примеру, числа 14 (2 7) и 15 (3 5) взаимно простые. Во-вторых, он показал, что для любого простого числа p в положительной целой степени a, (p^a) = 1 + p + p² + + p^a.

Возвращаясь к нашему предыдущему примеру, (1 260) = (2² 3² 5¹ 7¹) = (2²) (3²) (5¹) (7¹) = (1 + 2 + 2²)(1 + 3 + 3²)(1 + 5)(1 + 7) = 4 368. Обратите внимание, что в данном случае (n) не равняется 2n, а, значит, 1260 не совершенное число.

Рене Декарт нашёл первую имитацию совершенного числа

Теперь мы можем разобрать декартову имитацию число 198 585 576 189, или 3² 7² 11² 13² 22 021¹. Повторяя описанные выше вычисления, мы обнаружим, что (198 585 576 189) = (3² 7² 11² 13² 22,021¹) = (1 + 3 + 3²)(1 + 7 + 7²)(1 + 11 + 11²)(1 + 13 + 13²)(1 + 22,021¹) = 397 171 152 378. И это равно удвоенному изначальному числу, что означает, что оно должно быть настоящим совершенным числом вот только число 22 021 не является простым.

Поэтому это число Декарта является имитацией. Если мы притворимся, что 22 021 простое, и применим правила Эйлера для сигма-функции, число Декарта ведёт себя как совершенное число. Однако 22 021 на деле является произведением 19² и 61. Если бы мы правильно записали число Декарта, как 3² 7² 11² 13² 19² 61¹, тогда (n) не равнялась бы 2n. Ослабляя некоторые правила, мы получаем число, вроде бы удовлетворяющее нашим требованиям такова суть имитации.

На то, чтобы открыть второе число-имитацию нечётного совершенного числа, ушёл 361 год. Войт сделал это в 1999 году, и опубликовал открытие через четыре года. Почему так долго? Находка числа-имитации похожа на находку нечётного совершенного числа; оба они сходным образом арифметически сложны, сказал Бэнкс. Да и их поиски не были в приоритете у математиков. Однако Войта вдохновил отрывок из книги Ричарда Гая Нерешённые задачи теории чисел, где писали о поисках новых имитаций. Войт попытался, и в итоге нашёл новую имитацию, 3⁴ 7² 11² 19² (127)¹, или 22 017 975 903.

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

Имитации нечётных совершенных чисел

Число Декарта:

198 585 576 189, или 3² 7² 11² 13² 22 021¹.

Повторим вычисления сигма-функции: (198 585 576 189) = (3² 7² 11² 13² 22,021¹) = (1 + 3 + 3²)(1 + 7 + 7²)(1 + 11 + 11²)(1 + 13 + 13²)(1 + 22,021¹) = 397 171 152 378 = 2 198 585 576 189.

Но число 22 021 не является простым, это 19² 61. Число Декарта является лишь имитацией нечётного совершенного числа.

Число Войта:

22 017 975 903, или 3⁴ 7² 11² 19² (127)¹.

Повторим вычисления сигма-функции: (22 017 975 903) = (3⁴ 7⁴ 11² 19² (-127)¹) = (1 + 3 + 3² + 3³ + 3⁴)(1 + 7 + 7²)(1 + 11 + 11²)(1 + 19 + 19²)(1 + (-127)¹) = -44 035 951 806 = 2 22 017 975 903

-127 число отрицательное, поэтому число Войта ещё одна имитация совершенного числа.

После того, как Войт в декабре 2016 года провёл семинар в университете Бригама Янга, он обсудил это число с Нильсеном, Дженкинсом и другими. Вскоре после этого команда университета отправилась на систематические вычислительные поиски других имитаций. Они выбирали наименьшие основания и показатели степени, вроде 3², и потом компьютеры прочёсывали варианты дополнительных оснований и степеней, которые давали бы имитацию совершенного числа. Нильсен решил, что этот проект просто будет неким стимулирующим опытом исследований для его студентов, однако результаты анализа превзошли его ожидания.

Просеивая возможности

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

Группа обнаружила, что для любого заданного количества оснований, k, существует конечно число имитаций, что совпадает с результатом Диксона от 1913 года для настоящих нечётных совершенных чисел. Однако если k уйдёт в бесконечность, количество имитаций также становится бесконечным, сказал Нильсен. Это было неожиданно, добавил он, учитывая, что начиная этот проект, он не был уверен в открытии хотя бы одной новой нечётной имитации, не говоря уже о том, чтобы показать, что их число бесконечно.

Ещё один сюрприз, зародившийся из результата, впервые доказанного Эйлером: все простые основания нечётного совершенного числа, кроме одного, должны иметь чётные степени. Одно должно иметь нечётную степень она называется степенью Эйлера. Большинство математиков считает, что степень Эйлера для нечётных совершенных чисел всегда 1, однако команда показала, что у имитаций она может быть сколько угодно большой.

Некоторые находки команда обнаружила, ослабив требования в определении имитации, поскольку не существует чётких математических правил для их описания только то, что они должны удовлетворять равенству (n) = 2n. Исследователи допустили существование оснований, не являющихся простыми числами (как в примере Декарта) и отрицательных оснований (как в примере Войта). Однако они пошли дальше, разрешив имитациям иметь несколько одинаковых оснований. Одно основание, к примеру, может быть 7², а другое 7³, и записываются они отдельно, а не как 7⁵. Или они позволяли основаниям повторяться, как в имитации 3² 7² 7² 13¹ (19)². Член 7² 7² можно записать как 7⁴, но тогда имитации не получится, потому что раскрытие скобок в изменённой сигма-функции было бы другим.

Учитывая значительную разницу между имитациями и реальными нечётными совершенными числами, можно задать вопрос: и как же первые помогают в поисках вторых?

Путь вперёд?

Нильсен сказал, что имитации являются обобщением нечётных совершенных чисел. Нечётные совершенные числа это подмножество внутри более обширного семейства, куда входят и имитации, поэтому у нечётных совершенных чисел должны быть все свойства имитаций, а также дополнительные, ещё более жёсткие ограничения (как, к примеру, условие, что все основания должны быть простыми).

Любое поведение более крупного множества должно соблюдаться и для мелкого подмножества, сказал Нильсен. Так что, если мы найдём поведение имитаций, неприменимое к более ограниченному классу, мы автоматически сможем отказаться от возможности существования нечётных совершенных чисел. Если, к примеру, можно будет показать, что все имитации делятся на 105 что невозможно для нечётных совершенных чисел, как Сильвестер показал в 1888 тогда задача будет решена.

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

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

Другие эксперты по нечётным совершенным числам настроены не так оптимистично. Команда из университета Бригама Янга проделала отличную работу, сказал Войт, но я не уверен, что мы приблизились к вариантам атаки на проблему нечётных совершенных чисел. Это и правда задача на века, и, вероятно, она будет таковой оставаться.

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

Нильсен согласился, что шансов на успех тут мало, но чтобы решить эту древнюю задачу, математикам надо попробовать всё. Кроме того, исследование имитаций только начинается. Его группа предприняла некие ранние шаги, и уже открыла неожиданные свойства этих чисел. Поэтому он оптимистично относится к возможности открытия дополнительных скрытых структур внутри имитаций.

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

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

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

Подробнее..

Категории: Научно-популярное , Математика , Совершенные числа , Эйлер , Теория чисел

	Русский
	English