Consider the expression
$$\lfloor x/2 \rfloor + y + xy$$
where $x$ and $y$ are positive integers, $\lfloor x/2 \rfloor$ means rounding down to integer, for example, $\lfloor 3/2 \rfloor = 1$. Some positive integers can't be expressed by this expression, for example, 1, 3. Now, the question is how to quickly find out the first 40 numbers?
This very innocent problem turns out to be quite tricky. Let's look at the case of $x$ odd and $x$ even separately.
If $x$ is odd, write $x = 2k - 1$ for some positive integer $k$. Then, we have
$$n = (k-1) + y\cdot2k = 2ky + k - 1 = y(2k+1) - 1$$
Note that $y$ is any positive integer, and $2k+1$ is any odd integer greater than 1. The expression $y(2k+1)$ can thus generate any integer which has an odd prime factor. Thus, $n+1$ has a solution if it has an odd prime factor, so in order for it to be a non-solution, $n+1$ must either be 1 (which has no prime factors at all), or a power of two. Since $n+1$ is illegal (it would make $n = 0$, which can't happen since $x$ and $y$ are positive integers), we conclude that all non-solutions $n$ must have $n+1$ be a power of two.
Thus, we can write all our non-solutions as $2^m-1$ for some positive integer $m$.
Now let's look at the case of even $x$. We have
$$ n = 2^m-1 = k + y(2k+1) = k + 2ky + y $$
Look at $2n+1$:
$$2n+1 = 2^{m+1}-1 = 2k + 4ky + 2y + 1 = (2k + 1)(2y + 1)$$
$2k+1$ and $2y+1$ are arbitrary odd numbers. Because $2n+1$ is always odd, we conclude that $2n+1$ must be composite. Every solution (for $x$ even) must have this form. Thus, $n$ is a non-solution iff $n+1$ is a power of two, and $2n+1$ is prime.
In fact, this implies that $2n+1$ is a Mersenne prime, and so the first 40 non-solutions correspond to the first 40 Mersenne primes (given a Mersenne prime $M_p$, the corresponding non-solution is $\frac{M_p-1}{2}$).
The fastest algorithm to find the first 40 Mersenne primes is to ask the Internet. (Seriously -- finding Mersenne primes is hard work; the 50th Mersenne prime is not even known yet!) The exponents for the first 42 Mersenne primes is given by OEIS A000043:
1 2
2 3
3 5
4 7
5 13
6 17
7 19
8 31
9 61
10 89
11 107
12 127
13 521
14 607
15 1279
16 2203
17 2281
18 3217
19 4253
20 4423
21 9689
22 9941
23 11213
24 19937
25 21701
26 23209
27 44497
28 86243
29 110503
30 132049
31 216091
32 756839
33 859433
34 1257787
35 1398269
36 2976221
37 3021377
38 6972593
39 13466917
40 20996011
41 24036583
42 25964951
and so, for example, the 40th non-solution is $2^{20996011-1}-1$, which is a really big number.
Note: this was originally posted on StackOverflow, but the math formatting there is terrible :P
