Fastest way to compute maximal n s.t. n over k <= x

I'm looking for a fast way to compute the maximal n s.t. n over k <= x for given k and x. In my context n \leq n' for some known constant n', lets say 1000. k is either 1,2, or 3 and x is choosen at random from 0 ... n' over k

My current approach is to compute the binomial coefficient iterativly, starting from a_0 = k over k = 1. The next coefficient a_1 = k+1 over k can be computed as a_1 = a_0 * (k+1) / 1 and so on. The current C code looks like this

uint32_t max_bc(const uint32_t a, const uint32_t n, const uint32_t k) {
   uint32_t tmp = 1;
   int ctr = 0;
   uint32_t c = k, d = 1;
   while(tmp <= a && ctr < n) {
      c += 1;
      tmp = tmp*c/d;
      ctr += 1;
      d += 1;
   }

   return ctr + k - 1;
}

int main() {
   const uint32_t n = 10, w = 2;

   for (uint32_t a = 0; a < 10 /*bc(n, w)*/; a++) {
      const uint32_t b = max_bc(a, n, w);
      printf("%d %d\n", a, b);
   }
}

which outputs

So I'm looking for a Bittrick or something to get around the while-loop to speed up my application. Thats because the while loop gets executedat worst n-k times. Precomputation is not an option, because this code is part of a bigger algorithm which uses a lot of memory.

Thanks to @Aleksei This is my solution:

template<typename T, const uint32_t k>
inline T opt_max_bc(const T a, const uint32_t n) {
    if constexpr(k == 1) {
        return n - k - a;
    }

    if constexpr (k == 2) {
        const uint32_t t = __builtin_floor((double)(__builtin_sqrt(8 * a + 1) + 1)/2.);
        return n - t - 1;
    }

    if constexpr (k == 3) {
        if (a == 1)
            return n-k-1;

        float x = a;
        float t1 = sqrtf(729.f * x * x);
        float t2 = cbrtf(3.f * t1 + 81.f * x);
        float t3 = t2 / 2.09f;
        float ctr2 = t3;
        int ctr = int(ctr2);

        return  n - ctr - k;
    }

    if constexpr (k == 4) {
        const float x = a;
        const float t1 = __builtin_floorf(__builtin_sqrtf(24.f * x + 1.f));
        const float t2 = __builtin_floorf(__builtin_sqrtf(4.f * t1 + 5.f));
        uint32_t ctr = (t2 + 3.f)/ 2.f - 3;
        return  n - ctr - k;
    }


    // will never happen
    return -1;
}

Solution

If k is really limited to just 1, 2 or 3, you can use different methods depending on k:

k == 1: C(n, 1) = n <= x, so the answer is n.
k == 2: C(n, 2) = n * (n - 1) / 4 <= x. You can solve the equation n * (n - 1) / 4 = x, the positive solution is n = 1/2 (sqrt(16x + 1) + 1), the answer to the initial question should be floor( 1/2 (sqrt(16x + 1) + 1) ).
k == 3: C(n, 3) = n(n-1)(n-2)/6 <= x. There is no nice solution, but the formula for the number of combinations is straightforward, so you can use a binary search to find the answer.