21

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=200=2^3 5^2$, $f(n) = 2 \cdot 3 + 5 \cdot 2 = 16$.

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

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 9
    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 04 '14 at 13:27
  • @EmilJeřábek: Thanks, I meant reached by other than by $p$ itself; will correct. – Joseph O'Rourke Aug 04 '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 04 '14 at 17:08
  • 3
    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 04 '14 at 22:11
  • @StevenStadnicki: Yes, precisely what I am wondering; and a nice formulation. Is there any reason to expect the densities to be uniform? Seems unlikely they would be uniform. And if not, then there is the question of why they are different. – Joseph O'Rourke Aug 05 '14 at 00:43
  • 2
    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 05 '14 at 05:32
  • By the way, $g$ can be extended to a function from rationals to integers... – მამუკა ჯიბლაძე Aug 05 '14 at 05:34
  • 1
    $g(n)$ is calculated, with many links, at http://oeis.org/A001414 also closely related are http://oeis.org/A002217 and http://oeis.org/A029908 – Gerry Myerson Aug 28 '19 at 02:50
  • Also worth a look: Mohan Lal, Iterates of a number-theoretic function, Math. Comp. 23 (1969), 181-183 available at https://www.ams.org/journals/mcom/1969-23-105/S0025-5718-1969-0242765-9/home.html – Gerry Myerson Aug 28 '19 at 02:55
  • 1
    Abstract of the Lal paper: Iterates of a function defined by the sum of the prime divisors of a number, where the multiple factors are counted multiply, are considered. The process of iteration is terminated at a prime. The density distribution of these primes is investigated empirically, for $ N \leqq 60000$ and it is found to be quite constant. – Gerry Myerson Aug 28 '19 at 02:56
  • 1
    @GerryMyerson: A001414: "Downgrades the operators in a prime decomposition." Direct hit---Thanks! – Joseph O'Rourke Aug 28 '19 at 12:36

4 Answers4

23

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

Jeremy Rouse
  • 19,981
  • 2
  • 76
  • 103
  • 18
    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 04 '14 at 13:36
16

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

enter image description here

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]]]]]
მამუკა ჯიბლაძე
  • 17,468
4

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$):

          PrimesFixedHist
$266429$ of those numbers $n \le 10^6$ map $f(n)=5$; $152548$ map $f(n)=7$.
Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 1
    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 07 '14 at 08:15
  • 2
    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
4

g5

Was thinking about this old question again, and made another image (sorry it is unreadable), in the style of user @მამუკა ჯიბლაძე, of the numbers $\le 2000$ that ultimately map to $5$ ($5$ and $6$ are in the center, with $8$ right and $9$ left, each connecting to $6$). For example: \begin{eqnarray} n = 1788 &=& 2^2 \; 3^1 \; 149^1\\ g(1788) &=& 2 \cdot 2 + 3 \cdot 1 + 149 \cdot 1 = 156\\ n = 156 &=& 2^2 \; 3^1 \; 13^1 \\ g(156) &=& 2 \cdot 2 + 3 \cdot 1 + 13 \cdot 1 = 20\\ n = 20 &=& 2^2 \; 5^1\\ g(20) &=& 2 \cdot 2 + 5 \cdot 1 = 9\\ n = 9 &=& 3^2\\ g(9) &=& 3 \cdot 2 = 6\\ n = 6 &=& 2^1 \; 3^1 = 5\\ g(5) &=& 5 \end{eqnarray} The overall structure of the $5$-sink remains the same as far as I can take the computations.
Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933