Función exponencial a medias

21

Una función semi-exponencial es aquella que cuando se compone consigo misma da una función exponencial. Por ejemplo, si f(f(x)) = 2^x, entonces fsería una función medio exponencial. En este desafío, calcularás una función semiexponencial específica.

Específicamente, calculará la función desde los enteros no negativos hasta los enteros no negativos con las siguientes propiedades:

  • Monotónicamente creciente: si x < y, entoncesf(x) < f(y)

  • Al menos medio exponencial: para todos x,f(f(x)) >= 2^x

  • Lexicográficamente más pequeña: Entre todas las funciones con las propiedades anteriores, la salida de la que reduce al mínimo f(0), lo que, dado que reduce al mínimo la elección f(1), a continuación f(2), y así sucesivamente.

Los valores iniciales de esta función, para las entradas 0, 1, 2, ...son:

[1, 2, 3, 4, 8, 9, 10, 11, 16, 32, 64, 128, 129, 130, 131, 132, 256, 257, ...]

Puede generar esta función a través de cualquiera de los siguientes métodos, ya sea como función o como programa completo:

  • Tomar xcomo entrada, salida f(x).

  • Tomar xcomo entrada, generar los primeros xvalores de f.

  • Infinitamente salida de todo f.

Si desea tomar xy generar f(x), xdebe estar indexado a cero.

Implementación de referencia

Este es el código de golf: el código más corto en bytes gana. Las lagunas estándar están prohibidas, como siempre.

isaacg
fuente
parece que la definición no se verifica para 0: f (f (0)) = f (1) = 2 pero 2 ^ 0 = 1
Nahuel Fouilleul
y para 1: f (f (1)) = f (2) = 3 pero 2 ^ 1 = 2
Nahuel Fouilleul
1
@NahuelFouilleul el requisito es f (f (x)) > = 2 ^ x.
Martin Ender
1
¿Deberíamos someternos a OEIS ?
Jeppe Stig Nielsen

Respuestas:

8

JavaScript (ES7), 51 48 bytes

Guardado 3 bytes gracias a @Arnauld

f=i=>i?f[f[q=f(i-1),r=f[i]||q+1]=(i>1)<<i,i]=r:1

Toma n y saca el n . ° elemento de la secuencia.


JavaScript (ES7), 70 68 64 bytes

f=(n,a=[],q=1)=>n?f(n-1,a,(n=2**a.indexOf(a.push(q)))<++q?q:n):a

Una función recursiva que toma xy devuelve los primeros xelementos de la secuencia como una matriz.

Cómo funciona

La matriz a se genera de forma procesal, un elemento a la vez, hasta que alcanza la longitud deseada. (Un puerto de la técnica infinita utilizada en la excelente respuesta de Python de xnor probablemente sería más corto).

Podemos hacer la siguiente observación para cada índice i (indexado a 0):

  • Si i existe como un elemento en un índice j ( a [j] = i ), entonces a [i] debe ser al menos 2 j .

Esto es cierto porque f (f (j)) debe ser al menos 2 j , y f (f (j)) es equivalente a a [a [j]] , que a su vez es equivalente a a [i] .

Normalmente la opción correcta es exactamente 2 j . Sin embargo, para el caso singular i = 2 , 2 existe en la matriz en el índice j = 1 , lo que significa que 2 j sería 2, pero esto significa que tendríamos 2 en a [1] y a [2] . Para evitar esto, tomamos el máximo de 2 j y un [i-1] + 1 (uno más que el elemento anterior), que da 3 para i = 2 .

Esta técnica también se encarga de decidir si existe o no j ; si no existe, el .indexOf()método de JS devuelve -1 , lo que lleva a tomar el máximo de a [i-1] + 1 y 2 -1 = 0.5 . Como todos los elementos de la secuencia son al menos 1 , esto siempre devolverá el elemento anterior más uno.

(Estoy escribiendo esta explicación a altas horas de la noche, así que avíseme si algo es confuso o si me perdí algo)

ETHproducciones
fuente
Tenga en cuenta que las entradas 272y más dan respuestas incorrectas debido a problemas de desbordamiento de enteros. Esto está bien, ya que funciona hasta el límite del tipo de datos.
isaacg
Use en 2**lugar de con 1<<suerte solucionar el problema.
usuario202729
Ahora el .99mata la solución. ¿Pero por qué usar +.99y no solo +.9? ¿Cual es la diferencia?
usuario202729
@ user202729 Me siento como un idiota, que quedó allí desde una versión anterior donde estaba usando Math.log2(...)y tuve que calcular el techo. Ahora no es necesario en absoluto. ¡Gracias! Investigaré el 2**asunto: estaba usando 2**...+.99|0originalmente, pero 1<<era más corto porque no necesitaba el |0. Ahora creo que no hay diferencia ...
ETHproductions
2

Perl 5, 53 + 1 ( -p) = 54 bytes

$\=$_>0;map$a[$\=$a[$_]?2**$a[$_]:$\+1]=$_,++$\..$_}{

Pruébalo en línea

Nahuel Fouilleul
fuente
1

Bash, 66 bytes

for((r=$1?2:1,i=2;i<=$1;i++));{ a[r=a[i]?2**a[i]:r+1]=$i;};echo $r

Pruébalo en línea

Nahuel Fouilleul
fuente
1

Jalea , 14 bytes

iL’2*»Ṁ‘$ṭ
⁸Ç¡

Pruébalo en línea!

Cómo funciona

⁸Ç¡         Main link. No arguments.

⁸           Set the left argument and the return value to [].
 Ç¡         Read an integer n from STDIN and call the helper link n times, first on
            [], then on the previous result. Return the last result.


iL’2*»Ṁ‘$ṭ  Helper link. Argument: A (array)

 L          Take the length of A. This is the 0-based index of the next element.
i           Find its 1-based index in A (0 if not present).
  ’         Decrement to a 0-based index (-1 if not present).
   2*       Elevate 2 to the 0-based index.
      Ṁ‘$   Take the maximum of A and increment it by 1.
            Note that Ṁ returns 0 for an empty list.
     »      Take the maximum of the results to both sides.
         ṭ  Tack (append) the result to A.
Dennis
fuente
0

Python 2 , 111 bytes

def f(x):
 a=range(1,2**x)
 for i in range(1,x):a[i]=max(a[i],a[i-1]+1);a[a[i]]=max(a[a[i]],2**i)
 return a[:x]

Pruébalo en línea!

Esta es una modificación significativa de la respuesta del usuario 202729 . Hubiera publicado esta mejora como un comentario, pero la respuesta se elimina y, por lo tanto, los comentarios están deshabilitados.

notjagan
fuente
Esto falla con una excepción de "índice de lista fuera de rango" en la entrada 258. Creo que el problema es que x**2es demasiado pequeño.
isaacg
Bueno ... Python 2 es diferente (a menudo menos bytes) de Python 3.
user202729
1
Como se esperaba, la mitad exponencial es mucho más grande que la cuadrática. La solución obtiene "índice de lista fuera de rango" en x=1000. Es posible que desee probar 2**x, terriblemente grande, pero codegolf es codegolf.
user202729
@ user202729 Ah, esto es cierto. Desafortunadamente, ahora encuentra un problema completamente diferente con entradas más grandes que 2**xcrea un rango demasiado grande para que Python continúe.
notjagan
0

Swift , 137 bytes

func f(n:Int){var l=Array(1...n).map{$0>3 ?0:$0},p=8;if n>3{for i in 3..<n{if l[i]<1{l[i]=l[i-1]+1};if l[i]<n{l[l[i]]=p};p*=2}};print(l)}

Toma la entrada como Int(entero) e imprime como[Int] (matriz entera).

Versión sin golf

func f(n:Int){
    var l = Array(1...n).map{$0 > 3 ? 0 : $0} // Create the range from 1 to n and set all
    var p = 8                                 // values greater than 3 to 0
    if n > 3 {
        for i in 3 ..< n {
            if l[i] < 1 {
                l[i] = l[i - 1] + 1
            }
            if l[i] < n {
                l[l[i]] = p
            }
            p *= 2
        }
    }
    print(l)
}
Herman L
fuente
Tengo curiosidad, ¿qué pasará si eliminas el espacio antes del ??
ETHproductions
@ETHproductions Eso lleva a un error del compilador, ya que los enteros no pueden ser encadenados opcionalmente .
Herman L