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

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 ?

• You say P is a given non-prime number - what is its value? Jan 11 '17 at 15:58
• Brute forcing (going through every possible solution)is one option, however I think reading up on and applying some concepts & / properties of number theory into code would make it more efficiency and take less time. Jan 11 '17 at 16:02
• @unseen_rider I didn't thought it would matter but If it matters then its $(599 * 601)$ Jan 11 '17 at 16:03
• Ok thanks. Please update your question with this firstly. Jan 11 '17 at 16:41
• I suggest you start with a brute force algorithm, note it's running time, then research, try other ways, and refine your algorithm. Jan 11 '17 at 22:23

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

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

• Thanks, I get the brute force but what about those $N$ integers ? I missed writing those integers after N. Please see the updated the question. Jan 12 '17 at 16:15
• My code should cater for that, for $N$ up to $1000$ Jan 12 '17 at 16:21
• Thanks. I get that it can work for $N < 1000$ but where should I include those $N$ integers in the brute-force code ? Jan 12 '17 at 16:31
• At the line "N=1000" for the number of integers you are using Jan 12 '17 at 16:34
• Suppose $N=4$ and integers are $A_1=10,A_2=100,A_3=1000,A_4=10000$. Can you explain now where these integers are used in code ? Jan 12 '17 at 16:51

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