Inspirado por esta pregunta Math.SE .

Antecedentes

La secuencia de Fibonacci (llamada F) es la secuencia, comenzando de 0, 1tal manera que cada número (F(n) ) (después de los dos primeros) es la suma de los dos anteriores ( F(n) = F(n-1) + F(n-2)).

Una secuencia de Fibonacci mod K (llamada M) es la secuencia de los números de Fibonacci mod K ( M(n) = F(n) % K).

Se puede demostrar que la secuencia de Fibonacci mod K es cíclica para todo K, ya que cada valor está determinado por el par anterior, y solo hay K ² posibles pares de enteros no negativos, ambos menos que K. Debido a que la secuencia de Fibonacci mod K es cíclico después de su primer par de términos repetidos, un número que no aparece en la secuencia de Fibonacci mod K antes de que nunca aparezca el primer par de términos repetidos.

Para K = 4

0 1 1 2 3 1 0 1 ...

Para K = 8

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

Tenga en cuenta que para K = 8, 4 y 6 no aparecen antes de la repetición 0 1 , por lo que 4 y 6 nunca aparecerán en la secuencia 8 de Fibonacci mod.

Desafío

Dado un entero K estrictamente mayor que 0, genera todos los enteros no negativos menores que K que no aparecen en la secuencia de Fibonacci mod K.

Reglas

• Las lagunas predeterminadas están prohibidas .

• E / S por defecto .

• Los programas o funciones son aceptables .

• Puede suponer que K encajará en su tipo entero nativo ( dentro de lo razonable ).

• Si hay números no negativos menores que K que no aparecen en la secuencia de Fibonacci mod K, su programa / función debería generar todos esos números de manera razonable.

• Si no hay enteros no negativos menores que K que no aparecen en la secuencia de Fibonacci mod K, su programa / función puede indicar esto devolviendo una lista vacía, sin imprimir nada, produciendo un error, etc.

• El orden no importa.

• Este es el código de golf , por lo que gana la respuesta más corta en cada idioma.

Casos de prueba

¡Genere casos de prueba en línea!

Casos de prueba no vacíos

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

Casos de prueba vacíos (sin salida, error, lista vacía, etc., es un resultado aceptable)

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

Relacionado:

Contando las órbitas de Fibonacci

Encuentra el período de Pisano

Jalea , 9 8 bytes

²RÆḞ%ḟ@Ḷ

Pruébalo en línea!

Basado en el período pisano p(n) <= 6ndesde A001175 . Además, p(n) <= 6n <= n^2por n >= 6y p(n) <= n^2para n < 6. Guardado este byte gracias a Dennis.

Haskell , 70 bytes

Cierta cantidad de bytes guardados gracias a Esolanging Fruit

8 bytes guardados gracias a Laikoni

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

Pruébalo en línea!

Perl 6 ,  43 42 39  32 bytes

{^$_ (-)(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

Pruébalo

{^$_∖(1,1,(*+*)%$_...->\a,\b{!a&&b==1})}

Pruébalo

{^$_∖(1,1,(*+*)%$_...{!$^a&&$^b==1})}

Pruébalo

{^$_∖(1,1,(*+*)%$_...!*&*==1)}

Pruébalo

Expandido:

{  # 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:

Pruébalo en línea!

Toma entrada a través de la bandera -v.

Imprime una gran cantidad de líneas nuevas en exceso, pero hace el trabajo. Básicamente, esto usa la primera línea para almacenar el conjunto de números que han aparecido hasta ahora en la secuencia.

Cómo funciona:

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

Pruébalo en línea!

MATL , 19 18 bytes

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

Pruébalo en línea!

-1 byte gracias a 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

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

Pruébalo en línea!

cascarilla , 13 12 10 bytes

¡Gracias @Zgarb por -2 bytes!

-U2m%⁰İfŀ⁰

Imprime una lista vacía en caso de que aparezcan todos los enteros, pruébelo en línea!

Explicación

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

Python 3 , 78 bytes

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

Pruébalo en línea!

Imprime un conjunto, por lo que la salida para casos de prueba vacíos es set(), que es el conjunto vacío.

R, 92 86 bytes

¡Gracias a @Giuseppe por guardar 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)}

Pruébalo en línea!

Implementación bastante sencilla ( versión anterior , pero el mismo concepto):

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

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

Un agradecimiento especial a @ovs.

Pruébalo en línea

¿Como funciona?

La primera función toma dos parámetros myn, y devuelve el enésimo número de Fibonacci mod m. La segunda función recorre los números de Fibonacci mod k y comprueba si 0 y 1 se repiten. Almacena los números en una lista y lo compara con una lista que contiene los números 1-n. Se eliminan los números duplicados y se devuelven los números restantes.

05AB1E , 10 bytes

L<InLÅfI%K

Pruébalo en línea!

-3 bytes gracias a Emigna.

Ruby , 47 bytes

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

Pruébalo en línea!

Si bien utiliza parte de la misma lógica, esto no se basa en la respuesta de GB .

Explicación:

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

Lisp común, 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)))

Pruébalo en línea!

Pari / GP , 55 bytes

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

Pruébalo en línea!

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

Pruébalo en línea!

No es una respuesta especialmente competitiva, ¡pero fue muy divertido jugar al golf! Elixir es un lenguaje bastante legible, pero sigue una explicación del desorden de los personajes en el medio.

Esta explicación está en dos secciones, el mod-fibonacci y el funcionamiento en él.

Mod-fib:

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

Esto devuelve una corriente infinita de mod de Fibonacci x. Comienza con un acumulador {1,1}y aplica la siguiente operación hasta el infinito: acumulador dado {p,n}, salida p mod xa la secuencia. Luego, configure el acumulador en{n,p+n} .

El resto:

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

Pruébalo en línea!

Ruby , 55 53 bytes

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

Pruébalo en línea!

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}

Esto simplemente examina el ciclo más largo posible de números de Fibonnaci (n ^ 2) y crea una lista de todos los números que ocurren en ese momento. Para simplificar la lógica, los números se almacenan en el módulo n.