Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
8  
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 at 13:27
    
@EmilJeřábek: Thanks, I meant reached by other than by $p$ itself; will correct. –  Joseph O'Rourke Aug 4 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 at 17:08
2  
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 at 22:11
1  
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 at 5:32

3 Answers 3

up vote 14 down vote accepted

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

share|improve this answer
12  
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 at 13:36

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

Here is a (portion of a) histogram of $f(n)$ for $n=5,\ldots,100000$:


          PrimeFixed100K
About $27000$ of those numbers $n \le 10^5$ map $f(n)=5$.

share|improve this answer
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 7 at 8:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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