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

$\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$ 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$ 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$ 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$ 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$ Aug 28, 2019 at 2:56

4 Answers 4

23
$\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.)

$\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$ 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]]]]]
$\endgroup$
6
  • 1
    $\begingroup$ The self-loop on $1$ should actually be an arrow $1\mapsto0$. $\endgroup$ Aug 4, 2014 at 15:32
  • 1
    $\begingroup$ Right. Mathematica factorizes $1$ as $1^1$, that's why :D $\endgroup$ Aug 4, 2014 at 16:45
  • $\begingroup$ what app did you use to generate the graph? $\endgroup$
    – vzn
    Aug 4, 2014 at 17:08
  • 2
    $\begingroup$ @vzn Mathematica. I've added the code $\endgroup$ 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$ 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$.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.