Generatory liczb pseudolosowych (PRNG: Pseudo-Random Number Generators) bywają lepsze lub gorsze. Wszystkie mają jedną wspólną cechę: są przewidywalne. Dlatego nie powinno się ich używać do poważnych zastosowań - tu zdecydowanie używamy TRNG (True Random Number Generators), które biorą dane do wyprodukowania kolejnej liczby z jakiegoś losowego procesu, na przykład z ruchów Browna czy z aktualnej pogody na świecie. Zaletą TRNG jest jego faktyczna losowość, a wadą - trudność w uzyskiwaniu dużej liczby losowych danych w krótkim czasie.
W większości przypadków PRNG produkują liczby "wystarczająco losowe" do naszych zastosowań, stąd też ich niemalejąca popularność w świecie komputerów. Można też stosować podejście hybrydowe: używamy do generowania danych PRNG, uzupełniając jego entropię za pomocą TRNG, dzięki czemu jest i szybko, i losowo.
Dziś przyjrzyjmy się bliżej pewnemu bardzo prymitywnemu generatorowi PRNG. Ten konkretny egzemplarz ma bardzo, ale to bardzo kiepską jakość (w sensie losowości), jednak ma też jedną zdecydowaną zaletę: jest wyjątkowo prosty w implementacji. Chodzi o generator oparty o kwadraty. A konkretnie:
Ustalamy sobie najpierw jak długie liczby chcemy generować. Załóżmy na potrzeby dzisiejszej zagadki, że czterocyfrowe.
Bierzemy dowolną liczbę czterocyfrową (skąd? nie wiem, z kapelusza), następnie podnosimy ją do kwadratu i odrzucamy cztery skrajne cyfry (tzn. dwie z lewej i dwie z prawej), pozostawiając cztery cyfry środkowe. Następnie operację powtarzamy. W ten sposób dostaniemy pseudolosowy ciąg liczb czterocyfrowych.
Oczywiście jest haczyk: a co jeżeli po podniesieniu do kwadratu dostaniemy liczbę krótszą niż 8 cyfr? To proste: uzupełniamy zerami od lewej strony tj. dopisujemy zera na początku - tyle ile trzeba, żeby dobić do 8 cyfr.
Przykład: zaczynamy od 1234, 12342=1522756, mamy tylko siedem cyfr więc dodajemy zero na początku, mamy 01522756, odrzucamy cztery skrajne cyfry (czyli 01 oraz 56), zostaje nam 5227. 52272=27321529, odrzucamy cztery skrajne (czyli 27 i 29), zostaje 3215. I tak dalej, i tak dalej.
W pewnym momencie - i jest to gwarantowane jak śmierć, podatki i grawitacja - wpadniemy w pętlę, bo różnych liczb czterocyfrowych jest 10000, więc nawet jeżeli okaże się jakimś cudem, że wygenerowaliśmy 10000 różnych wartości, zgodnie z zasadą szufladkową Dirichleta kolejna liczba musi się powtórzyć z którąś z poprzednio wygenerowanych.
Czas na zagadkę właściwą:
Od jakiej liczby czterocyfrowej należy zacząć, aby uzyskać sekwencję unikalnych liczb o maksymalnej długości? Ile wynosi ta długość?
Dla jasności:
- Długość sekwencji rozumiemy jako liczbę jej różnych elementów, a więc nie zliczamy elementu, który się powtórzył. Jeżeli liczby idą, przykładowo: 1, 2, 3, 4, 5, 3, 4, 5, 3, 4, 5..., to długość sekwencji wynosi 5, nie 6.
- Nie szukamy długości najdłuższej pętli. W przypadku powyżej liczby zapętlają się na 3, 4, 5, 3, 4, 5... więc pętla ma długość 3, ale całkiem nas to nie interesuje.
A więc Python w dłoń (czy co tam kto lubi) i szukamy odpowiedzi.
Rozwiązanie zagadki tutaj.