Checking divisibility for (sort of) big numbers in python
Question: I've been writing a simple program in python that encodes a string into a
number using [Gödel's
encoding](https://en.wikipedia.org/wiki/G%C3%B6del_numbering#G.C3.B6del.27s_encoding).
Here's a quick overview: you take the first letter of the string, find its
position in the alphabet (a -> 1, b -> 2, ..., z -> 26) and raise the first
prime number (2) to this power. The you take the second letter in the string
and the second prime (3) and so on. Here's the code:

    
    
    import string, math
    alphabet = list(string.ascii_lowercase)
    
    def primes(n):
        "Returns a list of primes up to n."
    
        primes = [2, 3]
        i = 5
        while i < n:
            l = math.ceil(math.sqrt(i))
            k = math.ceil(math.sqrt(i+2))
            for p in primes[:l]:
                if i % p == 0:
                    break
            else:
                primes.append(i)
            for p in primes[:k]:
                if (i+2) % p == 0:
                    break
            else:
                primes.append(i+2)
            i += 6
        return primes
    
    def Encode(string):
        "Encodes a string using Godel's encoding."
    
        enc = 1
        p = primes(100)
        for i in range(len(string)):
            enc = enc*(p[i]**(alphabet.index(string[i])+1))
        return enc
    
    def Decode(code):
        "Decodes a Godel's encoding into a string."
    
        dec = ""
        for i in primes(100):
            count = 0
            while code % i == 0:
                code /= i
                count += 1
            if count == 0: #If we've found a prime that doesn't divide code, 
                           #there are no more letters to be added.
                break
            else:
                dec += alphabet[count-1]
        return dec
    

The primes() function works for my intends and purposes and so does Encode().
Now Decode() is the interesting part. It works for encodings up to ~15 digits
long but starts doing some mystical stuff starting at ~20 digits. So for
instance it gives the right output for the encoding of "aaaaaaaaaaaaaa" but
not for "python". For big numbers it seems to execute the `while code % i ==
0` loop too many times (176 for the first letter of "python" when it should be
just 16).

Is this just a problem with the mod function in python? Sounds strange as 20
digits isn't all that long for a computer. Is there a mistake in my code?
Thanks for all the help. I'm not a programmer myself but I'm trying to learn
doing stuff like this. Therefore any constructive criticism is welcome.


Answer: `/=` in Python 3 returns a double-precision floating point value. (As does
`math.ceil`, btw.) Floating point values do not have arbitrary precision. You
could use `//=` instead. That always results in an integer. (It gives the
floor of the result.)

(I previously said that math.ceil was your main culprit. I don't think that's
the case, but nonetheless, you probably shouldn't be using a floating point
value to index into a list. If you need to run the same code in Python 2 that
will fail. You can cast it back to an integer using `int(math.ceil(...))`,
although you might want to consider avoiding floating-point calculations
altogether, since things will begin to break down for sufficiently large
values.)

