Who wants to do some math for fun? I do!
So yesterday, I commented on this reddit post, which had the following image.
Long story short after some ragebaiting, I was dared to count to a trillion, which I started doing with a python script.
The principle problem here however, is that reddit has a 10k character limit on comments. So I wondered, how long would it take me to REALLY do this, assuming each comment takes me about 15ish (or any other amount) of seconds to create?
The hiccup in this question, is that as the numbers grow, so does the number of characters required for each number. An additional note is that every number is append with ", " a comma and a space, adding another 2 characters per number.
Let us define a few helpful functions.
N(x) = the amount of digits in x.
T(l, x) = the amount of numbers of length N(x) you could fit in a message of length at most l.
We can find t by solving a simple inequality. If we have n numbers of some length N(x), where for every number we also have two additional characters, then:
Now, n is an integer, so we will need to round. Since ceiling will give us a number too big to fit in a message, we must use floor.
And that is T(l, x). Great! Were you to naively apply it across every partition to check how many messages you need to rise a partition, IE by solving T(l,x)*k = <However many you need to go to the next partition>, you would get a very good estimate. But I did not want an estimate, I wanted the exact amount! That requires you the account for the times you swap partitions mid message, so we need a slightly more complex function. Let us define another two more helper functions:
Q(x) = how far x is from the next partition (how many numbers are left in the partition, in other words)
C(x) = How many numbers you can fit in a message, allowing to change partitions once mid message.
The reason I can assume there won't be multiple partition changes, is because even in the 4 digit numbers each message contains no more than 2000 numbers. We are at a starting point of 10k, so there is no way to go more than one partition midway. But how do we define C(x)?
It can look like a bit of a mouthful, but let's think about it together. We compare T to Q to know if this message is going to cross a partition. That is, if the amount of numbers we can fit in a message is less than the amount we have in the partition, we won't cross to a new one. In that case, T as is will work. But otherwise, we need to do more work.
First, we write Q(x) numbers who have the same amount of digits as x. The rest of the partition. After that, we can calculate how many more numbers we can write, by using T with a modified limit and multiplying x by 10 (the same as adding one more digit).
This new limit is our old one, minus the amount of characters we already wrote. You'll notice the amount we remove is exactly like the formula we used to derive T in the first place, which represented how many characters we are writing.
Boom! We have a function that for any x we give it, will tell us how many numbers starting from it we could write. It's pretty obvious then that if we calculate x + C(x), we will get the number the next post starts with.
Actually Answering The Question!
Now to make things easier, we will find what I call "critical numbers." These are the numbers for which T(10^4,x)=Q(x). I did this with python code.
It's not the most readable code and there's a small optimization there that made this easier than just scanning through hundreds of billions of numbers, but in essence it spat out the following numbers.
Now all we need to do is solve for how many times we'll be able to apply C(x) + x until we reached the critical point. For every partition, we simply need to solve:
Notice we use ceiling here. By doing z messages, we will get into the critical zone, the area between a critical number and the start of a new partition. Now once we are in the critical zone, it's easy enough to verify by contrasting C(x) for every critical number that one more message will get us to the next partition.
So then, to get past a partition, we need to do z + 1 steps, where x is the number we start that partition at. This is very easy to compute with the following code:
And the output in years? Drumroll....
It would have taken me 660.873~ years to do this! With 10^12+140 being the final number, and 1389432617 being the amount of messages.
Aaaand that's it. In a way it feels like it should not have taken me a few hours to solve this, but running into a the challenge of the numbers being so big that I can't bruteforce too much slowed the process down and forced me to get more efficient at places where I wanted to be lazy. It also had me trying to solve some really scary equations naively and forced me to think smart to get around them. Fun stuff.
