Solving euler problem 276

Question

i am trying to solve Euler problem 276

But... i am completely stuck. I need to find integer triplets $a$, $b$, $c$ such that $a \leq b \leq c$ and $a+b > c$ and $\gcd\bigl(a, (\gcd(b, c)\bigr) = 1$. also, $a+b+c$ must be ${}\leq 10$ million

brute force is not an option, it would take years to check all possible triplets. i can reduce the numbers a bit (a can only be ${}\leq \tfrac13$ of the perimeter, $b$ can not be ${}> \tfrac12$ perimeter, but this is far from enough.

i checked alcuin's sequence which tells me how many triangles can exist, but it includes those for which $\gcd(a, b, c)$ is different from one

i can already tell by checking for $a + b + c \leq 5000$ that the final number will be huge, so even generating valid triplets with near zero time/effort won't work. i need a way to know some partial sums.

however, i don't know how the things i'm looking for a called. i could use:

• $a$ function which generates values for $a$, $b$, $c$ such that $\gcd(a, b, c) = 1$
• a variant of alcuin's sequence for which $\gcd(a, b, c) = 1$

alternatively, i could use a function for this: https://oeis.org/A051493 as formula it only says "moebius transform of another sequence". what does this mean? how do i "read oeis pages"?

the main problem is runtime. usually i can break down the problem into smaller parts and reuse partial results, but i see no way how i can apply this strategy here. there is no recursion (that i can see) nor can i see any calculations that repeat.

Answer 1

Just a hint (giving a solution would be cheating):

1. The triplets with gcd of 1 are all triplets regardless of gcd, except those with a gcd of 2, or a gcd of 3, or a gcd of 4, ... or a gcd of n.

2. You get all triplets with a gcd of k and a sum ≤ n by taking all triplets with a gcd of 1 and a sum ≤ floor(n/k). and multiplying a, b, c by k.

Let f(n) be the number of triplets with a sum ≤ n. (1) or (2) give you a simple recursion formula for f(n). All you need to do is:

a. Whenever f(k) has been calculated, remember the result and don't calculate it again.

b. Observe that in your recursion formula you often calculate f(k) for small k very often. For example while calculating f(10,000,000), the recursion formula will tell you to subtract f(1) exactly 5,000,000 times.