Secuencia de casillas $\pi(x^2)$

Question

Dejemos que $\pi(x)$ sea el número de primos menores o iguales a x.

Considere la composición $\pi(\pi(x))...,$ etc. ¿Cuál es la cadena más larga de composiciones que sólo produce cuadrados?

Mi entrada inicial no es muy larga.

$\pi(100) = 25,~ \pi(25) = 9,~ \pi(9) = 4.$

Answer 1

Puedes hacer este problema a la inversa: empezando por el 1, construye un árbol en el que cada nodo sea un número $x$ que tiene exactamente una arista de salida hacia el nodo para $\pi(x)$ creando un árbol dirigido, en el que cada camino lleva directamente a la raíz.

A continuación, marca los números cuadrados, elimina todos los nodos que no estén marcados y encuentra el camino más largo que te queda.

Alternativamente, se puede hacer lo siguiente, excepto que sólo se consideran los números cuadrados, y si $\pi(x)$ no es cuadrado, cuéntalo como un nodo sin bordes exteriores. De esta manera, se crea el bosque sin tener que crear todos los nodos no cuadrados, lo que es mucho más eficiente (Un total de $O(\sqrt{n})$ en lugar de $O(n)$ si se mantiene una tabla precalculada de primos hasta $n$ que se quiere calcular).