recprimefac.py

#!/usr/bin/env python3
import sys, itertools
import urllib.parse
from collections import defaultdict, Counter

try:
    import primesieve
except ImportError as e:
    sys.exit("primesieve is required. See https://pypi.python.org/pypi/primesieve")

class RecursiveFactor:
    Top = itertools.repeat(0)
    def __init__(self, n):
        if isinstance(n, RecursiveFactor):
            if n.factors == RecursiveFactor.Top:
                self.factors = RecursiveFactor.Top
            else:
                self.factors = [RecursiveFactor(factor) for factor in n.factors]
        elif isinstance(n, int):
            if n == 0:
                self.factors = RecursiveFactor.Top
            else:
                factors = []
                i = 2
                print("factoring {0}".format(n))
                while i * i <= n:
                    while n % i == 0:
                        n = n // i
                        factors.append(i)
                    i = i + 1
                if n != 1: factors.append(n)
                self.factors = [RecursiveFactor(primesieve.count_primes(factor)) for factor in factors]
        else:
            self.factors = [RecursiveFactor(factor) for factor in n]
        if self.factors != RecursiveFactor.Top:
            self.factors.sort()

    def reduce(self, binary, unary, one, zero = None, horiz_combo = False, vert_combo = False):
        ''' binary expected to take sum and nextFactor
            unary expected to take factor (or (nextFactor, times) if horiz_combo)
                                or factor and depth if vert_combo)
            if binary = RF(a*b), you can expect sum < nextFactor
                 using ordinal (epsilon naught) ordering:
                                  (1,2,4,8,...,3,6,12...,9,...,27,...
                                   7,14,28,...,21,42,...,63,...
                                   19, ...
                                   ...
                                   5, ... 13, ... 37, ..., ..., 23, ...
                                   17, ..., 67, ...
                                   11, ......., 0)
            DOES NOT RECURSE - ADD RECURSION IN UNARY
        '''
        if self.factors == RecursiveFactor.Top:
            if zero is None:
                uninput = (0,...) if horiz_combo else 0
                return unary(uninput,...) if vert_combo else unary(uninput)
            else: return zero
        it = iter(sorted(Counter(self.factors).items() if horiz_combo else self.factors))
        out = one
        for factor in it:
            if vert_combo:
                depth = 0
                while(factor.is_prime()):
                    depth += 1
                    factor = factor.factors[0]
                out = binary(out, unary(factor, depth))
            else: out = binary(out, unary(factor))
        return out

    def stringify(self, left = '<', right = '>', middle = '', one = '', depth = None, zero = 'T'):
        ''' this.stringify([left],[right],[middle], [one], [depth])
            blearugh '''
        if depth is None:
            return self.reduce(lambda a, b: a+middle+b if a!=one else b,
                               lambda a: left
                               + a.stringify(left, right, middle, one = one, depth = depth, zero = zero)
                               + right,
                               one,
                               zero = zero)
        else:
            return self.reduce(lambda a, b: a+middle+b if a!= one else b,
                               lambda a, de:
                                   depth(de) if int(a)==1 else
                                   left(de)
                                   + a.stringify(left, right, middle, one = one, depth = depth, zero = zero)
                                   + right(de),
                               one,
                               zero = zero,
                               vert_combo = True)

    def factor_list(self):
        if self.factors == RecursiveFactor.Top:
            return [(RecursiveFactor(0), ...)]
        print(str(self.factors))
        print(sorted(Counter(self.factors).items()))
        return [(RecursiveFactor(1),...)] + sorted(Counter(self.factors).items())

    def __eq__(self,other):
        return self.factors == RecursiveFactor(other).factors

    def __hash__(self):
        return hash(self.stringify())

    def __ne__(self,other):
        other = RecursiveFactor(other)
        return self.factors != other.factors

    def __lt__(self,other):
        other = RecursiveFactor(other)
        if self.factors == RecursiveFactor.Top:
            return False
        if other.factors == RecursiveFactor.Top:
            return True
        if other.factors == []:
            return False
        if self.factors == []:
            return True
        max = min(len(self.factors), len(other.factors))
        for i in range(max):
            if self.factors[-i] != other.factors[-i]:
                return self.factors[-i]<other.factors[-i]
        return False

    def __ge__(self,other):
        other = RecursiveFactor(other)
        return not self < other

    def __repr__(self):
        return 'RecursiveFactor: [' + self.stringify(left = '[', right = ']', middle = ', ') + ']'

    def is_symmetrical(self):
        if self.factors == RecursiveFactor.Top:
            return self
        elif len(self.factors)==1:
            return self.factors[0].is_symmetrical()
        else:
            found_odd = False
            for factor, times in Counter(self.factors).items():
                if times % 2 == 1:
                    if found_odd:
                        return False
                    if not factor.is_symmetrical():
                        return False
                    found_odd = True
            return True

    def is_prime(self):
        if self.factors == RecursiveFactor.Top:
            return False
        else:
            return len(self.factors)==1

    def __int__(self):
        if self.factors == RecursiveFactor.Top: return 0
        return self.reduce(lambda x,y: x * y, lambda x: primesieve.nth_prime(x), 1)

def get_ordinal(n, latex=True):
    n = RecursiveFactor(n)
    def unary(factory):
        factor = factory[0]
        if int(factor) == 1:
            return str(factory[1])
        times = factory[1]
        if times == 1: times = ''
        omega = r'\omega' if latex else 'ω'
        if int(factor) == 2:
            return omega + str(times)
        else:
            ordinal = get_ordinal(factor, latex=latex)
            if latex:
                return omega + '^{' + ordinal + '}' + str(times)
            else:
                if '+' in ordinal or times != '':
                    return omega + '^(' + ordinal + ')' + str(times)
                else:
                    return omega + '^' + ordinal
    return n.reduce(lambda x,y:
                    y if x == '0' else y + '+' + x, unary, '0', zero = r'\epsilon_0' if latex else 'ε₀', horiz_combo = True)

def full_ordinal(n):
    return r'\mathfrak{p}(' + get_ordinal(n) + ')'

def get_info(n):
    info = {}
    n = RecursiveFactor(n)
    brackets = n.stringify()
    info["bracket_notation"] = brackets
    abc = brackets.replace('<>', 'a')
    letter = 'a'
    while letter in abc:
        abc = abc.replace('<'+letter+'>', chr(ord(letter)+1))
        letter = chr(ord(letter)+1)
    info["abc_notation"] = abc
    info["p_notation"] = n.stringify(lambda x: 'pdfghijklmnopqtuvwxyz'[x] + '<',
                                     lambda x: '>',
                                     one = 's',
                                     depth= lambda x: 'pdfghijklmnopqtuvwxyz'[x])

    digits_list = []
    last_bracket = ''
    for char in brackets:
        if char == last_bracket:
            digits_list[-1] += 1
        else:
            digits_list.append(1)
        last_bracket = char
    digits = ''.join(map(str,digits_list))
    info["digit_notation"] = digits

    depth = []
    current_depth = 0
    max_depth = 0
    add = True
    for digit in digits_list[:-1]:
        if add:
            current_depth += digit
        else:
            current_depth -= digit
        depth.append('*' * current_depth)
        add = not add
        if current_depth > max_depth:
            max_depth = current_depth
    info["depth_notation"] = '\n'.join(''.join(row) for row in itertools.zip_longest(*depth, fillvalue=' '))
    ordinal_escaped = urllib.parse.quote(full_ordinal(n))
    info["ordinal"] = '[img]http://latex.codecogs.com/gif.latex?' + ordinal_escaped + '[/img]'

    info["is_prime"] = len(n.factor_list()) == 2 and n.factor_list()[1] == 1
    info["is_prime_power"] = len(n.factor_list()) <= 2
    info["is_symmetrical"] = n.is_symmetrical()
    info["is_alphabetical"] = not ('<' in abc)

    factors = n.factor_list()
    factors = [int(factor) for factor in factors]
    factors.sort()

    info["length"] = len(brackets)
    info["reversals"]= len(digits_list) - 1
    info["max_depth"] = max_depth
    info["factors"] = len(factors)-1
    info["smoothness"] = int(factors[-1][0])
    info["necessary_brackets"] = abc.count('<')*2
    return info

def info_string(number):
    info = get_info(number)
    return '\n'.join([
        str(int(number)),
        info["bracket_notation"],
        info["abc_notation"],
        info["p_notation"],
        info["digit_notation"],
        '[code]',
        info["depth_notation"],
        '[/code]',
        info["ordinal"],
        '',
        'Prime: {0}'.format('Yes' if info["is_prime"] else 'No'),
        'Prime Power: {0}'.format('Yes' if info["is_prime_power"] else 'No'),
        'Symmetrical: {0}'.format('Yes' if info["is_symmetrical"] else 'No'),
        'Alphabetical: {0}'.format('Yes' if info["is_alphabetical"] else 'No'),
        '',
        'Length: {0}'.format(info["length"]),
        'Reversals: {0}'.format(info["reversals"]),
        'Max Depth: {0}'.format(info["max_depth"]),
        'Factors: {0}'.format(info["factors"]),
        'Smoothness: {0}'.format(info["smoothness"]),
        'Necessary Brackets: {0}'.format(info["necessary_brackets"])
    ])
if __name__ == '__main__':
    n = int(sys.argv[1] if len(sys.argv) > 1 else 1)
    while n != 0:
        print(info_string(n))
        print("-----------------------------------------")
        try: n = int(input())
        except:
            n = 0