# The first digit of a to the power of b (approximately)

Inspired by This answer to a Puzzling question

Background - exponentiation by squaring
If you don't want to read the background, or don't understand it, there's a worked example in Java, linked at the bottom of the post.

$$\a^{2^{x+1}} = a^{2^{x}} * a^{2^{x}}\$$

Therefore to find $$\a^b\$$ (where $$\a\$$ and $$\b\$$ are base-10 numbers), you can use the following steps:

(using the example: $$\a^b = 3^{2020} = 6.0944502154628860109199404161593e+963\$$)

1. Convert $$\b\$$ to binary ($$\2020\$$ -> $$\11111100100\$$)
2. For each $$\1\$$ in the binary ($$\n\$$), calculate $$\a^n\$$, by starting at $$\a^1\$$ and repeatedly squaring to get $$\a^2\$$, $$\a^4\$$, etc... and keeping only those numbers we need ($$\3^1 = 3\$$, $$\3^2 = 9\$$, squared gives $$\3^4 = 81\$$, squared gives $$\3^8 = 6561\$$, squared gives $$\3^{16} = 43046721\$$, squared gives $$\3^{32} = 1853020188851841\$$, etc. We just keep those numbers where the binary mask is a 1.)
3. Multiply all the kept answers from step 2 where the binary mask is a $$\1\$$ ($$\81*1853020188851841*...\$$).
4. The first non-zero digit is therefore $$\6\$$.

The problem with this method though, even though it is easier for humans than calculating such a large exponent straight-off, is that you still have to square some pretty large numbers.

In Theory, though, we can approximate!

According to the link at the start of the question, you can approximate by just considering the first $$\n\$$ digits (rounded) at each stage in step 2 above - with larger $$\n\$$ giving a lower margin of error.

For example, if $$\n=4\$$, then you get* $$\3^2=9,^2=81,^2=6561,^2\approx4305,^2\approx1853,^2\approx3434,^2\approx1179,^2\approx1390,^2\approx1932,^2\approx3733\$$.

note that the numbers here have been rounded*, rather than just truncated - e.g. 6561 * 6561 = 43046721 - which has been rounded to 4305 rather than 4304.

Keeping $$\3733,1932,1390,1179,3434,1853,81\$$ from the bitmask we can then do $$\3733*1932*1390*1179*3434*1853*81= 6091923575465178358320\$$, so the first digit is $$\6\$$, as we would expect.

This is not only easier in our heads, but it gives us the same first digit! Much simpler!

However, if we only consider the first $$\3\$$ digits when we double, instead of the first $$\4\$$, we get $$\353*188*137*117*342*185*81 = 5451573062187720\$$, which gives us a first digit of $$\5\$$ instead of $$\6\$$ - that's why it's only approximately accurate!

The Challenge is to find the first digit of $$\a^b\$$, where only the first $$\n\$$ digits, rounded, are considered each time we square. You don't have to use exponentiation by squaring in your program, if you can get the correct answers by another method.

Inputs

Three positive Integers (greater than $$\0\$$), up to an arbitrary maximum (your program should work in theory for all possible Integers) - the base $$\a\$$, the exponent $$\b\$$ and the approximation length $$\n\$$

Output

a single digit or character in the range [1..9]

Some Worked Examples

3,2020,3 -> 5 (see worked example in background above)
3,2020,4 -> 6 (see worked example in background above)

2,20,1 -> $$\20_{10} = 10100_2. 2^1=2,^2=4,^2=16\approx2,^2=4,^2=16\approx2\$$ which gives $$\2^{16}*2^4\approx2*2\$$ = 4
2,20,2 -> $$\2^1=2,^2=4,^2=16,^2=256\approx26,^2=676\approx68\$$ which gives $$\68*16 = 1088\$$, first digit 1
2,20,3 -> $$\2^1=2,^2=4,^2=16,^2=256,^2=65536\approx655\$$ which gives $$\655*16 = 10480\$$, first digit 1
2,20,4 -> $$\6554*16 = 104864\$$, first digit 1
2,20,5 or above -> $$\65536*16 = 1048576\$$, first digit 1

15,127,5 -> 15,225,50625,25629...,65685...,43145...,18615... -> 231009687490539279462890625 -> 2

The same Examples formatted for easy copying, plus some additional ones

a,b,n,outputs result
3,2020,3 outputs 5
3,2020,4 outputs 6
3,2020,5 outputs 6
2,20,1 outputs 4
2,20,2 outputs 1
2,20,3 outputs 1
2,20,4 outputs 1
2,20,5 outputs 1
2,20,6 outputs 1
2,11111,4 outputs 5
4,1234,3 outputs 8
5,54,2 outputs 6
6,464,3 outputs 1
7,2202,4 outputs 8
8,1666,5 outputs 3
9,46389,6 outputs 2
10,1234,7 outputs 1
11,5555,8 outputs 8
12,142,14 outputs 1


Sample implementation on TIO

This is , usual rules and restrictions apply, lowest bytes wins.

EDIT

*to clarify what I mean by rounding, any number less than $$\x.5\$$ should round down to $$\x\$$. Any number greater than $$\x.5\$$ should round up to $$\x+1\$$. The boundary ($$\x.5\$$) can go either way, depending on your language.

• About the sample implementation: a random quote from the getFirstCharacterApproximately function: BigInteger.valueOf(Long.parseLong(fullCurrentPowerString.substring(0, Math.min(fullCurrentPowerString.length(), n+1)))); :) May 4, 2020 at 9:22
• @mypronounismonicareinstate It wasn't supposed to be a golfed sample implementation :P May 4, 2020 at 12:18
• "Multiply and round" is not an associative operation. How should the various a^2^x be multiplied together? May 4, 2020 at 15:57
• That is a pretty convoluted way to get a wrong digit :D May 5, 2020 at 10:57
• Yep, fun it is ;) love this kind of maths May 5, 2020 at 11:00

# Python 2, 88 bytes

a,b,n=input()
s=1
while b:a=int(a[:n])+(a[n:]>"5");s*=a**(b%2);a*=a;b/=2
prints


Reads 3 integers from STDIN, and print out the first digit approximation.

Rounding: x.5 is always rounded down. This causes the test case (5, 54, 2) to gives the wrong result.

Explanation:

This part is the regular exponentiation by squaring:

while b:s*=a**(b%2);a*=a;b/=2


This is the rounding part:

a=int(a[:n])+(a[n:]>"5")


which takes the first n digits of a, and adds an extra 1 if the remaining part is more than 5.

• Way shorter than what I wrote :)
– RGS
May 4, 2020 at 20:40

# Charcoal, 45 bytes

ＮθＮηＮζＦ⮌↨η²«Ｆι⊞υθ≧×θθ¿›ＬＩθζ≔÷⁺⁵Ｉ…Ｉθ⊕ζχθ»§ＩΠυ⁰


Try it online! Link is to verbose version of code. Explanation:

ＮθＮηＮζ


Input a, b and n.

Ｆ⮌↨η²«


Loop over the bits of b from LSB to MSB.

Ｆι⊞υθ


If the current bit of b is set then push a to the empty list.

≧×θθ


Square a.

¿›ＬＩθζ


If a has more than n digits...

≔÷⁺⁵Ｉ…Ｉθ⊕ζχθ


... then take the first n+1 digits, add 5, and drop the last digit, thus rounding the power of a to n digits.

»§ＩΠυ⁰


Print the first digit of the product of the desired powers of a.

# JavaScript (Node.js), 100 bytes

Takes input as (b)(n)(a), where $$\a\$$ and $$\b\$$ are BigInts.

b=>n=>g=(a,k=p=1n)=>k>b?(p+g):g((BigInt((a*a+'0'.repeat(n)).slice(0,n+1))+5n)/10n,k+k,b&k?p*=a:0)


Try it online!

# JavaScript (ES6),  92  87 bytes

Improved the upper bound of $$\n\$$ thanks to @Neil

Without BigInts. Works for $$\n\le 10\$$.

b=>n=>g=(a,k=p=1)=>k>b?(p+g):g((+(a*a).toPrecision(n)+'').slice(0,n),k+k,b&k?p*=a:0)


Try it online!

### How?

At each iteration:

• We compute $$\a^2\$$ with $$\n\$$ significant digits thanks to the .toPrecision() method. This gives a string, which may be in scientific notation.

Example for $$\a=1023\$$:

  (1046529).toPrecision(4) ~> "1.047e+6"

• we coerce this result to a number and immediately back to a string:

  +(1046529).toPrecision(4)+'' ~> "1047000"

• we keep the $$\n\$$ first characters to get the new value of $$\a\$$:

  (+(1046529).toPrecision(4)+'').slice(0,4) ~> "1047"


The highest value of $$\n\$$ that can be supported is $$\10\$$ because:

$$(10^{10}-1)^2=99999999980000000000$$

which is already greater than Number.MAX_SAFE_INTEGER, but sill coerced to its standard decimal representation "99999999980000000000".

For $$\n>10\$$, the result is always stringified in scientific notation (e.g. 9.9999999998e+21) and the algorithm doesn't work anymore.

• How high could n go if you used toPrecision instead of manual rounding?
– Neil
May 4, 2020 at 14:59
• @Neil I think that would work up to n=10 -- and the same byte count, I think. Is that what you had in mind? May 4, 2020 at 15:15
• To be honest I hadn't looked at the byte count, I was just curious as to whether it worked for higher n.
– Neil
May 4, 2020 at 15:18

# Python 3.8 (pre-release), 131 bytes

lambda a,b,n:(m:=a)and str(math.prod((m:=round(m/10**(len(str(m))-n)))**int((m:=m**2)and c)for c in f"{b:b}"[::-1]))
import math


Try it online! How it works:

lambda a,B,n:                      # function taking the three arguments as input
(m:=a)and             # initialize the base for repeated squaring and
str(...) # return the first digit of the string representing the final number

# Inside str():
math.prod(                           ) # the product of (new in 3.8)
... for c in f"{B:b}"[::-1]  # something we compute for each character in the reversed binary representation of the input B

# Use repeated := to modify the base we keep squaring
# Inside math.prod(... for c in f"{B:b}"[::-1])
(m:=                            )                      # modify m
round(m/10**(len(str(m))-n))                       # by rounding it to the first n digits
(m:=m**2)and    # finally we square m again (without effecting anything else)
**int(             c) # and only include this number in the product if the binary digit is 1


My (5, 54, 2) test case gives a different result; I suspect it is because of how Python rounds 62.5 vs how the reference implementation rounds 62.5. Python rounds it down to 62, but if I force Python to round up I get the reference solution of 6.

• In Python 3, round tie-breaks to nearest even instead of away from 0. So you probably need to use the longer solution :( May 4, 2020 at 13:12
• I think the standard Python rounding is fine, actually. It's not key to the problem which what happens at the .5 boundary, just that the numbers are rounded. Other numbers should still round up/down accordingly though (so you can't just round everything decimal down, for example). I'll update the spec to clarify May 4, 2020 at 14:39
• @simonalexander2005 I'm not saying python's rounding is wrong or whatever. I just explained why my solution gave a different result from your solution. With your updated spec, my "error" is no longer an error and all is fine :)
– RGS
May 4, 2020 at 16:02
• Save a byte by using m*m in place of m**2. May 4, 2020 at 18:08
• 114 bytes by not using m, and shorten the rounding part. Can be way shorter with recursion though. May 5, 2020 at 2:42

# 05AB1E (legacy), 20 bytes

b©vDnDg°I°÷/ò})®RÏPн


Uses the legacy version of 05AB1E, because division-by-zero errors will result in the initial integer, whereas the new 05AB1E version would make it 0 instead.

Input-order as $$\b,a,n\$$.
Just like both Python answers, the test case 54,5,2 will result in 4 instead of 6, because of different rounding than the Java reference implementation.

Explanation:

b              # Convert the (implicit) input-integer b to a binary string
©             # Store it in variable ® (without popping)
v            # Pop and loop its length amount of times:
D           #  Duplicate the top value
#  (which is the implicit input-integer a in the first iteration)
n          #  Square it
Dg        #  Take its length without popping (by duplicating first)
°       #  Take 10 to the power that length
I°     #  Take 10 to the power input-integer n as well
÷    #  Integer-divide 10^length by 10^n
/   #  Divide the current square by this
#  (the value remains the same for division-by-zero errors in the legacy
#   version, which will happen if the amount of digits in the squared
#   value is smaller than n)
ò  #  And bankers-round that decimal to the nearest integer
})           # After the loop: wrap all values on the stack into a list
®R         # Push the binary-string from ® and reverse it
Ï        # Only leave the values in the list at the 1-bits
P       # Take the product of those remaining values
н      # And pop and push its first digit
# (after which it is output implicitly as result)