**Register Now!**

Welcome back with another problem to solve!

Today’s problem will focus on calculating big exponentials from scratch. This problem is similar to the problem seen in the **If you have problems following along, I highly recommend you check Daily Coding Problem number 20 for a much deeper explanation since the concepts involved are the same.**

This problem is provided by the wonderful website

We’ll be using Go for this program: headache time! :D

Let’s take a look at the problem:

*2¹⁵ = 32768, and the sum of its digits is 3+2+7+6+8=26.*

*What is the sum of the digits of the number 2¹⁰⁰⁰?*

The problem is really simple: we need to calculate 2¹⁰⁰⁰ and sum its digits to give it a result. Simple, isn’t it? Well…

To give out some simple basics, an exponential number is simply the repetition of that same number a certain number of times. For example, writing 4³ means calculating 4*4*4. What’s really cool about powers (which is also what causes us this problem) is how fast they grow: not the fastest, but still pretty fast.

The function we are interested in is the green one: you can easily see how fast it grows. Even if the power function x³ grows faster initially, the exponentiation of 2 catches up pretty quickly. As in the previous article, try with your calculator: you should not be able to calculate over 2³³², which is 8.749002899x10⁹⁹.

And yet, with a little bit of reasoning and a simple program, we can calculate that 2³³³ is

```
17498005798264095394980017816940970922825355447145699491406164851279623993595007385788105416184430592
```

And with the same approach, 2⁵⁰⁰ is

```
3273390607896141870013189696827599152216642046043064789483291368096133796404674554883270092325904157150886684127560071009217256545885393053328527589376
```

Cool right? Let’s see how it’s done then!

If there’s one thing computers are good at, **it’s repeating the same job multiple times really fast**. We’ll exploit this ability to repeat a simple task many, many times to iterate over all the exponents from 1 to the desired one and print out the result. The simple operation we are doing is the **multiplication of a certain number with the number 2** to increase the exponent. However, we are doing this by multiplying each digit of the starting number by 2: this way, we can manage increasingly big numbers simply by multiplying their digits. Let’s write a multiplication function.

As always, let’s explain a bit what’s happening here. We create the `multiply`

function, which takes in two parameters: `stringedInt`

, the integer we want to multiply, and `factor`

, the factor we are multiplying it for. After that, we define the variable `carryover`

, which we’ll explain in a moment.

Now we start looping: we loop over the length of `stringedInt`

and multiply each digit by `factor`

.

We have some type of conversion to do, however:

- first off, we use the variable
`integer`

to save our converted digit from the string (with`stringedInt[n]-'0'`

we convert the*rune*value to its UNICODE counterpart and then convert it to`int`

) - then, with the
`fmt.Sprintf`

function, we convert the result back to a string and add it to the front of the`out`

variable, which will be our result.

Let’s take a moment at the math done here: the possible digits we are multiplying are 0,1,2,3,4,5,6,7,8,9, but the results somehow repeat in a certain manner. For example, **2*2 is 4, and 2*7 is 14, so a 4 with a 1 in front of it**. The 1 will be our carryover, which will be added to the next multiplication, **so to keep just the unit digit we calculate** `integer % 5 * 2`

**.** If you’re not versed with modulo operations, `integer % 5 * 2 + carryover`

.

We must store the carry though; that is done in the next block of code, which evaluates if `integer > 4`

. This is because, for values from 5 to 9, our mudulo will bring us back to the values from 0 to 4, but we need to deal with the carry. **We know that the carry can only be 1 at most,** so we simply check if `integer > 4`

: if it is, we have a 1 to carryover and we store it in its variable `carryover`

.

**The final block, from lines 12 to 14, simply adds the last carry possibly left from the last multiplication:** for example, if the last number multiplied was an 8, `out`

will now start with a 6, but we have a 1 stored in `carryover`

. We must add it to the front of `out`

to have the correct result.

It’s really basic math, to be honest, but describing it textually could make it worse than it is. So here’s a drawn example of the process:

Now we just need to apply that process 1,000 times to calculate the wall of text corresponding to 2¹⁰⁰⁰! Let’s write the simple code:

In our `main`

function, we define the `final`

variable, initially equal to `"1"`

. Then we loop over for 1000 times to update the result. Now, since the problem wants the sum of the digits of 2¹⁰⁰⁰, we simply create the variable `sum`

and loop over `final`

summing up all the digits.

**Also, this same algorithm can be used to calculate every exponential of every number:** just change the value in the `multiply`

call or the `n`

upper limit in the loop, and you’ll get whatever result you want. For example, running

```
...
for n := 0; n < 500; n++ {
final = multiply(final, 5)
}
...
```

Will calculate 5⁵⁰⁰.

As in **ProjectEuler.net is really a lovely project:** besides presenting math riddles and problems, **their main focus is to provide a tool to start learning, thinking, and reasoning about math**. And I love that they are so committed that publishing results and guides for their problems is actually forbidden (this is one of the first 100 problems, so I understand it is permitted). Given this, **I don’t feel it would be fair to just give out the solution to copy-paste and get the achievement**.

Have a nice coding, guys! 😎

As always, let’s take a brief moment to discuss the time complexity of this algorithm. The first part of the code runs a number of times equal to the length of the `stringedInt`

, which, unfortunately, will increase at each loop. Then, we run the multiplier `n`

times to reach the nth exponent. So, technically speaking, we’ll have a complexity of `O[len(stringedInt)*n]`

, which we can generalize with some approximation to O(n²).

Here it is: that’s my solution! I hope you enjoyed following along and reading about this problem. If so, please leave a clap or two: that would make my day!

Also, if you are willing and can contribute to the channel, share a Ko-fi.

As always, thank you so much for reading.

*Nicola*

*Also published here.*

L O A D I N G

. . . comments & more!

. . . comments & more!