Sum_Of_Divisors

SumOfDivisors.py

import sys
import math

# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.

n = int(input())

# Write an action using print
# To debug: print("Debug messages...", file=sys.stderr)
is_Debug_Mode = (
    True
    #False
)
print(
        "n:{}".format(
            n), file=sys.stderr
    ) if is_Debug_Mode else None
"""
d(1)={1},
d(2)={1,2}, <- prime, even
d(3)={1,3},
d(4)={1,2,4},
d(5)={1,5}, <- prime, odd
d(6)={1,2,3,6},
d(7)={1,7}, <- prime, odd
d(8)={1,2,4,8},
d(9)={1,3,9},
d(10)={1,2,5,10},
d(11)={1,11},
d(12)={1,2,3,4,6,12},
d(13)={1,13},
d(14)={1,2,7,14},
d(15)={1,3,5,15},
d(16)={1,2,4,8,16},
d(17)={1,17},
...
(1) <- (all) have all
(2) <- every even or n // 2 or floor(n/2)
(3) <- every third or floor(n/3)
sum(up to 8) = 1*8 + (8 / 2 * 2 == 8) + (3 + 3) + (4 + 4) + (5) + (6) + (7) + (8) =
16 + 16 + 6 + 18 = 32 + 18 + 6 = 
56 = 
(8-1) * 8 ==
8*(1+1+1+1)+(7)+(6)*2+(5)
8*4+(8-1)+(8-2)*2+(8/2+1)
sum(up to 10) = 87 == 1*10 + (10 / 2 * 2 == 10) + (3+3+3<10) + (4+4<10) + (5*2==10) +
(6<10) + (7<10) + (8<10) + (9<10) + (10==10) ==
10*(1+1+1+1)+9*(1+1)+8*(1+1)+7+(6>=10/2+1)=
10*4+(10-1)*2+(10-2)*2+(10/2+2)+(10/2+1)
"""  
# @tailrec
def d_Sum_Recursive(
    limit: int,
    component: int,# = limit
    result_Accum: int# = 0
) -> int:
    """
    >>> n = 994
    >>> d_Sum(n, n, 0)
    813171
    >>> n = 995
    RuntimeError: maximum recursion depth exceeded in comparison
    """
    if component < 1 or component == 0:
        # base case
        return result_Accum
    else:  
        # recursive step
        assert component != 0 
        assert type(component) is int 
        assert type(result_Accum) is int 
        result_Accum += component * (limit // component)
        assert type(result_Accum) is int 
        assert result_Accum > 0
        
        return d_Sum_Recursive(
            limit = limit,
            component = component - 1,
            result_Accum = result_Accum
        )


def d_Sum_Iterative(
    limit: int
) -> int:
    """
    """
    component = limit
    result_Accum = 0
    
    while component > 0:
        result_Accum += component * (limit // component)
        component -= 1
        
    return result_Accum

#d_Sum(n, n, 0)
sum = d_Sum_Iterative(limit = n)

print(sum)