Znams utmaning

I talteorin frågar Znam-problemet vilka mängder av k heltal som har egenskapen att varje heltal i mängden är en riktig divisor av produkten av de andra heltal i mängden plus 1. Znam-problemet är uppkallat efter den slovakiske matematikern Stefan Znam , som föreslog problemet 1972, även om andra matematiker tittade på liknande problem ungefär samtidigt. Ett relaterat problem kräver inte att divisorn är en riktig divisor, och kallas Znams felaktiga problem.

En lösning på det felaktiga problemet är lätt att få för alla k — de första k termerna i Sylvester-sekvensen har de egenskaper som krävs. Sun [1] visade att det finns åtminstone en lösning på det (riktiga) Znam-problemet för alla k ≥ 5. Suns lösning är baserad på en rekursiv relation som liknar Sylvestersekvensen men med en annan uppsättning initiala värden.

Znam-problemet är nära relaterat till egyptiska fraktioner . Det är känt att det bara finns ett ändligt antal lösningar för varje fast k . Det är inte känt om det finns lösningar på Znam-problemet endast med udda nummer. Det finns också några andra öppna frågor.

Utmana

Znams problem frågar vilka uppsättningar av k heltal som har egenskapen att varje heltal i mängden är en riktig divisor av produkten av de andra heltal i mängden plus 1. Det vill säga, givet ett tal k , vilka uppsättningar heltal finns det

,

så att för något i delar talet n i men är inte lika med

Ett relaterat problem gäller uppsättningen heltal som är divisorer av produkten av de andra talen plus ett, men dessa divisorer behöver inte vara korrekta. Det verkar inte som att detta problem har fått ett stabilt namn i litteraturen, och vi kommer att kalla det Znams otillbörliga problem. Varje lösning på Znam-problemet är också en lösning på det felaktiga Znam-problemet, men det omvända är inte alltid sant.

Historik

Znam-problemet är uppkallat efter den slovakiske matematikern Stefan Znam, som föreslog problemet 1972. Barbeau [2] föreslog det olämpliga Znam-problemet för k = 3, och Mordell [3] hittade alla lösningar på det olämpliga problemet för k ≤ 5. Skula [4] visade att Znam-problemet inte har några lösningar för k < 5, och tillskriver Yanak att hitta lösningen {2, 3, 11, 23, 31} för k = 5.

Exempel

En av lösningarna för k = 5 är {2, 3, 7, 47, 395}. Enkla beräkningar visar det

3×7×47×395 + 1 = 389866,   är delbart med 2 men inte lika med 2
2×7×47×395 + 1 = 259911,   delbart med 3 men inte lika med 3
2×3×47×395 + 1 = 111391,   är delbart med 7 men inte lika med 7
2×3×7×395 + 1 = 16591,   delbart med 47 men inte lika med 47
2×3×7×47 + 1 = 1975   är delbart med 395 men inte lika med 395.

En intressant "nästan lösning" för k = 4 är mängden {2, 3, 7, 43} som bildas av de första fyra medlemmarna i Sylvester-sekvensen. En mängd har egenskapen att varje heltal i mängden delar produkten av de andra medlemmarna i mängden plus 1, men den sista medlemmen i den mängden är lika med produkten av de tre första medlemmarna plus en, så den medlemmen är inte en rätt divisor. Den här lösningen är alltså en lösning på det felaktiga Znam-problemet och inte på Znam-problemet.

Koppling med egyptiska bråk

Varje lösning på det felaktiga Znam-problemet motsvarar att lösa ekvationen

(F1)

där y , som alla x i , måste vara ett heltal. För att visa detta, överväg

(F2)

Observera att alla måste vara coprime (annars den gemensamma divisorn och måste dividera och ). Låt oss sätta

(F3)

Av samma skäl som ovan kan eventuella uppdelningar , och eftersom de alla är coprime, delbara med produkten . Vi dividerar nu båda delarna av ekvationen (F3) med , vi får (F4) [5]

Omvänt motsvarar alla lösningar av ekvation (F1) lösningar på det felaktiga Znam-problemet. Men för alla kända lösningar y = 1, så de uppfyller ekvationen

(F4)

Således leder detta till representationen av talet ett som ett egyptiskt bråk , summan av bråken av ett . Några av de citerade artiklarna om Znam-problemet studerar också lösningar på denna ekvation. Brenton och Hill [6] beskriver en tillämpning av ekvation (F4) i topologi för att klassificera ytegenskaper , och Domaracki et al [7] beskriver en tillämpning på teorin om icke-deterministiska finita automater .

Antal lösningar

Som Janak och Skula [8] visade är antalet lösningar för varje k ändligt, så det är vettigt att beräkna det totala antalet lösningar för varje k .

Brenton och Vassiliou fann efter beräkningar att antalet lösningar för små värden på k , med start från k = 5, bildar en sekvens

2 , 5 , 18 , 96 sekvens A075441 i OEIS .

För närvarande är flera lösningar kända för k = 9 och k = 10, men det är inte känt hur många lösningar som förblir ogrundade för dessa värden. Men om k inte är fixat finns det oändligt många lösningar - Cao och Jing [9] visade att det finns minst 39 lösningar för alla k ≥ 12, vilket förbättrar ett tidigare resultat som bevisade förekomsten av färre lösningar [10] [11] . Sun och Cao [11] föreslog att antalet lösningar för varje k växer monotont med k .

Det är inte känt om det finns någon lösning på Znam-problemet med endast udda nummer. Med ett undantag börjar alla kända lösningar med 2 . Om alla siffror i lösningen av Znam-problemet eller det felaktiga Znam-problemet är primtal , är deras produkt ett enkelt pseudoperfekttal [12] . Det är inte känt om det finns ett oändligt antal lösningar av detta slag.

Anteckningar

  1. ↑ Sön, 1983 .
  2. ↑ Barbeau, 1971 .
  3. ↑ Mordell, 1973 .
  4. ↑ Skula, 1975 .
  5. ↑ Brenton, Vasiliu, 2002 , sid. 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 sön , Cao, 1988 .
  12. ↑ Butske, Jaje, Mayernik, 2000 .

Litteratur

Länkar