Я придумал ряд цифр на днях и решил проверить, что это за номер OEIS. К моему большому удивлению, последовательность, по-видимому, отсутствует в базе данных OEIS, поэтому я решил назвать эту последовательность после себя (обратите внимание, что кто-то, кто намного умнее меня, возможно, уже придумал это, и если кто-то найдет Фактическое название этой последовательности, пожалуйста, прокомментируйте, и я изменю название вопроса). Так как я не мог найти где - нибудь последовательность, я решил назвать его в честь себя, следовательно , «Грифон номера». РЕДАКТИРОВАТЬ: Спасибо @Surb за внимание к тому факту, что эта последовательность равна последовательности OEIS A053696 - 1.

Число Gryphon - это число вида $a+a^2+...+a^x$ , где $a$ и $x$ являются целыми числами, большими или равными двум, а последовательность Gryphon представляет собой набор всех чисел Gryphon в порядке возрастания. Если существует несколько способов формирования числа Gryphon (первый пример - $30$ , который равен $2+2^2+2^3+2^4$ и $5+5^2$ ), число учитывается только один раз в последовательности. Первые несколько чисел Gryphon:$6, 12, 14, 20, 30, 39, 42, 56, 62, 72$ .

Твое задание:

Напишите программу или функцию, которая получает целое число $n$ качестве входных данных и выводит номер $n$ го грифона.

Входные данные:

Целое число от 0 до 10000 (включительно). Вы можете рассматривать последовательность как 0-индексированную или 1-индексированную, в зависимости от того, что вы предпочитаете. Пожалуйста, укажите, какую систему индексации вы используете в своем ответе, чтобы избежать путаницы.

Выход:

Номер Грифон, соответствующий вход.

Тестовые случаи:

Пожалуйста, обратите внимание, что это предполагает, что последовательность 0-индексирована. Если ваша программа использует последовательность с 1 индексом, не забудьте увеличить все введенные числа.

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

Подсчет очков:

Это код-гольф , поэтому выигрывает самая низкая оценка в байтах.

Желе , 9 байт

bṖ’ḅi-µ#Ṫ

Полная программа, которая читает (1-индексированное) целое число из STDIN и печатает результат.

Попробуйте онлайн!

Как?

Число Gryphon - это число, которое может быть выражено на основе меньше, чем она сама, так что все цифры являются единицами, кроме наименее значимого, что является нулем. Например:

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

Эта программа берет n, затем запускает v=0и проверяет это свойство и увеличивает vего до тех пор, пока не найдет nтакие числа, а затем выводит окончательное значение.

Чтобы проверить базу b число, оно вычитает по одному из каждой цифры, конвертирует из базового vи затем проверяет, равен ли результат $-1$ . (Обратите внимание, что bменьше, чем 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

MATL , 16 13 байт

:Qtt!^Ys+uSG)

1 на основе.

Попробуйте онлайн!

объяснение

Рассмотрим ввод n = 3в качестве примера.

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

Матрица, полученная на шаге (*), содержит, возможно, повторяющиеся числа грифонов. В частности, nв первом ряду он содержит разные числа грифонов. Это не обязательно самые nмаленькие цифры Gryphon. Однако левая нижняя запись 2+2^+···+2^n превышает правую верхнюю запись n+n^2, и, таким образом, все числа в последнем ряду превышают числа в первом ряду. Это подразумевает, что расширение матрицы вправо или вниз не приведет к тому, что число грифонов будет меньше, чем самые низкие nчисла в матрице. Следовательно, матрица гарантированно содержит nнаименьшие числа грифонов. Следовательно, его nвторым самым низким уникальным элементом является решение.

Haskell , 53 байта

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

Попробуйте онлайн!

$\newcommand{\ta}{{a}}\newcommand{\ti}{{i}}\newcommand{\tx}{{x}}\newcommand{\tn}{{n}}\newcommand{\ty}{{y}}$Число $\tn$ является грифоном, если существуют целые числа $\ta \geq 2$ и $\tx \geq 2$ такие что $\tn=\sum_{i=1}^\tx \ta^i$ .

Мы генерируем бесконечный список всех $\tn \geq 6$ такой, что поиск методом грубой силы показывает, что это так.

Ответом является индексная функция с нулевым индексом в этом списке, обозначаемая в Haskell как (list!!).

Почему a^y+n==n*a+aправильно?

Из формулы для суммирования геометрической прогрессии :

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

имеем: $(\alpha, \rho, \nu) = (\ta, \ta, \tx)$ :

Переставляя уравнение, мы получаем $n(1-a) = a - a^{x+1}$ .

Переставив это еще дальше, мы получим $\ta^{\tx+1}+n = \tn \ta + \ta$ .

Подстановка $\ty = \tx+1$ в поиске методом грубой силы дает окончательное выражение a^y+n=n*a+a.

nДостаточно ли поиска ?

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

• $\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}{{}^{*}}$We can assume $2^{n-1}>n+1$ because we know $n \geq 6$, the smallest Gryphon number.}

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

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.

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

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.

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!

Wolfram Language (Mathematica), 51 bytes

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

Try it online!

1-indexed

-8 bytes from @attinat

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.

Japt , 23 байта

Дорогой Джебус! Либо я действительно забыл, как играть в гольф, либо выпивка наконец берет свое!

Не прямой путь решения Джонатана, но очень вдохновленный его наблюдением.

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

Попытайся

05AB1E , 12 байтов

L¦ãε`LmO}êIè

0 индексированные

Попробуйте онлайн или проверьте первый$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)