Dado um número natural n, retorne o n-th número de Leyland .

Número Leyland

Os números de Leyland são números inteiros positivos kda forma

k = x^y + y^x

Onde x,ysão números inteiros estritamente maiores que 1.

Eles são enumerados em ordem crescente.

EDIT: @DigitalTrauma sugeriu que eu incluísse a seguinte "definição":

Imagine que jogar x^y+y^xem um saco para todos os valores possíveis de xe y, e jogando evitar em duplicatas. Então nós separamos a sacola. A bolsa classificada é a nossa sequência.

Detalhes

Você pode usar a indexação baseada em 0 ou 1, o que melhor lhe convier.

Seu programa deve ser capaz de gerar pelo menos todos os números de Leyland menores que o máximo de números inteiros de 32 bits assinados. (O último número de Leyland abaixo desse limite é 1996813914, no índice 82.)

Casos de teste

Os primeiros termos são os seguintes:

8, 17, 32, 54, 57, 100, 145, 177, 320, 368, 512, 593, 945, 1124

A076980 no OEIS, exceto a primeira entrada. Observe que, devido a essa primeira entrada adicional, os índices no OEIS são alterados em um.

Mais informações podem ser encontradas no arquivo b do OEIS

MATL , 16 15 13 bytes

Q:Qt!^t!+uSG)

A saída é baseada em 1.

Experimente online!

Explicação

Q    % Take input n. Add 1
:Q   % Range [2 ... n+1]. This is enough to be used as x and y
t!   % Duplicate and transpose
^    % Power, element-wise with broadcast. Gives 2D, square array with x^y
     % for all pairs of x and y
t!   % Duplicate and transpose. Gives square array with y^x
+    % Add, element-wise
u    % Keep unique elements. This linearizes (flattens) the 2D array
S    % Sort
G)   % Get the n-th entry. Implicitly display

Haskell, 52 bytes

r=[2..31]
([k|k<-[0..],elem k[x^y+y^x|x<-r,y<-r]]!!)

Realmente ineficiente. Testa cada número natural como sendo um número de Leyland, fazendo uma lista infinita daqueles que são. Dada uma entrada, pega esse elemento de índice da lista. Usa que apenas x,yaté 31 precisam ser verificados para números inteiros de 32 bits.

Mesmo comprimento com filter:

r=[2..31]
(filter(`elem`[x^y+y^x|x<-r,y<-r])[0..]!!)

Java 8, 225 221 219 216 206 204 193 192 bytes

import java.util.*;n->{List<Long>t=new Stack();for(long i=1,j,s;++i<30;)for(j=1;++j<30;){s=(int)(Math.pow(i,j)+Math.pow(j,i));if(!t.contains(s))t.add(s);}Collections.sort(t);return t.get(n);}

Indexado a 0

-2 bytes (221 → 219) salvos substituindo 1996813915por (1L<<31)graças a @LeakyNun .
-3 bytes (219 → 216) graças a @LeakyNun e @Frozn com algo que me esqueci ..
-10 bytes (216 → 206) alterando Java 7 para 8.
-2 bytes (206 → 204) substituindo ArrayListpor Vectorgraças a @TAsk .
-11 bytes (204 → 193) removendo s<(1L<<31)&, uma vez que a pergunta indica " pelo menos todos os números de Leyland são inferiores ao máximo de números inteiros de 32 bits assinados ".
-1 byte (193 → 192) alterando Vectorpara Stack.

Explicação:

Experimente aqui

import java.util.*;            // Required import for Stack
n->{                           // Method with integer parameter and long return-type
  List<Long>t=new Stack();     //  Temp list
  for(long i=1,j,s;++i<30;)    //  Loop (1) from 2 to 30 (exclusive)
    for(j=1;++j<30;){          //   Inner loop (2) from 2 to 30 (exclusive)
      s=(int)(                 //    `s` is:
         Math.pow(i,j)+Math.pow(j,i)); // i^j + j^i
      if(!t.contains(s))       //     If `s` is not already part of the List
        t.add(s);              //      Add it to the List
    }                          //   End of inner loop (2)
                               //  End of loop (1) (implicit / single-line body)
  Collections.sort(t);         //  Order the List
  return t.get(n);             //  Return the item at the given index
}                              // End of method

Pitão, 17 bytes

Indexado a 0.

@{Sms^M_Bd^}2+2Q2

Experimente online! (Por favor, mantenha-o em 100.)

Como funciona

@{Sms^M_Bd^}2+2Q2
@{Sms^M_Bd^}2+2Q2Q  implicit filling. Input:Q

           }2+2Q    Yield the array [2,3,4,...,Q+2]
          ^     2   Cartesian square: yield all the
                    pairs formed by the above array.
   m     d          Map the following to all of those pairs (e.g. [2,3]):
       _B               Create [[2,3],[3,2]]
     ^M                 Reduce by exponent to each array:
                        create [8,9]
    s                   Sum:   17     (Leyland number generated)
  S                 Sort the generated numbers
 {                  Remove duplicate
@                Q  Find the Q-th element.

Versão mais lenta

1 indexado.

e.ffqZs^M_BT^}2Z2

Experimente online! (Por favor, mantenha-o em 3.)

MATLAB, 58 bytes

Indexado 1

n=input('');[A B]=ndgrid(2:n+9);k=A.^B;x=unique(k'+k);x(n)

unique no MATLAB nivela e classifica a matriz.

Obrigado pela ajuda a @FryAmTheEggman e @flawr .

05AB1E, 20 19 bytes

Indexado a 0

ÝÌ2ãvyÂ`ms`m+}){Ù¹è

Explicado

ÝÌ                     # range(2,N+2)
  2ã                   # get all pairs of numbers in the range
    v                  # for each pair
     yÂ`ms`m+          # push x^y+y^x
             }         # end loop
              ){Ù      # wrap to list, sort and remove duplicates
                 ¹è    # get Nth element of list

Experimente online

Guardado 1 byte graças a @Adnan

Mathematica, 60 48 40 bytes

(Union@@Array[#^#2+#2^#&,{#,#},2])[[#]]&

Usa indexação baseada em um. Unioné usado aplicando-o entre cada linha da matriz 2D criada pelo Array. Lá, Unionachatará a matriz 2D em uma lista, além de remover as duplicatas e colocar os valores na ordem de classificação.

Economizou 8 bytes graças a @ LLlAMnYP .

Uso

Gelatina, 14 bytes

2 bytes graças a Dennis.

R‘*€¹$+Z$FṢQị@

Experimente online! (Leva ~ 1s para 82 para mim) (O (n ^ 2) tempo)

Resposta original de 16 bytes

2r30*€¹$+Z$FṢQị@

Experimente online! (Leva <1s para mim) (tempo constante)

Utilitários Bash + GNU, 63

printf %s\\n x={2..32}\;y={2..32}\;x^y+y^x|bc|sort -nu|sed $1!d

Indexação baseada em 1. Parece que essa é praticamente a mesma abordagem que a resposta de @ TimmyD . Em vez de loops aninhados, a expansão do bash brace é usada para gerar expressões aritméticas que são canalizadas bcpara avaliação.

Ideone.

Perl 6 ,  60 58  56 bytes

{sort(keys bag [X[&({$^a**$^b+$b**$a})]] (2..$_+2)xx 2)[$_]}
{sort(keys set [X[&({$^a**$^b+$b**$a})]] (2..$_+2)xx 2)[$_]}
{sort(unique [X[&({$^a**$^b+$b**$a})]] (2..$_+2)xx 2)[$_]}
{squish(sort [X[&({$^a**$^b+$b**$a})]] (2..$_+2)xx 2)[$_]}
{squish(sort [X[&({$^a**$^b+$b**$a})]] (2..31)xx 2)[$_]}
{squish(sort [X[&({$^a**$^b+$b**$a})]] 2..31,2..31)[$_]}

Teste:

#! /usr/bin/env perl6
use v6.c;

my &Leyland = {squish(sort [X[&({$^a**$^b+$b**$a})]] 2..31,2..31)[$_]}

say ^14 .map: &Leyland;
time-this {Leyland 81};

sub time-this (&code) {
  my $start = now;
  my $value = code();
  printf "takes %.3f seconds to come up with $value\n", now - $start;
}

(8 17 32 54 57 100 145 177 320 368 512 593 945 1124)
takes 0.107 seconds to come up with 1996813914

Explicação:

{
  squish( # remove repeated values
    sort
      [X[&( # cross reduce with:
        { $^a ** $^b + $b ** $a }
      )]]
        ( 2 .. $_+2 ) # ｢Range.new(2,$_+2)｣ (inclusive range)
        xx 2          # repeat list
  )[$_]
}

F #, 117 , 104

Welp, é mais curto que minha resposta C # pelo menos.

Economizou 13 bytes graças a Reed Copsey na sala de chat F #.

let f n=[for x in 2I..32I do for y in 2I..32I->x**(int y)+y**(int x)]|>Seq.sort|>Seq.distinct|>Seq.nth n

PowerShell v2 +, 84 73 68 bytes

(2..30|%{2..($x=$_)|%{"$x*"*$_+'1+'+"$_*"*$x+1|iex}}|sort)[$args[0]]

11 bytes salvos graças a @Neil ... salvaram 5 bytes adicionais reorganizando a forma como a iexexpressão é avaliada.

Naïve, simplesmente dobramos o loop for de x=2..30e y=2..x. Cada loop que colocamos x^y + y^xno pipeline. O 30foi escolhido experimentalmente para garantir que cobrimos todos os casos com menos de 2^31-1;-). Nós os canalizamos Sort-Objectpara ordená-los a subir. A saída é indexada em zero com base na entrada $args[0].

Sim, existem muitas entradas estranhas geradas aqui - esse algoritmo realmente gera 435 números de Leyland - mas 81não é garantido que as coisas acima do índice sejam precisas e em ordem (pode haver algumas que sejam ignoradas).

Exemplos

PS C:\Tools\Scripts\golfing> .\leyland-numbers.ps1 54
14352282

PS C:\Tools\Scripts\golfing> .\leyland-numbers.ps1 33
178478

PS C:\Tools\Scripts\golfing> .\leyland-numbers.ps1 77
1073792449

R, 58 54 bytes

1 indexado. Eliminado 4 bytes usando em pryr::rvez de function.

unique(sort(outer(2:99,2:9,pryr::f(x^y+y^x))))[scan()]

Explicação

Para todos os números de 2 a 99 e 2 a 9,

                  2:99,2:9

aplicar a função x^y+y^x. Isso gera uma matriz 98x8.

            outer(2:99,2:9,pryr::f(x^y+y^x))

Classifique esta matriz (coagindo-a em um vetor):

       sort(outer(2:99,2:9,pryr::f(x^y+y^x)))

Remova todos os valores não exclusivos:

unique(sort(outer(2:99,2:9,pryr::f(x^y+y^x))))

Leia a npartir de stdin e busque o nnúmero th da lista:

unique(sort(outer(2:99,2:9,pryr::f(x^y+y^x))))[scan()]

JavaScript (Firefox 42-57), 94 bytes

n=>[for(x of Array(32).keys())for(y of Array(x+1).keys())if(y>1)x**y+y**x].sort((x,y)=>x-y)[n]

Precisa do Firefox 42 porque usa tanto a compreensão da matriz quanto a exponenciação ( [for(..of..)]e **).

Haskell, 99 98 96 95 94 bytes

Provavelmente é facilmente ultrapassado, mas foi o melhor que consegui.

import Data.List
f n|n<2=[]|n>1=sort.nub$f(n-1)++[x^n+n^x|x<-[2..n]]
g n=(f.toInteger$n+3)!!n

Python 3, 76 69 bytes

r=range(2,32);f=lambda n:sorted({x**y+y**x for x in r for y in r})[n]

Indexado a 0.

https://repl.it/C2SA

C #, 141 , 127 bytes.

Oh c #, você é uma linguagem tão longa.

n=>(from x in Enumerable.Range(2,32)from y in Enumerable.Range(2,32)select Math.Pow(x,y)+Math.Pow(y,x)).Distinct().ToList()[n];

Este é um lambda que precisa ser designado delegate double del(int n);para ser executado, como tal:

delegate double del(int n);
del f=n=>(from x in Enumerable.Range(2,32)from y in Enumerable.Range(2,32)select Math.Pow(x,y)+Math.Pow(y,x)).OrderBy(q=>q).Distinct().ToList()[n];

SQL (PostgreSQL 9.4), 171 bytes

Feito como uma declaração preparada. Gere algumas séries 2 - 99, junte-se a elas e faça a equação. Classifique densamente os resultados para indexá-los e selecione o primeiro resultado que possui a classificação da entrada inteira.

prepare l(int)as select s from(select dense_rank()over(order by s)r,s from(select x^y+y^x from generate_series(2,99)x(x),generate_series(2,99)y(y))c(s))d where r=$1limit 1

Executado da seguinte forma

execute l(82)
s
-----------------
1996813914

Isso acabou correndo muito mais rápido do que eu esperava

J, 29 bytes

<:{[:/:~@~.@,[:(^+^~)"0/~2+i.

Usa indexação baseada em um. Conversão da minha solução Mathematica .

O verdadeiro segredo aqui é que eu tenho :(^+^~) do meu lado.

Uso

   f =: <:{[:/:~@~.@,[:(^+^~)"0/~2+i.
   f 7
145
   (,.f"0) >: i. 10  NB. Extra commands for formatting
 1   8
 2  17
 3  32
 4  54
 5  57
 6 100
 7 145
 8 177
 9 320
10 368

Explicação

<:{[:/:~@~.@,[:(^+^~)"0/~2+i.  Input: n
                         2+i.  Step one
                     "0/~      Step two
              :(^+^~)          ???
<:{[:/:~@~.@,[                 Profit

Mais a sério,

<:{[:/:~@~.@,[:(^+^~)"0/~2+i.  Input: n
                           i.  Create the range [0, 1, ..., n-1]
                         2+    Add 2 to each
               (^+^~)"0        Create a dyad (2 argument function) with inputs x, y
                               and returns x^y + y^x
             [:        /~      Use that function to create a table using the previous range
   [:       ,                  Flatten the table into a list
         ~.@                   Take its distinct values only
     /:~@                      Sort it in ascending order
<:                             Decrement n (since J is zero-indexed)
  {                            Select the value at index n-1 from the list and return

Swift 3, 138 bytes

import Glibc;func l(n:Int)->Int{let r=stride(from:2.0,to:50,by:1);return Int(Set(r.flatMap{x in r.map{pow(x,$0)+pow($0,x)}}).sorted()[n])}

Código ungolfed

Experimente aqui

import Glibc
func l(n: Int) -> Int {
    // Create a Double sequence from 2 to 50 (because pow requires Double)
    let r = stride(from: 2.0, to: 50.0, by: 1.0)

    return Int(Set(r.flatMap {
        x in r.map {
            pow(x, $0) + pow($0, x)
        }
    }).sorted()[n])

Axioma 148 bytes

w(n)==(v:List INT:=[];for i in 2..31 repeat for j in i..31 repeat(a:=i^j+j^i;if a>1996813914 then break;v:=cons(a,v));v:=sort v;~index?(n,v)=>0;v.n)

algum exemplo

w(n)==
 v:List INT:=[];for i in 2..31 repeat for j in i..31 repeat
        (a:=i^j+j^i;if a>1996813914 then break;v:=cons(a,v));v:=sort v;~index?(n,v)=>0
 v.n
 (2) -> [w(i)  for i in 0..85]
    Compiling function w with type NonNegativeInteger -> Integer

    (2)
    [0, 8, 17, 32, 54, 57, 100, 145, 177, 320, 368, 512, 593, 945, 1124, 1649,
     2169, 2530, 4240, 5392, 6250, 7073, 8361, 16580, 18785, 20412, 23401,
     32993, 60049, 65792, 69632, 93312, 94932, 131361, 178478, 262468, 268705,
     397585, 423393, 524649, 533169, 1048976, 1058576, 1596520, 1647086,
     1941760, 2012174, 2097593, 4194788, 4208945, 4785713, 7861953, 8389137,
     9865625, 10609137, 14352282, 16777792, 16797952, 33554432, 33555057,
     43050817, 45136576, 48989176, 61466176, 67109540, 67137425, 129145076,
     134218457, 177264449, 244389457, 268436240, 268473872, 292475249,
     364568617, 387426321, 536871753, 774840978, 1073742724, 1073792449,
     1162268326, 1173741824, 1221074418, 1996813914, 0, 0, 0]

Tipo: Número inteiro da lista

Perl 5 , 70 + 1 (-p) = 71 bytes

for$x(2..32){$r{$x**$_+$_**$x}++for$x..32}$_=(sort{$a<=>$b}keys%r)[$_]

Experimente online!

Ruby , 62 58 bytes

->n{a,*b=c=2;c+=1while(b<<a**c+c**a;c<32||32>c=a+=1);b[n]}

Experimente online!

J, 38 31 bytes

Indexado a 0.

[{[: (# ~~:) @ /: ~ @, / [: (+ |:) [: ^ / ~ 2 + i. @>: @]
((# ~~:) /: ~, / (+ |:) ^ / ~ 2 + i.29x) {~ [

Uso

>> f =: ((#~~:)/:~,/(+|:)^/~2+i.29x){~[
>> f 81
<< 1996813914

Java, 200 197 bytes

Indexado a 0

n->{long[]t=new long[999];for(int i=1,j;++i<31;)for(j=1;j++<i;)t[i*31+j]=(long)(Math.pow(i,j)+Math.pow(j,i));return java.util.Arrays.stream(t).sorted().distinct().skip(n+1).findAny().getAsLong();};

Parece que os fluxos de java podem realmente salvar bytes! Quem teria pensado ?!

Ungolfed:

package pcg;

import java.util.function.IntToLongFunction;

public class Pcg82981 {

  public static void main(String[] args) {
    IntToLongFunction f = (n) -> {
      long[] t = new long[999];
      for (int i = 1; ++i < 31; ) {
        for (int j = 1; j++ < i; ) {
          t[i * 31 + j] = (long) (Math.pow(i, j) + Math.pow(j, i));
        }
      }
      return java.util.Arrays.stream(t)
          .sorted()
          .distinct()
          .skip(n + 1) // We don't care about 0.
          .findAny()   // equivalent to `findFirst`
          .getAsLong();
    };

    for (int i = 0; i < 82; i++) {
      System.out.println(f.applyAsLong(i));
    }

  }
}

Edições:

1. 200 -> 197: espaço removido após long[]e parênteses removidos ao redor n.

Python 3, 129-> 116 bytes

Eu sei que há uma resposta mais curta do python 3, mas eu ainda queria contribuir com minha solução.

t=[]
for k in range(100):a,b,q=k//10,k%10,a**b+b**a;f=lambda q:0if q in t else t.append(q);f(q)
print(sorted(t)[7:])

Essa era a melhor maneira que eu conseguia pensar em lidar com todos os valores de x e todos os valores de y. Se alguém puder jogar minha abordagem, seria apreciado

APL (Dyalog) , 27 bytes

{d⊃⍨⍵⊃⍋d←∪,∘.(*⍨+*)⍨1↓⍳1+⍵}

Experimente online!

Japonês -g, 15 bytes

g2ôU ïÈ**Y+pXÃü

Tente

g2ôU ïÈ**Y+pXÃü
                    :Implicit input of integer U
g                   :Index into the following array
 2ôU                :  Range [2,U+2]
     ï              :  Cartesian product with itself
      È             :  Reduce each pair [X,Y]
       **Y          :    Raise X to the power of Y
          +pX       :    Add Y raised to the power of X
             Ã      :  End reduce
              ü     :  Sort & partition by value
                    :Implicit output of first element