Calculating modular inverses of p mod $2^p$

[castrate]

Let p an odd prime. We want to calculate $I(p)=p^{-1}\mod 2^p$.
If we use EXGCD, it takes $O(\log_22^p)=O(p)$ time, which is not efficient enough.
Some small values are 3, 13, 55, 931, 3781, 61681, 248347, 4011943, 259179061......
It seems that $I(p)$ is slightly smaller than $2^{p-1}$, but I didn't find more explicit patterns, nor did I find the sequence on OEIS.

So is there a closed form of $I(p)$, or at least can we calculate that more efficiently?
Any idea would be appreciated!

[jaap]

After some experimentation it turns out that if $p=2k+1$ then the inverse of $p$ mod $2^p$ is $\frac{k\cdot2^p + 1}{p}$.

Clearly if that fraction is actually an integer, then it works as the inverse of $p$ mod $2^p$.
To prove that it is an integer for prime $p$, you can use Fermat's little theorem ($2^p\equiv2 \bmod p$):
We have:
$$k\cdot2^p + 1 = k\cdot2 + 1 = p \equiv 0 \mod p$$
so for prime $p=2k+1$ the number $k\cdot2^p + 1$ is divisible by $p$, and that division produces the inverse you want.

[pjt33]

After some experimentation it turns out that if $p=2k+1$ then the inverse of $p$ mod $2^p$ is $\frac{k\cdot2^p + 1}{p}$.

Which is $2^{p-1} - \frac{2^{p-1} - 1}{p}$, explaining the observation that it's slightly smaller than $2^{p-1}$.

A variant approach is to use the form of Fermat's little theorem that says that $2^{p-1} \equiv 1 \pmod p$, so that $\frac{2^{p-1} - 1}{p}$ is an integer. We have a $-1$ rather than a $+1$ in the numerator, so square the numerator to get $q = \frac{(2^{p-1} - 1)^2}{p} = \frac{2^{2p-2} - 2^p + 1}{p} = \frac{2^p (2^{p-2} - 1) + 1}{p}$. Since $p > 2$, $q$ is a multiplicative inverse of $p$ modulo $2^p$. The big disadvantage with respect to jaap's approach is that $q$ isn't inherently reduced modulo $2^p$.