Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.