1
$\begingroup$

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 ?

$\endgroup$
9
  • $\begingroup$ You say P is a given non-prime number - what is its value? $\endgroup$ Jan 11 '17 at 15:58
  • $\begingroup$ 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. $\endgroup$ Jan 11 '17 at 16:02
  • $\begingroup$ @unseen_rider I didn't thought it would matter but If it matters then its $(599 * 601)$ $\endgroup$
    – sammy
    Jan 11 '17 at 16:03
  • 1
    $\begingroup$ Ok thanks. Please update your question with this firstly. $\endgroup$ Jan 11 '17 at 16:41
  • 1
    $\begingroup$ I suggest you start with a brute force algorithm, note it's running time, then research, try other ways, and refine your algorithm. $\endgroup$ Jan 11 '17 at 22:23
2
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$
    – sammy
    Jan 12 '17 at 16:15
  • $\begingroup$ My code should cater for that, for $N$ up to $1000$ $\endgroup$ Jan 12 '17 at 16:21
  • $\begingroup$ Thanks. I get that it can work for $N < 1000$ but where should I include those $N$ integers in the brute-force code ? $\endgroup$
    – sammy
    Jan 12 '17 at 16:31
  • $\begingroup$ At the line "N=1000" for the number of integers you are using $\endgroup$ Jan 12 '17 at 16:34
  • $\begingroup$ 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 ? $\endgroup$
    – sammy
    Jan 12 '17 at 16:51
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.