Простые числа и многозначные логики

info@vsetut.pro

Стать автором

Вернуться

05.09.2025 07:56:54 | Хабр

Хабы: Математика, Алгоритмы, Будущее здесь, Визуализация данных, Информационная безопасность

Интересным является вопрос о погружении арифметики в n+1-значные логики Лукасевича Ł_n+1. Какая часть арифметики может быть погружена в Ł_n+1? Для функции φ(х) = m рассматривается обратная к ней, определяемая соотношением φ ^–1(m) = {n, φ(n) = m}, где φ(х) – функция Эйлера.
Пример, если φ(n) = 4, то это уравнение имеет ровно четыре решения φ ^–1(4) = {5, 8, 10, 12}. Гольдбахом (1690 –1764) поставлена проблема о разложении четных чисел ≥ 4 на сумму двух простых. Если это верно, то для каждого числа m найдутся простые числа р и q такие, что φ(р) + φ(q) = 2m.
Эдмунд Ландау в 1912 г. на международном конгрессе математиков в Кембридже заявил, что проблема Гольдбаха недоступна для современного состояния науки. Недоступна она и сейчас. Верифицируемость предположения Гольдбаха установлена до 4∙10¹⁴.
Делались попытки найти формулу, с помощью которой вычислялись бы (или порождались) все простые числа. Наилучший результат принадлежит Ю.В. Матиясевичу (1977), который нашел полином из 10 переменных. Асимптотическое распределение простых чисел в НРЧ, доказываемое аналитическими методами, приводится в книге К. Прахара (1967). О первых 50 млн простых чисел статья Д. Цагера (1984).
Можно считать, что впервые на проблему решения подобных уравнений обратил внимание Э. Люка (1842 – 1891). Об этом сказано в книге И.В. Арнольда (1939) «… следуя Люка, сгруппированы числа n с одним и тем же значением функции φ(n) в пределах от 1 до 100, т.е. дана таблица функции обратной по отношению φ(n)»
В книге Серпинского (1968) задача №245 «Найти все натуральные числа n≤ 30, для которых φ(n) = d(n), где φ(n) – функция Эйлера, а число d(n) – число натуральных делителей числа n». Рассмотрим только случай n = 30. Делителями числа 30 являются числа 1, 2, 3, 5, 6, 10, 15 и 30, т.е. d(n = 30) = 8. Значит надо решить уравнение φ(30) = 8, где n≤ 30. Или, по-другому, найти значения для обратной функции Эйлера φ ^–1(8), т.е. определить множество {n, φ (n) = 8} для n≤ 30. Это множество образовано числами {15, 16, 20, 24, 30}. Более того, ни для каких других n >30 φ (n) ≠ 8.
Множество значений φ ^–1(m) = Ø пусто для всех нечетных значений и многих четных значений m > 1. В первой сотне числа 14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94 и 98 не являются значениями φ (n).

Подробнее