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.

• emanresu A: (note: I tried porting this to C, it was almost exactly the same speed. JavaScript can be surprisingly fast sometimes!)
• Arnauld: Oddly enough, your version is about twice as slow as mine on my machine (using Node.js 20.10.0 / measured by invoking the test suite 10 times with each function).
• emanresu A: @Arnauld I'm able to reproduce a similar thing: When running 10 times within the JS program, yours is 2.6s, mine is 4.1s; when running 10 times using a bash for loop, yours is 2.8s, mine is 2.1s. I have no clue why this happens, or how restarting the process speeds up mine twofold. (I'm using nodejs 20.12.0 which shouldn't make much difference). Also, the C port is fairly consistently 1.75s either way.
• Arnauld: The consecutive allocations and (implicit) de-allocations of your cache array may trigger garbage collection when the function is called several times within the JS program. This is unlikely to happen when using a bash loop. Doing let cache = new Uint32Array(m) makes it significantly faster in the 1st scenario (I haven't tested the bash loop).
• l4m2: Does it detect loop or what?

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!

Answer 3

Rust, ~89ms

Port of @emanresu A's C code in Rust.

Try it online!

fn f(a: usize, b: usize, m: usize, mut k: i64, n: u64) -> usize {
 let mut v1 = a;
 let mut v2 = b;
 let mut cache = vec![0i64; m<<1];
 cache[a] += 1;
 cache[b] += 1;
 let mut i: u64 = 2;
 while i < n {
 let tmp = v2;
 v2 = (v2 + v1) % m;
 v1 = tmp;
 if v1 == a && v2 == b {
 cache[v1] -= 1;
 let llen = i - 1;
 let mul = n / llen;
 let rem = n % llen;
 for val in &mut cache {
 *val *= mul as i64;
 }
 for _ in 0..rem {
 let tmp = v2;
 v2 = (v2 + v1) % m;
 v1 = tmp;
 cache[v2] += 1;
 }
 break;
 }
 cache[v2] += 1;
 i += 1;
 }
 let mut idx = 0;
 while k >= 0 && idx < m {
 k -= cache[idx];
 idx += 1;
 }
 idx - 1
}
fn main() {
 println!("{}", f(1, 1, 10, 8, 10)); // Output: 5
 println!("{}", f(8, 2, 15, 7, 63)); // Output: 2
 println!("{}", f(21948, 12412, 42124, 85217, 92412)); // Output: 38508
 println!("{}", f(102492, 128282, 87421, 242122, 341247)); // Output: 61572
 println!("{}", f(42424, 76767, 97487, 3784274, 10421244)); // Output: 35377
 println!("{}", f(50127, 31229, 99887, 9784274, 17421244)); // Output: 56002
 println!("{}", f(11127, 93229, 94823, 20084263, 20421244)); // Output: 93278
}