7
$\begingroup$

Let $f(n)$ denote the sum of the squares of the prime factors of $n$ with multiplicity.

For example, $f(60)=f(2\cdot2\cdot3\cdot5)=2^2+2^2+3^2+5^2=42$.

Denote the iterated function $f^k(n)=\underbrace{f(f(\dots(n)))}_{k\text{ times}}$.

For example, $f^2(60)=f(f(60))=f(42)=2^2+3^2+7^2=62$.


I want to know if there exists $k$ such that $f^k(30)$ is either prime or equal to $30$.

Is there a way to answer this question without applying a full "brute-force" search?

My goal is to be able to answer this question in general (for values other than $30$).

Side note: I do not know any cases where $f^k(n)=n$, other than $n=16$ and $n=27$.

$\endgroup$
  • $\begingroup$ I think it is possible to show that $\frac{2\ln n}{\ln 2}< f(n)\leq n^2.$ Then for example we need look no farther than $n = 50000$ to find $f(n) = 30.$ Not very useful. $\endgroup$ – daniel Jan 21 '15 at 19:23
  • $\begingroup$ @daniel: Finding $n$ such that $f(n)=30$ is easy, since $30=4+4+4+9+9=2^2+2^2+2^2+3^2+3^2$. So $n=2\cdot2\cdot2\cdot3\cdot3=72$. But I am actually looking for $k$ such that $f^k(30)=30$, and for that purpose, $n$ can grow to any value during the "cycle" (if a "cycle" happens to exist). $\endgroup$ – barak manos Jan 21 '15 at 19:36
  • $\begingroup$ @daniel: So do you think that once $f^k(30)>50000$, we can assume that it will never reach back to $30$? $\endgroup$ – barak manos Jan 21 '15 at 20:01
  • $\begingroup$ Actually that last one is tricky. Not sure I agree. What I would say is that if $n$ is sufficiently large (50K or so) f(n) will be greater than 30. This lemma if true only deals with first iterates. So suppose $n = 50000.$ Then $f(n)$ will be greater than 30. Suppose $f(n)$ is much less than 50000. Then I think $f(f(n)$ might be less than 30. $\endgroup$ – daniel Jan 21 '15 at 20:14
  • $\begingroup$ @daniel: Since $f^k$ is not monotonically increasing by $k$, proving (for example) that $f(50000)>30$ doesn't really help in answering the question in general (i.e., "in terms of $k$"). Thank you for your effort and observation. $\endgroup$ – barak manos Jan 21 '15 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.