17
\$\begingroup\$

Introduction

This question is inspired by this great question.

Challenge

Given a number \$N>0\$, output the largest integer \$a^b\$ that is smaller or equal to \$N\$, and the smallest integer \$c^d\$ that is greater or equal to \$N\$, where \$b>1\$ and \$d>1\$.

Output should be a list of two integers, the first being smaller or equal to \$N\$, the second being greater or equal to \$N\$, and both being a perfect power. The two outputs can be in any order.

If \$N\$ is a perfect power already, the output should be the list [N, N].

This is , so the shortest code (as measured in bytes) wins.

Example Input and Output

Input:

30

Output:

[27, 32]

Explanation: \$27=3^3\$ is the largest perfect power less than or equal to \$30\$ and \$32=2^5\$ is the smallest perfect power greater or equal to \$30\$. Note that exponents b and d are not the same in this case.

Test cases

2 -> [1, 4]
30 -> [27, 32]
50 -> [49, 64]
100 -> [100, 100]. 100 is already a perfect power.
126 -> [125, 128]
200 -> [196, 216]
500 -> [484, 512]
5000 -> [4913, 5041]
39485 -> [39304, 39601]
823473 -> [822649, 823543]
23890748 -> [23887872, 23892544]
Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ @noodle man thanks for the edit. I was trying to find how to use Latex and simple $ didn't work. Now I know :) \$\endgroup\$
    – Dmitry Kamenetsky
    Commented Oct 29, 2023 at 4:07
  • \$\begingroup\$ suggested test-case 2 -> [1,4], some approaches do not work for small numbers \$\endgroup\$
    – bsoelch
    Commented Oct 29, 2023 at 8:29
  • \$\begingroup\$ As long as it’s consistent, is it permissible to output the results in reverse order (e.g. 2 -> [4,1])? \$\endgroup\$
    – Nick Kennedy
    Commented Oct 29, 2023 at 9:12
  • \$\begingroup\$ @bsoelch added that case \$\endgroup\$
    – Dmitry Kamenetsky
    Commented Oct 29, 2023 at 9:18
  • \$\begingroup\$ @NickKennedy I will allow reverse order. Updated the statement \$\endgroup\$
    – Dmitry Kamenetsky
    Commented Oct 29, 2023 at 9:19

14 Answers 14

Reset to default
7
\$\begingroup\$

R, 62 60 bytes

function(n,y=outer(1:n,2:n,"^"))c(max(y[y<=n]),min(y[y>=n]))

Try it online!

Brute force approach: generate all powers of 1..n raised to 2..n and find and return least upper bound and greatest lower bound.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Jelly, 14 bytes

ÆEŻg/’
ÇƇṪ;Ç1#

A monadic Link that accepts a positive integer and yields the sandwich of perfect powers.

Try it online! (Excluded the three largest test cases since the implementation is inefficient.)

How?

ÆEŻg/’ - Link 1, perfect power?: positive integer, X
ÆE     - prime factor exponents of X (e.g.: 1 -> [], 8 -> [3], 63 -> [0,2,0,1])
  Ż    - prefix a zero (to allow the following reduction when X=1)
    /  - reduce by:
   g   -   greatest common divisor (Note that 0 GCD N = N GGD 0 = N)
          - non-perfect powers will result in 1
            perfect powers will result in an integer greater than 1, except X=1 -> 0
     ’ - decrement -> non-zero (truthy) iff X is a perfect power

ÇƇṪ;Ç1# - Main Link: positive integer, N
 Ƈ      - filter {[1..N]} keeping those for which:
Ç       -   call Link 1
  Ṫ     - tail
           -> perfect power less than or equal to N
     1# - starting with k=N find the first integer k for which:
    Ç   -   call Link 1
           -> perfect power greater than or equal to N
   ;    - concatenate

How?

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nice use of a similar technique to the one you had in your answer to the Achilles question! \$\endgroup\$
    – Nick Kennedy
    Commented Oct 29, 2023 at 23:30
5
\$\begingroup\$

Desmos, 55 bytes

f(n)=[floor(L)^I.max,ceil(L)^I.min]
L=n^{1/I}
I=[2...n]

Try It On Desmos!

Try It On Desmos! - Prettified

Eh, pretty sure this can be golfed.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 78 bytes

n=>eval("for(M=[m=1,x=p=2];(x*=p)>n|x<m?0:m=x,x<n?1:x>M?(x=++p)<n:M=x;)[m,M]")

Try it online!

JavaScript (ES6), 79 bytes

A faster version without eval(), also easier to comment.

n=>{for(M=[m=1,x=p=2];(x*=p)>n|x<m?0:m=x,x<n?1:x>M?(x=++p)<n:M=x;);return[m,M]}

Try it online!

n => {            // n = input
  for(            // loop:
    M = [         //   M = high bound
      m = 1,      //   m = low bound
      x =         //   x = current result
      p = 2       //   p = current multiplier
    ];            //
    (x *= p)      //   multiply x by p
    > n |         //   if x is greater than n
    x < m ?       //   or less than m:
      0           //     do nothing
    :             //   else:
      m = x,      //     set m to x
    x < n ?       //   if x is less than n:
      1           //     continue
    :             //   else:
      x > M ?     //     if x is greater than M:
        (x = ++p) //       increment p and set x to p
        < n       //       continue if x < n
      :           //     else:
        M = x;    //       set M to x and continue
  );              // end of loop
  return [m, M]   // return the final bounds
}                 //
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python, 85 bytes

This solution is designed to solve all test-cases in less than 1 second, for a slightly shorter but slower approach see corvus_192's solution

-21 bytes thanks to xnor's suggestion on corvus_192's solution

lambda n:[i*max(i*int(n**(1/p)//i*i)**p for p in range(2,len(bin(n))))for i in(1,-1)]

Attempt This Online!

Goes through floor/ceil of p-th root to power of p for all possible powers p and picks the highest lower and lowest upper bound

Python, 115 bytes

solves all test cases in less than a minute

lambda n:[next(q for q in x for b in r(2,len(bin(q)))if q==round(q**(1/b))**b)for x in[r(n,0,-1),r(n,3*n)]]
r=range

Attempt This Online!

Explanation

uses a less golfed version of the same approach

# check if a given number is a perfect power
p=lambda q:any(q==round(q**(1/b))**b for b in r(2,len(bin(q))))
# brute-force: check for all exponents b if q is a power of b
# due to rounding errors: q**(1/b)%1==0 and q==int(q**(1/b))**b) give the wrong result for the last two test-cases
# checking all numbers takes to much time 
# only check up to log2(q)+2 with is larger than the largest possible power p for which 2**p <= q

# find the power sandwich
lambda n:[next(filter(p,x))for x in[r(n,0,-1),r(n,3*n)]]
# find the first number x less/greater than or equal to n that satisfies p(x)
# use 3*n as upper bound for the next perfect power: if n is not a square number then the next square number is less than 3*n 
# (clear for n <9=3², if m=k*k for k >= 3 then (k+1)²=k²+2*k+1 <= k²+3*k <= 2*k² <= 2*m < 3*m)
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can iterate range(2,n+1), which is very slow, but technically correct. Need the extra int() to prevent float overflow problems. Results in 105 bytes lambda n:[R:=range(2,n+1),max(int(n**(1/p))**p for p in R),min(int(abs(n**(1/p)//-1))**p for p in R)][1:] \$\endgroup\$
    – corvus_192
    Commented Oct 29, 2023 at 21:00
3
\$\begingroup\$

Jelly, 16 bytes

2r⁸*þFfȯ_İ¥Þɗ⁸.ị

Try it online!

A monadic link taking an integer argument and returning a list of two integers. Will time out for large n, since internally a table of all powers of \$a^b\$ where \$a\$ is from 1 to n and \$b\$ is from 2 to n.

Explanation

2r                | Range from 2 to the input
  ⁸*þ             | Table of powers from 1 to the input raised to the power of from 2 to the input
     F            | Flatten
            ɗ⁸    | Following as a dyad, using the input as the right argument and the power table as the left:
      f           | - Filter (keep the input if present in the power table)
       ȯ  ¥       | - Or the following as a dyad
        _         |   - Subtract the input
         İ        |   - Invert
              .ị  | Take the last (power above or equal) and first (power below or equal) elements of this list
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 120 bytes

.+
$*
((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$
$&¶$&
O`
+`¶(?!((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$)
¶1
%`1

Try it online! Link includes faster test cases. Explanation:

.+
$*

Convert to unary.

((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$
$&¶$&

Find the largest perfect power that does not exceed N. This is based on my answer to What's next, Achilles? but also allowing N=1, which that question didn't have to handle.

O`

Sort the numbers back into order. (This is shorter than trying to get the above stage to output the numbers in ascending order.)

¶(?!((1+)((\2(1+))(?=(\4*)\2*$)\4*(?=\5$\6))+)?1$)
¶1

If N is not a perfect power then increment it.

+`

Repeat until a perfect power is reached.

%`1

Convert to decimal.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python, 77 bytes

lambda n:[i*max(i*int(n**(1/p)//i*i)**p for p in range(2,n+2))for i in(-1,1)]

Attempt This Online!

-16 bytes thanks to xnor and bsoelch

Previous version, 93 bytes

lambda n:[(g:=lambda f,i:f(int(abs(n**(1/p)//i))**p for p in range(2,n+1)))(max,1),g(min,-1)]

The core algorithm is from bsoelch: https://codegolf.stackexchange.com/a/266303> I just spent around 2 hours optimizing.

This version with a helper function is actually 2 bytes shorter than my alternative eval hack:

lambda n:eval(f"%s(int(abs({n}**(1/p)//%d))**p for p in range(2,{n}+1)),"*2%("max",1,"min",-1))

Attempt This Online!

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 80 bytes using just i to simulate either max or min \$\endgroup\$
    – xnor
    Commented Oct 30, 2023 at 0:59
  • \$\begingroup\$ 77 bytes by replacing the abs(.) in xnor's solution with *i \$\endgroup\$
    – bsoelch
    Commented Oct 30, 2023 at 6:40
  • \$\begingroup\$ Needs to be 2,n+2 to work in the case of n=1. \$\endgroup\$
    – Neil
    Commented Oct 30, 2023 at 8:38
3
\$\begingroup\$

05AB1E, 16 14 bytes

LÂZ+‚εR.ΔÓ0š¿≠

-2 bytes porting @JonathanAllan's Jelly answer instead.

Try it online or verify all test cases. (Times out for the largest two test cases, so those are omitted.)

Original 16 bytes answer:

L¦©zmDï®màsî®mß‚

Port of @AidenChow's Desmos answer.

Try it online or verify all test cases. (Times out for the largest four test cases, so those are omitted.)

Explanation:

L              # Push a list in the range [1, (implicit) input]
 Â             # Bifurcate it; short for Duplicate & Reverse copy
  Z+           # Add the input to each value in the reversed copy
    ‚          # Pair them together: [[1,2,...,n-1,n],[2n,2n-1,...,n+2,n+1]]
     ε         # Map over both inner lists:
      R        #  Reverse the list
       .Δ      #  Pop and find the first value that's truthy for:
         Ó     #   Push the exponents of its prime factorization
          0š   #   Prepend a 0 (edge case for value=1)
            ¿  #   Pop this list, and push its Greatest Common Divisor (GCD)
             ≠ #   Check that it's NOT equal to 1
               # (after which the pair is output implicitly as result)

L              # Push a list in the range [1, (implicit) input]
 ¦             # Remove the leading 1 to make the range [2,input]
  ©            # Store this list in variable `®` (without popping)
   z           # Pop and convert each value in the list to 1/value
    m          # Take the (implicit) input to the power of each of these 1/value
     D         # Duplicate this list
      ï        # Floor each to an integer
       ®m      # Take each to the power [2,input] (at the same positions)
         à     # Pop and leave its maximum
     s         # Swap so the list is at the top again
      î        # Ceil
       ®m      # To the power [2,input]
         ß     # Pop and leave its minimum
          ‚    # Pair this maximum and minimum together
               # (which is output implicitly as result)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

C (gcc), 98 bytes

-1 thanks to ceilingcat

Adapted from my JS answer. Prints the bounds separated by a space.

m,M,x,p;f(n){for(M=n*n,m=1,x=p=2;m=(x*=p)>n|x<m?m:x,x<n?:x<M?M=x:(x=++p)<n;);printf("%d %d",m,M);}

Try it online!

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Vyxal, 91 bitsv2, 11.375 bytes

⇧ḢĖe:⌊>g)₍<>

Try it Online!

Bitstring:

1101001100110001001011011110000101000101000100101011000010000101000011011110111001000110010

Explained

⇧ḢĖe:⌊>g)₍<>­⁡​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁤​‎⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁡​‎⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌­
        )₍<>  # ‎⁡Find the first numbers >= and <= the input where:
       g      # ‎⁢  The minimum of
      >       # ‎⁣  comparing whether
     ⌊        # ‎⁤  the floor of:
   e          # ‎⁢⁡    the number to the power of each item in
  Ė           # ‎⁢⁢    the reciprocals of items in
⇧Ḣ            # ‎⁢⁣    the range [2, number + 2]
    : >       # ‎⁢⁤  is greater than the original list
       g      # ‎⁣⁡  is 0
💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$
6
  • 1
    \$\begingroup\$ @DmitryKamenetsky it might require more than 10 seconds of processing. Using the T flag increases the time out time to 60 seconds. And if things time out after 60 seconds, that's okay, because so long as the algorithm works in theory, it can use as much resources as it needs \$\endgroup\$
    – lyxal
    Commented Oct 29, 2023 at 2:08
  • \$\begingroup\$ Cool I got 126 to work with the T flag. Great work! \$\endgroup\$
    – Dmitry Kamenetsky
    Commented Oct 29, 2023 at 2:12
  • \$\begingroup\$ What does the bitstring represent? \$\endgroup\$
    – Dmitry Kamenetsky
    Commented Oct 29, 2023 at 2:12
  • 1
    \$\begingroup\$ @DmitryKamenetsky the bitstring represents the actual program. The program being submitted is the string of 1s and 0s. The sbcs is provided for convenience. \$\endgroup\$
    – lyxal
    Commented Oct 29, 2023 at 2:13
  • \$\begingroup\$ codegolf.meta.stackexchange.com/questions/26042/… \$\endgroup\$
    – lyxal
    Commented Oct 29, 2023 at 2:14
2
\$\begingroup\$

Charcoal, 30 bytes

ＮθＦθＦθ⊞υＸ⊕ι⁺²κＩ⟦⌈Φυ¬›ιθ⌊Φυ¬‹ιθ

Try it online! Link is to verbose version of code. Explanation: Port of @Guiseppe's R answer.

Ｎθ

Input n.

ＦθＦθ⊞υＸ⊕ι⁺²κ

Generate a list of perfect powers from 1² to nⁿ⁺¹.

Ｉ⟦⌈Φυ¬›ιθ⌊Φυ¬‹ιθ

Find the largest one not greater than n and the smallest one not less than n.

42 bytes for a less inefficient version:

ＮθＦＥ⊕₂θＸ⊕ι…·²⎇ιＬ↨θ⊕ι²Ｆι⊞υκＩ⟦⌈Φυ¬›ιθ⌊Φυ¬‹ιθ

Try it online! Link is to verbose version of code. Explanation: As above but only loops up to ⌊√n⌋ and only powers up to 1+⌊logᵢn⌋ (or 2 if i=1).

33 bytes for a more efficient version that can suffer from floating-point inaccuracy:

ＮθＩＥ⟦¹±¹⟧×ι⌈Ｅ₂θ×ιＸ×ι⌊×ιＸθ∕¹⁺²λ⁺²λ

Try it online! Link is to verbose version of code. Explanation: Port of @bsolech's golf to @corvus_192's Python answer.

Ｎθ                                  Input `N` as a number
     ¹                              Literal integer `1`
       ¹                            Literal integer `1`
      ±                             Negated
    ⟦   ⟧                           Make into list
   Ｅ                                Map over units
              θ                     Input `N`
             ₂                      Square root
            Ｅ                       Map over implicit range
                        θ           Input `N`
                       Ｘ            Raised to power
                          ¹         Literal integer `1`
                         ∕          Divided by
                             λ      Current value
                           ⁺        Plus
                            ²       Literal integer `2`
                     ×              Multiplied by
                      ι             Current unit
                    ⌊               Floored to integer
                  ×                 Multiplied by
                   ι                Current unit
                 Ｘ                  Raised to power
                                λ   Current value
                              ⁺     Plus
                               ²    Literal integer `2`
               ×                    Multiplied by
                ι                   Current unit
           ⌈                        Take the maximum
         ×                          Multiplied by
          ι                         Current unit
  Ｉ                                 Cast to string
                                    Implicitly print
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Scala, 149 bytes

A port of @Giuseppe's R answer in Scala.

Golfed version. Try it online!

n=>{val y=for{i<-1 to n;j<-2 to n}yield math.pow(i,j);val(a,b)=y.partition(_<=n);(if(a.nonEmpty)a.max.toInt else 0,if(b.nonEmpty)b.min.toInt else 0)}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    println(f(1))
    println(f(2))
    println(f(4))
    println(f(30))
    println(f(50))
    println(f(100))
    println(f(126))
  }

  def f(n: Int): (Int, Int) = {
    val y = for {
      i <- 1 to n
      j <- 2 to n
    } yield math.pow(i, j)

    val yFilteredBelow = y.filter(_ <= n)
    val yFilteredAbove = y.filter(_ >= n)

    val maxBelow = if (yFilteredBelow.nonEmpty) yFilteredBelow.max.toInt else 0
    val minAbove = if (yFilteredAbove.nonEmpty) yFilteredAbove.min.toInt else 0

    (maxBelow, minAbove)
  }
}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 63 bytes

Prompts for integer:

(↑(n=⌊/n←|m-i)/m←(⌊i*÷p)*p),↑(n=⌊/n←|m-i)/m←(⌈(i←⎕)*÷p)*p←1↓⍳30

Increase the 30 at the end of the code to handle higher integers than the examples.

Try it online! Thanks to Dyalog Classic

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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