3
$\begingroup$

Let $n$ be an odd positive integer, Let $o=\operatorname{ord}_n 2$ be the order of 2 modulo $n$ and $m$ the period of $1/n, k$ is number of distinct odd residues contained in set $\{2^1,2^2,...,2^{n−1}\}$ modulo $n$.

If $o,m$ and $k$ are even power of 2 and $k$ divide $n-1$, then $n$ is item in the sequence $17, 257, 641, 65537, …$.

It seems all known items in the sequence are Fermat factors, How come?

$\endgroup$
  • $\begingroup$ @LSpice The sum of $n$ is the order of $2$ modulo $n$, see math.stackexchange.com/questions/413679/… for details. $\endgroup$ – Mike Oct 15 '19 at 11:44
  • $\begingroup$ @LSpice The cycle length of $n$ is the number of distinct odd residues contained in set $\{2^1, 2^2,...,2^{n-1}\}$ modulo $n$, details see:oeis.org/A179382 $\endgroup$ – Mike Oct 16 '19 at 0:23
  • $\begingroup$ also see: math.stackexchange.com/questions/3396113/… $\endgroup$ – Mike Oct 16 '19 at 12:34
  • 1
    $\begingroup$ If you want to make changes to your question, then you should edit it, not just say so in the comments. $\endgroup$ – LSpice Oct 18 '19 at 13:01
4
$\begingroup$

Hmm, unfortunately you deleted instructive portions of your OP, but let me answer based on that earlier version which included explicitela the iterations scheme.

You give a game of iteration on numbers, which I'd like to rewrite for some given positive odd number $z$ and an initial $a=1$ :
$$ b = {z+a\over 2^A } \tag 1 $$ where $A$ is taken such that $b$ is odd again.

You iterate that formula until this cycles: $$ c = {z+b\over 2^B } \qquad d = {z+c\over 2^C } \qquad \cdots \qquad a = {z+h\over 2^H } \tag 2 $$ Let us denote the number of iterates with $N$ and the sum of exponents $S=A+B+C+\cdots+H$ .
You wonder now about the observation that some numbers $z$ satisfy multiple conditions: that $N$ is a power of $2$, that $S$ is a power of $2$, (and about the period in decimal expansion of $1/z$ but which I shall not discuss here).


Let us look at some simple to detect properties.

  • What numbers $z$ have a cycle of $N=1$ ?
    this means $b=a$ and constructing a formula gives (here is $S=A$) $$\begin{array}{rll} a &= { z+a\over 2^S } \\ a2^S &= z+a \\ z &=a(2^S-1) \end{array} \tag {3.1} $$ $\qquad \qquad $ Assuming $ a=1 $ gives the set of solutions $$ \begin{array}{rll} z &\in \{1,3,7,15,\ldots\} \\ A=S &\in \{1,2,3,4,\ldots\} \end{array} \tag {3.2} $$

  • What numbers $z$ have a cycle of $N=2$ ?
    this means $c=a$ in definition (2) and a formula gives (here $S=A+B$) $$\begin{array}{rll} b &= { z+a\over 2^A } && a &= { z+b\over 2^B } \\ a &= { z+{ z+a\over 2^A }\over 2^B } & = { z2^A+ z+a \over 2^{A+B} } \\ a2^S -a &= z2^A+ z \\ z &= a{ 2^S-1 \over 2^A+1 } & \left(= a{ (2^S-1)(2^{A}-1) \over 2^{2A}-1 }\right) \end{array} \tag {4.1} $$ $\qquad \qquad $ Assuming $ a=1 $ gives the set of solutions $$ \Tiny \begin{array}{rr|ll} z & S & A & B \\ \hline 1 & 2 & 1 & 1 \\ 5 & 4 & 1 & 3 \\ 21 & 6 & 1 & 5 \\ \vdots & \vdots & \vdots & \vdots \\ \hline 3 & 4 & 2 & 2 \\ 51 & 8 & 2 & 6 \\ \vdots & \vdots & \vdots & \vdots \\ \hline 7 & 6 & 3 & 3 \\ 455 & 12 & 3 & 9 \\ \vdots & \vdots & \vdots & \vdots \\ \hline 15 & 8 & 4 & 4 \\ 3855 & 16 & 4 & 12 \\ 986895 & 24 & 4 & 20 \\ \vdots & \vdots & \vdots & \vdots \\ \hline 31 & 10 & 5 & 5 \\ 31775 & 20 & 5 & 15 \\ 32537631 & 30 & 5 & 25 \\ \vdots & \vdots & \vdots & \vdots \\ \hline 63 & 12 & 6 & 6 \\ 258111 & 24 & 6 & 18 \\ 1057222719 & 36 & 6 & 30 \\ \vdots & \vdots & \vdots & \vdots \\ \end{array} \tag {4.2} $$ This table displays easy to recognize patterns for setting up formulae for $z$ and $S,A,B$ for the $N=2$ case. One shot is surely
    $$ S=2A\cdot k \qquad \implies z={2^{2kA}-1\over2^A+1}= {(2^{2kA}-1)(2^{A}-1)\over 2^{2A}-1}$$
    and the left parenthese is always divisible by the denominator.
    For a better example: just to look at your question of $N=2^j$ && $ S=2^k$ for positive $j \le k$ we can extract cases for $j=1$, $N=2^j=2$ first
    $$ \Tiny \begin{array}{rr|ll} z & S & A & B \\ \hline 1 & 2 & 1 & 1 \\ 5 & 4 & 1 & 3 \\ 3 & 4 & 2 & 2 \\ 85 & 8 & 1 & 7 \\ 51 & 8 & 2 & 6 \\ 15 & 8 & 4 & 4 \\ 21845 & 16 & 1 & 15 \\ 13107 & 16 & 2 & 14 \\ 3855 & 16 & 4 & 12 \\ 255 & 16 & 8 & 8 \\ 1431655765 & 32 & 1 & 31 \\ 858993459 & 32 & 2 & 30 \\ 252645135 & 32 & 4 & 28 \\ 16711935 & 32 & 8 & 24 \\ 65535 & 32 & 16 & 16 \\ 6148914691236517205 & 64 & 1 & 63 \\ 3689348814741910323 & 64 & 2 & 62 \\ 1085102592571150095 & 64 & 4 & 60 \\ 71777214294589695 & 64 & 8 & 56 \\ 281470681808895 & 64 & 16 & 48 \\ 4294967295 & 64 & 32 & 32 \\ \vdots & \vdots & \vdots & \vdots \\ \end{array} \tag {4.3} $$
    As by (4.1) with $a=1$ and $S=2^k$ we have analytically
    $$\begin{array}{rll} z &= { 2^{2^k}-1 \over 2^A+1 } \\ &= { (2^{2^{k-1}}+1)(2^{2^{k-2}}+1)...(2^1+1)(2^1-1)\over 2^{A}+1 } &= { 3 \cdot 5 \cdot 17 \cdot 257 \cdot \ldots \cdot(2^{2^{k-1}}+1)\over 2^{A}+1 } \end{array} \tag {4.4} $$
    Because the parentheses in the numerator have no common factor, we can draw conclusions of possible $A$ in the denominator to make the fraction an integer value. (Empirically we can observe that all $A$ are perfect powers of $2$ and it is surely not difficult to prove this)


This can analoguously be extended to larger cycle-lengthes $N>2$ . It might furtherly be useful, to introduce a notation which combines the set of exponents $A,B,C,...$ with the resulting integer value $z$ in a fully compacted form, say $$ z = T(A_1,A_2,A_3,...,A_N) \tag 5$$ and look, for instance, at solutions $z$ for typical patterns of the exponents, like $z=T(1,1,1,...,1)$ or $z=T(1,1,...1,A_N)$ with $A_N\gt 1$ and $S=N-1+A$ to develop short formulae for the integer solutions.

I'm not going deeper into this nice game, but leave it to you as a suggestion how to approach analytical answers to your questions.

$\endgroup$
  • $\begingroup$ Thanks for your marvelous answer, and thank you for your contribution to this project. Your investment in time and energy was far beyond what I couldhave asked for. $\endgroup$ – Mike Oct 18 '19 at 6:02

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.