Problema Znám

Demonstrație grafică că 1 = 1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1 / (2 × 3 × 11 × 23 × 31). Fiecare rând, compus cu k pătrate de latură 1 / k, are suprafața totală 1 / k și toate împreună acoperă exact un pătrat de suprafață 1. Ultimul rând are 47058 pătrate de latură 1/47058 și, prin urmare, prea mic pentru a fi observat în cifra.

În teoria numerelor , problema Znám întreabă ce seturi de $k$ ${\ displaystyle k}$ $k$ numerele întregi au proprietatea că fiecare element din set este un divizor propriu al produsului celorlalte numere, plus 1. Denumirea problemei provine de la matematicianul slovac Štefan Znám, care a sugerat-o în 1972, deși alți matematicieni au considerat similar probleme în aceeași perioadă. O problemă asociată renunță la ipoteza divizibilității corecte și va fi numită ulterior problema necorespunzătoare a lui Znám.

O soluție la problema Znám necorespunzătoare este ușor de construit luând prima $k$ ${\ displaystyle k}$ $k$ termenii succesiunii Sylvester . Sun (1983) a arătat că există cel puțin o soluție a problemei (proprii) pentru fiecare $k\geq 5$ ${\ displaystyle k \ geq 5}$ ${\ displaystyle k \ geq 5}$ . Soluția lui Sun se bazează pe o relație de recurență similară cu cea a secvenței Sylvester, dar cu o alegere diferită a valorilor inițiale.

Problema Znám este strâns legată de fracțiile egiptene . Se știe că există doar un număr finit de soluții pentru fiecare $k$ ${\ displaystyle k}$ $k$ remediat, dar rămâne necunoscut dacă există soluții la problema Znám cu numere impare, împreună cu multe alte întrebări deschise.

Problema

Problema lui Znám întreabă ce seturi de numere întregi au proprietatea că fiecare element din mulțime este un divizor propriu al produsului celorlalte numere, plus 1. Adică fix $k$ ${\ displaystyle k}$ $k$ , cum ar fi seturi de numere întregi

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

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

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

există astfel încât, pentru fiecare $the$ ${\ displaystyle i}$ $the$ , $n_{i}$ ${\ displaystyle n_ {i}}$ $n_i$ împarte dar nu este egal cu

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

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

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

O problemă strâns legată se referă la seturi de numere întregi în care fiecare element este un divizor, nu neapărat propriu, al produsului celorlalte numere întregi plus 1. Această problemă nu pare să aibă un nume în literatură și va fi menționată aici ca o problemă necorespunzătoare Znám. Fiecare soluție a problemei Znám este, de asemenea, o soluție a versiunii necorespunzătoare, dar inversul nu este neapărat adevărat.

Istorie

Problema Znám își datorează numele matematicianului slovac Štefan Znám, care a sugerat-o în 1972. Barbeau (1971) a pus problema Znám pentru $k=3$ ${\ displaystyle k = 3}$ ${\ displaystyle k = 3}$ , și Mordell (1973) , independent de Znám, au găsit toate soluțiile problemei necorespunzătoare $k\leq 5$ ${\ displaystyle k \ leq 5}$ ${\ displaystyle k \ leq 5}$ . Skula (1975) a arătat că problema lui Znám nu are soluție $k<5$ ${\ displaystyle k <5}$ ${\ displaystyle k <5}$ , și a atribuit lui J. Janák descoperirea soluției {2, 3, 11, 23, 31} pentru $k=5$ ${\ displaystyle k = 5}$ ${\ displaystyle k = 5}$ .

Exemple

O soluție la caz $k=5$ ${\ displaystyle k = 5}$ ${\ displaystyle k = 5}$ este {2, 3, 7, 47, 395}. Unele calcule arată că

3 × 7 × 47 × 395	+ 1 =	389866,	care este divizibil, dar nu egal cu 2,
2 × 7 × 47 × 395	+ 1 =	259911,	care este divizibil, dar nu egal cu 2,
2 × 3 × 47 × 395	+ 1 =	111391,	care este divizibil, dar nu egal cu 2,
2 × 3 × 7 × 395	+ 1 =	16591,	care este divizibil, dar nu egal cu 2 și
2 × 3 × 7 × 47	+ 1 =	1975,	care este divizibil dar nu egal cu 2.

O soluție interesantă „eșuată” pentru $k=4$ ${\ displaystyle k = 4}$ ${\ displaystyle k = 4}$ este mulțimea {2, 3, 7, 43}, formată din primii patru termeni ai secvenței Sylvester. Are proprietatea că fiecare număr întreg împarte produsul celorlalte elemente în set plus 1, dar ultimul număr este egal cu produsul plus unu, în loc să fie propriul său divizor. În consecință, este o soluție a problemei Znám necorespunzătoare, dar nu a celei originale.

Legătura cu satele egiptene

Orice soluție la problema Znám necorespunzătoare este echivalentă (printr-o împărțire după produsul $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ ) pentru a rezolva ecuația

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

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

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

unde este $y$ ${\ displaystyle y}$ $y$ Și $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ trebuie să fie numere întregi. Cu toate acestea, toate soluțiile cunoscute au $y=1$ ${\ displaystyle y = 1}$ $y = 1$ , deci satisfac ecuația

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

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

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

Cu alte cuvinte, ele conduc la o reprezentare a fracției egiptene a numărului 1, adică ca sume de fracții unitare. Multe dintre articolele citate despre problema Znám studiază și soluțiile acestei ecuații. Brenton & Hill (1988) descrie o aplicație a ecuației în topologie , în clasificarea singularităților pe suprafețe și Domaratzki și colab. (2005) expune aplicarea teoriei automatului de stare finită nedeterminist .

Numărul de soluții

După cum au arătat Janák și Skula (1978) , numărul de soluții pentru $k$ ${\ displaystyle k}$ $k$ fix este k finit, deci pentru fiecare $k$ ${\ displaystyle k}$ $k$ are sens să numărăm soluțiile.

Brenton și Vasiliu au calculat că numărul de soluții pentru valori mici de $k$ ${\ displaystyle k}$ $k$ , începând de la $k=5$ ${\ displaystyle k = 5}$ ${\ displaystyle k = 5}$ , formează secvența

2 , 5 , 18 , 96 (secvența A075441 în OEIS ).

În prezent, sunt cunoscute câteva soluții pentru caz $k=9$ ${\ displaystyle k = 9}$ ${\ displaystyle k = 9}$ Și $k=10$ ${\ displaystyle k = 10}$ ${\ displaystyle k = 10}$ , dar este încă incert cât de multe soluții rămân de descoperit pentru aceste valori ale $k$ ${\ displaystyle k}$ $k$ . Cu toate acestea, există soluții infinite dacă $k$ ${\ displaystyle k}$ $k$ nu este fix: Cao și Jing (1998) au arătat că există cel puțin 39 de soluții pentru fiecare $k\geq 12$ ${\ displaystyle k \ geq 12}$ ${\ displaystyle k \ geq 12}$ , îmbunătățind rezultatele anterioare ale ( Cao, Liu și Zhang (1987) și Sun & Cao (1988) ). Sun & Cao (1988) au conjecturat că numărul de soluții pentru fiecare valoare a $k$ ${\ displaystyle k}$ $k$ a crescut monoton cu $k$ ${\ displaystyle k}$ $k$ .

Rămâne necunoscut dacă există soluții la problema lui Znám constând doar din numere impare. Cu o singură excepție, toate soluțiile încep cu numărul 2. Dacă toate elementele unei soluții a problemei Znám (adecvate sau necorespunzătoare) sunt numere prime , produsul lor este un număr primar pseudoperfect ( Butske, Jaje & Mayernik (2000) ); nu se știe dacă există infinite soluții de acest tip.

Bibliografie

GEJ Barbeau, Problema 179 , în Canadian Mathematical Bulletin , vol. 14, n. 1, 1971, p. 129.
Lawrence Brenton și Richard Hill, Despre ecuația diofantină 1 = Σ1 / n _i + 1 / Π n _i și o clasă de singularități de suprafață complexe triviale omologic , în Pacific Journal of Mathematics , vol. 133, nr. 1, 1988, pp. 41–67, DOI : 10.2140 / pjm.1988.133.41 , MR 0936356 .
Lawrence Brenton și Ana Vasiliu, problema lui Znám , în Revista de matematică , vol. 75, nr. 1, 2002, pp. 3-11, DOI : 10.2307 / 3219178 , JSTOR 3219178 .
William Butske, Lynda M. Jaje și Daniel R. Mayernik, Despre ecuație $\scriptstyle \sum _{p|N}{\frac {1}{p}}+{\frac {1}{N}}=1$ ${\ displaystyle \ scriptstyle \ sum _ {p | N} {\ frac {1} {p}} + {\ frac {1} {N}} = 1}$ ${\ displaystyle \ scriptstyle \ sum _ {p | N} {\ frac {1} {p}} + {\ frac {1} {N}} = 1}$ , numere pseudoperfecte și grafice perfect ponderate , în Matematica calculelor , vol. 69, 2000, pp. 407–420, DOI : 10.1090 / S0025-5718-99-01088-1 , MR 1648363 .
Zhen Fu Cao și Cheng Ming Jing, Despre numărul de soluții ale problemei lui Znám , în J. Harbin Inst. Tehnologie. , vol. 30, n. 1, 1998, pp. 46-49, MR 1651784 .
Zhen Fu Cao, Rui Liu și Liang Rui Zhang, În ecuație $\scriptstyle \sum _{j=1}^{s}(1/x_{j})+(1/(x_{1}\cdots x_{s}))=1$ ${\ displaystyle \ scriptstyle \ sum _ {j = 1} ^ {s} (1 / x_ {j}) + (1 / (x_ {1} \ cdots x_ {s})) = 1}$ ${\ displaystyle \ scriptstyle \ sum _ {j = 1} ^ {s} (1 / x_ {j}) + (1 / (x_ {1} \ cdots x_ {s})) = 1}$ și problema lui Znám , în Journal of Number Theory , vol. 27, n. 2, 1987, pp. 206-211, DOI : 10.1016 / 0022-314X (87) 90062-X , MR 0909837 .
Michael Domaratzki, Keith Ellul, Jeffrey Shallit și Ming-Wei Wang, Non-unicitate și raza NFA-urilor ciclice unare ( ps ), în International Journal of Foundations of Computer Science , vol. 16, nr. 5, 2005, pp. 883–896, DOI : 10.1142 / S0129054105003352 , MR 2174328 .
Jaroslav Janák și Ladislav Skula, Despre numerele întregi $\scriptstyle x_{i}$ ${\ displaystyle \ scriptstyle x_ {i}}$ ${\ displaystyle \ scriptstyle x_ {i}}$ pentru care $\scriptstyle x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1$ ${\ displaystyle \ scriptstyle x_ {i} | x_ {1} \ cdots x_ {i-1} x_ {i + 1} \ cdots x_ {n} +1}$ ${\ displaystyle \ scriptstyle x_ {i} | x_ {1} \ cdots x_ {i-1} x_ {i + 1} \ cdots x_ {n} +1}$ , în matematică. Slovaca , vol. 28, nr. 3, 1978, pp. 305-310, MR 0534998 .
LJ Mordell, Systems of congruences , în Canadian Mathematical Bulletin , vol. 16, 1973, pp. 457–462, DOI : 10.4153 / CMB-1973-077-3 , MR 0332650 .
Ladislav Skula, Despre o problemă a lui Znám , în Acta Fac. Rerum Natur. Universitatea Comeniană. Matematica. , vol. 32, 1975, pp. 87–90, MR 0539862 .
Qi Sun, despre o problemă a lui Š. Znám , în Sichuan Daxue Xuebao , nr. 4, 1983, pp. 9-12, MR 0750288 .
Qi Sun și Zhen Fu Cao, despre ecuație $\scriptstyle \sum _{j=1}^{s}1/x_{j}+1/x_{1}\cdots x_{s}=n$ ${\ displaystyle \ scriptstyle \ sum _ {j = 1} ^ {s} 1 / x_ {j} + 1 / x_ {1} \ cdots x_ {s} = n}$ ${\ displaystyle \ scriptstyle \ sum _ {j = 1} ^ {s} 1 / x_ {j} + 1 / x_ {1} \ cdots x_ {s} = n}$ și numărul de soluții ale problemei lui Znám , în Northeastern Mathematics Journal , vol. 4, nr. 1, 1988, pp. 43–48, MR 0970644 .