22
\$\begingroup\$

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 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 , so the shortest code in bytes wins
\$\endgroup\$

17 Answers 17

6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Removing the third for does save bytes: for(i=3;k=++i;)for(j=1;k=k<i?k:j++<i;)j**++k-i||print(j,k) \$\endgroup\$
    – tsh
    Mar 11 at 8:38
5
\$\begingroup\$

Vyxal, 9 bytes

ɾ›:Ẋµƒe;Ẏ

Try it Online!

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

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

\$\endgroup\$
7
  • \$\begingroup\$ A series of improvements: the list comprehension can be the condition of the while loop, since it's always truthy. The remaining statements can be squished onto one line after the :. It's also shorter to extend a list instead of building a range every time. \$\endgroup\$
    – pxeger
    Mar 11 at 8:12
  • \$\begingroup\$ You aren't a noob in Python if you can golf one of my answers, which you did ;) \$\endgroup\$
    – ophact
    Mar 11 at 8:13
  • \$\begingroup\$ @pxeger ok yep thanks, putting the list comprehension as the condition is pretty smart \$\endgroup\$
    – Aiden Chow
    Mar 11 at 8:14
  • \$\begingroup\$ @pxeger also what is i,=r=2 doing??? I can't comprehend what is going on there. \$\endgroup\$
    – Aiden Chow
    Mar 11 at 8:16
  • \$\begingroup\$ i,=r=2, is roughly equivalent to r = (2,); i = r[0] \$\endgroup\$
    – pxeger
    Mar 11 at 8:18
4
\$\begingroup\$

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 xy which is out of this range would have to be larger than 22 … 2n+1 or than 22 … (n+1)2, i.e. larger than n different elements, so it can't appear in the portion of the sequence we're outputting.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
  • 2
    \$\begingroup\$ p+1*/Þḣ (or p`‘*/Þḣ) works for 7. \$\endgroup\$
    – ovs
    Mar 11 at 16:53
  • \$\begingroup\$ @ovs Oh, forgot about automatic range conversion :) \$\endgroup\$
    – emanresu A
    Mar 11 at 19:50
2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ -2 bytes \$\endgroup\$
    – pajonk
    Mar 11 at 16:10
  • 1
    \$\begingroup\$ Another -4 bytes as order is (I think) stable. \$\endgroup\$
    – pajonk
    Mar 11 at 16:19
  • 1
    \$\begingroup\$ @pajonk aahh that's great! I was coming from an outer(a,a,"^") approach (as you might have been able to tell), so I needed the extra argument to order, since 4,2 comes before 2,4. Default sort method for order is stable, so that works, and there's even another byte saving. \$\endgroup\$
    – Giuseppe
    Mar 11 at 18:07
  • 1
    \$\begingroup\$ 49 bytes I think...? \$\endgroup\$ Mar 13 at 13:29
  • 1
    \$\begingroup\$ @DominicvanEssen Of course. And A%x%!!1:n is a byte shorter than rep(A,e=n) for numeric vectors A. \$\endgroup\$
    – Giuseppe
    Mar 14 at 14:41
1
\$\begingroup\$

APL+WIN, 27 bytes

Prompts for desired term i.

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

Try it online! thanks to Dyalog APL Classic

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 41 bytes

NθFθFθ⊞υ⟦X⁺²ι⁺²κ⁺²ι⁺²κ⟧≔⟦⟧ηFθ⊞η⌊⁻υηIEη✂ι¹

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

Nθ

Input n.

FθFθ⊞υ⟦X⁺²ι⁺²κ⁺²ι⁺²κ⟧

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

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

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.

IEη✂ι¹

Output the terms but exclude the exponentiations.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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