Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
common divisor selector

Subject: common divisor selector

From: Sam Van der Jeught

Date: 6 Mar, 2009 20:02:42

Message: 1 of 6

Hi all,
is there an easy (= low calculation intensity) way to check how many common divisors the integers in a given array have?
e.g. :(2,3,5,7,10,15) ==> (2,5 and 10| 3,5 and 15 )= 6 times
Thanks!

Sam

Subject: common divisor selector

From: Roger Stafford

Date: 6 Mar, 2009 20:53:01

Message: 2 of 6

Sam Van der Jeught <sam_vanderjeught@hotmail.com> wrote in message <25941464.1236369793215.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hi all,
> is there an easy (= low calculation intensity) way to check how many common divisors the integers in a given array have?
> e.g. :(2,3,5,7,10,15) ==> (2,5 and 10| 3,5 and 15 )= 6 times
> Thanks!
>
> Sam

  Your description is not at all clear, Sam. Taking your question literally there would be no common divisors at all in your example array except the number 1. Suppose the array consists of just the two elements [60,90]. As a pair they possess six different common divisors excluding 1. What would your count be and how is it compatible with having counted the 5 in your example twice? You need to explain things much more carefully so that others can understand what it is you are asking. We aren't mind readers.

Roger Stafford

Subject: common divisor selector

From: Sam Van der Jeught

Date: 7 Mar, 2009 00:04:52

Message: 3 of 6

Hello Roger,

You're right, I'll try to explain it in more detail.
What I want, ultimately, is a measure for how many 'incidents' occur. By incidents I mean each time two numbers share at least one divisor (not 1). It doesn't matter if they have more than one. So that's why the 5 in my example is counted twice: it shares a divisor greater then one with both 10 and 15, leading to two incidents.
The count for your example would therefore simply be 2.

I hope this makes it clearer, I'm really looking for the fastest way to do it.

Thanks again ,


Sam

Subject: common divisor selector

From: John D'Errico

Date: 7 Mar, 2009 01:24:01

Message: 4 of 6

Sam Van der Jeught <sam_vanderjeught@hotmail.com> wrote in message <30577730.1236384322486.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hello Roger,
>
> You're right, I'll try to explain it in more detail.
> What I want, ultimately, is a measure for how many 'incidents' occur. By incidents I mean each time two numbers share at least one divisor (not 1). It doesn't matter if they have more than one. So that's why the 5 in my example is counted twice: it shares a divisor greater then one with both 10 and 15, leading to two incidents.
> The count for your example would therefore simply be 2.
>
> I hope this makes it clearer, I'm really looking for the fastest way to do it.

Still a bit muddy. By your explanation, there are
these "incidents" between the numbers

2 and 10
3 and 15
5 and 10
5 and 15
10 and 15

I don't see 6 pairs with shared factors, only 5.
If this is what you want, then it is easy.

Turn this into a graph. Get the factors of each
number. A list of those factors is generated
easily enough.

N = {2,3,5,7,10,15};
F = cellfun(@factor,N,'uniformoutput','false');
Flist = unique(cell2mat(F))

Flist =
     2 3 5 7

Next, build a sparse matrix, such that the
(i,j) element is non-zero if prime factor j was
found in the factorization of the i'th number.

I'd probably do this with a loop here, but
I'm sure there is a non-looped way to do so.
I'm feeling lazy right now.

G = zeros(6,4);
for i = 1:length(F)
  G(i,:) = ismember(Flist,F{i});
end

Now, if you want to know how many "incidents"
there are, just count the number of non-zero
elements in the array

nnz(triu(G*G' - diag(sum(G.*G,2))))
ans =
     5

HTH,
John

Subject: common divisor selector

From: Roger Stafford

Date: 7 Mar, 2009 01:25:03

Message: 5 of 6

Sam Van der Jeught <sam_vanderjeught@hotmail.com> wrote in message <30577730.1236384322486.JavaMail.jakarta@nitrogen.mathforum.org>...
> .......
> What I want, ultimately, is a measure for how many 'incidents' occur. By incidents I mean each time two numbers share at least one divisor (not 1). It doesn't matter if they have more than one. So that's why the 5 in my example is counted twice: it shares a divisor greater then one with both 10 and 15, leading to two incidents.
> .......
> Sam

  That leaves the question of why 15 wasn't counted three times. As pairings it shares a common divisor with 3, with 5, and with 10. Or 10 three times since it shares a common divisor with 2, with 5, and with 15. All that would give a total count of 10, or if you're counting each pair only once, a total of 5. I still don't understand how you arrived at the count of 6. Suppose I had written [60,90,27]. Each pair has common divisors. Do you count that as 3, as 6, or as some other number?

  No-one can give you a fastest way until we know *all* the rules!

Roger Stafford

Subject: common divisor selector

From: Roger Stafford

Date: 7 Mar, 2009 01:50:03

Message: 6 of 6

Sam Van der Jeught <sam_vanderjeught@hotmail.com> wrote in message <30577730.1236384322486.JavaMail.jakarta@nitrogen.mathforum.org>...
> What I want, ultimately, is a measure for how many 'incidents' occur. By incidents I mean each time two numbers share at least one divisor (not 1).

  Assuming each pair counts twice, you can also do this, calling your array A:

 [I,J] = ndgrid(1:length(A),1:length(A));
 count = nnz(I~=J & gcd(A(I),A(J)~=1);

If each pair counts only once, divide 'count' by two.

Roger Stafford

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us