Calcule el súper logaritmo

29

Esto debería ser un simple desafío.

Dado un número n >= 0, genera el superlogaritmo (o el logaritmo log *, log-star o iterado , que son equivalentes ya nque nunca es negativo para este desafío) n.

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

Esta es una de las dos funciones inversas de la tetración . El otro es la superraíz , que está en una pregunta relacionada .

Ejemplos

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

Reglas

  • No necesita admitir decimales, aunque puede hacerlo.
  • Debe admitir la entrada de al menos 3814280 = ceiling(e^e^e).
  • No puede codificar los valores como 3814280. (Su programa debe teóricamente apoyar a los números más altos.) Quiero un algoritmo para ser implementado.
  • El código más corto gana.

OEIS relacionados

mbomb007
fuente
Relacionado.
Oliver Ni

Respuestas:

14

Jalea , 8 bytes

ÆlÐĿĊḊi1

Pruébalo en línea! o verificar todos los casos de prueba .

Fondo

Comenzamos tomando sucesivamente logaritmos naturales de la entrada y los resultados posteriores hasta que el resultado ya no cambie. Esto funciona porque la extensión del logaritmo natural al plano complejo tiene un punto fijo ; si z = e -W (-1) ≈ 0.318 + 1.337i - donde W denota la función Lambert W - tenemos log (z) = z .

Para la entrada n , después de calcular [n, log (n), log (log (n)),…, z] , primero aplicamos la función de techo a cada uno de los resultados. La implementación de Jelly ( Ċ) en realidad calcula la parte imaginaria del número complejo en su lugar , pero de todos modos no estamos interesados ​​en esto.

Una vez que el k ésimo aplicación de registro se obtiene un valor menor que o igual a 1 , Ċdevolverá 1 por primera vez. El índice basado en 0 de ese primer 1 es el resultado deseado.

La implementación sencilla (calcular el índice basado en 1, decremento) falla debido al caso límite 0 , que no tiene un 1 en su lista de logaritmos. De hecho, para la entrada 0 , la secuencia de logaritmos es

[0, None]

Esto se debe a que el logaritmo de Jelly ( Æl) está sobrecargado; primero intenta math.log(logaritmo real), luego cmath.log(logaritmo complejo) y finalmente "se rinde" y regresa None. Afortunadamente, Ċse sobrecarga de manera similar y simplemente le devuelve el argumento si no puede redondear o tomar una parte imaginaria.

Del mismo modo, la entrada 1 devuelve

[1, 0, None]

lo cual puede crear problemas en otros enfoques que involucran o no Ċ.

Una forma de solucionar este problema es aplicar (eliminar; elimina el primer elemento) a la matriz de logaritmos. Este mapas

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

entonces ninguna de las listas tiene un 1 ahora. De esta manera, encontrar el índice del primer 1 devolverá 0 (no encontrado), que es la salida deseada para las entradas 0 y 1 .

Cómo 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 es uno de los únicos tres átomos en Jelly que están sobrecargados de una manera no obvia.

Dennis
fuente
11

Jalea , 9 bytes

Æl>1$пL’

Pruébalo en línea!

Banco de pruebas. (Ligeramente modificado.)

Explicación

Æ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.
Monja permeable
fuente
7

Javascript, 45 27 26 bytes

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

Aquí está la suite de prueba (3ª rev.)

Gracias @LeakyNun por guardar 1 byte condicional y luego convertir la función a lambda, y @Neil por señalar falso es el valor de retorno correcto para <= 1 (la prueba cambiada es == en lugar de ===)

CShark
fuente
Lo estaba haciendo sin es6, pero sí, sería 1 byte más corto, gracias.
CShark
¿Por qué no usarías lambda?
Leaky Nun
sin una buena razón, simplemente no lo he usado tanto, así que no es mi primer instinto
CShark
Aparentemente, se nos permite regresar en falselugar de 0 (ya que se convierte automáticamente a 0 en una expresión entera) en cuyo caso puede soltar el |0.
Neil
Eso ahorraría 1 byte, pero ¿qué quiere decir con "se convierte automáticamente a 0"? Qué es"?
CShark
6

Mathematica, 21 bytes

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

Función anónima recursiva. Toma un entero como entrada y devuelve su superlogaritmo como salida. Solo usa la definición dada.

LegionMammal978
fuente
3
De hecho, miré con anticipación para ver si había un incorporado. Me sorprendió cuando no lo había. : D
mbomb007
5

Pyth, 10 bytes

L&>b1hy.lb

Banco de pruebas.

Esto define una función.

Monja permeable
fuente
No veo ningún resultado en su conjunto de pruebas. Solo un montón de líneas vacías en la salida.
mbomb007
@ mbomb007 Corregido.
Leaky Nun
Más fresco: tl.u?>N1.l;-)
Jakube
@Jakube ¡Podrías publicar eso!
Leaky Nun
5

Haskell, 23 bytes

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

Ejemplo de uso: l 3814280-> 4.

nimi
fuente
4

Python 3, 45 bytes

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

Para x <= 1, esto vuelve False(que está == 0en Python).

Lynn
fuente
Sí, Falsese puede usar para 0.
mbomb007
Además, superaste mi implementación ingenua (al usar en andlugar de if else). Grats
mbomb007
4

05AB1E, 16 13 bytes

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

Explicación

              # 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

Pruébalo en línea

Emigna
fuente
3

MATL , 15 12 bytes

0`ZetG>~}x@q

Pruébalo en línea! O verifique todos los casos de prueba (versión ligeramente modificada para manejar varias entradas).

Cómo funciona

Comenzando con 0, aplique exponenciación iterada hasta exceder la entrada. La salida es el número de iteraciones 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
fuente
3

J , 21 19 18 16 bytes

¡Ahorré 2 bytes a Leaky Nun, 1 byte a Galen Ivanov y 2 bytes a FrownyFrog!

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

Pruébalo en línea!

Casos de prueba

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
fuente
Aquí está mi solución de 18 bytes: 2#@}.^.^:(0<])^:a:(comencé a sovlar lo que resultó ser un duplicado de este problema).
Galen Ivanov
2#@}.(0>.^.)^:a:parece funcionar.
FrownyFrog
Sin embargo, no estoy seguro de si es equivalente.
FrownyFrog
2

MATLAB / Octave, 44 bytes

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

Intenté hacerlo todo como una función anónima, pero olvidé que MATLAB / Octave continúa evaluando expresiones incluso si se multiplican por un valor booleano falso (cero):

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

costrom
fuente
Sí, sería bueno tener un producto de cortocircuito :-)
Luis Mendo
2

R, 38 37 bytes

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

¡Gracias @ user5957401 por el byte extra!

Casos de prueba:

> 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
fuente
Creo que puede guardar un byte utilizando una instrucción literal if, else. if(x>1)1+f(log(x))else 0es decir, es un byte más corto.
user5957401
2

R , 34 bytes

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

Pruébalo en línea!

Es posible un enfoque no recursivo: 36 bytes y toma la entrada de stdin.

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

Java 7, 47 bytes

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

Pruébalo en línea.

El método recursivo de estilo Java 7 anterior es 2 bytes más corto que un lambda iterativo de estilo Java 8:

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

Pruébalo en línea.

Explicación:

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
fuente
Puede acortarlo con un Java 8 lambda.
mbomb007
@ mbomb007 respondiendo tres años después, jaja ... (en ese momento solo estaba jugando al golf en código en Java 7), pero para responder a su pregunta: no, desafortunadamente, un Java 8 lambda es 2 bytes más largo que el método recursivo. Lo agregué a mi respuesta y también agregué una explicación.
Kevin Cruijssen
¿Entonces no puedes hacer lambdas recursivas?
mbomb007
@ mbomb007 No, en Java lamentablemente no. En Python, JavaScript, y creo que también en C # .NET, las lambdas recursivas son posibles, pero en Java no por alguna razón ...
Kevin Cruijssen
1

Emacs Lisp, 38 bytes

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

Casos de prueba:

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

Jalea , 8 bytes

-Ælß$Ị?‘

Implementación directa de la definición. Pruébalo en línea! o verificar todos los casos de prueba .

Cómo 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
fuente
1

Perl 5, 35 bytes

Muy simple, requiere -M5.016(que es gratis) habilitar la __SUB__palabra clave para la recursión anónima.

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

Otra alternativa es

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

que es de 34 bytes y proporciona la misma salida para todas las entradas> 1, pero devuelve el valor falso especial para las entradas <= 1. Falso es numéricamente igual a cero, pero se imprime como "" (cadena vacía), por lo que probablemente no t calificar.

hobbs
fuente
Gran respuesta. Sin sub{($_=pop)>1?1+__SUB__->(log):0}embargo
Dada
1

CJam (16 bytes)

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

Demostración en línea

Bucle while simple con precondición. (Lo que realmente quiero aquí es una operación de despliegue al estilo de Golfscript, pero CJam no tiene una, y el punto flotante en GolfScript es desordenado y nada golfoso).

Peter Taylor
fuente
Por otro lado, esta es mi respuesta número 80 en matemáticas y hoy me gané mi segunda insignia de etiqueta.
Peter Taylor
1

PARI / GP , 24 bytes

Solo la recursión directa.

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

Raqueta, 61 bytes

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

Arce, 32,30 29 bytes

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

Casos de prueba:

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

R, 36 bytes

Enfoque ligeramente diferente de Plannapus

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

Utiliza una asignación correcta para ejecutar el código, por lo que el número deseado debe precederlo. es decir

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

Mathematica, 29 bytes

Simple como el infierno, y funciona para entradas cómicamente grandes y negativas:

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

ingrese la descripción de la imagen aquí

Landak
fuente
0

Ruby, 29 bytes

l=->n{n<=1?0:1+l[Math.log n]}
Seims
fuente
-1 byte reescribiendo n<=1?a:bcomo n>1?b:ay -1 byte más con funciones lambda anónimas .
Simplemente hermoso arte
0

Perl 6 , 21 bytes

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

Pruébalo en línea!

La expresión entre paréntesis es una secuencia. $_, el argumento de la función, es el primer elemento. *.loggenera cada elemento sucesivo tomando el registro del elemento anterior. La secuencia continúa hasta que la condición final 1 >= *, es verdadera: 1 es mayor o igual que el elemento actual. Restar 1 de la secuencia lo obliga a un número: su longitud.

Sean
fuente