Wechselstrom-Fibonacci-Sequenz

24

Definition

Die Wechselstrom-Fibonacci-Sequenz wird wie folgt gebildet.

  1. Beginnen Sie mit der leeren Sequenz und setzen Sie n auf 1 .

  2. Berechnen Sie f n , die n- te nicht negative Fibonacci-Zahl , mit Wiederholungen.
    0 ist die erste, 1 ist die zweite und die dritte, 2 ist die vierte. Alle anderen werden durch Summieren der beiden vorherigen Zahlen in der Folge erhalten, also ist 3 = 1 + 2 die fünfte, 5 = 2 + 3 die sechste usw.

  3. Wenn n ungerade ist, ändern Sie das Vorzeichen von f n .

  4. Fügen Sie der Sequenz 2 n-1 Kopien von f n hinzu .

  5. Inkrementiere n und gehe zurück zu Schritt 2.

Dies sind die ersten hundert Terme der APF-Sequenz.

 0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8

Aufgabe

Schreiben Sie ein vollständiges Programm oder eine Funktion, die eine positive ganze Zahl n als Eingabe verwendet und den n- ten Term der APF-Sequenz ausgibt oder zurückgibt .

Wenn Sie eine 0-basierte Indizierung bevorzugen, können Sie alternativ eine nicht-negative Ganzzahl n verwenden und die APF-Nummer am Index n ausgeben oder zurückgeben .

Das ist ; möge der kürzeste Code in Bytes gewinnen!

Testfälle (1-basiert)

    1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610

Testfälle (0-basiert)

    0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610
Dennis
quelle
Gibt es irgendwelche Einschränkungen für n ?
Okx
2
Solange Ihr Algorithmus für beliebig große Werte von n arbeitet , können Sie davon ausgehen, dass er in Ihren Datentyp passt.
Dennis
1
Hat das eine OEIS Nummer?
Mindwin
@ Mindwin tut es nicht.
Dennis

Antworten:

12

Gelee , 5 Bytes

BLCÆḞ

Probieren Sie es online!

Wie?

Erweiterung der Fibonacci-Reihe zurück in negative Indizes, sodass die Beziehung f(i) = f(i-2) + f(i-1)weiterhin gilt:

  i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ...

Wenn i=0wir von den Zahlen zurückgehen, müssen wir diese 2 n-1- mal wiederholen , und Jellys Fibonacci ist eingebaut ÆḞ, um diese zu berechnen.

Wir können die -i(eine positive Zahl) finden, die wir brauchen, indem wir die Bitlänge von nund subtrahieren 1.

Da wir wollen i(eine negative Zahl) können wir stattdessen durchführen 1-bitLengthund Jelly hat ein Atom für 1-x, C, das Komplement Monade.

BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21
Jonathan Allan
quelle
Ich wusste, dass es einen kürzeren Weg gibt, aber nicht so viel. Ich dachte, es wären 7 Bytes mit einer Möglichkeit zum Entfernen µund
Meilen am
Ihre wiederholte Verneinung war jedoch klug, ich habe Potenzen von minus eins betrachtet, was ein paar Bytes hinzufügt, bis ich mich an die negativen Fibonacci-Werte erinnerte und versuchte, sie in Jellys Monade zu integrieren.
Jonathan Allan
4
Ehrlich gesagt, ich bin überrascht, dass Jelly kein einziges Byte eingebaut hat, um die binäre Länge einer Zahl zu erhalten ...
ETHproductions
22

Python 2 , 30 Bytes

f=lambda n:n<1or f(n/4)-f(n/2)

Probieren Sie es online!

Einindexiert.

Die Sequenz fühlte sich wie ein Rätsel an, etwas, das Dennis durch einen kurzen Weg erzeugte, es auszudrücken. Die Zweierpotenz-Wiederholungen deuten auf eine Rekursion durch Bitverschiebung (Floor-Division durch 2) hin. Die Fibonacci-Rekursion f(n)=f(n-2)-f(n-1)mit alternierendem Vorzeichen kann anstelle der Dekrementierung an die Bitverschiebung angepasst werden. Das Basisgehäuse funktioniert sehr gut, weil alles funktioniert n=0.

xnor
quelle
6

Mathematica, 43 36 24 Bytes

Fibonacci@-Floor@Log2@#&

Dank @GregMartin wurden 7 Byte und dank @JungHwanMin weitere 12 Byte eingespart.

martin
quelle
1
Sie können ein paar Bytes mit Floor@Log2@#und durch Schreiben Fibonacci[t=...](und durch Entfernen der Leerzeichen im letzten Exponenten) sparen .
Greg Martin
1
-12 Bytes: Fibonacci@-Floor@Log2@#&- FibonacciKann auch negative Argumente enthalten (kümmert sich für Sie um das Vorzeichen).
JungHwan Min
5

MATL , 19 17 16 11 Bytes

lOiB"yy-]x&

Die Eingabe ist 1-basiert.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Für die 1-basierte Eingabe n sei m die Anzahl der Stellen in der binären Erweiterung von n . Der n- te Term in der Ausgabesequenz ist der m- te Term in der Fibonacci-Sequenz, möglicherweise mit geändertem Vorzeichen.

Eine Idee wäre, m- mal zu iterieren , um Terme der Fibonacci-Sequenz zu berechnen. Dies ist einfach mit einer for eachSchleife, die ein Array von Binärziffern verwendet. Wenn die Fibonacci-Sequenz wie üblich mit 0 und dann mit 1 initialisiert würde, würde eine m- malige Iteration zu m + 2 Termen auf dem Stapel führen, sodass die beiden oberen Zahlen gelöscht werden müssten. Stattdessen initialisieren wir mit 1 und dann mit 0 . Auf diese Weise sind die nächsten generierten Terme 1 , 1 , 2 , ... und es ist nur eine Löschung erforderlich.

Mit dem Vorzeichen könnte umgegangen werden, indem eine andere Schleife verwendet wird, um das Vorzeichen m- mal zu ändern . Aber das ist teuer. Es ist besser, die beiden Schleifen zu integrieren, indem einfach subtrahiert wird, anstatt die Fibonacci-Iteration hinzuzufügen.

l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack
Luis Mendo
quelle
4

JavaScript (ES6), 33 Byte

f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p

1-indiziert.

Eine Antwort von xnor wäre 23:

f=n=>n<1||f(n/4)-f(n/2)
ETHproductions
quelle
4

Python 2 , 83 82 79 Bytes

def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1)

Probieren Sie es online!

ovs
quelle
Leerzeichen nicht erforderlich bei or -1.
Yytsi
3

Gelee , 9 Bytes

BLµ’ÆḞN⁸¡

Verwendet eine einseitige Indizierung.

Probieren Sie es online!

Erläuterung

Diese Methode funktioniert, wenn Ihre Fibonacci-Funktion nur nicht negative Argumente unterstützt.

BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1)
Meilen
quelle
3

Japt , 6 Bytes

Mg1-¢l

Testen Sie es online!

Wie es funktioniert

Wie in anderen Antworten erwähnt, ist der n- te Term in der Fibonacci-Reihe mit Wechselzeichen der gleiche wie der -n- te Term in der regulären Reihe. n kann gefunden werden, indem die Bitlänge der Eingabe genommen und eine subtrahiert wird; Negiert man dies, ergibt sich 1 minus der Bitlänge.

Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index.
ETHproductions
quelle
3

05AB1E , 11 10 Bytes

Verwendet 1-basierte Indizierung

Die Fibonacci-Funktion von 05AB1E gibt positive Fib-Zahlen kleiner als n zurück , dh, wir müssten mehr als nötig generieren, die richtige nach Index ermitteln und dann das Vorzeichen berechnen. Daher bezweifle ich, dass eine Methode, die darauf basiert, kürzer ist als die iterative Berechnung der Zahlen.

Verwendet die Erkenntnis, dass wir den Stapel 1, 0umgekehrt initialisieren können , um den Fall zu behandeln, n=1wie in Luis Mendos MATL-Antwort beschrieben .

XÎbgG‚D«`-

Probieren Sie es online!

Erläuterung

X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements
Emigna
quelle
2

Perl 6 , 53 Bytes

{flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]}

Einfache Umsetzung des Ablaufs, wie er beschrieben wurde.
Nullbasiert.

smls
quelle
2

Julia 0,5 , 19 Bytes

!n=n<1||!(n/=4)-!2n

Probieren Sie es online!

Wie es funktioniert

Dies verwendet die gleiche Formel wie die Python-Antwort von @ xnor . Die Wiederholungsrelation
g (n) = g (n-2) + g (n-1) erzeugt die negativen Terme der Fibonacci-Sequenz, die den positiven Terme mit wechselnden Vorzeichen entsprechen. Von jeder Stelle in einem Durchlauf von 2 k Wiederholungen derselben Zahl können wir eine beliebige Wiederholung des vorherigen Durchlaufs von 2 k-1 Zahlen und des Durchlaufs von 2 k-2 Zahlen vor diesen auswählen, indem wir den Index durch 2 und 4 teilen .

Eher als das Unkomplizierte

f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes

Wir können einen Operator für unsere Zwecke neu definieren. Auch f funktioniert genauso gut mit Schwimmern, also bekommen wir

!n=n<1||!(n/4)-!(n/2)   # 21 bytes

Wenn wir schließlich n durch eine Division durch 4 aktualisieren, können wir n / 2 als 2n schreiben und ein Paar von Parens weglassen, was zu der 19-Byte-Funktionsdefinition in dieser Antwort führt.

Dennis
quelle
1

J , 18 Bytes

(%>:-*:)t.@<:@#@#:

Verwendet eine einseitige Indizierung. Nimmt eine Eingabe-Ganzzahl n > 0 und berechnet sie, floor(log2(n))indem sie die Länge ihrer Binärdarstellung ermittelt und diesen Wert dann um eins dekrementiert. Es wird dann der floor(log2(n))-1dritte Koeffizient der Erzeugungsfunktion x / (1 + x - x 2 ) ermittelt, der die gf für die negativ indizierten Fibonacci-Werte ist.

Probieren Sie es online!

Erläuterung

(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value
Meilen
quelle