Funkcja półwykładnicza

21

Funkcja półwykładnicza to taka, która po złożeniu daje funkcję wykładniczą. Na przykład jeśli f(f(x)) = 2^x, to fbyłaby funkcja półwykładnicza. W tym wyzwaniu obliczysz określoną funkcję półwykładniczą.

W szczególności obliczymy funkcję od liczb całkowitych nieujemnych do liczb całkowitych nieujemnych o następujących właściwościach:

  • Monotonicznie rośnie: jeśli x < y, tof(x) < f(y)

  • Co najmniej połowę wykładniczą: Dla wszystkich x,f(f(x)) >= 2^x

  • Leksykograficznie najmniejszy: Spośród wszystkich funkcji o powyższych właściwościach wypisz tę, która minimalizuje f(0), co przy takim wyborze minimalizuje f(1), a następnie f(2)itd.

Początkowe wartości tej funkcji dla danych wejściowych 0, 1, 2, ...to:

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

Możesz wyprowadzić tę funkcję za pomocą dowolnej z następujących metod, albo jako funkcja, albo jako pełny program:

  • Weź xjako wejście, wyjście f(x).

  • Weź xjako dane wejściowe, wypisz pierwsze xwartości f.

  • Nieskończone wyświetlanie wszystkich f.

Jeśli chcesz pobierać xi generować f(x), xmusi być zerowany.

Realizacja referencyjna

To jest golfowy kod - wygrywa najkrótszy kod w bajtach. Standardowe luki są jak zawsze zakazane.

isaacg
źródło
wydaje się, że definicja nie została zweryfikowana dla 0: f (f (0)) = f (1) = 2 ale 2 ^ 0 = 1
Nahuel Fouilleul
a dla 1: f (f (1)) = f (2) = 3 ale 2 ^ 1 = 2
Nahuel Fouilleul
1
@NahuelFouilleul wymaganiem jest f (f (x)) > = 2 ^ x.
Martin Ender,
1
Czy powinniśmy przesłać do OEIS ?
Jeppe Stig Nielsen,

Odpowiedzi:

8

JavaScript (ES7), 51 48 bajtów

Zaoszczędź 3 bajty dzięki @Arnauld

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

Pobiera n i wysyła n -ty element w sekwencji.


JavaScript (ES7), 70 68 64 bajtów

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

Funkcja rekurencyjna, która przyjmuje xi zwraca pierwsze xelementy sekwencji jako tablicę.

Jak to działa

Tablica a jest generowana proceduralnie, po jednym elemencie na raz, aż osiągnie pożądaną długość. (Port nieskończonej techniki zastosowanej w doskonałej odpowiedzi Xnora w Pythonie prawdopodobnie byłby krótszy.)

Możemy dokonać następującej obserwacji dla każdego indeksu i (indeksowanego 0):

  • Jeżeli i istnieje jako elementu o indeksie j ( A [j] = I ), a następnie A [b] musi wynosić co najmniej 2 j .

Jest to prawdą, ponieważ f (f (j)) musi wynosić co najmniej 2 j , a f (f (j)) jest równoważne z [a [j]] , co z kolei jest równoważne z [i] .

Zwykle poprawna opcja to dokładnie 2 j . Jednak w przypadku liczby pojedynczej i = 2 , 2 istnieje w tablicy o indeksie j = 1 , co oznacza, że 2 j będzie równe 2 - ale to oznacza, że ​​mielibyśmy 2 zarówno na [1], jak i [2] . Aby obejść ten problem, bierzemy maksymalnie 2 j oraz [i-1] + 1 (jeden więcej niż poprzedni element), co daje 3 dla i = 2 .

Ta technika zdarza się również, aby zadecydować, czy j istnieje - jeśli nie, .indexOf()metoda JS zwraca -1 , co prowadzi do przyjęcia maksimum [i-1] + 1 i 2 -1 = 0,5 . Ponieważ wszystkie elementy w sekwencji mają co najmniej 1 , zawsze zwróci poprzedni element plus jeden.

(Piszę to wyjaśnienie późno w nocy, więc proszę dać mi znać, jeśli coś jest mylące lub coś przeoczyłem)

ETHprodukcje
źródło
Pamiętaj, że dane wejściowe 272i wyższe dają nieprawidłowe odpowiedzi z powodu problemów z przepełnieniem liczb całkowitych. To dobrze, ponieważ działa do limitu typu danych.
isaacg,
Użyj 2**zamiast, 1<<mam nadzieję, naprawić problem.
user202729,
Teraz .99zabija rozwiązanie. Ale po co używać, +.99a nie tylko +.9? Co za różnica?
user202729,
@ user202729 Czuję się jak idiota - który został tam z poprzedniej wersji, w której używałem Math.log2(...)i musiałem obliczyć pułap. Teraz nie jest wcale potrzebny. Dzięki! Przyjrzę się temu 2**- 2**...+.99|0początkowo używałem, ale 1<<był krótszy, ponieważ nie potrzebowałem |0. Teraz myślę, że nie ma różnicy ...
ETHproductions
7

Python 2 , 60 bajtów

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

Wypróbuj online!

Drukuje na zawsze.


Python , 61 bajtów

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

Wypróbuj online!

Funkcja. Dane wyjściowe Truezamiast 1.

xnor
źródło
2

Perl 5, 53 + 1 ( -p) = 54 bajtów

$\=$_>0;map$a[$\=$a[$_]?2**$a[$_]:$\+1]=$_,++$\..$_}{

Wypróbuj online

Nahuel Fouilleul
źródło
1

Bash, 66 bajtów

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

Wypróbuj online

Nahuel Fouilleul
źródło
1

Galaretka , 14 bajtów

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

Wypróbuj online!

Jak to działa

⁸Ç¡         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
źródło
0

Python 2 , 111 bajtów

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]

Wypróbuj online!

Jest to znacząca modyfikacja odpowiedzi user202729 . Opublikowałbym to ulepszenie jako komentarz, ale odpowiedź została usunięta, więc komentarze zostały wyłączone.

notjagan
źródło
Nie udaje się to z wyjątkiem „indeksu listy poza zakresem” na wejściu 258. Myślę, że problem x**2jest zbyt mały.
isaacg,
Cóż ... Python 2 różni się (często mniej bajtów) od Python 3.
user202729
1
Zgodnie z oczekiwaniami, półwykładniczy jest znacznie większy niż kwadratowy. Rozwiązaniem jest „indeks listy poza zakresem” na x=1000. Możesz spróbować 2**x- strasznie duży, ale codegolf to codegolf.
user202729,
@ user202729 Ach, to prawda. Niestety, teraz napotyka on zupełnie inny problem z większymi danymi wejściowymi, który 2**xtworzy zbyt duży zakres, aby Python mógł kontynuować.
notjagan
0

Szybki , 137 bajtów

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

Pobiera dane wejściowe jako Int(liczba całkowita) i drukuje jako [Int](tablica liczb całkowitych).

Wersja bez golfa

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.
źródło
Jestem ciekawy, co się stanie, jeśli usuniesz przestrzeń przed ??
ETHprodukcje
@ETHproductions Prowadzi to do błędu kompilatora, ponieważ liczby całkowite nie mogą być łańcuchami opcjonalnymi .
Herman L