Find positive integer that can't be expressed by $\lfloor x/2 \rfloor + y + xy$

Question

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?

Answer 1

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}