Im Bored

I wasn't smart enough to do the math, but I worked pretty hard on this problem, so I want to show my work.

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

from mpmath import *

# mpmath doesn't support round(), so roll our own 
def mp_round(x):
    if frac(x) > .5: ret = ceil(x)
    else: ret = floor(x)
    return ret

# P(n) is the number of integer triangles with perimeter less than n
# see https://oeis.org/A001400
def P(n):
    return  int(mp_round(((n+1)**3 + 3*(n+1)**2 - 9*(n+1)*((n+1)%2))/144))

mp.dps = 300000
n = pow(mpf(7), 100000)
digit_sum = sum(map(int, list(str(P(n)))))
print(digit_sum)

# 1139929
# 0.817 seconds

Let $a,b,c$ be the side lengths of a triangle. Without loss of generality, let $a \le b \le c$ . Hence, for each tuple of $a,b,c$ to represent a unique triangle, $a,b,c$ must satisfy the following inequalities:

$\begin{aligned} &a \le b \le c \quad \rightarrow \quad a = b + k_0,\quad c = b + k_1 \\ &a + b < c \quad \rightarrow \quad a + b = c + 1 + k_2\\ \end{aligned}$

Where $k_0, k_1, k_2$ are non-negative integers. Rearranging the above yields the substitution below:

$\begin{aligned} c &= k_0 + 2k_1 + k_2 + 1 \\ b &= k_0 + k_1 + k_2 + 1 \\ a &= k_1 + k_2 + 1 \\ \end{aligned}$

$P(n)$ can hence be rewritten as the number of non-negative solutions to the diophantine equation $a + b + c = 2k_0 + 4k_1 + 3k_2 + 3 \le n$ . This can be computed recursively via the method shown here . This yields:

\[ P(n)=\begin{cases}
\frac{1}{8}(12k^3 - 6k^2 - (-1)^k + 1) & \text{ if } n-3 \equiv 0 \text{ mod } 6 \\ \frac{1}{2}(3k^3 - k) & \text{ if } n-3 \equiv 1 \text{ mod } 6 \\ \frac{1}{8}(12k^3 + 6k^2 + (-1)^k - 1) & \text{ if } n-3 \equiv 2 \text{ mod } 6 \\ \frac{1}{2}(3k^3 + 3k^2) & \text{ if } n-3 \equiv 3 \text{ mod } 6 \\ \frac{1}{8}(12k^3 + 18k^2 + 8k - (-1)^k + 1) & \text{ if } n-3 \equiv 4\text{ mod } 6 \\ \frac{1}{2}(3(k+1)^3 - 3(k+1)^2) & \text{ if } n-3 \equiv 5 \text{ mod } 6 \end{cases}

\text{ Where } k = \left\lfloor \frac{n-3}{6} \right\rfloor + 1 \]

Of course it is not required to derive all 6 cases for the answer but for the sake of completeness I did. My python code to compute the final answer is as follows:

 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

import time

def P(n):

    f_0 = lambda n: (12*n**3 - 6*n**2 - (-1)**n + 1)//8
    f_1 = lambda n: (3*n**3 - n)//2
    f_2 = lambda n: (12*n**3 + 6*n**2 + (-1)**n - 1)//8
    f_3 = lambda n: (3*n**3 + 3*n**2)//2
    f_4 = lambda n: (12*n**3 + 18*n**2 + 8*n - (-1)**n + 1)//8
    f_5 = lambda n: (3*(n+1)**3 - 3*(n+1)**2)//2

    n -= 3

    return [f_0, f_1, f_2, f_3, f_4, f_5][n%6](n//6 + 1)

assert P(3) == 1
assert P(4) == 1
assert P(5) == 2
assert P(6) == 3
assert P(25) == 136

digit_sum = lambda n: sum([int(i) for i in str(n)])

t = time.time()
print("Answer:", digit_sum(P(7**100000)))
print("Time Taken: {}s".format(time.time() - t))

# Answer: 1139929
# Time Taken: 1.5831763744354248s