Modern Computing for Mathematicians (Math 587)
A generalization of the Syracuse iterator

February 24, 2009

Recall that the Syracuse function $s$ is defined for integers $n$ by $$s\left(n\right)=\left\{\begin{array}{cc}\hfill 1& \text{if}n\le 1\hfill \\ \hfill 3n+1& \text{if}n>1\text{is odd}\hfill \\ \hfill n⁄2& \text{if}n>1\text{is even}\hfill \end{array}\right.$$

Many questions about the iterative behavior of $s$ – in particular, the question of whether the value of some iterate from any starting point is $1$ – are unaffected if $s$ is replaced with the function $s_1$ defined as follows: $$s_1\left(n\right)=\left\{\begin{array}{cc}\hfill 1& \text{if}n\le 1\hfill \\ \hfill 3n+1& \text{if}n>1\text{is odd}\hfill \\ \hfill n⁄2^k& \text{if}n=2^{k}m\text{where}m\text{is odd and}k\ge 1\hfill \end{array}\right.$$ or, as one might more informally write, for $n\ge 1$, $$s_1\left(n\right)=3n+1\text{made coprime to}2\text{.}$$

Generalizing this, for given pairwise coprime integers $a,b,m>0$ with $m\ge 2$, one defines for $n\ge 1$ Here, for an integer $x$, the phrase “$x$ made coprime to $m$” means that for any common prime divisor $p$ of $x$ and $m$ the highest power of $p$ dividing $x$ is removed as a factor. Note that the meaning of is not changed when $m$ is replaced by the product of the distinct primes dividing $m$; that is, without loss of generality one may restrict to the case where $m$ is square-free.

Example: .

Exercises:

1. Write code for gp to investigate the iterates of from a given integer. In particular, the code should be able to determine whether from a given starting integer $n$ a cycle is formed within the first $N$ iterates.

2. Determine what cycles, if any, are formed and whether there seems to be a pattern of unbounded growth in the iterates for $n,N\le 10000$ in the following cases:

   1. .

   2. .

   3. .