Wszyscy znamy zagadkę z drabinką liter: Żeby przejść od KOT do WAR możemy zrobić na przykład tak: KOT->KAT->WAT->WAR. W każdym kroku zamieniamy jedną literę na inną, zawsze tak, żeby uzyskane litery tworzyły poprawne słowo.
A co jeżeli słowa zamienimy na liczby pierwsze?
Okazuje się, że tu też są takie drabinki. Na przykład żeby przejść z 23 do 31 możemy zrobić to w ten sposób: 23->13->11->31. Czytelnikowi pozostawiam do sprawdzenia, że jest to para dwucyfrowych liczb pierwszych z najdłuższą minimalną drabinką (choć są też inne takie pary, na przykład 97->53).
Minimalna drabinka to najkrótsza liczba kroków wymaganych do przekształcenia jednej liczby w drugą (spełniając zasady drabinki a więc zawsze zamieniamy dokładnie jedną cyfrę na inną, a każda liczba pośrednia musi też być liczbą pierwszą). Dla różnych par liczb dwucyfrowych długości tych minimalnych drabinek będą różne. Na przykład dla 13, 37 minimalna drabinka ma trzy elementy: 13->17->37 (są też ine trzyelementowe). Krócej się nie da. A dla 23->31 minimalna drabinka ma cztery elementy - i wśród liczb pierwszych dwucyfrowych nie da się znaleźć pary z dłuższą (na przykład pięcioelementową) minimalną drabinką. Jest to więc najdłuższa minimalna drabinka.
Czas na zagadkę właściwą: ile elementów ma najdłuższa minimalna drabinka dla liczb pierwszych trzycyfrowych? Proszę podać przykładowe liczby z takiej drabinki.
Pytanie bonusowe: a dla czterocyfrowych?
Rozwiązanie zagadki tutaj.