Listen:

*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\times 1+7=20$$

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

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

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

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.

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?

*Negative values*- We are not able to handle small values, we should gracefully fail. The sequence is undefined for $i\le 0$.*Calculation too large*- We should be careful of overflows of large integer values during the calculation.*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.

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(13{z}_{x-1}+7)+7$$

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

For the fourth case we can write:

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

$${z}_{x+1}={13}^{3}{z}_{x-2}+({13}^{2}\times 7)+(13\times 7)+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\times {13}^{x}$$

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

$$lo{g}_{13}(\frac{13t}{20})=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}.

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