Su trabajo es crear la función de crecimiento más lento que pueda en no más de 100 bytes.

Su programa tomará como entrada un número entero no negativo y generará un número entero no negativo. Llamemos a su programa P.

Debe cumplir estos dos criterios:

• Su código fuente debe ser menor o igual a 100 bytes.
• Para cada K, hay una N, de modo que para cada n> = N, P (n)> K. En otras palabras, lim _{(n-> ∞)} P (n) = ∞ . (Esto es lo que significa que esté "creciendo").

Su "puntaje" es la tasa de crecimiento de la función subyacente de su programa.

Más específicamente, el programa P crece más lentamente que Q si hay un N tal que para todos n> = N, P (n) <= Q (n), y hay al menos un n> = N tal que P (n ) <Q (n). Si ninguno de los dos programas es mejor que el otro, están vinculados. (Básicamente, qué programa es más lento se basa en el valor de lim _{(n-> ∞)} P (n) -Q (n).)

La función de crecimiento más lento se define como la que crece más lentamente que cualquier otra función, de acuerdo con la definición del párrafo anterior.

Esta es la tasa de crecimiento del golf , por lo que gana el programa de crecimiento más lento.

Notas:

• Para ayudar en la puntuación, intente poner qué función calcula su programa en la respuesta.
• También ponga algunas entradas y salidas (teóricas), para ayudar a dar a las personas una idea de lo lento que puede ir.

Haskell, 98 bytes, puntaje = f _{ε 0} ⁻¹ ( 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

Cómo funciona

Esto calcula el inverso de una función de crecimiento muy rápido relacionada con el juego de gusanos de Beklemishev . Su tasa de crecimiento es comparable a f _{ε 0} , donde f _α es la jerarquía de rápido crecimiento y ε ₀ es el primer número de épsilon .

Para comparar con otras respuestas, tenga en cuenta que

• la exponenciación es comparable a f ₂ ;
• exponenciación iterada ( tetración o ↑↑ ) es comparable a f ₃ ;
• ↑↑ ⋯ ↑↑ con m flechas es comparable a f _{m + 1} ;
• La función de Ackermann es comparable a f _ω ;
• Las iteraciones repetidas de la función de Ackermann (construcciones como el número de Graham ) todavía están dominadas por f _{ω + 1} ;
• y ε ₀ es el límite de todas las torres ω ^{ω ω ⋰ ω} .

Brachylog , 100 bytes

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

Pruébalo en línea!

Probablemente esto no esté cerca de la lentitud de algunas otras respuestas elegantes, pero no podía creer que nadie hubiera intentado este enfoque simple y hermoso.

Simplemente, calculamos la longitud del número de entrada, luego la longitud de este resultado, luego la longitud de este otro resultado ... 100 veces en total.

Esto crece tan rápido como log (log (log ... log (x), con 100 registros de base 10.

Si ingresa su número como una cadena , esto se ejecutará extremadamente rápido en cualquier entrada que pueda intentar, pero no espere ver un resultado superior a 1: D

JavaScript (ES6), función Ackermann inversa *, 97 bytes

* si lo hice bien

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}

La función Aes la función de Ackermann . aSe supone que la función es la función inversa de Ackermann . Si lo implementé correctamente, Wikipedia dice que no golpeará 5hasta que sea migual 2^2^2^2^16. Tengo una StackOverflowvuelta 1000.

Uso:

console.log(a(1000))

Explicaciones:

Función de Ackermann

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

Función inversa de Ackermann

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

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

La declaración dentro de la evaluación crea una cadena de longitud 7 * 10 ^{10 10 10 10 10 8.57} que consiste en nada más que más llamadas a la función lambda, cada una de las cuales construirá una cadena de longitud similar , una y otra vez hasta que finalmentey convierta en 0. Ostensiblemente esto tiene la misma complejidad que el método Eschew a continuación, pero en lugar de depender de la lógica de si y o control, simplemente rompe cadenas gigantes juntas (y el resultado neto es obtener más pilas ... ¿probablemente?).

El yvalor más grande que puedo suministrar y calcular sin que Python arroje un error es 2, que ya es suficiente para reducir una entrada de max-float para devolver 1.

Una serie de longitud 7.625.597.484.987 es demasiado grande: OverflowError: cannot fit 'long' into an index-sized integer.

Yo debería dejar de.

Esquiar Math.log: Ir a la raíz (10º) (del problema), Puntuación: función efectivamente indistinguible de y = 1.

La importación de la biblioteca matemática está restringiendo el recuento de bytes. Vamos a eliminar eso y reemplazar la log(x)función con algo más o menos equivalente: x**.1y que cuesta aproximadamente el mismo número de caracteres, pero no requiere la importación. Ambas funciones tienen una salida sublineal con respecto a la entrada, pero x ^0.1 crece aún más lentamente . Sin embargo, no nos importa mucho, solo nos importa que tenga el mismo patrón de crecimiento base con respecto a grandes números mientras consume una cantidad comparable de caracteres (por ejemplo, x**.9es la misma cantidad de caracteres, pero crece más rápidamente, por lo que hay es un valor que exhibiría exactamente el mismo crecimiento).

Ahora, qué hacer con 16 personajes. ¿Qué tal ... extender nuestra función lambda para tener propiedades de secuencia de Ackermann? Esta respuesta para grandes números inspiró esta solución.

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

La z**zporción aquí me impide ejecutar esta función con cualquier lugar cercano a las entradas sensatas para yy z, los valores más grandes que puedo usar son 9 y 3 para los cuales obtengo el valor de 1.0, incluso para los soportes más grandes flotantes de Python (nota: while 1.0 es numéricamente mayor que 6.77538853089e-05, el aumento de los niveles de recursión mueve la salida de esta función más cerca de 1, mientras permanece mayor que 1, mientras que la función anterior movió los valores más cerca de 0 mientras permanece mayor que 0, por lo tanto, incluso una recursión moderada en esta función da como resultado tantas operaciones que el número de coma flotante pierde todos los bits significativos).

Reconfigurando la llamada lambda original para tener valores de recursividad de 0 y 2 ...

>>>1.7976931348623157e+308
1.0000000071

Si la comparación se realiza para "compensar desde 0" en lugar de "compensar desde 1", esta función regresa 7.1e-9, que es definitivamente más pequeña que 6.7e-05.

La recursión base del programa real (valor z) es 10 ^{10 10 10 1.97} niveles profundos, tan pronto como y se agota, se restablece con 10 ^{10 10 10 10 1.97} (por lo que un valor inicial de 9 es suficiente), así que no Ni siquiera sé cómo calcular correctamente el número total de recursiones que ocurren: he llegado al final de mi conocimiento matemático. Del mismo modo, no sé si mover una de las **nexponenciaciones de la entrada inicial a la secundaria z**zmejoraría o no el número de recursiones (ídem al revés).

Vayamos aún más lento con aún más recursividad

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 - ahorra 2 bytes sobre int(n)
• import math, math.ahorra 1 byte sobrefrom math import*
• a(...) ahorra 8 bytes en total m(m,...)
• (y>0)*x ahorra un byte másy>0and x
• 9**9**99aumenta el recuento de bytes en 4 y aumenta la profundidad de recursión en aproximadamente 2.8 * 10^xdónde xestá la profundidad anterior (o una profundidad cercana al tamaño de un googolplex: 10 ^{10 94} ).
• 9**9**9e9aumenta el número de bytes en 5 y aumenta la profundidad de recursión en ... una cantidad increíble. La profundidad de recursión es ahora 10 ^{10 10 9.93} , para referencia, un googolplex es 10 ^{10 10 2} .
• Declaración lambda aumenta la recursividad por un paso adicional: m(m(...))a a(a(a(...)))los costos de 7 bytes

Nuevo valor de salida (a 9 profundidades de recursión):

>>>1.7976931348623157e+308
6.77538853089e-05

La profundidad de recursión ha explotado hasta el punto en que este resultado es literalmente sin sentido, excepto en comparación con los resultados anteriores que utilizan los mismos valores de entrada:

• El original llamado log25 veces
• La primera mejora lo llama 81 veces
  • El programa real lo llamaría 1e99 ² o aproximadamente 10 ^{10 2.3} veces
• Esta versión lo llama 729 veces
  • El programa real lo llamaría (9 ^{9 99} ) ³ o un poco menos de 10 ^{10 95} veces).

Lambda Inception, puntuación: ???

Te escuché como lambdas, así que ...

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

Ni siquiera puedo ejecutar esto, apilo el desbordamiento incluso con solo 99 capas de recursión.

El método anterior (a continuación) regresa (omitiendo la conversión a un entero):

>>>1.7976931348623157e+308
0.0909072713593

El nuevo método regresa, usando solo 9 capas de incursión (en lugar del googol completo de ellas):

>>>1.7976931348623157e+308
0.00196323936205

Creo que esto resulta ser de una complejidad similar a la secuencia de Ackerman, solo pequeña en lugar de grande.

También gracias a ETHproductions por un ahorro de 3 bytes en espacios que no sabía que podrían eliminarse.

Vieja respuesta:

El truncamiento de enteros del registro de funciones (i + 1) iteró 20 25 veces (Python) usando lambda'd lambdas.

La respuesta de PyRulez se puede comprimir introduciendo una segunda lambda y apilándola:

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 caracteres utilizados.

Esto produce una iteración de 20 25, sobre el original 12. Además, ahorra 2 caracteres al usar en int()lugar de lo floor()que permite una x()pila adicional . Si los espacios después de la lambda se pueden eliminar (no puedo verificar en este momento), y()se puede agregar un quinto . ¡Posible!

Si hay una manera de omitir la from mathimportación mediante el uso de un nombre completo (por ejemplo x=lambda i: math.log(i+1))), eso ahorraría aún más caracteres y permitiría otra pila dex() pero no sé si Python admite tales cosas (sospecho que no). ¡Hecho!

Este es esencialmente el mismo truco utilizado en la publicación de blog de XCKD en grandes cantidades , sin embargo, la sobrecarga al declarar lambdas impide una tercera pila:

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

Esta es la recursión más pequeña posible con 3 lambdas que excede la altura de la pila calculada de 2 lambdas (al reducir cualquier lambda a dos llamadas, la altura de la pila cae a 18, por debajo de la versión de 2 lambda), pero desafortunadamente requiere 110 caracteres.

Haskell , 100 bytes

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

Pruébalo en línea!

Esta solución no toma el inverso de una función de crecimiento rápido, sino que toma una función de crecimiento bastante lento, en este caso length.show, y la aplica varias veces.

Primero definimos una función f. fes una versión bastarda de la notación uparrow de Knuth que crece un poco más rápido (un poco es un eufemismo, pero los números con los que estamos tratando son tan grandes que en el gran esquema de las cosas ...). Definimos el caso base de f 0 a bser a^bo aal poder de b. Luego definimos el caso general que se (f$c-1)aplicará a las b+2instancias de a. Si estuviéramos definiendo una notación Knuth uparrow como construcción, la aplicaríamos a binstancias de a, pero en b+2realidad es más golfista y tiene la ventaja de crecer más rápido.

Luego definimos el operador #. a#bestá definido para ser length.showaplicado a los b atiempos. Cada aplicación de length.showes aproximadamente igual a log ₁₀ , que no es una función de crecimiento muy rápido.

Luego, definimos nuestra función gque toma un número entero y se aplica length.showal número entero varias veces. Para ser específico, se aplica length.showa la entrada f(f 9 9 9)9 9. Antes de entrar en qué tan grande es esto, veamos f 9 9 9. f 9 9 9es mayor que 9↑↑↑↑↑↑↑↑↑9 (nueve flechas), por un margen masivo. Creo que está en algún lugar entre 9↑↑↑↑↑↑↑↑↑9(nueve flechas) y 9↑↑↑↑↑↑↑↑↑↑9(diez flechas). Ahora, este es un número inimaginablemente grande, demasiado grande para ser almacenado en cualquier computadora existente (en notación binaria). Luego tomamos eso y lo ponemos como el primer argumento de nuestro fque significa que nuestro valor es mayor que 9↑↑↑↑↑↑...↑↑↑↑↑↑9conf 9 9 9flechas en el medio. No voy a describir este número porque es tan grande que no creo que pueda hacerle justicia.

Cada uno length.showes aproximadamente igual a tomar la base de registro 10 del entero. Esto significa que la mayoría de los números devolverán 1 cuando fse les aplica. El número más pequeño para devolver algo distinto de 1 es 10↑↑(f(f 9 9 9)9 9), que devuelve 2. Pensemos en eso por un momento. Tan abominablemente grande como ese número que definimos anteriormente, el número más pequeño que devuelve 2 es 10 a su propia potencia que muchas veces. Eso es 1 seguido de 10↑(f(f 9 9 9)9 9)ceros.

Para el caso general de nla entrada más pequeña, la salida de cualquier n debe ser (10↑(n-1))↑↑(f(f 9 9 9)9 9).

Tenga en cuenta que este programa requiere cantidades masivas de tiempo y memoria incluso para n pequeña (más de lo que hay en el universo muchas veces), si desea probar esto, sugiero reemplazarlo f(f 9 9 9)9 9con un número mucho menor, pruebe 1 o 2 si lo desea Alguna vez obtuviste cualquier salida que no sea 1.

APL, Aplicar log(n + 1), e^9^9...^9veces, donde la longitud de la cadena es e^9^9...^9de longitud de cadena menos 1 veces, y así sucesivamente.

⌊((⍟1+⊢)⍣((*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣(*⍣⊢)))))))))))))))))))))9))⊢

MATL , 42 bytes

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

Pruébalo en línea!

Este programa se basa en la serie armónica con el uso de la constante Euler-Mascheroni. Mientras leía la documentación de @LuisMendo en su lenguaje MATL (con mayúsculas, por lo que parece importante) noté esta constante. La expresión de la función de crecimiento lento es la siguiente:

dónde εk ~ 1 / 2k

Probé hasta 10000 iteraciones (en Matlab, ya que es demasiado grande para TIO) y tiene una puntuación inferior a 10, por lo que es muy lento.

Explicaciones:

 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

Prueba empírica: (ln k ) + 1 en rojo siempre por encima de ln k + γ + εk en azul.

El programa para (ln k ) + 1 se realizó en

Matlab, 47 18 14 bytes

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

Es interesante notar que el tiempo transcurrido para n = 100 es 0.208693s en mi computadora portátil, pero solo 0.121945s con d=rand(1,n);A=d*0; e incluso menos, 0.112147s con A=zeros(1,n). Si los ceros son una pérdida de espacio, ¡ahorra velocidad! Pero estoy divergiendo del tema (probablemente muy lentamente).

Editar: gracias a Stewie por ayudar a reducir esta expresión de Matlab a, simplemente:

 @(n)log(1:n)+1

Python 3 , 100 bytes

El piso del registro de funciones (i + 1) itera 99999999999999999999999999999999999 veces.

Se pueden usar exponentes para hacer que el número anterior sea aún mayor ...

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

Pruébalo en línea!

El piso del registro de funciones (i + 1) iterado 14 veces (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())))))))))))))))

No espero que esto vaya muy bien, pero supuse que era un buen comienzo.

Ejemplos:

• e ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n ^ n -> ~ n (aproximadamente n)

Ruby, 100 bytes, puntaje ^-1 = f _{ω ^{ω + 1}} (n ² )

Básicamente tomado de mi mayor número imprimible , aquí está mi programa:

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

Pruébalo en línea

Básicamente calcula el inverso de f _{ω ^{ω + 1}} (n ² ) en la jerarquía de rápido crecimiento. Los primeros pocos valores son

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

Y luego continúa produciéndose 2durante mucho tiempo. Incluso x[G] = 2, ¿dónde Gestá el número de Graham?

Mathematica, 99 bytes

(suponiendo que ± toma 1 byte)

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

Los primeros 3 comandos definen x±ypara evaluarAckermann(y, x) .

El resultado de la función es la cantidad de veces f(#)=#±#±#±#±#±#±#±#que se debe aplicar a 1 antes de que el valor llegue al valor del parámetro. Como f(#)=#±#±#±#±#±#±#±#(es decir f(#)=Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[#, #], #], #], #], #], #], #]) crece muy rápido, la función crece muy lentamente.

Clojure, 91 bytes

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

Tipo de calcula el sum 1/(n * log(n) * log(log(n)) * ...), que encontré desde aquí . Pero la función terminó con 101 bytes de longitud, por lo que tuve que descartar el número explícito de iteraciones y, en su lugar, iterar siempre que el número sea mayor que uno. Ejemplo de salidas para entradas de 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

Supongo que esta serie modificada aún diverge, pero ahora sé cómo demostrarlo.

La tercera serie realmente requiere un número googolplex de términos antes de que los términos parciales excedan 10.

Javascript (ES6), 94 bytes

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

Explicación :

Id se refiere a x => x continuación.

Primero echemos un vistazo a:

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

p(Math.log) es aproximadamente igual a log*(x) .

p(p(Math.log))es aproximadamente igual a log**(x)(cantidad de veces que puede tomarlog* hasta que el valor sea como máximo 1).

p(p(p(Math.log))) es aproximadamente igual a log***(x) .

La función inversa de Ackermann alpha(x) es aproximadamente igual al número mínimo de veces que necesita componerp hasta que el valor sea como máximo 1.

Si luego usamos:

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

entonces podemos escribir alpha = p(Id)(Math.log) .

Sin embargo, eso es bastante aburrido, así que aumentemos el número de niveles:

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

Así es como construimos alpha(x), excepto que en lugar de hacerlo log**...**(x), ahora hacemosalpha**...**(x) .

¿Por qué detenerse aquí sin embargo?

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

Si la función anterior es f(x)~alpha**...**(x), esta es ahora ~ f**...**(x). Hacemos un nivel más de esto para obtener nuestra solución final.