Saya datang dengan serangkaian nomor hari yang lain dan memutuskan untuk memeriksa apa nomor OEIS itu. Betapa terkejutnya saya, urutannya tampaknya tidak ada dalam database OEIS, jadi saya memutuskan untuk memberi nama urutannya sendiri (perhatikan bahwa orang lain yang jauh lebih pintar dari saya mungkin telah menemukan ini, dan jika seseorang menemukan nama sebenarnya dari urutan ini, beri komentar dan saya akan mengubah judul pertanyaan). Karena saya tidak dapat menemukan urutan di mana pun, saya memutuskan untuk menamainya sendiri, maka "Gryphon Numbers". EDIT: Terima kasih kepada @Surb karena telah memperhatikan fakta bahwa urutan ini sama dengan urutan OEIS A053696 - 1.

Angka Gryphon adalah angka dari bentuk $a+a^2+...+a^x$ , di mana $a$ dan $x$ adalah bilangan bulat lebih besar dari atau sama dengan dua, dan urutan Gryphon adalah himpunan semua angka Gryphon dalam urutan menaik. Jika ada beberapa cara untuk membentuk nomor Gryphon (contoh pertama adalah $30$ , yang keduanya $2+2^2+2^3+2^4$ dan $5+5^2$ ) jumlahnya hanya dihitung satu kali dalam urutan. Beberapa angka Gryphon pertama adalah:$6, 12, 14, 20, 30, 39, 42, 56, 62, 72$ .

Tugas Anda:

Tulis program atau fungsi yang menerima bilangan bulat $n$ sebagai input dan menampilkan nomor Gryphon ke- $n$ .

Memasukkan:

Integer antara 0 dan 10.000 (inklusif). Anda dapat memperlakukan urutan sebagai 0-diindeks atau 1-diindeks, mana yang Anda inginkan. Harap sebutkan sistem pengindeksan yang Anda gunakan dalam jawaban Anda untuk menghindari kebingungan.

Keluaran:

Nomor Gryphon sesuai dengan input.

Kasus uji:

Harap dicatat bahwa ini mengasumsikan urutan diindeks 0. Jika program Anda mengasumsikan urutan 1-diindeks, jangan lupa untuk menambah semua angka input.

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

Mencetak:

Ini adalah kode-golf , sehingga skor terendah dalam byte menang.

Jelly , 9 byte

bṖ’ḅi-µ#Ṫ

Program lengkap yang membaca integer (1-diindeks) dari STDIN dan mencetak hasilnya.

Cobalah online!

Bagaimana?

Angka Gryphon adalah angka yang dapat diekspresikan dalam basis kurang dari itu sendiri sehingga semua digit adalah yang kecuali yang paling tidak signifikan, yaitu nol. Sebagai contoh:

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

Program ini mengambil n, kemudian mulai v=0dan menguji untuk properti ini dan kenaikan vsampai menemukan nangka-angka seperti itu, kemudian mengeluarkan yang terakhir.

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

:Qtt!^Ys+uSG)

Berbasis 1.

Cobalah online!

Penjelasan

Pertimbangkan input n = 3sebagai contoh.

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

Matriks yang diperoleh pada langkah (*) berisi angka Gryphon yang mungkin diulang. Secara khusus, ini berisi nnomor Gryphon yang berbeda di baris pertama. Ini belum tentu nangka Gryphon terkecil. Namun, entri kiri bawah 2+2^+···+2^n melebihi entri kanan atas n+n^2, dan dengan demikian semua angka di baris terakhir melebihi yang ada di baris pertama. Ini menyiratkan bahwa memperluas matriks ke kanan atau ke bawah tidak akan menyumbang angka Gryphon yang lebih rendah dari nangka terendah dalam matriks. Oleh karena itu, matriks dijamin mengandung nangka Gryphon terkecil. Akibatnya, nelemen unik terendah ke -nya adalah solusinya.

Haskell , 53 byte

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

Cobalah online!

$\newcommand{\ta}{{a}}\newcommand{\ti}{{i}}\newcommand{\tx}{{x}}\newcommand{\tn}{{n}}\newcommand{\ty}{{y}}$ Angka adalah Gryphon jika ada bilangan bulat dan sedemikian rupa sehingga .$\tn$$\ta \geq 2$$\tx \geq 2$$\tn=\sum_{i=1}^\tx \ta^i$

Kami membuat daftar semua yang tidak terbatas dari semua sehingga pencarian dengan kekerasan menunjukkan hal ini.$\tn \geq 6$

Jawabannya adalah fungsi indeks (tanpa indeks) ke dalam daftar ini, dilambangkan dalam Haskell as (list!!).

Mengapa itu a^y+n==n*a+abenar?

Dari rumus untuk menjumlahkan perkembangan geometrik :

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

yang kita miliki, membiarkan :$(\alpha, \rho, \nu) = (\ta, \ta, \tx)$

Mengatur ulang persamaan, kita mendapatkan .$n(1-a) = a - a^{x+1}$

Menyusun ulang itu lebih jauh, kita mendapatkan .$\ta^{\tx+1}+n = \tn \ta + \ta$

Substitusi dalam pencarian brute-force menghasilkan ekspresi akhir .$\ty = \tx+1$a^y+n=n*a+a

Apakah mencari sampai ncukup?

• Jika (dengan kata lain, ), maka yang membuktikan . Jadi tidak masuk akal memeriksa salah satu nilai .$\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$

• Demikian pula: jika , maka sekali lagi membuktikan .$\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}{{}^{*}}$ Kita dapat mengasumsikan karena kita tahu , angka Gryphon terkecil.$2^{n-1}>n+1$$n \geq 6$}

Python 3.8 (Pra-rilis) , 98 92 89 78 71 byte

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

Cobalah online!

Diindeks 0. Divisi integer harus digunakan di sini karena f (10000) meluap mengapung.

Menghasilkan semua angka Gryphon di mana dan , mengurutkannya, dan memilih elemen ke- .$2 \leq a \leq n+2$$2 \leq x \leq n+2$$n$

-6 byte terima kasih kepada Jonathan Allan

-3 byte terima kasih kepada ArBo. Saya hampir melakukan apa yang disarankannya sendiri, tetapi mencoba menggunakan {*(...)}yang tidak menghemat ruang

-11 byte berkat mathmandan

-7 byte terima kasih kepada ArBo

Bukti Matematika tentang Validitas

Menggunakan pengindeksan-demi bukti ini, meskipun konvensi matematika 1-diindeks.

• Biarkan menjadi nomor Gryphon ke-$G_n$$n$
• Misalkan (Nomor Gryphon dari dan )$g(a,x) = a + a^2 + ... + a^x$$a$$x$
• Biarkan menjadi himpunan semua angka Gryphon di mana dan$A_n$$2 \leq a \leq n+2$$2 \leq x \leq n+2$
• Kita tahu bahwa$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)$ untuk semua dan$a$$x$
• $g(a, x+1) < g(a+1, x+1)$ untuk semua dan$a$$x$
• Karenanya jika$G_{n+1} \neq g(a+1, x+1)$$G_n = g(a, x)$
• $g(a+1, x) < g(a+2, x)$ untuk semua dan$a$$x$
• $g(a, x+1) < g(a, x+2)$ untuk semua dan$a$$x$
• Karenanya harus berupa atau jika karena tidak ada kemungkinan lain.$G_{n+1}$$g(a+1, x)$$g(a, x+1)$$G_n = g(a, x)$
• Kita dapat menggunakan informasi ini untuk menyimpulkan bahwa jika$G_{n+1} \in A_{n+1}$$G_n \in A_n$
• Karena kita tahu bahwa , kita dapat menggunakan aturan ini untuk menginduksi untuk semua$G_0 \in A_0$$G_n \in A_n$$n$
• Karena ini dapat diterapkan dari ke , maka harus berada pada indeks dari jika dipesan dari yang terkecil hingga terbesar$G_0$$G_n$$G_n$$n$$A_n$$A_n$

J , ³⁵ 32 byte

-3 byte terima kasih kepada FrownyFrog

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

Cobalah online!

Penjelasannya sama seperti aslinya. Cukup gunakan formulir eksplisit untuk menyimpan byte menjadi menghapus beberapa @.

jawaban asli, diam-diam, dengan penjelasan: 35 byte

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

Cobalah online!

Mirip dengan pendekatan Luis Mendo, kami membuat "tabel kekuatan" (seperti tabel waktu) dengan baris atas 2 3 ... ndan kolom kiri 1 2 ... nmenghasilkan:

 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

^~/ >:membuat tabel, dan 1+i.@+&2membuat 1... nurutan, dan kami menambahkan 2 ( +&2) ke input untuk memastikan kami selalu memiliki cukup elemen untuk membuat tabel bahkan untuk 0 atau 1 input.

Setelah kita memiliki tabel di atas solusinya sepele. Kami hanya memindai jumlah baris +/\, dan kemudian menghapus baris pertama, ratakan, ambil unik, dan urutkan /:~@~.@,@}.. Akhirnya {menggunakan input asli untuk mengindeks ke dalam hasil itu, menghasilkan jawaban.

Gaia , 18 byte

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

Cobalah online!

Indeks berbasis 1.

Ini adalah jawaban yang agak menyedihkan dengan hidung panjang: )┅:Mungkin berharap itu bisa diturunkan lebih jauh.

Menyalin algoritma yang diberikan oleh jawaban Luis Mendo

R , 65 62 byte

-1 byte terima kasih kepada Giuseppe.

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

Cobalah online!

1-diindeks.

Menghasilkan matriks dari semua nilai dari bentuk , mengambil jumlah kumulatif, menghapus baris pertama (0s) dan baris kedua (entri yang sesuai dengan ), kemudian mengambil nilai yang diurutkan unik.$a^i$$x=1$

Perhatikan bahwa sort(unique(...))tidak akan berfungsi, karena uniqueakan memberikan baris unik dari matriks, dan bukan entri unik. Menggunakan unique(sort(...))karya karena sortdikonversi ke vektor.

JavaScript (ES7), 76 byte

1-diindeks.

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

Cobalah online!

JavaScript (ES7), 89 byte

1-diindeks.

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

Cobalah online!

Bahasa Wolfram (Mathematica) , 51 byte

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

Cobalah online!

1-diindeks

-8 byte dari @attinat

Arang , 36 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. 1-diindeks. Menggunakan algoritma Luis Mendo. Penjelasan:

Ｎθ

Masukan .$n$

ＦθＦθ⊞υ

Buat -by- grid nomor Gryphon dan mendorong masing-masing untuk daftar yang telah ditetapkan.$n$$n$

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

Hitung angka Gryphon menggunakan fakta bahwa .$\sum_1^x a^i = \frac{a^{x+1}-a}{a-1}$

Ｆ⊖θ≔Φυ›κ⌊υυ

Hapus angka Gryphon terendah .$n-1$

Ｉ⌊υ

Cetak angka Gryphon yang tersisa terendah.

Japt , 23 byte

Yebus sayang! Entah saya benar - benar lupa bagaimana golf atau minuman keras akhirnya mengambil korban!

Bukan port langsung solusi Jonathan tetapi sangat terinspirasi oleh pengamatannya.

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

Cobalah

05AB1E , 12 byte

L¦ãε`LmO}êIè

Diindeks 0

Cobalah online atau verifikasi item pertama$n$ .

Penjelasan:

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)