mycalc.py

# This is mycalc.py for Python 32


"""
often used functions:
time_stamp
numberRounding(n, sigdigits)
round_to_n(x, n),
secsToHMS(seconds),
factorsOfInteger(n), intSpell(n),
randIntOfRandLength(minLength, maxLength),
int_digits(n),
int_commas(n)
isPrime(n),
findDayOfWeek(1937, 4, 24)
croots(c, n),
decPow(n, power, precision=4)
is_dec_repeating(denominator)
decDiv(num, denom, precision=100)
find_repeat_seq(num, denom, precision=1000)
unique()
"""
import gmpy
import gmpy2
import random
import datetime
from math import log10
from time import time, clock

def is_hashable(object):
    try:
        hash(object)
    except TypeError:
        return False
    return True

def hex2dec(hex_n):
    """
    Given a hex integer in the 0x... form, returns the equivalent base-10 integer

    >>> hex2dec(0xf)
    15
    >>> hex2dec(0x10)
    16
    >>> hex2dec(0xA)
    10
    >>> hex2dec(0xff)
    255
    >>>
    """
    return int(hex_n)

def dec2hex(dec_n):
    """
    Given a base-10 int, return the equivalent hex integer as a string.

    >>> dec2hex(255)
    '0xff'
    >>> dec2hex(256)
    '0x100'
    >>>
    """
    return hex(dec_n)

def convertPath(path):
    r"""
    Given a path with backslashes, return that path with forward slashes.

    By Steven D'Aprano  07/31/2011 on Tutor list
    >>> path = r'C:\Users\Dick\Desktop\Documents\Notes\College Notes.rtf'
    >>> convertPath(path)
    'C:/Users/Dick/Desktop/Documents/Notes/College Notes.rtf'
    """
    import os.path
    separator = os.path.sep
    if separator != '/':
        path = path.replace(os.path.sep, '/')
    return path

def d(x, precision=50):
    """
    Given x is either an int of any length or a float with 16 or fewer digits,
    return decimal.Decimal(str(x)).

    This function appears in a simpler form in the 2nd ed. of
    _Python In a Nutshell_, p.373
    #>>> from decimal import Decimal as D
    #>>> decimal.getcontext().prec = 50
    #>>> D('234')**D('.555555555555555')
    #Decimal('20.712428960882622698237158800584555118350558990840')
    >>> d(234)**d(.555555555555555)
    Decimal('20.712428960882622698237158800584555118350558990840')
    >>> d(234, 25)**d(.555555555555555)
    Decimal('20.712428960882622698237158800584555118350558990840')
    >>> d(234)**d(.555555555555555, 25)
    Decimal('20.71242896088262269823716')
    >>> d(234)**d(.55555555555555557)
    float beginning 0.555 has too many digits.
    Maximum to maintain accuracy is 16
    (<http://www.wolframalpha.com/input/?i=234**.555555555555555>
    gives 20.71242896088262269823715880058455511835055899083967...)
    (for WA, us 927)
    """
    import decimal
    from decimal import getcontext
    getcontext().prec = precision
    import sys
    from decimal import Decimal as D

    if isinstance(x, float):
        decimal.getcontext().prec = 16
        if D(str(x)) != +D(str(x)):
            print('float beginning', str(x)[:5], 'has too many digits.')
            print('Maximum to maintain accuracy is 16 digits')
            sys.exit()
        decimal.getcontext().prec = precision
    elif isinstance(x, int):
        decimal.getcontext().prec = precision
    else:
        raise TypeError("WTF you didn't pass me an int or a float")
    return D(str(x))

def goldbach_pairs(n):
    """
    Given an even int > 3, returns the list of unique unordered Goldbach pairs, p1 and p2 such that p1 and p2 are prime, p1 + p2 = n, and p1 !> p2.

    Thus for n = 14, the list will contain either (3, 11) or (11, 3), but not both (11, 3) and (3, 11), because (3, 11) and (11, 3) are considered to be the same pair.
    >>> goldbach_pairs(50)
    [(3, 47), (7, 43), (13, 37), (19, 31)]
    Error: n must be even and >= 6
    >>> goldbach_pairs(51)
    None
    >>> goldbach_pairs(4)
    [(2, 2)]
    """
    from mycalc import isPrime
    if n == 4:
        return [(2, 2)]
    if n % 2 or n < 6:
        print("Error: n must be even and >= 6")
        return ''
    x = 3
    y = n - x
    pairs_count = 0
    pairs_list = []

    while x <= n // 2:
        if isPrime(x) and isPrime(y):
            pairs_list.append((x, y))
            pairs_count += 1
        x += 2
        y -= 2

    return pairs_list

def no_zero(n):
    """
    Given a float with abcissa of 0, returns an int. Otherwise returns the float.

    >>> no_zero(234.0)
    234
    >>> no_zero(-56.12)
    -56.12
    no_zero(3546)
    >>> 3456
    """
    if n == int(n):
        return int(n)
    else:
        return n


def remove_all_x(x, list_):
    """
    return list_ with all x removed

    >>> lst = ['asd', 'f', 'qwerty', 234, 'qwerty']
    >>> remove_all_x('qwerty', lst)
    ['asd', 'f', 234]
    >>>
    """
    return [e for e in list_ if e != x]

def is_permutation(a, b):
    """
    Given 2 sequences of same type, or given 2 integers, return True if the 2nd is a permutation of the 1st.


    >>> is_permutation('Moores', 'Moorse')
    True
    >>> is_permutation(189, 189)
    True
    >>> is_permutation(189, '189')
    the two are of different types
    >>> is_permutation(189, 1899)
    the two have different lengths: 3 and 4
    >>> is_permutation(['p','q',23], ['q',23,'p'])
    True
    >>> is_permutation(['p','q', 23], ['p', 24, 'q'])
    False
    >>> is_permutation(['p','q',23], ('p', 23, 'q'))
    the two are of different types
    >>> is_permutation(5.6, 5.6)
    the two are neither ints nor sequences
    >>> is_permutation('5.6', '6.5')
    True
    >>>
    """
    if type(a) != type(b):
        print('the two are of different types', type(a), 'and', type(b))
        return False
    elif not isinstance(a, (str, list, tuple, int)):
        print("the two are of the same type", type(a), "which is neither int nor sequence")
        return False
    else:
        for element in a:
            if not a.count(element) == b.count(element):
                return False
    return True

def int_digits_num(n):
    """
    Given an integer, (positive, 0, or negative), or an expression that
    evaluates to an integer, returns the number of digits in the integer.
    """
    from math import log10
    if not isinstance(n, int):
        raise TypeError("WTF you didn't pass me an int")
    if n == 0:
        return 1
    n = abs(n)
    return int(log10(n)) + 1

def harmonic_mean(Hlist):
    """
    return harmonic mean of positive numbers in Hlist

    ref: http://mathworld.wolfram.com/HarmonicMean.html
    test: hm of 1,2,3,4,5,6,7 is 980/363 or 2.6997245179063363
    """
    import math
    if any(x <= 0 for x in Hlist):
        raise ValueError("All items in Hlist must be positive numbers.")
    sum_ = math.fsum([1/x for x in Hlist])
    n = len(Hlist)
    invH = (1/n)*sum_
    H = 1/invH
    return H

def geometric_mean(Glist):
    """
    return geometric mean of positive numbers in Glist

    ref: http://mathworld.wolfram.com/GeometricMean.html
    test: G of 1,5,10 is (1*5*10)**(1/3), or 3.6840314986403864
    """
    if any(x <= 0 for x in Glist):
        raise ValueError("All items in Glist must be positive numbers.")
    product = 1
    for x in Glist:
        product *= x
    n = len(Glist)
    G = product ** (1/n)
    return G

def sound_Exit(n=1):
    import winsound
    for x in range(n):
        winsound.PlaySound("SystemExit", winsound.SND_ALIAS)

def is_squarefree(n):
    """
    Return True if integer n is squarefree; False if not

    A number is said to be squarefree if its prime decomposition contains no repeated factors.
    """
    factors_of_n = factorsOfInteger(n)
    for x in factors_of_n:
        if factors_of_n.count(x) > 1:
            return False
    return True

def is_squareful(n):
    """
    Return True if integer n is squareful; False if not

    A number is said to be squareful if its prime decomposition
    contains at least one repeated factor. (12 = 2*2*3)
    """
    factors_of_n = factorsOfInteger(n)
    for x in factors_of_n:
        if factors_of_n.count(x) > 1:
            return True
    return False

def proper_divisors(n):
    """
    Return a list of the proper divisors of positive integer n
    """
    limit = int(n/2)
    return [x for x in range(1,limit+1) if n % x == 0]

def proper_divisors_sum(n):
    """
    Return the sum of a list of the proper divisors of positive integer n
    """
    sum_ = 0
    limit = int(n/2)
    for x in range(1, limit+1):
        if n % x == 0:
            sum_ += x
    return sum_

def nth_substring(string, substring, n):
    """
    Return the index of the first character of the nth instance of substring in string.

    If no nth instance, return -1
    """
    max_n = string.count(substring)
    if n > max_n:
        return -1
    idx = 0
    original_string = string
    len_substring = len(substring)
    count = 0
    idx_sum = 0
    while True:
        count += 1
        idx = string[idx_sum:].find(substring)
        idx += len_substring
        idx_sum += idx
        if count >= n:
            idx = idx_sum-len_substring
            return idx

def time_stamp():
    return datetime.datetime.now().strftime("%H:%M:%S")

def sci_notation_to_non_sci_notation(sci_not):
    """
    Given a number in scientific notation as a string, return the number.

    E.g., 1.234e3 -> 1234; 1.234+E6 -> 1234000; 1+e2 -> 100; 1.234e2 -> 123.4
    """
    s = str(sci_not)
    # remove '.'
    s = s.replace('.', '')
    #remove '+'
    s = s.replace('+', '')
    s = s.replace('E', 'e')
    if 'e' not in s:
        print(sci_not, "is not in scientific notation form")
        return
    idx_e = s.find('e')
    s_before_e = s[:idx_e]
    exponent = int(s[idx_e+1:])
    len_s_before_e = len(s_before_e)
    if len_s_before_e <= exponent+1:
        return s_before_e + '0'*(exponent - len_s_before_e + 1)
    elif len_s_before_e > exponent+1:
        return s_before_e[:exponent+1] + '.' + s_before_e[exponent+1:]

def int_digits(n):
    """
    return number of digits of an integer
    """
    return int(log10(n) + 1)

def find_prime_before_n(n):
    for x in range(n, 2, -1):
        if isPrime(x):
            return x

def prime_to_biggest_prime(p):
    """
    Given a prime, return a much bigger one.

    For every prime p there there is at least one pair of positive integers a and b such
    that p = a + b, and such that 2**a*3**b is either 1 greater than or 1 less than another
    (much larger) prime. This function returns the pair that produces the greatest value
    of 2**a*3**b, and the greatest prime that p determines.
    """
    for b in range(p-1,0,-1):
        flag = 0
        a = p - b
        one_off_big_p = 2**a*3**b
        for x in [one_off_big_p - 1, one_off_big_p + 1]:
            if isPrime(x):
                return x, a, b

def tech_babble():  #TODO  edit so use random.choice(), delete import statement, and put import random at top.
    """
    Prints a 3 word meaningless phrase; each word a real tech term.

    I have a script, tech_babble2.py, that outputs the same phrases. Use AW tb.
    """
    from random import choice
    list1 = ["Integrated", "Pseudo", "Dynamic", "Potential", "Diurnal", "Stratosphere", "Cumulative", "Absolute", "Kinematic", "Conditional"]

    list2 = ["Thermal", "Vorticity", "Solenoidal", "Molecular", "Orthographic", "Turbulent", "Solar", "Inertial", "Rotational", "Vapor"]

    list3 = ["Equilibrium", "Transfer", "Stratification", "Balance", "Field", "Correlation", "Discontinuity", "Advection", "Trajectory", "Function"]

    print("CAUTION:", choice(list1), choice(list2), choice(list3))

def sets_intersection(sets_list):
    """
    Given a list of sets, return their intersection.
    """
    sets_list_length = len(sets_list)
    if sets_list[0] == set():
        return set()
    intersection_of_sets = sets_list[0]
    for i in range(1, sets_list_length):
        if sets_list[0] == set():
            return set()
        intersection_of_sets &= sets_list[i]
    return intersection_of_sets

def gcd(*args):
    """http://code.activestate.com/recipes/577512/"""
    if len(args) == 1:
        return args[0]

    L = list(args)

    while len(L) > 1:
        a = L[len(L) - 2]
        b = L[len(L) - 1]
        L = L[:len(L) - 2]

        while a:
            a, b = b%a, a

        L.append(b)

    return abs(b)

def gcd_all2(int_list):
    """
    Return gcd of list of integers
    """
    from fractions import gcd
    int_list = [abs(n) for n in int_list]
    # when int_list contains only zeros
    if max(int_list) == min(int_list) == 0:
        return 0
    divisor = gcd(int_list[0],int_list[1])
    int_list_length = len(int_list)
    for i in range(1, int_list_length-2):
        divisor = gcd(divisor, int_list[i+2])
    return divisor

def gcd_of_ints(*args): # wrong (for 30,45,55 returns 15)
    """
    Returns gcd of any number of positive integers
    """
    import fractions
    from mycalc import int_to_ordinal
    flag = False
    args = list(args)

    try:
        for i, x in enumerate(args):
            if not x > 0 or not isinstance(x, int):
                print('argument', x, 'is not a positive integer')
                flag = True
        if flag:
            return None

    except TypeError:
        print('The', int_to_ordinal(i+1), 'argument is not a positive integer')
        return None

    if len(args) == 1:
        args.append(args[0])
    gcd_ = fractions.gcd(args[0],args[1])
    for i in range(2, len(args)-1):
        gcd_ = fractions.gcd(gcd_, args[i])
    return gcd_

def int_commas(n):
    """
    inserts commas into integers and returns the string

    E.g. -12345678 -> -12,345,789
    """
    return format(n, ',d')

def next_n_primes(m, n):  # TODO permits negative primes; faster than using my isPrime in nextNPrimes(), etc.?
    """
    Return list of first n primes > m. Even if m is prime, it won't be in the list.
    """
    count = 0
    primes = []
    p = m
    while True:
        p = int(gmpy2.next_prime(p))
        primes.append(p)
        count += 1
        if count >= n:
            return primes

def percent_error_from_standard(standard, x):
    return 100*(abs(standard - x))/standard

def metric2BMI(kg, cm):
    """
    Given weight in kg and height in cm, return BMI
    """
    BMI = kg/(cm/100)**2
    BMI = round(BMI, 1)
    if BMI < 18.5:
        category = "Underweight"
    elif BMI < 25:
        category = "Normal"
    elif BMI < 30:
        category = "Overweight"
    else:
        category = "Obese"
    print()
    print("Your BMI is", BMI, "which is", category)
    print()
    print("BMI categories:")
    print("Below 18.5 Underweight")
    print("18.5 - 24.9 Normal")
    print("25 - 29.9 Overweight")
    print("30 and above Obese")
    kg_max = 24.9*(cm/100)**2
    kg_min = 18.5*(cm/100)**2
    print()
    print("Your Normal range in kg is from", round(kg_min, 1), "to", round(kg_max, 1))

def english2BMI(pounds, inches):
    """
    Given weight in pounds and height in inches, return BMI
    """
    BMI = pounds*703/inches**2
    BMI = round(BMI, 1)
    if BMI < 18.5:
        category = "Underweight"
    elif BMI < 25:
        category = "Normal"
    elif BMI < 30:
        category = "Overweight"
    else:
        category = "Obese"
    print()
    print("Your BMI is", BMI, "which is", category)
    print()
    print("BMI categories:")
    print("Below 18.5 Underweight")
    print("18.5 - 24.9 Normal")
    print("25 - 29.9 Overweight")
    print("30 and above Obese")
    pounds_max = (24.9*inches**2)/703
    pounds_min = (18.5*inches**2)/703
    print()
    print("Your Normal range in pounds is from", round(pounds_min, 1), "to", round(pounds_max, 1))

def pi_digits_gmpy(n):
    """
    Returns pi as a str to n digits; n must be >= 10

    >>> pi_digits_gmpy(10)
    '3.141592653' (the 10 digits includes the initial '3'
    """
    def special_rounding(f):
        """
        Given a long float as a str, return it rounded off by one digit
        """
        f_last10 = f[-10:]
        f_last10_over_1000000000 = int(f_last10)/10000000000
        x = round(f_last10_over_1000000000,9)
        if len(str(x)) < 11:
            zeros = 11 - len(str(x))
            x = str(x) + zeros*'0'
        else:
            x = str(x)
        rounded_f = f[:-10] + x[2:]
        return rounded_f
    if n < 10:
        print("n must be >= 10")
        return
    multiplier = 4
    bits = 4*n
    gmpy2.context().precision = bits
    rough_pie = gmpy2.const_pi(bits)
    rough_pie = str(rough_pie)
    pie = rough_pie[:n+2]
    rounded_pie = special_rounding(pie)
    return rounded_pie

def seconds_elapsed(t, digits=0):
    time_ = clock() - t
    if digits == 0:
        return int(round(time_, digits))
    else:
        return round(time_, digits)

def minutes_elapsed(t, digits=0):
    time_ = clock() - t
    minutes = time_/60
    if digits == 0:
        return int(round(minutes, digits))
    else:
        return round(minutes, digits)

def tim(t, digits, p=1):
    time_  = clock() - t
    if digits:
        seconds = round(time_, digits)
        minutes = round(time_/60, digits)
        hours = round(time_/3600, digits)
    else:
        seconds = int(round(time_, digits))
        minutes = int(round(time_/60, digits))
        hours = int(round(time_/3600, digits))
    if p and seconds > 3600:
        print("time was", hours, "hours  or ", secsToHMS(time_))
    elif p and seconds > 60:
        print("time was", minutes, "minutes  or ", secsToHMS(time_))
    elif p:
        print("time was", seconds, "seconds  or ", secsToHMS(time_))
    else:
        return secsToHMS(time_)


def catAge2HumanAge(catAge):
    """
    Given cat age, return equivalent human age

    See http://tinyurl.com/ylrjlp4
    """
    return 4 * (catAge - 1) + 16

def humanAge2CatAge(humanAge):
    """
    Given human age, return equivalent cat age
    """
    return (humanAge - 16) / 4 + 1

def int2int_length(n, dpi = 10):
    """
    Given integer (large) integer n,
    returns length of n in miles

    For my laptop monitor, there are
    about 10 digits per inch (dpi = 10)
    """
    digits = int_digits(n)
    miles = digits/dpi/12/5280
    return miles

def num_digits2int_length(num_digits, dpi = 10):
    """
    Given number of digits of (large) integer n,
    returns length of n in miles

    For my laptop monitor, there are
    about 10 digits per inch (dpi = 10)
    """
    #digits = int_digits(n)
    miles = num_digits/dpi/12/5280
    return miles

def decDiv(num, denom, precision=100):
    from decimal import getcontext, Decimal as D
    getcontext().prec = precision
    return D(str(num))/D(str(denom))

#TODO bugs with denoms: 96, 192, 384, 448
# note that 192 and 384 are multiples of 96
#def find_repeat_seq(num, denom, precision=1000):
    #"""
    #Given num and denom of fraction, returns repeating sequence if there is one.

    #Shows at least 2 repetitions of sequence. Also its length.
    #If no such sequence, then fraction's decimals expansion is exact. E.g., 0.375. Returns this.
    #"""
    #num, denom = reduceFraction(num, denom)
    ## long seqs: 3/911->(455); 37/947->(473); 547/1949->(1948)
    #precision = 2*denom
    #if precision < 50:
        #precision = 50
    #if denom > 50000:
        #print("reduced denom is", denom)
        #print("This is too large: calculation will take too long")
        #return ""
    ## dec, the decimal expansion
    #dec = decDiv(num, denom, precision+3)
    ## index of decimal point
    #dec_pt_idx = str(dec).find('.')
    ## the mantissa of the decimal expansion, as a string
    #str_mantissa = str(dec)[dec_pt_idx+1:-1]

    #s = str_mantissa

    ## These mantissas are short, and exact. Therefore there is no repeating sequence.
    ## E.g., for 3/8, mantissa is exactly 375. For 79/128, exactly 6171875
    #if not is_dec_repeating(num, denom):
        #return num/denom
    #else:
        #def format_return():
            #if num > denom:
                #pre = str(num//denom) + '.'
            #else:
                #pre = '0.'
            #s_length = 2*len(ss)+5
            #if s_length < 50 and len(ss) > 1:
                #s_length = 50
            #s1 = s[:s_length] + '...'
            #ss1 = '(' + ss + ')'
            #s2 = pre + s1.replace(ss,ss1)
            #return s2

        #for b in range(precision):
            ## (re)initializing ss, which will be a sub-string of s
            #ss = ""
            #for i in range(precision):
                ## Note that s[b+i] isn't actually appended to ss until last line of this loop.
                ## ss2 is the sequence of len(ss) that immediately follows ss.
                #ss2 = s[b+i:b+i+len(ss)]
                ## If the next digit in s after ss is also in ss, then ss is a candidate for the repeating seq.
                ## If ss == ss2, then ss is a repeating sequence.
                ## To test if ss is a single digit, see if all digits of s after ss are equal to ss.
                ## it is if after it all the digits in mantissa are identical to it.
                #if (s[b+i] in ss) and ss == ss2 and (s[b:].count(s[b+i]) == len(s[b:])):
                    ##print("The repeating single-digit sequence is", ss)
                    ##print("The repetition begins at index", b, "of the mantissa")
                    ##return ss, b, len(ss)
                    #return format_return(), len(ss)
                ## to test if repeating sequence has more than one digit
                #elif (s[b+i] in ss) and ss == ss2 and len(ss) > 1:
                    ###print("The repeating sequence is", ss)
                    ###print("The initial sequence begins at index", b, "of mantissa and has", len(ss), "digits")
                    ## Note that len(ss) == i
                    #return format_return(), len(ss)
                #else:
                    #ss += s[b+i]

def find_repeat_seq(num, denom, precision=1000):
    """
    Given num and denom of fraction, returns repeating sequence if there is one.

    Shows at least 2 repetitions of sequence. Also its length.
    If no such sequence, then fraction's decimal expansion is exact. E.g., 3,8 returns 0.375.
    """
    num, denom = reduceFraction(num, denom)
    f = str(num/denom)
    if f[-2:] == ".0":
        num = f[:-2]
        print(num,"/1 = ", num, ".0", sep="", end="")
        return None
    # long seqs: 3/911->(455); 37/947->(473); 547/1949->(1948)
    precision = 2*denom
    if precision < 50:
        precision = 50
    if denom > 50000:
        print("reduced denom is", denom)
        print("This is too large: calculation will take too long")
        return ""
    # dec, the decimal expansion
    dec = decDiv(num, denom, precision+3)
    # index of decimal point
    dec_pt_idx = str(dec).find('.')
    # the mantissa of the decimal expansion, as a string
    str_mantissa = str(dec)[dec_pt_idx+1:-1]

    s = str_mantissa

    # These mantissas are short, and exact. Therefore there is no repeating sequence.
    # E.g., for 3/8, mantissa is exactly 375. For 79/128, exactly 6171875
    if not is_dec_repeating(num, denom):
        return num/denom
    else:
        def format_return():
            if num > denom:
                pre = str(num//denom) + '.'
            else:
                pre = '0.'
            s_length = 2*len(ss)+5
            if s_length < 50 and len(ss) > 1:
                s_length = 50
            s1 = s[:s_length] + '...'
            ss1 = '(' + ss + ')'
            s2 = pre + s1.replace(ss,ss1)
            return s2

        for b in range(precision):
            # (re)initializing ss, which will be a sub-string of s
            ss = ""
            for i in range(precision):
                # Note that s[b+i] isn't actually appended to ss until last line of this loop.
                # ss2 is the sequence of len(ss) that immediately follows ss.
                ss2 = s[b+i:b+i+len(ss)]
                # If the next digit in s after ss is also in ss, then ss is a candidate for the repeating seq.
                # If ss == ss2, then ss is a repeating sequence.
                # To test if ss is a single digit, see if all digits of s after ss are equal to ss.
                # it is if after it all the digits in mantissa are identical to it.
                if (s[b+i] in ss) and ss == ss2 and (s[b:].count(s[b+i]) == len(s[b:])):
                    #print("The repeating single-digit sequence is", ss)
                    #print("The repetition begins at index", b, "of the mantissa")
                    #return ss, b, len(ss)
                    return format_return(), len(ss)
                # to test if repeating sequence has more than one digit
                elif (s[b+i] in ss) and ss == ss2 and len(ss) > 1:
                    ##print("The repeating sequence is", ss)
                    ##print("The initial sequence begins at index", b, "of mantissa and has", len(ss), "digits")
                    # Note that len(ss) == i
                    return format_return(), len(ss)
                else:
                    ss += s[b+i]

def find_repeat_seq2(fraction, precision=1000):
    """
    Given a fraction with denominator <= 50,000, returns repeating sequence if there is one.

    Shows at least 2 repetitions of sequence. Also its length.
    If no such sequence, then fraction's decimals expansion is exact. E.g., 0.375. Returns this.

    >>> find_repeat_seq2(121/331)
    121/331 = 0.36555891238670696 =
    ('0.(36555891238670694864048338368580060422960725075528700906344410876132930513595166163141993957703927492447129909)(36555891238670694864048338368580060422960725075528700906344410876132930513595166163141993957703927492447129909)36555...', 110)
    >>>
    >>> find_repeat_seq2(2/81)
    2/81 = 0.024691358024691357 =
    ('0.(024691358)(024691358)(024691358)(024691358)(024691358)02469...', 9)
    >>>
    >>> find_repeat_seq2(17/32)
    17/32 = 0.53125
    >>>
    """
    from decimal import getcontext, Decimal as D
    getcontext().prec = precision
    from fractions import Fraction
    f = str(fraction)
    if f[-2:] == ".0":
        num = f[:-2]
        print(num,"/1 = ", num, ".0", sep="", end="")
        return None
        #num = int(f[:-2])
        #denom = float(1.0)
        #print(num, denom)
    frac = Fraction(f).limit_denominator(1000000)
    frac = str(frac)
    num = int(frac.split("/")[0])
    denom = int(frac.split("/")[1])
    precision = 2*denom
    if precision < 50:
        precision = 50
    if denom > 50000:
        print("reduced denom is", denom)
        print("This is too large: calculation will take too long")
        return ""
    # dec, the decimal expansion
    dec = decDiv(num, denom, precision+3)
    # index of decimal point
    dec_pt_idx = str(dec).find('.')
    # the mantissa of the decimal expansion, as a string
    str_mantissa = str(dec)[dec_pt_idx+1:-1]

    s = str_mantissa

    # These mantissas are short, and exact. Therefore there is no repeating sequence.
    # E.g., for 3/8, mantissa is exactly 375. For 79/128, exactly 6171875
    #num = int(num)
    #denom = int(denom)
    if not is_dec_repeating(num, denom):
        print(num,"/",denom, " = ", num/denom, sep="", end="")
        return None
    else:
        def format_return():
            if num > denom:
                pre = str(num//denom) + '.'
            else:
                pre = '0.'
            s_length = 2*len(ss)+5
            if s_length < 50 and len(ss) > 1:
                s_length = 50
            s1 = s[:s_length] + '...'
            ss1 = '(' + ss + ')'
            s2 = pre + s1.replace(ss,ss1)
            return s2

        for b in range(precision):
            # (re)initializing ss, which will be a sub-string of s
            ss = ""
            for i in range(precision):
                # Note that s[b+i] isn't actually appended to ss until last line of this loop.
                # ss2 is the sequence of len(ss) that immediately follows ss.
                ss2 = s[b+i:b+i+len(ss)]
                # If the next digit in s after ss is also in ss, then ss is a candidate for the repeating seq.
                # If ss == ss2, then ss is a repeating sequence.
                # To test if ss is a single digit, see if all digits of s after ss are equal to ss.
                # it is if after it all the digits in mantissa are identical to it.
                if (s[b+i] in ss) and ss == ss2 and (s[b:].count(s[b+i]) == len(s[b:])):
                    #print("The repeating single-digit sequence is", ss)
                    #print("The repetition begins at index", b, "of the mantissa")
                    #return ss, b, len(ss)
                    print(num,"/",denom, " = ", num/denom, " =", sep="")
                    return format_return(), len(ss)
                # to test if repeating sequence has more than one digit
                elif (s[b+i] in ss) and ss == ss2 and len(ss) > 1:
                    ##print("The repeating sequence is", ss)
                    ##print("The initial sequence begins at index", b, "of mantissa and has", len(ss), "digits")
                    # Note that len(ss) == i
                    print(num,"/",denom, " = ", num/denom, " =", sep="")
                    return format_return(), len(ss)
                else:
                    ss += s[b+i]


def is_dec_repeating(num, denom):
    """
    Test denominator of fraction. Does it have a repeating decimal?

    First, reduce the fraction, if possible. 3/24 -> 1/8
    If the (new) denominator has a prime factor which is neither 2 nor 5,
    then the fraction will have a repeating decimal in its expansion.
    The importance of reduction is shown by the denom 24 = 2*2*2*3: 3/24 -> 3/8 (False);
    6/24 -> 1/4 (False); 2/12 -> 1/6 (True); 1/24 (True)
    """
    denom = reduceFraction(num, denom)[1]
    denom = abs(denom)
    factors = factorsOfInteger(denom)
    if factors.count(2) + factors.count(5) == len(factors):
        return False
    else:
        return True

def croots(c, n):
    """
    Return list of the n n'th roots of complex c.

    by Tim Peters
    """

    from math import sin, cos, atan2, pi
    arg = abs(c)**(1/n)
    theta = atan2(c.imag, c.real)
    result = []
    for i in range(n):
        theta2 = (theta + 2*pi*i)/n
        x = arg * cos(theta2)
        y = arg * sin(theta2)
        result.append(complex(x, y))
    return result


def prestrings2list(a_str):
    """
    Given a string of comma-separated words and phrases, or even passwords, return a list of them.
    """
    import re
    mult_space = re.compile(r'\s+')
    return [re.sub(mult_space, ' ', x).strip() for x in a_str.split(',')]

def float2Decimal(f):
    """
    Given a float, return the exact number stored in computer

    See http://docs.python.org/3.1/tutorial/floatingpoint.html#representation-error
    """
    from decimal import Decimal
    return Decimal.from_float(f)

def values_dupe_keys(d):
    """
    Return a list of values in a dict d that have more than one key each.
    The returned list will be of the form
    [[value1, [key1, key2, key3, ...]], [value2, [[key11, key12, key13, ...], ...]]]
    """
    ## This is by Kent Johnson. See thread at
    ## <http://thread.gmane.org/gmane.comp.python.tutor/49675/focus=49680>
    from collections import defaultdict
    rev = defaultdict(list)
    for k, v in d.items():
        rev[v].append(k)
    return [ [v, keys] for v, keys in rev.items() if len(keys) > 1 ]

def gcd2(a, b):
    """
    Given integers a, b, return their greatest common divisor.
    """
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

def gcd3(a, b, c):
    """
    Given integers a, b, c, return their greatest common divisor.
    """
    a, b, c = abs(a), abs(b), abs(c)
    d = gcd2(a, b)
    return gcd2(d, c)


def sin_deg(n):
    """
    Return sine of n, n in degrees
    """
    from math import sin, radians
    return sin(radians(n))

def asin_deg(a, c=1):
    """
    Given sides a and c of a right triangle,
    where c is the hypoteneuse,
    return angle A in degrees
    When a/c is known, e.g. is .345,
    use it alone: asin_deg(0.345)
    """
    from math import asin, degrees
    return degrees(asin(a/c))

def cos_deg(n):
    """
    Return cosine of n, n in degrees
    """
    from math import cos, radians
    return cos(radians(n))

def acos_deg(a, c=1):
    """
    Given sides b and c of a right triangle, where c is the hypoteneuse,
    return angle A in degrees. When b/c is known, e.g. is .655, use it alone: acos_deg(0.655)
    """
    from math import acos, degrees
    return degrees(acos(a/c))

def tan_deg(n):
    """
    Return tangent of n, n in degrees
    """
    from math import tan, radians
    return tan(radians(n))

def atan_deg(a, b=1):
    """
    Given sides b and a of a right triangle,
    where c is the hypoteneuse,
    return angle A in degrees
    When a/c is known, e.g. is 0.821,
    use it alone: atan_deg(0.821)
    """
    from math import atan, degrees
    return degrees(atan(a/b))

def foo():
    print("FOO on YO")

def remove_prompt(s):  #TODO
    """
    Print s with shell prompt's '>>> ' removed.
    Prepare an s such as this:
    """

    from string import replace
    s = s.replace(">>> ",'')
    print(s)


def sci_notation(n, sig_digits=30): #TODO
    """
    Return n in scientific notation form to sig_digits significant digits.
    If n is in float form, must be entered ether in quotes or as an mpf.
    If n is an integer, enter it as is.
    n must be a positive number.
    Setting sig_digits to 0 will set it to 1000.
    """
    from mpmath import mpf, mp, log
    precision = sig_digits
    if precision == 0:
        precision = 1000
    mp.dps = precision
    n = mpf(n)
    assert n > 0
    if n > 1:
        divisor = mpf(10)**int(log(n,10))
        return "%se+%03d" % (n/divisor, int(log(n,10)))
    else:
        divisor = mpf(10)**((int(log(n,10)))-1)
        return "%se%04d" % (n/divisor, (int(log(n,10)))-1)


def find_indexes_all_x_in_list(x, alist):
    """
    Return list of indexes of all x in a list.
    If no x in list, return []
    """
    n = alist.count(x)
    if n == 0:
        return []
    i = 0
    idx_list = []
    for j in range(n):
        idx = alist.index(x,i)
        idx_list.append(idx)
        i = idx + 1
    return idx_list

def sort_tuple_list_by_2nd_elements(alist):
    """
    Return a list of 2-element tuples, with the list
    sorted by the 2nd element of the tuples.
    """
    alist_tup_elements_reversed = [ (x[1], x[0]) for x in alist ]
    alist_tup_elements_reversed.sort()
    alist_tup_elements_reversed_and_reversed_again = [
        (x[1], x[0]) for x in alist_tup_elements_reversed ]
    return alist_tup_elements_reversed_and_reversed_again

def strip_punctuation(astr):
    from string import ascii_letters, digits
    return ''.join(c for c in astr if c in ascii_letters + digits + ' ')

def delete_underscores(astr):
    """
    Given a string with underscores, returns it without.
    E.g. "_cat_" --> "cat"
    """
    from mycalc import replace2
    return replace2(astr, r'_', '', 0, 0)

##def text(filename):
##    """
##    Return text of E:\PythonWork\Nutshell\\<filename> as a string
##    """
##    # see http://docs.python.org/lib/bltin-file-objects.html, close()
##
##    path = 'E:\PythonWork\Nutshell\\' + filename
##    with open(path) as file:
##        return file.read()

##def cap_words(astr):
##    """
##    Return a list of non-trivial capitalized words in a string/text.
##
##    The absence of trivial words in the list depends on both the string/text
##    and the list of trivial words in E:\PythonWork\Nutshell\words.txt .
##    Thus the output of cap_words() can be used to contribute to words.txt .
##    """
##    import re
##    from mycalc import unique, make_first_words
##    first_words = make_first_words() # make_first_words() is in mycalc.py
##    first_words.sort()
##    regex = r"[A-Za-z0-9]+(?:['-][A-Za-z0-9]+)*'?"
##    p = re.compile(regex)
##    cap_w = p.findall(astr)
##    lst = []
##    for word in first_words:
##        while word in cap_w:
##            cap_w.remove(word)
##        lst.append(word)
##    cap_w.sort()
##    u = unique(cap_w)
##    return u

##def make_first_words():
##    """
##    Make the list, "first_words", for use with various scripts
##    """
##    file = open('E:\PythonWork\Nutshell\\words.txt', 'r')
##    first_words = []
##    for line in file.readlines():
##        first_words.append(line[:-1])
##    file.close()
##    return first_words

def word_count(astr, hit_list=0):
    """
    Return a count of words in a string/text, and  optionally, a list of the words.
    """
    import re

    regex = r"[A-Za-z0-9]+(?:['-][A-Za-z0-9]+)*'?"
    p = re.compile(regex)
    f = p.findall(astr)
    if hit_list:
        lst = []
        for i, e in enumerate(f):
            lst.append(f[i])
        lst.sort()
        f = lst
        return f, len(f)
    return len(f)

def char_count(astr):
    """
    Return a count of visible characters in a string/text.
    """
    import re
    regex = r'[^\s]'
    p = re.compile(regex)
    f = p.findall(astr)
    return len(f)

def replace2(astr, regex, repl, I=0, count=0):
    """
    Replace all regex matches in a string with repl.
    I=0 is case sensitive; IGNORECASE is not used.
    count=0 means make all possible replacements.
    count=n (n > 0) means make the first n possible replacements.

    Couldn't name this function 'replace()' because
    'replace()' is an existing string method.
    """
    import re
    if I == 0:
        p = re.compile(regex)
    else:
        p = re.compile(regex, re.IGNORECASE)
    return p.sub(repl, astr, count)

# for 2.6 and 3.x, use isinstance(anobj,str) instead
def isStringLike(anobj):
    """
    Return True if anobj is a string; False if not
    """
    # Recipe 1.3 in Python Cookook, 2nd ed.
    # http://www.ubookcase.com/book/Oreilly/Python.Cookbook.2nd.edition/0596007973/pythoncook2-chp-1-sect-3.html
    try: anobj.lower( ) + anobj + ''
    except: return False
    else: return True

def is_dst():
    """
    Return True if local time is Daylight Time, False if not.
    """
    # from p. 129 of Python Cookbook, 2nd ed.
    import time
    return bool(time.localtime().tm_isdst)

def intListToString(intList):
    "convert a list of integers to a string, and return the string"
    # OR: return ''.join([str(x) for x in intList])
    return ''.join(map(str, intList))

def findFactor(n, startingAt):
    """
    Written by Kent Johnson
    """
    limit = int(n**.5) + 1
    x = startingAt
    while x < limit:
        if not n % x:
            return x
        x += 2
    return False

def factorsOfInteger(n):
    """
    Return list of prime factors of n.
    Returns [n] if n is prime.
    Re-written largely by Kent Johnson
    """
    factors = []
    if n == 1:
        return [1]
    # Get the factors of two out of the way to simplify findFactor
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
    lastFactor = 3
    r = n
    while True:
        factor = findFactor(r, lastFactor)
        if not factor:
            # r is prime
            if r == 1: # This is needed, at least for powers of 2
                break
            factors.append(r)
            break
        factors.append(factor)
        lastFactor = factor
        r = r / factor
    if len(factors) == 1: # changed this from  if n in factors
        return factors
    factors[-1] = int(factors[-1]) # without this some last factors are floats, ending in .0
    return factors

def findDayOfWeek(year, month, day):
    from calendar import weekday
    dayNumber = weekday(year, month, day)
    dayNames = ('Monday', 'Tuesday', 'Wednesday', 'Thursday',
                'Friday', 'Saturday', 'Sunday')
    return dayNames[dayNumber]

##def strIsInt(astr):
##    """
##    Tests if a string is comprised of just an integer.
##    E.g., "-1234" --> True; "A34" --> False; "34.56" --> False
##    """
##    try:
##        int(astr)
##        return True
##    except:
##        return False

def strIsInt(astr): #Revise? employ isinstance()?
    """
    Tests if a string is comprised of just an integer.
    E.g., "-1234" --> True; "A34" --> False; "34.56" --> False "01234" --> False
    """
    #strip initial "-", if any, to test if the first digit is a zero; if it is, return False
    if astr[0] == "-":
        astr = astr[1:]
    if astr[0] == "0":
        return False
    try:
        int(astr)
        return True
    except:
        return False


def rstripToInt(n):
    """
    If a decimal (as a string) ends in .0, .00, .000, etc.,
    strip that ending to convert to an integer (as string).
    """
    n = n.rstrip(".0")
    return n

def floatToNearestInt(x):
    """
    convert float x to the nearest integer n
    e.g., 3.4 --> 3;  45.5 --> 46; -2.1 --> -2; -0.8 --> -1
    """
    return int(round(x))

def reduceFraction(num, denom): # TODO use fractions module
    """
    Given num and denom of a fraction, return
    the num and denom of the reduced fraction.
    """
    div = gcd2(num, denom)
    reducedNum = num/div
    reducedDenom = denom/div
    return int(reducedNum), int(reducedDenom)

def printReducedFraction():  #TODO use fractions moduled
    """
    Get a fraction from user and print the reduced fraction"
    """
    print("Enter the num and denom of the fraction to reduce")
    num, denom = get2NonzeroIntsFromUser()
    div = gcd2(num, denom)
    reducedNum = num/div
    reducedDenom = denom/div
    print('%d%s%d' % (reducedNum, '/', reducedDenom))

def get_integer():
    """
    Get integer from user and return it.
    """
    while True:
        try:
            return int(input("Enter an integer: "))
        except ValueError:
            print('You did not enter an integer')

def get2IntsFromUser():
    """
    Get 2 integers from user and return them.
    """
    while True:
        print("Enter 2 integers separated by a comma")
        try:
            m, n = (input("m, n: ")).split(',')
            m, n = int(m.strip()), int(n.strip())
        except ValueError:
            print()
            continue
        return m, n

def get2PosIntsFromUser():
    """
    Get 2 positive integers from use and return them.
    """
    while True:
        print("Enter 2 positive integers separated by a comma")
        try:
            m, n = (input("m, n: ")).split(',')
            m, n = int(m.strip()), int(n.strip())
        except ValueError:
            print()
            continue
        if m < 1 or n < 1:
            print()
            continue
        return m, n

def get_2_non_negative_ints_from_user():
    """
    Get 2 non-negative integers from use and return them.
    """
    while True:
        print("Enter 2 non-negative integers separated by a comma")
        try:
            m, n = (input("m, n: ")).split(',')
            m, n = int(m.strip()), int(n.strip())
        except ValueError:
            print()
            continue
        if m < 0 or n < 0:
            print()
            continue
        return m, n

def get2NonzeroIntsFromUser():
    """
    Get 2 non-zero integers from use and return them.
    """
    while True:
        print("Enter 2 non-zero integers separated by a comma")
        try:
            m, n = (input("m, n: ")).split(',')
            m, n = int(m.strip()), int(n.strip())
        except ValueError:
            print()
            continue
        if m == 0 or n == 0:
            print()
            continue
        return m, n

def numTailZeros(n):
    """
    Return the number of consecutive zeros at end of an integer.
    E.g., 25! = 15511210043330985984000000 ends in 6 zeros.
    """
    astr = str(n)
    return len(astr) - len(astr.rstrip('0'))

def uniform(n):
    """
    return distribution of digits in an int
    """
    #if not (isinstance(n, int)):
        #return "Not an int or long"
    a = str(n)
    i0, i1, i2, i3, i4, i5, i6, i7, i8, i9 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    for x in range(len(a)):
        if a[x] == '0':
            i0 += 1
        elif a[x] == '1':
            i1 += 1
        elif a[x] == '2':
            i2 += 1
        elif a[x] == '3':
            i3 += 1
        elif a[x] == '4':
            i4 += 1
        elif a[x] == '5':
            i5 += 1
        elif a[x] == '6':
            i6 += 1
        elif a[x] == '7':
            i7 += 1
        elif a[x] == '8':
            i8 += 1
        elif a[x] == '9':
            i9 += 1
    dist = [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9]
    return dist

def to_base(n, base):   #TODO
    """
    converts base 10 integer to another base, up thru base 36.
    Returns the integer in that base.
    """
    import string
    n = int(n)
    base = int(base)
    if base < 2 or base > 36:
        raise ValueError("Base must be between 2 and 36")
    if not n:
        return 0
    symbols = string.digits + string.uppercase[:26]
    answer = []
    while n:
        n, remainder = divmod(n, base)
        answer.append(symbols[remainder])
    return ''.join(reversed(answer))

def nTo35Bases(n):  #TODO
    """
    Returns list of 35 tuples of form (base, n to that base)
    from base 2 through base 36.
    """
    tupleLst = []
    for base in range(2,37):
        nToBase = to_base(n,base)
        tupleLst.append((base,nToBase))
    return tupleLst


def base10ToBaseN(n, base=2):
    """
    converts base 10 integer n to base 2-9 integer as string
    """
    if n == 0: return '0'
    if n < 0:
        sign = '-'
    else:
        sign = ''
    num = abs(n)
    seq = []
    while (num != 0):
        (num, bit) = divmod(num, base)
        seq.append(str(bit))
    seq.append(sign)
    return ''.join(reversed(seq))

def n_to_bases_2_thru_9(n):
    """
    Use base10ToBaseN() to compute base 10 integer n to bases 2 through 9
    as strings and put them into a list.
    """
    aList = []
    for x in range(2,10):
        s = base10ToBaseN(n, x)
        aList.append(s)
    return aList

def b2tob10(n):
    """
    Given a base 2 number (in either string or integer form, return the base 10 integer
    """
    s = str(n)
    pow = len(s)-1
    b10 = 0
    for x in s:
        if x == '1':
            b10 += 2**pow
        elif int(x) > 1:
            print("The base 2 can't have an integer > 1!")
            return
        pow -= 1
    return b10

def base2_explained(b2):
    """
    Given a base 2 number (b2) as either an integer or a string, returns a string that explains b2.

    >>> base2_explained('1011')
    '1*2**3 + 0*2**2 + 1*2**1 + 1*2**0'
    (Use with b2tob10(n) to both explain and evaluate b2)
    >>> b2 = 111
    >>> base2_explained(b2);b2tob10(b2)
    '1*2**2 + 1*2**1 + 1*2**0'
    7
    """
    b2 = str(b2)
    pow2 = len(b2)-1
    b2explained = ''
    for i,x in enumerate(b2):
        if pow2 > 0:
            b2explained += x + '*' + '2' + '**' + str(pow2) + ' + '
            pow2 -= 1
        else:
            b2explained += x + '*' + '2' + '**' + str(pow2)
    return b2explained

def baseN2base10(n, N=2):
    """
    Given a base N number (N <= 10) (in either string or integer form), return the base 10 integer

    >>> baseN2base10(101,2)
    5
    >>> baseN2base10('101',2)
    5
    >>> baseN2base10(1234,5)
    194
    >>> baseN2base10(194,10)
    194
    >>> baseN2base10(1234,16)
    The base, N, can't be > 10!
    >>>
    """
    s = str(n)
    power = len(s)-1
    b10 = 0
    if N > 10:
        print("The base, N, must be <= 10!")
        return

    for x in s:
        if 0 < int(x) < N:
            b10 += int(x)*N**power
        elif int(x) >= N:
            print("The base", N, "can't have an integer >= N!")
            return
        power -= 1
    return b10

def sumRndInt(m, n):
    """
    Generates a list of length m of random positive integers that sum to n.
    All possible lists are equally probable.
    m, n must be <= 2,147,483,647 (i.e., 2**31-1)

    Of course, m >= n
    This is the "telegraph pole" solution described at
    http://tinyurl.com/2wdt48 .
    """
    import random
    t = sorted(random.sample(range(1,n), n-1))
    t2 = [0] + t + [m]
    return [ (t2[i] - t2[i-1]) for i in range(1, len(t2)) ]

# Delete because of Python 3 built-in, round() (However, even it doesn't always round to even. E.g. round(0.1301675, 6) => 0.130167)
#def roundToEven(n, digits):
    #"""
    #For "round-to-even" rounding.
    #See http://en.wikipedia.org/wiki/Rounding#Round-to-even_method
    #"""
    #s = str(n)
    #if '.' in s:
        #mantissa = s.split('.')[1]
        #if len(mantissa) - digits != 1:
            #return round(float(s), digits)
        #if mantissa[digits] != '5':
            #return round(float(s), digits)
        #if mantissa[digits -1] in '13579':
            #return round(float(s), digits)
        #else:
            #return  s[:-1]
    #else:
        #return round(float(s), digits)

#def round2(n, digits):
    #"""
    #A corrective for the built-in function, round().

    #round() is wrong about 4% of time when mantissa ends in "45",
    #and rounding calls for, e.g. rounding 0.1301345 to 0.130135
    #round(0.1301345, 6) returns instead 0.130134
    #round2(0.1301345, 6) returns 0.130135
    #This is correct "common method rounding"
    #See http://en.wikipedia.org/wiki/Rounding#Common_method
    #"""
    #s = str(n)
    #if '.' in s and s[-2:] == '45':
        #mantissa = s.split('.')[1]
        #if len(mantissa) - digits == 1:
            #s = s[:-2] + '5'
            #return s
        #else:
            #return round(float(s), digits)
    #else:
        #return round(float(n), digits)

def sumStringDigits(s):
    """
    Return the sum of the digits in a string.
    The string may contain non-digit characters.
    """
    lstS = list(s)
    lstN = []
    for x in lstS:
        if x in "0123456789":
            lstN.append(int(x))
    return sum(lstN)

def productStringDigits(s):
    """
    Return the product of the digits in a string.
    The string may contain non-digit characters.
    """
    lstS = list(s)
    lstN = []
    for x in lstS:
        if x in "01234456789":
            lstN.append(int(x))
    product = 1
    for x in lstN:
        product *= x
    return product

def avgStringDigits(s):
    """
    Return the mean of the digits in a string.
    The string may contain non-digit characters.
    Return 0 if string is empty or has no digits.
    """
    lstN = []
    digit_count = 0
    for x in s:
        if x in "0123456789":
            digit_count += 1
            lstN.append(int(x))
    if digit_count == 0:
        return 0
    return sum(lstN)/digit_count

def unique(seq):
    """
    Take a sequence--a string, list, or tuple--and return a sorted
    sequence of the same type, and of all unique elements.

    Cannot be used if sequence contains complex numbers. This will
    raise a TypeError: no ordering relation is defined for complex numbers.
    """
    def types(example):
        """
        Given an object, return its type.
        """
        import re
        astr = str(type(example))
        regex = "\'(\w+)\'"
        p = re.compile(regex)
        pf = p.findall(astr)
        if pf:
            return pf[0]

    def unique_list(l):
        l = set(l)
        return list(l)

    def unique_str(s):
        lst = list(s)
        lst = unique_list(lst)
        lst.sort()
        return "".join(lst)

    def unique_tuple(t):
        lst = list(t)
        lst = unique_list(lst)
        return tuple(lst)

    typ = types(seq)

    if typ == "str":
        return unique_str(seq)
    elif typ == "list":
        return unique_list(seq)
    elif typ == "tuple":
        return unique_tuple(seq)

def pi_digits2():
    """
    generator for digits of pi

    Cannot be used alone. Used by printNPiDigits()
    """
    q,r,t,k,n,l = 1,0,1,1,3,3
    while True:
        if 4*q+r-t < n*t:
            yield n
            q,r,t,k,n,l = (10*q,10*(r-n*t),t,k,(10*(3*q+r))/t-10*n,l)
        else:
            q,r,t,k,n,l = (q*k,(2*q+r)*l,t*l,k+1,(q*(7*k+2)+r*l)/(t*l),l+2)

#def piToNDigits(n):
#    """
#    Returns PI to n digits.
#    E.g. if n is 4, returns 3.141
#    Does no rounding (e.g., returns 3.141, not 3.142)
#    """
#    digits = pi_digits2()
#
#    piList = []
#    for i in range(n):
#        piList.append(str(digits.next()))
#    piList.insert(1,".") # insert period between the 3 and the 1
#    piString = "".join(piList)
#    return piString
#
#def printNPiDigits(n):
#    """
#    Prints PI to n digits.
#    E.g. if n is 4, prints 3.141
#    Does no rounding (e.g., prints 3.141, not 3.142)
#    """
#    digits = pi_digits2()
#
#    piList = []
#    for i in range(n):
#        piList.append(str(digits.next()))
#    piList.insert(1,".") # insert period between the 3 and the 1
#    piString = "".join(piList)
#    print piString

#def piDigits(digits):
    #"""
    #Returns pi to any number of digits.

    #Rounding is inconsistent, in that 5 is sometimes rounded up,
      #and sometimes down.
    #"""
    ##from mpmath import *;mp.dps=digits;mp.pretty=True
    #from mpmath import mpf, mp, pi
    #mpf.dps = digits
    #return pi()

#def piDigits(digits):
    #"""
    #Returns pi to any number of digits.

    #Rounding is inconsistent, in that 5 is sometimes rounded up,
      #and sometimes down.
    #"""
    ##from mpmath import mpf, mp, pi
    #from mpmath import *
    #mp.dps = digits
    #return pi()




## this reinvents the wheel! random.randint() also handles negative min and max!!
#def rndInt(min, max=None):
#    """
#    Returns a random integer in closed interval [min,max],
#    where min, max are non-negative and min <= max
#    """
#    from random import random
#    if max is None:
#        max, min = min, 0
#    diff = max - min + 1
#    diff = max - min + 1
#    while True:
#        # remove initial "0." and possible final 0's, to leave a string of 10 digits
#        s = str(random())[2:12]
#        # when diff > 10; need to add extra number of 10 digit strings to s
#        digits = len(str(diff))
#        if digits > 10:
#            # find how many extra strings of 10 to add, if necessary
#            if digits % 10 == 0:
#                extra = digits/10 - 1
#            else:
#                extra = digits/10
#            astr = ""
#            # add the extra strings to s
#            for x in range(extra):
#                astr += str(random())[2:12]
#            s = s + astr
#        # remove unneeded digits at end of s, i.e., when len(s) > digits
#        s = s[:digits]
#        s = s.lstrip("0")
#        # in case s above was all ""0""'s
#        if s == "":
#            s = "0"
#        n = int(s)
#        if min <= (n + min) <= max:
#            return n + min

def random_digits_string(n):
    """
    Return n (n > 0) random digits in a string with one call to random.

    by Steve D'Aprano of the Tutor list

    >>> random_digits(6)
    '041890'
    >>> random_digits(20)
    '89372507420797668889'
    """
    return "%0*d" % (n, random.randrange(10**n))

def randIntOfGivenLength(length):
    """
    Return a random int of a given number of digits
    """
    return random.randint(10**(length-1), 10**length - 1)

def randIntOfRandLength(minLength, maxLength):  #TODO this returns a string!
    """
    First, the function generates a random length in closed interval
    [minLength, maxLength]. Then it generates a random integer n of that length,
    i.e., that many digits. The important feature of this function is that
    lengths within the max and min are all equally likely, as opposed to
    functions such as random.randint(). For example, for
    random.randint(10, 999), integers of 3-digit integers are 10 times more
    likely to be generated than 2-digit integers.
    """
    import random
    x = None
    s = ""
    n = None
    length = random.randint(minLength, maxLength)
    while True:
        x = random.randint(0, 9)
        s = s + str(x)
        if s[0] == '0':
            s.lstrip('0')
        n = int(s)
        if n >= 10**(length - 1):
            return n


def isLeap(y):
    """
    Returns True if y is a leap year; False if not.

    y is a leap year unless (1) it is either not divisible by 4,
    or (2) divisible by 100 but not divisible by 400.
    E.g., 1937 is not a leap year; 2100 is not; 2000 is; 2008 is.

    >>> isLeap(1937)
    False
    >>> isLeap(2100)
    False
    >>> isLeap(2000)
    True
    >>> isLeap(2008)
    True
    """
    if y % 4 != 0 or (y % 100 == 0 and y % 400 != 0):
        return False
    else:
        return True

#def easterAndAshWednesdayDates(y):
    #"""
    #Under the ecclesiastical rules, Easter is never earlier than March 22,
    #nor later than April 25.
    #This function will print the date of Easter for each year in the Gregorian calendar.
    #(Algorithm is from http://aa.usno.navy.mil/faq/docs/easter.html)

    #Ash Wednesday is always 46 days earlier than Easter.
    #"""
    ## compute Easter, given the year, y
    #c = y / 100
    #n = y - 19 * ( y / 19 )
    #k = ( c - 17 ) / 25
    #i = c - c / 4 - ( c - k ) / 3 + 19 * n + 15
    #i = i - 30 * ( i / 30 )
    #i = i - ( i / 28 ) * ( 1 - ( i / 28 ) * ( 29 / ( i + 1 ) ) * ( ( 21 - n ) / 11 ) )
    #j = y + y / 4 + i + 2 - c + c / 4
    #j = j - 7 * ( j / 7 )
    #l = i - j
    #m = 3 + ( l + 40 ) / 44
    #d = l + 28 - 31 * ( m / 4 )
    #easterMonth = "March"
    #easterDate = d
    #if m == 4:
        #easterMonth = "April"
    #print("Easter in %d is %s %d" % (y, easterMonth, easterDate))
    ## now compute Ash Wednesday, given year y, easterMonth, and easterDate
    #ashWednesdayDate = None
    #ashWednesdayMonth = None
    #leap = 0
    #if isLeap(y): # isLeap() is a mycalc function
        #leap = 1
    #if easterMonth == "April":
        #febDateForEaster = easterDate + 28 + leap + 31
        #ashWednesdayDate = febDateForEaster - 46
        #ashWednesdayMonth = "February"
    #elif easterMonth == "March":
        #febDateForEaster = easterDate + 28 + leap
        #ashWednesdayDate = febDateForEaster - 46
        #ashWednesdayMonth = "February"
    #if ashWednesdayDate > 28:
        #ashWednesdayDate -= 28
        #ashWednesdayMonth = "March"
    #print("Ash Wednesday in %d is %s %d" % (y, ashWednesdayMonth, ashWednesdayDate))

def easter_date(year):
    """
    Under the ecclesiastical rules, Easter is never earlier than March 22,
    nor later than April 25.
    This function will print the date of Easter for each year in the Gregorian calendar.
    (Algorithm is from http://aa.usno.navy.mil/faq/docs/easter.php)
    (online calculator: http://aa.usno.navy.mil/data/docs/easter.php)

    Ash Wednesday is always 46 days earlier than Easter.
    """
    # compute Easter, given the year
    y = year
    c = y // 100
    n = y - 19 * ( y // 19 )
    k = ( c - 17 ) // 25
    i = c - c // 4 - ( c - k ) // 3 + 19 * n + 15
    i = i - 30 * ( i // 30 )
    i = i - ( i // 28 ) * ( 1 - ( i // 28 ) * ( 29 // ( i + 1 ) ) * ( ( 21 - n ) // 11 ) )
    j = y + y // 4 + i + 2 - c + c // 4
    j = j - 7 * ( j // 7 )
    l = i - j
    m = 3 + ( l + 40 ) // 44
    d = l + 28 - 31 * ( m // 4 )
    easterMonth = "March"
    easterDate = d
    if m == 4:
        easterMonth = "April"
    print("Easter in", y, "is", easterMonth, easterDate)

def specific_easter_date_over_range_of_years(month, date, start_year, end_year):
    """
    Under the ecclesiastical rules, Easter is never earlier than March 22,
    nor later than April 25.
    This function will print the date of Easter for each year in the Gregorian calendar. (The first complete Gregorian calendar year was 1583.)
    (Algorithm is from http://aa.usno.navy.mil/faq/docs/easter.php)
    (online calculator: http://aa.usno.navy.mil/data/docs/easter.php)

    Ash Wednesday is always 46 days earlier than Easter.

    >>> specific_easter_date_over_range_of_years("April", 24, 1583, 3000)
    April 24 1639, April 24 1707, April 24 1791, April 24 1859, April 24 2011, April 24 2095, April 24 2163, April 24 2231, April 24 2383, April 24 2467, April 24 2478, April 24 2535, April 24 2603, April 24 2687, April 24 2698, April 24 2755, April 24 2839, April 24 2850, April 24 2907, April 24 2918, 20 Easters

    >>> specific_easter_date_over_range_of_years("March", 26, 1583, 3000)
    March 26 1595, March 26 1606, March 26 1617, March 26 1690, March 26 1758, March 26 1769, March 26 1780, March 26 1815, March 26 1826, March 26 1837, March 26 1967, March 26 1978, March 26 1989, March 26 2062, March 26 2073, March 26 2084, March 26 2119, March 26 2130, March 26 2141, March 26 2209, March 26 2282, March 26 2293, March 26 2339, March 26 2350, March 26 2361, March 26 2372, March 26 2434, March 26 2445, March 26 2456, March 26 2502, March 26 2513, March 26 2524, March 26 2586, March 26 2597, March 26 2654, March 26 2665, March 26 2676, March 26 2711, March 26 2722, March 26 2733, March 26 2806, March 26 2817, March 26 2828, March 26 2969, March 26 2980, 45 Easters

    >>> specific_easter_date_over_range_of_years("April", 26, 1583, 3000)
    0 Easters
    """
    count = 0
    for y in range(start_year, end_year+1):
        c = y // 100
        n = y - 19 * ( y // 19 )
        k = ( c - 17 ) // 25
        i = c - c // 4 - ( c - k ) // 3 + 19 * n + 15
        i = i - 30 * ( i // 30 )
        i = i - ( i // 28 ) * ( 1 - ( i // 28 ) * ( 29 // ( i + 1 ) ) * ( ( 21 - n ) // 11 ) )
        j = y + y // 4 + i + 2 - c + c // 4
        j = j - 7 * ( j // 7 )
        l = i - j
        m = 3 + ( l + 40 ) // 44
        d = l + 28 - 31 * ( m // 4 )
        easterMonth = "March"
        easterDate = d
        if m == 4:
            easterMonth = "April"

        if easterMonth == month and easterDate == date:
            count += 1
            print(easterMonth, easterDate, y, end = ', '),
            #print("Easter in", y, "is", easterMonth, easterDate, end = ', ')
    print(count, "Easters")

def permute(word):
    """
    By Barry Carrol <[email protected]>
    on Tutor list, revised (last line) by me.
    """
    retList=[]
    if len(word) == 1:
        # There is only one possible permutation
        retList.append(word)
    else:
        # Return a list of all permutations using all characters
        for pos in range(len(word)):
            # Get the permutations of the rest of the word
            permuteList=permute(word[0:pos]+word[pos+1:len(word)])
            # Now, tack the first char onto each word in the list
            # and add it to the output
            for item in permuteList:
                retList.append(word[pos]+item)
    #return retList
    return list(set(retList)) # My revision of last line to make elements of retList unique


#def round_to_n(x, n):
    #"""
    #Rounds float x to n significant digits, in scientific notation.
    #Written by Tim Peters. See his Tutor list post of 7/3/04 at
    #http://mail.python.org/pipermail/tutor/2004-July/030324.html

    #The largest x this function can compute is approximately
    #1.7976931348623158e+308
    #"""
    #if n < 1:
        #raise ValueError("number of significant digits must be >= 1")
    #if n > 16:
        #raise ValueError("round_to_n(x, n) is accurate only for n <= 16")
    #if x > 1.7976931348623158e+308:
        #raise ValueError("x must be < approximately 1.7976931348623158e+308")
    #return "%.*e" % (n-1, x)

def round_to_n(x, n=10000):
    """
    Rounds float x to n significant digits, in scientific notation.
    An early, simpler version was written by Tim Peters.
    See his Tutor list post of 7/3/04 at
    http://mail.python.org/pipermail/tutor/2004-July/030324.html

    For floats, n must be 1 >= n <= 16
    i.e., n must be in closed interval [1,16]
    n < 1 raises ValueError
    For n > 16, n silently set to 16.

    For integers, converts int to scientific notation.
    If want the full int expressed in scientific notation,
    omit n. The exponent+1 = number of digits in the integer x.

    >>> x = 337234222221111113333333333333333333333333333333
    >>> print(round_to_n(x))
    3.37234222221111113333333333333333333333333333333e+47
    >>> len(str(x))
    48

    >>> x = 337234222221111113333333333333333333333333333333
    >>> print(round_to_n(x,7))
    3.372342e+47
    >>> len(str(x))
    9

    >>> x = 123456789
    >>> print(round_to_n(x))
    1.23456789e+8
    >>> len(str(x))
    9

    >>> x = 56784567.34567689345678906789023455673578900987
    >>> print(round_to_n(x))
    5.678456734567689e+07

    >>> x = 56784567.34567689345678906789023455673578900987
    >>> print(round_to_n(x,4))
    5.678e+07

    The largest x this function can compute is approximately
    x = 1.7976931348623158e+308, or x = 1.999999999999999*2**1023

    TODO
    >>> x = .00000123456
    >>> round_to_n(x)
    '1.234560000000000e-06'
    """
    if n < 1:
        raise ValueError("number of significant digits must be >= 1")

    if x < 0:
        sign = '-'
        x = abs(x)
    else:
        sign = ''

    if x > 1.7976931348623158e+308:
        stmt1 = "x must be <= approximately 1.7976931348623158e+308\n"
        stmt2 = "or <= 1.999999999999999*2**1023;\n"
        stmt3 = "x = 2**1024 is too big"
        stmt = stmt1 + stmt2 + stmt3
        raise ValueError(stmt)

    if n == 10000 and isinstance(x, int):
        n = len(str(x))
        temp = "%.*e" % (n-1, x)
        idx = temp.find('+')
        exp = temp[idx+1:]
        x = str(x)
        exp = str(len(x)-1)
        return sign + x + 'e+' + exp

    elif isinstance(x, int):
        temp = "%.*e" % (n-1, x)
        idx = temp.find('+')
        exp = temp[idx+1:]
        x = str(x)
        exp = str(len(x)-1)
        return sign + x[0] + '.' + x[1:n] + 'e+' + exp

    elif isinstance(x, float):
        if n > 16:
            n = 16
        if x < 1:
            if n == 16:
                #print("x =",x)
                temp = str(x)
                if 'e' in temp:
                    #print("SECTION 1")
                    return sign + temp
                elif 'e' not in temp:
                    #print("SECTION 2")
                    temp2 = temp.replace('.','')
                    #print("temp2 =", temp2)

                    #now count the zeroes between before the first non-zero
                    temp3 = temp2
                    count = 0
                    while temp3[0] == '0':
                        temp3 = temp3[1:]
                        count += 1
                    #print("temp3 =", temp3)
                    #print("count =", count)
                    exp = str(-count)
                    #print("exp =", exp)
                    return sign + temp3[0] + '.' + temp3[1:] + 'e' + exp
                else:
                    print("BUG3!")

            elif n < 16:
                #print("SECTION 3")
                #print("x =", x)
                temp = str(x)
                #print("temp =", temp)
                idx1 = temp.find('-')
                exp = temp[idx1+1:]
                temp2 = temp.replace('.','')
                #print("temp2 =", temp2)
                idx2 = temp2.find('e')
                #print("idx2 =", idx2)
                temp3 = temp2[:idx2]
                temp4 = temp3[0] + '.' + temp3[1:]
                #print("temp4 =", temp4)
                temp5 = round(float(temp4),n-1)
                #print("after rounding: ", temp5)
                return sign + str(temp5) + 'e-' + exp

            else:
                print("BUG4!")

        elif x >= 1:
            return sign + "%.*e" % (n-1, x)

        else:
            print("BUG2!")

    else:
        print("BUG1!")

def numberRounding(n, significantDigits): #TODO Swap sig_digits for this in my scripts
    """
    Rounds a string in the form of a string number
    (float or integer, negative or positive) to any number of
    significant digits. If an integer, there is no limitation on it's size.
    Safer to always have n be a string.
    """
    import decimal
    def d(x):
        return decimal.Decimal(str(x))
    decimal.getcontext().prec = significantDigits
    s = str(d(n)/1)
    s = s.lstrip('0')
    return s

#TODO Swap sig_digits for this in my scripts
# Don't use -- can't use
def numberRounding2a(n, significantDigits):
    """
    Rounds a string in the form of a string number
    (float or integer, negative or positive) to any number of
    significant digits. If an integer, there is no limitation on it's size.
    Safer to always have n be a string.
    """
    if isinstance(n, float) and significantDigits > 16:
        significantDigits = 16
    #import decimal
    #def d(x):
        #return decimal.Decimal(str(x))
    import decimal
    decimal.getcontext().prec = significantDigits
    s = str(d(n)/1)
    s = s.lstrip('0')

    return s

def sig_digits(n, d=6):
    """
    Return any real number n to d significant digits, in scientific notation.
    """
    return '%.*e' % (d-1, n)

def sig_digits2(n, d):
    """
    If abs(n) > 1 ten-thousandth (1/10000) or abs(n) < 1 trillion, returns n in ordinary, non-scientific notation. For other abs(n), returns n in scientific notation. All n's are returned to d significant digits.

    >>> sig_digits2(1234.5678, 3)
    '1,230'
    >>> sig_digits2(1234.5678, 6)
    '1,234.57'
    >>> sig_digits2(1234.5678 * 5555, 4)
    '6,858,000'
    >>> sig_digits2(12.345678 ** 55, 4)
    '1.080e+60'
    >>> sig_digits2(12.345678/555, 4)
    '0.02224'
    >>> sig_digits2(12.345678/-1234567890, 4)
    '-0.02224'
    >>> sig_digits2(22.345678/-123456, 4)
    '-0.0001810'
    >>> sig_digits2(22.345678/-1234567, 4)
    '-1.810e-05'
    """
    from mycalc import numberCommas
    orig_n = n
    if n < 0:
        sign = '-'
        n = abs(n)
    else:
        sign = ''

    # equivalent to applying my sig_digits(n, d)
    n = '%.*e' % (d-1, n)

    #Extract exp (exponent), with leading zeros stripped.
    #the [2] means the 3rd part of the 3-part partition, which is the exponent.
    #remember, n is always >= 0 (through use of abs() above.
    exp = n.partition('e')[2].lstrip('0')
    #handle case where exp is originally '00'; both zeros will be stripped.
    if exp == '':
        exp = '0'

    #if abs(n) <= 1 ten-thousandth (1/10000), returns n in scientific notation
    if int(exp) < -4:
        return sign + n

    # return an n where abs(n) >= 1 trillion in scientific notation
    elif int(exp) > 11:
        return sign + n

    if float(n) < 1:
        #remove the decimal point
        n = n.replace('.','')
        exp = n[n.find('e-')+2:].lstrip('0')
        return sign + '0.' + (int(exp)-1)*'0' + n.partition('e-')[0]

    elif float(n) >= 1:
        #remove the decimal point
        n = n.replace('.','')

        # the head is what is before the 'e' (my term)
        head = n.partition('e+')[0] #+ int(exp)*'0'
        n = head +(int(exp) - len(head) +1) * '0'

        #replace the decimal point
        n = n[:int(exp)+1] + '.' + n[int(exp)+1:]

        # remove decimal point if there is no fractional part of n
        if n[-1] == '.':
            n = n[:-1]
        return sign + numberCommas(n)

def getMinAndMaxIntegersFromUser(default_min, default_max):
    print("Enter 2 integers > 1 for min and max, with max >= min")
    print("Put a comma between the numbers. E.g., '8, 20'")
    print("Press Enter to set default of  %d, %d" % (default_min, default_max))

    while True:
        ans = input("min, max: ")
        if ans == '':
            print("The default min, max have been set to %d, %d\n" % (default_min, default_max))
            return (5, 20)
        try:
            min, max = ans.split(',')
        except ValueError:
            print("\nPlease start over and enter correct min and max.")
            print("Enter 2 integers > 1 for min and max, with max >= min")
            print("Press Enter to set default of  5, 20\n")
            continue
        try:
            min = int(min)
        except ValueError:
            print("\nPlease start over and enter correct min and max.")
            print("Enter 2 INTEGERS > 1 for min and max, with max >= min")
            print("Press Enter to set default of  5, 20\n")
            continue
        try:
            max = int(max)
        except ValueError:
            print("\nPlease start over and enter correct min and max.")
            print("Enter 2 INTEGERS > 1 for min and max, with max >= min")
            print("Press Enter to set default of  5, 20\n")
            continue
        if min > max or min < 2:
            print("\nPlease start over and enter correct min and max.")
            print("min must be <= max and min must be > 1")
            print("Enter 2 integers > 1 for min and max, with max >= min")
            print("Press Enter to set default of  5, 20\n")
            continue
        else:
            break
    return (min, max)

def group_num_to_group_name(group_num):
    """
    Function used only by intSpell

    Find American English illionName of group, given its illionNum.
    Example: illionName of group "345" (illionNum 2) in "111345666000" is "million"
    Reference: http://mathworld.wolfram.com/LargeNumber.html
    Reference: http://en.wikipedia.org/wiki/Nonillion#The_.22standard_dictionary_numbers.22
    """
    names = [ \
        "",
        " thousand,",
        " million,",
        " billion,",
        " trillion,",
        " quadrillion,",        #5
        " quintillion,",
        " sextillion,",
        " septillion,",
        " octillion,",
        " nonillion,",           #10
        " decillion,",
        " undecillion,",
        " duodecillion,",
        " tredecillion,",
        " quattuordecillion,",
        " quindecillion,",
        " sexdecillion,",
        " septendecillion,",
        " octodecillion,",
        " novemdecillion,",      #20
        " vigintillion,",
        " unvigintillion,",
        " duovigintillion,",
        " tresvigintillion,",
        " quattuorvigintillion",
        " quinquavigintillion",
        " sesvigintillion",
        " septemvigintillion",
        " octovigintillion",
        " novemvigintillion",    #30
        " trigintillion",
        " untrigintillion",
        " duotrigintillion",
        " trestrigintillion",
        " quattuortrigintillion",
        " quinquatrigintillion",
        " sestrigintillion",
        " septentrigintillion",
        " octotrigintillion",
        " novemtrigintillion",   #40
        " quadragintillion",
    ]
    group_name = names[group_num]
    return group_name


def stripZeros(group):
    """
    strip zeros at front of group, if any; or whole group if "000".
    E.g., 045 -> 45; 003 -> 3; 000 -> ''
    """
    if int(group) == 0:
        return ""
    return str(int(group))

#def isIntTooLarge(n): #TODO: delete this?
    #"""
    #Function used only by intSpell()

    #Largest n that can be spelled out is 10**66 - 1, or
    #999999999999999999999999999999999999999999999999999999999999999999
    #i.e., 999 vigintillion, 999 novemdecillion, 999 octodecillion,
    #999 septendecillion, 999 sexdecillion, 999 quindecillion,
    #999 quattuordecillion, 999 tredecillion, 999 duodecillion,
    #999 undecillion, 999 decillion, 999 nonillion, 999 octillion,
    #999 septillion, 999 sextillion, 999 quintillion, 999 quadrillion,
    #999 trillion, 999 billion, 999 million, 999 thousand, 999

    #There seem to be no more words for larger integers.
    #"""
    #if len(str(n)) > 66:
        #return True
    #else:
        #return False

def intSpell(n):
    """
    Returns spelling of any integer up to 126 digits in length.

    E.g. 1234567 -> 1 million, 234 thousand, 567
    """
    s = format(n, ',d')
    # no group names for n >= 10**126 (IOW, for a int of 128 digits or longer)
    if n >= 10**126:
        return s
    #handle s = 300 or 30 or 3, and have nothing to spell
    if "," not in s:
        return s
    # begin the creation of a list of the groups
    spelled_s = []
    #number of commas determines group_num of initial group
    initial_group_num = s.count(",")
    # employ group_num_to_group_name() function to get group_name (e.g., ' million,')
    initial_group_name = group_num_to_group_name(initial_group_num)
    # the ints of initial group are the characters up to the first comma of s, so need comma's index
    initial_group_ints = s[:s.find(",")]
    num_initial_group_ints = len(initial_group_ints)
    initial_group = initial_group_ints + initial_group_name
    spelled_s.append(initial_group)
    # the initial group having been determined, use the while loop to determine
    # the succeeding groups, all of which will have 3-digit group_ints
    group_num = initial_group_num
    count = -1
    while group_num >= 1:
        count += 1
        group_num -= 1
        group_name = group_num_to_group_name(group_num)
        group_ints = s[num_initial_group_ints+1+count*4:num_initial_group_ints+1+count*4+3]
        # when the group_ints are all zeros, skip processing it and continue on with the next
        if group_ints == "000":
            continue
        else:
            group_ints = group_ints.lstrip("0")
            group = group_ints + group_name
            spelled_s.append(group)

    spelled_s = ' '.join(spelled_s)
    # get rid of final comma in spelled_s such as "123 million, 456 thousand,"
    if spelled_s[-1] == ",":
        spelled_s = spelled_s[:-1]
    return spelled_s

def intFullSpell(n):  #TODO  output uses 2 commas for separator
    """
    Returns full spelling of an integer.

    E.g. 1234567 -> one million, two hundred thirty-four thousand, five hundred sixty-seven
    """
    s = format(n, ',d')
    list_of_group_ints = s.split(",")
    list_of_spelled_group_ints = []
    for gi in list_of_group_ints:
        list_of_spelled_group_ints.append(three_digit_int_spell(gi))
    num_groups = len(list_of_group_ints)
    spelled_s = []
    for i, group_int in enumerate(list_of_spelled_group_ints, 1):
        group_num = num_groups - i
        group_int = group_int.lstrip("0")
        if group_int == "":
            continue
        else:
            group_name = group_num_to_group_name(group_num)
            #group = group_int + " " + group_name + ","
            group = group_int + group_name
            spelled_s.append(group)
    spelled_s = ' '.join(spelled_s)
    spelled_s = spelled_s.rstrip(",' '")
    return spelled_s

def three_digit_int_spell(gi):
    """
    Used only by intFullSpell()
    """

    gi = str(gi)

    # if gi isn't a 3-digit int, prepend zeros to make it 3 digits
    while len(gi) < 3:
        gi = "0" + gi
    #print("gi =", gi)

    sd_lst = [ \
        "",
        "one",
        "two",
        "three",
        "four",
        "five",
        "six",
        "seven",
        "eight",
        "nine",
    ]

    hd_lst = sd_lst

    td_lst = [ \
        "",
        "twenty",
        "thirty",
        "forty",
        "fifty",
        "sixty",
        "seventy",
        "eighty",
        "ninety",
    ]

    teen_lst = [ \
        "",
        "ten",
        "eleven",
        "twelve",
        "thirteen",
        "fourteen",
        "fifteen",
        "sixteen",
        "seventeen",
        "eighteen",
        "nineteen",
    ]

    hd = gi[0]
    if gi[0] == "0":
        spelled_hd = ""
    elif gi[:2] == "00":
        return sd_lst[gi[2]]
    else:
        spelled_hd = hd_lst[int(hd)] + " hundred"

    td = gi[1]
    sd = gi[2]
    spelled_sd = sd_lst[int(sd)]
    if td == "1":
        sd = gi[2]
        spelled_dd = teen_lst[int(sd)+1] # "dd": double digit
        spelled_gi = spelled_hd + " " + spelled_dd
    elif int(td) > 1:
        spelled_td = td_lst[int(td)-1]
        spelled_sd = sd_lst[int(sd)]
        spelled_gi = spelled_hd + " " + spelled_td + "-" + spelled_sd
    elif td == "0":
        spelled_gi = spelled_hd + " " + spelled_sd
    spelled_gi = spelled_gi.lstrip(" ")
    spelled_gi = spelled_gi.rstrip("-")
    return spelled_gi

def secsToHMS(seconds):
    """
    Convert seconds to hours:minutes:seconds, with seconds rounded to hundredths of a second.
    """
    minutes, seconds = divmod(seconds, 60)
    hours, minutes = divmod(minutes, 60)
    return "%02d:%02d:%05.2f" % (hours, minutes, seconds)

def hms(seconds):
    """
    Convert seconds to tuple (hours, minutes, seconds)
    """
    hours, minutes = 0, 0

    if seconds >= 60 and seconds < 3600:
        minutes, seconds = divmod(seconds, 60)
    elif seconds >= 3600:
        hours, seconds = divmod(seconds, 3600)
        minutes, seconds = divmod(seconds, 60)

    return hours, minutes, seconds

def print_hms(seconds):
    """
    Convert seconds to hours, minutes, seconds and print result
    """
    seconds = floatToNearestInt(seconds)
    hours, minutes = 0, 0

    if seconds >= 60 and seconds < 3600:
        minutes, seconds = divmod(seconds, 60)
    elif seconds >= 3600:
        hours, seconds = divmod(seconds, 3600)
        minutes, seconds = divmod(seconds, 60)

    hp, mp, sp = "s", "s", "s" # add "s" to make "hour", "minute", "second" plural
    if hours == 1:
        hp = "" # no "s" on "hour"
    if minutes == 1:
        mp = ""
    if seconds >= 1 and seconds < 2:
        sp = ""

    if hours == 0 and minutes == 0:
        print("%d second%s" % (seconds, sp))
    elif hours == 0:
        if seconds == 0:
            print("%d minute%s exactly" % (minutes, mp))
        else:
            print("%d minute%s, %d second%s" % (minutes, mp, seconds, sp))

    elif minutes == 0:
        if seconds == 0:
            print("%d hour%s exactly" % (hours, hp))
        else:
            print("%d hour%s, %d second%s" % (hours, hp, seconds, sp))
    else:
        print("%d hour%s, %d minute%s, %d second%s" % (hours, hp, minutes, mp, seconds, sp))

def hmsToText(seconds):
    """
    Convert seconds to hours, minutes, seconds and return result
    """
    seconds = floatToNearestInt(seconds)
    hours, minutes = 0, 0

    if seconds >= 60 and seconds < 3600:
        minutes, seconds = divmod(seconds, 60)
    elif seconds >= 3600:
        hours, seconds = divmod(seconds, 3600)
        minutes, seconds = divmod(seconds, 60)

    hp, mp, sp = "s", "s", "s" # add "s" to make "hour", "minute", "second" plural
    if hours == 1:
        hp = "" # no "s" on "hour"
    if minutes == 1:
        mp = ""
    if seconds >= 1 and seconds < 2:
        sp = ""

    if hours == 0 and minutes == 0:
        result = "%d second%s" % (seconds, sp)
    elif hours == 0:
        if seconds == 0:
            result = "%d minute%s exactly" % (minutes, mp)
        else:
            result = "%d minute%s, %d second%s" % (minutes, mp, seconds, sp)
    elif minutes == 0:
        if seconds == 0:
            result = "%d hour%s exactly" % (hours, hp)
        else:
            result = "%d hour%s, %d second%s" % (hours, hp, seconds, sp)
    else:
        result = "%d hour%s, %d minute%s, %d second%s" % (hours, hp, minutes, mp, seconds, sp)
    return result

def iter_primes():
    """
    an iterator of all prime numbers between 2 and +infinity
    """
    import itertools
    numbers = itertools.count(2)

    # generate primes forever
    while True:
        # get the first number from the iterator (always a prime)
        prime = next(numbers)
        yield prime

        # remove all numbers from the (infinite) iterator that are
        # divisible by the prime we just generated
        numbers = filter(prime.__rmod__, numbers)


def primeList(n):
    """
    Returns list of all primes in closed interval [2,n].
    psyco will greatly increase speed.
    """
    import math
    if n == 2:
        return [2]
    primes=[3]
    for x in range(5,n+1,2):
        maxfact = math.sqrt(x)
        for y in primes:
            if y > maxfact:
                primes.append(x)
                break
            if not x%y:
                break
    primes = [2] + primes
    return primes

def nextPrime(n):
    """
    Return the first prime >= n.
    """
    x = n
    if x % 2 == 0:
        x += 1
    while True:
        if isPrime(x):
            p = x
            return p
        x += 2

def nextLargerPrime(n):
    """
    Return the first prime >= n.
    """
    x = n
    if x % 2 == 0:
        x += 1
    while True:
        if isPrime(x):
            p = x
            return p
        x += 2

def nextSmallerPrime(n):
    """
    Return the first prime <= n (n >= 2).
    """
    x = n
    if x != 2 and x % 2 == 0:
        x -= 1
    while True:
        if isPrime(x):
            p = x
            return p
        x -= 2

def nearestPrime(n):
    """
    Return the nearest prime to n, or if n is prime, return n.
    In case of ties, return the smaller.

    Thus if n = 17 return 17; if 16 return 17; if 14 return 13;
    if n = 15 return 13 (not 17)
    """
    x = n
    if x % 2 == 0:
        x += 1
    y = x - 2
    while True:
        if isPrime(x):
            return x
        if isPrime(y):
            return y
        x += 2
        y -= 2

def nearestPrimes(n, num_of_primes):
    """
    Return list of num_of_primes nearest primes to integer n; if n is prime, list will include n.

    List will include the prime 2 if appropriate, but no "prime" < 2.
    """
    primes = []
    count = 0
    lx = n  #for ints >= n  (l for larger)
    if lx == 2:
        primes.append(2)
        count += 1
        lx = 3
    elif lx % 2 == 0:
        lx += 1
    sx = lx - 2  #for ints < n  (s for smaller)

    while count < num_of_primes:
        if isPrime(lx):
            primes.append(lx)
            count += 1
        lx += 2
        if sx >= 2:
            if isPrime(sx):
                primes.append(sx)
                count += 1
        if sx == 3:
            sx = 2
        else:
            sx -= 2
    primes.sort()
    return primes

def nextNPrimes(m,n=1):
    """
    Return list of n primes >= m and smaller than any other primes
    """
    count = 0
    primes = []
    if m % 2 == 0:
        m += 1
    while count < n:
        if isPrime(m):
            primes.append(m)
            count += 1
        m += 2
    return primes

def nextNLargerPrimes(m,n=1):
    """
    Return list of first n primes >= m
    """
    count = 0
    primes = []
    if m % 2 == 0:
        m += 1
    while count < n:
        if isPrime(m):
            primes.append(m)
            count += 1
        m += 2
    return primes

def nextNSmallerPrimes(m,n=1):
    """
    Return list of n, or less than n primes that are the largest primes < m

    For example, if m = 8, there are only 4 primes less than 8 (7, 5, 3 and 2)
    """
    x = m
    count = 0
    primes = []
    if x <= 1:
        return []
    if x == 2:
        return [2]
    if x % 2 == 0:
        x -= 1
    while count < n:
        if x > 3:
            if isPrime(x):
                primes.append(x)
                count += 1
            x -= 2
        elif x == 3:
            primes.append(3)
            count += 1
            x -= 1
        elif x == 2:
            primes.append(2)
            return primes

    return primes

def maxDiffBetPrimes(n):
    """
    Prints max diff between primes that are in interval [2,n],
    and also prints those pairs of primes.
    """
    from mycalc import primeList
    primes = primeList(n)
    maxDiff = 1
    pairs = []
    for i in range(len(primes)-1):
        diff = primes[i+1] - primes[i]
        #pairs.append((primes[i], primes[i+1]))
        if diff == maxDiff:
            pairs.append((primes[i], primes[i+1]))

        if diff > maxDiff:
            pairs = []
            pairs.append((primes[i], primes[i+1]))
            maxDiff = diff

    print("For primes up through %d, max diff is %d" % (n, maxDiff))
    print("between the %d pair(s) of primes %s" % (len(pairs),pairs))

def maxAndMinDiffBetPrimes(n,m):  #TODO
    """
    Prints max diff and min diff between consecutive primes that are in
    closed interval [n,m], and prints those pairs of primes. If the min diff is
    2, also prints the percentage of the pairs that differ by 2.
    """
    from mycalc import primesNToM, numberCommas, intSpell
    primes = primesNToM(n,m)
    maxDiff = 1
    minDiff = 1000000000
    pairsMax = []
    pairsMin = []
    for i in range(len(primes)-1):
        diff = primes[i+1] - primes[i]
        #pairs.append((primes[i], primes[i+1]))
        if diff == maxDiff:
            pairsMax.append((primes[i], primes[i+1]))
        if diff == minDiff:
            pairsMin.append((primes[i], primes[i+1]))


        if diff > maxDiff:
            pairsMax = []
            pairsMax.append((primes[i], primes[i+1]))
            maxDiff = diff
        if diff < minDiff:
            pairsMin = []
            pairsMin.append((primes[i], primes[i+1]))
            minDiff = diff

    if n >= 1000000000:
        print("n = %s (%s)" % (numberCommas(n), intSpell(n)))
        print("m = %s (%s)" % (numberCommas(m), intSpell(m)))
    else:
        print("n = %s" % numberCommas(n))
        print("m = %s" % numberCommas(m))
    percent = len(primes)*100.0/(m-n+1)
    print("%d/%d (%.4g percent) of the integers in [n,m] are prime." % (len(primes), (m-n+1), percent))
    print()
    print("The %d primes in closed interval [n,m] are %s" % (len(primes), primes))
    print("The max diff between consecutive primes is %d," % maxDiff)
    print("between the %d pair(s) of primes %s" % (len(pairsMax),pairsMax))
    print()
    print("The min diff between consecutive primes is %d," % minDiff)
    print("between the %d pair(s) of primes %s" % (len(pairsMin),pairsMin))
    if minDiff == 2:
        percent = len(pairsMin)*100.0/(len(primes)-1)
        print("%d of the %d pairs (%.4g percent) differ by 2" % (len(pairsMin), len(primes)-1, percent))

def isPrime(n):
    """
    Return True if n is prime, False if not prime.
    """
    #import gmpy2
    #from gmpy2 import is_prime
    if not isinstance(n, int):
        raise TypeError("The argument to isPrime() must be an int.")
    x = gmpy2.is_prime(n, 25)
    return x != False

def primesNtoM(n, m):
    """
    returns the list of all primes in closed interval [n,m]

    assumes n <= m
    n may be < 0 or both n and m may be < 0
    """
    primes = []
    if m < 2:
        return []
    if n <= 2 and m >= 2:
        primes.append(2)
        n = 3
    elif n % 2 == 0:
        n += 1
    for x in range(n, m + 1, 2):
        if isPrime(x):
            primes.append(x)
    return primes

def primesNtoM2a(n, m):
    """
    Returns the list of all primes in closed interval [n,m]

    primesNtoM2a() is faster than primesNtoM2b() up to ~500 trillion, and
    """
    from gmpy import next_prime

    p = int(next_prime(n-1))
    primes = []
    primes.append(p)
    prev_p = p
    while True:
        p = int(next_prime(prev_p))
        if p > m:
            return primes
        primes.append(p)
        prev_p = p

def primesNtoM2b(n, m):
    """
    Returns the list of all primes in closed interval [n,m]
    """
    from gmpy2 import next_prime

    p = int(next_prime(n-1))
    primes = []
    primes.append(p)
    prev_p = p
    while True:
        p = int(next_prime(prev_p))
        if p > m:
            return primes
        primes.append(p)
        prev_p = p

def primesToN(n):
    """
    Return list of primes in closed interval [2,n]
    Note: find_primes() is about 10X faster
    """
    primes = [2]
    x = 3
    while x < n + 1:
        if isPrime(x):
            primes.append(x)
        x += 2
    return primes


def find_primes(n):
    """
    Return list of primes in closed interval [2,n]
    Note: find_primes() is about 10X faster than primesToN()
    """
    # from a post by bluemoo for #187 in Project Euler.
    # a very fast algorithm.
    # see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    from math import sqrt
    if n < 2:
        return []
    if n == 2:
        return [2]
    # do only odd numbers starting at 3
    s = list(range(3, n, 2))
    # n**0.5 may be slightly faster than math.sqrt(n)
    mroot = sqrt(n)
    half = len(s)
    i = 0
    m = 3
    while m <= mroot:
        if s[i]:
            j = (m * m - 3)//2
            s[j] = 0
            while j < half:
                s[j] = 0
                j += m
        i = i + 1
        m = 2 * i + 3
    # make exception for 2
    return [2]+[x for x in s if x]

def poi(lmda, k):
    """
    Poisson distribution. Returns probability of exactly k occurrences given lmda

    See http://en.wikipedia.org/wiki/Poisson_distribution
    Examples of lmdas:
    The number of soldiers killed by horse-kicks each year in each corps in the Prussian cavalry.
    The number of phone calls at a call center per minute.
    The number of times a web server is accessed per minute.
    The number of mutations in a given stretch of DNA after a certain amount of radiation.
    >>> poi(3.7, 4)
    0.19306612122157396
    >>> poi(10,4)
    0.018916637401035365
    """
    from math import e, factorial
    #if int(k) != k:
        #print k, "is not an integer"
    if not isinstance(k, int):
        raise TypeError("WTF you didn't pass me an int")
    p = (e**(-lmda)*(lmda**k))/factorial(k)
    return p

def poi_for_range_of_k(lmda, begin, end):
    """
    Returns probability of range of k occurrences given lmda.

    Example: for lmbda of 6.5, and k's of 3,4,5
    poi_for_range_of_k(6.5, 3, 5) = poi(6, 3) + poi(6, 4) + poi(6, 5) = 0.383710836948
    """
    p = 0
    for k in range(begin, end+1):
        p += poi(lmda, k)
    return p

def poiAtMost(lmda, k):
    """
    Poisson distribution. Returns probability of at most k occurrences given lmda.

    >>> poiAtMost(3.7, 4)
    0.6872193653719925
    """
    p = 0
    for k in range(k + 1):
        p += poi(lmda, k)
    return p

def poiAtLeast(lmda, k):
    """
    Poisson distribution. Returns probability of at least k occurrences given lmda.

    >>> poiAtLeast(3.7, 5)
    0.31278063462800754
    """
    return 1 - poiAtMost(lmda, k - 1)

def poiInterval(lmda, kMin, kMax):
    """
    Returns sum of probabilities of k occurrences for all kMin <= k <= kMax, given lmda.

    >>> poiInterval(3.7,0,4)
    0.6872193653719925
    >>> poiInterval(3.7,6,10)
    0.16833952392312523
    """
    p = 0
    for k in range(kMin, kMax + 1):
        p += poi(lmda, k)
    return p

def avg(sequence_):
    from math import fsum
    from fractions import Fraction
    return fsum(sequence_) * Fraction(1, len(sequence_))

def median(list_):
    """
    Returns the median of list_.
    In order to preserve the original order of list_,
    first makes a copy (tmp) of list_, and computes on the copy.
    """
    tmp = list_[:] # make a copy of list_ and then sort the copy
    tmp.sort()
    half = len(tmp) // 2
    if (len(tmp)%2)==1:
        return tmp[half]
    else:
        return sum(tmp[half-1:half+1])/2


def compareSequences(seq1, seq2):
    """
    Returns first index at which two sequences differ. If one is longer than the other,
    ignores the elements of the longer for which there are no corresponding elements in the shorter.
    The 2 sequences can be of different types.

    >>> a = "Now is the time"
    >>> b = "Now was the time"
    >>> compareSequences(a, b)
    4
    >>> a = '125477'
    >>> b = ['1','2','3','4']
    >>> compareSequences(a, b)
    >>> 2
    >>> b = ('1','2','3','4')
    >>> compareSequences(a, b)
    >>> 2
    >>> a = 'zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz'
    >>> b = 'zzzzzzzzzzzzz+zzzzzzzzzzzzzzzzzzzzzzzzzzz'
    >>> compareSequences(a, b)
    >>> 13
    >>> b = 'zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz'
    >>> compareSequences(a, b)
    >>> None
    >>> a
    >>> 'zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz'
    >>> b
    >>> 'zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz'
    """
    if len(seq2) > len(seq1):
        seq1, seq2 = seq2, seq1
    for index in range(0, len(seq2)):
        if seq1[index] != seq2[index]:
            return index

def comp_seqs_and_mark(str1, str2):
    """
    Prints 3 lines: str1, a line with only a '|' marker, and str2.
    If strings are identical up to end of shorter one, only the strings are printed.

    >>> a = 'Now is the time'
    >>> b = 'Now is our time'
    >>> comp_seqs_and_mark(a, b)
    Now is the time
           |
    Now is our time
    >>> a = '1.2345'
    >>> b = '1.2345678'
    >>> comp_seqs_and_mark(a, b)
    1.2345
    1.2345678
    >>> a = '1.23457777777777777777777777777777777777777777777777777777777777777777777'
    >>> b = '1.2345777777777777777777707777777777777777777777777777777777777777'
    >>> comp_seqs_and_mark(a, b)
    1.23457777777777777777777777777777777777777777777777777777777777777788777
                             |
    1.2345777777777777777777707777777777777777777777777777777777777777
    """
    reversed_flag = None
    if len(str2) > len(str1):
        str1, str2 = str2, str1
        print(str2)
        reversed_flag = True
    else:
        print(str1)
    for index in range(0,len(str2)):
        if str1[index] != str2[index]:
            if index == 0:
                print('|')
                break
            elif index > 0:
                print((index-1)*' ', '|')
                break
            else:
                print('BUG')

    if reversed_flag == True:
        print(str1)
    else:
        print(str2)

#def comp_seqs_and_mark(str1, str2):
    #reversed_flag = None
    #if len(str2) > len(str1):
        #str1, str2 = str2, str1
        #print(str2, label2)
        #reversed_flag = True
    #else:
        #print(str1)
    #for index in range(0,len(str2)):
        #if str1[index] != str2[index]:
            #if index == 0:
                #print('|')
                #break
            #elif index > 0:
                #print((index-1)*' ', '|')
                #break
            #else:
                #print('BUG')
    #if reversed_flag:
        #print(str1)
    #else:
        #print(str2)

def cmpSeq(seq1, seq2):
    """
    find first index at which two sequences differ
    """
    if seq1 == seq2:
        print("Sequences are identical, and of length %d" % len(seq1))
        return None
    if len(seq1) >= len(seq2):
        shorterOrEqualSequence = seq2
    else:
        shorterOrEqualSequence = seq1

    for index in range(len(shorterOrEqualSequence)):
        if seq1[index] != seq2[index]:
            print("sequences first differ at index", index)
            print("seq1[%d] = %s" % (index, seq1[index]))
            print("seq2[%d] = %s" % (index, seq2[index]))
            break

    if index == len(shorterOrEqualSequence)-1:
        print("sequences are identical thru end of shorter sequence at index", index)

    print("len(seq1) =", len(seq1))
    print("len(seq2) =", len(seq2))

def ordSuff(n):
    """
    returns suffix for ordinal integer n; e.g. 1237 -> 1237th
    """
    n = str(n)
    if n[-1] in "0456789":
        suff = "th"
    elif n[-2:] in ['11', '12', '13']:
        suff = "th"
    elif n[-1] == "1":
        suff = "st"
    elif n[-1] == "2":
        suff = "nd"
    else:
        suff = "rd"
    return suff

def int_to_ordinal(n):
    """
    Takes an int and returns the string ordinal integer, with commas as appropriate
    plus the appropriate suffix; e.g. 1237 -> 1,237th
    """
    n = str(n)
    if n[-1] in "0456789":
        suff = "th"
    elif n[-2:] in ['11', '12', '13']:
        suff = "th"
    elif n[-1] == "1":
        suff = "st"
    elif n[-1] == "2":
        suff = "nd"
    else:
        suff = "rd"
    return intCommas(n) + suff

def intCommas(n):
    """
    inserts commas into integers. E.g. -12345678 -> -12,345,789
    """
    s = str(n)
    sign = ''
    if s[0] == '-':
        sign = '-'
        s = s[1:]
    slen = len(s)
    a = ''
    for index in range(slen):
        if index > 0 and index % 3 == slen % 3:
            a = a + ','
        a = a + s[index]
    return sign + a

#TODO

def numberCommas(n):
    """
    Inserts commas into integers, or into the integer part of floats.
    (If for integers only, can use my function, intCommas().)
    Returns a string
    """
    def handle_minus(n):
        n = str(n)
        if n[0] == "-":
            n = n[1:]
            minus = "-"
        else:
            minus = ""
        return n, minus

    n, minus = handle_minus(n)
    n = n.lstrip("0") # E.g 00123->123 and 00034.4500->34.4500
    if "." in n:
        n = n.split(".")
        return minus + intCommas(n[0]) + "." + n[1]
    else:
        return minus + intCommas(n)

def stripZeroes(number):
    """
    Strips trailing zeroes in fraction part of a float converted to a string.
    This is not easily done with rstrip().
    """
    number = str(number)
    if "." in number:
        while number[-1] in ".0":
            number = number[:-1]
    return number # as string

def flatten(seq):
    """
    example of sequence to flatten: [1,2,3,4,[5,6,'seven',8,(9,10,11)]]
    output: [1, 2, 3, 4, 5, 6, 'seven', 8, 9, 10, 11]
    from http://aspn.activestate.com/ASPN/Mail/Message/python-list/453883
    """
    from types import TupleType, ListType
    res = []
    for item in seq:
        if type(item) in (TupleType, ListType):
            res.extend(flatten(item))
        else:
            res.append(item)
    return res

#def beep():  #doesn't work in Vista
    #"""A very short Beep"""
    #import winsound
    #pitch = 500
    #length = 30
    #winsound.Beep(pitch,length)

def beep():
    """A very short bop sound"""
    import winsound
    winsound.PlaySound("/P31Working/Sounds/beat", winsound.SND_ALIAS)

def beepN(times,interval):
    """Calls beep() n times at interval of x seconds."""
    import time
    for k in range(times-1):
        beep()
        time.sleep(interval)
    beep()

def tadaa():
    """a Ta Daa! sound"""
    import winsound
    winsound.PlaySound("/P31Working/Sounds/TaDa", winsound.SND_ALIAS)

#def beethoven(): #doesn't work in Vista
    #"""
    #The first notes of his 5th symphony.
    #"""
    #import time, winsound
    #seconds = .03
    #pitch = 490
    #length = 200
    #winsound.Beep(pitch,length)
    #time.sleep(seconds)
    #winsound.Beep(pitch,length)
    #time.sleep(seconds)
    #winsound.Beep(pitch,length)

    #time.sleep(.05)
    #winsound.Beep(400,900)
    #time.sleep(.8)
    #winsound.MessageBeep()

def beethoven():
    """
    A clip of the first notes of his 5th symphony.
    """
    import winsound
    winsound.PlaySound("/P31Working/Sounds/DaDaDaDaaa", winsound.SND_ALIAS)


def add():
    x = "0"
    sum = 0
    while True:
        x = input("enter a number to add: ")
        if x == "":
            break
        if "," in x:
            x = x.replace(",","")
        if "." in x:
            x = float(x)
        else:
            x = int(x)
        sum += x
    print(numberCommas(sum))

def mult():
    x = "0"
    product = 1
    while True:
        x = input("enter a number to multiply: ")
        if x == "":
            break
        if "," in x:
            x = x.replace(",","")
        if "." in x:
            x = float(x)
        else:
            x = int(x)
        product *= x
    print(numberCommas(product))

def div():
    x = "0"
    y = "0"
    x = input("enter a number to be divided: ")
    if "," in x:
        x = x.replace(",","")
    if "." in x:
        x = float(x)
    else:
        x = int(x)

    y = input("enter the divisor: ")
    if "," in y:
        y = y.replace(",","")
    if "." in y:
        y = float(y)
    else:
        y = int(y)
    print("%.17g" % (x*1.0/y))

def tdstelecomer():
    print("using math.pow()")
    import math
    x = "0"
    y = "0"

    x = input("enter a number to raise to a power: ")
    if "," in x:
        x = x.replace(",","")
    if "." in x:
        x = float(x)
    else:
        x = int(x)

    y = input("enter the exponent: ")
    if "," in y:
        y = y.replace(",","")
    if "." in y:
        y = float(y)
    else:
        y = int(y)
    print("%.17g" % math.pow(x,y))

def decPow(n, power, precision=4):
    """
    Raise any real number to any power to any precision

    If power is negative, must be an integer.
    If n is negative, power must be an integer
    """
    from decimal import getcontext, Decimal as D
    getcontext().prec = precision
    return D(str(n))**D(str(power))

def stripCommas(s):
    """Strips commas from a string"""
    a = s.split(",")
    s = ''.join(a)
    return s

def fact(n, d=0):
    """
    Returns n! to d significant digits
    Set digits to 0 to return the full n! integer. I.e, use fact(n,0) or fact(n).
    """
    import gmpy2
    from mycalc import sig_digits

    if d == 0:
        return int(gmpy2.fac(n))
    elif d > 0:
        return float(sig_digits(gmpy2.fac(n),d))

def print_fact(n):
    from mycalc import intCommas, sci_notation
    import gmpy2
    m = int(gmpy2.fac(n))
    print("%d! = %s" % (n, intCommas(m)))
    print("=", sci_notation(m, 4))

def printTime(timeStart, timeEnd):
    from mycalc import hmsToText
    timeElapsed = timeEnd - timeStart
    if timeElapsed > 60:
        print("Time was", hmsToText(timeElapsed))
    else:
        print("Time was %.4g seconds" % timeElapsed)

def get_time(timeStart, timeEnd):
    from mycalc import hmsToText
    timeElapsed = timeEnd - timeStart
    if timeElapsed > 60:
        return "Time was", hmsToText(timeElapsed)
    else:
        return "Time was %.4g seconds" % timeElapsed


if __name__ == '__main__':
    import time
    assert(numberCommas('7657657.7554') == "7,657,657.7554")
    assert(intCommas(76576577554) == "76,576,577,554")
    assert(nextNPrimes(1000000000000,10) == ([1000000000039, 1000000000061, 1000000000063, 1000000000091,
                                              1000000000121, 1000000000163, 1000000000169, 1000000000177,
                                              1000000000189, 1000000000193]))
    assert get_time(1215322934.0398701, 1215322947.0320001) == ('Time was 12.99 seconds')
    assert get_time(1215323011.4567342, 1215323947.0320001) == ('Time was', '15 minutes, 36 seconds')
    assert get_time(1215312921.0054233, 1215322947.0320001) == ('Time was', '2 hours, 47 minutes, 6 seconds')
    assert(int_to_ordinal(19283743) == '19,283,743rd')
    assert(word_count("Now is the time for all good men to come to the aid of their party.") == 16)
    result = fact(10,4)
    #print("result:", result)
    e = float(result)/100000
    #print("e:", e)
    assert(result - e < fact(10,4) < result + e)
    assert fact(30,0) == 265252859812191058636308480000000

    #print(mpPow('34.5', '57.4', 31))