Count pairwise coprime triples such that the maximum number of the triple is not greater than N

Question

Problem Statement:

Given N you are to count the number of pairwise coprime triples which satisfy $1≤a,b,c≤N$.

Example:

For example N=3, valid triples are (1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,1,3),(1,3,1),(3,1,1),(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,2,1),(3,1,2)

Hence answer for N=3 is 13.

Source: own problem.

Solution so far:

I have found the oeis series A256390 but Reyna & Heyman's work seems too overwhelming for me to understand.If someone can explain that in simple terms with an example it would be great or if you have an alternate solution you are welcome too.

I have found a solution. I will move the following to answer once I have better understanding. For now documenting my understandings here:

I found a code (modified) This is a deterministic approach and had nothing to do with Reyna & Heyman's approximation. For N=6 answer should be 64 .

Now let's see his implementation. He's constructing graph with just 7 edges

I:mu[1] * f[1] * f[1] * f[1]=216
I:mu[2] * f[2] * f[2] * f[2]=-27
I:mu[3] * f[3] * f[3] * f[3]=-8
I:mu[4] * f[4] * f[4] * f[4]=0
I:mu[5] * f[5] * f[5] * f[5]=-1
I:mu[6] * f[6] * f[6] * f[6]=1
3B:(mu[1] * f[2] + mu[2] * f[1]) * f[2] * f[2]=-27
3B:(mu[1] * f[3] + mu[3] * f[1]) * f[3] * f[3]=-16
3B:(mu[1] * f[5] + mu[5] * f[1]) * f[5] * f[5]=-5
3B:(mu[1] * f[6] + mu[6] * f[1]) * f[6] * f[6]=7
3B:(mu[2] * f[3] + mu[3] * f[2]) * f[6] * f[6]=-5
3B:(mu[2] * f[6] + mu[6] * f[2]) * f[6] * f[6]=2
3B:(mu[3] * f[6] + mu[6] * f[3]) * f[6] * f[6]=1
6A:mu[3] * mu[2] * mu[1] * 1 * 3 * mark[1]=6
6A:mu[6] * mu[2] * mu[1] * 1 * 3 * mark[1]=-3
6A:mu[6] * mu[3] * mu[1] * 1 * 2 * mark[1]=-2
6A:mu[6] * mu[3] * mu[2] * 1 * 1 * mark[2]=1

Ans=(216-27-8+0-1+1)+3*(-27-16-5+7-5+2+1)+6*(6-3-2+1)=64

gcd(a,b,c)=1 Case:

I have labelled 3 sections of the program with I:,3B:,6A: tags. For gcd(a,b,c)=1 problem I: tags are after which we stop. We don't need 3B: or 6A: tags. We neither need to construct the graph nor traverse it. And it indeed clocks less than a sec for n=1000000.

But for pairwise gcd=1 problem we need to exclude/include more scenarios.So lets proceed.

gcd(a,b)>1 or gcd(b,c)>1 or gcd(c,a)>1 Case:

For each of the items labelled 3B: he adds an edge from first mu node to first f node with weight equal to either of first f[i] value outside the first pathesis.

in 3B:(mu[1] * f[2] + mu[2] * f[1]) * f[2] * f[2] (mu[1] * f[2] + mu[2] * f[1]) part is for selecting an item in a column which is not multiple of 2.wile the other two columns have multiple of 2.3 in 3B is C(3 1) for permuting this column either at start , middle or end.

Essentially for all pair of factors of i we draw edge from smaller factor to larger factor with weight f[i].If the edge already exist we skip that. For 6 all pair of factors are:

1,2  =>already edge exists with weight f[2] so will skip
1,3  =>already edge exists with weight f[3] so will skip
1,6  =>draw edge with weight f[6]
2,3  =>draw edge with weight f[6]
2,6  =>draw edge with weight f[6]
3,6  =>draw edge with weight f[6]

Tiangle counting:

Note Neither for I: labeled values nor for 3B: labeled values the graph is required. The graph is being constructed for 6A: values

mark[c] denotes wheather it has been traversed earlier as first distance. if yes it has value equal to weight of edge used to traverse to it.

Before traversing node a, for each edge incident on a we mark the source node in by weight and clear it once traversing a case is complete. So mark[c] to have a valid value node x has to be node a. Hence a triangle.

w1 * w2 * mark[c] is equivalent to w1 * w2 * wc

The overall Time complexity = O(n+E +E^1.5)

=$O(n+nlogn+(nlogn)^{1.5})$

for n=1000000, its around = $O(n+10n+430n)$ = $4*10^8$

Since median of factors of a number is its square root we managed to get a sparse graph, so time complexity is order of $(nlogn)^{1.5}$ . If graph was dense ie $E=n^2$ then triangle finding is $O(n^3)$ when we arrive at complexity similar to @mike-earnest 's answer. Conversely if you substitute $n^{0.5}$ for $n$ in @mike-earnest 's answer you get complexity similar to this.

Answer 1

The OEIS formula is mistaken. To fix it, replace all instances of gcd with lcm. This code prints 13 when run.

from math import gcd

def lcm(a,b):
    return a * b // gcd(a, b)

mu = [0, 1, -1, -1]

N = 3    
accum = 0
for a in range(1, N + 1):
    for b in range(1, N + 1):
        for c in range(1, N + 1):
            accum += (
                  mu[a] 
                * mu[b] 
                * mu[c] 
                * (N // lcm(a, b))
                * (N // lcm(a, c))
                * (N // lcm(b, c))
                )
print('number of triples = ', accum)