This may sound like a very stupid question, but with Tor I've seen URLs where they have whateverxx9191.onion, i'm guessing the first part is randomised, how hard is it for them to get the first part of their name?

Is there a program or script that just keeps generating until the minimum hit (redbook* would be acceptable etc) is made?

There are a few different programs that will do it, but it comes down to brute force, so the difficulty depends on the length.

https://github.com/katmagic/Shallot

https://github.com/lachesis/scallion

FYI I just checked and Shallot is entirely CPU based, so for brute forcing there is no point in using it at all - Scallion (open cl) will always be much, much, much faster.