Liczby trunkowe

2 września 2010
Marek Penszko

Postanowiłem uogólnić owczo-baranie zadanie z poprzedniego wpisu. Pozostanę zatem jeszcze chwilę wśród łamigłówek algorytmicznych, czyli takich, których gruntowne rozgryzienie bez komputera jest praktycznie niemożliwe lub bardzo żmudne. Ciekawa, obszerna i stale rosnąca kolekcja takich problemów i problemików, najczęściej obliczeniowych, dostępna jest na Project Euler. To strona należąca do najpopularniejszych wśród adeptów programowania, traktowana jako zbiór znakomitych ćwiczeń. Niektóre z zamieszczonych na niej zadań można jednak i warto nadgryzać bez komputera. Możliwa do napoczęcia „na piechotę” jest również poniższa łamigłówka, wzorowana na owczo-baraniej.

Dany jest iloczyn liczb naturalnych:
a * b = c
a to liczba n-cyfrowa,
b to najmniejsza – dla danego a – taka liczba, że c składa się z jednakowych cyfr.
Proszę znaleźć największe b dla danego n. Inaczej mówiąc, należy wybrać największy mnożnik spośród najmniejszych znalezionych dla wszystkich n-cyfrowych a, gdy n jest ściśle określone.

Oczywiście, nie dla każdej mnożnej istnieje taki mnożnik, aby iloczyn składał się z jednakowych cyfr. Najłatwiej zauważyć, że odpadają mnożne zakończone zerem.

Dla n = 1 sprawa jest trywialna: b = 1 dla każdego a.
Dla n = 2 można pogłówkować bez programowania, ale przyda się kalkulator.
Na starcie wypada wykreślić wszystkie a złożone z dwóch jednakowych cyfr, bo dla nich b = 1. Odpadnie też sporo takich, które dla żadnego całkowitego b nie dadzą c – poza zakończonymi zerem będą to na przykład niektóre liczby pierwsze oraz zakończone piątką. Być może właśnie wśród nich – ale tych, które nie odpadną – ukrywa się największe b. Sprawdzając na przykład liczby 2-cyfrowe z piątką z prawej strony szybko wpada się na duże b = 15873 dla a = 35 (35 * 15873 = 555555).
Czy wśród pozostałych dwucyfrowych liczb ukrywa się a z większym b? Pytanie jest „prowokacyjne”, bo nietrudno ustalić, że tak. W ogóle, wydaje się, że znalezienie największego b dla n = 2 nie wymaga korzystania z komputera, tzn. można wpaść na pomysł gwarantujący umiarkowanie wyboistą drogę do celu. A jakie są rozwiązania dla większych n? To już jest pytanie do programistów.

Liczba złożona z jednakowych cyfr określana jest w niektórych językach z angielska – repdigit. Dla odmiany nazwa niemiecka pachnie alkoholem 🙂 – schnapszahl (zagadka: dlaczego?). Propozycje polskiego określenia, niekoniecznie trunkowe, będą mile widziane.

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.