A Znam kihívása

A számelméletben a Znam-probléma azt kérdezi, hogy mely k egész számból álló halmazok rendelkeznek azzal a tulajdonsággal, hogy a halmazban lévő összes egész szám megfelelő osztója a halmaz többi egész számának plusz 1 szorzatának. A Znam-probléma Stefan Znam szlovák matematikusról kapta a nevét. , aki 1972-ben javasolta a problémát, bár más matematikusok is hasonló problémákkal foglalkoztak ugyanebben az időben. Egy kapcsolódó probléma nem követeli meg, hogy az osztó megfelelő osztó legyen, és ezt Znam helytelen problémájának nevezik.

A helytelen probléma egyik megoldása könnyen elérhető bármely k esetén – a Sylvester sorozat első k tagja rendelkezik a szükséges tulajdonságokkal. Sun [1] kimutatta, hogy minden k ≥ 5 esetén létezik legalább egy megoldás a (megfelelő) Znam problémára. A Sun megoldása a Sylvester sorozathoz hasonló rekurzív reláción alapul, de eltérő kezdeti értékekkel.

A Znam probléma szorosan összefügg az egyiptomi törtekkel . Ismeretes, hogy bármely rögzített k -re csak véges számú megoldás létezik . Nem tudni, hogy a Znam-problémára csak páratlan számokkal van-e megoldás. Vannak még nyitott kérdések is.

Kihívás

A Znam problémája azt kérdezi, hogy mely k egész számból álló halmazok rendelkeznek azzal a tulajdonsággal, hogy a halmazban lévő minden egész szám megfelelő osztója a halmaz többi egész számának plusz 1 szorzatának. Vagyis ha adott egy k szám , milyen egész számok halmazai léteznek

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

úgy, hogy bármely i -re az n i szám osztódik, de nem egyenlő vele

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

Egy ehhez kapcsolódó probléma az egész számok halmazával kapcsolatos, amelyek osztói a többi szám plusz egy szorzatának, de ezeknek az osztóknak nem kell megfelelőnek lenniük. Úgy tűnik, hogy ez a probléma nem kapott stabil nevet a szakirodalomban, és mi a Znam helytelen problémájának fogjuk nevezni. A Znam-probléma bármely megoldása egyben a nem megfelelő Znam-probléma megoldása is, de ennek fordítva nem mindig igaz.

Történelem

A Znam-probléma Stefan Znam szlovák matematikusról kapta a nevét, aki 1972-ben javasolta a problémát. Barbeau [2] a helytelen Znam-feladatot javasolta k = 3-ra, Mordell [3] pedig megtalálta a nem megfelelő probléma összes megoldását k ≤ 5-re. Skula [4] kimutatta, hogy a Znam-feladatnak nincs megoldása k < 5-re, és Yanaknak tulajdonítja, hogy megtalálta a {2, 3, 11, 23, 31} megoldást k = 5-re.

Példák

A k = 5 egyik megoldása {2, 3, 7, 47, 395}. Az egyszerű számítások ezt mutatják

3×7×47×395	+ 1 =	389866,	osztható 2-vel, de nem egyenlő 2-vel
2×7×47×395	+ 1 =	259911,	osztható 3-mal, de nem egyenlő 3-mal
2×3×47×395	+ 1 =	111391,	osztható 7-tel, de nem egyenlő 7-tel
2×3×7×395	+ 1 =	16591,	osztható 47-tel, de nem egyenlő 47-tel
2×3×7×47	+ 1 =	1975	osztható 395-tel, de nem egyenlő 395-tel.

Érdekes "majdnem megoldás" k = 4-re a Sylvester sorozat első négy tagja által alkotott {2, 3, 7, 43} halmaz. Egy halmaznak megvan az a tulajdonsága, hogy a halmaz minden egész szám osztja a halmaz többi tagjának szorzatát plusz 1-gyel, de ennek a halmaznak az utolsó tagja egyenlő az első három tag plusz egy szorzatával, tehát ez a tag nem megfelelő osztó. Így ez a megoldás a nem megfelelő Znam probléma megoldása, és nem a Znam probléma.

Kapcsolat az egyiptomi frakciókkal

A nem megfelelő Znam-probléma bármely megoldása egyenértékű az egyenlet megoldásával

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

(F1)

ahol y , mint bármely x i , egész szám kell, hogy legyen. Ennek bemutatásához fontolja meg

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

(F2)

Ne feledje, hogy mindegyiknek másodlagosnak kell lennie (egyébként a közös osztó , és osztania és ). Tegyük fel $x_{i}$ $x_{i}$ $x_{j}$ $X_{i}$ $X_{i}+1$

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

(F3)

Ugyanazok az okok miatt, mint fent, bármely osztószám , és mivel mindegyik másodprím, osztható a szorzattal . Most az (F3) egyenlet mindkét részét elosztjuk -vel , így megkapjuk (F4) [5] $x_{i}$ $N$ $N$ ${\displaystyle \prod _{j\neq i}^{n}x_{j))$ ${\displaystyle \prod _{j\neq i}^{n}x_{j))$

Ezzel szemben az (F1) egyenlet minden megoldása megfelel a nem megfelelő Znam-probléma megoldásainak. Azonban minden ismert megoldásra y = 1, tehát kielégítik az egyenletet

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

(F4)

Így ez az egyes szám egyiptomi törtként való ábrázolásához vezet, az egy törteinek összegeként . A Znam-problémával foglalkozó idézett cikkek némelyike ennek az egyenletnek a megoldásait is tanulmányozza. Brenton és Hill [6] az (F4) egyenlet topológiában történő alkalmazását írja le a felületi jellemzők osztályozására , Domaracki és munkatársai [7] pedig egy alkalmazást írnak le a nem-determinisztikus véges automaták elméletére .

Megoldások száma

Ahogy Janak és Skula [8] megmutatta , tetszőleges k megoldásainak száma véges, ezért érdemes kiszámolni az egyes k megoldások teljes számát .

Brenton és Vassiliou számításai után megállapították, hogy a megoldások száma kis k értékeihez, k = 5- től kezdve , sorozatot alkot

2 , 5 , 18 , 96 szekvencia A075441 az OEIS - ben .

Jelenleg több megoldás is ismert k = 9 és k = 10 értékre, de nem tudni, hogy ezekre az értékekre hány megoldás marad meg nem találva. Ha azonban k nincs rögzítve, akkor végtelenül sok megoldás létezik – Cao és Jing [9] kimutatta, hogy legalább 39 megoldás létezik minden k ≥ 12-re, ami javít egy korábbi eredményhez képest, amely kevesebb megoldás létezését bizonyította [10]. [11] . Sun és Cao [11] azt javasolta, hogy az egyes k megoldások száma monoton növekszik k -val .

Nem tudni, hogy van-e megoldás a Znam-problémára csak páratlan számokkal. Egy kivétellel minden ismert megoldás 2 -vel kezdődik . Ha a Znam-feladat megoldásában vagy a nem megfelelő Znam-feladat megoldásában minden szám prím , akkor a szorzatuk egy egyszerű pszeudoperfektus szám [12] . Nem ismert, hogy végtelen számú ilyen megoldás létezik-e.

Jegyzetek

↑ V, 1983 .
↑ Barbeau, 1971 .
↑ Mordell, 1973 .
↑ Skula, 1975 .
↑ Brenton, Vasiliu, 2002 , p. 6.
↑ Brenton, Hill, 1988 .
↑ Domaratzki, Ellul, Shallit, Wang, 2005 .
↑ Janak, Skula, 1978 .
↑ Cao, Jing, 1998 .
↑ Cao, Liu, Zhang, 1987 .
↑ Sun 12 , Cao, 1988 .
↑ Butske, Jaje, Mayernik, 2000 .

Irodalom

GEJ Barbeau. 179. feladat // Kanadai Matematikai Értesítő . - 1971. - T. 14 , sz. 1 . - S. 129 .
Lawrence Brenton, Richard Hill. Az 1=Σ1/ n i + 1/Π n i diofantusi egyenletről és a homológiailag triviális komplex felületi szingularitások osztályáról // Pacific Journal of Mathematics . - 1988. - T. 133 , sz. 1 . – 41–67 . - doi : 10.2140/pjm.1988.133.41 . (nem elérhető link)
Lawrence Brenton, Ana Vasiliu. Znám problémája // Matematikai Magazin . - 2002. - T. 75 , sz. 1 . — P. 3–11 . - doi : 10.2307/3219178 . — .
William Butske, Lynda M. Jaje, Daniel R. Mayernik. Az egyenletről , pszeudoperfektus számokról és tökéletesen súlyozott gráfokról // A számítás matematikája . - 2000. - T. 69 . – S. 407–420 . - doi : 10.1090/S0025-5718-99-01088-1 . $\scriptstyle \sum _{p|N}{\frac {1}{p}}+{\frac {1}{N}}=1$ .
Zhen Fu Cao, Cheng Ming Jing. A Znám-probléma megoldásainak számáról // J. Harbin Inst. Tech.. - 1998. - T. 30 , sz. 1 . – 46–49 . .
Zhen Fu Cao, Rui Liu, Liang Rui Zhang. Az egyenletről és a Znám-problémáról // Journal of Number Theory . - 1987. - T. 27 , sz. 2 . – S. 206–211 . - doi : 10.1016/0022-314X(87)90062-X . $\scriptstyle \sum _{j=1}^{s}(1/x_{j})+(1/(x_{1}\cdots x_{s}))=1$
Michael Domaratzki, Keith Ellul, Jeffrey Shallit, Ming-Wei Wang. Ciklikus unáris NFA-k nem egyedisége és sugara // International Journal of Foundations of Computer Science. - 2005. - T. 16 , sz. 5 . – S. 883–896 . - doi : 10.1142/S0129054105003352 .
Jaroslav Janak, Ladislav Skula. Azokon az egész számokon , amelyekre // Math. Szlovákia. - 1978. - T. 28 , sz. 3 . – S. 305–310 . ${\displaystyle \scriptstyle x_{i))$ $\scriptstyle x_{i}|x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{n}+1$
LJ Mordell. Egybevágósági rendszerek // Canadian Mathematical Bulletin . - 1973. - T. 16 . – S. 457–462 . - doi : 10.4153/CMB-1973-077-3 .
Ladislav Skula. Znám problémájáról // Acta Fac. Rerum Natur. Univ. komikus. Matek.. - 1975. - T. 32 . – S. 87–90 . Oroszul.

Qi nap. Š. problémájáról. Znám // Sichuan Daxue Xuebao. - 1983. - Kiadás. 4 . — P. 9–12 . .
Qi Sun, Zhen Fu Cao. A Znám-feladat egyenletéről és megoldásainak számáról // Northeastern Mathematics Journal. - 1988. - V. 4 , sz. 1 . – 43–48 . $\scriptstyle \sum _{j=1}^{s}1/x_{j}+1/x_{1}\cdots x_{s}=n$

Linkek

primefan. Megoldások Znam problémájára . (határozatlan)
Weisstein, Eric W. Znám's Problem (angol) a Wolfram MathWorld weboldalán .