# Sequence of squares $\pi(x^2)$

Let $\pi(x)$ be the number of primes less than or equal to x.

Consider the composition $\pi(\pi(x))...,$ etc. What is the longest string of compositions that produces only squares?

My starting entry is not very long.

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

-

You can do this problem in reverse - starting from 1, build a tree with each node being a number $x$ that has exactly one out edge to the node for $\pi(x)$, creating a directed tree, with each path leading directly to the root.
Alternatively, you can do the following except only consider square numbers, and if $\pi(x)$ isn't square, count it as a node without any out-edges. This way, you create the forest without having to create all the non-square nodes, which is much more efficient (A total of $O(\sqrt{n})$ rather than $O(n)$ if you keep a precomputed table of primes up to $n$ that you want to calculate).
"Or what if there are arbitrarily long strings if we go "far enough" out?" Then this search could never come up with the longest one completely, and you'd have a sequence of numbers $a_n$ representing the smallest number that creates a string of length $n$. – Joe Z. Feb 1 '13 at 13:31
This algorithm, however, does find the longest string up to a number $n$. If you're looking for one globally, I can't help you. – Joe Z. Feb 1 '13 at 13:32