Halbexponentielle Funktion

21

Eine halbe Exponentialfunktion ist eine, die, wenn sie mit sich selbst zusammengesetzt ist, eine Exponentialfunktion ergibt. Wenn zum Beispiel, f(f(x)) = 2^xdann fwäre das eine halbexponentielle Funktion. In dieser Aufgabe berechnen Sie eine bestimmte halbexponentielle Funktion.

Im Einzelnen berechnen Sie die Funktion von den nicht negativen Ganzzahlen zu den nicht negativen Ganzzahlen mit den folgenden Eigenschaften:

  • Monoton steigend: wenn x < y, dannf(x) < f(y)

  • Mindestens die Hälfte exponentielle: Für alle x,f(f(x)) >= 2^x

  • Lexikographisch am kleinsten: Geben Sie unter allen Funktionen mit den oben genannten Eigenschaften diejenige aus, die minimiert wird f(0), die bei dieser Auswahl minimiert f(1)wird f(2), und so weiter.

Die Anfangswerte dieser Funktion für Eingaben 0, 1, 2, ...sind:

[1, 2, 3, 4, 8, 9, 10, 11, 16, 32, 64, 128, 129, 130, 131, 132, 256, 257, ...]

Sie können diese Funktion über eine der folgenden Methoden ausgeben, entweder als Funktion oder als vollständiges Programm:

  • Nehmen Sie xals Eingabe, Ausgabe f(x).

  • Nehmen Sie xals Eingang, Ausgang der ersten xWerte f.

  • Endlos alles ausgeben f.

Wenn Sie nehmen xund ausgeben möchten f(x), xmuss Null indiziert sein.

Referenzimplementierung

Dies ist Code Golf - kürzester Code in Bytes gewinnt. Standardlücken sind wie immer verboten.

isaacg
quelle
Die Definition scheint für 0 nicht verifiziert zu sein: f (f (0)) = f (1) = 2, aber 2 ^ 0 = 1
Nahuel Fouilleul
und für 1: f (f (1)) = f (2) = 3 aber 2 ^ 1 = 2
Nahuel Fouilleul
1
@NahuelFouilleul die Anforderung ist f (f (x)) > = 2 ^ x.
Martin Ender
1
Sollen wir uns bei OEIS einreichen ?
Jeppe Stig Nielsen

Antworten:

8

JavaScript (ES7), 51 48 Byte

3 Bytes dank @Arnauld eingespart

f=i=>i?f[f[q=f(i-1),r=f[i]||q+1]=(i>1)<<i,i]=r:1

Nimmt n auf und gibt das n -te Element in der Sequenz aus.


JavaScript (ES7), 70 68 64 Byte

f=(n,a=[],q=1)=>n?f(n-1,a,(n=2**a.indexOf(a.push(q)))<++q?q:n):a

Eine rekursive Funktion, die xdie ersten xElemente der Sequenz als Array aufnimmt und zurückgibt .

Wie es funktioniert

Das Array a wird einzeln prozedural generiert, bis es die gewünschte Länge erreicht. (Eine Portierung der unendlichen Technik, die in der ausgezeichneten Python-Antwort von xnor verwendet wird, wäre wahrscheinlich kürzer.)

Für jeden Index i (0-indiziert) können wir folgende Beobachtung machen :

  • Wenn i als Element in a am Index j existiert ( a [j] = i ), muss a [i] mindestens 2 j betragen .

Dies ist wahr, weil f (f (j)) mindestens 2 j sein muss und f (f (j)) äquivalent zu a [a [j]] ist , was wiederum äquivalent zu a [i] ist .

Normalerweise ist die richtige Option genau 2 j . Jedoch für den singulären Fall = I 2 , 2 in dem Array existiert bei Index j = 1 , was bedeutet , dass 2 j wäre 2 -but Das heißt, wir hätten 2 sowohl auf a [1] und a [2] . Um dies zu umgehen, nehmen wir das Maximum von 2 j und a [i-1] + 1 (eins mehr als der vorherige Punkt), was 3 für i = 2 ergibt .

Diese Technik kümmert sich auch darum, zu entscheiden, ob j existiert oder nicht - wenn dies nicht der Fall ist, gibt die .indexOf()Methode von JS -1 zurück , was dazu führt, dass das Maximum von [i-1] + 1 und 2 -1 = 0,5 angenommen wird . Da alle Elemente in der Sequenz mindestens 1 sind , wird immer das vorherige Element plus eins zurückgegeben.

(Ich schreibe diese Erklärung spät in der Nacht, also lass es mich wissen, wenn etwas verwirrend ist oder ich etwas verpasst habe.)

ETHproductions
quelle
Beachten Sie, dass Eingaben 272und höher aufgrund von Integer-Überlaufproblemen falsche Antworten geben. Dies ist in Ordnung, da es bis zur Grenze des Datentyps funktioniert.
Isaacg
Verwenden Sie 2**statt 1<<hoffentlich das Problem zu beheben.
user202729
Jetzt .99tötet das die Lösung. Aber warum +.99und nicht nur +.9? Was ist der Unterschied?
user202729
@ user202729 Ich fühle mich wie ein Idiot - der da drin geblieben ist von einer Vorgängerversion, in der ich verwendet habe Math.log2(...)und die Decke berechnen musste. Jetzt wird es überhaupt nicht benötigt. Vielen Dank! Ich werde in die 2**Sache schauen - ich habe 2**...+.99|0ursprünglich verwendet, war aber 1<<kürzer, weil ich das nicht brauchte |0. Jetzt denke ich, dass es keinen Unterschied gibt ...
ETHproductions
7

Python 2 , 60 Bytes

d={};a=n=1
while 1:print a;a=d.get(n,a+1);d[1%n*a]=2**n;n+=1

Probieren Sie es online!

Druckt für immer.


Python , 61 Bytes

f=lambda n,i=2:n<1or(i>=n)*-~f(n-1)or(f(i)==n)<<i or f(n,i+1)

Probieren Sie es online!

Eine Funktion. Ausgänge Trueanstelle von 1.

xnor
quelle
1

Bash, 66 Bytes

for((r=$1?2:1,i=2;i<=$1;i++));{ a[r=a[i]?2**a[i]:r+1]=$i;};echo $r

Probieren Sie es online aus

Nahuel Fouilleul
quelle
1

Jelly , 14 Bytes

iL’2*»Ṁ‘$ṭ
⁸Ç¡

Probieren Sie es online!

Wie es funktioniert

⁸Ç¡         Main link. No arguments.

⁸           Set the left argument and the return value to [].
 Ç¡         Read an integer n from STDIN and call the helper link n times, first on
            [], then on the previous result. Return the last result.


iL’2*»Ṁ‘$ṭ  Helper link. Argument: A (array)

 L          Take the length of A. This is the 0-based index of the next element.
i           Find its 1-based index in A (0 if not present).
  ’         Decrement to a 0-based index (-1 if not present).
   2*       Elevate 2 to the 0-based index.
      Ṁ‘$   Take the maximum of A and increment it by 1.
            Note that Ṁ returns 0 for an empty list.
     »      Take the maximum of the results to both sides.
         ṭ  Tack (append) the result to A.
Dennis
quelle
0

Python 2 , 111 Bytes

def f(x):
 a=range(1,2**x)
 for i in range(1,x):a[i]=max(a[i],a[i-1]+1);a[a[i]]=max(a[a[i]],2**i)
 return a[:x]

Probieren Sie es online!

Dies ist eine wesentliche Änderung der Antwort von user202729 . Ich hätte diese Verbesserung als Kommentar gepostet, aber die Antwort wurde gelöscht und daher sind Kommentare deaktiviert.

notjagan
quelle
Dies schlägt mit einer Ausnahme "Listenindex außerhalb des Bereichs" für die Eingabe 258 fehl. Ich denke, das Problem ist, dass x**2es zu klein ist.
Isaacg
Nun ... Python 2 unterscheidet sich (oft weniger Bytes) von Python 3.
user202729
1
Wie erwartet ist die halbe Exponentialfunktion viel größer als die quadratische. Die Lösung erhält "Listenindex außerhalb des Bereichs" unter x=1000. Vielleicht möchten Sie es versuchen 2**x- furchtbar groß, aber Codegolf ist Codegolf.
user202729
@ user202729 Ah, das ist wahr. Leider stößt es jetzt bei größeren Eingaben auf ein völlig anderes Problem, das 2**xeinen viel zu großen Bereich erzeugt, als dass Python fortfahren könnte.
Notjagan
0

Schnell , 137 Bytes

func f(n:Int){var l=Array(1...n).map{$0>3 ?0:$0},p=8;if n>3{for i in 3..<n{if l[i]<1{l[i]=l[i-1]+1};if l[i]<n{l[l[i]]=p};p*=2}};print(l)}

Nimmt die Eingabe als Int(Ganzzahl) und druckt als[Int] (Ganzzahl-Array).

Ungolfed-Version

func f(n:Int){
    var l = Array(1...n).map{$0 > 3 ? 0 : $0} // Create the range from 1 to n and set all
    var p = 8                                 // values greater than 3 to 0
    if n > 3 {
        for i in 3 ..< n {
            if l[i] < 1 {
                l[i] = l[i - 1] + 1
            }
            if l[i] < n {
                l[l[i]] = p
            }
            p *= 2
        }
    }
    print(l)
}
Herman L
quelle
Ich bin gespannt, was passiert, wenn Sie das Leerzeichen vor dem entfernen ??
ETHproductions
@ETHproductions Dies führt zu einem Compilerfehler, da Ganzzahlen nicht optional verkettet werden können .
Herman L