Znamin haaste

Lukuteoriassa Znam -tehtävä kysyy, millä k kokonaisluvun joukolla on ominaisuus, että jokainen joukon kokonaisluku on oikea jakaja joukon muiden kokonaislukujen tulolle plus 1. Znam-tehtävä on nimetty slovakialaisen matemaatikon Stefan Znamin mukaan. , joka ehdotti ongelmaa vuonna 1972, vaikka muut matemaatikot tarkastelivat samanlaisia ​​ongelmia suunnilleen samaan aikaan. Liittyvä ongelma ei vaadi jakajan olevan oikea jakaja, ja sitä kutsutaan Znamin virheelliseksi ongelmaksi.

Yksi ratkaisu väärään ongelmaan on helppo saada mille tahansa k :lle — Sylvester-sekvenssin ensimmäisellä k termillä on vaaditut ominaisuudet. Sun [1] osoitti, että (oikealle) Znam-tehtävälle on olemassa ainakin yksi ratkaisu millä tahansa k ≥ 5:llä. Sunin ratkaisu perustuu rekursiiviseen relaatioon, joka on samanlainen kuin Sylvester-sekvenssi, mutta jolla on eri alkuarvot.

Znam-ongelma liittyy läheisesti egyptiläisiin jakeisiin . Tiedetään, että mille tahansa kiinteälle k :lle on vain äärellinen määrä ratkaisuja . Ei tiedetä, onko Znam-ongelmaan ratkaisuja vain parittomilla luvuilla. On myös muita avoimia kysymyksiä.

Haaste

Znamin tehtävä kysyy, millä k kokonaisluvun joukolla on ominaisuus, että jokainen joukon kokonaisluku on oikea jakaja joukon muiden kokonaislukujen tulolle plus 1. Toisin sanoen mitä kokonaislukujoukkoja on olemassa , kun annetaan luku k .

,

siten, että minkä tahansa i :n luku n i jakaa, mutta ei ole yhtä suuri

Tähän liittyvä ongelma koskee kokonaislukujen joukkoa, jotka ovat muiden lukujen plus yhden tulon jakajia, mutta näiden jakajien ei tarvitse olla oikeita. Tämä ongelma ei näytä saaneen pysyvää nimeä kirjallisuudessa, ja kutsumme sitä Znamin epäasianmukaiseksi ongelmaksi. Mikä tahansa ratkaisu Znam-ongelmaan on myös ratkaisu väärään Znam-ongelmaan, mutta päinvastoin ei aina ole totta.

Historia

Znam-tehtävä on nimetty slovakialaisen matemaatikon Stefan Znamin mukaan, joka ehdotti ongelmaa vuonna 1972. Barbeau [2] ehdotti väärää Znam-tehtävää arvolle k = 3, ja Mordell [3] löysi kaikki väärän ongelman ratkaisut arvolle k ≤ 5. Skula [4] osoitti, että Znam-tehtävässä ei ole ratkaisuja arvolle k < 5, ja antaa Yanakille ratkaisun {2, 3, 11, 23, 31} k = 5:lle.

Esimerkkejä

Yksi k = 5:n ratkaisuista on {2, 3, 7, 47, 395}. Yksinkertaiset laskelmat osoittavat sen

3×7×47×395 + 1 = 389866,   on jaollinen kahdella, mutta ei ole yhtä suuri kuin 2
2×7×47×395 + 1 = 259911,   jaollinen kolmella, mutta ei yhtä suuri kuin 3
2×3×47×395 + 1 = 111391,   on jaollinen 7:llä, mutta ei ole yhtä suuri kuin 7
2×3×7×395 + 1 = 16591,   jaollinen luvulla 47, mutta ei yhtä suuri kuin 47
2×3×7×47 + 1 = 1975   on jaollinen luvulla 395, mutta ei ole yhtä suuri kuin 395.

Mielenkiintoinen "melkein ratkaisu" arvolle k = 4 on Sylvester-sekvenssin neljän ensimmäisen jäsenen muodostama joukko {2, 3, 7, 43}. Joukolla on ominaisuus, että jokainen joukon kokonaisluku jakaa joukon muiden jäsenten tulon plus 1, mutta joukon viimeinen jäsen on yhtä suuri kuin kolmen ensimmäisen jäsenen plus yksi tulo, joten kyseinen jäsen ei ole oikea jakaja. Siten tämä ratkaisu on ratkaisu väärään Znam-ongelmaan, ei Znam-ongelmaan.

Yhteys egyptiläisiin fraktioihin

Mikä tahansa ratkaisu väärään Znam-ongelmaan vastaa yhtälön ratkaisemista

(F1)

missä y :n , kuten minkä tahansa x i :n, on oltava kokonaisluku. Jos haluat näyttää tämän, harkitse

(F2)

Huomaa, että kaikkien on oltava koprime (muuten yhteinen jakaja ja täytyy jakaa ja ). Laitetaan

(F3)

Samoista syistä kuin edellä, kaikki jaot ja koska ne ovat kaikki alkulukuja, ovat jaettavissa tulolla . Jaamme nyt yhtälön (F3) molemmat osat :lla , saamme (F4) [5]

Toisaalta kaikki yhtälön (F1) ratkaisut vastaavat virheellisen Znam-tehtävän ratkaisuja. Kuitenkin kaikille tunnetuille ratkaisuille y = 1, joten ne täyttävät yhtälön

(F4)

Siten tämä johtaa luvun ykkösen esittämiseen egyptiläisenä murto - osana, ykkösen murto -osien summana . Jotkut Znam-ongelmaa käsittelevistä kirjoituksista tutkivat myös ratkaisuja tähän yhtälöön. Brenton ja Hill [6] kuvaavat yhtälön (F4) sovelluksen topologiassa pinnan piirteiden luokittelemiseksi , ja Domaracki ym. [7] kuvaavat sovellusta ei-determinististen äärellisten automaattien teoriaan .

Ratkaisujen määrä

Kuten Janak ja Skula [8] osoittivat , minkä tahansa k :n ratkaisujen lukumäärä on äärellinen, joten on järkevää laskea kunkin k :n ratkaisujen kokonaismäärä .

Brenton ja Vassiliou havaitsivat laskelmiensa jälkeen, että k = 5: stä alkaen k = 5 k :n pienten arvojen ratkaisujen määrä muodostaa sekvenssin

2 , 5 , 18 , 96 sekvenssi A075441 OEIS : ssä .

Tällä hetkellä tunnetaan useita ratkaisuja arvoille k = 9 ja k = 10, mutta ei tiedetä, kuinka monta ratkaisua näille arvoille jää ratkaisematta. Jos k ei kuitenkaan ole kiinteä, ratkaisuja on äärettömän monta - Cao ja Jing [9] osoittivat, että jokaiselle k ≥ 12:lle on olemassa vähintään 39 ratkaisua , mikä parantaa aikaisempaa tulosta, joka osoitti, että ratkaisuja on vähemmän [10] . [11] . Sun ja Cao [11] ehdottivat, että kunkin k :n ratkaisujen lukumäärä kasvaa monotonisesti k :n kanssa .

Ei tiedetä, onko Znam-ongelmaan olemassa ratkaisua vain parittomilla luvuilla. Yhtä poikkeusta lukuun ottamatta kaikki tunnetut ratkaisut alkavat numerolla 2 . Jos kaikki Znam-tehtävän ratkaisussa tai epäsopivan Znam-tehtävän ratkaisussa olevat luvut ovat alkulukuja , niiden tulo on yksinkertainen pseudoperfektiluku [12] . Ei tiedetä, onko tällaisia ​​ratkaisuja olemassa ääretön määrä.

Muistiinpanot

  1. ↑ Sun, 1983 .
  2. ↑ Barbeau, 1971 .
  3. ↑ Mordell, 1973 .
  4. ↑ Skula, 1975 .
  5. ↑ Brenton, Vasiliu, 2002 , s. 6.
  6. ↑ Brenton, Hill, 1988 .
  7. ↑ Domaratzki, Ellul, Shallit, Wang, 2005 .
  8. ↑ Janak, Skula, 1978 .
  9. ↑ Cao, Jing, 1998 .
  10. ↑ Cao, Liu, Zhang, 1987 .
  11. ↑ 12 Sun , Cao, 1988 .
  12. ↑ Butske, Jaje, Mayernik, 2000 .

Kirjallisuus

Linkit