Sandbox

# 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 , 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.

• Thanks for the tag, didn't know it existed. – Don Thousand Dec 10 '19 at 23:07
• 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 Dec 10 '19 at 23:11
• @LuisMendo I'll add it to the text – Don Thousand Dec 10 '19 at 23:19
• Any requirements for the range of outputs? 'Cause I can save bytes if leave it as int – Varad Mahashabde Dec 11 '19 at 19:44
• @RosLuP I don't know the language, but that looks right to me. – Don Thousand Dec 17 '19 at 18:15

# 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


Try it online!

• This program's score is 102334155. It is $f(n+1)$ – Don Thousand Dec 10 '19 at 23:18
• @DonThousand It's now 33 bytes. – Arnauld Dec 10 '19 at 23:18

# R, 33 bytes, score 34

n=scan();while(T%%n)F={T=T+F}-F;T


Try it online!

I thought I was going to have to resort to a 54 byte solution for a score of 55 (and had fun making an irreducible one), but eventually found this 33 byte solution.

When coerced to integers, F and T are initially worth 0 and 1; they go through the Fibonacci sequence until T is divisible by n.

# Perl 6, 33 bytes, Score: 34

->$a {(1,1,*+*...*).first(*%%$a)}


Try it online!

There's no specifically redundant parts, even if it would pretty easy to golf.

# Jelly, 12 bytes score = 13

ÆḞ
1Çḍ@¥1#ÆḞ


Try it online!

A full program that takes an integer and returns an integer.

• Could you explain what each part does in more detail? – Corsaka Dec 13 '19 at 13:58

# Python 2, 54 bytes; score 55

def f(n):
a,b=0,1
while b/n*n!=b:a,b=b,a+b
return b


Try it online!

# Japt, 12 bytes, Score: 13

@XvU}a@MgX+1


Try it

## Explanation

The shortest possible solution (below) for this is 9 bytes, which means we're looking for the lowest possible score greater than or equal to f(10)=610.

_©vU}a!gM


Try it

That gives a target length of 12 bytes as f(13)=13, which can easily be achieved with some ungolfing/code bowling, giving:

@XvU}a@MgX+1     :Implicit input of integer U
@                :Left function, taking an integer X as argument
XvU             :  Is X divisible by U?
}            :End function
a           :Starting at 0, pass each integer through the right function and return the first result that returns true when passed through the left function
@          :Right function, taking an integer X as argument
MgX+1     :  X+1th Fibonacci number


## Proofs

Hopefully, showing that no one character can be removed should also suffice to show that 2 or more characters can't be removed. I'll try to add a few words of explanation to the rest of these tomorrow.

*{box-sizing:border-box;}html{background:#fff;}body{background:#fff;color:#000;margin:0 auto;padding:20px;max-width:600px;}p{font-family:Arial,Helvetica Neue,Helvetica,sans-serif;font-size:14px;line-height:20px;margin:0 0 15px;}p.link{background:#eff0f1;border-radius:3px 0 0 3px;display:inline-block;margin:0 0 10px;width:32px;}a{display:block;padding:4px;}svg{fill:#212121;height:24px;width:24px;vertical-align:middle;}svg.warning{fill:#b00020;}pre{background:#eff0f1;border-radius:0 3px 3px 0;display:inline-block;line-height:16px;margin:0 0 10px 2px;padding:8px;width:calc(100% - 34px);}code{font-family:Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,sans-serif;font-size:13px;}p>code{background:#eee;padding:1px 5px;}
<p>Click the play icon next to each programme to test it. Note that all programmes will auto-run and some, highlighted in red with a circle, may freeze or crash the tab they're running in so proceed with cautiond.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=WHZVfWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>XvU}a@MgX+1</code></pre><p>Without the first <code>@</code> to open the left function the, now unmatched, closing <code>}</code> causes the programme to throw an error.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QHZVfWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@vU}a@MgX+1</code></pre><p>Removing the first <code>X</code> results in <code>U</code> being auto-inserted between the <code>@</code> and the <code>v</code> and, therefore, the left function instead testing whether <code>U</code> is divisible by itself, which, of course, it is. So, no matter the input, the programme will exit after the first iteration and always return <code>1</code>.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFhVfWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XU}a@MgX+1</code></pre><p>If the <code>v</code> is removed then the <code>X</code> is ignored and the left function now tests whether <code>U</code> is truthy, which, for all non-zero inputs, it always will be. So, as above, the programme will exit after the first iteration and always return <code>1</code>.</p><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2fWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@Xv}a@MgX+1</code></pre><p>The default agrument for the <code>v</code> method when applied to an integer is <code>2</code> so, by checking if <code>X</code> is divisible by 2, this version will always return the first even Fibonacci number: <code>2</code>.<p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VWFATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvUa@MgX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1ATWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}@MgX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hTWdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}aMgX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQGdYKzE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}a@gX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1YKzE&input=MTM" target="_blank"><svg class="warning" viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M12,20C7.59,20 4,16.41 4,12C4,7.59 7.59,4 12,4C16.41,4 20,7.59 20,12C20,16.41 16.41,20 12,20M12,2A10,10 0 0,0 2,12A10,10 0 0,0 12,22A10,10 0 0,0 22,12A10,10 0 0,0 12,2M10,16.5L16,12L10,7.5V16.5Z"/></svg></a></p><pre><code>@XvU}a@MX+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1nKzE&input=MTM" target="_blank"><svg class="warning" viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M12,20C7.59,20 4,16.41 4,12C4,7.59 7.59,4 12,4C16.41,4 20,7.59 20,12C20,16.41 16.41,20 12,20M12,2A10,10 0 0,0 2,12A10,10 0 0,0 12,22A10,10 0 0,0 22,12A10,10 0 0,0 12,2M10,16.5L16,12L10,7.5V16.5Z"/></svg></a></p><pre><code>@XvU}a@Mg+1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1nWDE&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}a@MgX1</code></pre><p class="link"><a href="https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QFh2VX1hQE1nWCs&input=MTM" target="_blank"><svg viewBox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><title>Try it</title><path d="M8,5.14V19.14L19,12.14L8,5.14Z"/></svg></a></p><pre><code>@XvU}a@MgX+</code></pre>

## Alternative, 12 bytes, score: 13

Unlike the original solution above, this one can't be golfed any further.

°õ!gM ævN ªß


Try it

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

int F(int m,int a=1,int b=1){return a%m?F(m,a+b,a):a;}


Try it online!

• I never thought about recursive functions! – Varad Mahashabde Dec 17 '19 at 11:44

# Cubix, 20 bytes, Score 21

U;;O01I%!^;u.@|W$p+q  Try it online! Maps onto the cube as follows  U ; ; O 0 1 I % ! ^ ; u . @ | W$ p + q
. .
. .


Watch it run

Fairly basic, builds the sequence on the stack checking the % for each iteration until it is zero then outputs and exits.

• 01I seed the stack with start of the sequence and input. 11I would also work.
• %! take modulus of TOS and test for 0. Also start of the loop
• ^;U;O!$@ if 0 pop TOS, u-Turn, pop TOS and output number, a couple of no affecting commands and halt • ;uq+p otherwise, pop TOS, u-turn, push TOS to bottom (input), add TOS and pull BOS to top • $W|W some trickery to keep the score nice while keeping it irreducible. skip the next command(W), reflect back onto the W, change the lane up onto the beginning of the loop

# C (clang), 54 bytes, score 55

f(n){int a=0,b=1;while(b%n){b+=a;a-=b;a=-a;}return b;}


Try it online!

# 05AB1E, score: 8 (7 bytes)

∞Åf.ΔIÖ


Explanation:

∞        # Push an infinite list: [1,2,3,...]
Åf      # Get the n'th Fibonacci number for each value in this list
.Δ    # Leave the first value of this list which is truthy for:
Ö  #  Is it divisible by
I   #  The input
# (after which this is output implicitly as result)


These are all the possible builtins after removing one or multiple characters of the program, none of which are able to have the same functionality as the full program above:

∞   # Push an infinite list: [1,2,3,...]
Åf  # Get the a'th Fibonacci number
f   # Get the prime factors of the given number(s) a
.Δ  # Leave the first value of the given list a which is truthy for
Δ   # Repeat the inner code until the result no longer changes
ÅΔ  # Get the (0-based) index of the first element of list a which is truthy for
Ö   # Check if integer a is divisible by b
I   # Push the input
.I  # Get the a'th permutation of b
Å   # No-op
.   # No-op

• Oooo, a new low score. I was waiting for a super short esolang solution. – Don Thousand Dec 12 '19 at 8:43

# SNOBOL4 (CSNOBOL4), 71 bytes, score 144

	N =INPUT
T =1
F	F =(T =F + T) - F
OUTPUT =T EQ(REMDR(T,N))	:F(F)
END


Try it online!

This might also be the most golfed version of this program, which would be interesting; I also learned that inline assignment works...

# Red, 54 bytes, score 55

func[n][a: 0 b: 1 until[t: a a: b(b: t + b)// n = 0]b]


Try it online!

In fact it doesn't work in Red console after removing the space in front of n:

>> f: func[n][a: 0 b: 1 until[t: a a: b(b: t + b)//n = 0]b]
== func [n][a: 0 b: 1 until [t: a a: b (b: t + b) / /n = 0] b]
>> f 55
*** Script Error: / does not allow refinement! for its value2 argument
*** Where: /
*** Stack: f


so I thiink it's a valid submission. I suppose there are some subtle differences in Red for Win and Linux

# Red, 67 bytes, score 2584

func[n][set[a b][0 1]until[set[t a]reduce[a b]zero?(b: t + b)% n]b]


Try it online!

• Looking back on this, this is invalid, since removing the space between '/' and 'n' doesn't change the functionality. – Don Thousand Jan 4 at 17:36
• @Don Thousand Yes, you are right. That's strange - other operators need a space as delimiter. I'll try to find another solution. Thanks for finding this oddity! – Galen Ivanov Jan 5 at 8:51
• @Don Thousand - It works as expected in Red console for Windows - the removal of the space results in an error (please see above). I added an alternative solution. – Galen Ivanov Jan 5 at 9:04

# MATL, (12 bytes), score 13

Oltb+tG\]wx


Try it online!

## Explanation

O       % Push 0
l       % Push 1
% Do...while. The stack contains F(k), F(k+1)
tb+   %   Duplicate, bubble up, add. The stack contains F(k+1), F(k+2)
t     %   Duplicate
G     %   Push input
\     %   Modulo
]       % End. If top of the stack is nonzero the loop continues
wx      % Swap, delete. This leaves only the latest Fibonacci number
% Implicitly display

• That's 144 points! – Don Thousand Dec 10 '19 at 22:58
• @DonThousand Sorry, I thought it was standard code golf. Score corrected (and improved!) – Luis Mendo Dec 10 '19 at 22:59
• I'm not smart enough to check, but have you made sure your code is irreducible? – Don Thousand Dec 10 '19 at 23:03
• I'm pretty sure it is irreducible, but it's unfeasible to check all 8191 reduced versions by hand. From the explanation it should be obvious that removing any of the used functions or control statements spoils the program – Luis Mendo Dec 11 '19 at 0:12

# Charcoal, 20 bytes, score 21

⊞υ¬υＷ⌊﹪υＩθ⊞υΣ…⮌υ²Ｉ⊟υ


Try it online! Link is to verbose version of code. Explanation:

⊞υ¬υ


Take the logical not of the predefined empty list and push that to the list. (Using a literal 1 would increase my score of course.)

Ｗ⌊﹪υＩθ


Divide each member of the list by the input and repeat while the minimum remainder is nonzero.

⊞υΣ…⮌υ²


Reverse the list, take the first (originally last) two elements (duplicates the single element in the first pass), take the sum, and push that to the list.

Ｉ⊟υ


Cast the last element of the list to string for implicit print.

# C++, 60 bytes, score : 610

long f(int m){long a=0,b=1;while(b%m){b+=a;a=b-a;}return b;}


If I had used int all the way, I would have had a score of 591286729879!

Try it online!

• I think this works for a score of 55, but due to limitations of int this doesn't work for some values: tio.run/… – 79037662 Dec 11 '19 at 20:24
• @79037662 Hello again! Are we taking it on faith that a is initialized as 0? – Varad Mahashabde Dec 11 '19 at 20:28
• Yes, isn't that how C++ works? I'm not too clear to be honest. – 79037662 Dec 11 '19 at 20:28
• @79037662 Quite sadly no. C++ is not clean with auto-nulled memory like that as it is designed to be run on, along with other bigger things, resource-limited real-time embedded systems. Any memory that gets allocated to our variables, we clean ourselves – Varad Mahashabde Dec 11 '19 at 20:31
• @79037662 Using your approach(with a=b-a also shifted inside the for), I can get down to 56 bytes, but it only worsens the score! Try it online! – Varad Mahashabde Dec 11 '19 at 20:41

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

r←u w
a←1⋄⎕ct←0⋄r←1x
→0×⍳0=w∣r⋄r+←a⋄a←r-a⋄→2


The above has the problem change the global variable ⎕ct, and not define the variable 'a' as local (so if there is one extern global variable name 'a' and a extern function use 'a' or ⎕ct even trhu some operation, that extern function could return the wrong result...).

test:

  (1..8),¨u¨1..8
1 1  2 2  3 3  4 8  5 5  6 144  7 21  8 8
u 70
5358359254990966640871840
u 89
89
u 7373
1895175617433302745829870137958720928499852361085393597796453313487
4796286293483889267053950822315526092023966574765828063258184
5381860131060934476214808351544411531275197835352771384243811
1374862903608742278191775434865737602577844700159135211456619
9731096037977185178018629433653291613989743478589685505639564
4857727724829027387848536067017682345714489064874396569806069
164055864141425


I copy "r+←a⋄a←r-a" from https://codegolf.stackexchange.com/a/196929/58988

• @Giuseppe thank you – RosLuP Dec 16 '19 at 19:34

# Ruby, 33 bytes, score 34

->n{a=b=1;a=b+b=a until b%n==0;b}


Try it online!

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

for(a=o=1;o%i;t=a,a+=o,o=t);


Edit: -2 bytes

Try it online!

Input goes in i, output goes in o 😅

• We do not allow input to be assigned to a predefined variable. It must be taken either as a function argument or via prompt. We also, by default, don't allow snippets; all solutions must be a function or full programme. – Shaggy Dec 11 '19 at 12:37
• Relevant meta posts: Program, Function or Snippet? and its follow-up: Input/Output methods – Arnauld Dec 11 '19 at 12:56

# C (gcc), 33 bytes, Score:34

int F(m,a,b){m=a%m?F(m,a+b,a):a;}