Find the Missing Numbers in the Fibonacci Sequence Mod K

Question

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 K² 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

• Default loopholes are forbidden.

• Default I/O.

• Programs or functions are acceptable.

• 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 code-golf, 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

Answer 1

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!

Answer 2

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.

Answer 3

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

  )
}

Answer 4

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

Answer 5

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!

Answer 6

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

Answer 7

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]

Answer 8

Python 3,173 152 143 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.

Answer 9

05AB1E, 10 bytes

L<InLÅfI%K

Try it online!

-3 bytes thanks to Emigna.

Answer 10

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!

Answer 11

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.
}

Answer 12

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.

Answer 13

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
}

Answer 14

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!

Answer 15

Ruby, 55 53 bytes

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

Try it online!

Answer 16

Pari/GP, 55 bytes

n->setminus([0..n-1],Set([fibonacci(i)%n|i<-[0..n^2]]))

Try it online!

Answer 17

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

Answer 18

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!

Answer 19

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)

Answer 20

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.