# Find the Missing Numbers in the Fibonacci Sequence Mod K

Inspired by this Math.SE question.

# Background

The Fibonacci Sequence (called F) is the sequence, starting 0, 1 such that each number (F(n)) (after the first two) is the sum of the two before it (F(n) = F(n-1) + F(n-2)).

A Fibonacci Sequence mod K (called M) is the sequence of the Fibonacci numbers mod K (M(n) = F(n) % K).

It can be shown that the Fibonacci Sequence mod K is cyclic for all K, as each value is determined by the previous pair, and there are only K2 possible pairs of non-negative integers both less than K. Because the Fibonacci sequence mod K is cyclic after its first repeated pair of terms, a number which doesn't appear in the Fibonacci Sequence mod K before the first repeated pair of terms will never appear.

For K = 4

0 1 1 2 3 1 0 1 ...

For K = 8

0 1 1 2 3 5 0 5 5 2 7 1 0 1 ...

Notice that for K = 8, 4 and 6 do not appear before the repeated 0 1, so 4 and 6 will never appear in the Fibonacci Sequence mod 8.

# Challenge

Given an integer K strictly greater than 0, output all of the non-negative integers less than K that do not appear in the Fibonacci Sequence mod K.

# Rules

• You can assume that K will fit in your native integer type (within reason).

• If there are non-negative numbers less than K that do not appear in the Fibonacci Sequence mod K, your program/function should output all such numbers in any reasonable manner.

• If there are no non-negative integers less than K that do not appear in the Fibonacci Sequence mod K, your program/function may indicate this by returning an empty list, printing nothing, producing an error, etc.

• Order does not matter.

• This is , so shortest answer in each language wins.

# Test Cases

Generate test cases online!

## Non-Empty Test Cases

  8 [4, 6]
11 [4, 6, 7, 9]
12 [6]
13 [4, 6, 7, 9]
16 [4, 6, 10, 12, 14]
17 [6, 7, 10, 11]
18 [4, 6, 7, 9, 11, 12, 14]
19 [4, 6, 7, 9, 10, 12, 14]
21 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 19]
22 [4, 6, 7, 9, 15, 17, 18, 20]
23 [4, 7, 16, 19]
24 [4, 6, 9, 11, 12, 14, 15, 18, 19, 20, 22]
26 [4, 6, 7, 9, 17, 19, 20, 22]
28 [10, 12, 14, 16, 18, 19, 23]
29 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27]
31 [4, 6, 9, 12, 14, 15, 17, 18, 19, 22, 25, 29]
32 [4, 6, 10, 12, 14, 18, 20, 22, 26, 28, 30]
33 [4, 6, 7, 9, 15, 17, 18, 20, 24, 26, 27, 28, 29, 31]
34 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 28, 30]
36 [4, 6, 7, 9, 10, 11, 12, 14, 16, 18, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32]
37 [9, 10, 14, 17, 20, 23, 27, 28]
38 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 36]
39 [4, 6, 7, 9, 15, 17, 19, 20, 22, 24, 30, 32, 33, 35]
...
200 [4, 6, 12, 14, 20, 22, 28, 30, 36, 38, 44, 46, 52, 54, 60, 62, 68, 70, 76, 78, 84, 86, 92, 94, 100, 102, 108, 110, 116, 118, 124, 126, 132, 134, 140, 142, 148, 150, 156, 158, 164, 166, 172, 174, 180, 182, 188, 190, 196, 198]
...
300 [6, 18, 30, 42, 54, 66, 78, 90, 102, 114, 126, 138, 150, 162, 174, 186, 198, 210, 222, 234, 246, 258, 270, 282, 294]
...
400 [4, 6, 10, 12, 14, 20, 22, 26, 28, 30, 36, 38, 42, 44, 46, 52, 54, 58, 60, 62, 68, 70, 74, 76, 78, 84, 86, 90, 92, 94, 100, 102, 106, 108, 110, 116, 118, 122, 124, 126, 132, 134, 138, 140, 142, 148, 150, 154, 156, 158, 164, 166, 170, 172, 174, 180, 182, 186, 188, 190, 196, 198, 202, 204, 206, 212, 214, 218, 220, 222, 228, 230, 234, 236, 238, 244, 246, 250, 252, 254, 260, 262, 266, 268, 270, 276, 278, 282, 284, 286, 292, 294, 298, 300, 302, 308, 310, 314, 316, 318, 324, 326, 330, 332, 334, 340, 342, 346, 348, 350, 356, 358, 362, 364, 366, 372, 374, 378, 380, 382, 388, 390, 394, 396, 398]
...


## Empty Test Cases (no output, error, empty list, etc. is acceptable output)

1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35 ... 100 ...


### Related:

Counting Fibonacci Orbits

Find the Pisano Period

• Sandbox (deleted). Commented Jan 22, 2018 at 3:47

# Jelly, 9 8 bytes

²RÆḞ%ḟ@Ḷ


Try it online!

Based on the pisano period p(n) <= 6n from A001175. Also, p(n) <= 6n <= n^2 for n >= 6 and p(n) <= n^2 for n < 6. Saved this byte thanks to Dennis.

• ² should work instead of ×6. Commented Jan 22, 2018 at 12:57

# Haskell, 70 bytes

Some amount of bytes saved thanks to Esolanging Fruit

8 bytes saved thanks to Laikoni

a=1:scanl(+)1a
f x=[u|u<-[2..x-1],and[mod b x/=u|(_,b)<-zip[1..x^2]a]]


Try it online!

• @EsolangingFruit Ah thanks! I was just coming to a similar conclusion myself. Commented Jan 22, 2018 at 4:34
• read$show works instead of fromInteger in this case and saves two bytes. Commented Jan 23, 2018 at 1:37 • Using zip[1..x^2] for truncating saves some more bytes: Try it online! Commented Jan 23, 2018 at 1:47 • @Laikoni Took a while but I made the change. Thanks, that's a good idea. Commented Feb 2, 2018 at 23:36 # Perl 6, 43 42 39 32 bytes {^$_ (-)(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}  Test it {^$_∖(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}  Test it {^$_∖(1,1,(*+*)%$_...{!$^a&&$^b==1})}  Test it {^$_∖(1,1,(*+*)%$_...!*&*==1)}  Test it ## Expanded: { # bare block lambda with implicit parameter ｢$_｣

^$_ # Range upto and excluding the input ∖ # set minus (U+2216) ( # generate the Fibonacci sequence mod k 1, 1, # seed the sequece (can't be 0,1) ( * + * ) %$_  # add two values and modulus the input (lambda)

...             # keep doing that until

# it matches 0,1
!*              #   negate the first param (1 when 0)
&               #   and Junction
*               #   second param
== 1            #   both match 1

)
}


# ><>, 48 bytes

01\
?!\:&+{:}%:1$0p&$:
v0\~:1=?
>?!;1-::0g?!nao:


Try it online!

Takes input through the -v flag.

Prints a lot of excess newlines, but gets the job done. This basically uses the first line to store the set of numbers that have appeared so far in the sequence.

### How It Works:

01\    Input is already on the stack
...... Initialises the sequence with 1 and 0
...... Goes to the second line
......

......
..\:&+{:}% Gets the next number in the modded Fibonacci sequence while preserving the previous number
......
......

......
..........:1$0p&$: Puts a 1 at that cell number on the first line
.......
.......

......             If the number is a 0 go to the third line
?!\..............: Check if the next number is a 1, meaning we've reached the end of the sequence
v0\~:1=?           Go to the fourth line if so
>.....             Re-add the 0 and go back to the second line if not

......           While input:
......             Get the cell from the first line
......             If not 0: print the number
>?!;1-::0g?!nao:   Finally, print a newline and decrement the input


# Python 2, 69 bytes

m=input();r=set(range(m))
a=b=1
exec"a,b=b,a+b;r-={a%m};"*m*6
print r


Try it online!

# MATL, 19 18 bytes

0lbU:"yy+]vG\G:qX~


Try it online!

-1 byte thanks to Guiseppe.

  bU:"   ]         % Do K^2 (>6K) times.
0l    yy+          %  Fibbonaci
X~ % Set exclusive difference between
vG\      %  the fibonacci numbers mod K
G:q   %  and 0...K-1

• 18 bytes; rearranging recovers your use of X~! Commented Jan 22, 2018 at 15:30
• @Giuseppe Thanks! Still very long though.... Commented Jan 22, 2018 at 15:52

# Python 3, 91 bytes

lambda n:{*range(n)}-{*f(n*n,n)}
f=lambda c,m,l=[1,0]:f(c-1,m,[(l[0]+l[1])%m]+l)if c else l


Try it online!

# Husk, 13 12 10 bytes

Thanks @Zgarb for -2 bytes!

-U2m%⁰İfŀ⁰


Prints an empty list in case all integers appear, try it online!

### Explanation

-U2m%⁰İfŀ⁰  -- named argument ⁰, example with: 8
-           -- difference of
ŀ⁰  -- | lowered range: [0,1,2,3,4,5,6,7]
-- and
İf    -- | Fibonacci sequence: [1,1,2,3,5,8,13,21,34,55,89,144,233,377…
m%⁰      -- | map (modulo ⁰): [1,1,2,3,5,0,5,5,2,7,1,0,1,1…
U2         -- | keep longest prefix until 2 adjacent elements repeats: [1,1,2,3,5,0,5,5,2,7,1,0,1]
-- : [4,6]

• You can use U2 to get the longest prefix where no adjacent pair repeats. Commented Jan 22, 2018 at 8:44

# Python 3, 78 bytes

def m(K):M=0,1;exec(K*6*'M+=sum(M[-2:])%max(K,2),;'+'print({*range(K)}-{*M})')


Try it online!

Prints a set, so the output for empty test cases is set(), which is the empty set.

• 72 bytes as a full program
– ovs
Commented Jan 22, 2018 at 15:28
• @ovs you mean in Python 2, right? sure Commented Jan 22, 2018 at 15:38

# R, 92 86 bytes

Thanks to @Giuseppe for saving 6 bytes!

function(k,n=!!0:2){while(any((z=tail(n,2))-n[1:2]))n=c(n,sum(z)%%k);setdiff(1:k-1,n)}


Try it online!

Pretty straightforward implementation (previous version, but same concept):

function(k,
K=1:k-1,      #Uses default arguments to preset variables for legibility
n=c(0,1,1)){  #(wouldn't change byte-count to put them in the body of the function)
while(any((z=tail(n,2))!=n[1:2])) #Do as long as first 2 elements are not identical to last 2 elements
n=c(n,sum(z)%%k) #Built the fibonacci mod k sequence
K[!K%in%n] #Outputs integers < k if not in sequence.
}

• 86 bytes Commented Jan 22, 2018 at 14:40
• @Giuseppe ah setdiff, good idea! Commented Jan 22, 2018 at 14:44
• 70 bytes porting the 1:k^2 approach that everyone else uses Commented Jan 22, 2018 at 21:29

# Python 3,173152143 131 bytes

f=lambda n,m,a=0,b=1:a%m if n<=0else f(n-1,m,b,a+b)
p=lambda n,i=2,y={0}:y^{*range(n)}if f(i,n)==1>f(i-1,n)else p(n,i+1,y|{f(i,n)})


Special Thanks to @ovs.

Try It Online

How Does It Work?

The first function takes two parameters m and n, and it returns the nth Fibonacci number mod m. The second function loops through the Fibonacci numbers mod k and checks if 0 and 1 are repeated. It stores the numbers in a list and compares it with a list containing the numbers 1-n. The duplicate numbers are removed and the remaining numbers are returned.

• Its a part of the header and that is not compulsory to include in the code. Commented Jan 22, 2018 at 7:54
• Okay done. @ovs Thanks for telling, I was unaware of it. Commented Jan 22, 2018 at 10:15
• 131 bytes by creating sets with curly brackets instead of set() and chained comparisons.
– ovs
Commented Jan 22, 2018 at 14:51

# 05AB1E, 10 bytes

L<InLÅfI%K


Try it online!

-3 bytes thanks to Emigna.

• L<I6*LÅfI%K Commented Jan 22, 2018 at 11:09
• @Emigna I have been looking for that built-in for ages! Thanks! Commented Jan 22, 2018 at 11:12

# Ruby, 47 bytes

->n{a=b=1;[*1...n]-(1..n*n).map{a,b=b,a+b;a%n}}


Try it online!

While it uses some of the same logic, this is not based off G B's Answer.

## Explanation:

->n{
a=b=1;   # start sequence with 1,1
[*1...n] # all the numbers from 1 to n-1 as an array
# 0 is excluded as it should never be in the final answer
-  # set operation; get all items in the first set and not in the second
(1..n*n).map{ # n squared times
a,b=b,a+b;  # assign next fibonacci numbers
a%n         # return a fibonacci number mod n
}    # Map to an array
}


# Common Lisp, 106 bytes

(lambda(k)(do((a 1 b)c(b 1(mod(+ a b)k)))((=(1- b)0 a)(dotimes(i k)(or(member i c)(print i))))(push a c)))


Try it online!

# Vyxal, 9 bytes

ʁ⁰²ɾ∆f⁰%F


Try it Online!

## How?

ʁ⁰²ɾ∆f⁰%F
# (implicit input)
ʁ          # Exclusive zero range [0, n)
⁰²        # Input squared
ɾ       # Inclusive one range [1, n]
∆f     # Nth fibonacci number (implicit vectorization)
⁰%   # Modulo with input
F  # Remove all values from this list in the other list


# Elixir, 148 144 bytes

 fn x->Enum.to_list(1..x-1)--List.flatten Enum.take_while Stream.chunk(Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end),2),&Enum.sum(&1)!=1end


Try it online!

Not an especially competitive answer, but was really fun to golf! Elixir is a pretty readable language, but an explanation for the the mess of characters in the middle follows.

This explanation is in two sections, the mod-fibonacci and the operating on it

Mod-fib:

Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end)


This returns an infinite stream of fibonacci mod x. It starts with an accumulator {1,1}, and applies the following operation ad infinitum: given accumulator {p,n}, output p mod x to the stream. Then, set the accumulator to {n,p+n}.

The rest:

fn x->                              Define a fxn f(x) that returns
Enum.to_list(1..x-1)--            The numbers from 1..x-1 that are not in
List.flatten                      The flattened list constructed by
Enum.take_while                 Taking from mod-fib until
Stream.chunk(                 A 2-size chunk
Stream.unfold({1,1},fn{p,n}->{rem(p,x),{n,p+n}}end) (of mod fib)
,2)
,&Enum.sum(&1)!=1             sums to 1, representing [0,1] or [1,0]
end


# SNOBOL4 (CSNOBOL4), 153 bytes

 k =input
a =table()
y =1
i z =remdr(x + y,k)
a<z> =1
x =y
y =z
i =lt(i,k * 6) i + 1 :s(i)
o output =eq(a<o>) lt(o,k) o
o =lt(o,k) o + 1 :s(o)
end


Try it online!

# Ruby, 55 53 bytes

->n{*a=0,b=1;(n*n).times{a<<(b+=a[-2])%n};[*1...n]-a}


Try it online!

# JavaScript (ES6), 84 bytes

f=(n,a=0,b=1,q=[...Array(n).keys()])=>a*b+a-1?f(n,b,(a+b)%n,q,q[b]=0):q.filter(x=>x)


# Python 3, 76 bytes

def t(n,r=[1]):
while n*n>len(r):r+=[sum(r[-2:])%n]
return{*range(n)}-{*r}


This simply looks over the longest possible cycle of Fibonnaci numbers (n^2), and creates a list of all numbers that occur in that time. To simplify logic the numbers are stored modulo n.

# Pari/GP, 49 bytes

n->[k|k<-[0..n-1],prod(i=0,n^2,k-fibonacci(i)%n)]


Try it online!