21
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 9
    $\begingroup$ 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$? $\endgroup$
    – Emil Jeřábek
    Commented Aug 4, 2014 at 13:27
  • 3
    $\begingroup$ 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|$? $\endgroup$
    – Steven Stadnicki
    Commented Aug 4, 2014 at 22:11
  • 2
    $\begingroup$ 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. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 5, 2014 at 5:32
  • 1
    $\begingroup$ $g(n)$ is calculated, with many links, at oeis.org/A001414 also closely related are oeis.org/A002217 and oeis.org/A029908 $\endgroup$
    – Gerry Myerson
    Commented Aug 28, 2019 at 2:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Aug 28, 2019 at 2:56

4 Answers 4

Reset to default
24
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 18
    $\begingroup$ 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$. $\endgroup$
    – Jeremy Rouse
    Commented Aug 4, 2014 at 13:36
16
$\begingroup$

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]]]]]
Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ The self-loop on $1$ should actually be an arrow $1\mapsto0$. $\endgroup$
    – Emil Jeřábek
    Commented Aug 4, 2014 at 15:32
  • 1
    $\begingroup$ Right. Mathematica factorizes $1$ as $1^1$, that's why :D $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 4, 2014 at 16:45
  • $\begingroup$ what app did you use to generate the graph? $\endgroup$
    – vzn
    Commented Aug 4, 2014 at 17:08
  • 2
    $\begingroup$ @vzn Mathematica. I've added the code $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 4, 2014 at 17:10
  • $\begingroup$ @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... $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 4, 2014 at 19:04
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 7, 2014 at 8:15
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 14, 2015 at 21:43
4
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .