Background (not necessary for the challenge)

A standard number theory result using the pigeonhole principle is the fact that given any natural number k, there is a Fibonacci number that is a multiple of k.

We can see this by considering modular pairs (F(n-1) % k, F(n) % k), and noting that there are only a finite number of possibilities of the pairs, while there are infinitely many pairs, so by the pigeonhole principle, there are naturals n, m such that (F(m-1) % k, F(m) % k) = (F(n-1) % k, F(n) % k). But, this implies that F(m-2) % k = F(n-2) % k, and more generally, F(m-i) % k = F(n-i) % k. Notably, if m < n, F(0) % k = F(n-m) % k. But, F(0)=0, so this means that F(n-m) is a multiple of k.

Challenge

You must provide a program that takes in a natural k as an input and return m, the smallest Fibonacci number that is a multiple of k. This program must be irreducible in the sense that one can't remove any bytes and maintain the same functionality.

This challenge is a code-challenge, as your score will be the smallest Fibonacci multiple of (the number of bytes in your program + 1).

To find your program's score, use this TIO link: Try it online!

The lowest score for a valid response in each language wins!

Test Cases

1: 1
2: 2
3: 3
4: 8
5: 5
6: 144
7: 21
8: 8
9: 144
10: 610
11: 55
12: 144
13: 13
14: 46368
15: 6765
16: 144
17: 34
18: 144
19: 2584
20: 832040
21: 21
22: 832040
23: 46368
24: 144
25: 75025
26: 10946
27: 14930352
28: 46368
29: 377
30: 1548008755920
31: 832040
32: 46368
33: 6765
34: 34
35: 102334155
36: 144
37: 4181
38: 2584
39: 317811
40: 832040
41: 6765
42: 46368
43: 701408733
44: 832040
45: 1548008755920
46: 46368
47: 987
48: 144
49: 225851433717
50: 2111485077978050
51: 14930352
52: 267914296
53: 196418
54: 14930352
55: 55
56: 46368
57: 14930352
58: 267914296
59: 591286729879
60: 1548008755920
61: 610
62: 832040
63: 46368
64: 4807526976
65: 9227465
66: 1548008755920
67: 72723460248141
68: 2584
69: 46368
70: 5358359254990966640871840
71: 190392490709135
72: 144
73: 24157817
74: 365435296162
75: 354224848179261915075
76: 2584
77: 102334155
78: 160500643816367088
79: 8944394323791464
80: 1548008755920
81: 16641027750620563662096
82: 1548008755920
83: 160500643816367088
84: 46368
85: 1134903170
86: 1725375039079340637797070384
87: 317811
88: 832040
89: 89
90: 1548008755920
91: 225851433717
92: 46368
93: 1548008755920
94: 4807526976
95: 2880067194370816120
96: 46368
97: 7778742049
98: 57602132235424755886206198685365216
99: 1548008755920

You can use the TIO link above to generate more test cases if needed.

EDIT: As there seems to be some confusion on the scoring, here is how to generate your score:

Take the number of bytes in your function, add 1, and take the result of this addition, and find the smallest Fibonacci multiple of this result.

Don Thousand

Posted 2019-12-10T22:42:51.007

Reputation: 1 781

1Thanks for the tag, didn't know it existed. – Don Thousand – 2019-12-10T23:07:17.183

Strictly a pristine program is one that will error if bytes are removed. This challenge only requires that the program will have different functionality, which I interpret as producing a different output for some inputs – Luis Mendo – 2019-12-10T23:11:11.870

@LuisMendo That is correct. – Don Thousand – 2019-12-10T23:16:07.277

1@LuisMendo I'll add it to the text – Don Thousand – 2019-12-10T23:19:15.723

@Shaggy Thanks, I missed that bit. – Grimmy – 2019-12-11T12:41:03.760

1Any requirements for the range of outputs? 'Cause I can save bytes if leave it as int – Varad Mahashabde – 2019-12-11T19:44:52.787

@VaradMahashabde Sure, you can leave it as an int. – Don Thousand – 2019-12-12T01:18:46.173

While you've found a different way of quantifying it, it's unclear to me how this is any different from classic code golf. The shorter the program is in terms of bytes, the lower score it is going to have under your scoring criteria. Are there exceptions that I'm missing? Why not just make this code golf? – Cody Gray – 2019-12-12T07:19:08.190

@CodyGray That's not completely true. Some small byte patterns have high scores (for example, $13$ bytes). This condition ensured that code isn't just copied directly from other Fibonacci challenges. See Sandbox for discussion. – Don Thousand – 2019-12-13T01:37:45.190

in other words "a←1⋄r←1x⋄⎕ct←0" is not ok because this can be rewritten as "a←r←1x⋄⎕ct←0" eliminate 2 bytes (and the result of the funtion would the same) but this "a←1⋄⎕ct←0⋄r←1x" would be ok because if i eliminate some byte the meaning change... is thit right? – RosLuP – 2019-12-17T18:12:53.460

1@RosLuP I don't know the language, but that looks right to me. – Don Thousand – 2019-12-17T18:15:14.010

Answers

JavaScript (Node.js), 33 bytes, score: 34

Expects a BigInt as input.

f=(n,x=0n,y=1n)=>y%n?f(n,y,x+y):y

Smallest Fibonacci Multiples

Background (not necessary for the challenge)

Challenge

Test Cases

Answers

JavaScript (Node.js), 33 bytes, score: 34

R, 33 bytes, score 34

Japt, 12 bytes, Score: 13

Explanation

Proofs

Alternative, 12 bytes, score: 13

Perl 6, 33 bytes, Score: 34

Jelly, 12 bytes score = 13

Python 2, 54 bytes; score 55

C++ (clang), 54 bytes, score : 55

Cubix, 20 bytes, Score 21

Red, 54 bytes, score 55

Alternative:

Red, 67 bytes, score 2584

C (clang), 54 bytes, score 55

05AB1E, score: 8 (7 bytes)

SNOBOL4 (CSNOBOL4), 71 bytes, score 144

MATL, (12 bytes), score 13

Explanation

Charcoal, 20 bytes, score 21

C++, 60 bytes, score : 610

APL(NARS), chars 44, bytes 88, score 89

Ruby, 33 bytes, score 34

JavaScript (Node.js), 28 bytes, score 377

C (gcc), 33 bytes, Score:34