L'autre jour, j'ai trouvé une série de chiffres et j'ai décidé de vérifier quel était le numéro OEIS. À ma grande surprise, la séquence ne semblait pas figurer dans la base de données OEIS, j'ai donc décidé de nommer la séquence d'après moi-même (notez que quelqu'un d'autre qui est beaucoup plus intelligent que moi l'a probablement déjà trouvé, et si quelqu'un trouve le nom réel de cette séquence, veuillez commenter et je changerai le titre de la question). Comme je n'ai pu trouver la séquence nulle part, j'ai décidé de la nommer d'après moi-même, d'où "Gryphon Numbers". EDIT: Merci à @Surb d'avoir porté à mon attention le fait que cette séquence est égale à la séquence OEIS A053696 - 1.

Un nombre Gryphon est un nombre de la forme , où et sont des entiers supérieurs ou égaux à deux, et la séquence Gryphon est l'ensemble de tous les nombres Gryphon en ordre croissant ordre. S'il existe plusieurs façons de former un nombre Gryphon (le premier exemple est , qui est à la fois et ), le nombre n'est compté qu'une seule fois dans la séquence. Les premiers chiffres de Gryphon sont: .$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$

Ta tâche:

Écrivez un programme ou une fonction qui reçoit un entier en entrée et génère le ème numéro de Gryphon. $n$$n$

Contribution:

Un entier entre 0 et 10000 (inclus). Vous pouvez traiter la séquence comme indexée 0 ou indexée 1, selon votre préférence. Veuillez indiquer le système d'indexation que vous utilisez dans votre réponse pour éviter toute confusion.

Sortie:

Le numéro de Gryphon correspondant à l'entrée.

Cas de test:

Veuillez noter que cela suppose que la séquence est indexée 0. Si votre programme suppose une séquence indexée sur 1, n'oubliez pas d'incrémenter tous les nombres saisis.

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

Notation:

C'est le code-golf , donc le score le plus bas en octets gagne.

Gelée , 9 octets

bṖ’ḅi-µ#Ṫ

Un programme complet qui lit un entier (indexé 1) à partir de STDIN et imprime le résultat.

Essayez-le en ligne!

Comment?

Un nombre Gryphon est un nombre qui est exprimable dans une base inférieure à elle-même de telle sorte que tous les chiffres sont un sauf le moins significatif, qui est un zéro. Par exemple:

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

Ce programme prend n, puis démarre à v=0et teste cette propriété et incrémente vjusqu'à ce qu'il trouve de ntels nombres, puis sort le dernier.

Pour tester un bnombre de base, il soustrait un de chaque chiffre, convertit de la base v, puis vérifie si le résultat est . (Notez que c'est moins 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 octets

:Qtt!^Ys+uSG)

1 basé.

Essayez-le en ligne!

Explication

Considérez la saisie n = 3comme exemple.

:    % 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 matrice obtenue à l'étape (*) contient des nombres de Gryphon éventuellement répétés. En particulier, il contient ndes numéros de Gryphon distincts dans sa première ligne. Ce ne sont pas nécessairement les nplus petits nombres de Gryphon. Cependant, l'entrée en bas à gauche 2+2^+···+2^n dépasse l' entrée en haut à droite n+n^2, et donc tous les nombres de la dernière ligne dépassent ceux de la première ligne. Cela implique que l'extension de la matrice vers la droite ou vers le bas ne contribuerait pas à un nombre de Gryphon inférieur aux nnombres les plus bas de la matrice. Par conséquent, la matrice est garantie pour contenir les nplus petits nombres de Gryphon. Par conséquent, son n-ème élément unique le plus bas est la solution.

Haskell , 53 octets

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

Essayez-le en ligne!

$\newcommand{\ta}{{a}}\newcommand{\ti}{{i}}\newcommand{\tx}{{x}}\newcommand{\tn}{{n}}\newcommand{\ty}{{y}}$ Un nombre est Gryphon s'il existe des entiers et tels que .$\tn$$\ta \geq 2$$\tx \geq 2$$\tn=\sum_{i=1}^\tx \ta^i$

Nous générons une liste infinie de tous les telle sorte qu'une recherche par force brute montre que c'est le cas.$\tn \geq 6$

La réponse est une fonction d'index (indexée zéro) dans cette liste, notée dans Haskell comme (list!!).

Pourquoi est-ce a^y+n==n*a+acorrect?

De la formule de sommation d'une progression géométrique :

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

nous avons, laissant :$(\alpha, \rho, \nu) = (\ta, \ta, \tx)$

En réarrangeant l'équation, nous obtenons .$n(1-a) = a - a^{x+1}$

En réarrangeant cela encore plus, nous obtenons .$\ta^{\tx+1}+n = \tn \ta + \ta$

Une substitution dans la recherche par force brute donne l'expression finale .$\ty = \tx+1$a^y+n=n*a+a

La recherche est-elle nsuffisante?

• Si $\ta > \tn$ (en d'autres termes, $\ta \geq \tn+1$ ), alors

  $$\ta^\ty + \tn > \ta^2 \geq (\tn+1)\ta = \tn\ta + \ta$$ ce qui prouve $\ta^\ty+\tn \neq \tn\ta+\ta$ . Il est donc inutile de vérifier les valeurs $\ta > \tn$ .

• $\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}{{}^{*}}$$2^{n-1}>n+1$$n \geq 6$}

Python 3.8 (version préliminaire) , 98 92 89 78 71 octets

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

Essayez-le en ligne!

0 indexé. La division entière doit être utilisée ici car f (10000) déborde flottant.

$2 \leq a \leq n+2$$2 \leq x \leq n+2$$n$

-6 octets grâce à Jonathan Allan

-3 octets grâce à ArBo. J'ai presque fait comme il me l'avait suggéré, mais j'ai essayé d'utiliser {*(...)}ce qui ne permettait pas d'économiser de l'espace

-11 octets grâce à mathmandan

-7 octets grâce à ArBo

Preuve mathématique de validité

Utiliser l'indexation 0 pour cette preuve, même si la convention mathématique est indexée 1.

• $G_n$$n$
• $g(a,x) = a + a^2 + ... + a^x$$a$$x$
• $A_n$$2 \leq a \leq n+2$$2 \leq x \leq n+2$
• $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)$$a$$x$
• $g(a, x+1) < g(a+1, x+1)$$a$$x$
• $G_{n+1} \neq g(a+1, x+1)$$G_n = g(a, x)$
• $g(a+1, x) < g(a+2, x)$$a$$x$
• $g(a, x+1) < g(a, x+2)$$a$$x$
• $G_{n+1}$$g(a+1, x)$$g(a, x+1)$$G_n = g(a, x)$
• $G_{n+1} \in A_{n+1}$$G_n \in A_n$
• $G_0 \in A_0$$G_n \in A_n$$n$
• $G_0$$G_n$$G_n$$n$$A_n$$A_n$

J , ³⁵ 32 octets

-3 octets grâce à FrownyFrog

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

Essayez-le en ligne!

L'explication est la même que l'original. Utilise simplement un formulaire explicite pour enregistrer les octets en supprimant le multiple @.

réponse originale, tacite, avec explication: 35 octets

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

Essayez-le en ligne!

Semblable à l'approche de Luis Mendo, nous créons une "table de puissance" (comme une table de multiplication) avec la ligne du haut 2 3 ... net la colonne de gauche 1 2 ... nrésultant 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

^~/ >:crée la table et 1+i.@+&2crée les 1... nséquences, et nous ajoutons 2 ( +&2) à l'entrée pour nous assurer que nous avons toujours suffisamment d'éléments pour créer une table même pour 0 ou 1 entrées.

Une fois que nous avons le tableau ci-dessus, la solution est triviale. Nous analysons simplement la somme des lignes +/\, puis supprimons la première ligne, aplatissons, prenons unique et trions /:~@~.@,@}.. Enfin, {utilise l'entrée d'origine pour indexer ce résultat, produisant la réponse.

Gaia , 18 octets

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

Essayez-le en ligne!

Index basé sur 1.

C'est une réponse plutôt triste avec un long nez: )┅:il souhaite probablement qu'il puisse être approfondi.

Copie l'algorithme donné par la réponse de Luis Mendo

R , 65 62 octets

-1 octet grâce à Giuseppe.

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

Essayez-le en ligne!

1 indexé.

$a^i$$x=1$

Notez que sort(unique(...))cela ne fonctionnerait pas, car uniquecela donnerait des lignes uniques de la matrice et non des entrées uniques. Utilisation de unique(sort(...))travaux car sortconvertit en vecteur.

JavaScript (ES7), 76 octets

1 indexé.

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

Essayez-le en ligne!

JavaScript (ES7), 89 octets

1 indexé.

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

Essayez-le en ligne!

Wolfram Language (Mathematica) , 51 octets

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

Essayez-le en ligne!

1 indexé

-8 octets de @attinat

Fusain , 36 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. 1 indexé. Utilise l'algorithme de Luis Mendo. Explication:

Ｎθ

$n$

ＦθＦθ⊞υ

$n$$n$

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

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

Ｆ⊖θ≔Φυ›κ⌊υυ

$n-1$

Ｉ⌊υ

Imprimez le plus petit nombre de Gryphon restant.

Japt , 23 octets

Cher Jebus! Soit j'ai vraiment oublié comment jouer au golf, soit l'alcool finit par faire des ravages!

Pas un port direct de la solution de Jonathan mais très inspiré par son observation.

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

Essayez-le

05AB1E , 12 octets

L¦ãε`LmO}êIè

0 indexé

$n$

Explication:

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)