godel_util.py

import math
from functools import lru_cache

def pair(x, y):
    return math.pow(2, x) * (2 * y + 1) - 1

def unpair(z):
    zr = z + 1
    x = 0
    while zr % 2 == 0:
        x += 1
        zr /= 2
    y = (zr - 1) / 2
    return x, y

def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3:
        return True
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

def prime(x):
    return primes(x+1)[-1]

def primes(x):
    global prime_cache
    if x < 1:
        return []
    primes = 1
    curr = 3
    ls = [2]
    while primes < x:
        if is_prime(curr):
            ls.append(curr)
            primes += 1
        curr += 2
    return ls

def godel(ls):
    prime_list = primes(len(ls))
    res = 1
    for i in range(len(ls)):
        res *= (prime_list[i] ** ls[i])
    return res - 1

def ungodel(x):
    x += 1
    ls = []
    curr = 0
    while x != 1:
        total = 0
        curr_prime = prime(curr)
        while x % curr_prime == 0:
            x //= curr_prime
            total += 1
        ls.append(total)
        curr += 1
    return ls

def display_ungodel(ls):
    prime_list = primes(len(ls))
    for i in range(len(ls)):
        if ls[i] == 0:
            continue
        print(str(prime_list[i]) + "^" + str(ls[i]))