Seu trabalho é criar a função de crescimento mais lento possível em não mais que 100 bytes.

Seu programa terá como entrada um número inteiro não negativo e emitirá um número inteiro não negativo. Vamos chamar o seu programa P.

Ele deve atender a esses dois critérios:

• Seu código-fonte deve ser menor ou igual a 100 bytes.
• Para todo K, existe um N, tal que para todo n> = N, P (n)> K. Em outras palavras, lim _{(n-> ∞)} P (n) = ∞ . (É isso que significa "crescer".)

Sua "pontuação" é a taxa de crescimento da função subjacente do seu programa.

Mais especificamente, o programa P cresce mais lentamente que Q se houver um N tal que para todos n> = N, P (n) <= Q (n) e houver pelo menos um n> = N tal que P (n ) <Q (n). Se nenhum dos programas é melhor que o outro, eles estão vinculados. (Essencialmente, qual programa é mais lento é baseado no valor de lim _{(n-> ∞)} P (n) -Q (n).)

A função de crescimento mais lento é definida como a que cresce mais lentamente que qualquer outra função, de acordo com a definição do parágrafo anterior.

Como o golfe é a taxa de crescimento , o programa de crescimento mais lento vence!

Notas:

• Para ajudar na pontuação, tente colocar a função que seu programa calcula na resposta.
• Coloque também algumas entradas e saídas (teóricas), para ajudar as pessoas a ter uma idéia de quão lento você pode ir.

Haskell, 98 bytes, pontuação = 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

Como funciona

Isso calcula o inverso de uma função de crescimento muito rápido relacionada ao jogo de worms de Beklemishev . Sua taxa de crescimento é comparável a f _{ε 0} , onde f _α é a hierarquia de rápido crescimento e ε ₀ é o primeiro número epsilon .

Para comparação com outras respostas, observe que

• exponenciação é comparável a f ₂ ;
• exponenciação iterada ( tetração ou ↑↑ ) é comparável a f ₃ ;
• ↑↑ with ↑↑ com setas m é comparável a f _{m + 1} ;
• A função Ackermann é comparável a f _ω ;
• iterações repetidas da função Ackermann (construções como o número de Graham ) ainda são dominadas por f _{ω + 1} ;
• e ε ₀ é o limite de todas as torres ω ^{ω ω ⋰ ω} .

Braquilog , 100 bytes

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll

Experimente online!

Provavelmente, isso não está nem perto da lentidão de outras respostas sofisticadas, mas eu não podia acreditar que ninguém havia tentado essa abordagem simples e bonita.

Simplesmente, calculamos o comprimento do número de entrada, o comprimento deste resultado e o comprimento desse outro resultado ... 100 vezes no total.

Isso cresce tão rápido quanto o log (log (log ... log (x)), com 100 logs de base 10.

Se você digitar seu número como uma sequência , isso será executado extremamente rápido em qualquer entrada que você possa tentar, mas não espere ver um resultado maior que 1: D

JavaScript (ES6), Função Inversa Ackermann *, 97 bytes

* se eu fiz direito

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}

Função Aé a função Ackermann . A função adeve ser a função Inversa Ackermann . Se eu o implementei corretamente, a Wikipedia diz que não será atingido 5até que mseja igual 2^2^2^2^16. Eu dou uma StackOverflowvolta 1000.

Uso:

console.log(a(1000))

Explicações:

Função 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))

Função Ackermann Inversa

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

A instrução dentro do eval cria uma cadeia de comprimento 7 * 10 ^{10 10 10 10 10 8,57,} que consiste em nada além de mais chamadas para a função lambda, cada uma das quais constrói uma cadeia de comprimento semelhante , continuamente até eventualmente yse tornar 0. Ostensivelmente isso tem a mesma complexidade do método Eschew abaixo, mas, em vez de depender da lógica de controle if-and-or, ele apenas esmaga cadeias gigantes (e o resultado líquido está ficando mais acumulado ... provavelmente?).

O maior yvalor que posso fornecer e calcular sem o Python gerar um erro é 2, o que já é suficiente para reduzir a entrada de max-float no retorno 1.

A cadeia de comprimento 7.625.597.484.987 é muito grande: OverflowError: cannot fit 'long' into an index-sized integer.

Eu deveria parar.

Evitar Math.log: Indo para a (10ª) raiz (do problema), Pontuação: função efetivamente indistinguível de y = 1.

A importação da biblioteca de matemática está restringindo a contagem de bytes. Vamos acabar com isso e substituir a log(x)função por algo aproximadamente equivalente: x**.1e que custa aproximadamente o mesmo número de caracteres, mas não requer a importação. Ambas as funções têm uma saída sublinear em relação à entrada, mas x ^0,1 cresce ainda mais lentamente . No entanto, não nos importamos muito, apenas nos importamos que ele tenha o mesmo padrão de crescimento base em relação a grandes números enquanto consome um número comparável de caracteres (por exemplo, x**.9é o mesmo número de caracteres, mas cresce mais rapidamente, portanto é algum valor que exibirá exatamente o mesmo crescimento).

Agora, o que fazer com 16 caracteres. Que tal ... estender nossa função lambda para ter propriedades de Sequência Ackermann? Essa resposta para grandes números inspirou essa solução.

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

A z**zparte aqui me impede de executar esta função em qualquer lugar próximo de entradas sãs para ye z, os maiores valores que posso usar são 9 e 3 para os quais recupero o valor de 1,0, mesmo para os maiores suportes flutuantes de Python (nota: enquanto 1.0 é numericamente maior que 6.77538853089e-05, os níveis de recursão aumentados movem a saída dessa função para mais perto de 1, enquanto permanecem maiores que 1, enquanto a função anterior moveu os valores para mais perto de 0 enquanto permanece maior que 0, portanto, mesmo recursão moderada nessa função resulta em tantas operações que o número do ponto flutuante perde todos os bits significativos).

Reconfigurando a chamada lambda original para ter valores de recursão de 0 e 2 ...

>>>1.7976931348623157e+308
1.0000000071

Se a comparação for feita para "compensar de 0" em vez de "compensar de 1", essa função retornará 7.1e-9, que é definitivamente menor que 6.7e-05.

A recursão base do programa real (valor z) tem 10 ^{10 10 10 1,97} níveis de profundidade, assim que y se esgota, ela é redefinida com 10 ^{10 10 10 10 1,97} (e é por isso que um valor inicial de 9 é suficiente), então não nem sei como calcular corretamente o número total de recursões que ocorrem: cheguei ao fim do meu conhecimento matemático. Da mesma forma, não sei se mover uma das **nexponenciações da entrada inicial para a secundária z**zmelhoraria o número de recursões ou não (idem ao contrário).

Vamos ir ainda mais devagar com ainda mais recursão

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 - economiza 2 bytes sobre int(n)
• import math, math.economiza 1 bytefrom math import*
• a(...) economiza 8 bytes no total m(m,...)
• (y>0)*x salva um byte maisy>0and x
• 9**9**99aumenta a contagem de bytes em 4 e aumenta a profundidade da recursão em aproximadamente 2.8 * 10^xonde xestá a profundidade antiga (ou uma profundidade próxima ao googolplex em tamanho: 10 ^{10 94} ).
• 9**9**9e9aumenta a contagem de bytes em 5 e aumenta a profundidade da recursão em ... uma quantidade insana. A profundidade da recursão agora é 10 ^{10 10 9,93} ; para referência, um googolplex é 10 ^{10 10 2} .
• declaração lambda aumenta recursão por um passo extra: m(m(...))a a(a(a(...)))custos 7 bytes

Novo valor de saída (com 9 profundidade de recursão):

>>>1.7976931348623157e+308
6.77538853089e-05

A profundidade da recursão explodiu até o ponto em que esse resultado é literalmente sem sentido, exceto em comparação com os resultados anteriores usando os mesmos valores de entrada:

• O original ligou log25 vezes
• A primeira melhoria chama 81 vezes
  • O programa real chamaria 1e99 ² ou cerca de 10 ^{10 2,3} vezes
• Esta versão chama 729 vezes
  • O programa atual chamaria (9 ^{9 99} ) ³ ou um pouco menos de 10 ^{10 95} vezes).

Lambda Inception, pontuação: ???

Ouvi você gostar de lambdas, então ...

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

Não consigo nem executar isso, empilhar estouro, mesmo com meras 99 camadas de recursão.

O método antigo (abaixo) retorna (pulando a conversão para um número inteiro):

>>>1.7976931348623157e+308
0.0909072713593

O novo método retorna, usando apenas 9 camadas de incursão (em vez de o googol completo delas):

>>>1.7976931348623157e+308
0.00196323936205

Eu acho que isso tem complexidade semelhante à sequência de Ackerman, apenas pequena em vez de grande.

Também graças à ETHproductions por uma economia de 3 bytes em espaços que eu não sabia que poderiam ser removidos.

Resposta antiga:

O truncamento inteiro do log da função (i + 1) repetiu 20 25 vezes (Python) usando lambdas lambda'd.

A resposta de PyRulez pode ser compactada introduzindo um segundo lambda e empilhando-o:

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 usados.

Isso produz uma iteração de 20 25, sobre o 12. original. Além disso, ele salva 2 caracteres usando em int()vez do floor()que permitiu uma x()pilha adicional . Se os espaços após o lambda puderem ser removidos (não posso verificar no momento), um quinto y()pode ser adicionado. Possível!

Se houver uma maneira de pular a from mathimportação usando um nome totalmente qualificado (por exemplo x=lambda i: math.log(i+1))), isso salvaria ainda mais caracteres e permitiria outra pilha, x()mas não sei se o Python suporta essas coisas (suspeito que não). Feito!

Esse é essencialmente o mesmo truque usado na postagem do blog do XCKD em grandes números , no entanto, a sobrecarga na declaração de lambdas impede uma terceira pilha:

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

Essa é a menor recursão possível com três lambdas que excedem a altura da pilha computada de 2 lambdas (reduzir qualquer lambda para duas chamadas reduz a altura da pilha para 18, abaixo da versão 2-lambda), mas infelizmente requer 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#)

Experimente online!

Essa solução não assume o inverso de uma função que cresce rapidamente, mas assume uma função que cresce lentamente, nesse caso length.show, e a aplica várias vezes.

Primeiro, definimos uma função f. fé uma versão bastarda da notação ascendente de Knuth que cresce um pouco mais rápido (um pouco é um pouco de eufemismo, mas os números com os quais estamos lidando são tão grandes que no grande esquema das coisas ...). Definimos o caso base de f 0 a bser a^bou aao poder de b. Em seguida, definimos o caso geral a ser (f$c-1)aplicado às b+2instâncias de a. Se estivéssemos definindo uma notação de Knuth como uma construção, a aplicaríamos a binstâncias de a, mas b+2na verdade é mais golfista e tem a vantagem de crescer mais rapidamente.

Em seguida, definimos o operador #. a#bestá definido para ser length.showaplicado às b ahoras. Cada aplicação de length.showé aproximadamente igual ao log ₁₀ , o que não é uma função que cresce muito rapidamente.

Em seguida, definimos nossa função gque recebe um número inteiro e se aplica length.showao número inteiro várias vezes. Para ser específico, aplica-se length.showà entrada f(f 9 9 9)9 9. Antes de entendermos o tamanho, vamos ver f 9 9 9. f 9 9 9é maior que 9↑↑↑↑↑↑↑↑↑9 (nove setas), por uma margem massiva. Eu acredito que está em algum lugar entre 9↑↑↑↑↑↑↑↑↑9(nove flechas) e 9↑↑↑↑↑↑↑↑↑↑9(dez flechas). Agora, esse é um número inimaginavelmente grande, muito grande para ser armazenado em qualquer computador existente (em notação binária). Nós pegamos isso e colocamos isso como o primeiro argumento do nosso, o fque significa que nosso valor é maior do que 9↑↑↑↑↑↑...↑↑↑↑↑↑9comf 9 9 9setas no meio. Não vou descrever esse número porque é tão grande que não acho que seria capaz de fazer justiça.

Cada um length.showé aproximadamente igual a obter a base de log 10 do número inteiro. Isso significa que a maioria dos números retornará 1 quando ffor aplicada a eles. O menor número para retornar algo diferente de 1 é 10↑↑(f(f 9 9 9)9 9), que retorna 2. Vamos pensar nisso por um momento. Por mais abominável que seja o número que definimos anteriormente, o menor número que retorna 2 é 10 em seu próprio poder tantas vezes. Isso é 1 seguido por 10↑(f(f 9 9 9)9 9)zeros.

Para o caso geral da nmenor entrada de saída, qualquer n deve ser (10↑(n-1))↑↑(f(f 9 9 9)9 9).

Observe que este programa requer quantidades enormes de tempo e memória para n pequenos (mais do que existe no universo muitas vezes); se você quiser testar isso, sugiro que substitua f(f 9 9 9)9 9por um número muito menor; tente 1 ou 2, se quiser. obter qualquer saída diferente de 1.

APL, Apply log(n + 1), e^9^9...^9times, em que o comprimento da cadeia é e^9^9...^9do comprimento da cadeia menos 1 vezes, e assim por diante.

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

MATL , 42 bytes

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

Experimente online!

Este programa é baseado nas séries harmônicas com o uso da constante de Euler – Mascheroni. Enquanto eu lia a documentação do @LuisMendo em sua linguagem MATL (com letras maiúsculas, isso parece importante), notei essa constante. A expressão da função de crescimento lento é a seguinte:

Onde εk ~ 1 / 2k

Testei até 10000 iterações (no Matlab, já que é muito grande para o TIO) e a pontuação é inferior a 10, por isso é muito lento.

Explicações:

 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

Prova empírica: (ln k ) + 1 em vermelho sempre acima de ln k + γ + εk em azul.

O programa para (ln k ) + 1 foi realizado em

Matlab, 47 18 14 bytes

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

Interessante notar que o tempo decorrido para n = 100 é 0,208693s no meu laptop, mas apenas 0,121945s com d=rand(1,n);A=d*0; e menos ainda 0,112147s com A=zeros(1,n). Se zeros é um desperdício de espaço, economiza velocidade! Mas estou divergindo do tópico (provavelmente muito devagar).

Edit: obrigado a Stewie por ajudar a reduzir essa expressão do Matlab para, simplesmente:

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

Python 3 , 100 bytes

O piso do log de funções (i + 1) repetiu 999999999999999999999999999999999 vezes.

Pode-se usar expoentes para tornar o número acima ainda maior ...

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

Experimente online!

O piso do log de funções (i + 1) repetiu 14 vezes (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())))))))))))))))

Não espero que isso funcione muito bem, mas achei que é um bom começo.

Exemplos:

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

Ruby, 100 bytes, pontuação ^-1 = f _{ω ^{ω + 1}} (n ² )

Emprestado basicamente do meu maior número imprimível , aqui está o meu 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}

Experimente online

Calcula basicamente o inverso de f _{ω ^{ω + 1}} (n ² ) na hierarquia de rápido crescimento. Os primeiros valores são

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

E então continua a ser produzido 2por um tempo muito longo. Mesmo x[G] = 2, onde Gestá o número de Graham.

Mathematica, 99 bytes

(assumindo que ± leva 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)&

Os três primeiros comandos definem x±ypara avaliar Ackermann(y, x).

O resultado da função é o número de vezes que f(#)=#±#±#±#±#±#±#±#precisa ser aplicado a 1 antes que o valor chegue ao valor do parâmetro. Como f(#)=#±#±#±#±#±#±#±#(isto é, f(#)=Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[Ackermann[#, #], #], #], #], #], #], #]) cresce muito rápido, a função cresce muito 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 o sum 1/(n * log(n) * log(log(n)) * ...), que eu encontrei a partir daqui . Mas a função terminou com 101 bytes, então tive que eliminar o número explícito de iterações e, em vez disso, iterar, desde que o número seja maior que um. Exemplo de saídas para entradas de10^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

Presumo que essa série modificada ainda diverja, mas agora sei como provar isso.

A terceira série, na verdade, exige um número de termos no googolplex antes que os termos parciais excedam 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)

Explicação :

Id refere-se a x => x a seguir.

Vamos primeiro dar uma olhada em:

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

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

p(p(Math.log))é aproximadamente igual a log**(x)(número de vezes que você podelog* até que o valor seja no máximo 1).

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

A função inversa de Ackermann alpha(x)é aproximadamente igual ao número mínimo de vezes que você precisa compor paté que o valor seja no máximo 1.

Se usarmos:

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

então nós podemos escrever alpha = p(Id)(Math.log).

Isso é muito chato, no entanto, então vamos aumentar o número de níveis:

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

É assim que construímos alpha(x), exceto que ao invés de fazer log**...**(x), agora fazemos alpha**...**(x).

Por que parar aqui embora?

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

Se a função anterior for f(x)~alpha**...**(x), esta é agora ~ f**...**(x). Fazemos mais um nível disso para obter nossa solução final.