Сито Лемера - Lehmer sieve

Лехмер сито - примитивный цифровой компьютер когда - то для нахождения простых чисел и решение простых диофантовых уравнений .

Сита Lehmer - это механические устройства, которые применяют сита в теории чисел . Сита Lehmer названы в честь Деррика Нормана Лемера и его сына Деррика Генри Лемера . Отец в то время был профессором математики в Калифорнийском университете в Беркли , а сын пошел по его стопам в качестве теоретика чисел и профессора в Беркли.

Сито в целом предназначено для поиска чисел, которые являются остатками от деления набора чисел на второй набор. Обычно они используются при нахождении решений диофантовых уравнений или для факторизации чисел. Сито Лемера сигнализирует о том, что такие решения могут быть найдены разными способами в зависимости от конкретной конструкции.

строительство

Первое сито Лемера в 1926 году было изготовлено с использованием велосипедных цепей различной длины со стержнями в соответствующих местах цепей. Когда цепи вращались, стержни замыкали электрические переключатели , и когда все переключатели замыкались одновременно, создавая полную электрическую цепь , решение было найдено. Сита Lehmer были очень быстрыми, в одном конкретном случае факторинг

${\ displaystyle 2 ^ {93} + 1 = 3 \ times 3 \ times 529510939 \ times 715827883 \ times 2903110321}$

за 3 секунды.

Созданное в 1932 году устройство с шестеренками было показано на выставке Century of Progress в Чикаго . У них были шестерни, представляющие числа, как и раньше, с отверстиями на цепях. Оставленные отверстия оставались открытыми, и искали остатки. Когда отверстия совпадали, свет на одном конце устройства попадал на фотоэлемент на другом, что могло остановить машину, позволяя наблюдать раствор. Это воплощение позволяло проверять пять тысяч комбинаций в секунду.

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

Несколько сит Лемера выставлены в Музее компьютерной истории . С тех пор та же основная идея использовалась при разработке сит в интегральных схемах или программном обеспечении .

Смотрите также

• Сито Эратосфена

Ссылки

дальнейшее чтение

• Лемер, Д. Н. (1932), "Охота на крупную дичь в теории чисел" , Scripta Mathematica , 1 : 229–235.
• Лехмер, DH (1928), "Механическое сочетание линейных форм", American Mathematical Monthly , Математическая ассоциация Америки, 35 (3): 114-121, DOI : 10,2307 / 2299504 , JSTOR  2299504. Также онлайн на домашней странице Antique Computer.
• Бейлер, Альберт Х. (1964), Развлечение в теории чисел , Дувр, главы XX, XXI.
• Уильямс, Майкл Р. (2002), Лемер Сивз.

внешние ссылки

• Сита Лемера , доктор Майкл Р. Уильямс, главный хранитель Музея компьютерной истории
• Сита Лемера в Музее компьютерной истории (внизу страницы)