Подробности

    ЦифроМахИгры и ГоловоломкиГоловоломки → Гонки по вертикали, или Числа Ферма от Эйлера до наших дней

    Гонки по вертикали, или Числа Ферма от Эйлера до наших дней

    простые числа

    Практически все компьютеры, которые используются людьми, выполняют очень мало полезной работы. Большую часть времени, которое они находятся во включенном состоянии, они только потребляют электричество. На компьютерах набирают тексты, ведут бухгалтерию, бродят по Интернету, играют в игры и т.д. Но ведь потенциал современных компьютеров гораздо выше. Обработка нажатий на клавишу или щелчок мыши занимает микросекунды, а оставшееся время процессор ничем не занят, превращая компьютер в дорогой обогревательный прибор. Можно даже сказать, что обычный PC 99% своей мощности не использует в течении всего срока эксплуатации.

    "Компьютерра" не раз рассказывала о распределенных проектах, позволяющих не только обогревать комнату, в которой стоит ваш компьютер, но и делать полезные вычисления параллельно основной работе. Известный проект SETI@Home ищет слабые сигналы от других миров и пытается сделать новые открытия в астрономии. Математический проект GIMPS1 ищет самые большие простые числа Мерсенна которые имеют вид Mp=2p-1 и даже предлагает крупный денежный приз в случае обнаружения нового простого числа Мерсенна. За 5 лет работы этого проекта (при использовании десятков тысяч компьютеров во всем мире) найдено только 4 таких числа.

    Но в SETI@Home не ясны реальные результаты отдельного участника, а в GIMPS забрать приз еще менее вероятно, чем выиграть иномарку у Якубовича.

    Дорогой читатель, надеюсь, Вы не являетесь Геростратом, который сжег храм Артемиды, чтобы оставить свое имя в истории. Возможно, Вы не Эйлер. Но все же Вы хотите, чтобы Ваше имя осталось в истории навечно? У вас есть хороший шанс - став участником распределенного проекта "Поиск делителей для чисел Ферма" (FermatSearch). Проект создан русским человеком, автором этой статьи. И я попытаюсь подробно рассказать любителям математики и компьютеров об этой затее.

    Эти непростые простые числа

    Простые числа будоражили воображение математиков с древнейших времен. Еще Евклид доказал, что простых чисел бесконечно много, но их распределение носит весьма неравномерный характер. Есть простые числа-близнецы, разность между которыми равна 2, но существуют сколь угодно большие промежутки, в которых простых чисел нет. Поэтому распределение простых чисел было названо заколдованным. Были предприняты попытки построить функции, значениями которых были бы только простые числа, но и таких функций пока нет2. Можно доказать, что никакой многочлен, отличный от постоянной, с целыми коэффициентами не может для всех n или для всех достаточно больших n, представлять простые числа. Вполне естественным является рассмотрение показательных функций типа:

    f(n)=an ± bn, где a, b, n -целые числа.

    Для случая когда берется знак минус:

    an - bn=(a-b)(an-1+an-2b+...+bn-1)

    в этой формуле простые числа могут появиться лишь при a - b=1 и простом показатели степени. Для a=2, b=1 получаются числа Мерсенна. Во втором случае число:

    an + bn=(a+b)(a2n-a2n-1b+...+b2n)

    может быть простым лишь тогда, когда n является степенью числа 2. Для a=2, b=1 получаются числа вида:

    Fm=

    Первым человеком изучавшим эти числа был величайший математик средневековья Пьер Ферма, позже числа данного вида назвали в его честь. В письме датированное 25-м декабря 1640 года к своему другу и коллеге Мерсенну Ферма заметил, что при m=0, 1, 2, 3, 4 (соответственно F0=3, F1=5, F2=17, F3=257, F4=65537) все эти числа являются простыми. Он считал, что F5=429496729 простое число, так как не смог найти для него делитель. и попытался "догадаться", что все числа этого вида простые. Ни Мерсенн, ни Ферма не решали эту проблему, хотя могли бы. В том же 1640 году Ферма доказал свою малую теорему:

    "Для всякого простого числа p и натурального x число xp-1 -1 делится на p".

    Если не делится, следовательно p не является простым числом. Используя свою теорему, Ферма мог бы проверить 5-е число, использовав всего 32 операции возведения в квадрат по модулю 232+1, получил бы число 3029026160 и этим доказал, что F5 составное, даже не находя его делителей. Начиная с 1640 г. Ферма упорно искал доказательство для своего ложного предположения относительно простоты чисел Fm и предлагал найти его своим корреспондентам. В 1659 г. Ферма в письме к Каркави уже указывал, что теорема о простоте Fm может быть доказана методом бесконечного спуска. Потребовалось 92 года и гений Леонарда Эйлера, чтобы опровергнуть это утверждение. Эйлер разложил F5 на множители: 641 и 6700417. Ему было тогда 25 лет и он любил разные вычислительные задачи. Но для достижения этого результата он действовал не вслепую (в конце жизни великий Эйлер ослеп на один глаз от титанической вычислительной работы, которую сумел выполнить в рекордно короткий срок), а доказал факт, что всякий делитель числа Ферма имеет вид k*2m+1 +1. Таким образом, Эйлер проверял всего 10 делителей вида 64k+1.

    В 1878 Эдуард Люка (Lucas) усилил этот результат: каждый делитель числа Ферма имеет вид: k*2m+2 +1 при любом k.

    Когда "королю математиков" Карлу Гауссу было всего 19 лет, он доказал, что с помощью циркуля и линейки можно построить правильный N- угольник для простого N тогда и только тогда, когда N=Fm= - простое число. Таким образом, можно построить 3, 5, 17, 257 и 65537 угольники. Сам Гаусс построил 17 -угольник. Ришело на 80 страницах указал построение 257 угольника. В гёттингенской библиотеке в чемоданах больших размеров хранится способ построения правильного 65537-угольника, выполненное неким Гермесом. По этому поводу Джеймс Литлвуд пошутил: "Один навязчивый аспирант достал своего руководителя, и тот сказал ему: "Идите и разработайте способ построения правильного 65537-угольника!" Аспирант ушел и вернулся только через 20 лет". Как видите, многие величайшие математики увлекались этими забавными числами. Увлечение это не пропало и сегодня, особенно с возникновением компьютеров. А с приходом в нашу жизнь Интернета усилия людей разных стран стали совместными.



  • Результаты матчей

    Так как за каждый выигрыш дают по 3 очка, а за ничью - по одному очку, то у Ювентуса один выигрыш и две ничьих, у Пармы и Милана - по одному выигрышу, одной ничьей и одному проигрышу, а Лацио один раз выиграл и дважды проиграл

     
  • Источник: http://arbuz.uz