Day031NumberSearch.sagews

Author: Vincent J. Matsko
Date: 13 March 2016, Day031
Post: Number Searches

# Recursive pair of functions to find prime factors (including repetitions).
# test is the factor to check.
# If n is divisible by test, try again!  It may be a repeated prime factor.
# Otherwise, recurse with the current n (which keeps getting smaller as more factors are found),
# but increment test to test + 1.
# Don't use for numbers too large - the recursive depth will be exceeded!
def primefactorsaux(n, factorlist, test):
    if n == 1:
        return factorlist
    elif n % test == 0:
        factorlist.append(test);
        return primefactorsaux(n/test, factorlist, test)
    else:
        return primefactorsaux (n, factorlist, test + 1)
    
def primefactors(n):
    return primefactorsaux(n, [], 2)

primefactors(123456)

[2, 2, 2, 2, 2, 2, 3, 643]

# Iterative version.
# Note the similarity to the recursive version.
# test becomes testfactor here, and is a local variable (rather than an argument to a function).
def factorize (n):
    factorlist = [];
    testfactor = 2;
    currentn = n;
    done = False;
    while not done:
        if currentn == 1:
            done = True
        elif currentn % testfactor == 0:
            factorlist.append(testfactor)
            currentn = currentn / testfactor
        else:
            testfactor += 1
    return factorlist

factorize(123456789)

[3, 3, 3607, 3803]

# This is helpful in solving Number Search puzzles!
def tobase(n,b):
    result = ""
    place = floor(log(n,b))              # Highest power of b less than n.
    nleft = n                            # Keeps track of what we still need to convert.
    while place >= 0:
        digit = floor(nleft / b^place)   # Leading digit of what's left.
        result = result + str(digit)     # Adds this digit to the number (as a string). 
        nleft = nleft - digit * b^place  # Finds what's left to convert.
        place = place - 1                # Moves one place to the right.
    return result

tobase(1024,3)

'1101221'