Płonący statek

Dzisiaj koniec serii nt. różnych fraktali. Skończymy w płomieniach.

Ponad 2 lata temu na kursie asemblera na PWr mieliśmy za zadanie napisać program w dowolnym języku wysokiego poziomu wykorzystując przy tym zarówno wstawki asemblerowe jak i wywołania procedur napisanych w czystym asemblerze, dołączanych jako pliki .OBJ. Dodatkowo w ramach ćwiczenia trzeba było wykorzystać koprocesor numeryczny. Mój wybór na Pascala z racji młodzieńczych sentymentów. A czy jest coś fajniejszego i prostszego do napisania na koprocesor niż fraktale i tryb 13h? Raczej nie ;)

W początkowej wersji program obsługiwał tylko zbiory Julii, wczoraj i dzisiaj dopisałem zbiór Mandelbrota oraz bardzo ciekawy fraktal, "Płonący statek".

Kostka Rubika rozwiązana!

9 sierpnia tego roku ostatecznie ustalono - dowolnie pomieszaną kostkę Rubika można ułożyć wykonując tylko 20 (lub mniej) ruchów.

Jest to zaskakujące, jeżeli weźmie się pod uwagę liczbę możliwych ustawień oryginalnej kostki Rubika. Składa się ona z 8 narożników (kosteczek narożnych) i 12 krawędzi (kosteczek na krawędziach). Narożniki można ustawić na 8! (40 320) sposobów. Dodatkowo kosteczki te mogą różnić się orientacją (sposobem obrócenia) - to daje nam 3⁷ możliwości (przyjmujemy, że np. jedna z kosteczek jest ustawiona białą powierzchnią do góry, to każdą z pozostałych 7 kosteczek można obrócić na 3 sposoby).

Krawędzie można ustawić na 12!/2 sposobów (239 500 800) - dzielimy przez 2, bo permutacja krawędzi zależy od permutacji narożników - muszą one mieć tą samą parzystość (http://en.wikipedia.org/wiki/Parity_of_a_permutation). A każdą z 12 kosteczek na krawędziach można zorientować na 2 sposoby, co przy przyjęciu jednej z nich za "orientującą" całą kostkę daje nam 2¹¹ (2 048) możliwości.

Razem:

8! * 3⁷ * 12!/2 * 2¹¹ = 43,25 * 10¹⁸

Zadziwiające, że tylko w 20 ruchów można z każdej z tych pozycji dojść do pozycji wyjściowej.

Tablica Wythoffa

Czyli macierz powstała z ciągu Fibonacciego, która ma wiele ciekawych właściwości.

Wygląda ona tak:

Konstruowana jest w następujący sposób:
1. Pierwsza kolumna to kolejne nieujemne liczby całkowite: 0, 1, 2, 3...

2. Druga kolumna to dolna sekwencja Wythoffa (http://www.research.att.com/~njas/sequences/A000201), której n-ty element jest równy części całkowitej z (n+1)*φ
gdzie φ to złoty podział (1,61803399...), który jak wiadomo pojawia się też w ciągu Fibonacciego ;)

3. Mając pierwsze dwie kolumny wiersze konstruujemy podobnie do ciągu Fibonacciego - każda kolejna kolumna to suma dwóch poprzednich.

OK, to jakie są ciekawe właściwości tablicy Wythoffa?

Mandelbox

Dzisiaj kolejny bardzo ładny fraktal, tym razem trójwymiarowy. Uwaga, to świeży wynalazek, z 2010 roku ;)

Mandelbox został zaproponowany na jednym z forów poświęconych fraktalom w lutym tego roku przez Toma Lowe. Jego nieskomplikowana formuła (kilkanaście linii pseudo-kodu) tworzy niesamowite, katedro-podobne obrazy. Na przykład:

A to nic w porównaniu do podróży w głąb tej trójwymiarowej konstrukcji.

Hipoteza Collatza

Dzisiaj kolejny z pozoru prosty problem matematyczny, który jeszcze nie znalazł rozwiązania. A prace nad Hipotezą Collatza trwają już ponad 70 lat.

Weźmy dowolną liczbę naturalną c₀. Jest to pierwszy wyraz ciągu określonego rekurencyjnie jako:

                c_n / 2 dla c_n parzystego
c_{n + 1} =
                3 * c_n + 1 dla c_n nieparzystego

Czyli dostaniemy następujące ciągi, w zależności od wyrazu początkowego:

1 → 4 → 2 → 1 → 4 → 2 → 1 → ...
2 → 1 → 4 → 1 → ...
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → ...
4 → 2 → 1 → ...
5 → 16 → 8 → 4 → 2 → 1 → ...
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → ...

Zazwyczaj jako ostatni wyraz ciągu przyjmuje się jedynkę, ponieważ potem wpada on w pętlę ;) Liczbę elementów poprzedzających jedynkę określa się czasem stopu dla danej wartości pierwszego wyrazu ciągu.

Co zatem tutaj tak ciekawego?

Buddhabrot

Każdy chyba zna taki fraktal jak zbiór Mandelbrota. W 1993 został znaleziony inny fraktalo-podobny obraz, o wiele moim zdaniem ładniejszy ;)

Zbiór Mandelbrota to zbiór takich liczb zespolonych c, że ciąg z_n definiowany jako
 z₀ = 0
 z_n+1 = (z_n)² + c
nie dąży do nieskończoności przy n -> ∞.

W rzeczywistych rozwiązaniach sprawdza się, czy w określonej liczbie iteracji (np. 1000) ciąg ten nie wykroczy poza okrąg o środku w punkcie (0, 0) i promieniu równym 2 - jeżeli kolejna liczba zespolona w ciągu ma moduł większy niż 2, to wiadomo już, że na pewno dla tej wartości c ciąg z_n dąży do nieskończoności

Kiedy liczby c przedstawimy na płaszczyźnie zespolonej dostaniemy taki oto, znajomy obrazek:

W 1993 pani Melinda Green zadała sobie pytanie:
A co się dzieje z ciągiem z_n, kiedy dąży on do nieskończoności? Jaką ścieżkę przebywa zanim "wyskoczy" na odległość większa niż 2 od środka płaszczyzny?

Odpowiedź jest niezwykle ładna.

Liczby otwarto-meandryczne

Rzeka ma źródło na południowym-zachodzie i wpływa do morza na wschodzie. Z zachodu na wschód jest też droga, na której jest n mostów nad rzeką. Na ile możliwych sposobów może ta rzeka przecinać drogę?

Rozwiązanie tego problemu w zależności od n tworzy ciąg tzw. liczb otwarto-meandrycznych (open meandric numbers) - oznaczany m_i. Meandryczne - oczywiście od meandrów rzeki, natomiast otwartość bierze się z faktu, iż rzeka to krzywa otwarta. Liczby meandryczne dotyczą krzywych zamkniętych - pytanie jak taka rzeka płynie ;)

Spróbujmy znaleźć parę początkowych liczb otwarto-meandrycznych.

Pierwiastek sześcienny na zwykłym kalkulatorze

Na maturze z matematyki można mieć kalkulator - ale "zwykły". Czyli najbardziej wyszukana operacja na nim dostępna to pierwiastek kwadratowy :P

Ale jest możliwość wyliczenia na standardowym kalkulatorze pierwiastka trzeciego stopnia (gdyby ktoś potrzebował). Algorytm jest prosty i nie wymaga żadnej kartki papieru czy innego rodzaju pamięci ;)

Sztuka szacowania

Projektant i programista powinien potrafić szacować różne wielkości. Warto się w tym ćwiczyć.

Chodzi zazwyczaj o znalezienie odpowiedzi na podstawowe pytania - "ile pamięci dyskowej potrzebujemy?", "o ile rekordów rocznie będzie się powiększać baza danych?" czy w końcu "dla jak dużych danych można powiedzieć, że działa to zbyt wolno?". Co ciekawe, szacowanie tych wielkości nie różni się wcale od szacowania innych wielkości fizycznych, a to można trenować, bawiąc się przy tym geekowsko ;) Na początek 3 zadania:

1. Ile sekund trwają szkolne wakacje?
2. Ile boisk piłkarskich (na długość) jest od Ziemi na Księżyc?
3. Ile piłek tenisowych zmieści się w Twoim pokoju?

Odpowiedzcie na początku nie wykonując żadnych obliczeń, potem zastanawiając się nad każdym pytaniem 1 minutę, a potem kliknijcie więcej, bo to policzymy (i gratis poznacie moje strzały) ;)

Początki najdziwniejszej encyklopedii

Chodzi o Encyklopedię Ciągów Liczb Całkowitych, którą w latach 60-tych zaczął tworzyć Neil Sloane, brytyjski matematyk.

Encyklopedia, jak sama nazwa wskazuje, jest kolekcją ciągów liczb całkowitych - np. wpis dla liczb Lucasa: http://www.research.att.com/~njas/sequences/A000032

Ale jak ktoś wpadł na taki dziwny pomysł, jak zbieranie ciągów liczb?

Liczby prawie całkowite

Weź do ręki swój kalkulator i wpisz

sin 11

Wynik bardzo bliski -1, prawda? ;) Wynika to z tego, iż π ≈ 22/7.
O dziwo takich liczb "prawie całkowitych" jest o wiele więcej.