El otro día se me ocurrió una serie de números y decidí verificar cuál era el número OEIS. Para mi sorpresa, la secuencia no parecía estar en la base de datos de OEIS, así que decidí nombrar la secuencia después de mí (tenga en cuenta que alguien más que es mucho más inteligente que yo probablemente ya haya llegado a esto, y si alguien encuentra el nombre real de esta secuencia, comente y cambiaré el título de la pregunta). Como no pude encontrar la secuencia en ningún lado, decidí ponerle un nombre, de ahí "Números de grifos". EDITAR: Gracias a @Surb por llamar mi atención sobre el hecho de que esta secuencia es igual a la secuencia OEIS A053696 - 1.

Un número de grifo es un número de la forma , donde y son enteros mayores o iguales que dos, y la secuencia de grifo es el conjunto de todos los números de grifo en forma ascendente orden. Si hay varias formas de formar un número de grifo (el primer ejemplo es , que es y ), el número solo se cuenta una vez en la secuencia. Los primeros números de Gryphon son: .$a+a^2+...+a^x$$a$$x$$30$$2+2^2+2^3+2^4$$5+5^2$$6, 12, 14, 20, 30, 39, 42, 56, 62, 72$

Tu tarea:

Escribir un programa o función que recibe un número entero como entrada y salida a la ésimo número Gryphon. $n$$n$

Entrada:

Un entero entre 0 y 10000 (inclusive). Puede tratar la secuencia como indexada a 0 o indexada a 1, lo que prefiera. Indique qué sistema de indexación utiliza en su respuesta para evitar confusiones.

Salida:

El número de grifo correspondiente a la entrada.

Casos de prueba:

Tenga en cuenta que esto supone que la secuencia está indexada en 0. Si su programa asume una secuencia indexada en 1, no olvide incrementar todos los números de entrada.

Input:    Output:
0   --->  6
3   --->  20
4   --->  30
10  --->  84
99  --->  4692
9999 -->  87525380

Tanteo:

Este es el código de golf , por lo que gana la puntuación más baja en bytes.

Jalea , 9 bytes

bṖ’ḅi-µ#Ṫ

Un programa completo que lee un número entero (1 indexado) de STDIN e imprime el resultado.

Pruébalo en línea!

¿Cómo?

Un número de Gryphon es un número que se puede expresar en una base menor que sí mismo, de modo que todos los dígitos son unos excepto el menos significativo, que es un cero. Por ejemplo:

$30=1\times 2^4+1\times 2^3+1\times2^2+1\times2^1+0\times2^0 \rightarrow 30_2 = 11110$

$84=1\times 4^3+1\times 4^2+1\times 4^1+0\times 4^0 \rightarrow 84_4 = 1110$

Este programa toma n, luego comienza v=0y comprueba esta propiedad e incrementa vhasta encontrar nesos números, luego genera el último.

Para probar un bnúmero base , resta uno de cada dígito, convierte de base vy luego verifica si el resultado es . (Tenga en cuenta que es menor que )$-1$bv

$30_2 \rightarrow 0\times 30^4+0\times 30^3+0\times30^2+0\times30^1+(-1)\times30^0 = -1$

$84_4 \rightarrow 0\times 84^3+0\times 84^2+0\times 84^1+(-1)\times 84^0 = -1$

bṖ’ḅi-µ#Ṫ - Main Link: no arguments
       #  - set v=0 then count up collecting n=STDIN matches of:
      µ   -  the monadic link -- i.e. f(v):  e.g. v=6
 Ṗ        -    pop (implicit range of v)            [1,2,3,4,5]
b         -    to base (vectorises)                 [[1,1,1,1,1,1],[1,1,0],[2,0],[1,2],[1,1]]
  ’       -    decrement (vectorises)               [[0,0,0,0,0,0],[0,0,-1],[1,-1],[0,1],[0,0]]
   ḅ      -    from base (v) (vectorises)           [0,-1,5,1,0]
     -    -    literal -1                           -1
    i     -    first index of (zero if not found)   2
          - }  e.g. n=11 -> [6,12,14,20,30,39,42,56,62,72,84]
        Ṫ - tail         -> 84
          - implicit print

MATL , 16 13 bytes

:Qtt!^Ys+uSG)

Basado en 1.

Pruébalo en línea!

Explicación

Considere la entrada n = 3como un ejemplo.

:    % Implicit input: n. Range
     % STACK: [1 2 3]
Q    % Add 1, element-wise
     % STACK: [2 3 4]
tt   % Duplicate twice, transpose
     % STACK: [2 3 4], [2 3 4], [2;
                                 3;
                                 4]
^    % Power, element-wise with broadcast
     % STACK: [2 3 4], [ 4   9  16;
                         8  27  64;
                        16  81 256]
Ys   % Cumulative sum of each column
     % STACK: [2 3 4], [ 4    9  16;
                         12  36  80;
                         28 117 336]
+    % Add, element-wise with broadcast (*)
     % STACK: [ 6  12  20;
               14  39  84
               30 120 340]
u    % Unique elements. Gives a column vector
     % STACK: [  6;
                14;
                30;
                12;
               ···
               340]
S    % Sort
     % STACK: [  6;
                12
                14;
                20;
               ···
               340]
G)   % Push input again, index. This gets the n-th element. Implicit display
     % STACK: 14

La matriz obtenida en el paso (*) contiene posiblemente números repetidos de Gryphon. En particular, contiene ndistintos números de Gryphon en su primera fila. Estos no son necesariamente los nnúmeros más pequeños de Gryphon. Sin embargo, la entrada inferior izquierda 2+2^+···+2^n excede la entrada superior derecha n+n^2y, por lo tanto, todos los números en la última fila exceden los de la primera fila. Esto implica que extender la matriz hacia la derecha o hacia abajo no contribuiría con ningún número de Gryphon menor que los nnúmeros más bajos de la matriz. Por lo tanto, se garantiza que la matriz contenga los nnúmeros de Gryphon más pequeños. En consecuencia, su nelemento único más bajo es la solución.

Haskell , 53 bytes

([n|n<-[6..],or[a^y+n==n*a+a|a<-[2..n],y<-[3..n]]]!!)

Pruébalo en línea!

$\newcommand{\ta}{{a}}\newcommand{\ti}{{i}}\newcommand{\tx}{{x}}\newcommand{\tn}{{n}}\newcommand{\ty}{{y}}$ Un número es Gryphon si existen enteros y modo que .$\tn$$\ta \geq 2$$\tx \geq 2$$\tn=\sum_{i=1}^\tx \ta^i$

Generamos una lista infinita de todos modo que una búsqueda de fuerza bruta muestra que este es el caso.$\tn \geq 6$

La respuesta es una función de índice (indexado a cero) en esta lista, denotada en Haskell como (list!!).

¿Por qué es a^y+n==n*a+acorrecto?

De la fórmula para sumar una progresión geométrica :

$$\sum_{i=1}^\nu \alpha \rho^{i-1} = \frac{\alpha(1-\rho^\nu)}{1-\rho}$$

tenemos, dejando :$(\alpha, \rho, \nu) = (\ta, \ta, \tx)$

Al reorganizar la ecuación, obtenemos .$n(1-a) = a - a^{x+1}$

Reorganizando eso aún más, obtenemos .$\ta^{\tx+1}+n = \tn \ta + \ta$

Una sustitución en la búsqueda de fuerza bruta produce la expresión final .$\ty = \tx+1$a^y+n=n*a+a

¿Está buscando hasta que sea nsuficiente?

• Si (en otras palabras, ), entonces que prueba . Por lo tanto, no tiene sentido verificar ninguno de los valores .$\ta > \tn$$\ta \geq \tn+1$

  $$\ta^\ty + \tn > \ta^2 \geq (\tn+1)\ta = \tn\ta + \ta$$ $\ta^\ty+\tn \neq \tn\ta+\ta$$\ta > \tn$

• Del mismo modo: si , entonces demostrando nuevamente .$\ty > \tn$

  $$\ta^\ty + \tn > \ta^\tn = \ta^{\tn-1}\ta \geq 2^{\tn-1}\ta \stackrel{\color{red}*}> (\tn+1)\ta = \tn\ta + \ta,$$ $\ta^\ty + \tn \neq \tn\ta + \ta$

  ^{$\color{red}{{}^{*}}$ Podemos suponer porque sabemos , el número de Gryphon más pequeño.$2^{n-1}>n+1$$n \geq 6$}

Python 3.8 (versión preliminar) , 98 92 89 78 71 bytes

lambda n:sorted({a*~-a**x//~-a for a in(r:=range(2,n+3))for x in r})[n]

Pruébalo en línea!

0 indexado. La división de enteros se debe usar aquí porque f (10000) desborda los flotadores.

Genera todos los números Gryphon donde y , los ordena, y selecciona el -ésimo elemento.$2 \leq a \leq n+2$$2 \leq x \leq n+2$$n$

-6 bytes gracias a Jonathan Allan

-3 bytes gracias a ArBo. Casi hice lo que me sugirió, pero traté de usar {*(...)}lo que de todos modos no ahorró espacio

-11 bytes gracias a Mathmandan

-7 bytes gracias a ArBo

Prueba matemática de validez

Uso de la indexación 0 en aras de esta prueba, a pesar de que la convención matemática está indexada en 1.

• Deje ser el º número Gryphon$G_n$$n$
• Sea (El número de grifo de y )$g(a,x) = a + a^2 + ... + a^x$$a$$x$
• Sea el conjunto de todos los números de Gryphon donde y$A_n$$2 \leq a \leq n+2$$2 \leq x \leq n+2$
• Sabemos que$A_0 = \{ g(2,2) \} = \{ 6 \} = \{ G_0 \}$
• $A_{n+1} = \{ g(a, x), g(a+1, x), g(a, x+1), g(a+1, x+1) | g(a, x) \in A_n \}$
• $g(a+1, x) < g(a+1, x+1)$ para todos y$a$$x$
• $g(a, x+1) < g(a+1, x+1)$ para todos y$a$$x$
• Por lo tanto, si$G_{n+1} \neq g(a+1, x+1)$$G_n = g(a, x)$
• $g(a+1, x) < g(a+2, x)$ para todos y$a$$x$
• $g(a, x+1) < g(a, x+2)$ para todos y$a$$x$
• Por lo tanto, debe ser o si ya que no existen otras posibilidades.$G_{n+1}$$g(a+1, x)$$g(a, x+1)$$G_n = g(a, x)$
• Podemos usar esta información para concluir que si$G_{n+1} \in A_{n+1}$$G_n \in A_n$
• Como sabemos que , podemos usar esta regla para inducir que para todos los$G_0 \in A_0$$G_n \in A_n$$n$
• Como esto se puede aplicar de a , debe estar en el índice de si se ordena de menor a mayor$G_0$$G_n$$G_n$$n$$A_n$$A_n$

J , ³⁵ 32 bytes

-3 bytes gracias a FrownyFrog

3 :'y{/:~~.,}.+/\(^~/>:)1+i.y+2'

Pruébalo en línea!

La explicación es la misma que la original. Simplemente usa la forma explícita para guardar los bytes al eliminar el múltiplo @.

respuesta original, tácita, con explicación: 35 bytes

{[:/:~@~.@,@}.[:+/\@(^~/>:)1+i.@+&2

Pruébalo en línea!

Similar al enfoque de Luis Mendo, creamos una "tabla de potencia" (como una tabla de tiempos) con la fila superior 2 3 ... ny la columna izquierda que 1 2 ... nresultan en:

 2   3    4     5     6      7
 4   9   16    25    36     49
 8  27   64   125   216    343
16  81  256   625  1296   2401
32 243 1024  3125  7776  16807
64 729 4096 15625 46656 117649

^~/ >:crea la tabla, y 1+i.@+&2crea las 1... nsecuencias, y agregamos 2 ( +&2) a la entrada para asegurarnos de que siempre tengamos suficientes elementos para crear una tabla, incluso para 0 o 1 entradas.

Después de tener la tabla de arriba, la solución es trivial. Simplemente escaneamos la suma de las filas +/\, y luego eliminamos la primera fila, aplanamos, tomamos únicos y ordenamos /:~@~.@,@}.. Finalmente {usa la entrada original para indexar ese resultado, produciendo la respuesta.

Gaia , 18 bytes

)┅:1D¤*‡+⊣¦tv<_uȯE

Pruébalo en línea!

Índice basado en 1.

Esta es una respuesta bastante triste con una nariz larga: )┅:probablemente desearía poder jugar más golf.

Copia el algoritmo dado por la respuesta de Luis Mendo

R , 65 62 bytes

-1 byte gracias a Giuseppe.

n=scan();unique(sort(diffinv(t(outer(2:n,1:n,"^")))[3:n,]))[n]

Pruébalo en línea!

1 indexado.

$a^i$$x=1$

Tenga en cuenta que sort(unique(...))no funcionaría, ya uniqueque daría filas únicas de la matriz y no entradas únicas. Usar unique(sort(...))obras porque se sortconvierte en vector.

JavaScript (ES7), 76 bytes

1 indexado.

f=(n,a=[i=2])=>(n-=a.some(j=>a.some(k=>(s+=j**k)==i,s=j)))?f(n,[...a,++i]):i

Pruébalo en línea!

JavaScript (ES7), 89 bytes

1 indexado.

n=>eval('for(a=[i=1e4];--i>1;)for(s=1e8+i,x=1;a[s+=i**++x]=x<26;);Object.keys(a)[n]-1e8')

Pruébalo en línea!

Wolfram Language (Mathematica) , 51 bytes

(Union@@Array[Sum[(#2+1)^k,{k,#+1}]&,{30,#}])[[#]]&

Pruébalo en línea!

1 indexado

-8 bytes de @attinat

Carbón , 36 bytes

ＮθＦθＦθ⊞υ÷⁻Ｘ⁺²ι⁺³κ⁺²ι⊕ιＦ⊖θ≔Φυ›κ⌊υυＩ⌊υ

Pruébalo en línea! El enlace es a la versión detallada del código. 1 indexado. Utiliza el algoritmo de Luis Mendo. Explicación:

Ｎθ

$n$

ＦθＦθ⊞υ

$n$$n$

÷⁻Ｘ⁺²ι⁺³κ⁺²ι⊕ι

$\sum_1^x a^i = \frac{a^{x+1}-a}{a-1}$

Ｆ⊖θ≔Φυ›κ⌊υυ

Elimina los más bajos$n-1$

Ｉ⌊υ

Imprima el número de grifo restante más bajo.

Japt , 23 bytes

Querido Jebus! ¡O realmente he olvidado cómo jugar golf o el alcohol finalmente está pasando factura!

No es un puerto directo de la solución de Jonathan, pero está muy inspirado por su observación.

@ÈÇXìZ mÉ ìZÃeÄ}fXÄ}gNÅ

Intentalo

05AB1E , 12 bytes

L¦ãε`LmO}êIè

0 indexado

$n$

Explicación:

L             # Create a list in the range [1, (implicit) input-integer]
              #  i.e. 4 → [1,2,3,4]
 ¦            # Remove the first item to make the range [2, input-integer]
              #  i.e. [1,2,3,4] → [2,3,4]
  ã           # Create each possible pair of this list by using the cartesian product
              #  i.e. [2,3,4] → [[2,2],[2,3],[2,4],[3,2],[3,3],[3,4],[4,2],[4,3],[4,4]]
   ε          # Map each pair to:
    `         #  Push the values of the pair separately to the stack
              #   i.e. [4,3] → 4 and 3
     L        #  Take the list [1, value] for the second value of the two
              #   i.e. 3 → [1,2,3]
      m       #  And then take the first value to the power of each integer in this list
              #   i.e. 4 and [1,2,3] → [4,16,64]
       O      #  After which we sum the list
              #   i.e. [4,16,64] → 84
        }ê    # After the map: uniquify and sort the values
              #  i.e. [6,14,30,12,39,120,20,84,340] → [6,12,14,20,30,39,84,120,340]
          Iè  # And index the input-integer into it
              #  i.e. [6,12,14,20,30,39,84,120,340] and 4 → 30
              # (after which the result is output implicitly)