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:

0001 def find_x(target):0002 x=10003 z_x=10004 while z_x<target:0005 z_x=(13*z_x)+70006 x+=10007 return x

Testing:

0008 print(find_x(1))0009 print(find_x(10))0010 print(find_x(100))0011 print(find_x(1000))0012 print(find_x(10000))0013 print(find_x(100000))

And the results of the program:

001410015200163001740018500196

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`

):

0020 def find_x_v2(target):0021 max_z_x=(sys.maxint-5)/130022 assert(target>=1)0023 x=10024 z_x=10025 while z_x<target:0026 assert(z_x<max_z_x)0027 z_x=(13*z_x)+70028 x+=10029 return x

And for testing:

0030 print(find_x_v2(1))# 1 0031 print(find_x_v2(10))# 2 0032 print(find_x_v2(100))# 3 0033 print(find_x_v2(1000))# 4 0034 print(find_x_v2(10000))# 5 0035 print(find_x_v2(100000))# 6 0036 print(find_x_v2(1000000))# 7 0037 print(find_x_v2(10000000))# 8 0038 print(find_x_v2(100000000))# 9 0039 print(find_x_v2(1000000000))# 10 0040 print(find_x_v2(10000000000))# 11 0041 print(find_x_v2(100000000000))# 12 0042 print(find_x_v2(1000000000000))# 13 0043 print(find_x_v2(10000000000000))# 14 0044 print(find_x_v2(100000000000000))# 15 0045 print(find_x_v2(1000000000000000))# 16 0046 print(find_x_v2(10000000000000000))# 17 0047 print(find_x_v2(100000000000000000))# 18 0048 print(find_x_v2(1000000000000000000))# 19 0049 print(find_x_v2(10000000000000000000))# 20 0050 print(find_x_v2(100000000000000000000))# 21

And as a result we get:

005110052200533005440055500566005770058800599006090061100062110063120064130065140066150067160068170069170070 Traceback(most recent call last):0071 File"main.py",line41,in<module>0072 print(find_x_v2(10000000000000000000))#200073 File"main.py",line17,in find_x_v20074 assert(z_x<max_z_x)0075 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.↩