The Nth Gryphon Number

Question

I came up with a series of numbers the other day and decided to check what the OEIS number for it was. Much to my surprise, the sequence did not appear to be in the OEIS database, so I decided to name the sequence after myself (note that someone else who's a lot smarter than me has probably already come up with this, and if someone finds the actual name of this sequence, please comment and I'll change the question title). As I couldn't find the sequence anywhere, I decided to name it after myself, hence "Gryphon Numbers". EDIT: Thanks to @Surb for bringing to my attention the fact that this sequence is equal to OEIS sequence A053696 - 1.

A Gryphon number is a number of the form \$a+a^2+...+a^x\$, where both \$a\$ and \$x\$ are integers greater than or equal to two, and the Gryphon sequence is the set of all Gryphon numbers in ascending order. If there are multiple ways of forming a Gryphon number (the first example is \$30\$, which is both \$2+2^2+2^3+2^4\$ and \$5+5^2\$) the number is only counted once in the sequence. The first few Gryphon numbers are: \$6, 12, 14, 20, 30, 39, 42, 56, 62, 72\$.

Your Task:

Write a program or function that receives an integer \$n\$ as input and outputs the \$n\$th Gryphon number.

Input:

An integer between 0 and 10000 (inclusive). You may treat the sequence as either 0-indexed or 1-indexed, whichever you prefer. Please state which indexing system you use in your answer to avoid confusion.

Output:

The Gryphon number corresponding to the input.

Test Cases:

Please note that this assumes the sequence is 0-indexed. If your program assumes a 1-indexed sequence, don't forget to increment all the input numbers.

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

Scoring:

This is code-golf, so the lowest score in bytes wins.

Answer 1

Jelly, 9 bytes

bṖ’ḅi-µ#Ṫ

A full program which reads a (1-indexed) integer from STDIN and prints the result.

Try it online!

How?

A Gryphon number is a number which is expressible in a base less than itself such that all the digits are ones except the least significant, which is a zero. For example:

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

This program takes n, then starts at v=0 and tests for this property and increments v until it finds n such numbers, then outputs the final one.

To test a base b number it subtracts one from every digit, converts from base v, and then checks if the result is \$-1\$. (Note that b is less than v)

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

Answer 2

MATL, 16 13 bytes

:Qtt!^Ys+uSG)

1-based.

Try it online!

Explanation

Consider input n = 3 as an example.

:    % 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

The matrix obtained in step (*) contains possibly repeated Gryphon numbers. In particular, it contains n distinct Gryphon numbers in its first row. These are not necessarily the n smallest Gryphon numbers. However, the lower-left entry 2+2^+···+2^n exceeds the upper-right entry n+n^2, and thus all the numbers in the last row exceed those in the first row. This implies that extending the matrix rightward or downward would not contribute any Gryphon number lower than the lowest n numbers in the matrix. Therefore, the matrix is guaranteed to contain the n smallest Gryphon numbers. Consequently, its n-th lowest unique element is the solution.

Answer 3

Haskell, 53 bytes

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

Try it online!

\$\newcommand{\ta}{{a}}\newcommand{\ti}{{i}}\newcommand{\tx}{{x}}\newcommand{\tn}{{n}}\newcommand{\ty}{{y}}\$A number \$\tn\$ is Gryphon if there exist integers \$\ta \geq 2\$ and \$\tx \geq 2\$ such that \$\tn=\sum_{i=1}^\tx \ta^i\$.

We generate an infinite list of all \$\tn \geq 6\$ such that a brute-force search shows this is the case.

The answer is a (zero-indexed) index function into this list, denoted in Haskell as (list!!).

Why is a^y+n==n*a+a correct?

From the formula for summing a geometric progression:

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

we have, letting \$(\alpha, \rho, \nu) = (\ta, \ta, \tx)\$: $$\tn = \sum_{\ti=1}^\tx \ta^\ti = \frac{\ta(1-\ta^\tx)}{1-\ta} = \frac{\ta-\ta^{\tx+1}}{1-\ta}.$$

Rearranging the equation, we get \$n(1-a) = a - a^{x+1}\$.

Rearranging that even further, we get \$\ta^{\tx+1}+n = \tn \ta + \ta\$.

A substitution \$\ty = \tx+1\$ in the brute-force search yields the final expression a^y+n=n*a+a.

Is searching until n enough?

• If \$\ta > \tn\$ (in other words, \$\ta \geq \tn+1\$), then $$\ta^\ty + \tn > \ta^2 \geq (\tn+1)\ta = \tn\ta + \ta$$ which proves \$\ta^\ty+\tn \neq \tn\ta+\ta\$. So there's no sense checking any of the values \$\ta > \tn\$.

• Similarly: if \$\ty > \tn\$, then $$\ta^\ty + \tn > \ta^\tn = \ta^{\tn-1}\ta \geq 2^{\tn-1}\ta \stackrel{\color{red}*}> (\tn+1)\ta = \tn\ta + \ta,$$ again proving \$\ta^\ty + \tn \neq \tn\ta + \ta\$.

  ^{\$\color{red}{{}^{*}}\$We can assume \$2^{n-1}>n+1\$ because we know \$n \geq 6\$, the smallest Gryphon number.}

Answer 4

Python 3.8 (Pre-release), 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]

Try it online!

0-indexed. Integer division must be used here because f(10000) overflows floats.

Generates all Gryphon numbers where \$2 \leq a \leq n+2\$ and \$2 \leq x \leq n+2\$, sorts them, and selects the \$n\$th element.

-6 bytes thanks to Jonathan Allan

-3 bytes thanks to ArBo. I almost did as he suggested myself, but tried to use {*(...)} which didn't save space anyway

-11 bytes thanks to mathmandan

-7 bytes thanks to ArBo

Mathematical Proof of Validity

Using 0-indexing for the sake of this proof, even though mathematical convention is 1-indexed.

• Let \$G_n\$ be the \$n\$th Gryphon number
• Let \$g(a,x) = a + a^2 + ... + a^x\$ (The Gryphon number from \$a\$ and \$x\$)
• Let \$A_n\$ be the set of all Gryphon numbers where \$2 \leq a \leq n+2\$ and \$2 \leq x \leq n+2\$
• We know that \$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)\$ for all \$a\$ and \$x\$
• \$g(a, x+1) < g(a+1, x+1)\$ for all \$a\$ and \$x\$
• Therefore \$G_{n+1} \neq g(a+1, x+1)\$ if \$G_n = g(a, x)\$
• \$g(a+1, x) < g(a+2, x)\$ for all \$a\$ and \$x\$
• \$g(a, x+1) < g(a, x+2)\$ for all \$a\$ and \$x\$
• Therefore \$G_{n+1}\$ must either be \$g(a+1, x)\$ or \$g(a, x+1)\$ if \$G_n = g(a, x)\$ since no other possibilities exist.
• We can use this information to conclude that \$G_{n+1} \in A_{n+1}\$ if \$G_n \in A_n\$
• Since we know that \$G_0 \in A_0\$, we can use this rule to induce that \$G_n \in A_n\$ for all \$n\$
• Since this can be applied from \$G_0\$ to \$G_n\$, then \$G_n\$ must be at index \$n\$ of \$A_n\$ if \$A_n\$ is ordered from smallest to largest

Answer 5

J, ³⁵ 32 bytes

-3 bytes thanks to FrownyFrog

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

Try it online!

Explanation is same as original. Simply uses explicit form to save bytes be removing the multiple @.

original answer, tacit, with explanation: 35 bytes

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

Try it online!

Similar to Luis Mendo's approach, we create a "power table" (like a times table) with top row 2 3 ... n and left column 1 2 ... n resulting in:

 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

^~/ >: creates the table, and 1+i.@+&2 creates the 1... n sequences, and we add 2 (+&2) to the input to ensure we always have enough elements to create a table even for 0 or 1 inputs.

After we have the table above the solution is trivial. We just scan sum the rows +/\, and then remove the first row, flatten, take unique, and sort /:~@~.@,@}.. Finally { uses the original input to index into that result, producing the answer.

Answer 6

Gaia, 18 bytes

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

Try it online!

1-based index.

This is a rather sad answer with a long nose: )┅: It probably wishes it could be golfed down further.

Copies the algorithm given by Luis Mendo's answer

Answer 7

R, 65 62 bytes

-1 byte thanks to Giuseppe.

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

Try it online!

1-indexed.

Generates a matrix of all values of the form \$a^i\$, takes the cumulative sum, removes the first row (0s) and the second row (entries corresponding to \$x=1\$), then takes the unique sorted values.

Note that sort(unique(...)) would not work, as unique would give unique rows of the matrix, and not unique entries. Using unique(sort(...)) works because sort converts to vector.

Answer 8

JavaScript (ES7), 76 bytes

1-indexed.

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

Try it online!

---

JavaScript (ES7), 89 bytes

1-indexed.

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

Try it online!

Answer 9

Wolfram Language (Mathematica), 51 bytes

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

Try it online!

1-indexed

-8 bytes from @attinat

Answer 10

Charcoal, 36 bytes

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

Try it online! Link is to verbose version of code. 1-indexed. Uses Luis Mendo's algorithm. Explanation:

Ｎθ

Input \$ n \$.

ＦθＦθ⊞υ

Create an \$ n \$-by-\$ n \$ grid of Gryphon numbers and push each one to the predefined list.

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

Calculate the Gryphon number using the fact that \$ \sum_1^x a^i = \frac{a^{x+1}-a}{a-1} \$.

Ｆ⊖θ≔Φυ›κ⌊υυ

Remove the lowest \$ n-1 \$ Gryphon numbers.

Ｉ⌊υ

Print the lowest remaining Gryphon number.

Answer 11

Japt, 23 bytes

Dear Jebus! Either I really have forgotten how to golf or the booze is finally taking its toll!

Not a direct port of Jonathan's solution but very much inspired by his observation.

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

Try it

Answer 12

05AB1E, 12 bytes

L¦ãε`LmO}êIè

0-indexed

Try it online or verify the first \$n\$ items.

Explanation:

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)