Background

In programming, there is a recursive algorithm called binary exponentiation, which allows for large integer powers to be calculated in a faster way. Given a non-zero base $$\x\$$ and a non-negative exponent $$\n\$$, the algorithm goes something like this (based on the example code from Wikipedia):

Function exp_by_squaring(x, n)
if n = 0  then return  1;
else if n is even  then return exp_by_squaring(x * x,  n / 2);
else if n is odd  then return x * exp_by_squaring(x * x, (n - 1) / 2);


Basically, the code "reduces" the exponent term by first checking whether the current exponent is odd or even, then if it is even, just square root it; otherwise, divide by the base then square root it. Then repeat until the exponent reaches $$\0\$$. If the exponent is initially $$\0\$$, then just return $$\1\$$ directly.

This allows for an exponent term to be calculated faster than just multiplying the base by itself one at a time.

Example

Here is an example of the algorithm being applied on $$\x=3,n=21\$$.

1. $$\n=21\$$ is odd and non-zero, so we divide by the base, then square root. In this case, the number reduces to $$\\sqrt{\frac{3^{21}}3}=3^{10}\$$.
2. $$\n=10\$$ is even and non-zero, so we simply take the square root. $$\\sqrt{3^{10}}=3^5\$$.
3. $$\n=5\$$ is odd and non-zero, so we divide by the base, then square root. $$\\sqrt{\frac{3^5}3}=3^2\$$.
4. Continuing the process, we get $$\3^1\$$ then $$\3^0\$$, after which the recursion stops.

Notice how at each step in the example above, we have a value which resulted from reducing the original number. Your task is to return a list of these numbers, given a non-zero integer base $$\x\ne-1\$$ and a non-negative integer exponent $$\n\$$. The list should always contain the initial value as the first element. The list can be returned in reverse order if you want to.

Test Cases

   x, n     -> Output
3, 21    -> [10460353203, 59049, 243, 9, 3, 1]
1000, 0     -> [1]
2, 15    -> [32768, 128, 8, 2, 1]
1, 40000 -> [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
21, 3     -> [9261, 21, 1]
2, 30    -> [1073741824, 32768, 128, 8, 2, 1]


This is , so shortest code in bytes wins!

• Do we have to return the trailing 1? Jul 3, 2022 at 2:44
• @emanresuA Nah, too many answers, it’s too late to change now. Jul 5, 2022 at 3:18
• can you add some test cases with negatives? Jul 5, 2022 at 3:20
• @tsh will clarify, no -1 exponent Jul 5, 2022 at 3:21
• @PeterCordes If you read the rules, you can see that "the list can be returned in reverse order if you want to." So you can return it in whatever order (ascending or descending) is golfier to you. Jul 8, 2022 at 7:01

Vyxal, 5 bytes

‡½⌊↔e


Try it Online!

Takes inputs in reverse order.

Jelly, 6 bytes

HḞ$Ƭ*@  Try it online! Takes inputs in reverse order. Explanation HḞ$Ƭ*@  Dyadic link f(n, x)
Ƭ    Repeatedly apply on n until the results are no longer unique

19 bytes, different array from a more normal algorithm:

expint_v2: ; uint32_t *out (rdi),  x = esi   n = ebx
push 1
pop  rax      ; mov eax,1
stosd
.loop:              ;do{
shr  ebx, 1  ; n /= 2,  CF = old low bit
jnc .was_even
mul  esi          ; total *= x;   (destroys EDX with the high-half result, but this saves a byte vs. imul eax, esi)
.was_even:
stosd             ; *out++ = eax
imul esi, esi     ; square x
test ebx, ebx
jnz  .loop      ;}while(n!=0);
ret


Same inputs as before, same result in EAX and the highest array element (since the last bit shifted out before it becomes zero is a 1, unless n=0 in which case we leave the loop without having done mul esi.)

e.g. for 3^21 it produces these steps, where 1870418611 is 3^21 mod 2^32.

{1, 3, 3, 243, 243, 1870418611}


The x*=x steps where n doesn't have a set bit don't change the running product. (Like for multiply by addition, where you're not adding a partial product at that shift.)

I don't think it's possible to recover the same proof-of-work temporaries from this (even with a mov/imul into another temp), because we're working from the low bit up, not from the high bit down.

Starting with 1 is actually helpful, since we actually need to not start with total = x if n is even, but after we square x this iteration we no longer have any odd power of the original x left to multiply by, so the total would remain an odd power.

Starting with total=1 also makes the n=0 case Just Work for free.

Anyway, this order of temporaries is perhaps less interesting, but could probably also be recovered from a recursive implementation. I'm curious whether another challenge, perhaps titled iterative binary exponentiation, would get different answers in other languages. Probably still easier to use ** or ^ built-ins in languages that have them, after generating the right array of what, prefix-sum of bit-indices of non-zero bits or something?

Retina, 69 bytes

^
1,
\d+$* +(.+),(.+),\b(_*)\3(_?)$1¶$.($($.4*$2,1)***),$2,$3
,.+



Try it online! Link includes test cases. Outputs the list in ascending order. Explanation:

^
1,


Prefix a 1 which is the working value for the result.

\d+$*  Convert n to unary. (.+),(.+),\b(_*)\3(_?)  Match the previous result, x, n/2 and n%2. $1¶$.($($.4*$2,1)***),$2,$3


Keep a copy of the previous result, then square it and multiply it by x or 1 depending on whether n was odd. (Retina only uses the first integer it finds in a string, so multiplying 3,1, 59049,3,_ and 59049,3,_ is equivalent to multiplying 3, 59049 and 59049.) Append x and n/2 for the next pass through the loop.

+


Repeat the above until n=0.

,.+



Delete x.

Retina doesn't have exponentiation. Retina 1 does however have both eval and multiplication, so exponentiation can be (slowly) performed in 30 bytes:

~(.+),(.+)
.+¶.($2*$($1$*)_


Try it online! Link includes examples.

Husk, 6 bytes

M^U¡÷2


Try it online!

Another port of Steffan's answers: upvote those.

   ¡      # Apply function repeatedly, collect values in infinite list:
#  (using arg1 as starting value)
÷2    #  Integer-divide by 2
U       # Longest prefix with all unique elements
M         # Map over this:
^        #  arg2 to the power of this


APL (Dyalog Unicode), 20 bytes SBCS

{⍵=0:1⋄(⍺*⍵),⍺∇⌊⍵÷2}


Try it on APLgolf!

-2 bytes thanks to Vadim Tukaev

• Excellent brainchild! You can save two bytes: {⍵=0:1⋄(⍺*⍵),⍺∇⌊⍵÷2} Jul 13, 2022 at 4:08

Charcoal, 18 bytes

ＩＸθＥ⊕Ｌ↨η²↨²✂↨η²¦⁰ι


Try it online! Link is to verbose version of code. Outputs the list in ascending order (+1 byte to output in the order given in the question). Explanation:

  θ                 First input x
Ｘ                  Vectorised raised to power
η            Second input n
↨ ²           Converted to base 2
Ｌ              Take the length
⊕               Incremented
Ｅ                Map over implicit range
η      Second input n
↨ ²     Converted to base 2
✂    ⁰   Sliced to length
ι  Current value
↨²         Converted from base 2
Ｉ                   Cast to string
Implicitly print


Although Charcoal's BaseString() function would convert 0 to "0", its Base() function returns an array rather than a string, and this array is empty when n=0, so it doesn't have the problem that, say, the 05AB1E answer has. Instead, it has the problem that CycleChop([], 0) throws a ZeroDivisionError, so I have to use Slice()` instead.