8
$\begingroup$

Title basically says it all, but...

Is it known whether the sequence generated by $2^n \bmod n$ is periodic as $n$ traverses the natural numbers?

Just for some flavor, the first 50 elements:

{0, 0, 2, 0, 2, 4, 2, 0, 8, 4,
 2, 4, 2, 4, 8, 0, 2, 10, 2, 16,
 8, 4, 2, 16, 7, 4, 26, 16, 2, 4,
 2, 0, 8, 4, 18, 28, 2, 4, 8, 16,
 2, 22, 2, 16, 17, 4, 2, 16, 30, 24,
   ...}
$\endgroup$
  • 3
    $\begingroup$ I don’t know, but I would guess no, because I would expect the sequence to be unbounded. $\endgroup$ – Joe Aug 26 at 12:28
  • 2
    $\begingroup$ This sequence appear on the list of integer sequences as oeis.org/A015910. It is conjectured that this sequence takes on every value but $1$. The much weaker statement that it takes on arbitrarily high values would be enough to disprove periodicity. $\endgroup$ – quarague Aug 26 at 12:33
8
$\begingroup$

$a_n=0$ iff $n$ is a power of $2$. This is obviously not periodic.

$\endgroup$
  • $\begingroup$ All that means is that the eventual period, if one exists, must be a power of 2, right? $\endgroup$ – Connor Harris Aug 26 at 13:04
  • 2
    $\begingroup$ The gap between zeroes gets twice as long every time they occur. So there will never be a period. $\endgroup$ – Matthew Daly Aug 26 at 13:07
  • $\begingroup$ Right, iff not if. $\endgroup$ – Connor Harris Aug 26 at 13:50
  • $\begingroup$ Several good answers, but I gotta go with this one. Duh. $\endgroup$ – Trevor Aug 26 at 17:18
9
$\begingroup$

If the sequence be periodic, there should exist $M$ s.t. $\forall n,2^n\,mod\,n<M$.

Choose $k$ s.t. $2^k>M$. Choose big prime $p>2^k$.

Let $n=pk$ then $2^n\equiv 2^k$ mod $p$. Thus, $2^n\,mod\,n\ge 2^k$. (contradiction)

$\endgroup$
7
$\begingroup$

It's easy to prove that $2^{3^n} \equiv 3^n-1 mod(3^n)$. So if you consider the sequence $x_{n}=(2^{3^n} \equiv 3^n-1 mod(3^n))$ it's divergent to infinity, and assumes infinite distinct values. So the sequence can't be periodic.

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