Задача Знама

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

Графическая демонстрация равенства 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 — первые k членов последовательности Сильвестра имеют требуемые свойства. Сан^[1] показал, что имеется по меньшей мере одно решение (собственной) задачи Знама для любого k ≥ 5. Решение Сана основывается на рекуррентном соотношении, подобном соотношению для последовательности Сильвестера, но с другим множеством начальных значений.

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

ЗадачаПравить

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

\text{[math]}

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

,

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

\text{[math]}

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

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

ИсторияПравить

Задача Знама названа по имени словацкого математика Стефана Знама, который предложил задачу в 1972. Барбо^[2] предложил несобственную задачу Знама для k = 3, а Морделл^[3], нашёл все решения несобственной задачи для k ≤ 5. Скула^[4] показал, что задача Знама не имеет решений для 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, но последний член этого множества равен произведению первых трёх членов плюс единица, так что этот член не является собственным делителем. Таким образом, это решение является решением несобственной задачи Знама, а не задачи Знама.

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

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

\text{[math]}

\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=y,

(Ф1)

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

\text{[math]}

X_{i}=\prod _{j\neq i}^{n}x_{j}

(Ф2)

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

\text{[math]}

N=\sum _{1}^{n}X_{i}+1

(Ф3)

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

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

\text{[math]}

\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=1.

(Ф4)

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

Число решенийПравить

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

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

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

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

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

ПримечанияПравить

ЛитератураПравить

G. E. J. Barbeau. Problem 179 // Canadian Mathematical Bulletin. — 1971. — Т. 14, вып. 1. — С. 129.
Lawrence Brenton, Richard Hill. On the Diophantine equation 1=Σ1/n_i + 1/Πn_i and a class of homologically trivial complex surface singularities // Pacific Journal of Mathematics. — 1988. — Т. 133, вып. 1. — С. 41–67. — doi:10.2140/pjm.1988.133.41. (недоступная ссылка)
Lawrence Brenton, Ana Vasiliu. Znám's problem // Mathematics Magazine. — 2002. — Т. 75, вып. 1. — С. 3–11. — doi:10.2307/3219178. — JSTOR 3219178.
William Butske, Lynda M. Jaje, Daniel R. Mayernik. On the equation $\text{[math]}$ $\text{[math]}$ $\scriptstyle \sum _{p|N}{\frac {1}{p}}+{\frac {1}{N}}=1$ , pseudoperfect numbers, and perfectly weighted graphs // Mathematics of Computation. — 2000. — Т. 69. — С. 407–420. — doi:10.1090/S0025-5718-99-01088-1..
Zhen Fu Cao, Cheng Ming Jing. On the number of solutions of Znám's problem // J. Harbin Inst. Tech.. — 1998. — Т. 30, вып. 1. — С. 46–49..
Zhen Fu Cao, Rui Liu, Liang Rui Zhang. On the equation $\text{[math]}$ $\text{[math]}$ $\scriptstyle \sum _{j=1}^{s}(1/x_{j})+(1/(x_{1}\cdots x_{s}))=1$ and Znám's problem // Journal of Number Theory. — 1987. — Т. 27, вып. 2. — С. 206–211. — doi:10.1016/0022-314X(87)90062-X.
Michael Domaratzki, Keith Ellul, Jeffrey Shallit, Ming-Wei Wang. Non-uniqueness and radius of cyclic unary NFAs // International Journal of Foundations of Computer Science. — 2005. — Т. 16, вып. 5. — С. 883–896. — doi:10.1142/S0129054105003352.
Jaroslav Janák, Ladislav Skula. On the integers $\text{[math]}$ $\text{[math]}$ $\scriptstyle x_{i}$ for which $\text{[math]}$ $\text{[math]}$ $\scriptstyle x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1$ // Math. Slovaca. — 1978. — Т. 28, вып. 3. — С. 305–310.
L. J. Mordell. Systems of congruences // Canadian Mathematical Bulletin. — 1973. — Т. 16. — С. 457–462. — doi:10.4153/CMB-1973-077-3.
Ladislav Skula. On a problem of Znám // Acta Fac. Rerum Natur. Univ. Comenian. Math.. — 1975. — Т. 32. — С. 87–90. На русском языке.

Qi Sun. On a problem of Š. Znám // Sichuan Daxue Xuebao. — 1983. — Вып. 4. — С. 9–12..
Qi Sun, Zhen Fu Cao. On the equation $\text{[math]}$ $\text{[math]}$ $\scriptstyle \sum _{j=1}^{s}1/x_{j}+1/x_{1}\cdots x_{s}=n$ and the number of solutions of Znám's problem // Northeastern Mathematics Journal. — 1988. — Т. 4, вып. 1. — С. 43–48.

СсылкиПравить

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

[_aba01f27b3877a68-1] Sun, 1983.

[_915b7b0fc092dc5f-2] Barbeau, 1971.

[_955bcf07740491ca-3] Mordell, 1973.

[_69fa3ead7c94504b-4] Skula, 1975.

[_29c4c6bf533c1daa-5] Brenton, Vasiliu, 2002, с. 6.

[_03a281426909a2ae-6] Brenton, Hill, 1988.

[_8173774677dd6e00-7] Domaratzki, Ellul, Shallit, Wang, 2005.

[_657893e4ae4c9930-8] Janák, Skula, 1978.

[_ab3cbce892a61bed-9] Cao, Jing, 1998.

[_b818f8c956623403-10] Cao, Liu, Zhang, 1987.

[_a30bd342ae860c70-11] ¹ ² Sun, Cao, 1988.

[_cfa0f070d899b58b-12] Butske, Jaje, Mayernik, 2000.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]