9
\$\begingroup\$

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.

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

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
print`s`[0]

Try it online! or Check all test cases!

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Way shorter than what I wrote :) \$\endgroup\$ – RGS May 4 at 20:40
2
\$\begingroup\$

Charcoal, 45 bytes

NθNηNζF⮌↨粫Fι⊞υθ≧×θθ¿›LIθζ≔÷⁺⁵I…Iθ⊕ζχ軧IΠυ⁰

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

NθNηNζ

Input a, b and n.

F⮌↨粫

Loop over the bits of b from LSB to MSB.

Fι⊞υθ

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

≧×θθ

Square a.

¿›LIθζ

If a has more than n digits...

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

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

»§IΠυ⁰

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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)[0]: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)[0]: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.

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

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]))[0]
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(...)[0] # 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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ In Python 3, round tie-breaks to nearest even instead of away from 0. So you probably need to use the longer solution :( \$\endgroup\$ – Surculose Sputum May 4 at 13:12
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – simonalexander2005 May 4 at 14:39
  • \$\begingroup\$ @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 :) \$\endgroup\$ – RGS May 4 at 16:02
  • \$\begingroup\$ Save a byte by using m*m in place of m**2. \$\endgroup\$ – Noodle9 May 4 at 18:08
  • \$\begingroup\$ 114 bytes by not using m, and shorten the rounding part. Can be way shorter with recursion though. \$\endgroup\$ – Surculose Sputum May 5 at 2:42
1
\$\begingroup\$

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.

Try it online or verify all test cases.

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)
| improve this answer | |
\$\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.