# 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.$

-

## 1 Answer

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.

Then, mark off the square numbers, delete all nodes that aren't marked, and find the longest path you have left.

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).

-
This is helpful if we know there is a longest string and we expect to find it in a short finite search. What if the one given is the longest? Or what if there are arbitrarily long strings if we go "far enough" out? – daniel Feb 1 '13 at 3:56
"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
I think your answer is helpful for looking at the problem. Before posting I found 14 2-strings less than 300,000. So for small numbers there isn't much. – daniel Feb 1 '13 at 13:56