Eldönthető-e polinomidőben, hogy ez a Q* -> N algoritmus megáll-e?

#8-9-es, picit csalásnak érzem, amit csinálsz, de elfogadom válasznak. Megy a zöld kéz. :)

Ha jól értem, arról van szó, hogy az 1/9-et (0.111...) akarod közelíteni egy hozzá közel eső prím gyökével, és rájöttél, hogy 1/9 négyzete, 1/81 könnyedén előállítható a fent leírt módon, vetted a hozzá legközelebb eső prímet, és gyököt vontál. Mivel nagy számmal volt felszorozva és kicsit vontál le belőle, így hosszú szakaszon csupa 1-est kaptál, aztán jött az irracionális rész.

De megmondom mi a baj ezzel: az inputod mérete túl nagy az output méretéhez képest. Túlon túl nagy.

Egy másik érdekes probléma felvetése. Az emlegetett Q* -> N függvényünk legyen f(x), és legyen g : N -> N függvény a következő: g(n) = f(sqrt(n)). A g függvény ismételt alkalmazásával újabb és újabb számokat kapunk. Az érdekes része a dolognak, hogy bizonyos esetekben egész kicsi köröket kapunk. Tekinthetjük gráfnak is az így kapott konstrukciót.

Példa:

5-ből, 7-ből és 12-ből el lehet jutni 2-be, onnan pedig 1-be.

7-be el lehet jutni 57-ből is.

59-ből, 19-ből és 48-ból el lehet jutni 21-be, onnan pedig 1-be.

156-ból 34-be, 34-ből 6-ba, 6-ból 1-be. De 81-ből 3-ba, és 3-ból, 9-ből és 11-ből szintén 6-ba.

A kakukktojás:

13-ból 367326277, 367326277-ből 182407613-ba, és 182407613-ból vissza 13-ba. (közvetlen utak)

Nagyon kíváncsi lennék, hogy hogy nézne ki egy nagy gráf, ami ezeket az utakat mutatja.

Bónusz kérdés: hány független részből áll ez a végtelen gráf?