Pewnego dnia wymyśliłem serię liczb i postanowiłem sprawdzić, jaki to numer OEIS. Ku mojemu zaskoczeniu, sekwencja nie pojawiła się w bazie danych OEIS, więc postanowiłem nazwać tę sekwencję po sobie (zauważ, że ktoś, kto jest o wiele mądrzejszy ode mnie, prawdopodobnie już to wymyślił i jeśli ktoś znajdzie faktyczna nazwa tej sekwencji, proszę o komentarz, a ja zmienię tytuł pytania). Ponieważ nigdzie nie mogłem znaleźć sekwencji, postanowiłem ją nazwać po sobie, stąd „Gryphon Numbers”. EDYCJA: Dzięki @Surb za zwrócenie mojej uwagi na fakt, że ta sekwencja jest równa sekwencji OEIS A053696 - 1.

Numer gryfa szereg postaci $a+a^2+...+a^x$ , gdzie zarówno $a$ jak i $x$ są liczbami całkowitymi większymi lub równymi dwa, a sekwencja Gryphona jest zbiorem wszystkich liczb Gryphona w porządku rosnącym. Jeśli istnieje wiele sposobów tworzenia liczby Gryfa (pierwszy przykład to $30$ , czyli $2+2^2+2^3+2^4$ i $5+5^2$ ), liczba jest liczona tylko raz w sekwencji. Pierwsze kilka liczb Gryfa to:$6, 12, 14, 20, 30, 39, 42, 56, 62, 72$ .

Twoje zadanie:

Napisać program lub funkcji, które otrzymuje się całkowitą na wejściu i na wyjściu z th liczby Gryphon. $n$$n$

Wkład:

Liczba całkowita od 0 do 10000 (włącznie). Możesz traktować sekwencję jako indeksowaną 0 lub 1 indeksowaną, w zależności od tego, co wolisz. Proszę podać, jakiego systemu indeksowania używasz w swojej odpowiedzi, aby uniknąć nieporozumień.

Wydajność:

Numer Gryphona odpowiadający wejściu.

Przypadki testowe:

Należy pamiętać, że przy założeniu, że sekwencja ma indeks 0. Jeśli twój program zakłada sekwencję 1-indeksową, nie zapomnij zwiększyć wszystkich liczb wejściowych.

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

Punktacja:

To jest golf golfowy , więc wygrywa najniższy wynik w bajtach.

Galaretka , 9 bajtów

bṖ’ḅi-µ#Ṫ

Pełny program, który odczytuje liczbę całkowitą (indeksowaną 1) ze STDIN i wypisuje wynik.

Wypróbuj online!

W jaki sposób?

Liczba Gryphona to liczba, która jest wyrażana w bazie mniej niż sama, tak że wszystkie cyfry są jedynymi, z wyjątkiem najmniej znaczących, czyli zerowych. Na przykład:

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

Ten program pobiera n, a następnie uruchamia o v=0i testuje tę właściwość i zwiększa vją, aż znajdzie ntakie liczby, a następnie wyprowadza ostateczną.

Aby przetestować bnumer bazowy , odejmuje jeden od każdej cyfry, konwertuje z bazy v, a następnie sprawdza, czy wynikiem jest $-1$ . (Uwaga, że bjest mniejsza niż 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 bajtów

:Qtt!^Ys+uSG)

Na podstawie 1.

Wypróbuj online!

Wyjaśnienie

Rozważ dane wejściowe n = 3jako przykład.

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

Macierz uzyskana w kroku (*) zawiera prawdopodobnie powtarzające się liczby Gryphona. W szczególności zawiera nwyraźne liczby Gryphon w pierwszym rzędzie. Niekoniecznie są to nnajmniejsze liczby Gryfa. Jednak dolny lewy wpis 2+2^+···+2^n przekracza górny prawy wpis n+n^2, a zatem wszystkie liczby w ostatnim rzędzie przekraczają liczby w pierwszym rzędzie. Oznacza to, że rozszerzenie macierzy w prawo lub w dół nie przyczyni się do uzyskania liczby Gryphonów niższej niż najniższe nliczby w macierzy. Dlatego macierz ma zagwarantowane, że zawiera nnajmniejsze liczby Gryphona. W rezultacie rozwiązaniem jest jego nnajniższy unikalny element.

Haskell , 53 bajty

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

Wypróbuj online!

$\newcommand{\ta}{{a}}\newcommand{\ti}{{i}}\newcommand{\tx}{{x}}\newcommand{\tn}{{n}}\newcommand{\ty}{{y}}$Liczba $\tn$ to Gryphon, jeśli istnieją liczby całkowite $\ta \geq 2$ i $\tx \geq 2$ takie, że $\tn=\sum_{i=1}^\tx \ta^i$ .

Generujemy nieskończoną listę wszystkich $\tn \geq 6$ tak że wyszukiwanie metodą brutalnej siły pokazuje, że tak jest.

Odpowiedzią jest funkcja indeksu (indeksowana od zera) na tę listę, oznaczona w Haskell jako (list!!).

Dlaczego jest a^y+n==n*a+apoprawny?

Ze wzoru na sumowanie postępu geometrycznego :

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

Czy szukanie jest nwystarczające?

• Jeśli $\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$

• Podobnie: Jeśli $\ty > \tn$ , a następnie Y +

  $$\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 (wersja wstępna) , 98 92 89 78 71 bajtów

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

Wypróbuj online!

0-indeksowane. Należy tu zastosować dzielenie liczb całkowitych, ponieważ f (10000) przelewa się.

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

-6 bajtów dzięki Jonathanowi Allanowi

-3 bajty dzięki ArBo. Prawie zrobiłem, jak sam sugerował, ale próbowałem użyć, {*(...)}co i tak nie oszczędzało miejsca

-11 bajtów dzięki Mathmandan

-7 bajtów dzięki ArBo

Matematyczny dowód ważności

Wykorzystanie indeksowania 0 dla tego dowodu, mimo że konwencja matematyczna ma indeks 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$
• W związku z tym $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 bajtów

-3 bajty dzięki FrownyFrog

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

Wypróbuj online!

Wyjaśnienie jest takie samo jak oryginału. Wystarczy użyć jawnej formy, aby zaoszczędzić bajty, usuwając wielokrotność @.

oryginalna odpowiedź, milcząca, z wyjaśnieniem: 35 bajtów

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

Wypróbuj online!

Podobnie do podejścia Luisa Mendo, tworzymy „tabelę mocy” (jak tabelę czasu) z górnym rzędem 2 3 ... ni lewą kolumną, w 1 2 ... nwyniku czego:

 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

^~/ >:tworzy tabelę i 1+i.@+&2tworzy 1... nsekwencje, i dodajemy 2 ( +&2) do danych wejściowych, aby upewnić się, że zawsze mamy wystarczającą liczbę elementów, aby utworzyć tabelę nawet dla danych wejściowych 0 lub 1.

Po powyższej tabeli rozwiązanie jest banalne. Po prostu skanujemy sumowanie wierszy +/\, a następnie usuwamy pierwszy wiersz, spłaszczamy, wybieramy unikatowe i sortujemy /:~@~.@,@}.. Na koniec {wykorzystuje oryginalne dane wejściowe do indeksowania tego wyniku, tworząc odpowiedź.

Gaia , 18 bajtów

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

Wypróbuj online!

Indeks oparty na 1.

To dość smutna odpowiedź z długim nosem: )┅:prawdopodobnie żałuje, że nie można dalej grać w golfa.

Kopiuje algorytm podany w odpowiedzi Luisa Mendo

R , 65 62 bajtów

-1 bajt dzięki Giuseppe.

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

Wypróbuj online!

1-indeksowany.

Generuje macierz wszystkich wartości postaci ı bierze skumulowaną sumę, usuwa się z pierwszego rzędu (0s) oraz drugi rząd (pozycje odpowiadające X$a^i$$x=1$

Zauważ, że sort(unique(...))to nie zadziałałoby, ponieważ uniquedałoby unikalne wiersze macierzy, a nie unikatowe wpisy. Używanie unique(sort(...))działa, ponieważ sortkonwertuje na wektor.

JavaScript (ES7), 76 bajtów

1-indeksowany.

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

Wypróbuj online!

JavaScript (ES7), 89 bajtów

1-indeksowany.

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

Wypróbuj online!

Wolfram Language (Mathematica) , 51 bajtów

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

Wypróbuj online!

1-indeksowany

-8 bajtów od @attinat

Węgiel drzewny , 36 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. 1-indeksowany. Wykorzystuje algorytm Luisa Mendo. Wyjaśnienie:

Ｎθ

$n$

ＦθＦθ⊞υ

$n$$n$

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

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

Ｆ⊖θ≔Φυ›κ⌊υυ

$n-1$

Ｉ⌊υ

Wydrukuj najniższy pozostały numer Gryphona.

Japt , 23 bajty

Drogi Jebusie! Albo ja naprawdę zapomniałem, jak grać w golfa, albo alkohol w końcu zbiera żniwo!

Nie jest to bezpośredni przykład rozwiązania Jonathana, ale bardzo zainspirowany jego obserwacją.

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

Spróbuj

05AB1E , 12 bajtów

L¦ãε`LmO}êIè

0-indeksowane

$n$

Wyjaśnienie:

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)