Python riddle to solve in reasonable time

Hello. My name is Robert Krawiec. I am a mathematics major. I’ve been working for Profil Software (a Python web app and mobile app Development Company that also offers software testing services and UX/UI Design Services) for quite some time. I often use different algorithms and I find my mathematical background useful while developing web apps using object oriented languages.

Today I would like to share with you a riddle that I came across while working here. It goes like this:

Find a number that ends with the digit 2 and has the following feature: if you create a new number by moving the last digit into position as the first digit, this new number will be twice as big as the original one.

As complicated as it sounds, we can transcribe this riddle into an equation:

We are looking for a number ab…n2; let’s call it x for the remainder of the article. Just to clarify things, the dots are meant to represent that we don’t know how many digits this number has.

Seems quite straightforward eh? Well, that was my first observation too. Anyway, let me share my research with you. I would also like to show you some different approaches to this problem.

Construction method

Some of you may be familiar with the concept of constructing different mathematical objects. We’re going to use construction method here, but it’s not really something that is straightforward, so let’s take a closer look at it.

Let’s take two sides of the equation. Let’s say y=2*(ab..n2) and z = 2ab..n . We already know that in order to fit the equation, y and z must be the same length.

This is derived from the fact that two numbers may be equal only when they share the same length. Wait, what… since y and z are the same length, and y simply equals 2*x, and the first digit in the number z is 2, we can conclude that the first digit in the number x is indeed 1.

So now the problem gets easier. We can conclude that the digit in position n in the number x is twice as big as the digit in position n+1. This is another feature that is derived from what we’ve stated above. Now we can start constructing such a number having in mind that the written method for multiplication uses carry overs. So it goes:

2
42
842
6842
36842
736842
4736842
94736842
894736842
7894736842
57894736842
157894736842

Ok, let’s check this number. It may be our solution since it has a 2 at the end and a 1 at the beginning. Nope, let’s proceed.

...
3157894736842
63157894736842
263157894736842
5263157894736842
05263157894736842
105263157894736842

We’ve finally found a solution by constructing such a number. We can see that if we continue constructing numbers, we will come across a pattern.

Every 16 construction steps we’re going to have a number that is a solution to our problem. Moreover, since the set of all natural numbers is infinite and there is a pattern, we can say that there are an infinite number of solutions to this problem.

Brute-force search method

Since we use a lot of Python in our everyday work, I figured I would use it to perform an exhaustive search, even though I’m quite aware of the fact that this is not the most effective language for such a task. I am also going to use my own i7 4/8 processor.

For the sake of clarity, I will note down the partial time needed for an exhaustive search script to reach 10 figures. For obvious reasons, I won’t run every version of the code until it finds the solution.

Let’s summarize what we know about the candidates for such a number. We certainly know that it ends with 2, which means we can decrease our search by a factor of 10. Here’s the code:

Let’s run it and measure its partial efficiency. We’ve calculated that it has taken around a minute to reach the first number that consists of 10 digits.

Now that we can see the code works, let’s look at how we can possibly improve it. The problem here is that we are wasting a lot of time because of how we increment.

Let’s use this code to jump to a higher range to ignore numbers that do not start with 1. Here’s the code:

As with the previous algorithm, we’ve tested it and it takes about 45 seconds to reach 10 digits.

That’s a significant improvement. Now let’s use a generator to populate the queue on the fly. Here’s some code that is doing pretty much the same thing, but in a different way.

We can run this code, but unfortunately it does not hasten our search, because it still takes around 45 seconds to fulfill its job.

Observation:

There’s an exponential growth in the amount of numbers that we have to check. Let’s take for instance the amount of numbers that we need to check that have 9 digits.

We know that each number must have 1 as the first digit and 2 as the last, so we end up with 10 000 000 numbers to check. We can see that each time the range is increased, the amount of numbers that we have to check is 10 times bigger than the previous one. Using this information, we can express how many possible solutions there are. To count the amount of digits that might be a solution to our problem, we can use the formula for the partial sum of a geometrical series, which in this case is represented by:

For example, there are 1111111 numbers that we have to check before getting into numbers that have 10 digits. That way, we can estimate how much checking each candidate takes, which is 0.0405000041 ms per number. We can use it as the lower limit of this operation, which means that operations on bigger numbers can take at least that long, but might take longer.

As we all know, it’s a mundane assignment to use an exhaustive search to find a really big number. After countless attempts to speed up finding the solution using multiprocessing or multi-threading with Python, I came to the conclusion that distributing everything across the processors yourself is almost as good as Python managing these kinds of tasks on its own.

Next, I thought I’d estimate the time needed to check all possible candidates that have less than 18 digits. I figured out that it would take years, which makes solving this problem using a brute-force search very ineffective.

Breaking down the problem

To solve a problem, it’s imperative to find as many features of the problem as possible.

Looking at the brute-force search, it’s ineffective mostly because we didn’t find more features or assumptions to start with. Let’s take a look at the problem using the first equation:

We can transform it into:

Let k = ab..n (Which is our number without the 2 at the end). Then:

Finally we get:

We know that k is a possible solution to our problem. Let’s create a function that takes n = len k as an argument. Which in this case will be next natural numbers.

We get:

Let’s take a look at what this function’s values are:

2
10.315789
3
105.052632
4
1052.421053
5
10526.105263
6
105262.947368
7
1052631.368421
8
10526315.578947
…

We can see that this function approximates solutions to our problem based on it’s length.

For n = 17 we get the first whole number which is our ab…z without 2 at the end. If we were to continue, another solution would pop up every 16 incrementations. We can see this function works like a generator, especially when you look for the integer part of those numbers. It works just like the construction method above except it builds the solution from the left side and omits the number 2.

Summary:

We have just shown some examples of how to solve this kind of puzzle. Despite the fact that we worked hard to make the brute-force search time effective, we failed to do so.

This is something that we could have expected based on its nature and the vast number of possible solutions. That’s why it is always useful to seek more elegant solutions, even when they do not come to us very easily. If you're curious about other things related to Python, such as making your code more Pythonic using Python Magic Methods or choosing a Python Framework for a Startup, make sure to look through our software development blog.

I hope that you have found this article useful.