# 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 at 2:44
• @emanresuA Nah, too many answers, it’s too late to change now. Jul 5 at 3:18
• can you add some test cases with negatives? Jul 5 at 3:20
• @tsh will clarify, no -1 exponent Jul 5 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 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
$Last two links as a monad: H Halve Ḟ Floor *@ x to the power of each  # Jelly, 5 bytes :Ƭ2*@  Try it online! Takes n on the left, and x on the right. Based on Steffan's answer, so be sure to give them an upvote as well. ## How it works :Ƭ2*@ - Main link. Takes n on the left and x on the right Ƭ - Repeatedly apply until a duplicate value is found: : 2 - Floor divide n by 2 *@ - Raise x to each power  # 05AB1E, 7 bytes bη0šÙCm  Try it online! b convert the exponent to binary η takes all prefixes 0š append the prefix "0", to include 1 in the list Ù uniquify, since if the exponent was 0 then "0" was already a prefix C convert each prefix from binary to a number m exponentiation  # 05AB1E, 7 bytes ·.Γ;ï}m  Try it online! A port of the Vyxal and Jelly answer # PARI/GP, 34 bytes f(x,n)=[x^m\=2|i<-binary(m=2*n+1)] Attempt This Online! # PARI/GP, 29 bytes f(a,n)=if(n,f(a,n\2)*x+a^n,1) Attempt This Online! This returns a polynomial whose coefficients are the results. # Desmos, 42 bytes f(x,n)=x^{floor(n/2^{[0...ceil(log_2n)]})}  Try it on Desmos! # Python 2, 37 bytes (-1 @Steffan, -2 @dingledooper) f=lambda x,n:[1][n:]or[x**n]+f(x,n/2) Attempt This Online! ### Old Python, 40 bytes f=lambda x,n:[x**n]+(n*[n]and f(x,n//2)) Attempt This Online! Doesn't actually implement the algorithm. But produces correct output. • I guess you could save a byte if you wanted to use Python 2 Jul 3 at 3:18 • True ...@Steffan Jul 3 at 3:21 • 38 bytes? f=lambda x,n:[1][n:]or[x**n]+f(x,n//2) Jul 3 at 6:37 # JavaScript (Node.js), 30 bytes x=>g=n=>[x**n,...n?g(n>>1):[]]  Try it online! # Java, 59 bytes x->n->{for(n*=2;n>0;)System.out.println(Math.pow(x,n/=2));}  Try it online! # BQN, 16 bytes ⊣⋆{×𝕩?𝕩∾𝕊⌊𝕩÷2;0}  Try it at BQN REPL  { } # Recursive function acting on right argument 𝕩 : ? # if ×𝕩 # sign of 𝕩 is non-zero 𝕩∾ # join 𝕩 to 𝕊 # the result(s) of a recursive call to this function # with argument: ⌊ # floor of 𝕩÷2 # 𝕩 divided by 2. # Now, get ⊣ # the left argument ⋆ # raised to these powers  # C (GCC), 66 53 bytes -13 bytes thanks to @att r;f(x,n){printf("%d ",r=n?f(x,n/2),(n%2?x:1)*r*r:1);} Attempt This Online! • 53 bytes – att Jul 6 at 2:47 # 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. # 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.

### 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?

# 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 at 4:08