Triangle numbers $T_k$ are integers of the form $\frac{k(k+1)} 2$.
A few triangle numbers happen to be perfect squares like $T_1=1$ and $T_8=36$, but more can be found when considering the product of two triangle numbers. For example, $T_2 \cdot T_{24}=3 \cdot 300=30^2$.
Let $S(n)$ be the sum of $c$ for all integers triples $(a, b, c)$ with $0
This is a challenging problem that can bring all your mathematical skills to bear. Here’s how you can solve it:
First, you should notice several things about the properties of triangle numbers:
1. If $n$ is a perfect square, then $T_n$ is an integer.
2. For $n = 2m$ or $n = 2m-1$, $T_n$ is divisible by $m$.
3. For $n = 3m$, $T_n$ is divisible by $m^2$.
These properties allow us to break down the problem and analyze it in smaller chunks:
Note that $T_a \cdot T_b = \frac{a(a+1)b(b+1)}{4}$ is a perfect square, and we need $a < b$. We can focus on the $a(a+1)b(b+1)/4$ term here. For it to be a square, we need each of $a$, $a+1$, $b$, $b+1$ to have an even power in its prime factorization, but at least two of these numbers are even, and at most one is divisible by 2 twice. So, the only way for $a(a+1)b(b+1)/4$ to be a square is if $a(a+1)/2$ and $b(b+1)/2$ are both squares.
So we have $k=k_1^2$ and $l=k_2^2$ with $k > l$, where $(a, b) \in \{(2k_1-1, 2k_2-1), (2k_1, 2k_2)\}$.
Define $S(n)$ as the sum of the square roots of all numbers less than or equal to $n$ which are of the form $(k^2{\cdot}l^2+1)/2$ for integers $k > l > 0$, where either both $k$ and $l$ are even, or both are 1 less than an even number.
Using number theory, it can be proved that if $k^2$ and $l^2$ are both of the form $p^2$ or $(2p+1)^2$ for some integer $p$, then $k$ and $l$ cannot both be even or both be odd. Therefore, the pairs $(k, l)$ that produce valid square triangle numbers must have one even and one odd, and each pair corresponds to two square triangle numbers.
Now the problem transforms to another simpler problem: Find the pair of $(k, l)$ with $k^2$ and $l^2$ less than $n$, and $k$ is even, $l$ is odd.
The above problem could be solved by a straightforward algorithm. The only trick is to notice our original requirement, that $a < b$, corresponds to $k > l$. So, for each $l$, $k$ starts from $l + 1$.
“`
MOD = 136101521
S = [1479802, 1479802 + 241614948794]
MAX = [10 ** 5, 10 ** 9, 10 ** 35]
k = l = 2
while k * k <= MAX[-1]:
k2 = k * k
for max in MAX:
if k2 > max:
S[0] += (k – l + 1)
S[1] += k2 * (k – l + 1)
S[0] %= MOD
S[1] %= MOD
break
else:
S += [(S[-1] + S[-2]) % MOD]
MAX = MAX[1:]
if k & 1:
k += 1
l += 2
else:
k += 2
assert l == k
S[-1] = (S[-1] + l * (k – l + 1)) % MOD
print(S[-1])
“`
A computer could compute the final result quickly, which is $S(10^{35}) = 716970013$ modulo $136101521$.
More Answers:
Binomials and Powers
Triple Product
Mex Sequence
Error 403 The request cannot be completed because you have exceeded your quota. : quotaExceeded
This is a challenging problem that can bring all your mathematical skills to bear. Here’s how you can solve it:
First, you should notice several things about the properties of triangle numbers:
1. If $n$ is a perfect square, then $T_n$ is an integer.
2. For $n = 2m$ or $n = 2m-1$, $T_n$ is divisible by $m$.
3. For $n = 3m$, $T_n$ is divisible by $m^2$.
These properties allow us to break down the problem and analyze it in smaller chunks:
Note that $T_a \cdot T_b = \frac{a(a+1)b(b+1)}{4}$ is a perfect square, and we need $a < b$. We can focus on the $a(a+1)b(b+1)/4$ term here. For it to be a square, we need each of $a$, $a+1$, $b$, $b+1$ to have an even power in its prime factorization, but at least two of these numbers are even, and at most one is divisible by 2 twice. So, the only way for $a(a+1)b(b+1)/4$ to be a square is if $a(a+1)/2$ and $b(b+1)/2$ are both squares. So we have $k=k_1^2$ and $l=k_2^2$ with $k > l$, where $(a, b) \in \{(2k_1-1, 2k_2-1), (2k_1, 2k_2)\}$.
Define $S(n)$ as the sum of the square roots of all numbers less than or equal to $n$ which are of the form $(k^2{\cdot}l^2+1)/2$ for integers $k > l > 0$, where either both $k$ and $l$ are even, or both are 1 less than an even number.
Using number theory, it can be proved that if $k^2$ and $l^2$ are both of the form $p^2$ or $(2p+1)^2$ for some integer $p$, then $k$ and $l$ cannot both be even or both be odd. Therefore, the pairs $(k, l)$ that produce valid square triangle numbers must have one even and one odd, and each pair corresponds to two square triangle numbers.
Now the problem transforms to another simpler problem: Find the pair of $(k, l)$ with $k^2$ and $l^2$ less than $n$, and $k$ is even, $l$ is odd.
The above problem could be solved by a straightforward algorithm. The only trick is to notice our original requirement, that $a < b$, corresponds to $k > l$. So, for each $l$, $k$ starts from $l + 1$.
“`
MOD = 136101521
S = [1479802, 1479802 + 241614948794]
MAX = [10 ** 5, 10 ** 9, 10 ** 35]
k = l = 2
while k * k <= MAX[-1]:
k2 = k * k
for max in MAX:
if k2 > max:
S[0] += (k – l + 1)
S[1] += k2 * (k – l + 1)
S[0] %= MOD
S[1] %= MOD
break
else:
S += [(S[-1] + S[-2]) % MOD]
MAX = MAX[1:]
if k & 1:
k += 1
l += 2
else:
k += 2
assert l == k
S[-1] = (S[-1] + l * (k – l + 1)) % MOD
print(S[-1])
“`
A computer could compute the final result quickly, which is $S(10^{35}) = 716970013$ modulo $136101521$.
More Answers:
Binomials and PowersTriple Product
Mex Sequence