Znamova výzva

V teorii čísel se problém Znam ptá, které množiny k celých čísel mají tu vlastnost, že každé celé číslo v množině je správným dělitelem součinu ostatních celých čísel v množině plus 1. Problém Znam je pojmenován po slovenském matematikovi Stefanu Znamovi , který navrhl problém v roce 1972, ačkoli jiní matematici se na podobné problémy dívali přibližně ve stejnou dobu. Související problém nevyžaduje, aby byl dělitel správným dělitelem, a nazývá se Znamův nesprávný problém.

Jedno řešení nesprávného problému lze snadno získat pro jakékoli k — prvních k členů Sylvesterovy posloupnosti má požadované vlastnosti. Sun [1] ukázal, že existuje alespoň jedno řešení (správné) úlohy Znam pro libovolné k ≥ 5. Sunovo řešení je založeno na rekurzivním vztahu podobném Sylvesterově posloupnosti, ale s jinou sadou počátečních hodnot.

Problém Znam úzce souvisí s egyptskými zlomky . Je známo, že pro každé pevné k existuje pouze konečný počet řešení . Není známo, zda existují řešení problému Znam pouze s lichými čísly. Existují také některé další otevřené problémy.

Výzva

Znamův problém se ptá, které množiny k celých čísel mají tu vlastnost, že každé celé číslo v množině je vlastním dělitelem součinu ostatních celých čísel v množině plus 1. To znamená , jaké množiny celých čísel existují při daném čísle k

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

takové, že pro libovolné i se číslo n i dělí, ale není rovno

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

Související problém se týká množiny celých čísel, která jsou děliteli součinu ostatních čísel plus jedna, ale tito dělitelé nemusí být vlastní. Nezdá se, že by tento problém získal v literatuře ustálené jméno, a budeme jej nazývat Znamův nevhodný problém. Jakékoli řešení problému Znam je také řešením nesprávného problému Znam, ale opak není vždy pravdou.

Historie

Problém Znam je pojmenován po slovenském matematikovi Stefanu Znamovi, který problém navrhl v roce 1972. Barbeau [2] navrhl nevlastní úlohu Znam pro k = 3 a Mordell [3] našel všechna řešení nevlastní úlohy pro k ≤ 5. Skula [4] ukázal, že problém Znam nemá řešení pro k < 5, a připisuje Yanakovi, že našel řešení {2, 3, 11, 23, 31} pro k = 5.

Příklady

Jedno z řešení pro k = 5 je {2, 3, 7, 47, 395}. Ukazují to jednoduché výpočty

3×7×47×395	+ 1 =	389866,	je dělitelné 2, ale nerovná se 2
2×7×47×395	+ 1 =	259911,	dělitelné 3, ale ne rovno 3
2×3×47×395	+ 1 =	111391,	je dělitelné 7, ale nerovná se 7
2×3×7×395	+ 1 =	16591,	dělitelné 47, ale ne rovno 47
2×3×7×47	+ 1 =	1975	je dělitelné 395, ale nerovná se 395.

Zajímavým "téměř řešením" pro k = 4 je množina {2, 3, 7, 43} tvořená prvními čtyřmi členy Sylvestrovy posloupnosti. Množina má tu vlastnost, že každé celé číslo v množině dělí součin ostatních členů množiny plus 1, ale poslední člen této množiny se rovná součinu prvních tří členů plus jedna, takže tento člen není správný dělitel. Toto řešení je tedy řešením nesprávného problému Znam, nikoli problému Znam.

Spojení s egyptskými zlomky

Jakékoli řešení nesprávného problému Znam je ekvivalentní řešení rovnice

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

(F1)

kde y , stejně jako jakékoli x i , musí být celé číslo. Chcete-li to ukázat, zvažte

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

(F2)

Všimněte si, že všechny musí být coprime (jinak společný dělitel a musí dělit a ). Položme $x_{i}$ $x_{i}$ $x_{j}$ $X_{i}$ $X_{i}+1$

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

(F3)

Ze stejných důvodů jako výše se jakékoli dělí , a protože jsou všechny coprime, dělitelné součinem . Nyní vydělíme obě části rovnice (F3) , dostaneme (F4) [5] $x_{i}$ $N$ $N$ ${\displaystyle \prod _{j\neq i}^{n}x_{j))$ ${\displaystyle \prod _{j\neq i}^{n}x_{j))$

Naopak všechna řešení rovnice (F1) odpovídají řešením nevlastní úlohy Znam. Pro všechna známá řešení však platí y = 1, takže rovnici splňují

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

(F4)

To vede k reprezentaci čísla jedna jako egyptského zlomku , součtu zlomků jedničky . Některé z citovaných prací o problému Znam také studují řešení této rovnice. Brenton a Hill [6] popisují aplikaci rovnice (F4) v topologii pro klasifikaci povrchových prvků a Domaracki et al [7] popisují aplikaci v teorii nedeterministických konečných automatů .

Počet řešení

Jak ukázali Janak a Skula [8] , počet řešení pro libovolné k je konečný, takže má smysl vypočítat celkový počet řešení pro každé k .

Brenton a Vassiliou po výpočtech zjistili, že počet řešení pro malé hodnoty k , počínaje k = 5, tvoří sekvenci

2 , 5 , 18 , 96 sekvence A075441 v OEIS .

V tuto chvíli je známo několik řešení pro k = 9 ak = 10, ale není známo, kolik řešení pro tyto hodnoty zůstalo nenalezeno. Pokud však k není pevné, existuje nekonečně mnoho řešení – Cao a Jing [9] ukázali, že pro každé k ≥ 12 existuje alespoň 39 řešení , což zlepšuje dřívější výsledek, který prokázal existenci méně řešení [10] [11] . Sun a Cao [11] navrhli, že počet řešení pro každé k roste monotónně s k .

Není známo, zda existuje nějaké řešení problému Znam pouze s lichými čísly. S jedinou výjimkou začínají všechna známá řešení 2 . Pokud jsou všechna čísla v řešení úlohy Znam nebo nevlastní úlohy Znam prvočísla , jejich součin je jednoduché pseudodokonalé číslo [12] . Není známo, zda existuje nekonečné množství řešení tohoto druhu.

Poznámky

↑ Slunce, 1983 .
↑ Barbeau, 1971 .
↑ Mordell, 1973 .
↑ Skula, 1975 .
↑ Brenton, Vasiliu, 2002 , str. 6.
↑ Brenton, Hill, 1988 .
↑ Domartzki, Ellul, Shallit, Wang, 2005 .
↑ Janák, Skula, 1978 .
↑ Cao, Jing, 1998 .
↑ Cao, Liu, Zhang, 1987 .
↑ 12 Sun , Cao, 1988 .
↑ Butske, Jaje, Mayernik, 2000 .

Literatura

GEJ Barbeau. Úloha 179 // Kanadský matematický bulletin . - 1971. - T. 14 , no. 1 . - S. 129 .
Lawrence Brenton, Richard Hill. K diofantické rovnici 1=Σ1/ n i + 1/Π n i a třídě homologicky triviálních komplexních povrchových singularit // Pacific Journal of Mathematics . - 1988. - T. 133 , čís. 1 . — s. 41–67 . - doi : 10.2140/pjm.1988.133.41 . (nedostupný odkaz)
Lawrence Brenton, Ana Vasiliu. Známův problém // Mathematics Magazine . - 2002. - T. 75 , no. 1 . — S. 3–11 . - doi : 10.2307/3219178 . — .
William Butske, Lynda M. Jaje, Daniel R. Mayernik. Na rovnici , pseudodokonalá čísla a dokonale vážené grafy // Matematika počítání . - 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. K počtu řešení Známova problému // J. Harbin Inst. Tech.. - 1998. - T. 30 , no. 1 . — s. 46–49 . .
Zhen Fu Cao, Rui Liu, Liang Rui Zhang. O rovnici a Známově problému // Journal of Number Theory . - 1987. - T. 27 , no. 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. Nejedinečnost a poloměr cyklických unárních NFA // International Journal of Foundations of Computer Science. - 2005. - T. 16 , no. 5 . — S. 883–896 . - doi : 10.1142/S0129054105003352 .
Jaroslav Janák, Ladislav Skula. Na celá čísla , pro která // Math. Slováca. - 1978. - T. 28 , no. 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. Systémy kongruencí // Canadian Mathematical Bulletin . - 1973. - T. 16 . — S. 457–462 . - doi : 10.4153/CMB-1973-077-3 .
Ladislav Skula. K problému Znám // Acta Fac. Rerum Natur. Univ. komický. Matematika.. - 1975. - T. 32 . — S. 87–90 . V Rusku.

Qi slunce. K problému Š. Znám // Sichuan Daxue Xuebao. - 1983. - Vydání. 4 . — S. 9–12 . .
Qi Sun, Zhen Fu Cao. O rovnici a počtu řešení Známova problému // Northeastern Mathematics Journal. - 1988. - V. 4 , čís. 1 . — s. 43–48 . $\scriptstyle \sum _{j=1}^{s}1/x_{j}+1/x_{1}\cdots x_{s}=n$

Odkazy

primefan. Řešení Znamova problému . (neurčitý)
Weisstein, Eric W. Znám's Problem (anglicky) na webu Wolfram MathWorld .