logo
 
Witamy, Gość. Zaloguj się lub zarejestruj.

Zaloguj się podając nazwę użytkownika, hasło i długość sesji

Autor Wątek: 3. Podstawowe pojęcia  (Przeczytany 72385 razy)

0 użytkowników i 1 Gość przegląda ten wątek.

Online Lucyfer

  • Administrator
  • Ekspert
  • *****
  • Wiadomości: 620
    • Zobacz profil
    • Email
Odp: 3. Podstawowe pojęcia
« Odpowiedź #70 dnia: Sierpień 16, 2019, 18:17:37 »
Cytat: SasQ
A jesteś pewny, że to faktycznie jest zagadka, a nie tylko rekwizyt filmowy z nic nie znaczącymi symbolami

Oczywiście że jest to rekwizyt filmowy ale jak wiesz w mediach przemyca się sporo intrygujących treści
co sam pokazałeś na przykładzie bajek
Więc kto wie być może i tutaj symbole mają znacznie.. :mysl:

Mam jeszcze inną zagadkę, tym razem z serialu Another Life, która być może bardziej Cię zainteresuje bo rozwiązanie jej znają tylko kosmici  :oczko:
http://swietageometria.info/iu/di-LECW.png
3. Podstawowe pojęcia


« Ostatnia zmiana: Sierpień 16, 2019, 18:21:58 wysłana przez Lucyfer »

Offline Lady F

  • Zaawansowany użytkownik
  • ****
  • Wiadomości: 305
  • Merlin
    • Zobacz profil
Odp: 3. Podstawowe pojęcia
« Odpowiedź #71 dnia: Sierpień 21, 2019, 19:41:30 »
SasQ -

Cytuj
Dla porównania: Moje zagadki zawsze mają rozwiązanie, i zawsze znam je z góry, gdy je tutaj zadaję.

 :o cieszy mnie to :super: ;)

Lucyfer -

Cytuj
Mam jeszcze inną zagadkę, tym razem z serialu Another Life, która być może bardziej Cię zainteresuje bo rozwiązanie jej znają tylko kosmici

Sorry Lucek, ale SasQ pyta czy Ty znasz rozwiazanie, a jesli znasz = jestes kosmita.

A ja, choc (jestem kosmita) nie znam odpowiedzi. Ale z powyzszego wypisywania SasQ dokopalam sie do tego:
https://pl.wikipedia.org/wiki/Liczby_Mersenne%E2%80%99a

I jest to dosc ciekawe, bo gdy zglebic temat doglebnie, to mnich mial i ma racje, ale maszyny liczace popelniaja bledy... :taaak:



Offline SasQ

  • Collegium Invisible
  • Zaawansowany użytkownik
  • *
  • Wiadomości: 309
  • Płeć: Mężczyzna
  • Quanta rhei... :-)
    • Jabber/AQQ
    • Zobacz profil
    • Naukowy kącik kwantowy
    • Email
Odp: 3. Podstawowe pojęcia
« Odpowiedź #72 dnia: Sierpień 22, 2019, 00:16:55 »
Sorry Lucek, ale SasQ pyta czy Ty znasz rozwiazanie, a jesli znasz = jestes kosmita.

Tak? O to pytam? Qrcze, nie wiedziałem...  :mysl:
Wydawało mi się, że pytałem jedynie, czy Lucek ma pewność, że rozwiązanie w ogóle istnieje (niekoniecznie czy on sam go zna), bo gdyby nie istniało, szukanie go (rozwiązania, nie Lucka) mogłoby się okazać stratą czasu :czas:

Ale z powyzszego wypisywania SasQ dokopalam sie do tego:
https://pl.wikipedia.org/wiki/Liczby_Mersenne%E2%80%99a

Miło słyszeć, że moje wypisywanie jednak zainspirowało Cię do zgłębiania tematu, nawet mimo tego, że nie chciałaś szukać rozwiązania samej zagadki ;) Czyżby na ich trop naprowadził Cię fakt, że te liczby powstają ze zsumowania kolejnych potęg dwójki? :->

Liczby Mersenne'a (to tego się nie odmienia "Mersennego"?) faktycznie mają związek z liczbami doskonałymi, które były rozwiązaniem mojej zagadki, jako że każda parzysta liczba doskonała to liczba pierwsza Mersenne'a (czyli prosta potęga dwójki zmniejszona o 1) pomnożona przez poprzednią potęgę dwójki:

(2p – 1) · 2p–1

Pisał o tym już Euklides w propozycji 36 wieńczącej IX księgę jego "Elementów", w której podał przepis na znajdowanie parzystych liczb doskonałych i udowodnił jego poprawność.

Fermat w liście do Mersenne'a z czerwca 1640 r. proponował nazywać takie potęgi dwójki zmniejszone o 1 "rdzeniami liczb doskonałych" właśnie z tego powodu, że służą do ich zbudowania, i aby znaleźć parzystą liczbę doskonałą, najpierw trzeba znaleźć jej "rdzeń" w takiej właśnie postaci i upewnić się, że jest on liczbą pierwszą.

Można to łatwiej zauważyć, gdy się je zapisze tak, jak robią to komputery: w systemie dwójkowym ;) Odkryjesz wtedy, że taka suma potęg dwójki to nic innego jak liczba dwójkowa złożona z samych jedynek :) (bo jedynka na każdej kolejnej pozycji oznacza, że ta konkretna potęga dwójki wchodzi w skład wynikowej liczby).
To nam rozwiązuje sprawę sumy ciągu geometrycznego o podstawie 2: 1 + 2 + 22 + 23 + 24 + … + 2n.
Gdy do takiej liczby dwójkowej dodasz jeszcze 1, to nastąpi przeniesienie, które lawinowo odwiedzi wszystkie kolejne pozycje i wyzeruje je, aż dotrze na drugi koniec łańcucha i stanie na czele ;) więc dostaniesz następną potęgę dwójki. Czyli oryginalna liczba była tą potęgą dwójki o 1 zmniejszoną.
To nam rozwiązuje drugą część równania: 2n – 1  8*)
Ostatni element to wymnożenie tego wszystkiego przez 2n–1. W systemie dwójkowym każde mnożenie przez 2 przesuwa bity (cyfry dwójkowe) o 1 pozycję w lewo, podobnie jak w systemie dziesiętnym mnożenie przez 10. Więc 2n-1 przesunie ten ciąg jedynek o n-1 pozycji w lewo, zostawiając za sobą n-1 zer ;)  (o jedno zero mniej, niż było jedynek).
Tak więc w systemie dwójkowym każda parzysta liczba doskonała to ciąg samych jedynek, a po nim o jedną cyfrę krótszy ciąg samych zer ;) Np.:

   610 =           1102
  2810 =         111002
 49610 =     1111100002
812810 = 11111110000002


itd. ;)

Można je więc także zapisać jako różnicę dwóch potęg dwójki (co też daje ciąg geometryczny, lecz zaczynający się od tej mniejszej potęgi dwójki, zamiast od 1).


Liczby Mersenne'a to jednak tylko wierzchołek góry lodowej :)  Bo takie ciągi największej cyfry dla danego systemu liczbowego można tworzyć nie tylko w systemie dwójkowym, lecz w każdym systemie, dla dowolnej podstawy ;) Np. w systemie dziesiętnym będą to ciągi samych dziewiątek (jako że to dziewiątka jest największą cyfrą w tym systemie). Np.:

999999  =  106 – 1  =  9 · (1 + 10 + 102 + 103 + 104 + 105)

i w ogólności 10n – 1 to ciąg n samych dziewiątek ;) i odpowiada sumie n kolejnych potęg dziesiątki (ciągowi geometrycznemu o podstawie 10) pomnożonych przez 9 (różnicę między 10 a 1):

999…999  =  10n – 1  =  (10 – 1) · (1 + 10 + 102 + 103 + … + 10n–1)

Takie ciągi dziewiątek też mają ciekawe właściwości matematyczne ;>  Jedną z nich odkryłem, gdy szukałem sposobu na zamianę okresowych ułamków dziesiętnych na zwykłe:

Każda liczba pierwsza (prócz 2 i 5) dzieli nieskończenie wiele ciągów złożonych z samych dziewiątek. 8*)

Np. 37 dzieli liczbę 999 (a także 999999, 999999999, i każdą następną, w której liczba dziewiątek to wielokrotność trójki).
Podobnie 41 dzieli 99999 (a także 9999999999, 999999999999999 itd.).
Czasami trzeba tych dziewiątek nazbierać dość sporo. Np. liczba pierwsza 89 dzieli dopiero ciąg złożony z 88 dziewiątek :P  Zawsze jednak da się znaleźć taki ciąg dziewiątek, który podzieli się przez daną liczbę pierwszą ;)
Udowodnienie tego faktu może być dość trudne, jeśli zaczniesz od końca (czyli tego, co pokazałem powyżej), oraz bardzo łatwe, gdy zaczniesz od zupełnie innej strony (tej, od której ja zacząłem, gdy go odkryłem). Jako bonus można też przy tej okazji odkryć twierdzenie Fermata o kongruencjach ;)


Przytoczony artykuł na Wikipedii jest jednak dość kiepski (jak zwykle), wygląda jak przetłumaczony z angielskiego na kolanie (np. słowo "indeks" zamiast "wykładnik" ,:) ).
Nie wspomina też o tym, że ten wzór na liczby doskonałe dotyczy jedynie parzystych liczb doskonałych (jako że jak dotąd nikomu nie udało się jeszcze znaleźć żadnej nieparzystej liczby doskonałej, ani metody na ich znajdowanie :czytaj: ).

Do tego podany tam dowód jest niekompletny, bo nie upewnia się, że czynniki wyniku są dzielnikami właściwymi. Bo jeśli nie są, lecz np. któryś z nich to 1, a ten drugi to pełna liczba wynikowa, to wynik nadal może być liczbą pierwszą :figielek:  A nam przecież chodziło o to, by udowodnić coś zgoła przeciwnego  ;)  (że gdy wykładnik był złożony, to wynik też musi być złożony).

Właśnie dlatego przy "zgłębianiu tematów" staram się jednak unikać Wikipedii, bo niezbyt dobrze się do tego nadaje ;J  Lepiej nadają się oryginalne publikacje odkrywców i stare zakurzone księgi :nauka:

I jest to dosc ciekawe, bo gdy zglebic temat doglebnie, to mnich mial i ma racje, ale maszyny liczace popelniaja bledy... :taaak

A z czym dokładnie miał rację w przeciwieństwie do tego, co później policzyły maszyny?
Sugerujesz, że wszystkie podane przez niego liczby były pierwsze? :q
Niestety nie były, i można się o tym przekonać samemu.

Mersenne twierdził (błędnie), że liczby w postaci 2p–1·(2p – 1) są pierwsze, gdy ich wykładnik p to kolejno:

2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257

jednak dwie z podanych przez niego liczb są złożone:

267 – 1  =  147573952589676412927  =  193707721 · 761838257287

2257 – 1  =  231584178474632390847141970017375815706539969331281128078915168015826259279871
          =  535006138814359 · 1155685395246619182673033 ·
                 374550598501810936581776630096313181393


o czym możesz przekonać się sama, bez maszyn, wymnażając te czynniki z powrotem do kupy, a potem sprawdzając, czy po dodaniu jedynki do wyniku otrzymałaś faktycznie potęgę dwójki (to z kolei można sprawdzić dzieląc liczbę w kółko na pół, aż zostanie tylko jedynka). (Tylko że bez pomocy maszyn pewnie zejdzie Ci na to trochę czasu ;))

Tak właśnie zrobił to Frank Nelson Cole, by pokazać zebranym na jego wykładzie, że liczba 267 – 1 jest złożona: najpierw obliczył z mozołem jej wartość i wypisał na tablicy: 147573952589676412927. Następnie obok napisał 761838257287, a pod spodem 193707721, po czym wymnażał je skrzętnie przez następne kilkanaście minut w całkowitym milczeniu. Gdy otrzymał wynik identyczny z tym, który obliczył wcześniej dla  267 – 1, wrócił na swoje miejsce, wśród owacji na stojąco wszystkich zgromadzonych na sali wykładowej ;) To było chyba najbardziej widowiskowe mnożenie w słupku w historii ;D i najbardziej pouczający wykład w historii podczas którego wykładający nie wypowiedział ani jedno słowa :-X


Oczywiście Twoje obawy co do tego, czy maszyny dobrze liczą, są słuszne. Dlatego trzeba zawsze najpierw upewnić się co do tego, testując algorytmy na mniejszych liczbach, oraz weryfikując wyniki, które otrzymaliśmy dla tych większych, innymi metodami. Ale gdy już zyskamy pewność, powierzenie tej mozolnej pracy maszynie, która zrobi to za nas szybciej i oszczędzi nasz czas, jest rozsądną decyzją ;J bo w tym czasie my możemy już zająć się odkrywaniem nowych rzeczy, by znów być o parę kroków do przodu przed maszynami ;)

Nic też nie zastąpi matematycznego dowodu, który często pozwala rozstrzygnąć daną kwestię bez konieczności "mielenia cyferek" ;) Ale do stworzenia takiego dowodu potrzebny jest już ludzki umysł zdolny do kreatywnego, abstrakcyjnego myślenia – coś, czego maszyny jeszcze długo nie będą potrafiły.


Wracając jednak do braciszka Mersenne'a: na jego liście brakuje jeszcze kilku liczb w tej postaci, które też są liczbami pierwszymi:

261  – 1  =                2305843009213693951
289  – 1  =        618970019642690137449562111
2107 – 1  =  162259276829213363391578010288127


Oczywiście co innego przeoczyć jakieś (mógł przecież nie wiedzieć, że istnieją), a co innego błędnie twierdzić, że któreś z nich są pierwsze :P:  Bo jeśli nie był tego pewny, nie powinien był publikować "fake newsa" ;)


OK, to na razie tyle. Następnym razem może napiszę co nieco o tym, jak udowodnić, że liczby w postaci opisanej przez Euklidesa faktycznie są parzystymi liczbami doskonałymi (bez konieczności wypisywania wszystkich ich dzielników i sumowania ich ręcznie), oraz jak wykazać, że wszystkie parzyste liczby doskonałe są opisane tym wzorem, bez wyjątków ;)
« Ostatnia zmiana: Sierpień 22, 2019, 08:54:23 wysłana przez SasQ »
Naukowy kącik kwantowy Saska:  http://nauka.mistu.info/  :-)
Ostatnio dodane artykuły: Splątanie kwantowe rozplątane

Offline Lady F

  • Zaawansowany użytkownik
  • ****
  • Wiadomości: 305
  • Merlin
    • Zobacz profil
Odp: 3. Podstawowe pojęcia
« Odpowiedź #73 dnia: Sierpień 22, 2019, 09:01:09 »
"Liczby Mersenne’aW Cogitata Physico-Mathematica (1644) Mersenne twierdzi, że jeśli p jestliczba pierwszą nie większą od 257, to liczba 2p–1 jest pierwsza wtw gdy p= 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257. Ostatnia z tych potęg ma 77 cyfr!Łatwo policzyć, że 211–1 nie jest pierwsza. Ale ostatnia z tych liczb ma 77 cyfr! Ostatecznie listę tych liczb zweryfikowano w 1947. Okazało się, że Mersenne pomylił się kilka razy: jego lista zawiera dwie potęgi, których nie może tam być (67, 257) i brakuje na niej trzech takich, które powinny tam wystąpić (61, 89, 107). Jednak liczby z tej poprawionej listy, a także dalsze liczby pierwsze otrzymane według tego wzoru, nazywamy liczbami pierwszymi Mersenne’a. Używa się ich w programach komputerowych zawierających testy pierwszości. Obecnie znamy 47 takich liczb. Ostatnia ma około 13 milionów cyfr."

zrodlo: http://zpgk.fais.uj.edu.pl/documents/2349539/68323986/MD5(Pierwsze).pdf

W poszukiwaniu materialow na temat tych liczb natknelam sie na ciekawe publikacje, ale obcojezyczne, wiec aby je tu zaprezentowac nalezaloby przetlumaczyc, ale w skrocie napisze tak, ze Marsenne nie pomylil sie, lecz ci, ktorzy przepisywali jego prace. Nie bylo wtedy kopiarek itp.

Offline SasQ

  • Collegium Invisible
  • Zaawansowany użytkownik
  • *
  • Wiadomości: 309
  • Płeć: Mężczyzna
  • Quanta rhei... :-)
    • Jabber/AQQ
    • Zobacz profil
    • Naukowy kącik kwantowy
    • Email
Odp: 3. Podstawowe pojęcia
« Odpowiedź #74 dnia: Sierpień 22, 2019, 09:33:39 »
Jeśli masz na myśli sugestie jego fanów, że 67 to błąd w druku, i miało być 61, to i tak nie ratuje mu to tyłka do końca, bo:
1. Mimo wszystko dwie liczby pominął.
2. Drugiej z błędnie podanych przez niego liczb nie da się już wyjaśnić błędem w druku (musiałby się pomylić w więcej niż jednej cyferce i nawet już nie podobnych graficznie).
3. Ten sam błąd z 67 i 257 został przez niego powtórzony w kolejnych jego publikacjach. Gdyby wiedział, że to błąd, na pewno skorygowałby go w kolejnych wydaniach, nie sądzisz? :->

Ale jeśli masz coś ciekawego na ten temat, to możesz mimo wszystko podrzucić linkami, chętnie poczytam. Mogą być obcojęzyczne, nawet jeśli ten obcy język to nie angielski ;)

Tak czy owak, nawet pomimo tych błędów, zasługi Mersenne'a w tym temacie i tak były spore, i jego lista była nie lada osiągnięciem, zważywszy na środki i metody obliczeniowe, jakie były dla niego dostępne w tamtych czasach. Łatwiej je docenić, gdy się samemu spróbuje sprawdzić, które z tych (dość dużych) liczb są liczbami pierwszymi, a które rozpadają się na jakieś czynniki, i znaleźć te czynniki. Nawet współczesne komputery mają z tym problemy już przy liczbach mających 100 i więcej cyfr.

Wyobraź sobie na przykład, że chcesz sprawdzić tę 267 – 1, która ma 21 cyfr dziesiętnych. Jak się do tego zabrać? Naiwnym podejściem musiałabyś przetestować 547932122 dzielników pierwszych, dla każdego z nich dzieląc w słupku :o  Do tego musiałabyś najpierw przygotować sobie tabelę liczb pierwszych od 1 do 50 miliardów! :pada śnieg: Coś na kształt tej, którą zrobiłem sobie kiedyś dla liczb od 1 do 10000:

http://mistu.info/Stuff/Ble/Factors.png
3. Podstawowe pojęcia

(Link bezpośredni do obrazka, bo coś ta forumowa lupka pomniejsza, zamiast powiększać :q )

tylko ta Twoja musiałaby mieć 5 milionów takich stron :help:
Oczywiste jest więc, że Mersenne nie mógł testować tego w taki sposób.
Znajomość sztuczki, jaką podzielił się z nim Fermat w liście z czerwca 1640 roku i kilku następnych, mogłaby mu to zadanie nieco ułatwić, odsiewając wiele z tych dzielników jako z góry nie pasujące. Ale to nadal za mało w przypadku tak dużych liczb.
« Ostatnia zmiana: Sierpień 22, 2019, 09:47:42 wysłana przez SasQ »
Naukowy kącik kwantowy Saska:  http://nauka.mistu.info/  :-)
Ostatnio dodane artykuły: Splątanie kwantowe rozplątane

Offline Leszek

  • Administrator
  • Ekspert
  • *****
  • Wiadomości: 1810
    • Status GG
    • Zobacz profil
    • swietageometria.info
    • Email
Odp: 3. Podstawowe pojęcia
« Odpowiedź #75 dnia: Sierpień 22, 2019, 19:22:27 »
(Link bezpośredni do obrazka, bo coś ta forumowa lupka pomniejsza, zamiast powiększać :q )[/center]
Aby tutaj nie spamować, napisałem o lupce w wątku o funkcjonalności forum

Offline Prazeodym

  • Użytkownik
  • **
  • Wiadomości: 20
    • Zobacz profil
    • Email
Odp: 3. Podstawowe pojęcia
« Odpowiedź #76 dnia: Sierpień 25, 2019, 12:04:02 »
Sasq z czego wynika fakt, że liczby doskonałe są sumą sześcianów kolejnych liczb nieparzystych? Pozostałe cechy liczb doskonałych były proste do uzasadnienia, ale na tym się zaciąłem.

Offline SasQ

  • Collegium Invisible
  • Zaawansowany użytkownik
  • *
  • Wiadomości: 309
  • Płeć: Mężczyzna
  • Quanta rhei... :-)
    • Jabber/AQQ
    • Zobacz profil
    • Naukowy kącik kwantowy
    • Email
Odp: 3. Podstawowe pojęcia
« Odpowiedź #77 dnia: Sierpień 25, 2019, 15:18:19 »
Tak na szybko:
Jeśli weźmiesz wzór na sumę sześcianów n kolejnych liczb nieparzystych:

n2 · (2·n2 – 1)

i jako n podstawisz w nim k-tą potęgę dwójki, czyli 2k, to otrzymasz:

(2k)2 · (2·(2k)2 – 1)
co z prawa wykładników daje:
22k · (2·22k – 1)
i ostatecznie:
22k · (22k+1 – 1)

Widzimy więc, że dostaliśmy iloczyn dwóch czynników:
1. Dwójki podniesionej do potęgi 2k, oraz...
2. Dwójki podniesionej do potęgi 2k+1 (następnej po tej z poprzedniego punktu), pomniejszonej na koniec o 1.
Brzmi znajomo? ;)
Możemy więc tę potęgę z punktu 1 zastąpić innym symbolem: m-1, a następną symbolem m (dwie kolejne liczby).
Otrzymamy wtedy znany wzór na parzystą liczbę doskonałą:

2m–1 · (2m – 1)
:)

Dlaczego podstawiłem akurat 2k?
Wynika to z obserwacji ile sześcianów kolejnych liczb nieparzystych trzeba było dodać, by dostać liczbę doskonałą: dla 28 były 2, dla 496 były 4, dla 8128 było ich 8, a dla 33550336 potrzeba ich 64, itd. Wszystkie te liczby były potęgami dwójki.

A skąd bierze się wzór na sumę sześcianów liczb nieparzystych? :->
To wyjaśnię innym razem, jak znajdę trochę więcej czasu. I może przy tej okazji omówię też inne podobne wzory na sumy kwadratów, sześcianów itp., bo mają ze sobą wiele wspólnego ;) (za to mniej wspólnego z samymi liczbami doskonałymi).
« Ostatnia zmiana: Sierpień 25, 2019, 15:32:15 wysłana przez SasQ »
Naukowy kącik kwantowy Saska:  http://nauka.mistu.info/  :-)
Ostatnio dodane artykuły: Splątanie kwantowe rozplątane

Offline Prazeodym

  • Użytkownik
  • **
  • Wiadomości: 20
    • Zobacz profil
    • Email
Odp: 3. Podstawowe pojęcia
« Odpowiedź #78 dnia: Sierpień 25, 2019, 19:22:22 »
Ok. Dzięki. Dowód na sumę tych sześcianów znalazłem tutaj. Swoją drogą bardzo ciekawy.
http://matematykadlastudenta.pl/strona/782.html  Na podstawie tego dowodu można wydedukować sposób wyprowadzenia tego wzoru? Kurcze chcą kasy łobuzy żeby mi to jeszcze raz pokazać, ale był to dowód indukcyjny, więc raczej z niego wzoru nie da rady wyprowadzić.... Hmmm.
« Ostatnia zmiana: Sierpień 25, 2019, 20:24:21 wysłana przez Prazeodym »