Najpierw porozmawiajmy o sekwencjach Beatty . Biorąc pod uwagę dodatnią liczbę niewymierną r , możemy skonstruować nieskończoną sekwencję poprzez pomnożenie dodatnich liczb całkowitych do r w kolejności i zabranie głosu za każde wynikowe obliczenie. Na przykład,

Jeśli r > 1, mamy specjalny warunek. Możemy utworzyć inną liczbę niewymierną s jako s = r / ( r - 1). To może następnie wygenerować jego własnej sekwencji Beatty, B _y . Schludny Sztuką jest to, że B _R i B _s są komplementarne , co oznacza, że każda dodatnia jest dokładnie w jednym z dwóch sekwencji.

Jeśli ustawimy r = ϕ, złoty stosunek, otrzymamy s = r + 1 i dwie specjalne sekwencje. Mniejsza sekwencja Wythoff do R :

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... 

i górna sekwencja Wythoffa dla s :

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... 

Są to odpowiednio sekwencje A000201 i A001950 w OEIS.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą wejściową 1 <= n <= 1000, wyślij jedną z dwóch różnych wartości wskazujących, czy dane wejściowe są w dolnej sekwencji Wythoffa czy w górnej sekwencji. Wartościami wyjściowymi mogą być -1i 1, truei false, upperi loweritd.

Chociaż przesłany algorytm musi teoretycznie działać dla wszystkich danych wejściowych, w praktyce musi on działać tylko z pierwszymi 1000 liczbami wejściowymi.

I / O i reguły

• Dane wejściowe i wyjściowe można podać dowolną dogodną metodą .
• Można założyć, że dane wejściowe i wyjściowe pasują do rodzimego typu liczb w twoim języku.
• Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je drukować.
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

JavaScript (ES6), 50 35 bajtów

f=(n,s="1",t=0)=>s[n-1]||f(n,s+t,s)

<input type=number min=1 oninput=o.textContent=this.value&amp;&amp;f(this.value)><pre id=o>

Wyjścia 1dla dolnej i 0górnej. Objaśnienie: Częściowa wykazy wartości logicznych może być wykonana przy użyciu Fibonacciego jak tożsamość: podany dwa wykazy, począwszy 1i 10każda następna lista jest połączeniem dwóch poprzednich, w wyniku czego 101,10110 , 10110101itd. W tym przypadku jest to nieco golfier mieć fałszywy 0 wpis 0i użyj go do skonstruowania drugiego elementu listy.

Haskell , 26 bajtów

(l!!)
l=0:do x<-l;[1-x..1]

Wypróbuj online!

Bez pływaków, nieograniczona precyzja. Dzięki za H.PWiz za dwa bajty.

Python , 25 bajtów

lambda n:-n*2%(5**.5+1)<2

Wypróbuj online!

Wykorzystuje bardzo prosty warunek:

njest w dolnej sekwencji Wythoffa dokładnie, jeśli -n%phi<1.

Zauważ, że wynik modulo jest dodatni, chociaż -nujemny, co odpowiada modulo w Pythonie.

Dowód: Let a = -n%phi, który leży w przedziale 0 <= a < phi. Możemy podzielić -nmodulo phijak -n = -k*phi + ana pewną dodatnią liczbę całkowitą k. Zmień to nan+a = k*phi .

Jeśli a<1takn = floor(n+a) = floor(k*phi) i tak jest w dolnej sekwencji Wythoffa.

W przeciwnym razie mamy 1 <= a < phito

n+1 = floor(n+a) = floor(k*phi)
n > n+a-phi = k*phi - phi = (k-1)*phi

dlatego nmieści się w szczelinie pomiędzy floor((k-1)*phi)a floor(k*phi) i pominięcia przez dolną sekwencji Wythoff.

Odpowiada to kodowi:

lambda n:-n%(5**.5/2+.5)<1

Wypróbuj online!

Oszczędzamy bajt, podwajając do -(n*2)%(phi*2)<2.

05AB1E , 9 bajtów

L5t>;*óså

Wypróbuj online!

0 oznacza górny, 1 oznacza dolny. Wypróbuj pierwsze 100: Wypróbuj online!

    CODE   |      COMMAND      # Stack (Input = 4)
===========+===================#=======================
L          | [1..a]            # [1,2,3,4]
 5t>;      | (sqrt(5) + 1)/2   # [phi, [1,2,3,4]]
     *     | [1..a]*phi        # [[1.6,3.2,4.8,6.4]]
      ó    | floor([1..a]*phi) # [[1,3,4,6]]
       så  | n in list?        # [[1]]

Surowy zrzut poleceń:

----------------------------------
Depth: 0
Stack: []
Current command: L

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4]]
Current command: 5

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], '5']
Current command: t

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 2.23606797749979]
Current command: >

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 3.23606797749979]
Current command: ;

----------------------------------
Depth: 0
Stack: [[1, 2, 3, 4], 1.618033988749895]
Current command: *

----------------------------------
Depth: 0
Stack: [[1.618033988749895, 3.23606797749979, 4.854101966249685, 6.47213595499958]]
Current command: ó

----------------------------------
Depth: 0
Stack: [[1, 3, 4, 6]]
Current command: s

----------------------------------
Depth: 0
Stack: [[1, 3, 4, 6], '4']
Current command: å
1
stack > [1]

Galaretka , 5 bajtów

N%ØpỊ

Wypróbuj online!

Zaoszczędzono 1 bajt dzięki xnor's Python golf .

Galaretka , 6 bajtów

×€ØpḞċ

Wypróbuj online!

Zwraca 1 dla dolnej i 0 dla górnej.

×€ØpḞċ – Full Program / Monadic Link. Argument: N.
×€     – Multiply each integer in (0, N] by...
  Øp   – Phi.
    Ḟ  – Floor each of them.
     ċ – And count the occurrences of N in that list.

$(0,\:N]\cap \mathbb{Z}$$\varphi > 1$$N > 0$$0 < N < N\varphi$

Brain-Flak , 78 bajtów

([{}]()){<>{}((([()]))){{<>({}())}{}(([({})]({}{})))}<>([{}]{}<>)}<>({}()){{}}

Wypróbuj online!

Nie wyprowadza nic dla dolnego i 0górnego. Przejście na bardziej rozsądny schemat wyjściowy kosztuje 6 bajtów.

Python 2 , 39 33 32 bajty

^{-6 bajtów dzięki Mr. Xcoder
-1 bajtów dzięki Zacharýmu}

lambda n,r=.5+5**.5/2:-~n//r<n/r

Wypróbuj online!

Zwraca Falsedolną i Truegórną

Julia 0.6 , 16 bajtów

n->n÷φ<-~n÷φ

Wypróbuj online!

Podczas zabawy z liczbami natknąłem się na tę właściwość: floor (n / φ) == floor ((n + 1) / φ), jeśli n jest w górnej sekwencji Wythoffa, a floor (n / φ) <floor ( (n + 1) / φ), jeśli n jest w dolnej sekwencji Wythoffa. Nie zorientowałem się, jak ta właściwość się pojawia, ale daje prawidłowe wyniki co najmniej do n = 100000 (i prawdopodobnie więcej).

Stara odpowiedź:

Julia 0.6 , 31 bajtów

n->n∈[floor(i*φ)for i∈1:n]

Wypróbuj online!

Zwraca truedla dolnej i falsegórnej sekwencji Wythoffa.

Pyth , 8 bajtów

/sM*.n3S

Wypróbuj tutaj!

Zwraca 1 dla dolnej i 0 dla górnej.

Wolfram Language (Mathematica) , 26 bajtów

#~Ceiling~GoldenRatio<#+1&

Wypróbuj online!

Liczba całkowita nznajduje się w dolnej sekwencji Wythoffa iff ceil(n/phi) - 1/phi < n/phi.

Dowód, że ceil(n/phi) - 1/phi < n/phi...

Wystarczający:

1. Let ceil(n/phi) - 1/phi < n/phi.

2. Potem ceil(n/phi) * phi < n + 1.

3. Uwaga n == n/phi * phi <= ceil(n/phi) * phi.

4. Dlatego też n <= ceil(n/phi) * phi < n + 1.

5. Ponieważ ni ceil(n/phi)są liczbami całkowitymi, odwołujemy się do definicji floor i state floor(ceil(n/phi) * phi) == n, i nznajduje się w dolnej sekwencji Wythoffa.

Niezbędny; dowód antykoncepcyjny:

1. Let ceil(n/phi) - 1/phi >= n/phi.

2. Potem ceil(n/phi) * phi >= n + 1.

3. Uwaga n + phi > (n/phi + 1) * phi > ceil(n/phi) * phi

4. Stąd n > (ceil(n/phi) - 1) * phi.

5. Ponieważ (ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi, nnie jest w dolnej sekwencji Wythoff.

Japt , 10 bajtów

Zwraca true dla dolnej i false dla górnej.

õ_*MQ fÃøU

Wypróbuj online!

Wyjaśnienie:

õ_*MQ fÃøU
             // Implicit U = Input
õ            // Range [1...U]
 _           // Loop through the range, at each element:
  *MQ        //   Multiply by the Golden ratio
      f      //   Floor
       Ã     // End Loop
        øU   // Return true if U is found in the collection

Java 10, 77 53 52 bajty

n->{var r=Math.sqrt(5)/2+.5;return(int)(-~n/r)<n/r;}

Odpowiedź na Python 2 dla portu @ Rod .
-1 bajt dzięki @ Zacharý .

Wypróbuj online.

Stara 77 76 bajtów odpowiedź:

n->{for(int i=0;i++<n;)if(n==(int)((Math.sqrt(5)+1)/2*i))return 1;return 0;}

-1 bajt dzięki @ovs za coś co poleciłem sobie w zeszłym tygodniu .. xD

Zwroty 1 za niższe;0do cholewki.

Wypróbuj online.

Wyjaśnienie:

n->{                    // Method with integer as both parameter and return-type
  for(int i=0;++i<=n;)  //  Loop `i` in the range [1, `n`]
    if(n==(int)((Math.sqrt(5)+1)/2*i))
                        //   If `n` is equal to `floor(Phi * i)`:
      return 1;         //    Return 1
  return 0;}            //  Return 0 if we haven't returned inside the loop already

i*Phijest obliczany na podstawie wzięcia (sqrt(5)+1)/2 * i, a następnie wprowadzamy wartość podłogową, rzucając ją na liczbę całkowitą w celu obcięcia dziesiętnego.

Haskell , 153 139 126 79 bajtów

Nieograniczona precyzja!

l=length
f a c|n<-2*l a-c,n<0||l a<a!!n=c:a|1>0=a
g x=x==(foldl f[][1..x+1])!!0

Wypróbuj online!

Wyjaśnienie

Zamiast używać przybliżenia złotego współczynnika do obliczania wyniku, co oznacza, że ​​są podatne na błędy wraz ze wzrostem wielkości wejściowej. Ta odpowiedź nie. Zamiast tego wykorzystuje wzór podany w OEIS, który ajest unikalną sekwencją taką, że

∀n . b(n) = a(a(n))+1

gdzie bjest zamówiony komplement.

Brachylog , 8 bajtów

≥ℕ;φ×⌋₁?

Wypróbuj online!

Predykat się powiedzie, jeśli dane wejściowe znajdują się w dolnej sekwencji Wythoffa, a porażki, jeśli będą w górnej sekwencji Wythoffa.

 ℕ          There exists a whole number
≥           less than or equal to
            the input such that
  ;φ×       multiplied by phi
     ⌋₁     and rounded down
       ?    it is the input.

Jeśli niepowodzeniem zakończenia jest poprawna metoda wyjściowa, pierwszy bajt można pominąć.

MATL , 8 bajtów

t:17L*km

Wypróbuj online!

Wyjaśnienie

t      % Implicit input. Duplicate
:      % Range
17L    % Push golden ratio (as a float)
*      % Multiply, element-wise
k      % Round down, element-wise
m      % Ismember. Implicit output

K (oK) , 20 bajtów

Rozwiązanie:

x in_(.5*1+%5)*1+!x:

Wypróbuj online!

Wyjaśnienie:

x in_(.5*1+%5)*1+!x: / the solution
                  x: / save input as x
                 !   / generate range 0..x
               1+    / add 1
              *      / multiply by
     (       )       / do this together
           %5        / square-root of 5
         1+          / add 1
      .5*            / multiply by .5
    _                / floor
x in                 / is input in this list?

TI-BASIC (TI-84), 18 bajtów

max(Ans=iPart((√(5)+1)/2randIntNoRep(1,Ans

Wejście jest w Ans.
Wyjście jest włączone Ansi jest drukowane automatycznie.
Wydruki1 jeśli dane wejściowe są w dolnej sekwencji lub0 jeśli jest w górnej sekwencji.

Przypadkowo ten program będzie działał tylko dla $0<N<1000$ .

Przykład:

27
             27
prgmCDGFA
              1
44
             44
prgmCDGFA
              0

Wyjaśnienie:

max(Ans=iPart((√(5)+1)/2randIntNoRep(1,Ans    ;full program, example input: 5
                        randIntNoRep(1,Ans    ;generate a list of random integers in [1,Ans]
                                               ; {1, 3, 2, 5, 4}
              (√(5)+1)/2                      ;calculate phi and then multiply the resulting
                                              ;list by phi
                                               ; {1.618 4.8541 3.2361 8.0902 6.4721}
        iPart(                                ;truncate
                                               ; {1 4 3 8 6}
    Ans=                                      ;compare the input to each element in the list
                                              ;and generate a list based off of the results
                                               ; {0 0 0 0 0}
max(                                          ;get the maximum element in the list and
                                              ;implicitly print it

Uwaga: TI-BASIC jest językiem tokenizowanym. Liczba znaków nie jest równa liczbie bajtów.

cQuents , 5 bajtów

?F$`g

Wypróbuj online!

Wyjaśnienie

?         output true if in sequence, false if not in sequence
          each term in the sequence equals:

 F        floor (
  $               index * 
   `g                     golden ratio
     )                                 ) implicit