  |
|
| ° Forum ° Rejestracja ° Szukaj ° | |
| Auto giełda ° wnętrzowe stacje transformatowe |
 |
Matma / podzlozonosc, czesc 3 -- wh, 2001-03-11 |
| . 1 . 2 . 3 . >> |
| Autor | Wiadomość |
| Posted: 11 Mar 2001 08:10:32 -- Uparlem sie, zeby recznie policzyc zn(t) dla malych t, chyba bez sensu. Lepiej byloby zajac sie wynikami bardziej ogolnymi. W kazdym razie podam obliczena w mniejszych dawkach niz poczatkowo planowalem. Nie chodzi o dlugosc artykulow (to tez), ale o wprowadzeie wiekszej ilosci pomocniczych podzlozonosci, co ulatwia organizacje i strawienie obliczen. Tak wiec tym razem wartosci t dojada gdzies do 30, z dwoma lukami (t=23 29) i paroma wartosciami powyzej 30. Moze to i nonsens, ale planuje doprowadzic t systematycznie do ponad 100 (matematyczny masochizm! :-). Nawet wstawie to do planu czyli spisu rzeczy. (Byc moze dam tez ogolne wyniki zanim dokoncze zmudne spisanie obliczen). Przypominam, ze wymienione ponizej paragrafy 1-3 zamiescilem w czesci 1, a paragrafy 4-5 w czesci 2. W niniejszej czesci 3 daje/ tylko paragraf 6 (oraz kopiuje paragraf 2 -- oznaczenia, z jednym uzupelnieniem). Pozdrawiam, Wlodzimierz Holsztynski PS. Wygodnie jest czytac artykuly matematyczne, w szczegolnosci te o podzlozonosci, umieszczajac kopie w dwoch oknach -- z jednego mozna czytac, a w drugim miec na oku pewne twierdzenia, tabele... na ktore tekst powoluje sie czesto i z duzej odleglosci. Mozna nawet rozne wzory, definicje, tabele... same, bez reszty tekstu, skopiowac do tego drugiego okna. Ulatwi to czytanie. ----------------------------------------------------- podzlozonosci ============= Spis rzeczy: 1. WSTEP 2. OZNACZENIA 3. ZLOZONOSC I PODZLOZONOSC NATURALNA 4. PODZLOZONOSCI C0 ... C9 5. ZNIWO -- zastosowania C9 6. OBLICZENIE zn(t) dla malych t. 7. OBLICZENIE zn(t) dla malych, ale nie az tak, t. 8. OBLICZENIE zn(t) dla nieco wiekszych t. ---------------- 2. OZNACZENIA N -- zbior liczb naturalnych R -- cialo liczb rzeczywistych < -- mniejsze lub rowne / -- wieksze lub rowne
x/ -- sufit liczby rzeczywistej x /x -- podloga liczby rzeczywistej x Objasnienie: /x x/ sa liczbami calkowitymi, takimi ze: x-1 < /x < x < x/ < x+1 T := 3^(1/3) lt -- logarytm o podstawie T czyli taki, ze lt(3) = 3. W tabelach bede pisal "k-n", a twierdzeniach i w tekscie "k..n" zamiast "k...n". ----------- 6. OBLICZENIE zn(t) dla malych t ================================ Niech: --------- tabela c0 --------- c0(n) := n dla n = 1-5 c0(6) := 5 c0(n) := 6 dla n = 7 8 9 c0(n) := 7 dla n = 10 12 c0(n) := 8 dla n = 11 13 14 15 16 18 c0(n) := 9 dla n = 17 19 20 21 24 27 c0(n) := 10 dla n = 22 23 25 26 oraz dla n 27 Zdefinowalismy w ten sposob c0 : N -- N, przy tym tak, ze: c0(1+n) < 1 + c0(n) dla dowolnego n in N. Wynika stad, ze c0(a+b) < a + c0(b) dla dowolnych a b in N. Poniewaz c0(a) = a dla a = 1..5, to nierownosc: <+0 c0(a+b) < c0(a) + c0(b) zachodzi dla a = 1..5 oraz dowolnego b in N. Teraz niech liczby naturalne a b spelniaja nierownosc: 5 < a < b. Wtedy c0(a) / 5, max c0 = 8, wiec nierownosc (+) jest spelniona dla wszystkich b takich, ze c0(b) / 5, jako ze wtedy: c(a) + c(b) / 10 / c(a+b) Udowodnilismy wiec <0+ w pewnej ogolnosci, dla dowolnych naturalnych a b. Przechodzimy do dowodu: <*0 c0(a*b) < c0(a) + c0(b) Jest to prawda dla a=1. Zalozmy, ze liczby naturalne a b spelniaja nierownosc 2 < a < b. Wtedy c0(a) / 2. Zatem <*0 zachodzi dla wszystkich b takich, ze c0(b) / max(c0) - 2 = 8. Pozostalo wiec sprawdzic b dla ktorych c0(b) < 7. Warunek <*0 zachodzi tez dla a=2 b = 10 12 (kiedy c0(b)=7), bowiem c0(2*10) = c0(2*12) = 9 (patrz tabela c0). Podobnie z pomoca tabeli c0 sprawdzamy, ze c0(2*b) < 2+b dla pozostalych b = 2..9. Pozostal wiec do sprawdzenia zakres 3 < a < b. Wtedy c0(a) / 3, wiec wystarczy sprawdzic b takie, ze c0(b) < max(c0) - 3 = 7, czyli dla b = 3..9, co widzimy patrzac w tabele c0. Pozostal zakres 4 < a < b. Wtedy c0(a) / 4. Wystarczy sprawdzic b takie, ze c0(b) < 5. Oznacza to, ze 4 < a < b < 5. Pozostaly wiec tylko trzy pary (a b) = (4 4) (4 5) oraz (5 5). Tabela c0 pokazuje, ze <*0 zachodzi we wszystkich trzech wypadkach. Udowodnilismy wiec: ======================================= TWIERDZENIE 7. c0 jest podzlozonoscia. ======================================= Latwo stad wynika, ze: ================================== Twierdzenie 8. zn(t) = c0(t) dla t = 1..22 24..28 30 32 36 ================================== Mozemy twierdzenie 7 zapisac w postaci czesciowej, skonczonej tabeli: zn(n) = n dla n = 1-5 zn(6) = 5 zn(n) = 6 dla n = 7 8 9 zn(n) = 7 dla n = 10 12 zn(n) = 8 dla n = 11 13 14 15 16 18 zn(n) = 9 dla n = 17 19 20 21 24 27 zn(n) = 10 dla n = 22 25 26 28 30 32 36 Dowod twierdzenia 8 ------------------- Wiemy, ze zn(1) = 1 oraz zn(1+t) < 1 + zn(t), skad zn(t) < t dla dowolnego t in N. Zatem t < c0(t) < zn(t) < t dla t=1...5, skad zn(t) = c0(t) = t dla t = 1...5. Takze zn(6) = zn(2*3) < zn(2)+zn(3) < 5. Zatem zn(6) = c0(6) = 5. Podobnie: zn(7) < 1 + zn(6) = 6 = c0(7) < 7, wiec zn(7) = c0(7) = 6. Podsumowujac: zn(t) = c0(t) dla t = 1..7. Nastepnie latwo sprawdzic, ze c0(n) = 2 + c0(n/2) = 2 + zn(n/2) / zn(n) czyli zn(n) = c0(n) dla n=8 10 12 14. Podobnie: c0(n/3) = 3 + c0(n/3) = 3 + zn(n/3) / zn(n) dla n = 9 15 18 21 24. Podsumowujac: zn(t) = c0(t) dla t = 1..10 12 14 15 18 21 24. Teraz: (i) zn(t) < 1+zn(t-1) = 1+c0(t-1) = c0(t) < zn(t) czyli zn(t) = c0(t) dla t = 11 13 19 22 25. Takze: zn(16) < 4*zn(2) = 8 = c0(16) < zn(16), czyli zn(16) = c0(16); po czym (i) zachodzi dla t=17, czyli zn(17) = c0(17). Podsumowujac: zn(t) = c0(t) dla t = 1..18 21 24 25 Dla n = 18 21 mamy c0(1+n) = 1+c0(n), skad zn(t) = c0(t) dla t = 19 22. Takze c0(t) = 2+c0(t/2) dla t=20 22 26 28 30 32 36, oraz c0(3*9) = 3+c0(9), skad zn(27) = c0(27). Podsumowujac: zn(t) = c0(t) dla t=1..22 24..28 30 32 36 cbdo. |
|
| Andrzej Komisarski
|
Posted: 11 Mar 2001 10:08:30 Uparlem sie, zeby recznie policzyc zn(t) dla
malych t, chyba bez sensu. Moze to i nonsens, ale planuje doprowadzic t systematycznie do ponad 100 (matematyczny masochizm! :-). Kilkunastolinijkowy program napisany w C wypluł w ciągu pół sekundy następujące wartości (obciąłem wyniki programu do pierwszych 600 wartości). 1 | 1 2 3 4 5 5 6 6 6 7 11 | 8 7 8 8 8 8 9 8 9 9 21 | 9 10 11 9 10 10 9 10 11 10 31 | 11 10 11 11 11 10 11 11 11 11 41 | 12 11 12 12 11 12 13 11 12 12 51 | 12 12 13 11 12 12 12 13 14 12 61 | 13 13 12 12 13 13 14 13 14 13 71 | 14 12 13 13 13 13 14 13 14 13 81 | 12 13 14 13 14 14 14 14 15 13 91 | 14 14 14 15 14 13 14 14 14 14 101 | 15 14 15 14 14 15 16 13 14 14 111 | 14 14 15 14 15 15 14 15 15 14 121 | 15 15 15 15 15 14 15 14 15 15 131 | 16 15 15 16 14 15 16 15 16 15 141 | 16 16 16 14 15 15 15 15 16 15 151 | 16 15 15 16 16 15 16 16 16 15 161 | 16 14 15 15 15 16 17 15 16 16 171 | 15 16 17 16 16 16 17 17 18 15 181 | 16 16 16 16 16 16 17 17 15 16 191 | 17 15 16 16 16 16 17 16 17 16 201 | 17 17 17 16 17 17 17 16 17 16 211 | 17 17 17 18 17 15 16 16 16 16 221 | 17 16 17 16 16 17 18 16 17 17 231 | 17 17 18 16 17 17 17 17 18 16 241 | 17 17 15 16 17 16 17 17 17 17 251 | 18 16 17 17 17 16 17 17 17 17 261 | 17 18 19 17 18 17 18 18 19 16 271 | 17 17 17 18 17 17 18 18 17 17 281 | 18 18 19 18 17 18 18 16 17 17 291 | 17 17 18 17 18 17 17 18 19 17 301 | 18 18 18 17 18 17 18 18 18 18 311 | 19 17 18 18 17 18 19 18 19 17 321 | 18 18 18 16 17 17 17 17 18 17 331 | 18 18 17 18 19 17 18 18 18 18 341 | 19 17 18 18 18 19 20 18 19 18 351 | 17 18 19 18 19 19 18 19 20 17 361 | 18 18 18 18 18 18 19 18 18 18 371 | 19 18 19 19 18 19 19 17 18 18 381 | 18 19 20 17 18 18 18 18 19 18 391 | 19 18 19 19 19 18 19 19 18 18 401 | 19 19 19 19 17 18 19 18 19 18 411 | 19 19 20 18 19 18 19 19 20 18 421 | 19 19 19 19 19 19 19 20 19 19 431 | 20 17 18 18 18 18 19 18 19 18 441 | 18 19 20 18 19 19 19 18 19 18 451 | 19 19 19 20 19 18 19 19 18 19 461 | 20 19 20 19 19 20 21 18 19 19 471 | 19 19 20 19 19 19 19 20 21 18 481 | 19 19 19 19 19 17 18 18 18 19 491 | 20 18 19 19 18 19 20 19 20 19 501 | 20 20 21 18 19 19 19 19 20 19 511 | 19 18 18 19 20 19 20 19 20 19 521 | 20 19 20 20 19 20 20 19 20 20 531 | 20 19 20 20 21 20 21 21 20 18 541 | 19 19 19 19 19 19 20 20 19 19 551 | 20 19 20 20 19 20 21 19 20 19 561 | 20 20 21 20 20 21 18 19 20 19 571 | 20 20 20 19 20 18 19 19 19 19 581 | 20 19 20 19 19 20 21 19 20 20 591 | 20 19 20 19 20 20 20 20 21 19 |
| PiotrCF
|
Posted: 11 Mar 2001 12:59:12 Andrzej Komisarski napisał: Uparlem sie, zeby recznie policzyc zn(t) dla
malych t, chyba bez sensu. Moze to i nonsens, ale planuje doprowadzic t systematycznie do ponad 100 (matematyczny masochizm! :-). Kilkunastolinijkowy program napisany w C wypluł w ciągu pół sekundy następujące wartości (obciąłem wyniki programu do pierwszych 600 wartości). Tak, to liczy się "natychmiast". Dla zainteresowanych: Programik (źródło + .exe): http://nest.gliwice.pl/~piotrcf/zn01.zip Wyniki dla n<10000: http://nest.gliwice.pl/~piotrcf/zn10000.txt Piotr -- Zabezpieczenie antyspamowe: w moim adresie nie ma cyfr |
| Posted: 11 Mar 2001 14:02:49 Ja (wh): Uparlem sie, zeby recznie policzyc zn(t) dla
malych t, chyba bez sensu. Moze to i nonsens, ale planuje doprowadzic t systematycznie do ponad 100 (matematyczny masochizm! :-). Andrzej Komisarski: Kilkunastolinijkowy program napisany w C wypluł w ciągu pół sekundy
następujące wartości (obciąłem wyniki programu do pierwszych 600 wartości). Piotr: Tak, to liczy się "natychmiast". Dla zainteresowanych:
Programik (źródło + .exe): http://nest.gliwice.pl/~piotrcf/zn01.zip Wyniki dla n<10000: http://nest.gliwice.pl/~piotrcf/zn10000.txt Piotr Zlozonosc w wypadku (1 + *) jest rzeczywiscie jak marzenie programisty, bo nie ma zadnego niebezpieczenstwa nieskonczonych petli, wyniki dzialan zawsze przewyzszaja argumenty, wiec najprostsze programy sa calkiem szybkie. Reczne liczenie ma pewien sens, zmusza do stosowania wydajniejszych metod, co jest pouczajace. Gdyby ktos chcial rachowac zn(t) dla t rzedu 10^10, to optymalizacja (mozna skrocic do optymizacja?) mialaby sens. Chyba jednak zarzuce/ zarzucanie listy recznymi rachunkami niskich wartosci. Tabele wartosci pozwalaja na szybkie eksperymenty, mozna korzystac np z egrep. Rzut oka na tabele pozwala zauwazyc spora/ stabilnosc zn. Na przyklad zn(k) = 28 dla k=9361...9370, az dla 10 kolejnych argumentow pod rzad. Czy istnieja odcinki k = a+1 ... a+L dla ktorych zn(k) jest stale, o dowolnej dlugosci L? Czy istnieja odcinki k = a ... a+L-1, o dowolnej dlugosci L, dla ktorych zn(a+t) = zn(a)+t dla t=1 ... L-1? Czy istnieje taki odcinek o dlugosci L 5? Dziekuje za tabelki. Pozdrawiam, Wlodek PS. Mam wlasciwie perl, ale tylko w drugiej czesci dysku, tej unixowej. Sciagnalbym perl do win98, istnieja/ w sieci darmowe, ale zawsze cos w przeszlosci mi sie w procedurze mylilo i tylko zasmiecalem PC, wiec juz nie probuje. Czy istnieje miejsce w Interncie, z ktorego perl sciaga sie bez zamieszania? (Mialem kiedys perl na PC, ale sam go z sieci nie sciagalem). |
|
| PiotrCF
|
Posted: 11 Mar 2001 14:56:39 Reczne liczenie ma pewien sens, zmusza do stosowania
wydajniejszych metod, co jest pouczajace. Gdyby ktos chcial rachowac zn(t) dla t rzedu 10^10, to optymalizacja (mozna skrocic do optymizacja?) mialaby sens. To rośnie w przybliżeniu logarytmicznie. Zobacz: http://nest.gliwice.pl/~piotrcf/znwyk1.gif (skala liniowa) http://nest.gliwice.pl/~piotrcf/znwyk2.gif (skala logarytmiczna) Dla 10^10 byłoby około 73. Czy istnieja odcinki k = a+1 ... a+L dla ktorych
zn(k) jest stale, o dowolnej dlugosci L? Wygląda na to, że tak - funkcja jest coraz bardziej "płaska". Ale to niczego nie dowodzi. Czy istnieja odcinki k = a ... a+L-1, o dowolnej dlugosci L, dla ktorych zn(a+t) = zn(a)+t dla t=1 ... L-1? Czy istnieje taki odcinek o dlugosci L 5? Raczej nie, chociaż kto wie... Piotr -- Zabezpieczenie antyspamowe: w moim adresie nie ma cyfr |
| Posted: 11 Mar 2001 18:06:11 -- Piotr: Reczne liczenie ma pewien sens, zmusza do stosowania wydajniejszych metod, co jest pouczajace. Gdyby ktos chcial rachowac zn(t) dla t rzedu 10^10, to optymalizacja (mozna skrocic do optymizacja?) mialaby sens. To rośnie w przybliżeniu logarytmicznie. [...] Nie o to mi chodzilo, tylko o zlozonosc algorytmu. O zachowaniu asymptotycznym zn od dawna wiadomo, mianowicie, ze w przyblizeniu chodzi o funkcje logarytmiczna/ lt o podstawie T := 3^(1/3). A Tobie teraz najprosciej zajrzec do "Czesci 2" niniejszej serii, gdzie znajdziesz lt < C0 < zn. Ciekawe, czy: lim sup (zn(k) - lt(k)) = oo Prawie na pewno tak, bez watpienia. Ale jak szybko? Moglbys empirycznie zobaczyc tendencje/ zn(k)-lt(k) dla k w zakresie programu. Mozna tez by probowac zbadac: lim (2*k - zn(2^k)) Chyba jednak otad nie wiadomo, czy przypadkiem 2*k - zn(2^k) nie jest 0 dla wszystkich k. Bardzo watpie. Wierze, ze lim (2*k - 2^k) = oo Dla 10^10 byłoby około 73.
lt(10^10) = 10*lt(10) przy czym 6 < lt(10) < 7 = rn(10), zatem: 60 < lt(10^10) < rn(10^10) < 70 a wiec wyraznie mniej niz 73. Nawet wyraznie mniej niz 70, bowiem, co nawet jest ciekawe, zn(5^5) < 5*zn(5) = 25, i to porzadnie: zn(5^5) < 1 + zn(15624) = 1 + zn(2^3 * 3^2 * 17) < 1 + (6 + 6 + 9) = 22 czyli: zn(5^5) < 22 Stad: zn(10^10) = zn(2^10 * 5^10) < 20 + 44 = 64 Tak wiec: zn(10^10) < 64 Z innych przykladow na zn(p^k) < k*zn(p), dla liczby pierwszej p, podam: zn(11^2) < 1 + zn(120) = 1 + zn(8*3*5) < 1 + 4 + 3 + 5 = 13 < 16 = 2*zn(11) czyli: zn(11^2) = 2*zn(11) - 3 < 2*zn(11) p=11 jest raczej ekstremalne pod tym wzgledem, p=5 tez wychyla sie mocno w te/ strone/, choc nie az tak. Za to p=13 jest raczej ekstremalne w druga/ strone/. (Oczywiscie p=3 jest specjalne, bo multiplikatywnie jest blisko stalej Eulera e, blizej niz inne liczby calkowite). Chyba sie tym jeszcze zajme. Czy istnieja odcinki k = a+1 ... a+L dla ktorych
zn(k) jest stale, o dowolnej dlugosci L? Wygląda na to, że tak - funkcja jest coraz bardziej "płaska". Ale to niczego nie dowodzi. Plaskosc nie wystarczy. Jest niejasnym ile jest fluktuacji. Chyba zawsze: min(zn(p-1) zn(p+1)) < zn(p) dla kazdej liczby pierwszej p. Ale podobne nierownosci moga zachodzic dla wielu innych konfiguracji teorioliczbowych. Mimo to raczej sadze, ze dlugosc L moze byc dowolnie wielka, nawet jesli takie dlugie odcinki beda niezwykle rzadkie. Czy istnieja odcinki k = a ... a+L-1, o dowolnej dlugosci L, dla ktorych zn(a+t) = zn(a)+t dla t=1 ... L-1? Czy istnieje taki odcinek o dlugosci L 5? Raczej nie, chociaż kto wie... Piotr A poza poczatkowym, czy istnieje inny o dlugosci 5? O dlugosci 4? Czy istnieje nieskonczenie wiele o dlugosci 3? (Oczywiscie istnieje oo-wiele o dlugosci L=2 :-) Pozdrawiam, Wlodek |
|
| PiotrCF
|
Posted: 11 Mar 2001 19:02:02 Dla 10^10 byłoby około 73.
(...) 60 < lt(10^10) < rn(10^10) < 70 a wiec wyraznie mniej niz 73. (...) czyli: zn(5^5) < 22 Tak dokładnie w to się nie wgłębiałem :-) Ale akurat zn(5^5) = zn(3125) jest w tabelce, której adres wcześniej wysłałem i jest równe 25. Analizowanie ciągu zn(n) jest bardzo trudne (poza szczególnymi przypadkami). W encyklopedii ciągów liczb całkowitych jest też inny ciąg: najmniejszych liczb, do przedstawienia których w postaci "jedynkowych wyrażeń" potrzeba n jedynek. Zaczyna się tak: 1,2,3,4,5,7,10,11 tzn. pierwszą liczbą, na którą potrzeba 8 jedynek, jest 11. http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An um=A005520 Dalsze elementy często kończą się na 9, 99 i 999. Ale dlaczego, tego pewnie nikt nie wie... Piotr -- Zabezpieczenie antyspamowe: w moim adresie nie ma cyfr |
| . 1 . 2 . 3 . >> |