Odkurzone, wygrzebane

Czasem zakopane w starych czasopismach, pożółkłych książkach czy innych tego typu zapomninych miejscach do których nikt nie zagląda leżą ciekawe, potencjalnie pożyteczne i eleganckie perełki. Bywa, że odkrywane po wielokroć na nowo stają się elementem folkloru i nikt w zasadzie już nie pamięta kiedy, jak i po co je odkryto po raz pierwszy.
Postanowiłem od czasu do czasu, kiedy natknę się na coś godnego uwagi zanotować to w tym blogu - żeby nacieszyć oko odkurzonym drobiażdżkiem i licząc, że może komuś się przyda...

Dziś następujący problem:
Niech A będzie nieskończonym podzbiorem zbioru liczb naturalnych N (bez 0 dla uniknięcia niepotrzebnych subtelności w rozważaniach o indeksach). Załóżmy, że mamy daną fukcję, COUNT: N->N która dla liczby naturlanej n daje informację ile liczb w zbiorze A jest mniejszych bądź równych n:
COUNT(n) = #{x \in A | x <= n}
poszukujemy algorytmu pozwalającego dla zadanej liczby m wyznaczyć m-ty element zbioru A.

Rozwiązanie jest następujące (użyję c-podobnego pseudokodu):

ORD(m)
{
retval = m;
x = COUNT(retval);
while(x != m)
{
retval += (m - x);
x = COUNT(retval);
}
return retval;
}

miłośnikom dobrej zabawy polecam udowodnienie poprawności algorytmu używając indukcji matematycznej.
"Intuicjonistom", którzy lubią czuć skąd się wziął pomysł, może spodoba się następujące rozumowanie:
Pierwszy strzał to najmniejsza liczba dla której fukcja COUNT ma w ogóle szansę równać się m czyli po prostu m.
Trafiony - świetnie, szukaną liczbą jest właśnie m. Jeżeli nie trafiony, to znaczy, że COUNT(m) < m. Kolejną najmniejszą liczbą m_2 dla której możliwe będzie, że COUNT(m_2)=m jest oczywiście liczba większa od m o tyle ile COUNT(m) zabrakło do m czyli (m-COUNT(m)). Zatem następny strzał to m_2=m+(m-COUNT(m)).
Sprawdzamy więc ile wynosi COUNT(m_2). Jeżeli m to mamy swoją liczbę. Jeżeli nie, to powtarzamy "strzelanie" opierając się na tym samym rozumowaniu i dostajemy m_3 = m_2+(m-COUNT(m_2)) itd. Aż do - murowanego - skutku (pamiętamy - A jest nieskończone!).