algorithm - Find positive integer that can't be expressed by [x/2] y x*y? -

there expression: [x/2] + y + x * y, x , y positive integers, [x/2] mean rounding down integer, example, [3/2] = 1. positive integers can't expressed expression, example, 1, 3. now, question how find out first 40 numbers?

when x = 1, expression 2*y, number must not number. when y = 1, expression [x/2] + x + 1, not include 3*n. tried follow:

int64_t givean( int n ) {     if( n == 1 ) return 1;     if( n == 2 ) return 3;     int = 3;     int count = 2;     while( true ){         int64_t m = * 3;         bool ok = true;         for( int x = 3; x <= ( 2*m - 2 ) / 3; x++ ){            if( ( x / 2 + x + 1 ) >= m ){                ok = false;            }            if( !( ( m - x/2 ) % ( x + 1 ) ) ){                ok = false;                break;            }         }         if( ok && ++count == n ){            return m;         }         += 2;     } } 

the first 7 numbers can found, find eighth number cost 2 minutes... first 8 numbers are:

1 3 15 63 4095 65535 262143 1073741823 

is there other high-performance algorithm solve problem?

this innocent problem turns out quite tricky. let's @ case of x odd , x separately.

if x odd, write x = 2k - 1 positive integer k. then, have

n = (k-1) + y * 2k = 2ky + k - 1 = y(2k+1) - 1 

note y positive integer, , 2k+1 odd integer greater 1. expression y*(2k+1) can generate any integer has odd prime factor. thus, n+1 has solution if has odd prime factor, in order non-solution, n+1 must either 1 (which has no prime factors @ all), or power of two. since n+1 illegal (it make n 0, can't happen since x , y positive integers), conclude non-solutions n must have n+1 power of two.

thus, can write our non-solutions 2^m-1 positive integer m.

---

now let's @ case of x. have

n = 2^m-1 = k + y * (2k+1) = k + 2ky + y 

look @ 2n+1:

2n+1 = 2^(m+1)-1 = 2k + 4ky + 2y + 1 = (2k + 1)(2y + 1) 

2k+1 , 2y+1 arbitrary odd numbers. because 2n+1 odd, conclude 2n+1 must composite. every solution (for x even) must have form. thus, n non-solution iff n+1 power of two, , 2n+1 prime.

in fact, implies 2n+1 mersenne prime, , first 40 non-solutions correspond first 40 mersenne primes (given mersenne prime mp, corresponding non-solution (mp-1)/2).

---

the fastest algorithm find first 40 mersenne primes ask internet. (seriously -- finding mersenne primes hard work; 50th mersenne prime not known yet!) exponents first 42 mersenne primes given 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, example, 40th non-solution 2^(20996011-1)-1, big number.