# Coffee Space

Listen:

## Python Loops

Just a quick random one...

A friend recently proposed the following problem as part of their coursework (which I've changed to not give away the answers to others):

A sequence of numbers are defined as:

${z}_{1}=1$

${z}_{x+1}=13{z}_{x}+7$

You are to define a function `find_x(target)` that returns the smallest value of $x$ where ${z}_{x}$ is greater than or equal to the `target` value.

If implemented correctly, you should expect to see:

${z}_{1}=1$

${z}_{2}=13×1+7=20$

${z}_{3}=13×20+7=267$

${z}_{4}=13×267+7=3478$

Not too complicated - and I was really just helping with their debugging process as a new Python programmer.

### Initial Solution

Given how quickly something like this can be coded, I decided to whip something up so that I could test the correctness of their solution:

``````def find_x(target) :
x = 1
z_x = 1
while z_x < target :
z_x = (13 * z_x) + 7
x += 1
return x``````

Testing:

``````print(find_x(1))
print(find_x(10))
print(find_x(100))
print(find_x(1000))
print(find_x(10000))
print(find_x(100000))``````

And the results of the program:

``````1
2
3
4
5
6``````

Passes the sniff test.

### More Interesting

So that is kind of boring, but probably of help for others. Let's dissect this a little and make it more interesting...

Firstly, what problems does this current version have? I.e. What traps are there for new players?

1. Negative values - We are not able to handle small values, we should gracefully fail. The sequence is undefined for $i\le 0$.
2. Calculation too large - We should be careful of overflows of large integer values during the calculation.
3. Slow for large values - This will be quite painful for really large values, but fortunately this won't be a problem for Python and its limitations for the maximum integer size.

For the first two, we can do something like (we'd likely pre-calculate `max_z_x`):

``````def find_x_v2(target) :
max_z_x = (sys.maxint - 5) / 13
assert(target >= 1)
x = 1
z_x = 1
while z_x < target :
assert(z_x < max_z_x)
z_x = (13 * z_x) + 7
x += 1
return x``````

And for testing:

``````print(find_x_v2(1))                     #  1
print(find_x_v2(10))                    #  2
print(find_x_v2(100))                   #  3
print(find_x_v2(1000))                  #  4
print(find_x_v2(10000))                 #  5
print(find_x_v2(100000))                #  6
print(find_x_v2(1000000))               #  7
print(find_x_v2(10000000))              #  8
print(find_x_v2(100000000))             #  9
print(find_x_v2(1000000000))            # 10
print(find_x_v2(10000000000))           # 11
print(find_x_v2(100000000000))          # 12
print(find_x_v2(1000000000000))         # 13
print(find_x_v2(10000000000000))        # 14
print(find_x_v2(100000000000000))       # 15
print(find_x_v2(1000000000000000))      # 16
print(find_x_v2(10000000000000000))     # 17
print(find_x_v2(100000000000000000))    # 18
print(find_x_v2(1000000000000000000))   # 19
print(find_x_v2(10000000000000000000))  # 20
print(find_x_v2(100000000000000000000)) # 21``````

And as a result we get:

``````1
2
3
4
5
6
7
8
9
9
10
11
12
13
14
15
16
17
17
Traceback (most recent call last):
File "main.py", line 41, in <module>
print(find_x_v2(10000000000000000000))  # 20
File "main.py", line 17, in find_x_v2
assert(z_x < max_z_x)
AssertionError``````

So it appears that Python correctly crashes for suitably large integer values.

### Even More Interesting

Start off with the following formula:

${z}_{x+1}=13{z}_{x}+7$

For the third case (skipping the second) we can write:

${z}_{x+1}=13\left(13{z}_{x-1}+7\right)+7$

${z}_{x+1}={13}^{2}{z}_{x-1}+\left(13×7\right)+7$

For the fourth case we can write:

${z}_{x+1}={13}^{2}\left(13{z}_{x-2}+7\right)+\left(13×7\right)+7$

${z}_{x+1}={13}^{3}{z}_{x-2}+\left({13}^{2}×7\right)+\left(13×7\right)+7$

There appears to be a pattern...

${z}_{x+1}={13}^{x}{z}_{1}+{13}^{x-1}7+...+{13}^{0}7$

For example:

${z}_{6}={13}^{5}+{13}^{4}7+{13}^{3}7+{13}^{2}7+{13}^{1}7+{13}^{0}7=587880$

Whilst it's annoying that we have this long term that expands, actually for the most part we can ignore it. The first term ${13}^{x-1}7$ is much larger than all the summed terms down to ${13}^{0}7$. For the search we can therefore simplify to:

${z}_{x+1}={13}^{x}+{13}^{x-1}7$

We are trying to find something around the target, $t$, so now we search for:

$t={13}^{x}+{13}^{x-1}7$

This can be rewritten as:

$13t=20×{13}^{x}$

$\frac{13t}{20}={13}^{x}$

$lo{g}_{13}\left(\frac{13t}{20}\right)=x$

And now we have something for approximating the location of some positive value of $x$ given some target $t$.

I'm not going to go to the effort of programming this (because I don't care so much), but it's interesting to see that it's possible to find an approximate solution very quickly, without being required to do a large loop. In theory you can now find arbitrary values by performing just a 'few' calculations either side of the predicted value 1.

1. I would need to think about exactly a search strategy.