Pairs of integers ordered by their exponentiation

Question

Output the infinite list of pairs of integers (a, b), where both \$ a > 1 \$ and \$ b > 1 \$, ordered by the value of \$ a^b \$. When there are multiple pairs where \$ a^b \$ is equal, they should be ordered lexicographically.

For example, \$ 2^4 = 4^2 = 16 \$, but (2, 4) should come before (4, 2), because it is lexicographically earlier.

This sequence starts:

2, 2
2, 3
3, 2
2, 4
4, 2
5, 2
3, 3
2, 5
6, 2
7, 2

Here are the first 100,000 pairs: https://gist.github.com/pxeger/0974c59c38ce78a632701535181ccab4

Rules

• As with standard sequence challenges, you may choose to either:
  • Take an input \$ n \$ and output the \$ n \$th pair in the sequence
  • Take an input \$ n \$ and output the first \$ n \$ pairs
  • Output the sequence indefinitely, e.g. using a generator
• You may use \$ 0 \$- or \$ 1 \$-indexing
• You may use any standard I/O method
• Standard loopholes are forbidden
• This is code-golf, so the shortest code in bytes wins

Answer 1

Brachylog (v2), 12 bytes

⟦+₂ᵐgj∋ᵐ.^?∧

Try it online!

Function submission, a generator that generates all solutions. The TIO link uses a header + a command-line argument to print the first ten.

Explanation

⟦+₂ᵐgj∋ᵐ.^?∧
⟦              Form a range from 0 to ? inclusive, for some number ?
 +₂            Add 2 to
   ᵐ             each element of the range
     j         Make two copies of the range
    g            as two separate lists (don't concatenate them)
      ∋        Generate all ways to select one element
       ᵐ         from each list
         ^       such that the first element to the power of the second
          ?      is ?
        .  ∧   and output the selected elements

Not explicitly specified is the ordering, but ⟦ will try possible values of ? in order (which in this case are positive integers), and ᵐ will process the first element before the second (so it'll try 2⁴ before 4² because it's checking all possible exponents with base 2, then all possible exponents with base 3, etc.)

This algorithm is, of course, very inefficient. A reversed exponentiation, ~^, seems like it could be an efficient way to solve the problem, and potentially shorter too – but adding the requirement that the base and exponent are ≥2 is nontrivial when writing the program in that form, and more importantly, Brachylog seems to enter an infinite loop when trying to calculate what value the base and exponent have in that situation. So the Jelly-ish algorithm written here is probably the best available option in the current version of Brachylog.

Answer 2

JavaScript (V8), 58 bytes

for(i=3;k=++i;)for(j=1;k=k<i?k:j++<i;)j**++k-i||print(j,k)

Try it online!

Outputs indefinitely.

This code is shorter than it would be were I to remove the third for-loop and instead use logarithms.

Thanks to @Arnauld for -2 bytes and to @tsh for -2 more.

Answer 3

Vyxal, 9 bytes

ɾ›:Ẋµƒe;Ẏ

Try it Online!

ɾ›        # 2..n+1
  :Ẋ      # Cartesian product with self
    µ  ;  # Sort by...
     ƒ    # Reduce by...
      e   # Exponentiation.
        Ẏ # Get the first n.

Answer 4

Ruby, 70 60 52 bytes

2.step{|x|x.times{|y|x.times{|z|x==y**z&&p([y,z])}}}

Try it online!

How actually?

For any given x (starting from 2), check if there is a pair of values y,z in the range (0,x-1) which satisfies y^z==x

y and z will be greater than 2 because:

• If z==0, the result will be 1
• If y==0, the result will be 0 (or 1)
• If y==1, the result will be 1
• If z==1, the result will be y, which is always less than x

Answer 5

Python 3.8 (pre-release), 75 67 bytes

Thanks @pxeger for -8 bytes

i,=r=2,
while[j**k-i or print(j,k)for j in r for k in r]:i+=1;r+=i,

Try it online!

Prints indefinitely.

Port of @ophact's Javascript answer. Can probably still be golfed considerably, cuz I'm a noob at golfing in Python :P

Answer 6

Jelly, 10 bytes

‘Ḋ*þ`ZŒỤ‘ḣ

Try it online!

This works either as a full program or as a function. Takes an argument n and returns the first n pairs.

Explanation

‘Ḋ*þ`ZŒỤ‘ḣ
 Ḋ            Form an inclusive range from 2 to
‘               {n} + 1
   þ          Form an                table
  *                   exponentiation
    `           using {that range} and itself
     Z        Transpose (so that (x+1)^(y+1) is at index [x,y])
      ŒỤ      Produce a list of all coordinates (index pairs) in
                {the table}, sorted by the values of the table
        ‘     Increment {both halves of each coordinate pair}
         ḣ    {Output} the first {n} {coordinate pairs}

The basic idea is that given an input n, we calculate all possible exponentiations of numbers in the range 2 to n+1 inclusive, then return the inputs that produced the n lowest results. Jelly's tiebreak for ŒỤ happens to match the tiebreaking behaviour required by the question, but we need to transpose the table (and add 1 to the coordinates – Jelly uses 1-based coordinates but the exponentiation table conceptually uses 2-based coordinates) to make the coordinate system also match the format required by the question.

The range 2 to n+1 is sufficient because any x^y which is out of this range would have to be larger than 2² … 2ⁿ⁺¹ or than 2² … (n+1)², i.e. larger than n different elements, so it can't appear in the portion of the sequence we're outputting.

Answer 7

J, 26 23 bytes

Returns the first n pairs.

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

Try it online!

2+i. Integers from 2 to n+1.
{@;~ Table of all pairs of these integers.
(/:^/&>)&, Flatten into a list of pairs and sort by the value of the exponentiation.
{. Take the first n pairs.

Answer 8

05AB1E, 9 bytes

L>ãΣ`m}I£

Outputs the first \$n\$ pairs.

Port of @emanresuA's Vyxal answer.

Try it online.

Could alternatively be the 1-based \$n^{th}\$ value by replacing £ with è: try it online.
The infinite sequence would be 2 bytes longer: ∞εL>ãΣ`m}Nè - try it online.

Explanation:

L       # Push a list in the range [1, (implicit) input]
 >      # Increase each by 1 to make the range [2,input+1]
  ã     # Pop and push the cartesian product of itself to get all pairs
   Σ    # Sort this list of pairs by:
    `   #  Pop and push both values separated to the stack
     m  #  Exponentiation
   }I£  # After the sort-by: leave the first input amount of pairs
        # (which is output implicitly as result)

Answer 9

Python 2, 75 76 bytes

Outputs the first n pairs. (A previous version of this answer was one byte shorter by returning just the nth pair, but it raised an error for n <= 2.)

Not as short as @Aidan Chow's Python answer, but I wanted to see how well sorted would do. Using Python 2's lambda argument destructuring is a bit shorter than lambda p:p[0]**p[1] in Python 3.

lambda n:sorted([(i/n+2,i%n+2)for i in range(n*n)],key=lambda(i,j):i**j)[:n]

Try it online!

Answer 10

Haskell, 45 bytes

f=[(y,z)|x<-[2..],y<-[2..x],z<-[2..x],y^z==x]

Try it online!

f is the infinite sequence.

Inspired by @G B answer

Answer 11

Jelly, 7 bytes

p`‘*/Þḣ

Try it online!

Port of my Vyxal. -1 thanks to ovs.

p`       Cartesian product with (implicit) range from 1 to self
  ‘      Increment anything
     Þ   Sort by...
    /    Reduce by...
   *     Exponentiation
      ḣ  Get first n.

Answer 12

R, 57 55 50 46 bytes

\(n)cbind(a<-n:1+1,b<-a%x%!!a)[order(a^b)[n],]

Attempt This Online!

Returns the \$n^\text{th}\$ value.

-2 bytes thanks to pajonk, then -4 more bytes thanks to pajonk. -1 byte thanks to Dominic van Essen.

Answer 13

APL+WIN, 27 bytes

Prompts for desired term i.

(v[⍋*/¨v←,n∘.,n←1+⍳i])[i←⎕]

Try it online! thanks to Dyalog APL Classic

Answer 14

Java 8, 91 bytes

n->{for(int t=4,i;;t++)for(i=1;i++<t*t;)if(Math.pow(i/t,i%t)==t&&--n<0)return i/t+","+i%t;}

Outputs the 0-based \$n^{th}\$ value.

Try it online.

Outputting the infinite sequence is 6 bytes longer:

n->{for(int t=4,i;;t++)for(i=1;i++<t*t;)if(Math.pow(i/t,i%t)==t)System.out.println(i/t+","+i%t);}

Try it online

Explanation:

n->{                   // Method with integer parameter and String return-type
  for(int t=4,         //  Target-integer, starting at 4
          i;           //  Output integer, uninitialized
      ;                //  Loop indefinitely:
       t++)            //    Increase `t` by 1 after every iteration
    for(i=1;i++<t*t;)  //   Inner loop `i` in the range (1,t*t):
      if(Math.pow(i/t, //    If `i` integer-divided by `t`
                  i%t) //    to the power `i` modulo-`t`
          ==t&&        //    Is equal to `t`:
         --n           //     First decrease the input by 1
            <0)        //     And if it's now negative:
        return i/t+","+i%t;}
                       //      Return the divmod of `i,t` as result

Answer 15

Julia 1.0, 49 bytes

!n=sort([a^b=>a=>b for a=2:n+1,b=2:n+1][:])[n][2]

Try it online!

output is the n-th pair in the sequence (1-indexed). For n>14, a BigInt is expected to avoid overflow

Answer 16

Retina, 98 bytes

.+
*
L$`_
$=$.($`__
%L$`_(?=_*(.+))
:$1,$.($`__
%~`:(.+),(.+)
^¶$$.($2*$($1$*
N`.+
"$+"+0`.+:

A`:

Try it online! Outputs the first n terms. Explanation: Port of my Charcoal answer inspired by @ais523's answer.

.+
*

Convert n to unary.

L$`_
$=$.($`__

Create the numbers from 2 to n+1 in decimal, each prefixed with n in unary.

%L$`_(?=_*(.+))
:$1,$.($`__

Create the Cartesian product of the range 2 to n+1 with itself.

%~`:(.+),(.+)
^¶$$.($2*$($1$*

Precede each product with its exponentiation, computed by constructing a repeated multiplication and evaluating it.

N`.+

Sort the exponentiations, resolving ties stably i.e. keeping the lowest base first.

"$+"+

Loop n times...

0`.+:

... delete one exponentiation.

A`:

Keep only the lines where the exponentiation was removed i.e. the first n lines.

Answer 17

Charcoal, 41 bytes

ＮθＦθＦθ⊞υ⟦Ｘ⁺²ι⁺²κ⁺²ι⁺²κ⟧≔⟦⟧ηＦθ⊞η⌊⁻υηＩＥη✂ι¹

Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation: Inspired by @ais523's answer.

Ｎθ

Input n.

ＦθＦθ⊞υ⟦Ｘ⁺²ι⁺²κ⁺²ι⁺²κ⟧

Generate the Cartesian product of [2..n+2) with itself, plus include the result of the exponentiation as the first term.

≔⟦⟧ηＦθ⊞η⌊⁻υη

Get the n lowest terms from that list, which takes values in ascending order of exponentiation resolving ties by taking the base in ascending order.

ＩＥη✂ι¹

Output the terms but exclude the exponentiations.

35 bytes using the newer version of Charcoal on ATO:

ＮθＦθ⊞υ⌊⁻ΣＥθＥθ⟦Ｘ⁺²κ⁺²μ⁺²κ⁺²μ⟧υＩＥυ✂ι¹

Attempt This Online! Link is to verbose version of code.