Find an integer such that when squared, the first 4 digits are '6666'.

You need $6666\times 10^k \leq x^2<6667\times 10^k$

If $k=2n$ is even, then this means:

$$10^{n}\sqrt{6666}\leq x\leq 10^{n}\sqrt{6667}$$

$\sqrt{6666}\approx 81.646$ and $\sqrt{6667}\approx 81.652$, so we can see that for $n=2$, $x=8165$ will work.

If $k=2n+1$ is odd, then you need:

$$10^{n}\sqrt{66660}\leq x\leq 10^{n}\sqrt{66670}$$

$\sqrt{66660}\approx 258.186$ and $\sqrt{66670}\approx 258.205$ and we get for $n=1$ that $x=2582$.

If you want to start with $D$, note that $\sqrt{D+1}-\sqrt{D}=\frac{1}{\sqrt{D+1}+\sqrt{D}} > \frac{1}{\sqrt{4D+2}}$. So at the very least, if $k>\log_{10}(4D+2)$ then $10^{k/2}\sqrt{D+1}-10^{k/2}\sqrt{D}>1$ so there must be an integer $x$ such that:

$$10^{k/2}\sqrt{D}\leq x<10^{k/2}\sqrt{D+1}$$ This technique would work for cubes, too, but you'd have to separate the question into three cases, $k=3n,k=3n+1,k=3n+2$. For $m$th powers, you consider $m$ cases.

For example, the smallest integer such that $x^7$ starts with $6666$ is $x=4888$.

Theoretically, you are essentially using the formula $\sqrt{100x}=10\sqrt{x}$.

Your iterations are, essentially, first compute $\sqrt{6666}=81.6455...$. You multiply exponentials of $10$ to get larger numbers, and apparently the second just works: $8165^2=66667225$.

There are two types of solutions: numbers starting from $\sqrt{6666}=81.6455...$ and numbers starting from $\sqrt{66660}=258.1859...$ and your answer is the second case. The "third" case would be numbers starting from $\sqrt{666600}$ which is just the same as the first case.

I'm both a programmer and a (quite amateur) mathematician. I wrote this python 3 program before looking at the answers just for fun (I hand calculated that the answer must start with either 81 or 25):

from math import sqrt

def f(n):
    for d in range(10):
        for i in range(10**d):
            x = n * 10**d + i
            y = x * x
            if str(y)[0:4] == '6666':
                print (x, y)
                return

if __name__ == '__main__':
    f(81)
    f(25)

prints out:

2582 6666724
8165 66667225

and runs well under a tenth of a second on my laptop.