smoothnumbers.py

# author Jeffrey Kozik

import random
import math

devMode = False
def prin(log):
    if(devMode):
        print(log)

def addZeros(array, length):
    for num in range(len(array), length):
        array.insert(0, '0')
    return array

def decimalNumberToBinaryArray(decimal_number):
    binary_string = bin(decimal_number)[2:]
    binary_array = []
    for char in binary_string:
        binary_array.append(char)
    return binary_array

def decimalNumbersToBinaryArrays(max_decimal_number):
    binary_arrays = []
    max_decimal_number_binary_array = decimalNumberToBinaryArray(max_decimal_number)
    binary_arrays.append(max_decimal_number_binary_array)
    for decimal_number in range(0, max_decimal_number):
        binary_arrays.append(addZeros(decimalNumberToBinaryArray(decimal_number), len(max_decimal_number_binary_array)))
    prin("BINARY ARRAYS: ")
    for binary_array in binary_arrays:
        for digit in binary_array:
            prin(digit)
        prin("")
    return binary_arrays

def multiplyAllCombos(array, max_decimal_number):
    all_combos_array = []
    binary_arrays = decimalNumbersToBinaryArrays(max_decimal_number)
    # print("binary_arrays", binary_arrays)
    for count, binary_array in enumerate(binary_arrays):
        this_result = 1
        total = 0
        for i in range(0, len(binary_array)):
            if(binary_array[i] == "1"):
                total += 1
                this_result *= array[i]
        if(total > 1):
            all_combos_array.append([this_result, binary_array])
    prin("COMBOS")
    for combo in all_combos_array:
        prin(combo)
    return all_combos_array

def isSquare(num):
    return math.sqrt(num).is_integer()

def check(array, num):
    newArray = array[:(num + 1)]
    for combo in multiplyAllCombos(newArray, (2**len(newArray)) - 1):
        if(isSquare(combo[0])):
            return num

def calculateN(x):
    array = []
    for num in range(0, x):
        array.append(random.randrange(1, x))
    prin("ARRAY")
    for num in array:
        prin(num)
    # print("array", array)
    for num in range(1, x + 1):
        prin("TESTING: ")
        prin(num)
        if (check(array, num)):
            prin("NUMMM")
            print(num)
            print("smoothness", Lx1overSqrt2(x))
            if(findSmooth):
                findSmoothSubsequence(array, Lx1overSqrt2(x))
            return num

def findSmoothSubsequence(array, smoothness):
    newArray = []
    for count,element in enumerate(array):
        # print(count)
        if isSmooth(smoothness, element):
            newArray.append(element)
    print("AMOUNT", (2**len(newArray)) - 1)
    for combo in multiplyAllCombos(newArray, (2**len(newArray)) - 1):
        if(isSquare(combo[0])):
            print("combo[0]", combo[0])
            # binary_arrays = decimalNumbersToBinaryArrays((2**len(array)) - 1)
            print("THIS COMB", combo[1])
            subsarray = []
            for count,c in enumerate(combo[1]):
                if c == '1':
                    subsarray.append(newArray[count])
            print("subsarray", subsarray)
            # print("THIS COMB", combo)
            return combo

def calcBigN(x, numTimes):
    n = 0
    for num in range(0, numTimes):
        result = calculateN(x)
        if(result > n):
            n = result
    print("EXPERIMENTAL N")
    print(n)
    return n

def Lx(x):
    return (2.718281828 ** math.sqrt(math.log(x, 10) * math.log(math.log(x, 10), 10)))

def LxSqrt2(x):
    return Lx(x) ** math.sqrt(2)

def Lx1overSqrt2(x):
    return Lx(x) ** (1/math.sqrt(2))

def isSmooth(s, x):
    return largestPrimeFactor(x) <= s

def largestPrimeFactor(x):
    primeFactors = primeFactor(x)
    # print("x", x)
    # print("primeFactors", primeFactors)
    return primeFactors[len(primeFactors) - 1]

def factor(x):
    factors_array = []
    for num in range(1, x + 1):
        if((x / num).is_integer()):
            factors_array.append(num)
    # print(factors_array)
    return factors_array

def isPrime(x):
    return(len(factor(x)) <= 2)

def primeFactor(x):
    return(primeFactorHelper(x, []))

def primeFactorHelper(x, array):
    factor_array = factor(x)
    if(isPrime(factor_array[(len(factor_array) - 1)])):
        return(factor_array)
    factor_array = factor_array[:(len(factor_array) - 1)]
    for thisFactor in factor_array:
        if (isPrime(thisFactor) and (not thisFactor in array)):
            array.append(thisFactor)
        else:
            returnedArray = primeFactorHelper(thisFactor, array)
            for element in returnedArray:
                if (not element in array):
                    array.append(element)
    return array

findSmooth = True
def mainFunction(x, numTrials):
    calcBigN(x, numTrials)
    print("THEORETICAL N:")
    print(LxSqrt2(x))
    print("this", Lx1overSqrt2(x))

mainFunction(1000, 5)
# print(primeFactor(17))