Editing Znám's problem

{{Short description|On divisibility among sets of integers}}
[[Image:Znam-2-3-11-23-31.svg|thumb|301px|Graphical demonstration that 1 = 1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1/(2×3×11×23×31). Each row of {{mvar|k}} squares of side length&thinsp;1/{{mvar|k}} has total [[area]]&thinsp;1/{{mvar|k}}, and all the squares together exactly cover a larger square with area 1. The bottom row of 47058 squares with side length 1/47058 is too small to see in the figure and is not shown.]]
In [[number theory]], '''Znám's problem''' asks which [[set (mathematics)|sets]] of [[integer]]s have the property that each integer in the set is a [[proper divisor]] of the product of the other integers in the set, plus 1. Znám's problem is named after the Slovak mathematician [[Štefan Znám]], who suggested it in 1972, although other mathematicians had considered similar problems around the same time.

The initial terms of [[Sylvester's sequence]] almost solve this problem, except that the last chosen term equals one plus the product of the others, rather than being a proper divisor. {{harvtxt|Sun|1983}} showed that there is at least one solution to the (proper) Znám problem for each <math>k\ge 5</math>. Sun's solution is based on a [[recurrence relation|recurrence]] similar to that for Sylvester's sequence, but with a different set of initial values.

The Znám problem is closely related to [[Egyptian fraction]]s. It is known that there are only finitely many solutions for any fixed <math>k</math>. It is unknown whether there are any solutions to Znám's problem using only [[odd number]]s, and there remain several other [[open problem|open questions]].

==The problem==
Znám's problem asks which sets of integers have the property that each integer in the set is a [[proper divisor]] of the product of the other integers in the set, plus 1. That is, given <math>k</math>, what sets of integers 
<math display=block>\{n_1, \ldots, n_k\}</math>
are there such that, for each <math>i</math>, <math>n_i</math> divides but is not equal to
<math display=block>\Bigl(\prod_{j \ne i}^n n_j\Bigr) + 1 ?</math>
A closely related problem concerns sets of integers in which each integer in the set is a divisor, but not necessarily a proper divisor, of one plus the product of the other integers in the set. This problem does not seem to have been named in the literature, and will be referred to as the improper Znám problem. Any solution to Znám's problem is also a solution to the improper Znám problem, but not necessarily vice versa.

== History ==
Znám's problem is named after the Slovak mathematician [[Štefan Znám]], who suggested it in 1972. {{harvtxt|Barbeau|1971}} had posed the improper Znám problem for <math>k=3</math>, and {{harvtxt|Mordell|1973}}, independently of Znám, found all solutions to the improper problem for <math>k\le 5</math>. {{harvtxt|Skula|1975}} showed that Znám's problem is unsolvable for <math>k<5</math>, and credited J. Janák with finding the solution <math>\{2, 3, 11, 23, 31\}</math> for <math>k=5</math>.<ref>{{harvnb|Barbeau|1971}}; {{harvnb|Mordell|1973}}; {{harvnb|Skula|1975}}</ref>

== Examples ==
[[Sylvester's sequence]] is an [[integer sequence]] in which each term is one plus the product of the previous terms. The first few terms of the [[sequence]] are
{{bi|left=1.6|2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 {{OEIS|id=A000058}}.}}
Stopping the sequence early produces a set like <math>\{2, 3, 7, 43\}</math> that almost meets the conditions of Znám's problem, except that the largest value equals one plus the product of the other terms, rather than being a proper divisor.{{sfn|Brenton|Hill|1988}} Thus, it is a solution to the improper Znám problem, but not a solution to Znám's problem as it is usually defined.

One solution to the proper Znám problem, for <math>k=5</math>, is <math>\{2, 3, 7, 47, 395\}</math>. A few calculations will show that

{| style="margin-left:1.6em"
|align="right" | 3 × 7 × 47 × 395 || + 1 = || 389866, || &nbsp; || which is divisible by but unequal to 2,
|-
|align="right" | 2 × 7 × 47 × 395 || + 1 = || 259911, || &nbsp; || which is divisible by but unequal to 3,
|-
|align="right" | 2 × 3 × 47 × 395 || + 1 = || 111391, || &nbsp; || which is divisible by but unequal to 7,
|-
|align="right" | 2 × 3 × 7 × 395 || + 1 = || 16591, || &nbsp; || which is divisible by but unequal to 47, and
|-
|align="right" | 2 × 3 × 7 × 47 || + 1 = || 1975, || &nbsp; || which is divisible by but unequal to 395.
|}

== Connection to Egyptian fractions ==
Any solution to the improper Znám problem is equivalent (via division by the product of the values <math>x_i</math>) to a solution to the equation
<math display=block>\sum\frac1{x_i} + \prod\frac1{x_i}=y,</math>
where <math>y</math> as well as each <math>x_i</math> must be an integer, and [[converse (logic)|conversely]] any such solution corresponds to a solution to the improper Znám problem. However, all known solutions have <math>y=1</math>, so they satisfy the equation
<math display=block>\sum\frac1{x_i} + \prod\frac1{x_i}=1.</math>
That is, they lead to an [[Egyptian fraction]] representation of the number one as a sum of [[unit fraction]]s. Several of the cited papers on Znám's problem study also the solutions to this equation. {{harvtxt|Brenton|Hill|1988}} describe an application of the equation in [[topology]], to the classification of [[singularity (mathematics)|singularities]] on surfaces,{{sfn|Brenton|Hill|1988}} and {{harvtxt|Domaratzki|Ellul|Shallit|Wang|2005}} describe an application to the theory of [[nondeterministic finite automata]].{{sfn|Domaratzki|Ellul|Shallit|Wang|2005}}

== Number of solutions ==
The number of solutions to Znám's problem for any <math>k</math> is finite, so it makes sense to count the total number of solutions for each <math>k</math>.{{sfn|Janák|Skula|1978}} {{harvtxt|Sun|1983}} showed that there is at least one solution to the (proper) Znám problem for each <math>k\ge 5</math>. Sun's solution is based on a recurrence similar to that for Sylvester's sequence, but with a different set of initial values.{{sfn|Sun|1983}} The number of solutions for small values of <math>k</math>, starting with <math>k=5</math>, forms the sequence{{sfn|Brenton|Vasiliu|2002}}
:[[2 (number)|2]],&nbsp;[[5 (number)|5]],&thinsp;[[18 (number)|18]],&nbsp;[[96 (number)|96]] {{OEIS|id=A075441}}.
Presently, a few solutions are known for <math>k=9</math> and <math>k=10</math>, but it is unclear how many solutions remain undiscovered for those values of <math>k</math>.
However, there are infinitely many solutions if <math>k</math> is not fixed:
{{harvtxt|Cao|Jing|1998}} showed that there are at least 39 solutions for each <math>k\ge 12</math>, improving earlier results proving the existence of fewer solutions;<ref>{{harvnb|Cao|Liu|Zhang|1987}} {{harvnb|Sun|Cao|1988}}</ref> {{harvtxt|Sun|Cao|1988}} [[conjecture]] that the number of solutions for each value of <math>k</math> grows [[Sequence#Increasing and decreasing|monotonically]] with <math>k</math>.{{sfn|Sun|Cao|1988}} 

It is unknown whether there are any solutions to Znám's problem using only odd numbers. With one exception, all known solutions start with 2. If all numbers in a solution to Znám's problem or the improper Znám problem are [[prime number|prime]], their product is a [[primary pseudoperfect number]];{{sfn|Butske|Jaje|Mayernik|2000}} it is unknown whether infinitely many solutions of this type exist.

== See also ==
* [[Giuga number]]
* [[Primary pseudoperfect number]]

== References ==
===Notes===
{{reflist|colwidth=30em}}

===Sources===
{{refbegin|colwidth=30em}}
* {{citation
  | last = Barbeau | first = G. E. J.
  | title = Problem 179
  | journal = [[Canadian Mathematical Bulletin]]
  | volume = 14
  | year = 1971
  | issue = 1
  | pages = 129}}.
* {{citation
  | last1 = Brenton| first1 = Lawrence
  | last2 = Hill | first2 = Richard
  | title = On the Diophantine equation <math display=inline>1=\sum 1/n_i+1/\prod n_i</math> and a class of homologically trivial complex surface singularities
  | journal = [[Pacific Journal of Mathematics]]
  | volume = 133
  | issue = 1
  | year = 1988
  | pages = 41–67
  | mr = 0936356
  | doi=10.2140/pjm.1988.133.41| doi-access = free
  | url = https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-133/issue-1/On-the-Diophantine-equation-1sum-1-n_i1-prod-n_i-and/pjm/1102689567.full
  }}.
* {{citation
  | doi = 10.2307/3219178
  | last1 = Brenton| first1 = Lawrence
  | last2 = Vasiliu| first2 = Ana
  | title = Znám's problem
  | journal = [[Mathematics Magazine]]
  | volume = 75
  | issue = 1
  | pages = 3–11
  | year = 2002
  | jstor = 3219178}}.
* {{citation
  | last1 = Butske| first1 = William
  | last2= Jaje|first2= Lynda M.
  | last3 = Mayernik| first3 = Daniel R.
  | title = On the equation <math display=inline>\sum_{p|N}\frac{1}{p}+\frac{1}{N}=1</math>, pseudoperfect numbers, and perfectly weighted graphs
  | journal = [[Mathematics of Computation]]
  | volume = 69
  | year = 2000
  | pages = 407–420
  | url = http://www.ams.org/mcom/2000-69-229/S0025-5718-99-01088-1/home.html
  | mr = 1648363 | doi=10.1090/S0025-5718-99-01088-1| doi-access = free
  }}.
* {{citation
  | last1 = Cao |first1= Zhen Fu
  | last2 = Jing| first2= Cheng Ming
  | title = On the number of solutions of Znám's problem
  | journal = J. Harbin Inst. Tech.
  | volume = 30
  | year = 1998
  | issue = 1
  | pages = 46–49
  | mr = 1651784}}.
* {{citation
  | last1 = Cao| first1 = Zhen Fu
  | last2 = Liu| first2 = Rui
  | last3 = Zhang| first3= Liang Rui
  | title = On the equation <math display=inline>\sum^s_{j=1}(1/x_j)+(1/(x_1\cdots x_s))=1</math> and Znám's problem
  | journal = [[Journal of Number Theory]]
  | volume = 27
  | year = 1987
  | issue = 2
  | pages = 206–211
  | mr = 0909837
  | doi = 10.1016/0022-314X(87)90062-X| doi-access = 
  }}.
* {{citation
  | last1 = Domaratzki| first1 = Michael
  | last2 = Ellul | first2 = Keith
  | last3 = Shallit| first3 = Jeffrey | author2-link = Jeffrey Shallit
  | last4 = Wang| first4 = Ming-Wei
  | title = Non-uniqueness and radius of cyclic unary NFAs
  | journal = International Journal of Foundations of Computer Science
  | volume = 16
  | issue = 5
  | pages = 883–896
  | year = 2005
  | url = http://www.cs.umanitoba.ca/~mdomarat/pubs/DESW_dcfs.ps
  | mr = 2174328
  | doi = 10.1142/S0129054105003352}}.
* {{citation
  | last1 = Janák| first1 = Jaroslav
  | last2= Skula| first2= Ladislav | authorlink2 = Ladislav Skula
  | title = On the integers <math display=inline> x_{i}</math> for which <math display=inline> x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1</math>
  | journal = Math. Slovaca
  | volume = 28
  | year = 1978
  | issue = 3
  | pages = 305–310
  | mr = 0534998}}.
* {{citation
  | last = Mordell| first = L. J. | author-link = Louis J. Mordell
  | title = Systems of congruences
  | journal = [[Canadian Mathematical Bulletin]]
  | volume = 16
  | year = 1973
  | issue = 3 | pages = 457–462
  | mr = 0332650
  | doi = 10.4153/CMB-1973-077-3 | doi-access=free}}.
* {{citation
  | last = Skula| first= Ladislav | author-link = Ladislav Skula
  | title = On a problem of Znám
  | type = Russian, Slovak summary
  | journal = Acta Fac. Rerum Natur. Univ. Comenian. Math.
  | volume = 32
  | year = 1975
  | pages = 87–90
  | mr = 0539862}}.
* {{citation
  | last = Sun| first= Qi
  | title = On a problem of Š. Znám
  | journal = Sichuan Daxue Xuebao
  | year = 1983
  | issue = 4
  | pages = 9–12
  | mr = 0750288}}.
* {{citation
  | last1 = Sun| first1 = Qi
  | last2= Cao| first2 = Zhen Fu
  | title = On the equation <math display=inline>\sum^s_{j=1}1/x_j+1/x_1\cdots x_s=n</math> and the number of solutions of Znám's problem
  | journal = Northeastern Mathematics Journal
  | volume = 4
  | year = 1988
  | issue = 1
  | pages = 43–48
  | mr = 0970644}}.
{{refend}}

== External links ==

* {{citation
  | author = Primefan
  | url = http://primefan.tripod.com/ZnamProbSols.html
  | title = Solutions to Znám's Problem}}
* {{mathworld | title = Znám's Problem | urlname = ZnamsProblem|mode=cs2}}

<!-- future interwiki links:
sk:Známovo problem
sl:Známovo problem -->

{{good article}}

{{DEFAULTSORT:Znam's Problem}}
[[Category:Number theory]]
[[Category:Integer sequences]]
[[Category:Egyptian fractions]]
[[Category:Mathematical problems]]