Lassen Sie uns zunächst über Beatty-Sequenzen sprechen . Eine positive irrationale Zahl gegeben r , können wir eine unendliche Folge durch Multiplikation der positiven ganzen Zahlen konstruieren , r , um und unter dem Boden jeder resultierenden Berechnung. Beispielsweise,

Wenn r > 1, haben wir eine spezielle Bedingung. Wir können eine andere irrationale Zahl s als s = r / ( r - 1) bilden. Dies kann dann seine eigene Beatty-Sequenz B _s erzeugen . Die unverdünnte Trick ist , dass B _r und B _s sind komplementär , was bedeutet , dass jede positive ganze Zahl in genau einer der beiden Sequenzen ist.

Wenn wir r = ϕ, den goldenen Schnitt, setzen, erhalten wir s = r + 1 und zwei Spezialsequenzen. Die untere Wythoff-Sequenz für r :

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

und die obere Wythoff-Sequenz für s :

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

Dies sind die Sequenzen A000201 und A001950 auf OEIS.

Die Herausforderung

Bei einer positiven Ganzzahl 1 <= n <= 1000geben Sie einen von zwei unterschiedlichen Werten aus, die angeben, ob sich die Eingabe in der unteren Wythoff-Sequenz oder in der oberen Sequenz befindet. Die Ausgabewerte könnten -1und 1, trueund false, upperund lowerusw. sein.

Obwohl Ihr eingereichter Algorithmus theoretisch für alle Eingaben funktionieren muss, muss er in der Praxis nur mit den ersten 1000 Eingabenummern funktionieren.

I / O und Regeln

• Die Eingabe und Ausgabe kann durch jede bequeme Methode erfolgen .
• Es kann davon ausgegangen werden, dass die Eingabe und Ausgabe in den Native-Number-Typ Ihrer Sprache passt.
• Es ist entweder ein vollständiges Programm oder eine Funktion zulässig. Bei einer Funktion können Sie die Ausgabe zurückgeben, anstatt sie zu drucken.
• Standardlücken sind verboten.
• Dies ist Codegolf, daher gelten alle üblichen Golfregeln, und der kürzeste Code (in Byte) gewinnt.

JavaScript (ES6), 50 35 Bytes

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>

Ausgänge 1für unteres und 0für oberes. Erläuterung: Teillisten Boolesche Werte können mit einem Fibonacci-like konstruiert werden Identität: Da zwei Listen, beginnend mit 1und 10jeder nachfolgende Liste ist die Verkettung der beiden vorangegangenen, was 101, 10110, 10110101usw. In diesem Fall Golfier es ist leicht zu haben ein gefälschter 0. Eintrag von 0und benutze diesen, um das zweite Element der Liste zu konstruieren.

Haskell , 26 Bytes

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

Probieren Sie es online!

Keine Schwimmer, unbegrenzte Präzision. Danke für H.PWiz für zwei Bytes.

Python , 25 Bytes

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

Probieren Sie es online!

Verwendet die sehr einfache Bedingung:

nist in der unteren Wythoff-Sequenz genau wenn -n%phi<1.

Beachten Sie, dass das Modulo-Ergebnis positiv ist, obwohl -nes negativ ist. Dies entspricht der Vorgehensweise von Python bei Modulo.

Beweis: Lass a = -n%phi, was im Bereich liegt 0 <= a < phi. Wir können -nModulo phiwie -n = -k*phi + aeine positive ganze Zahl teilen k. Ordne das neu an n+a = k*phi.

Wenn a<1, dann n = floor(n+a) = floor(k*phi)und so ist in der unteren Wythoff-Sequenz.

Ansonsten haben wir 1 <= a < phiso

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

so nfällt die Lücke zwischen floor((k-1)*phi)und floor(k*phi) und wird von der unteren Wythoff-Sequenz verfehlt.

Dies entspricht diesem Code:

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

Probieren Sie es online!

Wir sparen ein Byte, indem wir auf verdoppeln -(n*2)%(phi*2)<2.

05AB1E , 9 Bytes

L5t>;*óså

Probieren Sie es online!

0 bedeutet oben, 1 bedeutet unten. Probieren Sie die ersten 100: Probieren Sie es 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]]

Raw-Befehlsspeicherauszug:

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

Gelee , 5 Bytes

N%ØpỊ

Probieren Sie es online!

Dank xnors Python-Golf 1 Byte gespart .

Gelee , 6 Bytes

×€ØpḞċ

Probieren Sie es online!

Gibt 1 für den unteren und 0 für den oberen Wert zurück.

×€Ø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$

Gehirn-Flak , 78 Bytes

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

Probieren Sie es online!

Gibt nichts für unteres und 0für oberes aus. Ein Wechsel zu einem sinnvolleren Ausgabeschema würde 6 Byte kosten.

Python 2 , 39 33 32 Bytes

^{-6 Bytes dank Mr. Xcoder
-1 Bytes dank Zacharý}

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

Probieren Sie es online!

Gibt Falsefür unteres und Truefür oberes zurück

Julia 0,6 , 16 Bytes

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

Probieren Sie es online!

Beim Herumspielen mit den Zahlen bin ich auf diese Eigenschaft gestoßen: Etage (n / φ) == Etage ((n + 1) / φ), wenn n in der oberen Wythoff-Sequenz ist, und Etage (n / φ) <Etage ( (n + 1) / φ), wenn n in der unteren Wythoff-Sequenz liegt. Ich habe nicht herausgefunden, wie diese Eigenschaft zustande kommt, aber sie liefert die korrekten Ergebnisse mindestens bis zu n = 100000 (und wahrscheinlich darüber hinaus).

Alte Antwort:

Julia 0,6 , 31 Bytes

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

Probieren Sie es online!

Gibt truefür die untere und falseobere Wythoff-Sequenz zurück.

Pyth , 8 Bytes

/sM*.n3S

Probieren Sie es hier aus!

Gibt 1 für den unteren und 0 für den oberen Wert zurück.

Wolfram Language (Mathematica) , 26 Byte

#~Ceiling~GoldenRatio<#+1&

Probieren Sie es online!

Eine Ganzzahl nbefindet sich in der unteren Wythoff-Sequenz iff ceil(n/phi) - 1/phi < n/phi.

Beweis dafür, dass ceil(n/phi) - 1/phi < n/phi...

Ausreichend:

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

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

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

4. Daher n <= ceil(n/phi) * phi < n + 1.

5. Da nund ceil(n/phi)ganze Zahlen sind, rufen wir die Definition von Boden und Zustand floor(ceil(n/phi) * phi) == n, und nsind in der unteren Wythoff Sequenz.

Notwendig; Beweis durch Kontrapositiv:

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

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

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

4. Daher n > (ceil(n/phi) - 1) * phi.

5. Da (ceil(n/phi) - 1) * phi < n < n + 1 <= ceil(n/phi) * phi, nist in der unteren Wythoff Sequenz nicht.

Japt , 10 Bytes

Gibt true für lower und false für upper zurück.

õ_*MQ fÃøU

Probieren Sie es online!

Erläuterung:

õ_*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 Bytes

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

Port von @ Rods Python 2 Antwort .
-1 Byte danke an @ Zacharý .

Probieren Sie es online aus.

Alte 77 76 Bytes Antwort:

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

-1 Byte Danke an @ovs 'für etwas, das ich mir letzte Woche empfohlen habe. XD

Kehrt 1für niedriger zurück; 0für obere.

Probieren Sie es online aus.

Erläuterung:

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*Phiwird mit take berechnet (sqrt(5)+1)/2 * iund dann durch Umwandlung in eine Ganzzahl, um die Dezimalstelle abzuschneiden, geebnet.

Haskell , 153 139 126 79 Bytes

Unbegrenzte Präzision!

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

Probieren Sie es online!

Erläuterung

Anstatt zur Berechnung des Ergebnisses eine Approximation des Goldenen Schnitts zu verwenden, sind sie mit zunehmender Größe der Eingabe fehleranfällig. Diese Antwort gibt es nicht. Stattdessen wird die auf dem OEIS angegebene Formel verwendet, die adie eindeutige Sequenz ist, so dass

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

Wo bist das bestellte Kompliment?

Brachylog , 8 Bytes

≥ℕ;φ×⌋₁?

Probieren Sie es online!

Das Prädikat ist erfolgreich, wenn sich die Eingabe in der unteren Wythoff-Sequenz befindet, und schlägt fehl, wenn sich die Eingabe in der oberen Wythoff-Sequenz befindet.

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

Wenn das Nichtbeenden eine gültige Ausgabemethode ist, kann das erste Byte weggelassen werden.

MATL , 8 Bytes

t:17L*km

Probieren Sie es online!

Erläuterung

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 Bytes

Lösung:

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

Probieren Sie es online!

Erläuterung:

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 Byte

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

Eingang ist in Ans.
Die Ausgabe erfolgt in Ansund wird automatisch gedruckt. Wird
gedruckt, 1wenn die Eingabe in der unteren Reihenfolge oder erfolgt0 in der oberen Reihenfolge erfolgt.

Zufälligerweise läuft dieses Programm nur für $0<N<1000$ .

Beispiel:

27
             27
prgmCDGFA
              1
44
             44
prgmCDGFA
              0

Erläuterung:

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

Hinweis: TI-BASIC ist eine Token-Sprache. Die Anzahl der Zeichen entspricht nicht der Anzahl der Bytes.

cQuents , 5 Bytes

?F$`g

Probieren Sie es online!

Erläuterung

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

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