First, this is obviously true with no restrictions on $b$. For example, for $b = 2^n-2$ we get that $2^n - b = 2^n - (2^n-2) = 2$ is prime. This is boring, and likely not what you mean (and instead, I imagine you want $b$ small).
How small of $b$ should we expect for this to hold for?
One interpretation of the Prime Number Theorem is that the primes have "density $1/\ln x$".
This is to say that, when $x = 2^{40}$ to $2^{60}$, we (roughly) expect $\approx 1/40$ to $1/60$ numbers to be prime.
There are various ways of formalizing this (depending on whether you believe in the Riemann Hypothesis), see this page, especially the "generalizations" section.
Anyway, the takeaway should be that
- prime numbers are relatively "plentiful", so
- to find prime numbers (of your desired form), "just look".
This is to say that it is simple to write a program that searches for the smallest positive $b$ such that $2^n-b$ is prime.
The following is a Sage program, and should demonstrate how simple things are (provided primality testing is implemented).
def find_b(n):
q = 2**n
b = 0
while not (q-b).is_prime():
b += 1
return b
As you are interested in the cases of $2^{40}$ to $2^{60}$, I've computed those for you below
[(40, 87),
(41, 21),
(42, 11),
(43, 57),
(44, 17),
(45, 55),
(46, 21),
(47, 115),
(48, 59),
(49, 81),
(50, 27),
(51, 129),
(52, 47),
(53, 111),
(54, 33),
(55, 55),
(56, 5),
(57, 13),
(58, 27),
(59, 55),
(60, 93)].
The data format is that $(a,b)$ denotes the number $2^a-b$, so for example the first entry is the number $2^{40}-87$.
All numbers in the above list are prime.
Moreover, the choice of $b$ in the above is (as mentioned before) always the minimal choice such that $(a,b)$ is prime.
Executing this program is extremely efficient, it took well under a second on my desktop.
That all being said, the precise structure of $q_i$ that admit efficient arithmetic is a little more complex than what you describe, at least when doing Ring-LWE type things (where you are using polynomial arithmetic).
Here, being able to utilize Number Theoretic Transforms (even if only "incomplete" ones) is quite useful.
This imposes fairly strong requirements on the precise form of the moduli chosen (for complete NTTs, you need $q\equiv 1\bmod 2n$ when working in $\mathbb{Z}_q[x]/(x^n+1)$ iirc). That being said, these optimizations are perhaps a little more technically involved, so perhaps should be skipped initially when learning about encryption.