Я знаю проблему

Графическая демонстрация того, что 1 = 1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1/(2×3×11×23×31). Каждый ряд из k квадратов со стороной 1/ k имеет общую площадь 1/ k , и все квадраты вместе в точности покрывают больший квадрат площадью 1. Нижний ряд из 47058 квадратов со стороной 1/47058 слишком мал, чтобы его можно было увидеть в на рисунке так и не показано.

В чисел теории проблема Знама спрашивает, какие наборы целых чисел обладают тем свойством, что каждое целое число в наборе является собственным делителем произведения других целых чисел в наборе плюс 1. Проблема Знама названа в честь словацкого математика Штефана Знама , который предложил это в 1972 году, хотя примерно в то же время другие математики рассматривали аналогичные проблемы.

Начальные члены последовательности Сильвестра почти решают эту проблему, за исключением того, что последний выбранный член равен единице плюс произведение остальных, а не является собственным делителем. Сан (1983) показал, что существует по крайней мере одно решение (собственной) проблемы Знама для каждого $k\geq 5$. Решение Сана основано на повторении, аналогичном последовательности Сильвестра, но с другим набором начальных значений.

Проблема Знама тесно связана с египетскими дробями . Известно, что при любом фиксированном числе решений существует лишь конечное число решений. $k$. Неизвестно, существуют ли какие-либо решения проблемы Знама с использованием только нечетных чисел , и остается еще несколько открытых вопросов .

Проблема

Проблема Знама спрашивает, какие наборы целых чисел обладают тем свойством, что каждое целое число в наборе является собственным делителем произведения других целых чисел в наборе плюс 1. То есть, учитывая $k$, какие наборы целых чисел $$\{n_{1},\ldots ,n_{k}\}$$ существуют ли такие, что для каждого $i$, $n_{i}$ делит, но не равно $${\Bigl (}\prod _{j\neq i}^{n}n_{j}{\Bigr )}+1?$$ Тесно связанная проблема касается наборов целых чисел, в которых каждое целое число в наборе является делителем, но не обязательно собственным делителем, одного плюс произведение других целых чисел в наборе. Эта проблема, похоже, не была названа в литературе и будет называться несобственной проблемой Знама. Любое решение проблемы Знама является также решением несобственной проблемы Знама, но не обязательно наоборот.

История

Проблема Знама названа в честь словацкого математика Штефана Знама , который предложил ее в 1972 году. Барбо (1971) поставил несобственную проблему Знама для $k=3$и Морделл (1973) , независимо от Знама, нашли все решения несобственной задачи для $k\leq 5$. Скула (1975) показал, что проблема Знама неразрешима для $k<5$и поблагодарил Й. Янака за нахождение решения. $\{2,3,11,23,31\}$ для $k=5$.

Примеры

Последовательность Сильвестра — это целочисленная последовательность , в которой каждый член равен единице плюс произведение предыдущих членов. Первые несколько членов последовательности :

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (последовательность A000058 в OEIS ).

Ранняя остановка последовательности приводит к набору вроде $\{2,3,7,43\}$ это почти соответствует условиям задачи Знама, за исключением того, что наибольшее значение равно единице плюс произведение других членов, а не является собственным делителем. Таким образом, это решение несобственной проблемы Знама, но не решение проблемы Знама, как ее обычно определяют.

Одно из правильных решений проблемы я знаю, потому что $k=5$, является $\{2,3,7,47,395\}$. Несколько расчетов покажут, что

3 × 7 × 47 × 395	+ 1 =	389866,		которое делится на 2, но не равно 2,
2 × 7 × 47 × 395	+ 1 =	259911,		которое делится на 3, но не равно 3,
2 × 3 × 47 × 395	+ 1 =	111391,		которое делится на 7, но не равно 7,
2 × 3 × 7 × 395	+ 1 =	16591,		которое делится на 47, но не равно 47, и
2 × 3 × 7 × 47	+ 1 =	1975,		которое делится на 395, но не равно.

Подключение к египетским дробям

Любое решение несобственной проблемы Знама эквивалентно (через деление на произведение значений $x_{i}$) к решению уравнения $$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=y,$$ где $y$ а также каждый $x_{i}$ должно быть целым числом, и наоборот, любое такое решение соответствует решению несобственной задачи Знама. Однако все известные решения имеют $y=1$, поэтому они удовлетворяют уравнению $$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=1.$$ То есть они приводят к представлению числа один в египетской дроби как суммы единичных дробей . В нескольких цитируемых статьях по проблеме Знама также изучаются решения этого уравнения. Брентон и Хилл (1988) описывают применение уравнения в топологии для классификации особенностей на поверхностях: и Домарацки и др. (2005) описывают приложение к теории недетерминированных конечных автоматов .

Количество решений

Число решений задачи Знама для любого $k$ конечно, поэтому имеет смысл подсчитать общее количество решений для каждого $k$. Сан (1983) показал, что существует по крайней мере одно решение (собственной) проблемы Знама для каждого $k\geq 5$. Решение Сана основано на повторении, аналогичном последовательности Сильвестра, но с другим набором начальных значений. Число решений для малых значений $k$, начиная с $k=5$, образует последовательность

2 , 5 , 18 , 96 (последовательность A075441 в OEIS ).

На данный момент известно несколько решений $k=9$ и $k=10$, но неясно, сколько решений остается неоткрытым для этих значений $k$. Однако решений бесконечно много, если $k$ не зафиксировано: Цао и Цзин (1998) показали, что для каждой задачи существует как минимум 39 решений. $k\geq 12$, улучшая предыдущие результаты, доказывая существование меньшего количества решений; Сунь и Цао (1988) предполагают , что количество решений для каждого значения $k$ растет монотонно с $k$.

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

См. также

• Номер Джуги
• Первичное псевдосовершенное число

Ссылки

Источники

• Барбо, GEJ (1971), «Задача 179», Canadian Mathematical Bulletin , 14 (1): 129 .
• Брентон, Лоуренс; Хилл, Ричард (1988), «О диофантовом уравнении ${\textstyle 1=\sum 1/n_{i}+1/\prod n_{i}}$ и класс гомологически тривиальных комплексных особенностей поверхности» , Pacific Journal of Mathematics , 133 (1): 41–67, doi : 10.2140/pjm.1988.133.41 , MR   0936356 .
• Брентон, Лоуренс; Василиу, Ана (2002), «Проблема Знама», Mathematics Magazine , 75 (1): 3–11, doi : 10.2307/3219178 , JSTOR   3219178 .
• Буцке, Уильям; Джадже, Линда М.; Майерник, Дэниел Р. (2000), «Об уравнении ${\textstyle \sum _{p|N}{\frac {1}{p}}+{\frac {1}{N}}=1}$, псевдосовершенные числа и идеально взвешенные графики» , Mathematics of Computation , 69 : 407–420, doi : 10.1090/S0025-5718-99-01088-1 , MR   1648363 .
• Цао, Чжэнь Фу; Цзин, Ченг Мин (1998), «О числе решений проблемы Знама», J. Harbin Inst. Тех. , 30 (1): 46–49, МР   1651784 .
• Цао, Чжэнь Фу; Лю, Руй; Чжан, Лян Жуй (1987), «Об уравнении ${\textstyle \sum _{j=1}^{s}(1/x_{j})+(1/(x_{1}\cdots x_{s}))=1}$ и проблема Знама», Journal of Number Theory , 27 (2): 206–211, doi : 10.1016/0022-314X(87)90062-X , MR   0909837 .
• Домарацкий, Майкл; Эллул, Кейт ; Шалит, Джеффри; Ван, Минг-Вэй (2005), «Неуникальность и радиус циклических унарных NFA» , Международный журнал основ компьютерных наук , 16 (5): 883–896, doi : 10.1142/S0129054105003352 , MR   2174328 .
• Янак, Ярослав; Скула, Ладислав (1978), "О целых числах ${\textstyle x_{i}}$ для чего ${\textstyle x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1}$», Math. Slovaca , 28 (3): 305–310, MR   0534998 .
• Морделл, Л.Дж. (1973), «Системы сравнений», Canadian Mathematical Bulletin , 16 (3): 457–462, doi : 10.4153/CMB-1973-077-3 , MR   0332650 .
• Скула, Ладислав (1975), «К проблеме Знама», Acta Fac. Рерум Натур. унив. Коменианец. Математика. (русское, словацкое резюме), 32 : 87–90, МР   0539862 .
• Сунь, Ци (1983), «К проблеме Ш. Знама», Сычуань Даксуэ Сюэбао (4): 9–12, MR   0750288 .
• Солнце, Ци; Цао, Чжэнь Фу (1988), «Об уравнении ${\textstyle \sum _{j=1}^{s}1/x_{j}+1/x_{1}\cdots x_{s}=n}$ и количество решений проблемы Знама», Northeastern Mathematics Journal , 4 (1): 43–48, MR   0970644 .

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

• Primefan, Решения проблемы Знама
• Вайсштейн, Эрик В. , «Я знаю задачу» , MathWorld