Number of distinct remainders of modulo N when repeatedly applying power of 2s For an integer $x$, we compute $y=x^2$. If $y\geq N$, we do $y=y \mod N$. Set the value of $y$ as $x$, and repeat the whole process until we see a duplicate $y$. We want to find the number of distinct $y$s Y.
For example, for $x=26$ and $N=1000$:
$$26^2\mod{1000}=676$$
$$676^2\mod{1000}=976$$
$$976^2\mod{1000}=576$$
$$576^2\mod{1000}=776$$
$$776^2\mod{1000}=176$$
$$176^2\mod{1000}=976$$
$976$ is repeated, so the process ends. In this case, $Y=5$.
Can we find out $Y$ without doing the process described above? It seems the number of possible values for $Y$ is small compared to $N$. For $N=1000, 1\leq y \lt 1000, Y\in{1,2,4,5,20,21}$.
 A: Let's$\def\mod{\ \text{mod}\ }$$\def\ord#1{\text{ord}_{#1}}$
analyze the iteration modulo prime powers, and then put it all together.  There are two kinds of primes we are interested in:
Primes that divide $N$ and $x$
The order to which $p$ divides the $j$-th iterate $x_j=x^{2^j}$ is
$$\ord p(x_j) = 2^j\ord p(x)$$
Because $\ord p(x)\neq0$, there is some minimal index $j\in\Bbb N_0$ such that
$$2^j\ord p(x) \geqslant \ord p(N)$$
and for such a $j$ we have for the first time that $x_j\equiv 0 \mod p^k$ with $k=\ord p(N)$. This means the sequence has a period of 1 and a pre-period of $j$ values that are non-zero mod $p^k$.
Primes that divide $N$ but not $x$
Let $n$ denote the product of these primes to the order they occur in $N$, i.e. divide out all primes of the 1st kind out of $N$. Then we have obviously
$$\gcd(x,n) = 1.$$
The sequence $x_j$ will also enter a finite cycle, i.e. there are minimal $i, j\in \Bbb N_0$ with $j<i$ and
$$x_j \equiv x_i \mod n$$
The period $f$ satisfies $f=i-j\geqslant 1$ and
$$x^{2^j} \equiv x^{2^{j+f}} \mod n $$
which due to Fermat's little theorem means for the exponents that
$$2^j(2^f-1) \equiv 0 \ \mod\ \ord n(x) \tag 1$$
where $\ord n(x)$ denotes the multiplicative order of $x$ in $\Bbb Z/n\Bbb Z^\times$.
The values for $f$ and $j$ can be determined by computation, and to all of my knowledge there is no explicit formula.
Taking it all together

*

*The period for prime(power)s of the 1st kind will always be 1, thus the period of the sequence will be determined by $f$ from 2.


*The pre-period is the maximum of the pre-periods of either case.


*The dynamic ist almost completely determined by case 2: Case 1 does not add to the period, and the pre-period of case 1 will be short due to the exponential growth of the prime factors of the iterates of $x$.

Can we find out Y without doing the process described above?

No, knowing the period would basically mean to know the factorization of $N$, see Pollar's $\varrho$-method.
