Coffee Space


Listen:

Python Loops

Preview Image

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

zx+1=13zx+7

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

If implemented correctly, you should expect to see:

z1=1

z2=13×1+7=20

z3=13×20+7=267

z4=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 i0.
  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:

zx+1=13zx+7

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

zx+1=13(13zx1+7)+7

zx+1=132zx1+(13×7)+7

For the fourth case we can write:

zx+1=132(13zx2+7)+(13×7)+7

zx+1=133zx2+(132×7)+(13×7)+7

There appears to be a pattern...

zx+1=13xz1+13x17+...+1307

For example:

z6=135+1347+1337+1327+1317+1307=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 13x17 is much larger than all the summed terms down to 1307. For the search we can therefore simplify to:

zx+1=13x+13x17

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

t=13x+13x17

This can be rewritten as:

13t=20×13x

13t20=13x

log13(13t20)=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.