呢篇文係一篇好文。想知更多,請撳呢個掣。

Znám 問題

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

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,不過太細睇唔到。

數論入面,Znám 問題英文Znám's problem)係想問邊啲 k 個整數嘅組合符合呢個條件:每個整數都可以整除而且唔等於其他整數乘埋再加 1。Znám 問題係以斯洛伐克數學家 Štefan Znám 命名,佢喺1972年提出呢個問題,不過其實喺嗰段時間都有其他數學家諗緊類似嘅問題。其中一個相關嘅問題係,唔要求整數係真因數,淨係需要係因數就得,則係話容許某啲整數直情等於其他整數乘埋再加一,呢種問題喺呢篇文入邊會叫做仿 Znám 問題

對任何 k,仿 Znám 問題都有一個好簡單嘅解:喺 Sylvester 數列到攞佢頭 k 個數出嚟就得。Sun (1983) 證明對 ,Znám 問題都有最少一個解,佢嘅證明用咗同 Sylvester 數列好似嘅遞歸方法,不過個初始值就唔同。

Znám 問題同埃及分數有關。目前已知揀定一個 k 嘅話,Znám 問題只有有限個解。未知有無一啲淨係用單數嘅解,另外仲有幾個問題嘅答案都係未知嘅。

問題內容[編輯]

Znám 問題就係想問有邊啲整數組合,佢哋每一個都係「其他整數乘埋再加一」嘅真因數。亦即係話,固定一個 k,有邊啲整數集合,對於每一個標號 i,都整除但係唔等於

一個相關嘅問題係,喺上邊嘅要求入邊,唔再要求係真因數,只係要求係因數,即係話某個係可以等於。呢條問題喺文獻入邊似乎無正式嘅一個名,喺呢篇文入邊會叫做仿 Znám 問題。任何Znám 問題嘅解都係仿 Znám 問題嘅解,但係掉反轉就唔一定啱。

歷史[編輯]

Znám 問題係用斯洛伐克數學家 Štefan Znám 命名,佢喺1972年提出呢個問題,但係其實當年好多數學家都諗緊類似嘅問題,例如Barbeau (1971)就諗緊 k=3 情況嘅仿 Znám 問題,Mordell (1973)就獨立於Znám咁搵哂 k ≤ 5 仿 Znám 問題嘅解出嚟,Skula (1975)就證明咗 k<5 Znám 問題係無解嘅,並展示咗k = 5嗰陣,{2, 3, 11, 23, 31}呢一組係解,話係 J. Janák 搵嘅。

例子[編輯]

k = 5 嘅時候 {2, 3, 7, 47, 395} 係一個解,可以計一計:

3 × 7 × 47 × 395 + 1 = 389866,   被 2 整除
2 × 7 × 47 × 395 + 1 = 259911,   被 2 整除
2 × 3 × 47 × 395 + 1 = 111391,   被 7 整除
2 × 3 × 7 × 395 + 1 = 16591,   被 47 整除
2 × 3 × 7 × 47 + 1 = 1975,   被 395 整除

k = 4 嘅時候 {2, 3, 7, 43} 喺一個仿解,由 Sylvester 數列嘅頭四項組成。呢四個數每個都可以整除其他三個數乘埋再加一,但係最大嗰個(43)係等於其他三個(2、3、7)乘埋再加一,並唔係真因數,所以,呢組數係仿 Znám 問題嘅解,唔係原本 Znám 問題嘅解。

同埃及分數嘅關係[編輯]

任何仿 Znám 問題嘅解都可以除以轉換成嘅解,呢度同啲都要係整數;相反,呢啲解都可以整返啲仿 Znám 問題嘅解出嚟。喺現實上,所有已知嘅仿 Znám 問題解其實都符合

亦即係話,佢哋可以整到數字 1 嘅埃及分數表示出嚟。幾篇引文入邊都有研究呢一條等式,Brenton & Hill (1988)研究呢條等式喺拓樸學入邊嘅應用,可以幫曲面上面嘅奇異點分類,Domaratzki et al. (2005)就將佢應用喺非決定性有限狀態機上面。

解嘅數量[編輯]

Janák & Skula (1978)證明咗,揀定任何一個 k,解嘅數量都係有限嘅,所以去數每個 k 有幾多個解都係一個研究課題。

Brenton 同 Vasiliu 由 k=5 開始,對細嘅幾個 k 數咗有幾多個解:

2, 5, 18, 96OEIS中嘅數列A075441

現時嚟講,k=9 同 10 嘅情況有幾個解計咗出嚟,但係唔知道總共有幾多個解。如果唔固定 k 嘅話,總共係有無窮咁多個解:Cao & Jing (1998)證明咗如果 k ≥ 12 嘅話,就最少有 39 個解,改善咗之前嘅下界(Cao, Liu & Zhang 1987Sun & Cao 1988)。Sun & Cao (1988)推測解嘅數量會隨住 k 而單調上升。

現時未知存唔存在純單數嘅解。除咗有一組解第一個數係 3 之外,其他解第一個數都係 2。如果解入邊所有數都係質數嘅話,佢哋嘅積就係一個原偽完美數(primary pseudoperfect number)(Butske,Jaje & Mayernik 2000),目前亦都未知呢種解係咪有無限多組。

參考[編輯]

  • Barbeau, G. E. J. (1971), "Problem 179", Canadian Mathematical Bulletin, 14 (1): 129.
  • Brenton, Lawrence; Hill, Richard (1988), "On the Diophantine equation 1=Σ1/ni + 1/Πni and a class of homologically trivial complex surface singularities", Pacific Journal of Mathematics, 133 (1): 41–67, doi:10.2140/pjm.1988.133.41, MR 0936356.
  • Brenton, Lawrence; Vasiliu, Ana (2002), "Znám's problem", Mathematics Magazine, 75 (1): 3–11, doi:10.2307/3219178, JSTOR 3219178.
  • Butske, William; Jaje, Lynda M.; Mayernik, Daniel R. (2000), "On the equation , pseudoperfect numbers, and perfectly weighted graphs", Mathematics of Computation, 69: 407–420, doi:10.1090/S0025-5718-99-01088-1, MR 1648363.
  • Cao, Zhen Fu; Jing, Cheng Ming (1998), "On the number of solutions of Znám's problem", J. Harbin Inst. Tech., 30 (1): 46–49, MR 1651784.
  • Cao, Zhen Fu; Liu, Rui; Zhang, Liang Rui (1987), "On the equation and Znám's problem", Journal of Number Theory, 27 (2): 206–211, doi:10.1016/0022-314X(87)90062-X, MR 0909837.
  • Domaratzki, Michael; Ellul, Keith; Shallit, Jeffrey; Wang, Ming-Wei (2005), "Non-uniqueness and radius of cyclic unary NFAs", International Journal of Foundations of Computer Science, 16 (5): 883–896, doi:10.1142/S0129054105003352, MR 2174328.
  • Janák, Jaroslav; Skula, Ladislav (1978), "On the integers for which ", Math. Slovaca, 28 (3): 305–310, MR 0534998.
  • Mordell, L. J. (1973), "Systems of congruences", Canadian Mathematical Bulletin, 16 (3): 457–462, doi:10.4153/CMB-1973-077-3, MR 0332650.
  • Skula, Ladislav (1975), "On a problem of Znám", Acta Fac. Rerum Natur. Univ. Comenian. Math. (Russian, Slovak summary), 32: 87–90, MR 0539862.
  • Sun, Qi (1983), "On a problem of Š. Znám", Sichuan Daxue Xuebao (4): 9–12, MR 0750288.
  • Sun, Qi; Cao, Zhen Fu (1988), "On the equation and the number of solutions of Znám's problem", Northeastern Mathematics Journal, 4 (1): 43–48, MR 0970644.

連結[編輯]