Algebra or Computer Science? (II)

The problem asks for $999999999$ but let's solve for a general $n$ . Suppose $S$ is the set of all numbers that divide $n$ different from $1$ and itself, we could choose any of them to be the first number we write and there are $|S|$ numbers we can choose. Now, let's say that $f(n)$ is the number of ways you can write $n$ and $s_i$ is a member of our set, for each $s_i$ we choose to be the first one we use, there are $f({n \over s_i}) + 1$ ways of writing the number being that you could write $s_i \cdot {n \over s_i}$ or $s_i$ times any of the ways of witting ${n \over s_i}$ . This gets us to the formula:

$f(n) = | S | + \sum_{s_i \in S} f({n \over s_i})$

Now that we got the recursive relation is time to get the base case, and for this is quite simple, there are $0$ ways of writing any prime number as a multiple os $2$ numbers different than $1$ and itself so if $n$ is prime $f(n) = 0$ . Since we are only dividing $n$ on our algorithm, we eventually get to a prime input $n$ . Here is my python implementation of the algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

def prime_factorization(n):
    """Returns a divtionary with the prime facotrs of
    n and it's prime factorization
    """
    if n == 1:
        return {1:1}

    i = 2
    k = n**0.5
    prime_factors = {}

    while i <= k:
        if n%i == 0:
            n //= i
            k = n**0.5
            prime_factors[i] = prime_factors[i] + 1 if i in prime_factors else 1
            i -= 1

        i += 1
    if n != 1:
        prime_factors[n] = prime_factors[n] + 1 if n in prime_factors else 1

    return prime_factors


def find_factors(prime_factors, depth):
    """Uses the result of prime_factorization to
    recursivelly find all the factors of a number"""
    if depth == len(prime_factors):
        return [1]

    factors = []
    key = list(prime_factors.keys())[depth]
    for i in range(prime_factors[key] + 1):
        for j in find_factors(prime_factors, depth+1):
            factors.append(j*(key**i))

    return factors

def factor(n):
    """Returns a sorted list of all factors of n"""
    prime_factors = prime_factorization(n)
    factors = find_factors(prime_factors, 0)

    return sorted(factors)

def f(n):
    """
    Let's calculate how in many ways can we write a number
    as a multiple of it's factors.
    """

    # First we get a list of all factors of N excluding 1 and itself
    factors = factor(n)[1:-1]

    _sum = len(factors)
    for number in factors:
        _sum += f(n//number)

    return _sum


print(f(999999999))

Here is how I solved the problem such that S(Prime)=0 and S(Composite) is sum of number of unique factors and S of composite after dividing by each factor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

# S calculates the number of ways in which we get n by multiplying two or more numbers
def S(n, D = {}):
    if n in D:
        return D[n]
    SUM = 0
    for i in range(2, n//2+1):
        if not n%i:
            if isPrime(n//i):
                SUM += 1
            else:
                SUM += 1+S(n//i)
    D[n] = SUM
    return D[n]

# Function validation and finding required answer
print (S(20) == 7, S(18) == 7, S(999999999)) # True True 367