Finding number of Coprime tuples from $1$ to $N$

Question

Given $N$ Integers $A_1,A_2....A_N$, and a function $$F(i,j)=A_i*A_j mod P$$

$P =599*601$ both of which are prime.

I need to find out the number of integer 4-tuples $(a, b, c, d)$ there are such that $F(a, b), F(c, d)$ are co-prime and $ 1 ≤ a, b, c, d ≤ N$

I can only think of checking every pair of integers i.e brute force. Is there any way better than this ?

Answer 1

This answer is for the original version of the question. Some VBA for initial brute force attempt below using N = 1000. This been ran once on a laptop, and took > 15 mins to get to over 4 million for counttuples before process was stopped.

It is expected to take a significant time to run since requires at least $N^2$ calculations - eg probably a few hours for $N=1000$

Function Modulo(x as double, y as double, p as double) as Double

Modulo = x * y mod p

End Function

Main sub:

Public p as Double
Public a as double
Public b as double
Public c as double
Public d as double

Dim N as Long  
Dim dblGcd as Long
Dim mod_result_ab as Long
Dim mod_result_cd as Long
Dim count_tuples as Double
Dim Prime1 as Long
Dim Prime2 as Long
Dim answer1 as Variant

Sub Number_tuples()

N = 1000
Prime1 = 599
Prime2 = 601
P=Prime1*Prime2
Count_tuples=0

For a=1 to N
    For b=1 to N
        Mod_result_ab = modulo(a,b,p)    
        If mod_result_ab = 1 then
        Count_tuples = Count_tuples + N*N
    Else
        For c=1 to N
            For d=1 to N
               if d=1 then
                   count_tuples = count_tuples+1    
               Else
                   Mod_result_cd = modulo(c,d,p)    
                   if mod_result_cd = 1 then
                        count_tuples = count_tuples+1
                   else 
                       DblGcd = WorksheetFunction.Gcd(Arg1:=Mod_result_ab,Arg2:=Mod_result_cd)
                       if DblGcd = 1 then
                           Count_tuples=Count_tuples+1
                       End if
                   End if
               End if
             Next d
        Next c
    End if
Next b

Next a

Answer1=Msgbox ("Number of tuples is " & Count_tuples & " for " & N & " integers, for Prime1="&Prime1 & " and Prime2 = " & Prime2)

End Sub

Answer 2

I suggest the following approach for the revised question:

1) Put the list of integers into a 1D array (array1)

2) Get $N$ from the amount of elements in the array.

3) Calculate all non-unique possible values of $F(i,j)$ using array1, and put these into a 1D array (array2).

4) Using array2, derive unique value of $F(i,j)$, and put them into a 1D array (array3).

5) Using array3 and array2, calculate the frequency for each unique $F(i,j)$, and put unique $F(i,j)$ and its frequency into a 2D array (array4).

6) Review contents of array4 to pick up any patterns that can be coded for - to help with the next step. Eg For unique $F(i,j)$ with value of $1$, these all have a GCD of $1$ with all other $F(i,j)$ so counting them is easier.

7) Start with counttuples=0. Work out and add countuples for every occurence of $F(i,j)=1$ with another $F(i,j)$

8) For each occurence of $F(i,j)>1$, calculate GCD of that with every other $F(i,j)>1$ using the frequencies. If the GCD=1, then the values are coprime, so increment counttuples by 1.

Note: further efficiencies could be made to step 8) using concepts from number theory.

9) After step 8) is done, show what value of counttuples is to the user

Example - VBA code in: https://stackoverflow.com/questions/41852006/excel-vba-how-to-make-code-more-efficient-and-take-less-time