How to evaluate zero sets fast?

Question

This recent code golfing post asked the possibilities of fast implementation in C the following (assuming n is an unsigned integer):

if (n==6 || n==8 || n==10 || n==12 || n==14 || n==16 || n==18 || n==20)

One possible simplification is to observe that the numbers a[]={6,8,10,12,14,16,18,20} form an arithmetic progression, so shifting the range and then using some bitwise tricks

if (((n - 6) & 14) + 6 == n)

leads to a shorter (and probably indeed more efficient) implementation, as answered by John Bollinger.

Now I am asking what is the analogously elegant (and hopefully equally efficient) implementation of

if (n==3 || n==5 || n==11 || n==29 || n==83 || n==245 || n==731 || n==2189)

Hint: this time the numbers a[k] form a geometric progression: a[k]=2+3^k.

I guess in the general case one cannot do better than sort the numbers a[k] and then do a logarithmic search to test if n is a member of the sorted array.

Answer 1

if ((n > 2) && (2187 % (n - 2) == 0)) 

Checks if (n - 2) is a power of 3 and is less than or equal to 2187 (3 to the power of 7)

As a generalization, to check if any unsigned integer n is a power of prime number k, you can check if n divides the largest power of k that can be stored in an unsigned integer.

Answer 2

This is very similar to recognizing a power of three, and you can adapt for example this solution:

bool test(unsigned x) {     x -= 2;     if (x > 2187)         return 0;     if (x > 243)         x *= 0xd2b3183b;     return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145; } 

With the given range, this can be further simplified (found by brute force):

bool test2(unsigned x) {   x -= 2;   return x <= 2187 && (((x * 0x4be55) & 0xd2514105) == 5); }