20
\$\begingroup\$

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

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

\$\endgroup\$

20 Answers 20

6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ ² should work instead of ×6. \$\endgroup\$ – Dennis Jan 22 '18 at 12:57
6
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @EsolangingFruit Ah thanks! I was just coming to a similar conclusion myself. \$\endgroup\$ – Sriotchilism O'Zaic Jan 22 '18 at 4:34
  • \$\begingroup\$ read$show works instead of fromInteger in this case and saves two bytes. \$\endgroup\$ – Laikoni Jan 23 '18 at 1:37
  • \$\begingroup\$ Using zip[1..x^2] for truncating saves some more bytes: Try it online! \$\endgroup\$ – Laikoni Jan 23 '18 at 1:47
  • \$\begingroup\$ @Laikoni Took a while but I made the change. Thanks, that's a good idea. \$\endgroup\$ – Sriotchilism O'Zaic Feb 2 '18 at 23:36
5
\$\begingroup\$

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

  )
}
\$\endgroup\$
3
\$\begingroup\$

><>, 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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 18 bytes; rearranging recovers your use of X~! \$\endgroup\$ – Giuseppe Jan 22 '18 at 15:30
  • \$\begingroup\$ @Giuseppe Thanks! Still very long though.... \$\endgroup\$ – Sanchises Jan 22 '18 at 15:52
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ You can use U2 to get the longest prefix where no adjacent pair repeats. \$\endgroup\$ – Zgarb Jan 22 '18 at 8:44
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 86 bytes \$\endgroup\$ – Giuseppe Jan 22 '18 at 14:40
  • \$\begingroup\$ @Giuseppe ah setdiff, good idea! \$\endgroup\$ – plannapus Jan 22 '18 at 14:44
  • \$\begingroup\$ 70 bytes porting the 1:k^2 approach that everyone else uses \$\endgroup\$ – Giuseppe Jan 22 '18 at 21:29
2
\$\begingroup\$

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.

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

05AB1E, 10 bytes

L<InLÅfI%K

Try it online!

-3 bytes thanks to Emigna.

\$\endgroup\$
  • \$\begingroup\$ L<I6*LÅfI%K \$\endgroup\$ – Emigna Jan 22 '18 at 11:09
  • \$\begingroup\$ @Emigna I have been looking for that built-in for ages! Thanks! \$\endgroup\$ – Mr. Xcoder Jan 22 '18 at 11:12
2
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 55 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 55 53 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.