23
$\begingroup$

This is likely piling one mystery on another, but ...

I was exploring a function $f(n): \mathbb{N} \mapsto \mathbb{N}$ defined as follows: $$ f(n) = \begin{cases} n^2 & \text{if} \;n \;\text{is prime} \\ \lfloor n/2 \rfloor & \text{if} \;n \;\text{is composite} \end{cases} $$ For example, $$ \begin{eqnarray*} f(11) &=& 121 \\ f(121) &=& 60 \\ f(60) &=& 30 \\ f(30) &=& 15 \\ f(15) &=& 7 \\ f(7) &=& 49 \\ f(49) &=& 24 \\ f(24) &=& 12 \\ f(12) &=& 6 \\ f(6) &=& 3 \\ f(3) &=& 9 \\ f(9) &=& 4 \\ f(4) &=& 2 \\ \end{eqnarray*} $$ and now we are in a $2/4$ cycle.

For all $n=2,\ldots,228$, repeated applications of $f(n)$ leads to a $2/4$ cycle. For $n=229$ (a prime), $f(229)$ seems to shoot off, in spurts, to large values: $$229, 52441, 26220, 13110, 6555, 3277, 1638, 819, 409, 167281, 83640, 41820, 20910, 10455, 5227, 27321529, \ldots $$


      f229n15
      f229n100
For $n=2,\ldots,10^4$, about $87$% end in a $2/4$ cycle, and $13$% seem to shoot off into the realm of large numbers.

Q0. Have iterates of this function $f(n)$ (or its close analogs) been studied before?

Q1. Is there any hope of explaining the behavior of iterates of $f(n)$?

Q2. Can the convergence of iterates of $f(n)$ be proved for selected classes of values of $n$?

For example, $n=2^k$ always ends in the $2/4$ cycle.

Q3. For which values of $n$ can it be proved that $f^k(n) \to \infty$?


(Added 8Aug15): Here are the trajectories of the first 20 primes (in red), all heading toward the $2/4$ cycle (green). It remains unsettled if (a) any integer starting value diverges to $\infty$, and (b) whether the only cycle is the $2/4$ cycle.
      Primes20Graph


$\endgroup$
  • 5
    $\begingroup$ Do you see a decrease in the percentage? Spontaneously I would guess that "large" values will typically diverge. Also minor observation: after a prime-induced increase there are (small exceptions aside) always at least four divisions as $2^33 \mid p^2 - 1$ for $p>3$. $\endgroup$ – user9072 May 7 '15 at 0:09
  • 2
    $\begingroup$ @quid: About 13% of random numbers $< 2^{15}$ do not (quickly) converge, and 17% $< 2^{25}$ do not (quickly) converge. My statistics are so far unclear and I think unreliable, because the numbers become huge and it is unclear how long to iterate ... $\endgroup$ – Joseph O'Rourke May 7 '15 at 0:43
  • 7
    $\begingroup$ Starting $229$,with reduce algebra,reached $4$ in $6309$ iterations,45 sec. I don't know how reduce's predicate primep is implemented (probabilistic?).Largest value reached $10613768981163204414627175313180737349067051074117777300661796192134932051543\\ 82936445589838033817648348402302759356278430463871174932095409785775688743146\\ 91761724995212201235865527079622200206370309059836496544759514650302268022149\\ 99434766295761932722545442857968114170818294806704220521159133772871452206394\\ 314754503711087596770519332383394996894366623801534088917281323964529$ $\endgroup$ – Mirko May 7 '15 at 3:40
  • 2
    $\begingroup$ A list of primes $p<1200$ with the corresponding number (when it seems big) of iterations to reach $4$. For $p=397$ my computer ran overnight and keeps going. (229,6309) (277,2050) (311,5897) (397,?big??) (409,6301) (449,1999) (491,6477) (521,2220) (599,2042) (653,?) (719,?) (727,6453) (787,1990) (827,?) (941,6468) (1009,?) (1033,749) (1051,3577) (1061,?) (1069,?) (1091,?) (1097,1140) (1123,?) (1129,?) (1193,?) I used reduce-algebra.com again. Could there be other cycles than ending in 2/4? Taking $n^2$ seems big compared to Collatz $3n+1$, on the other hand primes become rearer. $\endgroup$ – Mirko May 8 '15 at 12:34
  • 2
    $\begingroup$ Variations on $2^k$ theme.I posted math.stackexchange.com/questions/1273644 and learned about Riesel numbers, i.e. $k$ with $k⋅2^n−1$ composite for all $n$, e.g. $k=509203$. As $f^{29}(k−1)=f^{29}(509202)=4$ it follows $f^{29+n}(509203⋅2^n−1)=4$ for all $n$. Indeed if $n\ge1$, then $f(k⋅2^n-1)=f(k⋅2^n-2+1)=f(k⋅2^n-2)=f(2(k⋅2^{n-1}-1))=k⋅2^{n-1}-1$. Also $k=762701, k=777149, k=790841, k=992077$ all work, $k−1$ ends in 2/4,and so do $k⋅2^n-1$ all $n$, and $k⋅2^n-2$, $n\ge1$.If $m$ ends in 2/4 so do $m⋅2^n$, and $m⋅2^n+1$ but when composite. $\endgroup$ – Mirko May 9 '15 at 5:08
8
$\begingroup$

Let us use a rough estimate for the probability of a large integer $n$ being prime as $\frac{1}{\ln n}$ (as suggested by PNT). Then the expectation of $\ln f(n)$ can be estimated as $$\frac{1}{\ln n}\cdot \ln n^2 + \left(1-\frac{1}{\ln n}\right)\cdot \ln \lfloor \frac{n}{2}\rfloor = \ln n + 1 - \ln 2 + O(\frac{1}{\ln n}).$$ Since $1-\ln 2>0$, we have that the expectation of $\ln f(n)$ is larger than $\ln n$, which suggests that iterations of $f()$ may diverge for some large $n$.

This approach also suggests that to eliminate divergence, instead of the divisor 2 in the composite case one needs to take a divisor larger than $e\approx 2.718$ (e.g., 3).

P.S. Unavoidable divisions after squaring do not change the picture. E.g., if we have $\lfloor\frac{n^2}{2^5}\rfloor$ instead of $n^2$, the expectation of $\ln f(n)$ is still estimated as $\ln n + 1 - \ln 2 + O(\frac{1}{\ln n})$ for large $n$.

$\endgroup$
  • $\begingroup$ Nice insights from estimating probabilities! $\endgroup$ – Joseph O'Rourke May 10 '15 at 12:41
  • $\begingroup$ divisor $3$ (instead of $2$) may split the integers in (at least) two disjoint unbounded sets, the numbers from one of them ending up in $\dots\mapsto 4 \mapsto 1 \mapsto ?$, and the numbers from the other set ending up in $\dots\mapsto 3 \mapsto 9 \mapsto 3$. $\endgroup$ – Mirko May 10 '15 at 13:25
  • $\begingroup$ @Mirko: That's fine. Under divergence I meant unboundness of iterations of $f()$ starting at some $n$. If these iterations are bounded for all $n$, they fall into a limiting cycle. There may be one or more such limiting cycles, depending on the definition of $f()$. $\endgroup$ – Max Alekseyev May 10 '15 at 14:12
1
$\begingroup$

The full detail of this is of course a complex matter but I can build out some structure and connect the problem to some powerful tools for you; namely that, like the Collatz conjecture, this structure descends linear combinations of Lucas sequences.

The floor function of dividing by two descends the sequences $x_{n+1}=2x_n+1$; e.g.:

$0,1,3,7,15,31,63,\ldots$

Which should be fairly obvious. Furthermore if you divide alternate numbers in this sequence by $3$ you have the immediate odd predecessors of $1$ in the Collatz graph; namely $\{1,5,21,85,341,\ldots\}$ so the connection is fairly obvious.

Numbers just below any descending sequence converge to the same path. In fact the catchment gets wider the higher up the sequence you go, so e.g. $\{62,61,60\}$ go to $15$ then $\{62,61,60,59,58,57,56\}$ go to $7$ etc.

Of course your function will descend these sequences and their neighbourhoods until it hits some highest prime so to build the graph it's necessary to break apart the descending sequences at the prime numbers and graph those upwards to $x^2$ instead of down, connecting the next descending sequence.

I happened to choose the Mersenne numbers, and there are likely infinitely many prime examples although like all Lucas sequences of the first kind this is a divisibility sequence and therefore only a number with a prime index can itself be prime. But this isn't generally the case in all of your function's descending sequences.

The Mersenne numbers are the Lucas sequence $U_n(3,2)$. You can generate every such descending sequence which your function descends, by the linear combinations of $U_n(3,2)$ with its companion $V_n(3,2)=2,3,5,9,17,33\ldots$

$U_n$ is the sequence $2^n-1$ while $V_n$ is the sequence $2^n+1$ so they converge in $\Bbb{Z}_2^{\times}$ to $\pm1$ giving you a set dense enough in $\lvert\cdot\rvert_2$ that perhaps intuitively hints at them covering a set $\{z_1,z_2\in\Bbb{N}:\lvert z_1-z_2\rvert_2\leq\frac{1}{2}\}$ i.e. having an integrality gap of 2 - the odd numbers.

To fully index your descending sequences, and graph the vertices where they stop descending and go up, you need to identify the set of linear combinations of these such that the least value in the sequence is a prime number.

To do that, you need the set of primes $p$ such that $2p+1$ is not prime and define the sequence $S_p=a\cdot U_n(3,2)+b\cdot V_n(3,2)$ by setting $b\cdot V_0(3,2)=p$ and choosing $a$ such that $S_{p+1}=2p+1$

That gives you the set of sequences:

$S_p=(\frac{p}{2}+1)\cdot U_n(3,2)+(\frac{p}{2})\cdot V_n(3,2)$

Next you need to build the successor relation between these sequences; i.e. from the prime at the base of one, to the next descending sequence via the function $x^2$. A (fairly obvious) observation is that the floor function of an odd square halved is equal to $\frac{n^2-1}{2}$. All odd squares are of the form $4n+1$ so the function $p^2$ will always be followed by at least a division by $4$, so we will always have: $\dfrac{p^2-1}{4}$ before possibly more divisions by $2$.

The next part of the exercise is to show that the function $x^2$ totally orders these sequences $S_p(3,2)$.

I could go on but you are probably bored (and answering Collatz-related questions can be risky for low-rep users!) Hopefully I have built out a good amount of the structure which others with greater skills than me may be able to take further.

Another critical structural note to bear in mind is that once you have eliminated unnecessary structure such as perhaps the even numbers, the leaves of this graph, if there are any, will initially be among the primes $p$ for which $2p+1$ is also a prime since these $p$ are the primes which cannot be descended to down some sequence $S_n$ (as obviously any such descent would stop at $2p+1$ and ascend, if $2p+1$ were prime). But if I were a betting man I would predict that the "unnecessary structure" is actually pretty complex and there is a vast amount to be whittled away, and that in the final construct of this graph, the Mersenne Primes may actually be the leaves of the graph, and that the proof this converges to a cycle for all inputs is largely equivalent to there being infinitely many Mersenne Primes. But that is conjecture.

There is a vast array of research into Lucas sequences and numerous algebraic structures underpin any set of linear sequences of them as per the link I gave above. The next part of the exercise I would suggest is to take a look at that structure and find how it determines that the function $p\to p^2$ preorders the sequences $S_p=(\frac{p}{2}+1)\cdot U_n(3,2)+(\frac{p}{2})\cdot V_n(3,2)$

$\endgroup$
1
$\begingroup$

This is not an answer, just a comment to give another display of the results for smaller $n$. It is produced using Pari/GP and its inherent "ispseudoprime()" function.
I document the (odd) initial number $n$ and then a string of numbers. Here the numbers mean the number of consecutive division operations after one squaring operation. If $n$ is a (strong pseudo-) prime then the string of numbers begins with a zero, because the number of division-operations is zero before the first squaring operation occurs.

(btw: Pari/GP gives also a finite length for $n=229$; (the same number $6093$ steps as in @Mirko's comment)

3 : 0,2
5 : 0,3,2
7 : 0,4,2
9 : 2
11 : 0,4,4,2
13 : 0,5,3,2
15 : 1,4,2
17 : 0,7
19 : 0,5,4,4,2
21 : 2,3,2
23 : 0,8
25 : 3,2
27 : 1,5,3,2
29 : 0,6,5,3,2
31 : 0,7,4,2
33 : 4
35 : 1,7
37 : 0,8,3,2
39 : 1,5,4,4,2
41 : 0,7,5,3,2
43 : 0,8,4,2
45 : 2,4,4,2
47 : 0,7,7
49 : 4,2
51 : 4,2
53 : 0,6,8,4,2
55 : 2,5,3,2
57 : 3,4,2
59 : 0,8,5,3,2
61 : 0,7,6,5,3,2
63 : 1,7,4,2
65 : 5
67 : 0,8,7
69 : 2,7
71 : 0,5,13,2
73 : 0,6,6,7,7,7,6,5,3,2
75 : 1,8,3,2
77 : 2,5,4,4,2
79 : 0,6,7,6,6,7,7,7,6,5,3,2
81 : 4,3,2
83 : 0,6,7,7,7,6,5,3,2
85 : 4,3,2
87 : 1,8,4,2
89 : 0,7,7,6,5,3,2
91 : 3,4,4,2
93 : 2,8
95 : 1,7,7
97 : 0,7,6,6,7,7,7,6,5,3,2
99 : 5,2
101 : 0,7,6,7,6,6,7,7,7,6,5,3,2
103 : 0,5,11,6,8,4,2
105 : 3,5,3,2
107 : 0,7,7,7,6,5,3,2
109 : 0,9,8
111 : 3,5,3,2
113 : 0,6,5,12,9,10,5,13,2
115 : 4,4,2
117 : 2,6,5,3,2
119 : 1,8,5,3,2
121 : 4,4,2
123 : 1,7,6,5,3,2
125 : 2,7,4,2
127 : 0,9,7,4,2
129 : 6
131 : 0,8,8,7
133 : 6
135 : 1,8,7
137 : 0,6,9,11,5,3,2
139 : 0,9,8,3,2
141 : 3,7
143 : 1,5,13,2
145 : 6
147 : 1,6,6,7,7,7,6,5,3,2
149 : 0,7,6,6,12,17,7,6,5,3,2
151 : 0,8,7,7,6,5,3,2
153 : 3,5,4,4,2
155 : 3,5,4,4,2
157 : 0,13,2
159 : 1,6,7,6,6,7,7,7,6,5,3,2
161 : 5,3,2
163 : 0,8,5,11,6,8,4,2
165 : 2,7,5,3,2
167 : 0,11,5,3,2
169 : 5,3,2
171 : 5,3,2
173 : 0,6,6,12,17,7,6,5,3,2
175 : 2,8,4,2
177 : 4,4,4,2
179 : 0,10,7,4,2
181 : 0,8,9,7,4,2
183 : 4,4,4,2
185 : 3,8
187 : 3,8
189 : 2,7,7
191 : 0,9,5,13,2
193 : 0,14
195 : 1,7,6,6,7,7,7,6,5,3,2
197 : 0,8,8,7,7,6,5,3,2
199 : 0,5,12,9,10,5,13,2
201 : 6,2
203 : 1,7,6,7,6,6,7,7,7,6,5,3,2
205 : 6,2
207 : 1,5,11,6,8,4,2
209 : 4,5,3,2
211 : 0,7,12,6,5,3,2
213 : 2,6,8,4,2
215 : 1,7,7,7,6,5,3,2
217 : 4,5,3,2
219 : 1,9,8
221 : 4,5,3,2
223 : 0,9,7,6,6,7,7,7,6,5,3,2
225 : 5,4,2
227 : 0,14,2
229 : 0,7,5,7,8,25,34,19,26,58,28,8,8,21,10,13,5,21,25,7,32,10,13,6,5,14,18,20,9,27,12,41,33,14,11,52,25,37,52,14,23,141,35,79,78,64,149,23,446,167,341,716,22,165,316,337,152,65,62,1038,179,369,71,287,69,20,6,7,7,7,6,5,3,2
231 : 5,4,2
233 : 0,10,6,8,4,2
235 : 3,6,5,3,2
237 : 2,8,5,3,2
239 : 0,8,9,7,6,6,7,7,7,6,5,3,2
241 : 0,6,6,20,13,2
243 : 5,4,2
245 : 2,7,6,5,3,2
247 : 2,7,6,5,3,2
249 : 3,7,4,2
251 : 0,10,7,6,5,3,2
253 : 3,7,4,2
255 : 1,9,7,4,2
257 : 0,15
259 : 7
261 : 7
263 : 0,5,16,5,13,2
265 : 7
267 : 7
269 : 0,12,7
271 : 0,10,5,13,2
273 : 4,7
275 : 1,6,9,11,5,3,2
277 : 0,7,7,7,20,14,6,9,18,10,21,28,7,23,74,20,56,100,118,214,113,600,16,62,293,58,45,13,9,22,12,5,4,4,2
279 : 1,9,8,3,2
281 : 0,5,8,10,22,25,13,2
283 : 0,12,5,4,4,2
285 : 2,5,13,2
287 : 2,5,13,2
289 : 7
291 : 7
293 : 0,9,11,5,3,2
295 : 2,6,6,7,7,7,6,5,3,2
297 : 3,8,3,2
299 : 1,7,6,6,12,17,7,6,5,3,2
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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