Leyland Numbers

Question

Given a natural number n, return the n-th Leyland number.

Leyland Number

Leyland numbers are positive integers k of the form

k = x^y + y^x

Where x,y are integers strictly greater than 1.

They are enumerated in ascending order.

EDIT: @DigitalTrauma suggested I include following "definition":

Imagine we throw x^y+y^x in a bag for all possible values of x and y, and avoid throwing in duplicates. Then we sort that bag. The sorted bag is our sequence.

Details

You may use 0 or 1 based indexing, whatever suits you best.

Your program must be able to output at least all Leyland numbers less than the maximum of signed 32-bit integers. (The last Leyland number below this limit is 1996813914, at index 82.)

Test cases

The first few terms are following:

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

A076980 in OEIS, except for the first entry. Note that because of that additional first entry, the indices on OEIS are shifted by one.

More can be found in the OEIS b-file

Answer 1

MATL, 16 15 13 bytes

Q:Qt!^t!+uSG)

Output is 1-based.

Try it online!

Explanation

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

Answer 2

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);}

0-indexed

-2 bytes (221 → 219) saved by replacing 1996813915 with (1L<<31) thanks to @LeakyNun.
-3 bytes (219 → 216) thanks to @LeakyNun and @Frozn with something I forgot myself..
-10 bytes (216 → 206) by changing Java 7 to 8.
-2 bytes (206 → 204) by replacing ArrayList with Vector thanks to @TAsk.
-11 bytes (204 → 193) by removing s<(1L<<31)&, since the question states "at least all Leyland numbers less than the maximum of signed 32-bit integers".
-1 byte (193 → 192) by changing Vector to Stack.

Explanation:

Try it here

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

Answer 3

Haskell, 52 bytes

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

Really inefficient. Tests each natural number for being a Leyland number, making an infinite list of those that are. Given an input, takes that index element of the list. Uses that only x,y up to 31 need to be checked for 32 bit integers.

Same length with filter:

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

Answer 4

Pyth, 17 bytes

0-indexed.

@{Sms^M_Bd^}2+2Q2

Try it online! (Please, keep it at 100.)

How it works

@{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.

Slower version

1-indexed.

e.ffqZs^M_BT^}2Z2

Try it online! (Please, keep it at 3.)

Answer 5

MATLAB, 58 bytes

1-indexed

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

unique in MATLAB flattens and sorts the matrix.

---

Thanks for help to @FryAmTheEggman and @flawr.

Answer 6

05AB1E, 20 19 bytes

0-indexed

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

Explained

ÝÌ                     # 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

Try it online

Saved 1 byte thanks to @Adnan

Answer 7

Mathematica, 60 48 40 bytes

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

Uses one-based indexing. Union is used by applying it between each row of the 2D matrix created by the Array. There, Union will flatten the 2D matrix into a list while also removing any duplicates and placing the values in sorted order.

Saved 8 bytes thanks to @LLlAMnYP.

Usage

Answer 8

PowerShell v2+, 84 73 68 bytes

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

Saved 11 bytes thanks to @Neil ... saved additional 5 bytes by reorganizing how the iex expression is evaluated.

Naïve method, we simply double-for loop from x=2..30 and y=2..x. Each loop we put x^y + y^x on the pipeline. The 30 was chosen experimentally to ensure that we covered all cases less than 2^31-1 ;-). We pipe those to Sort-Object to order them ascending. Output is zero-indexed based on the input $args[0].

Yes, there are a lot of extraneous entries generated here -- this algorithm actually generates 435 Leyland numbers -- but things above index 81 are not guaranteed to be accurate and in order (there may be some that are skipped).

Examples

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

Answer 9

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]

Needs Firefox 42 because it uses both array comprehensions and exponentiation ([for(..of..)] and **).

Answer 10

Jelly, 14 bytes

2 bytes thanks to Dennis.

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

Try it online! (Takes ~ 1s for 82 for me) (O(n^2) time)

Original 16-byte answer

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

Try it online! (Takes < 1s for me) (Constant time)

Answer 11

Bash + GNU utilities, 63

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

1-based indexing. It looks like this is pretty much the same approach as @TimmyD's answer. Instead of nested loops, bash brace expansion is used to generate arithmetic expressions that are piped to bc for evaluation.

Ideone.

Answer 12

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)[$_]}

Test:

#! /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

Explanation:

{
  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
  )[$_]
}

Answer 13

F#, 117, 104

Welp, it's shorter than my C# answer at least.

Saved 13 bytes thanks to Reed Copsey in the F# chatroom.

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

Answer 14

R, 58 54 bytes

1-indexed. Eliminated 4 bytes by using pryr::r instead of function.

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

Explanation

For all numbers from 2 to 99, and 2 to 9,

                  2:99,2:9

apply the function x^y+y^x. This generates a 98x8 matrix.

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

Sort this matrix (coercing it to a vector):

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

Remove all non-unique values:

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

Read n from stdin, and fetch the nth number from the list:

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

Answer 15

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

some example

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]

Type: List Integer

Answer 16

Ruby, 62 58 bytes

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

Try it online!

Answer 17

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

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

Try it online!

Answer 18

Haskell, 99 98 96 95 94 bytes

It is probably easily outgolfed, but that was the best I was able to come up with.

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

Answer 19

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]

0-indexed.

https://repl.it/C2SA

Answer 20

C#, 141, 127 bytes.

Oh c#, you are such a long language.

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];

This is a lambda that needs to be assigned to delegate double del(int n); to be run, as such:

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];

Answer 21

SQL (PostgreSQL 9.4), 171 bytes

Done as a prepared statement. Generate a couple of series 2 - 99, cross join them and do the equation. Densely rank the results to index them and select the first result that has the rank of the integer input.

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

Executed as follows

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

This ended up running a lot quicker than I expected

Answer 22

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])}

Ungolfed code

Try it here

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

Answer 23

J, 29 bytes

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

Uses one-based indexing. Conversion from my Mathematica solution.

The true secret here is that I have :(^+^~) on my side.

Usage

   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

Explanation

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

More seriously,

<:{[:/:~@~.@,[:(^+^~)"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

Answer 24

APL (Dyalog), 27 bytes

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

Try it online!

Answer 25

Japt -g, 15 bytes

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

Try it

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

Answer 26

J, 38 31 bytes

0-indexed.

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

Usage

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

Answer 27

Python 3, 129->116 bytes

I know there is a shorter python 3 answer, but I still wanted to contribute my solution.

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:])

This was the best way that I could to think of to handle going through all values for x and all values for y. If anyone can golf my approach it would be appreciated

Answer 28

Java, 200 197 bytes

0-indexed

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();};

Looks like java's streams can actually save bytes! Who would've thought?!

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));
    }

  }
}

Edits:

1. 200 -> 197 : removed space after long[] and removed parenthesis around n.