If $g$ is a primitive root modulo $p,ord_pg=p-1$
If $g^x\equiv g^y\pmod p\iff g^{x-y}\equiv1\pmod p\iff ord_pg\mid (x-y)$ (Proof below)
$\implies (p-1)\mid (x-y)$
This can be generalized to any composite $m>4$ having primitive root.So, $m$ must be of the form $p^e,2p^e$ where $p$ is an odd prime.
Now, $\phi(p^e)=p^{e-1}(p-1), \phi(2p^e)=phi(2)\phi(p^e)=p^{e-1}(p-1)$
In either cases if $g$ is a primitive root modulo $m,ord_pg=\phi(m)=p^{e-1}(p-1)$
If $g^x\equiv g^y\pmod m\iff g^{x-y}\equiv1\pmod m\iff ord_mg\mid (x-y)$
$\implies p^{e-1}(p-1)\mid (x-y)$
[
Proof :
Let $ord_ma=d$ and $a^n\equiv1\pmod m$ and $n=q\cdot d+r$ where $0\le r<d$
So, $a^{q\cdot d+r}\equiv1\pmod m\implies a^r\cdot (a^d)^q\equiv1\implies a^r\equiv1\pmod m$
But $d$ is the smallest positive integer such that $a^d\equiv1\pmod m$
$\implies r=0\implies n=q\cdot d$ i.e., $d\mid n$
]
First of all, one can see that $a^n\bmod b$ is eventually periodic in $n$. Let $a^{n+b'}\equiv a^n$ for sufficiently large $n$. Then the problem boils down to finding $n\bmod b'$.
By similar arguments, one can furthermore show that $n^k\bmod b'$ is eventually periodic in $k$ for $k<b'$. By induction, this let's us push a $\bmod$ up the power tower, until eventually we reach $\bmod1$, which gives us $0$. At such a point, additional powers only contribute to reaching the point where we reach that "eventually periodic" step.
Conclusion:
$a^{P_n(k)}\bmod b$ is eventually constant in $k$. What you are observing is the special case when it starts being constant at $k=1$.
Additional note:
Euler's totient and Carmichael's functions gives a $\bmod$ that gets pushed up into the next power (although it may not be optimal), so repeatedly applying $\varphi$ or $\lambda$ to the initial $b$ gives you a maximum height to check. For example, when $b=7$ and with Euler's totient function, we have
$\varphi(7)=6$
$\varphi(6)=2$
$\varphi(2)=1$
which means we only have to manually check $k<3$. For $a=40$ and $n=3$, it happens to be the case, so it holds for all $k\ge1$.
Best Answer
The largest power of $2$ that divides $10^9$ is $2^9=512$. From there on we have $$ 2^{9+n} \bmod 10^9 = 2^9\left(2^n \bmod \frac{10^9}{2^9}\right) $$ The sequence $2^n \bmod 5^9$ does satisfy the conditions for Euler's Theorem to apply; we find that it has period $\varphi(5^9)=4\cdot 5^8=1562500$. (Though actually it is not trivial that the period is not some divisor of this -- see Carmichael's theorem).
So we get $$ 2^n \bmod 10^9 = \begin{cases} 2^n \bmod 10^9 & n < 1562509 \\ 2^{((n-9)\bmod 1562500)+9} \bmod 10^9 & n \ge 1562509 \end{cases}$$