Solving a difficult (polynomial?) equation in Python

Question

I am new to programming (Python is my first language) but I love to design algorithms. I am currently working on a system of equations (integers) and I cannot find any references to solving my particular problem.

Let me explain.

I have an equation (a test, if you will):

raw_input == [(90*x + a) * y] + z

where a is some constant.

My problem is, the variable z counts in a manner very similar to a Fibonacci sequence, and the variable x is the step of z. So what I mean by this (for a Fibonacci sequence) is that at the first term of the z sequence, x = 0, and at the second term of the z sequence, x = 1. I need to solve for y.

The exact process for determining z is as follows

where c and d are constants:
#at x = 0
temp = (c+(90*x)) * (d+(90*x))
temp/90 = z(0) 

#at x = 1
new_temp = (c+(90*x)) * (d + (90*x))

new_temp/90 = z(1)  

#for all the rest of the values of z (and x), use:

j = z(@ x=1) - z(@ x=0)
k = j + 180
l = z(@ x=1) + k
print "z(@ x=1) - z(@ x=0) = j"
print "j + 180 = k"
print "k + z(1) = l"
repeat until z > raw_input

this creates the spread of z values by the relation:
j = z(@ x=n) - z(@ x=n-1)
k = j + 180
l = k + z(@ x = n)

I need to scan through (skip) the values of z < x to test for the condition of a whole-number solution for y.

Does this seem possible?

Answer 1

It seems your best approach would be to recast the given equation as a recurrence relation and then either define a recursive function to determine the values you desire to compute or find the closed form solution to the relation. For more information on recurrence relations see:

• Any decent book on Combinatorics
• Wikipedia: Recurrence relation. Particularly, the sections:
  • 2.1: Linear homogeneous recurrence relations with constant coefficients
  • 2.2: Rational generating function
  • 3.1: Solving recurrence relations, General Methods
  • Though the general methods for solving recurrence relations are reasonably able, the most powerful technique is the z-transform: 3.3: Solving with z-transforms
  • 3.5: Solving non-homogeneous recurrence relations. The techniques and discussion in the rest of the article are mostly suited for pure applications, but may occasionally find practical uses as well.
• WolframMathWorld: Recurrence equation

Finally, in my experience, such problems are best tackled with mathematical numerical analysis software such as MatLab, Octave,or Mathematica. At the very least, with these you have a platform which enables rapid deployment and testing.

Answer 2

All I've done is translate your psuedo-code into Python. Maybe it can be of some help. Perhaps you should have a look at the Python tutorial if you haven't already.

# python 2.7

# raw_input returns string - convert to int
upper_bound = int(raw_input('Upper bound: '))

def z(x):
    'A function to calculate z from x.'
    # c and d are constants
    c = 5
    d = 2
    # integer division here
    return (c + 90*x)*(d + 90*x)/90

# the value of z_0
z0 = z_x = z(0)
# a list to hold the z values z_0, z_1, ...
# the list includes z_0 (when x = 0)
zs = [z0]

x = 1
while z_x < upper_bound:
    z_x = z(x)
    zs.append(z_x)

    j = zs[x] - zs[x - 1]
    k = j + 180
    l = zs[x] + k
    print j, k, l

    x += 1