Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
    
They are enumerated in ascending order I'm not really sure what this means. Could you provide a list of x and y? – Dr Green Eggs and Iron Man yesterday
    
@DrGreenEggsandIronMan That means, 8 is before 17, not the other way round. – Leaky Nun yesterday
1  
@DrGreenEggsandIronMan Imagine we throw x^y+y^x in a bag for all possible values of x and y, and avoid thrwoing in duplicates. Then we sort that bag. The sorted bag is our sequence. – flawr yesterday
6  
Very large bag you have there – Luis Mendo yesterday
2  
@LuisMendo Ask @​HenriLéonLebesgue and he is going to tell you that this bag is basically nothing. – flawr yesterday

21 Answers 21

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
share|improve this answer
    
In Matlab unique sorts the elements. Doesn't it in MATL, too? – pajonk yesterday
1  
@pajonk MATL uses the 'stable' flag for unique by default as that is the more typical usage. – Suever yesterday
    
@Suever Ok, thanks for clarifying. – pajonk yesterday
1  
I feel like we use the t!^ (where ^ can be replaced by +, -, or any number of operators) motif a lot. What if we made & mean 1 input for some of those where for a vector it has that behavior? – Suever yesterday
    
@Suever That's a great idea! I've done some research with your script; see the chat – Luis Mendo yesterday

Java 7, 225 221 219 bytes

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

2 bytes saved by replacing 1996813915 with (1L<<31) thanks to @LeakyNun
(and 4 more thanks to @LeakyNun and @Frozn with something I forgot myself..)

Ungolfed & test code:

Try it here

import java.util.*;

public class Main{
  static long c(int n){
    List<Long> t = new ArrayList();
    for(int i = 2, j; ++i < 30; ){
      for(j = 2; ++j < 30; ){
        long s = (long) (Math.pow(i, j) + Math.pow(j, i));
        if (s < (1L<<31) & !t.contains(s)){
          t.add(s);
        }
      }
    }
    Collections.sort(t);
    return t.get(n);
  }

  public static void main(String[] a) {
    // Test code for altering output (displaying one, skipping one, etc.)
    for (int i = 0; i < 14; i += 2) {
      System.out.println(c(i));
    }
  }
}

Output:

8
32
57
145
320
512
945
share|improve this answer
2  
10/10 for using java – Leaky Nun yesterday
    
Since you only need to support up to 2^31-1 (i.e., signed int), can't you swap out a bunch of the long casts? – TimmyD yesterday
1  
Quick golfs: import java.util.*;long c(int n){List<Long>t=new ArrayList();for(int i=2,j;i<25;i++)for(j=2;j<25;j++){long s=(long)(Math.pow(i,j)+Math.pow(j,i));if(s<(1L<<31)&!t.contains(s))t.add(s);}Col‌​lections.sort(t);return t.get(n);} – Leaky Nun yesterday
1  
The for loop variable declaration. – Leaky Nun yesterday
1  
How about for (int i = 1, j; ++i < 30;) and for (j = 1; ++j < 30;) – Frozn 20 hours ago

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

share|improve this answer
    
Would it help to create an array of powers [[4,8,...][9,27,...]] and add it to its transpose? – Neil yesterday
    
@Neil I don't think so. It would be helpful in Jelly, but not in Pyth. Pyth does not automatically vectorize. – Leaky Nun yesterday
    
Also helps in MATL, it seems. – Neil yesterday
    
Why do you keep the slower version? – Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ 17 hours ago

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..]!!)
share|improve this answer
    
In hindsight such an obvious solution, I like it a lot! – flawr yesterday

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.

share|improve this answer

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

share|improve this answer
    
Very nice! One tip, ÝÌ is short for >L>. – Adnan yesterday
    
@Adnan: Thanks! I can't belive I didn't think of that :P – Emigna yesterday

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.

share|improve this answer

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
share|improve this answer

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)

share|improve this answer
    
R‘*€¹$+Z$FṢQị@ is faster, shorter and has no artificial upper bound. – Dennis yesterday
    
@Dennis and beats my answer :-P – Luis Mendo yesterday
    
@Dennis I don't get it. How come it is faster than the second one. – Leaky Nun yesterday
    
It isn't faster than the second one. The execution time is too short to get an accurate measurement. – Dennis yesterday
    
Now 13 bytes :-P – Luis Mendo yesterday

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
share|improve this answer
    
import Data.List f n|w<-[2..toEnum$n+3]=(sort$nub[x^y+y^x|x<-w,y<-w])!!n Do you know why toInteger/toEnum is needed? – Damien yesterday
    
Wow, this is crazy=) Feel free to add it as your own answer, as it is qutie different from mine! If we omit toInteger in my solution we'll have an overflow using int, because we iterate way higher (to n+3 instead of n) when working with the list. Otherwise we'd need to hardcode the first four terms or so. What exactly does toEnum do in your solution? – flawr yesterday
    
OK, that's because of (!!) operator which binds n to an Int. Since n is supposed to be under 82, w can be replaced by [2..99] for example and f=(sort(nub[x^y+y^x|x<-[2..99],y<-[2..x]])!!) . toEnum converts an Int to an Enum, and Integer is an instance of Enum class so toEnum here converts n+3 to an Integer. – Damien yesterday

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

share|improve this answer
2  
It’s okay to just write your answer as r=range(2,32) lambda n:sorted(…)[n] – Lynn yesterday

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
  )[$_]
}
share|improve this answer
    
Can't you remove the spaces between sort [ and ] 2..31? – Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ 17 hours ago
    
@EʀɪᴋᴛʜᴇGᴏʟғᴇʀ That would turn it from a subroutine call sort([... to an array access of a term sort[.... A similar thing happens with the other space. – Brad Gilbert b2gills 14 hours ago

JavaScript (Firefox 42+), 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 **).

share|improve this answer
    
Shouldn't you just mark it as ES7? – mbomb007 yesterday
    
@mbomb007 I don't think [for...of] made it to ES7. – Neil yesterday
    
It's part of ES6 – mbomb007 yesterday
    
No, that's for(..of..), not [for(..of..)]. – Neil yesterday
    
Ah, okay. (Non-standard. Do not use.) lol – mbomb007 yesterday

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];
share|improve this answer
1  
Still shorter than Java. – flawr yesterday
    
@flawr Wooooooo? – Morgan Thrapp yesterday
    
I know nothing about C#, but couldn't you save Enumerable.Range( to a variable/function/iterator/whatever with a shorter name for reuisng? – flawr yesterday
    
I could, but then I would need to include a class and type defs, which ends up costing me a ton. – Morgan Thrapp yesterday

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
share|improve this answer

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

share|improve this answer

Mathematica, 60 48 bytes

(Union@@Array[#^#2+#2^#&,{#+1,#+1},{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.

Usage

Example

share|improve this answer

J, 38 31 bytes

0-indexed.

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

Usage

>> f =: ((#~~:)/:~,/(+|:)^/~2+i.29x){~[
>> f 81
<< 1996813914
share|improve this answer
    
You can get 29 bytes using {[:/:~@~.@,@(+|:)[:^/~2+i.@>:. – miles yesterday

Python 3, 129 bytes

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

m=n=10;t=[]
for k in range(n*m):a,b=(-~k)//n,(-~k)%m;q=a**b+b**a;f=lambda q: 0 if 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

share|improve this answer
    
Make t a set instead of a list, and replace the last for statements with a plain t.add(q). – Cristian Ciupitu 6 hours ago

Swift 3, 146 bytes

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

Ungolfed code

Try it here

import Glibc
func l(n: Int) -> Int {
    let r = stride(from:2.0, to: 15.0, by: 1.0)
    let v = Set(r.flatMap {x in r.map { Int(pow(x, $0) + pow($0, x)) } }).sorted()
    return v[n]
}
share|improve this answer
1  
Welcome to Programming Puzzles and Code Golf! Nice first answer, but it'd be better if you could explain what's going on. – DerpfacePython 22 hours ago

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.