Задача Знама ({g;gcg {ugbg)

Графическая демонстрация равенства 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 слишком мала, чтобы её отразить на рисунке.

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

Одно решение несобственной задачи легко получить для любого k — первые k членов последовательности Сильвестра имеют требуемые свойства. Сан показал, что имеется по меньшей мере одно решение (собственной) задачи Знама для любого k ≥ 5. Решение Сана основывается на рекуррентном соотношении, подобном соотношению для последовательности Сильвестера, но с другим множеством начальных значений.

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

Задача

Задача Знама спрашивает, какие множества k целых чисел имеют свойство, что каждое целое в множестве является собственным делителем произведения других целых чисел в множестве плюс 1. То есть, если дано число k, какие существуют множества целых чисел

$\{n_{1},\ldots ,n_{k}\}$,

таких, что для любого i число n_i делит, но не равен

${\Bigl (}\prod _{j\neq i}^{n}n_{j}{\Bigr )}+1$

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

История

Задача Знама названа по имени словацкого математика Стефана Знама, который предложил задачу в 1972. Барбо предложил несобственную задачу Знама для k = 3, а Морделл, нашёл все решения несобственной задачи для k ≤ 5. Скула показал, что задача Знама не имеет решений для k < 5, и приписывает Я. Янаку нахождение решения {2, 3, 11, 23, 31} для k = 5.

Примеры

Одно из решений для 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, но не равно 395.

Интересное "чуть не решение" для k = 4 — множество {2, 3, 7, 43}, образованное четырьмя первыми членами последовательности Сильвестера. Множество имеет свойство, что каждое целое число в множестве делит произведение других членов множества плюс 1, но последний член этого множества равен произведению первых трёх членов плюс единица, так что этот член не является собственным делителем. Таким образом, это решение является решением несобственной задачи Знама, а не задачи Знама.

Связь с египетскими дробями

Любое решение несобственной задачи Знама эквивалентно решению уравнения

$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=y,$ (Ф1)

где y, как и любой x_i, должен быть целым числом. Чтобы это показать, рассмотрим

$X_{i}=\prod _{j\neq i}^{n}x_{j}$ (Ф2)

Заметим, что все $x_{i}$ должны быть взаимно просты (иначе общий делитель $x_{i}$ и $x_{j}$ должен делить $X_{i}$ и $X_{i}+1$). Положим

$N=\sum _{1}^{n}X_{i}+1$ (Ф3)

По тем же причинам, что и выше, любое $x_{i}$ делит $N$, а поскольку они все взаимнопросты, $N$ делится на произведение $\prod _{j\neq i}^{n}x_{j}$. Разделим теперь обе части уравнения (Ф3) на $\prod _{j\neq i}^{n}x_{j}$, получим (Ф4)

Обратно — все решения уравнения (Ф1) соответствуют решениям несобственной задачи Знама. Однако для всех известных решений y = 1, так что они удовлетворяют уравнению

$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=1.$ (Ф4)

Таким образом, это ведёт к представлению числа единица в виде египетской дроби, суммы долей единицы. Некоторые из цитируемых статей о задаче Знама изучают также решения этого уравнения. Брентон и Хилл описывают приложение уравнения (Ф4) в топологии для классификации особенностей поверхностей, а Домарацки и др. описывают приложение к теории недерминированных конечных автоматов.

Число решений

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

Брентон и Василиу после вычислений нашли, что число решений для малых значений k, начиная с k = 5, образуют последовательность

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

На настоящий момент несколько решений известны для k = 9 и k = 10, но не известно, сколько решений осталось не найдено для этих значений. Однако, если k не фиксировано, существует бесконечно много решений — Цао и Цзин показали, что имеется по меньшей мере 39 решений для любого k ≥ 12, что улучшает более ранний результат, в котором доказано существование меньшего количества решений. Сан и Цао высказали предположение, что число решений для каждого k растёт монотонно от k.

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

Ссылки

• Primefan. Solutions to Znám's Problem  (неопр.).
• Weisstein, Eric W. Znám's Problem (англ.) на сайте Wolfram MathWorld.