Soluţia problemei Nambartiori
Notăm cu cel mai mic divizor comun dintre şi . şi au semnificaţia din enunţ.
Cazul cu o sa îl tratăm separat. Se observă că orice două numere naturale şi cu formează o progresie geometrică validă, deoarece . Deci numărul de progresii geometrice care încep cu un număr este chiar .
Fie numărul de progresii geometrice de lungime care încep cu un număr mai mic sau egal decât şi au raţia între şi . Conform observaţiei de mai sus . Putem afla prima poziţie din progresia geometrică cu o căutare binară în sau cu o parcurgere simplă în . Mai departe este foarte simplu să aflăm care este progresia cerută.
Fie primul termen al unei progresii. Putem scrie raţia unei progresii ca , unde şi sunt numere naturale prime între ele astfel încât .
Avem . Cum
În loc de a afla numărul de fracţii putem afla numărul de fracţii de forma , cu si , pentru că sunt echivalente conform demonstraţiei de mai sus.
Dacă vrem ca progresia să aibă termeni, atunci ne interesează fracţiile pentru care numărul este număr natural. Cum , proprietatea anterioară este echivalentă cu .
Rămâne să numărăm câte fracţii există. Pentru un valid, poate lua valori doar numere mai mici sau egale cu astfel încât , deci numarul de fracţii este (Indicatorul lui Euler).
Fie numărul de progresii geometrice de lungime care încep cu şi au raţia mai mare strict decât şi mai mică sau egală cu . Conform observaţiei de mai sus , unde .
Fie numărul de progresii geometrice de lungime care încep cu un număr mai mic sau egal decât şi au raţia între şi . Aşadar . Dacă extindem suma obţinem , unde . Putem calcula suma rapid dacă aflăm pentru fiecare de câte ori apare în sumă. poate lua valori până la , iar apare de ori în sumă. Deci putem calcula în . Căutăm binar prima valoare din progresie. Fie aceasta . Fie cel mai mare numar astfel încât . Observăm că poate fi scris ca , dar această sumă este egală cu deoarece . Fie fracţiile . Numărul acestora este , ele fiind distincte două câte două, iar pentru că este natural, înseamnă că progresiile geometrice valide care încep cu p sunt doar cele care au raţiile egale cu . Pe noi ne interesează progresie geometrică care începe cu , unde . Conform observaţiilor anterioare aceasta este . Complexitatea finală pentru a afla progresie geometrică de lungime este .