Pchełki Python: za ciosem

Niedawno opublikowałem pchełkę rozwiązującą prościutkie, acz względnie interesujące zadanie matematyczne: ile potęg dwójki należy wygenerować, aby w zestawie wyników dostać każdą cyfrę od 0 do 9 przynajmniej raz?

Chwilę potem zadumałem się: a co, gdyby zamiast dwójki wziąć trójkę? albo piątkę?

Efektem owej zadumy jest kolejna pchełka, którą dziś prezentuję. Jest to rozwinięcie pchełki z zeszłego razu, rozwiązujące zagadkę nie tylko dla dwójki, ale dla wszystkich liczb całkowitych 2-9.

Kod jest całkiem podobny do tego, co ostatnio, tylko opakowałem całość w zewnętrzną pętelkę i dodałem bardziej szczegółowe informacje na wyjściu.

Wygląda to, o tak:

podstawa = 2
print("podstawa,krok,ostatnia")
while podstawa < 10:
    cyfry = set('023456789')
    liczba = 1
    krok = 1
    while cyfry:
        liczba *= podstawa
        krok += 1
        cyfry -= set(str(liczba))
    output=str(podstawa)+','+str(krok)+','+str(liczba)
    print (output)
    podstawa+=1

W wyniku dostajemy:

podstawa,krok,ostatnia
2,16,32768
3,11,59049
4,11,1048576
5,12,48828125
6,13,2176782336
7,8,823543
8,6,32768
9,7,531441

Jak widać najmniej kroków, bo tylko sześć, potrzebujemy podnosząc do kolejnych potęg ósemkę.

Najwięcej, bo aż piętnaście kroków, trzeba zrobić, zaczynając od dwójki.

Ogólna tendencja jest taka, że czym większa podstawa, tym mniej kroków. Wynika to z tego, że kolejne potęgi przyrastają dużo szybciej przy większych podstawach, a więc mamy więcej cyfr do dyspozycji. Spróbujmy tę właściwość zweryfikować dla większych podstaw, na przykład 11-19:

11,8,19487171
12,7,2985984
13,7,4826809
14,8,105413504
15,10,38443359375
16,6,1048576
17,8,410338673
18,5,104976
19,6,2476099

i jeszcze 21-29:

21,9,37822859361
22,7,113379904
23,7,148035889
24,7,191102976
25,9,152587890625
26,7,308915776
27,6,14348907
28,6,17210368
29,8,17249876309

Tu, jak widać, proces się ustabilizował – wszystkie cyfry dostajemy na ogół po 6-9 krokach. Zróbmy jeszcze jedno wariactwo i sprawdźmy, jak to wygląda dla dużo większych podstaw. Na przykład 1201-1209:

1201,6,2498705294406001
1202,5,2087458598416
1203,6,2519579909286243
1204,5,2101386547456
1205,5,2108376600625
1206,4,1754049816
1207,4,1758416743
1208,6,2572377317408768
1209,5,2136511345761

Udało się zejść do czterech kroków. A gdyby tak pójść jeszcze ze dwa rzędy wielkości w górę? Sprawdźmy, na przykład dla podstaw z zakresu 653821-653829

653821,3,427481900041
653822,4,279497925814368248
653823,4,279499208265952767
653824,4,279500490721460224
653825,4,279501773180890625
653826,4,279503055644243976
653827,4,279504338111520283
653828,3,427491053584
653829,4,279506903057841789

Tu mamy kilka przypadków, kiedy udało się uzyskać komplet cyfr w trzech krokach. Prawdopodobnie dałoby się wykonać bardziej systematyczne badanie i poznajdować najmniejsze podstawy dla każdej ilości prób, ale mi się już nie chce. I tak przydatność tej pchełki jest zerowa.

Na deser dodam jeszcze, że przygotowując dzisiejszą pchełkę oczywiście omyłkowo udało mi się wcisnąć dziesiątkę w test. Efekt jest łatwy do przewidzenia – ponieważ dowolna potęga całkowita dziesiątki składa się wyłącznie z jedynki oraz mnóstwa zer, nawet po wykonaniu nieskończenie wielkiej ilości kroków nie uzyskamy pożądanego wyniku. Aczkolwiek…

Przywykły do programowania w VBA wiem, że takie eksperymenty kończą się komunikatem o błędzie zakresu (innymi słowy, próbujemy do zmiennej typu 32-bitowego przypisać wartość 33-bitową) – tutaj jednak zostałem przez Pythona bardzo, bardzo pozytywnie zaskoczony. Zobaczmy na bardzo prostym przykładzie:

n=10
while 1:
    n*=10
    print(n)

Kto zgadnie jaki jest efekt uruchomienia tego kodu?

Efekt jest taki, że po chwili wypisywania coraz to dłuższych liczb na ekran, środowisko IDE wyrzuca komunikat: „Too much output to process”, i przestaje wyświetlać kolejne liczby – ale program działa dalej! Dopiero po mniej więcej minucie całe środowisko się wysypuje, z błędem przepełnienia pamięci.

A więc wniosek z tego jest taki, że w Pythonie nie jesteśmy ograniczeni do nędznych 32 czy nawet 64 bitów, ale możemy sobie liczyć na dowolnie wielkich liczbach, o ile tylko nie zabraknie nam pamięci.

zeroes

Spróbujmy jeszcze – dla zgrywy – przemnożyć przez siebie dwie ogromne liczby:

print (324985792384765982736495832746589234765983274569328475*987632498576324856234523469563246568324651230841287038415723987)

Efekt:

20966530134773194749883202245249807003658760469678936117678703565888696911501628774041939230938907261083991539629825

Sprawdźmy jeszcze, czy wynik jest poprawny. W tym celu wchodzimy na:

http://www.wolframalpha.com/input/?i=324985792384765982736495832746589234765983274569328475*987632498576324856234523469563246568324651230841287038415723987

Wynik:

bignums

Faktycznie, cholera, zgadza się.

Bardzo fajny ten cały Python jest. Bez dwóch zdań.

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz