A property of v

Question

Let $n$ be a natural number. Denote by $v(n)$ the sum of the numbers appearing in the canonical factorization of $n$ (like in A curious property of integers). Then I believe that for $n>1$ the sequence

$ n, v(n), v(v(n)), v(v(v(n))),\ldots $

is eventually the same prime number. Was this stated anywhere?

Answer 1

Yes, this observation was already made in http://oeis.org/A008474 , but no proof was attached to this.

Answer 2

I guess you can show that $\forall n \in \mathbb N: n \geq v(n)$ by recurrence. Obviously, $\mathbb N$ is well-ordered, so the sequence $k \mapsto v^k(n)$ must eventually reach a minimal value.

For the recurrence, the base case is $n = 1$ and $v(n) = 0$. Then, let $n = p \cdot m$ for some prime $p$ and assume we already proved the result $m \geq v(m)$. Thus, $$v(n) = p + v(m) \leq 2 \cdot \max\{p,v(m)\} \leq p \cdot v(m) \leq p \cdot m = n.$$

Addendum: I did not understand you required the sequence to converge to a prime number. Here is a proof you can have equality in the above equation only if $n < 5$ or $n$ is prime. If this is the case, the only values where it is possible to converge to are primes and $4$.

That is, let's prove the inequality is strong (i.e. we have $v(n) < n$) when $n > 5$ and $n$ is not a prime. Let again $n = p \cdot m$ for a prime p and $m > 1$. First observe that if $v(m) = 2$, then $m$ must be $2$ because any other summation of primes would give a result greater than $2$ through $v$. Let now go over the result, case by case.

If $p = 2$, then $m\geq3$ or else we would have $n < 5$. hus $m \geq 3$ implies $v(m) \geq 3$. So we have $$ v(n) = 2 + v(m) < v(m) + v(m) = 2 \cdot v(m) = n$$

If $p \ne 2$ and $m = 2$, then $v(m) = 2$ and $$v(n) = p + 2 < 2 \cdot p = n.$$

If $p \ne 2$ and $m \ne 2$, then $2 < \min\{p,v(m)\}$ and we obtain \begin{align} v(n) &= p + v(m) \leq 2 \cdot \max\{p,v(m)\} < \min\{p,v(m)\} \cdot \max\{p,v(m)\} \\ &= p \cdot v(m) \leq p \cdot m = n. \end{align}

Finally note that the only possible $n$ such that $v(n) = 4$ is $n = 4$, because $v(2) = 2$, $v(3) = 3$, and any other summation of primes will give a result greater than $4$.

Answer 3

It is only true for $n \ge 5$ as the iteration reaches $4$ for starting values of $2,3,4$ and gets stuck at $4$. Given the cited computer check we can use strong induction. The only $n$ for which $v(n) \gt n$ are primes, then $v(v(n))=2+\frac {n+1}2$ or less. We then have to show we never get less than $5$, but the only $n$ for which $v(n) \lt 5$ are less than $5$ themselves.