Calcular o superlogaritmo

29

Este deve ser um desafio simples.

Dado um número n >= 0, produza o superlogaritmo (ou log *, log-star ou logaritmo iterado , que são equivalentes, pois nnunca é negativo para esse desafio.) De n.

log * (n): = {0 se n <= 1;  1 + log * (log (n)) se n> 1}

Esta é uma das duas funções inversas à tetração . O outro é a super raiz , que está em uma questão relacionada .

Exemplos

Input       Output
0           0
1           0
2           1
3           2
4           2
...
15          2
16          3
...
3814279     3
3814280     4

Regras

  • Você não precisa suportar decimais, embora possa.
  • Você precisa apoiar a entrada de pelo menos 3814280 = ceiling(e^e^e) .
  • Você não pode codificar os valores como 3814280. (Seu programa deve, teoricamente, suportar números mais altos.) Quero que um algoritmo seja implementado.
  • O menor código vence.

OEIS relacionado

mbomb007
fonte
Relacionado.
Oliver Ni

Respostas:

14

Gelatina , 8 bytes

ÆlÐĿĊḊi1

Experimente online! ou verifique todos os casos de teste .

fundo

Começamos sucessivamente tomando logaritmos naturais da entrada e dos resultados subsequentes até que o resultado não seja mais alterado. Isso funciona porque a extensão do logaritmo natural ao plano complexo tem um ponto fixo ; se z = e -W (-1) ≈ 0,318 + 1,337i - onde W denota a função Lambert W -, temos log (z) = z .

Para a entrada n , após calcular [n, log (n), log (log (n)),…, z] , primeiro aplicamos a função de teto a cada um dos resultados. A implementação de Jelly ( Ċ) na verdade calcula a parte imaginária do número complexo , mas não estamos interessados ​​nisso de qualquer maneira.

Uma vez que a k- ésima aplicação do log produza um valor menor ou igual a 1 , Ċretornará 1 pela primeira vez. O índice baseado em 0 desse primeiro 1 é o resultado desejado.

A implementação direta (cálculo com base no índice 1, decremento) falha devido ao caso 0 de borda , que não possui um 1 em sua lista de logaritmos. De fato, para a entrada 0 , a sequência de logaritmos é

[0, None]

Isso ocorre porque o logaritmo de Jelly ( Æl) está sobrecarregado; primeiro tenta math.log(logaritmo real), depois cmath.log(logaritmo complexo) e finalmente "desiste" e retorna None. Felizmente, Ċestá sobrecarregado de maneira semelhante e simplesmente retorna o argumento se não puder arredondar ou assumir uma parte imaginária.

Da mesma forma, a entrada 1 retorna

[1, 0, None]

o que pode criar problemas em outras abordagens que envolvem ou não Ċ.

Uma maneira de corrigir esse problema é aplicar (desenfileirar; remove o primeiro elemento) à matriz de logaritmos. Este mapeia

0ÆlÐĿ -> [0, None]    -> [None]
1ÆlÐĿ -> [1, 0, None] -> [0, None]

então nenhuma lista tem 1 agora. Dessa forma, encontrar o índice do primeiro 1 retornará 0 (não encontrado), que é a saída desejada para as entradas 0 e 1 .

Como funciona

ÆlÐĿĊḊi1  Main link. Argument: n (non-negative integer)

  ÐĿ      Apply the following link until the results are no longer unique.
Æl          Natural logarithm.
          Return the array of all unique results.
    Ċ     Round all resulting real numbers up to the nearest integer. This takes
          the imaginary part of complex numbers and does nothing for non-numbers.
     Ḋ    Dequeue; remove the first item (n) of the array of results.
      i1  Find the first index of 1 (0 if not found).

Este é um dos únicos três átomos em Jelly sobrecarregados de uma maneira não óbvia.

Dennis
fonte
11

Geléia , 9 bytes

Æl>1$пL’

Experimente online!

Suíte de teste.(Ligeiramente modificado.)

Explicação

Æl>1$пL’
     п    while loop, collect all intermediate results.
  >1$      condition: z>1
Æl         body: natural logarithm.
       L   length of the array containing all intermediate results,
           meaning number of iterations
        ’  minus one.
Freira Furada
fonte
7

Javascript, 45 27 26 bytes

l=a=>a>1&&1+l(Math.log(a))

Aqui está o conjunto de testes (3ª rev)

Obrigado @LeakyNun por salvar 1 byte com função condicional e depois converter para lambda, e @Neil por apontar false é ok, retorne o valor para <= 1 (teste alterado para ser == em vez de ===)

CShark
fonte
Eu estava fazendo isso sem es6, mas sim, isso seria 1 byte menor, obrigado.
CShark
Por que você não usaria lambda?
gotejante Nun
nenhuma boa razão, eu só não usei-o muito, por isso não é o meu primeiro instinto
CShark
Aparentemente, é permitido retornar em falsevez de 0 (pois ele se converte automaticamente em 0 em uma expressão inteira). Nesse caso, você pode soltar o |0.
Neil
Isso economizaria 1 byte, mas o que você quer dizer com "ele se converte automaticamente em 0"? O que é isso"?
CShark
6

Mathematica, 21 bytes

If[#>1,1+#0@Log@#,0]&

Função anônima recursiva. Pega um número inteiro como entrada e retorna seu superlogaritmo como saída. Apenas usa a definição dada.

LegionMammal978
fonte
3
Na verdade, eu olhei com antecedência para ver se havia um built-in. Fiquei surpreso quando não havia. : D
mbomb007
5

Dyalog APL , 13 bytes

Tradução direta do OP:

{⍵≤1:0⋄1+∇⍟⍵}

TryAPL online!

Adão
fonte
5

Pitão, 10 bytes

L&>b1hy.lb

Suíte de teste.

Isso define uma função.

Freira Furada
fonte
Não vejo nenhuma saída no seu conjunto de testes. Apenas um monte de linhas vazias na saída.
mbomb007
@ mbomb007 Fixed.
Freira vazando
Caminho mais frio: tl.u?>N1.l;-)
Jakube
@Jakube Você pode postar isso!
Leaky Nun
5

Haskell, 23 bytes

l x|x>1=1+l(log x)|1<2=0

Exemplo de uso: l 3814280-> 4.

nimi
fonte
4

Python 3, 45 bytes

import math
s=lambda x:x>1and-~s(math.log(x))

Pois x <= 1, isso retorna False(que está == 0em Python).

Lynn
fonte
Sim, Falsepode ser usado para 0.
mbomb007
Além disso, você venceu minha implementação ingênua (usando em andvez de if else). Grats.
mbomb007
4

05AB1E, 16 13 bytes

[Dî2‹#¼žr.n]¾

Explicação

              # implicit input n
[          ]  # infinite loop
 Dî2‹#        # break if n rounded up is less than 2
      ¼       # else, increase counter
       žr.n   # set next n = log(n)
            ¾ # push counter and implicitly print

Experimente online

Emigna
fonte
3

MATL , 15 12 bytes

0`ZetG>~}x@q

Experimente online! Ou verifique todos os casos de teste (versão ligeiramente modificada para lidar com várias entradas).

Como funciona

Começando com 0, aplique a exponenciação iterada até exceder a entrada. A saída é o número de iterações menos 1.

0       % Push 0
`       % Do...while loop
  Ze    %   Exponential
  t     %   Duplicate
  G     %   Push input
  >~    %   Is current value less than or equal to the input? If so: next iteration
}       % Finally (code executed at the end of the last iteration)
  x     %   Delete
  @q    %   Iteration index minus 1
        % Implicitly end loop
        % Implicitly display stack
Luis Mendo
fonte
3

J , 21 19 18 16 bytes

Salva 2 bytes em Leaky Nun, 1 byte em Galen Ivanov e 2 bytes em FrownyFrog!

2#@}.(0>.^.)^:a:

Experimente online!

Casos de teste

ls =: >:@$:@^.`0:@.(<:&1)
   ls 0
0
   ls 1
0
   ls 2
1
   ls 3
2
   ls 4
2
   ls 15
2
   ls 16
3
   ls 3814280
4
Conor O'Brien
fonte
Aqui está a minha solução de 18 bytes: 2#@}.^.^:(0<])^:a:(I começou sovling o que acabou por ser um dup deste problema.)
Galen Ivanov
2#@}.(0>.^.)^:a:parece funcionar.
precisa saber é o seguinte
Não tenho certeza se é equivalente.
precisa saber é o seguinte
2

MATLAB / oitava, 44 bytes

function a=g(n);a=0;if n>1;a=1+g(log(n));end

Tentei fazer tudo isso como uma função anônima, mas esqueci que o MATLAB / Octave continua avaliando expressões mesmo que sejam multiplicadas por um valor booleano false (zero):

f=@(n)(n>1)*(1+f(log(n)))

costrom
fonte
Sim, seria bom ter um-circuito curto produto :-)
Luis Mendo
2

R, 38 bytes 37

f=function(x)if(x>1)1+f(log(x))else 0

Obrigado @ user5957401 pelo byte extra!

Casos de teste:

> f(0)
[1] 0
> f(1)
[1] 0
> f(2)
[1] 1
> f(3)
[1] 2
> f(4)
[1] 2
> f(3814279)
[1] 3
> f(3814280)
[1] 4
plannapus
fonte
Eu acho que você pode salvar um byte usando uma declaração literal if, else. ou seja, if(x>1)1+f(log(x))else 0é um byte mais curto.
user5957401
2

R , 34 bytes

f=pryr::f(`if`(n>1,1+f(log(n)),0))

Experimente online!

É possível uma abordagem não recursiva: 36 bytes e recebe a entrada de stdin.

n=scan()
while((n=log(n))>0)F=F+1
+F
rturnbull
fonte
2

Java 7, 47 bytes

int c(double n){return n>1?1+c(Math.log(n)):0;}

Experimente online.

O método recursivo do estilo Java 7 acima é 2 bytes menor que um lambda iterativo do estilo Java 8:

n->{int c=0;for(;n>1;c++)n=Math.log(n);return c;}

Experimente online.

Explicação:

int c(double n){      // Method with double parameter and integer return-type
  return n>1?         //  If the input is larger than 1:
    1+                //   Return 1 +
      c(Math.log(n))  //   A recursive call with log(input)
   :                  //  Else:
    0;                //   Return 0 instead

n->{                  // Method with double parameter and integer return-type
  int c=0;            //  Create a counter, starting at 0
  for(;n>1;           //  Loop as long as the input is still larger than 1:
    c++)              //   Increase the counter by 1
    n=Math.log(n);    //   And update the input to log(input)
  return c;}          //  After the loop: return the counter as result
Kevin Cruijssen
fonte
Você pode reduzi-lo com um Java 8 lambda.
precisa saber é o seguinte
@ mbomb007 respondendo três anos depois, haha ​​.. (na época eu estava apenas desenvolvendo código no Java 7), mas ainda assim respondo sua pergunta: não, infelizmente um Java 8 lambda é 2 bytes mais longo que o método recursivo. Adicionei à minha resposta e também adicionei uma explicação.
Kevin Cruijssen
Então você não pode fazer lambdas recursivas?
mbomb007 9/08
@ mbomb007 Não, em Java infelizmente não. Em Python, JavaScript, e acho que também em C # .NET, lambdas recursivas são possíveis, mas em Java não por alguma razão ..
Kevin Cruijssen
1

Emacs Lisp, 38 bytes

(defun l(n)(if(> n 1)(1+(l(log n)))0))

Casos de teste:

(mapcar 'l '(0 1 2 3 4 15 16 3814279 3814280))
;; (0 0 1 2 2 2 3 3 4)
Lord Yuuma
fonte
1

Gelatina , 8 bytes

-Ælß$Ị?‘

Implementação direta da definição. Experimente online! ou verifique todos os casos de teste .

Como funciona

-Ælß$Ị?‘  Main link. Argument: x

     Ị    Insignificant; test if |x| ≤ 1.
      ?   If the result is 1:
-           Return -1.
          Else:
   $        Execute the monadic chain formed by the two links to the left.
Æl            Apply natural logarithm to x.
  ß           Recursively call the main link.
       ‘  Increment the result.
Dennis
fonte
1

Perl 5, 35 bytes

Muito simples, requer -M5.016(que é gratuito) ativar a __SUB__palavra - chave para recursão anônima.

sub{$_[0]>1?1+__SUB__->(log pop):0}

Outra alternativa é

sub{$_[0]>1?1+__SUB__->(log pop):0}

que é 34 bytes e fornece a mesma saída para todas as entradas> 1, mas retorna o valor falso especial para as entradas <= 1. False é numericamente igual a zero, mas é impresso como "" (string vazia), portanto provavelmente não ' não se qualifica.

hobbs
fonte
Ótima resposta. Você pode ganhar 1 byte, fazendo sub{($_=pop)>1?1+__SUB__->(log):0}embora
Dada
1

CJam (16 bytes)

rd{_1>}{_ml}w],(

Demonstração online

Loop while simples com pré-condição. (O que eu realmente quero aqui é uma operação de desdobramento no estilo Golfscript, mas o CJam não possui uma, e o ponto flutuante no GolfScript é confuso e nem um pouco golfe).

Peter Taylor
fonte
Como um aparte, esta é minha 80ª resposta em matemática e me valeu meu segundo crachá hoje.
Peter Taylor
1

PARI / GP , 24 bytes

Apenas a recursão direta.

f(n)=if(n>1,1+f(log(n)))
Charles
fonte
1

Raquete, 61 bytes

(λ(x)(letrec([a(λ(b)(if(> b 1)(+ 1 (a(log b)))0))])(a x)))
Steven H.
fonte
1

Bordo, 32,30 29 bytes

f:=x->`if`(x>1,1+f(log(x)),0)

Casos de teste:

> f(0.);
  0
> f(1.);
  0
> f(2.);
  1
> f(3.);
  2
> f(4.);
  2
> f(3814279.);
  3
> f(3814280.);
  4
DSkoog
fonte
1

R, 36 bytes

Abordagem ligeiramente diferente do Plannapus

->n;a=0;while(n>1){a=a+1;n=log(n)};a

Usa uma atribuição correta para executar o código - portanto, o número desejado deve precedê-lo. ie

10->n;a=0;while(n>1){a=a+1;n=log(n)};a
user5957401
fonte
0

Mathematica, 29 bytes

Simples como o inferno, e funciona para entradas cômicas e negativas:

f[x_]:=If[x>1,1+f[Log[x]],0]

enter image description here

Landak
fonte
0

Ruby, 29 bytes

l=->n{n<=1?0:1+l[Math.log n]}
Seims
fonte
-1 byte reescrevendo n<=1?a:bcomo n>1?b:ae -1 mais byte com funções lambda anônimas .
Simply Beautiful Art
0

Perl 6 , 21 bytes

{($_,*.log...1>=*)-1}

Experimente online!

A expressão entre parênteses é uma sequência. $_, o argumento para a função, é o primeiro elemento. *.loggera cada elemento sucessivo tomando o log do elemento anterior. A sequência continua até que a condição final,, 1 >= *seja verdadeira: 1 é maior que ou igual ao elemento atual. Subtrair 1 da sequência o força a um número: seu comprimento.

Sean
fonte