# Prime factorization “demoted” leads to function whose fixed points are primes?

Let $n$ be a natural number whose prime factorization is $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \; .$$ Define a function $g(n)$ as follows $$g(n)=\sum_{i=1}^{k}p_i {\alpha_i} \,$$ i.e., exponentiation is "demoted" to multiplication, and multiplication is demoted to addition. For example: $n=20=2^2 5^1$, $f(n) = 2\cdot 2 + 5\cdot 1 = 9$.

Define $f(n)$ to repeat $g(n)$ until a cycle is reached. For example: $n=154=2^1 7^1 11^1$, $g(n)=20$, $g^2(n)=g(20)=9$, $g^3(n)=g(9)=6$, $g^4(n)=g(6)=5$, and now $g^k(n)=5$ for $k \ge 4$. So $f(154)=5$.

It is clear that every prime is a fixed point of $f(\;)$. I believe that $n=4$ is the only composite fixed point of $f(\;)$.

Q1. Is it the case that $4$ is the only composite fixed point of $f(\;)$, and that there are no cycles of length greater than $1$? (Yes: See EmilJeřábek's comment.)

Q2. Does every prime $p$ have an $n \neq p$ such that $f(n) = p$, i.e., is every prime "reached" by $f(\;)$? (Yes: See JeremyRouse's answer.)

There appear to be interesting patterns here. For example, it seems that $f(n)=5$ is common. (Indeed: See მამუკა ჯიბლაძე's graphical display.)

-
Isn’t it obvious that the product of at least two integers greater or equal $2$ is larger than their sum except for $2+2=2\cdot2$, hence $g(n)< n$ unless $n$ is a prime or $4$? And every prime is reached by $f(p)=p$? – Emil Jeřábek Aug 4 '14 at 13:27
@EmilJeřábek: Thanks, I meant reached by other than by $p$ itself; will correct. – Joseph O'Rourke Aug 4 '14 at 13:30
some superficial resemblance to collatz conjecture in the iteration etc. there is some way of unifying these types of questions under an automata theory formulation. – vzn Aug 4 '14 at 17:08
The next natural question to ask seems to be density of attracting basins: what are the asymptotics of (for instance) $\frac1N\left|\{x: x\leq N\wedge f(x)=5\}\right|$? – Steven Stadnicki Aug 4 '14 at 22:11
Cardinality of $g^{-1}(n)$ seems to grow exponentially; note that it is the number of presenting $n$ as a positive linear combination of primes. – მამუკა ჯიბლაძე Aug 5 '14 at 5:32

A way to get a non-trivial solution to $f(n) = p$ is that every odd number $\geq 7$ can be written as a sum of three primes (by Helfgott's recent work), so if $p \geq 7$ is prime, we can write $p = q + r + s$, and we have $g(qrs) = q + r + s = p$. (This is of course a bit overkill, we don't really need such a difficult result to see this.)

-
Another way to see this is to note that if $n \geq 2$, then $n = 2x + 3y$ for some non-negative integers $x$ and $y$. Then $g(2^{x} \cdot 3^{y}) = 2x + 3y$. This gives $f(n) = p$ non-trivially if $p \geq 5$. – Jeremy Rouse Aug 4 '14 at 13:36

NOT AN ANSWER, just an illustration :D ($g$ up to $n=150$)
Quite amusing...

In case anybody wants to play with this, here is the Mathematica code

g[n_] := Dot @@ Transpose[FactorInteger[n]]
Graph[Map[# \[DirectedEdge] g[#] &, Range[2, 150]],
VertexLabels -> Placed["Name", {1/2, 1/2}], VertexShape -> ""]


And since, as discussed in the comments below, the picture might be misleading in that cutting at any given $n$ creates false impression that larger numbers have smaller $g$-preimages while in fact it is the exact opposite, here is the table of sizes and smallest and largest elements in $g^{-1}(n)$ for $n\leqslant30$:

n   |  min size max
-------------------
2   |   2   1   2
3   |   3   1   3
4   |   4   1   4
5   |   5   2   6
6   |   8   2   9
7   |   7   3   12
8   |   15  3   18
9   |   14  4   27
10  |   21  5   36
11  |   11  6   54
12  |   35  7   81
13  |   13  9   108
14  |   33  10  162
15  |   26  12  243
16  |   39  14  324
17  |   17  17  486
18  |   65  19  729
19  |   19  23  972
20  |   51  26  1458
21  |   38  30  2187
22  |   57  35  2916
23  |   23  40  4374
24  |   95  46  6561
25  |   46  52  8748
26  |   69  60  13122
27  |   92  67  19683
28  |   115 77  26244
29  |   29  87  39366
30  |   161 98  59049


And here is the code for $g^{-1}$:

ginverse[n_]:=Which[
n == 0, {1},
n == 1, {},
n == 2, {2},
True, With[{p = Prime[Range[PrimePi[n]]]},
Sort[Map[Times @@ (p^#) &, FrobeniusSolve[p, n]]]]]

-
The self-loop on $1$ should actually be an arrow $1\mapsto0$. – Emil Jeřábek Aug 4 '14 at 15:32
Right. Mathematica factorizes $1$ as $1^1$, that's why :D – მამუკა ჯიბლაძე Aug 4 '14 at 16:45
what app did you use to generate the graph? – vzn Aug 4 '14 at 17:08
@vzn Mathematica. I've added the code – მამუკა ჯიბლაძე Aug 4 '14 at 17:10
@JosephO'Rourke Well that might be misleading since I've cut at 150 (for larger $n$ picture became too messy). It might be for example that after large enough $n$ all sinks look the same. The only thing one may say for sure is that nothing goes to 2 or 3... – მამუკა ჯიბლაძე Aug 4 '14 at 19:04

Here is a (portion of a) histogram of $|f^{-1}(n)|$ for $n=5,\ldots,10^6$ (newly updated from $10^5$ to $10^6$):

$266429$ of those numbers $n \le 10^6$ map $f(n)=5$; $152548$ map $f(n)=7$.

-
Very interesting. The ratio $r_{5,7}(n):=\#(f^{-1}(7)\cap\{1,...,n\})/\#(f^{-1}(5)\cap\{1,...,n\})$ keeps oscillating, it is difficult to say whether it tends to 0 or to something positive or does have any limit at all. For example, $r_{5,7}(100)\approx0.576$, $r_{5,7}(1000)\approx0.582$, $r_{5,7}(10000)\approx0.567$, $r_{5,7}(100000)\approx0.583$, $r_{5,7}(1000000)\approx0.572$. – მამუკა ჯიბლაძე Aug 7 '14 at 8:15
I would be interested in any conjectures why $f^{-1}(17)$ is smaller than $f^{-1}(19)$, etc.---all the twin primes exhibit this behavior. – Joseph O'Rourke Sep 14 '15 at 21:43