Non-Decreasing Fibonacci Sequence modulo M

Question

Given integers \$a,b,m, k, n\$ and array \$F = (f_1, f_2,...,f_n)\$ defined as: \begin{cases} f_1 = \text{a}\\ f_2 = \text{b}\\ f_i = (f_{i-1} + f_{i-2}) \text{ mod m},∀i > 2 \end{cases} When \$F\$ array is sorted into a non-decreasing sequence, your task is to find the \$k\$-th integer of the sorted \$F\$ array where \$k ≤ n\$.

Sample I/O

I/O format is flexible.

# I/O format
# a, b, m, k, n -> Output
  1, 1, 10, 8, 10 -> 5
  8, 2, 15, 7, 63 -> 2
  21948, 12412, 42124, 85217, 92412 -> 38508
  102492, 128282, 87421, 242122, 341247 -> 61572
  42424, 76767, 97487, 3784274, 10421244 -> 35377
  50127, 31229, 99887, 9784274, 17421244 -> 56002
  11127, 93229, 94823, 20084263, 20421244 -> 93278

Visualization

Let's take the \$1^{st}\$ Sample I/O.
After generating the array \$F\$, our array would be: \begin{cases} f_1 = 1\\ f_2 = 1\\ f_3 = 2\\ f_4 = 3\\ f_5 = 5\\ f_6 = 8\\ f_7 = 3\\ f_8 = 1\\ f_9 = 4\\ f_{10} = 5\\ \end{cases} When sorting the array \$F\$ into a non-decreasing sequence, we will get: \begin{cases} f_1 = 1\\ f_2 = 1\\ f_3 = 1\\ f_4 = 2\\ f_5 = 3\\ f_6 = 3\\ f_7 = 4\\ f_8 = 5\\ f_9 = 5\\ f_{10} = 8\\ \end{cases} Since our given \$k\$ was \$8\$ as per our sample, we will print out the value of \$f_k\$ or \$f_8\$ of the sorted \$F\$ array, the value of which is \$5\$.
Therefore, for our \$1^{st}\$ sample, the output returned was \$5\$.

Winning Criterion

This is a fastest-code challenge. Timing will be based on the timing shown in the tio.run link provided, in the Debug section, User Time. A more precise one with times tested on my machine will be conducted later, since performance on tio.run may vary over time.
The time will be measured by how long it takes to complete all 7 test cases provided in the Sample I/O section.

Standing

Code	Language	Runtime
emanresu A	C (gcc)	0.5 - 3 ms
emanresu A	Node.js	1.7 - 4.4 ms

Answer 1

C (gcc), ~3.7ms

#include<stdlib.h>
#include<stdio.h>

int f(int a, int b, int m, int k, int n) {
  int v1 = a; int v2 = b;

  int tmp = 0;
  int* cache = malloc(m * sizeof(int));
  cache[a]++; cache[b]++;

  for(int i = 2; i < n; i++) {
    tmp = v2;
    v2 = (v2 + v1) % m;
    v1 = tmp;
    if (v1 == a && v2 == b) {
      cache[v1]--;

      int llen = i - 1;
      int mul = n / llen;
      int rem = n % llen;
      
      for (int i = 0; i < m; i++) cache[i] *= mul;
      for (int i = 0; i < rem; i++) {
        tmp = v2;
        v2 = (v2 + v1) % m;
        v1 = tmp;
        cache[v2]++;
      }
      break;
    }
    cache[v2]++;
  }

  int i = 0;

  while (k >= 0) k -= cache[i++];

  return i - 1;
}

Try it online! Compiled with -O3. Port of the below algorithm to C. Leaks a ton of memory but works.

JavaScript (Node.js), ~4.6ms

function f(a, b, m, k, n) {
  let v1 = a, v2 = b;

  let cache = new Uint32Array(m);
  cache[a]++; cache[b]++;

  for(let i = 2; i < n; i++) {
    //console.log(i, v1)
    tmp = v2;
    cache[v2 = (v2 + v1) % m]++;
    v1 = tmp;
    if (v1 == a && v2 == b) { // we're in a loop

      let llen = i - 1; // - 2 + 1 because post-increment
      let mul = n / llen | 0;
      let rem = n % llen;

      cache[v1]--;
      cache[v2]--;
      for (let i = 0; i < m; i++) cache[i] *= mul;

      // rerun the first rem terms of the loop to catch excess
      for (let i = 0; i < rem; i++) {
        tmp = v2;
        cache[v2 = (v2 + v1) % m]++;
        v1 = tmp;
      }
      break;
    }
  }

  i = 0;

  while (k >= 0) k -= cache[i++];

  return i - 1;
}

Try it online! Thanks to Arnauld for the idea of using a Uint32Array, speeding this up almost tenfold.

Based on Arnauld's answer, but tracks the number of times each value has occured to speed things up substantially and avoid a costly sort call. Arnauld's answer takes about 270-280ms on my machine.

Answer 2

Node.js 20.10.0, ~1.5 sec.

function f(a, b, m, k, n) {
  let A = [ a, b ];

  for(let i = 2; i < n; i++) {
    A[i] = (A[i - 2] + A[i - 1]) % m;

    if(A[i] == b && A[i - 1] == a) {
      A = A.slice(0, -2);
      break;
    }
  }

  A = A.map((v, i) => [v, i]).sort((a, b) => a[0] - b[0]);

  let q = Math.floor(n / A.length),
      r = n % A.length,
      j = 0;

  do {
    k -= q + (A[j++][1] < r);
  } while(k >= 0);

  return A[j - 1][0];
}

Try it online!