Skip to main content
added 39 characters in body
Source Link
MT0
  • 1k
  • 5
  • 8

Given that: \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$

Since \$a\$, \$b\$ and \$c\$ have no common divisors then it also follows that: \$GCD(rad(a),rad(b))=GCD(rad(a),rad(c))=GCD(rad(b),rad(c))=1\$

And: \$rad(abc) = rad(a)*rad(b)*rad(c)\$.


Since \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$ then when \$a\$, \$b\$ and \$c\$ are all even then \$GCD(a,b)>=2\$ so you can skip all the even \$a\$ values if \$c\$ is also even which eliminates a quarter of the checks that you need to do.

You can simplify the final part of the code to:

    for c in range(2, limit):
        rc = rad[c]
        if rc == c:
            continue
        step = 1 if c%2 == 1 else 2
        for a in range(1, (c + 1) // 2, step):
            ra = rad[a]
            rb = rad[c - a]
            rc = rad[c]
            if ra * rb * rc < c and math.gcd(ra, rb) == 1:
                # print(a, c - a, c)
                answer += c

Given that: \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$

Since \$a\$, \$b\$ and \$c\$ have no common divisors then it also follows that: \$GCD(rad(a),rad(b))=GCD(rad(a),rad(c))=GCD(rad(b),rad(c))=1\$

And: \$rad(abc) = rad(a)*rad(b)*rad(c)\$.


Since \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$ then when \$a\$, \$b\$ and \$c\$ are all even then \$GCD(a,b)>=2\$ so you can skip all the even \$a\$ values if \$c\$ is also even which eliminates a quarter of the checks that you need to do.

You can simplify the final part of the code to:

    for c in range(2, limit):
        step = 1 if c%2 == 1 else 2
        for a in range(1, (c + 1) // 2, step):
            ra = rad[a]
            rb = rad[c - a]
            rc = rad[c]
            if ra * rb * rc < c and math.gcd(ra, rb) == 1:
                # print(a, c - a, c)
                answer += c

Given that: \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$

Since \$a\$, \$b\$ and \$c\$ have no common divisors then it also follows that: \$GCD(rad(a),rad(b))=GCD(rad(a),rad(c))=GCD(rad(b),rad(c))=1\$

And: \$rad(abc) = rad(a)*rad(b)*rad(c)\$.


Since \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$ then when \$a\$, \$b\$ and \$c\$ are all even then \$GCD(a,b)>=2\$ so you can skip all the even \$a\$ values if \$c\$ is also even which eliminates a quarter of the checks that you need to do.

You can simplify the final part of the code to:

    for c in range(2, limit):
        rc = rad[c]
        if rc == c:
            continue
        step = 1 if c%2 == 1 else 2
        for a in range(1, (c + 1) // 2, step):
            ra = rad[a]
            rb = rad[c - a]
            if ra * rb * rc < c and math.gcd(ra, rb) == 1:
                # print(a, c - a, c)
                answer += c
added 1 character in body
Source Link
MT0
  • 1k
  • 5
  • 8

Given that: \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$

Since \$a\$, \$b\$ and \$c\$ have no common divisors then it also follows that: \$GCD(rad(a),rad(b))=GCD(rad(a),rad(c))=GCD(rad(b),rad(c))=1\$

And: \$rad(abc) = rad(a)*rad(b)*rad(c)\$.


Since \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$ then when \$a\$, \$b\$ and \$c\$ are all even then \$GCD(a,b)>=2\$ so you can skip all the even \$a\$ values if \$c\$ is also even which eliminates a quarter of the checks that you need to do.

You can simplify the final part of the code to:

    for c in range(2, limit):
        step = 1 if c%2 == 1 else 2
        for a in range(1, (c + 1) // 2, step):
            ra = rad[a]
            rb = rad[c - a]
            rc = rad[c]
            if ra * rb * rc < c and math.gcd(ra, rb) === 1:
                # print(a, bc - a, c)
                answer += c

Given that: \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$

Since \$a\$, \$b\$ and \$c\$ have no common divisors then it also follows that: \$GCD(rad(a),rad(b))=GCD(rad(a),rad(c))=GCD(rad(b),rad(c))=1\$

And: \$rad(abc) = rad(a)*rad(b)*rad(c)\$.


Since \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$ then when \$a\$, \$b\$ and \$c\$ are all even then \$GCD(a,b)>=2\$ so you can skip all the even \$a\$ values if \$c\$ is also even which eliminates a quarter of the checks that you need to do.

You can simplify the final part of the code to:

    for c in range(limit):
        step = 1 if c%2 == 1 else 2
        for a in range(1, (c + 1) // 2, step):
            ra = rad[a]
            rb = rad[c - a]
            rc = rad[c]
            if ra * rb * rc < c and math.gcd(ra, rb) = 1:
                # print(a, b, c)
                answer += c

Given that: \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$

Since \$a\$, \$b\$ and \$c\$ have no common divisors then it also follows that: \$GCD(rad(a),rad(b))=GCD(rad(a),rad(c))=GCD(rad(b),rad(c))=1\$

And: \$rad(abc) = rad(a)*rad(b)*rad(c)\$.


Since \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$ then when \$a\$, \$b\$ and \$c\$ are all even then \$GCD(a,b)>=2\$ so you can skip all the even \$a\$ values if \$c\$ is also even which eliminates a quarter of the checks that you need to do.

You can simplify the final part of the code to:

    for c in range(2, limit):
        step = 1 if c%2 == 1 else 2
        for a in range(1, (c + 1) // 2, step):
            ra = rad[a]
            rb = rad[c - a]
            rc = rad[c]
            if ra * rb * rc < c and math.gcd(ra, rb) == 1:
                # print(a, c - a, c)
                answer += c
Source Link
MT0
  • 1k
  • 5
  • 8

Given that: \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$

Since \$a\$, \$b\$ and \$c\$ have no common divisors then it also follows that: \$GCD(rad(a),rad(b))=GCD(rad(a),rad(c))=GCD(rad(b),rad(c))=1\$

And: \$rad(abc) = rad(a)*rad(b)*rad(c)\$.


Since \$GCD(a,b)=GCD(a,c)=GCD(b,c)=1\$ then when \$a\$, \$b\$ and \$c\$ are all even then \$GCD(a,b)>=2\$ so you can skip all the even \$a\$ values if \$c\$ is also even which eliminates a quarter of the checks that you need to do.

You can simplify the final part of the code to:

    for c in range(limit):
        step = 1 if c%2 == 1 else 2
        for a in range(1, (c + 1) // 2, step):
            ra = rad[a]
            rb = rad[c - a]
            rc = rad[c]
            if ra * rb * rc < c and math.gcd(ra, rb) = 1:
                # print(a, b, c)
                answer += c