Coffee Space


Listen:

Python Loops

Preview Image

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:

z1=1 z_{1} = 1

zx+1=13zx+7 z_{x + 1} = 13 z_{x} + 7

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

If implemented correctly, you should expect to see:

z1=1 z_{1} = 1

z2=13×1+7=20 z_{2} = 13 \times 1 + 7 = 20

z3=13×20+7=267 z_{3} = 13 \times 20 + 7 = 267

z4=13×267+7=3478 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.

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:

0001 def find_x(target) :
0002   x = 1
0003   z_x = 1
0004   while z_x < target :
0005     z_x = (13 * z_x) + 7
0006     x += 1
0007   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:

0014 1
0015 2
0016 3
0017 4
0018 5
0019 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 i0i \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):

0020 def find_x_v2(target) :
0021   max_z_x = (sys.maxint - 5) / 13
0022   assert(target >= 1)
0023   x = 1
0024   z_x = 1
0025   while z_x < target :
0026     assert(z_x < max_z_x)
0027     z_x = (13 * z_x) + 7
0028     x += 1
0029   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:

0051 1
0052 2
0053 3
0054 4
0055 5
0056 6
0057 7
0058 8
0059 9
0060 9
0061 10
0062 11
0063 12
0064 13
0065 14
0066 15
0067 16
0068 17
0069 17
0070 Traceback (most recent call last):
0071   File "main.py", line 41, in <module>
0072     print(find_x_v2(10000000000000000000))  # 20
0073   File "main.py", line 17, in find_x_v2
0074     assert(z_x < max_z_x)
0075 AssertionError

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

Even More Interesting

Start off with the following formula:

zx+1=13zx+7 z_{x + 1} = 13 z_{x} + 7

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

zx+1=13(13zx1+7)+7 z_{x + 1} = 13 (13 z_{x - 1} + 7) + 7

zx+1=132zx1+(13×7)+7 z_{x + 1} = 13^{2} z_{x - 1} + (13 \times 7) + 7

For the fourth case we can write:

zx+1=132(13zx2+7)+(13×7)+7 z_{x + 1} = 13^{2} (13 z_{x - 2} + 7) + (13 \times 7) + 7

zx+1=133zx2+(132×7)+(13×7)+7 z_{x + 1} = 13^{3} z_{x - 2} + (13^{2} \times 7) + (13 \times 7) + 7

There appears to be a pattern…

zx+1=13xz1+13x17+...+1307 z_{x + 1} = 13^{x} z_{1} + 13^{x - 1} 7 + ... + 13^{0} 7

For example:

z6=135+1347+1337+1327+1317+1307=587880 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 13x1713^{x - 1} 7 is much larger than all the summed terms down to 130713^{0} 7. For the search we can therefore simplify to:

zx+1=13x+13x17 z_{x + 1} = 13^{x} + 13^{x - 1} 7

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

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

This can be rewritten as:

13t=20×13x 13 t = 20 \times 13^{x}

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

log13(13t20)=x log_{13}(\frac{13 t}{20}) = x

And now we have something for approximating the location of some positive value of xx given some target tt.

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.↩︎