Zainspirowany to pytanie Math.SE .

tło

Fibonacciego (zwany F) sekwencję rozpoczynając 0, 1taki sposób, że każdy numer ( F(n)) (po pierwszych dwóch) jest sumą dwóch przed nim ( F(n) = F(n-1) + F(n-2)).

Sekwencja Fibonacciego mod K (nazywana M) jest sekwencją liczb Fibonacciego mod K ( M(n) = F(n) % K).

Można wykazać, że F Sekwencja Fibonacciego mod K jest cykliczna dla wszystkich K, ponieważ każda wartość jest określona przez poprzednią parę, i istnieje tylko K ² możliwych par liczb całkowitych nieujemnych, obie mniejsze niż K. Ponieważ sekwencja Fibonacciego mod K jest cykliczny po pierwszej powtórzonej parze terminów, liczba, która nie pojawia się w modie F Sekwencji Fibonacciego, zanim pierwsza powtarzająca się para terminów nigdy się nie pojawi.

Dla K = 4

0 1 1 2 3 1 0 1 ...

Dla K = 8

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

Zauważ, że dla K = 8, 4 i 6 nie pojawiają się przed powtórzeniem 0 1, więc 4 i 6 nigdy nie pojawią się w Fibonacciego Modie 8.

Wyzwanie

Biorąc pod uwagę liczbę całkowitą K ściśle większą niż 0, wypisz wszystkie nieujemne liczby całkowite mniejsze niż K, które nie pojawiają się w modie Sekwencji Fibonacciego K.

Zasady

• Domyślne luki są zabronione .

• Domyślnie I / O .

• Programy lub funkcje są dopuszczalne .

• Możesz założyć, że K zmieści się w twoim rodzimym typie liczb całkowitych ( w granicach rozsądku ).

• Jeśli istnieją liczby nieujemne mniejsze niż K, które nie pojawiają się w F Sekwencji Fibonacciego mod K, twój program / funkcja powinna wypisać wszystkie takie liczby w jakikolwiek rozsądny sposób.

• Jeśli nie ma nieujemnych liczb całkowitych mniejszych niż K, które nie pojawiają się w modie Sekwencji Fibonacciego K, twój program / funkcja może to wskazać, zwracając pustą listę, nic nie drukując, powodując błąd itp.

• Porządek nie ma znaczenia.

• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w każdym języku.

Przypadki testowe

Generuj przypadki testowe online!

Niepuste skrzynki testowe

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

Puste przypadki testowe (brak danych wyjściowych, błąd, pusta lista itp. Jest akceptowalnym wynikiem)

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

Związane z:

Liczenie orbit Fibonacciego

Znajdź okres Pisano

Galaretka , 9 8 bajtów

²RÆḞ%ḟ@Ḷ

Wypróbuj online!

Na podstawie okresu pisanop(n) <= 6n z A001175 . Również p(n) <= 6n <= n^2dla n >= 6i p(n) <= n^2dla n < 6. Ten bajt uratował dzięki Dennis.

Haskell , 70 bajtów

Oszczędność pewnej ilości bajtów dzięki Esolanging Fruit

8 bajtów zapisanych dzięki Laikoni

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

Wypróbuj online!

Perl 6 ,  43 42 39  32 bajtów

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

Sprawdź to

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

Sprawdź to

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

Sprawdź to

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

Sprawdź to

Rozszerzony:

{  # 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 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe poprzez flagę -v.

Drukuje dużo nadmiarowych linii, ale wykonuje zadanie. Zasadniczo używa pierwszego wiersza do przechowywania zestawu liczb, które pojawiły się do tej pory w sekwencji.

Jak to działa:

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 bajtów

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

Wypróbuj online!

MATL , 19 18 bajtów

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

Wypróbuj online!

-1 bajt dzięki 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 bajtów

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

Wypróbuj online!

Łuska , 13 12 10 bajtów

Dzięki @Zgarb za -2 bajty!

-U2m%⁰İfŀ⁰

Drukuje pustą listę na wypadek, gdyby pojawiły się wszystkie liczby całkowite, spróbuj online!

Wyjaśnienie

-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 bajtów

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

Wypróbuj online!

Drukuje zestaw, więc wyjściem dla pustych przypadków testowych jest set(), który jest pustym zestawem.

R 92 92 bajtów

Dzięki @Giuseppe za zapisanie 6 bajtów!

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

Wypróbuj online!

Dość prosta implementacja ( poprzednia wersja , ale ta sama koncepcja):

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 bajtów

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

Specjalne podziękowania dla @ovs.

Wypróbuj online

Jak to działa?

Pierwsza funkcja przyjmuje dwa parametry min, i zwraca n-tą liczbę Fibonacciego mod m. Druga funkcja zapętla mod Fibonacciego mod k i sprawdza, czy 0 i 1 są powtarzane. Przechowuje liczby na liście i porównuje je z listą zawierającą liczby 1-n. Zduplikowane numery są usuwane, a pozostałe numery są zwracane.

05AB1E , 10 bajtów

L<InLÅfI%K

Wypróbuj online!

-3 bajty dzięki Emignie.

Ruby , 47 bajtów

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

Wypróbuj online!

Chociaż wykorzystuje tę samą logikę, nie jest to oparte na odpowiedzi GB .

Wyjaśnienie:

->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 bajtów

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

Wypróbuj online!

Pari / GP , 55 bajtów

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

Wypróbuj online!

Eliksir , 148 144 bajtów

 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

Wypróbuj online!

Niezbyt konkurencyjna odpowiedź, ale gra w golfa była naprawdę fajna! Eliksir jest dość czytelnym językiem, ale wyjaśniono bałagan znaków na środku.

Wyjaśnienie to składa się z dwóch części: mod-fibonacci i operacji na nim

Mod-fib:

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

Zwraca to nieskończony strumień modów Fibonacciego x. Zaczyna się od akumulatora {1,1}i stosuje następującą operację ad infinitum: dany akumulator {p,n}, wyjście p mod xdo strumienia. Następnie ustaw akumulator na {n,p+n}.

Reszta:

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 bajty

 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

Wypróbuj online!

Rubinowy , 55 53 bajtów

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

Wypróbuj online!

JavaScript (ES6), 84 bajtów

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 bajtów

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

Po prostu przegląda najdłuższy możliwy cykl liczb Fibonnaci (n ^ 2) i tworzy listę wszystkich liczb, które występują w tym czasie. Aby uprościć logikę, numery są przechowywane w module.