Stwórz najwolniej rosnącą funkcję, jaką możesz mieć w czasie poniżej 100 bajtów

23

Twoim zadaniem jest stworzenie najwolniejszej rosnącej funkcji, która nie może przekraczać 100 bajtów.

Twój program weźmie jako dane wejściowe nieujemną liczbę całkowitą i wyświetli nieujemną liczbę całkowitą. Nazwijmy twój program P.

Musi spełniać te dwa kryteria:

  • Kod źródłowy musi być mniejszy lub równy 100 bajtów.
  • Dla każdego K istnieje N, takie, że dla każdego n> = N, P (n)> K. Innymi słowy, lim (n-> ∞) P (n) = ∞ . (To właśnie oznacza, że ​​„rośnie”).

Twój „wynik” to tempo wzrostu funkcji podstawowej programu.

Mówiąc dokładniej, program P rośnie wolniej niż Q, jeśli istnieje taki N, że dla wszystkich n> = N, P (n) <= Q (n), i jest co najmniej jeden n> = N taki, że P (n ) <Q (n). Jeśli żaden program nie jest lepszy od drugiego, są one powiązane. (Zasadniczo, który program jest wolniejszy, zależy od wartości lim (n-> ∞) P (n) -Q (n).)

Zgodnie z definicją z poprzedniego akapitu najwolniejszą funkcją wzrostu jest ta, która rośnie wolniej niż jakakolwiek inna funkcja.

Jest to o tempie wzrostu, więc wygrywa najwolniej rozwijający się program!

Uwagi:

  • Aby pomóc w punktacji, spróbuj podać w odpowiedzi funkcję obliczoną przez Twój program.
  • Dodaj także (teoretyczne) dane wejściowe i wyjściowe, aby pomóc ludziom zorientować się, jak wolno możesz jechać.
PyRulez
źródło
3
Związane z.
Martin Ender
3
Skuteczną strategią jest napisanie szybko rosnącej funkcji i odwrócenie jej, tj. Znalezienie najmniejszego wkładu, który daje co najmniej wymaganą wartość. Może to jest dupek?
xnor
Brakowało jednej trzeciej akapitu „Bardziej konkretnie”, ponieważ Markdown uważa, że <po niej następuje litera jako początek znacznika HTML. Przejrzyj swoje pytania, zanim je opublikujesz: P
ETHproductions
1
Jakie duże aksjomaty kardynalne możemy założyć?
Peter Taylor,
1
Czy podano maszynę czasu do przetestowania naszych odpowiedzi?
Magic Octopus Urn

Odpowiedzi:

13

Haskell, 98 bajtów, wynik = f ε 0 −1 ( n )

_#[]=0
k#(0:a)=k#a
k#(a:b)=1+(k#(([1..k]>>fst(span(>=a)b)++[a-1])++b))
f n=[k|k<-[0..],k#[k]>n]!!0

Jak to działa

Oblicza to odwrotność bardzo szybko rosnącej funkcji związanej z robakiem Beklemisheva . Jego tempo wzrostu jest porównywalne z f ε 0 , gdzie f α jest szybko rosnącą hierarchią, a ε 0 jest pierwszą liczbą epsilon .

Aby to porównać z innymi odpowiedziami, zwróć uwagę na to

  • potęgowanie jest porównywalne z f 2 ;
  • iterowane potęgowanie ( tetracja lub ↑↑ ) jest porównywalne z f 3 ;
  • ↑↑ ⋯ ↑↑ z m strzałkami jest porównywalna z f m + 1 ;
  • Funkcja Ackermanna jest porównywalna z f ω ;
  • powtarzane iteracje funkcji Ackermanna (konstrukcje takie jak liczba Grahama ) są nadal zdominowane przez f ω + 1 ;
  • a ε 0 jest granicą wszystkich wież ω ω ω ω .
Anders Kaseorg
źródło
Bardziej podoba mi się opis tutaj .
PyRulez
Możesz umieścić link do wprowadzenia Wiki Googology do szybko rosnącej hierarchii
MilkyWay90
18

Brachylog , 100 bajtów

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

Wypróbuj online!

Prawdopodobnie nie jest to bliskie powolności innych fantazyjnych odpowiedzi, ale nie mogłem uwierzyć, że nikt nie próbował tego prostego i pięknego podejścia.

Po prostu obliczamy długość liczby wejściowej, następnie długość tego wyniku, a następnie długość tego innego wyniku ... łącznie 100 razy.

Rośnie to tak szybko, jak log (log (log ... log (x), przy 100 logach base-10).

Jeśli wpiszesz swój numer jako ciąg , będzie on działał niezwykle szybko na każdym wejściu, którego możesz spróbować, ale nie oczekuj, że kiedykolwiek zobaczysz wynik większy niż 1: D

Lew
źródło
8
+1 tylko dla czystego szaleństwa: o Ciekawostka: Działa również w galaretce, jeśli dokonasz wszystkich kapsli. : P
HyperNeutrino
5
Pierwsza liczba, która wyprowadza 2, to 10 ↑↑ 99.
Wheat Wizard
11

JavaScript (ES6), funkcja odwrotna Ackermanna *, 97 bajtów

* jeśli zrobiłem to dobrze

A=(m,n)=>m?A(m-1,n?A(m,n-1):1):n+1
a=(m,n=m,i=1)=>{while(A(i,m/n|0)<=Math.log2(n))i++;return i-1}

Funkcja Ajest funkcją Ackermanna . Funkcja ama być funkcją odwrotnej Ackermanna . Jeśli poprawnie go zaimplementowałem, Wikipedia mówi, że nie trafi, 5dopóki nie będzie mrówny 2^2^2^2^16. Mam StackOverflowwokół siebie 1000.

Stosowanie:

console.log(a(1000))

Objaśnienia:

Funkcja Ackermanna

A=(m,n)=>                           Function A with parameters m and n
         m?                   :n+1  If m == 0, return n + 1; else,
           A(m-1,n?        :1)       If n == 0, return A(m-1,1); else,
                   A(m,n-1)          return A(m-1,A(m,n-1))

Odwrotna funkcja Ackermanna

a=(m,n=m,i=1)=>{                                                Function a with parameter m, with n preinitialized to m and i preinitialized to 1
                while(A(i,m/n|0)<=Math.log2(n))                 While the result of A(i, floor(m/n)) is less than log₂ n,
                                               i++;             Increment i
                                                   return i-1}  Return i-1
Stephen
źródło
2
Czyż jednak przepełnienie stosu nie jest dobre ?
NoOneIsHere
Twoje stwierdzenie, że nie trafi 5, dopóki m = 2 ^^ 7 jest błędne. Nie trafi 5, dopóki m = 2 ^^ 7-3, ale przy 2 ^^ 7-1 wynosi 5. Wiem, że -3 jest bardzo małe w porównaniu do 2 ^^ 7, ale 5A5 = 2 ^^ 7-3 <2 ^^ 7. (^^ oznacza tetrację)
user75200
8

Pure Evil: Eval

a=lambda x,y:(y<0)*x or eval("a("*9**9**9+"x**.1"+",y-1)"*9**9**9)
print a(input(),9**9**9**9**9)//1

Instrukcja wewnątrz eval tworzy ciąg o długości 7 * 10 10 10 10 10 10 8.57, który składa się wyłącznie z wywołań funkcji lambda, z których każde będzie konstruować ciąg o podobnej długości, tak długo, aż w końcu stanie ysię 0. Pozornie ma to tę samą złożoność co poniższa metoda Eschew, ale zamiast polegać na logice „i-lub-lub”, po prostu rozbija gigantyczne łańcuchy razem (a wynik netto jest coraz większy stosów ... prawdopodobnie?).

Największą ywartością, jaką mogę podać i obliczyć bez zgłaszania błędu przez Python, jest 2, co jest już wystarczające do zmniejszenia wartości wejściowej max-float do zwracania 1.

Łańcuch o długości 7,625,597,484,987 jest po prostu zbyt duży: OverflowError: cannot fit 'long' into an index-sized integer.

Powinienem przestać

Unikaj Math.log: Przechodząc do (dziesiątego) źródła (problemu), Wynik: funkcja skutecznie nie do odróżnienia od y = 1.

Importowanie biblioteki matematycznej ogranicza liczbę bajtów. Pozbądźmy się tego i zastąpmy log(x)funkcję czymś w przybliżeniu równoważnym: x**.1i która kosztuje w przybliżeniu taką samą liczbę znaków, ale nie wymaga importu. Obie funkcje mają podliniowe wyjście względem wejścia, ale x 0,1 rośnie jeszcze wolniej . Jednak nie obchodzi nas to zbytnio, dbamy tylko o to, że ma ten sam podstawowy wzorzec wzrostu w odniesieniu do dużych liczb, zużywając porównywalną liczbę znaków (np. x**.9Jest taka sama liczba znaków, ale rośnie szybciej, więc jest to pewna wartość, która wykazałaby dokładnie taki sam wzrost).

Teraz, co zrobić z 16 postaciami. Co powiesz na ... rozszerzenie naszej funkcji lambda o właściwości Sekwencji Ackermanna? Ta odpowiedź dla dużej liczby zainspirowała to rozwiązanie.

a=lambda x,y,z:(z<0)*x or y and a(x**.1,z**z,z-1)or a(x**.1,y-1,z)
print a(input(),9,9**9**9**99)//1

z**zCzęść tutaj powstrzymuje mnie przed uruchomieniem tej funkcji w dowolnym miejscu blisko do rozsądnych wejść do yi znajwiększe wartości mogę wykorzystać to 9 i 3 , dla którego wrócę wartość 1,0, nawet dla największych podpór pływak Pythona (Uwaga: podczas 1,0 jest liczbowo większy niż 6.77538853089e-05, zwiększone poziomy rekurencji zbliżają wyjście tej funkcji do 1, pozostając większe niż 1, podczas gdy poprzednia funkcja przenosiła wartości bliższe 0, pozostając większa niż 0, w ten sposób nawet umiarkowaną rekurencję dla tej funkcji powoduje tyle operacji, że liczba zmiennoprzecinkowa traci wszystkie znaczące bity).

Ponowna konfiguracja oryginalnego wywołania lambda w celu uzyskania wartości rekurencji 0 i 2 ...

>>>1.7976931348623157e+308
1.0000000071

Jeśli zostanie wykonane porównanie z „przesunięciem od 0” zamiast „przesunięciem z 1”, funkcja ta zwraca wartość 7.1e-9, która jest zdecydowanie mniejsza niż 6.7e-05.

Rzeczywista podstawowa rekurencja programu (wartość z) wynosi 10 10 10 10 1,97 poziomów głębokości, gdy tylko y się wyczerpie, resetuje się z 10 10 10 10 10 1,97 (dlatego wystarcza wartość początkowa 9), więc nie nawet nie wiem, jak poprawnie obliczyć całkowitą liczbę rekurencji: doszedłem do końca mojej wiedzy matematycznej. Podobnie nie wiem, czy przeniesienie jednego z **nwykładników z początkowego sygnału wejściowego na wtórny z**zpoprawiłoby liczbę rekurencji, czy też nie (podobnie jak odwrotnie).

Idziemy jeszcze wolniej z jeszcze większą rekurencją

import math
a=lambda x,y:(y<0)*x or a(a(a(math.log(x+1),y-1),y-1),y-1)
print a(input(),9**9**9e9)//1
  • n//1 - oszczędza 2 bajty int(n)
  • import math, math.oszczędza 1 bajtfrom math import*
  • a(...) oszczędza łącznie 8 bajtów m(m,...)
  • (y>0)*x zapisuje bajt overy>0and x
  • 9**9**99zwiększa liczbę bajtów o 4 i zwiększa głębokość rekurencji o około 2.8 * 10^xgdzie xjest stara głębokość (lub głębokość zbliżona do googolplex w rozmiarze: 10 10 94 ).
  • 9**9**9e9zwiększa liczbę bajtów o 5 i zwiększa głębokość rekurencji o ... szaloną ilość. Głębokość rekurencji wynosi teraz 10 10 10 9,93 , dla porównania, googolplex wynosi 10 10 10 2 .
  • deklaracja lambda zwiększa rekursji przez dodatkowy krok: m(m(...))do a(a(a(...)))kosztów 7 bajtów

Nowa wartość wyjściowa (przy 9 głębokości rekurencji):

>>>1.7976931348623157e+308
6.77538853089e-05

Głębokość rekurencji eksplodowała do punktu, w którym ten wynik jest dosłownie bez znaczenia, z wyjątkiem porównania z wcześniejszymi wynikami używającymi tych samych wartości wejściowych:

  • Oryginał nazwany log25 razy
  • Pierwsza poprawka nazywa to 81 razy
    • Rzeczywisty program będzie nazwać 1e99 2 lub około 10 10 2,3 razy
  • Ta wersja nazywa to 729 razy
    • Rzeczywisty program będzie to (9 wywołać 9 99 ) 3 lub nieco mniej niż 10 10 95 -krotnie).

Lambda Incepcja, wynik: ???

Słyszałem, że lubisz lambdas, więc ...

from math import*
a=lambda m,x,y:y<0and x or m(m,m(m,log(x+1),y-1),y-1)
print int(a(a,input(),1e99))

Nie mogę nawet tego uruchomić, układam przepełnienie nawet przy zaledwie 99 warstwach rekurencji.

Stara metoda (poniżej) zwraca (pomijając konwersję do liczby całkowitej):

>>>1.7976931348623157e+308
0.0909072713593

Nowa metoda powraca, używając tylko 9 warstw wtargnięcia (zamiast ich pełnego googola ):

>>>1.7976931348623157e+308
0.00196323936205

Myślę, że to działa podobnie do sekwencji Ackermana, tylko małe zamiast duże.

Również dzięki produktom ETH za 3-bajtowe oszczędności w przestrzeniach, o których nie wiedziałem, że można je usunąć.

Stara odpowiedź:

Skrócenie liczb całkowitych dziennika funkcji (i + 1) iterowało 20 25 razy (Python) przy użyciu lambda'd lambda.

Odpowiedź PyRuleza można skompresować, wprowadzając drugą lambdę i układając ją w stos:

from math import *
x=lambda i:log(i+1)
y=lambda i:x(x(x(x(x(i)))))
print int(y(y(y(y(y(input()))))))

99 100 używanych znaków.

Powoduje to iterację 20 25, w stosunku do oryginału 12. Dodatkowo zapisuje 2 znaki, używając int()zamiast tego floor()dozwolonego dla dodatkowego x()stosu. Jeśli spacje po lambda można usunąć (nie mogę w tej chwili sprawdzić), y()można dodać piątą . Możliwy!

Jeśli istnieje sposób na pominięcie from mathimportu przy użyciu w pełni kwalifikowanej nazwy (np. x=lambda i: math.log(i+1))), To zaoszczędziłoby jeszcze więcej znaków i pozwoliłoby na inny stos, x()ale nie wiem, czy Python obsługuje takie rzeczy (podejrzewam, że nie). Gotowy!

Jest to w zasadzie ta sama sztuczka, którą zastosowano w blogu XCKD na dużą liczbę , jednak narzut związany z deklarowaniem lambdas wyklucza trzeci stos:

from math import *
x=lambda i:log(i+1)
y=lambda i:x(x(x(i)))
z=lambda i:y(y(y(i)))
print int(z(z(z(input()))))

Jest to najmniejsza możliwa rekurencja z 3 lambdami, która przekracza obliczoną wysokość stosu 2 lambdas (zmniejszenie dowolnej lambdy do dwóch wywołań obniża wysokość stosu do 18, poniżej wysokości wersji 2-lambda), ale niestety wymaga 110 znaków.

Draco18s
źródło
Do twojej wiadomości, liczę 103 bajty w górnym programie
ETHproductions
@ETHproductions ooch. Prawdopodobnie liczyłem bez intkonwersji i myślałem, że mam części zamienne.
Draco18s,
Myślę , że możesz usunąć spację po importi spację po y<0. Nie znam jednak dużo Pythona, więc nie jestem pewien
ETHproductions
Ponadto, może y<0and x or m(m,m(m,log(x+1),y-1),y-1)zapisać kolejny bajt (zakładając, że xnie ma 0kiedy y<0)
ETHproductions
2
Cóż ... log(x)rośnie wolniej niż DOWOLNA moc dodatnia x(dla dużych wartości x), i nie jest to trudne do wykazania przy użyciu reguły L'Hopital. Jestem prawie pewien, że twoja obecna wersja robi (...(((x**.1)**.1)**.1)** ...)wiele razy. Ale te moce po prostu się mnożą, więc jest to efektywne x**(.1** (whole bunch)), co jest (bardzo małą) siłą pozytywną x. Oznacza to, że faktycznie rośnie szybciej niż JEDNA iteracja funkcji dziennika (chociaż, oczywiście, musiałbyś spojrzeć na BARDZO duże wartości xzanim zauważysz ... ale to właśnie rozumiemy przez „przejście w nieskończoność” ).
matmandan
4

Haskell , 100 bajtów

f 0 a b=a^b
f c a b=foldr(f$c-1)a$[0..b]>>[a]
i=length.show
0#x=i x
y#x=i$(y-1)#x
g=(f(f 9 9 9)9 9#)

Wypróbuj online!

To rozwiązanie nie przyjmuje odwrotności szybko rosnącej funkcji, zamiast tego przyjmuje raczej wolno rosnącą funkcję, w tym przypadku length.show, i stosuje ją kilka razy.

Najpierw definiujemy funkcję f. fto drań wersja notacji Knutha, która rośnie nieco szybciej (nieco to trochę mało powiedziane, ale liczby, z którymi mamy do czynienia, są tak duże, że w wielkim schemacie rzeczy ...). Definiujemy podstawowy przypadek f 0 a bby być a^blub ado potęgi b. Następnie definiujemy ogólny przypadek do (f$c-1)zastosowania w b+2wystąpieniach a. Gdybyśmy zdefiniowali konstrukt typu Knut w górę, zastosowalibyśmy go do bprzypadków a, ale b+2jest bardziej golfistą i ma tę zaletę, że szybciej rośnie.

Następnie definiujemy operatora #. a#bjest zdefiniowane jako length.showstosowane do b aczasów. Każde zastosowanie length.showjest w przybliżeniu równe log 10 , co nie jest bardzo szybko rosnącą funkcją.

Następnie zaczynamy definiować naszą funkcję, gktóra przyjmuje i przyjmuje liczbę całkowitą i stosuje length.showsię do liczby całkowitej kilka razy. Mówiąc konkretniej, dotyczy length.showto danych wejściowych f(f 9 9 9)9 9. Zanim przejdziemy do tego, jak duże to jest, spójrzmy f 9 9 9. f 9 9 9jest większy niż 9↑↑↑↑↑↑↑↑↑9 (dziewięć strzał) o ogromny margines. Uważam, że jest to gdzieś pomiędzy 9↑↑↑↑↑↑↑↑↑9(dziewięć strzał) a 9↑↑↑↑↑↑↑↑↑↑9(dziesięć strzał). Teraz jest to niewyobrażalnie duża liczba, zbyt duża, aby przechowywać ją na dowolnym istniejącym komputerze (w zapisie binarnym). Następnie bierzemy to i stawiamy jako nasz pierwszy argument, fktóry oznacza, że ​​nasza wartość jest większa niż 9↑↑↑↑↑↑...↑↑↑↑↑↑9zf 9 9 9strzały pomiędzy. Nie zamierzam opisywać tej liczby, ponieważ jest ona tak duża, że ​​nie sądzę, że byłbym w stanie to zrobić sprawiedliwie.

Każda length.showjest w przybliżeniu równa przyjęciu podstawy logarytmu 10 liczby całkowitej. Oznacza to, że większość liczb zwróci 1, gdy fzostanie do nich zastosowana. Najmniejsza liczba do zwrócenia czegoś innego niż 1 10↑↑(f(f 9 9 9)9 9), która zwraca 2. Zastanówmy się przez chwilę. Jakkolwiek okropnie duża, jak liczba, którą zdefiniowaliśmy wcześniej, najmniejsza liczba, która zwraca 2, wynosi tyle razy, ile wynosi 10. To 1, po których następuje 10↑(f(f 9 9 9)9 9)zero.

W ogólnym przypadku nnajmniejszego wyjścia na wyjściu musi być dowolne n (10↑(n-1))↑↑(f(f 9 9 9)9 9).

Zauważ, że ten program wymaga ogromnej ilości czasu i pamięci nawet dla małych n (więcej niż we wszechświecie wiele razy), jeśli chcesz to przetestować, sugeruję zastąpienie f(f 9 9 9)9 9go znacznie mniejszą liczbą, spróbuj 1 lub 2, jeśli chcesz kiedykolwiek uzyskasz wynik inny niż 1.

Kreator pszenicy
źródło
Nie wydaje mi się, żeby ktokolwiek dbał o to, ile czasu to zajmie i ile pamięci potrzeba, aby program działał na tego rodzaju pytania.
Po prostu piękna sztuka,
3

APL, Zastosuj log(n + 1), e^9^9...^9czasy, gdzie długość łańcucha jest równa e^9^9...^9długości łańcucha minus 1 razy i tak dalej.

⌊((⍟1+⊢)⍣((*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣⊢)))))))))))))))))))))9))⊢
Uriel
źródło
Czy mogę to uruchomić?
Draco18s
7
@ Draco18s zdobywają komputer kwantowy z praktycznie nieskończoną pamięcią, instalują przyzwoitą dystrybucję APL i spędzają czas, czekając, aż utworzy serum zapobiegające starzeniu, bo będziesz musiał siedzieć ciasno przez kilka stuleci.
Uriel
Ha ha. Ok, więc. : p
Draco18s,
Czy jesteś pewien, że zbliża się to do nieskończoności?
PyRulez
@PyRulez jest tak samo jak inne rozwiązania, tyle że z większą ilością iteracji w dzienniku. ale więcej iteracji to wciąż to samo zamknięcie - któremu przeciwstawia się również wykładnictwo. Nie byłem pewien tej e^n^n...^nczęści, więc zmieniłem ją w stałą, ale to może być prawda
Uriel
3

MATL , 42 bajty

iXI:`2*.]X{oXH1H/16L+XKxI:`Yl.]K+XKXdXzXGx

Wypróbuj online!

Program ten oparty jest na szeregach harmonicznych z wykorzystaniem stałej Eulera – Mascheroniego. Kiedy czytałem dokumentację @LuisMendo na temat jego języka MATL (dużymi literami, więc wygląda to na ważne) zauważyłem tę stałą. Wyrażenie funkcji powolnego wzrostu jest następujące: wprowadź opis zdjęcia tutaj

gdzie εk ~ 1 / 2k

Testowałem do 10000 iteracji (w Matlabie, ponieważ jest on zbyt duży dla TIO) i ma wynik poniżej 10, więc jest bardzo wolny.

wprowadź opis zdjęcia tutaj

Objaśnienia:

 iXI      % ask user input (number of iterations)

:`2*.]    % do...while loop, multiply by 2

X{        % convert numeric array into cell array

o         % convert to double precision array 

XH1H/     % copy to clipboard H and divide by 1: now we have an array of 1/2k

16L       % Euler–Mascheroni constant 

+         % addition (element-wise, singleton expansion)

XKxI:`    % save, clear the stack, do...while loop again

  Yl      % logarithm 

  .]      % break, ends the loop

K+XK      % paste from clipboard K, sum all

Xd        % trim: keep the diagonal of the matrix 

Xz        % remove all zeros

XG        % plot (yes it plots on-line too!)

x         % clear the stack
          % (implicit) display

Dowód empiryczny: (ln k ) + 1 na czerwono zawsze powyżej ln k + γ + εk na niebiesko.

wprowadź opis zdjęcia tutaj

Program dla (ln k ) + 1 został utworzony w

Matlab, 47 18 14 bajtów

n=input('')
A=(1:n)
for k=1:n
A(k)=log(k)+1
end

Ciekawe, że minął czas dla n = 100 to 0,208693s na moim laptopie, ale tylko 0,121945s z, d=rand(1,n);A=d*0;a nawet mniej, 0,12147s z A=zeros(1,n). Jeśli zera to marnowanie miejsca, oszczędza prędkość! Ale odbiegam od tematu (prawdopodobnie bardzo powoli).

Edycja: dzięki Stewie za pomoc w zmniejszeniu tego wyrażenia Matlab do:

 @(n)log(1:n)+1
J Doe
źródło
+1 za nie tylko odwrócenie szybkiej funkcji
PyRulez
1
Interesujący wpis SO dotyczący Twojej ciekawej notatki. :)
Stewie Griffin,
Nawiasem mówiąc, gra w golfa skrypt w dole (ponieważ zawiera liczbę bajtów): Ostatni skrypt MATLAB jest prosta: n=input('');A=log(1:n)+1albo jako bezimiennego funkcji anonimowej (14 bajtów) @(n)log(1:n)+1. Nie jestem pewien co do MATLAB, ale A=log(1:input(''))+1pracuje w Octave ...
Stewie Griffin,
dziękuję @Stewie n=input('');A=log(1:n)+1działa, @(n)log(1:n)+1nie rób tego (naprawdę poprawna funkcja z uchwytem w Matlabie, ale nie pytamy o dane wejściowe), A=log(1:input(''))+1działa i można ją skrócićlog(1:input(''))+1
J Doe
Z anonimową funkcją miałem na myśli to . Jest to „normalny” sposób zapisywania bajtów (przynajmniej na tej stronie), wymagając, aby dane wejściowe były podawane jako argumenty funkcji (meta-post) zamiast wiersza polecenia. Ponadto, f=nie muszą być policzone, ponieważ jest to możliwe tylko do: @(n)log(1:n)+1a następnie ans(10), aby uzyskać pierwsze 10 cyfr.
Stewie Griffin
2

Python 3 , 100 bajtów

Dół dziennika funkcji (i + 1) iterował 99999999999999999999999999999999999 razy.

Można użyć wykładników, aby powyższa liczba była jeszcze większa ...

from math import *
s=input()
exec("s=log(s+1);"*99999999999999999999999999999999999)
print(floor(s))

Wypróbuj online!

Leaky Nun
źródło
2
Czy rozwiązania naprawdę muszą działać? To powoduje błąd OverflowError.
ETHproductions
2
@EETH Przy takich problemach powszechnie przyjmuje się, że rozwiązania muszą być teoretycznie wykonalne na maszynie z nieskończoną pamięcią i jednostką centralną. Jeśli chcesz tego spróbować, zmniejsz 99999 ... 999 do zaledwie 999 lub mniej więcej
Sparr
3
Dlaczego więc nie użyć 9**9**9**...**9**9e9?
CalculatorFeline
2

Dół dziennika funkcji (i + 1) iterował 14 razy (Python)

import math
x=lambda i: math.log(i+1)
print int(x(x(x(x(x(x(x(x(x(x(x(x(x(x(input())))))))))))))))

Nie spodziewam się, że będzie to bardzo dobre, ale pomyślałem, że to dobry początek.

Przykłady:

  • e ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n -> ~ n (około n)
PyRulez
źródło
Jeśli użyjesz intzamiast floor, możesz zmieścić innyx(
Beta Decay
@BetaDecay Dobra zaktualizowałem to.
PyRulez
1
Nie powinno to być wyrażenie e^e^e^e...^n? Ponadto, dlaczego po znaku jest spacja :?
CalculatorFeline
@CalculatorFeline, ponieważ nie jest to golf golfowy, musi on mieć mniej niż 100 bajtów.
Cyoce,
Więc? Co jest takiego złego w zapisywaniu bajtu, aby móc dodać kolejne x()połączenie?
CalculatorFeline
2

Rubin, 100 bajtów, wynik -1 = f ω ω + 1 (n 2 )

Zasadniczo zapożyczony z mojego największego numeru do druku , oto mój program:

->k{n=0;n+=1 until(H=->z,a=[0]*z{b,*c=a;z.times{z+=b ?H[z,b==1?c:[b>1?b-1:z]*z+c]:z};z};H[n*n]>k);n}

Wypróbuj online

Zasadniczo oblicza odwrotność f ω ω + 1 (n 2 ) w szybko rosnącej hierarchii. Pierwsze kilka wartości to

x[0] = 1
x[1] = 1
x[2] = 1
x[3] = 1
x[4] = 2

A potem kontynuuje produkcję 2przez bardzo długi czas. Nawet x[G] = 2, gdzie Gjest liczba Grahama.

Po prostu piękna sztuka
źródło
Ale co z g (f <sub> ω9001CK </sub> 3), gdzie f oznacza FGH?
user75200
@ user75200 fgh nie jest dobrze zdefiniowane dla niepoliczalnych porządków.
Po prostu piękna sztuka,
FGH jest dobrze zdefiniowany dla nieobliczalnych rzędnych, ponieważ mają one podstawowe sekwencje. To po prostu nieobliczalne.
user75200,
@ user75200 Nie. Podstawowe sekwencje są bardzo dowolne. Mógłbym zdefiniować ω9001CK [x] = x, aby mieć podstawową sekwencję długości ω9001CK, którą można obliczyć dla skończonego x, ale najprawdopodobniej nie to, co chciałeś. Przez „dobrze zdefiniowane” miałem na myśli, że nie istnieje standardowa podstawowa sekwencja dla nieobliczalnych porządków, na którą wszyscy mogliby się zgodzić.
Po prostu piękna sztuka
Chociaż prawdą jest, że podstawowe sekwencje nie są unikalne, podstawowa sekwencja dla policzonego porządkowego ma mieć długość ω.
Anders Kaseorg,
0

Mathematica, 99 bajtów

(przy założeniu, że ± zajmuje 1 bajt)

0±x_=1±(x-1);y_±0=y+1;x_±y_:=(y-1)±x±(x-1);(i=0;NestWhile[(++i;#±#±#±#±#±#±#±#)&,1,#<k&/.k->#];i)&

Pierwsze 3 polecenia definiują x±ydo oceny Ackermann(y, x).

Wynikiem tej funkcji jest to, ile razy f(#)=#±#±#±#±#±#±#±#należy zastosować 1, zanim wartość osiągnie wartość parametru. Ponieważ f(#)=#±#±#±#±#±#±#±#(czyli f(#)=Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[#, #], #], #], #], #], #], #]) rośnie bardzo szybko, funkcja rośnie bardzo wolno.

użytkownik202729
źródło
0

Clojure, 91 bajtów

(defn f (apply +(for[n(range %)](/(loop[r 1 v n](if(< v 1)r(recur(* r v)(Math/log v))))))))

Rodzaj oblicza sum 1/(n * log(n) * log(log(n)) * ...), który znalazłem stąd . Ale funkcja skończyła się na 101 bajtach, więc musiałem usunąć jawną liczbę iteracji, a zamiast tego iterować, dopóki liczba jest większa niż jeden. Przykładowe dane wyjściowe dla danych wejściowych 10^i:

0 1
1 3.3851305685279143
2 3.9960532565317575
3 4.232195089969394
4 4.370995106860574
5 4.466762285601703
6 4.53872567524327
7 4.595525574477128
8 4.640390570825608

Zakładam, że ta zmodyfikowana seria wciąż się różni, ale teraz wiem, jak to udowodnić.

Trzecia seria faktycznie wymaga liczby wyrażeń googolpleksowych, zanim warunki częściowe przekroczą 10.

NikoNyrh
źródło
0

JavaScript (ES6), 94 bajty

(p=j=>i=>h=>g=>f=>x=>x<2?0:1+p(p(j))(j(i))(i(h))(h(g))(g(f))(f(x)))(_=x=>x)(_)(_)(_)(Math.log)

Objaśnienie :

Idodnosi się x => xponiżej.

Najpierw spójrzmy na:

p = f => x => x < 2 ? 0 : 1 + p(p(f))(f(x))

p(Math.log)jest w przybliżeniu równy log*(x).

p(p(Math.log))jest w przybliżeniu równa log**(x)(ile razy możesz wziąć, log*aż wartość wyniesie najwyżej 1).

p(p(p(Math.log)))jest w przybliżeniu równy log***(x).

Odwrotna funkcja Ackermanna alpha(x)jest w przybliżeniu równa minimalnej liczbie powtórzeń, które trzeba skomponować, paż wartość wyniesie co najwyżej 1.

Jeśli następnie użyjemy:

p = g => f => x => x < 2 ? 0 : 1 + p(p(g))(g(f))(f(x))

wtedy możemy pisać alpha = p(Id)(Math.log).

To dość nudne, więc zwiększmy liczbę poziomów:

p = h => g => f => x => x < 2 ? 0 : 1 + p(p(h))(h(g))(g(f))(f(x))

To jest tak, jak skonstruowaliśmy alpha(x), tyle log**...**(x)że teraz robimy alpha**...**(x).

Po co tu jednak zatrzymywać się?

p = i => h => g => f => x => x < 2 ? 0 : 1 + p(p(i))(i(h))(h(g))(g(f))(f(x))

Jeśli poprzednia funkcja jest f(x)~alpha**...**(x), ta jest teraz ~ f**...**(x). Robimy jeszcze jeden poziom, aby uzyskać nasze ostateczne rozwiązanie.

es1024
źródło
p(p(x => x - 2)) jest w przybliżeniu równe log**(x)(ile razy możesz wziąć, log*aż wartość wyniesie najwyżej 1)”. Nie rozumiem tego stwierdzenia. Wydaje mi się, że p(x => x - 2)powinno to być „tyle razy, ile możesz odjąć, 2aż wartość wyniesie co najwyżej 1”. Oznacza to, że p (x => x - 2) `powinno być funkcją„ dziel przez 2 ”. Dlatego p(p(x => x - 2))powinna być „liczba razy, którą można podzielić przez 2, dopóki wartość nie będzie co najwyżej 1” ... to znaczy, powinna to być logfunkcja, nie log*lub log**. Być może można to wyjaśnić?
matmandan
@mathmandan wygląda na to, że zrobiłem literówkę w tej linii, powinno być p = f => x => x < 2 ? 0 : 1 + p(p(f))(f(x))tam, gdzie pjest przekazywana p(f)jak w innych liniach, a nie f.
es1024