## lowest common divider

May 2, 2007 at 11:46pm

# lowest common divider

Hi all,

Sorry, this is probably very basic for most of you but – is there an object to find the lowest common divider of a single number other than 1.

Went thru max reference and couldn’t find anything – checked out Mathworld too but… that just confused me further.

thanks
vic

#31727
May 3, 2007 at 12:15am

Quote: pechnatunk wrote on Wed, 02 May 2007 16:46
—————————————————-
> Hi all,
>
> Sorry, this is probably very basic for most of you but – is there an object to find the lowest common divider of a single number other than 1.
>
> Went thru max reference and couldn’t find anything – checked out Mathworld too but… that just confused me further.
>
> thanks
> vic
—————————————————-

Huh? Could you use a different term. Common usually implies more than one number. Are you looking for factors, or…?

mz

#103418
May 3, 2007 at 2:05am

sorry,

yes, now that i think about it I want the lowest factor –

8 = 2 9 = 3 10 = 5 7 = 1 etc.

i’m using this as a basis for sample slicing – where i’ll have a list of selected dividers in a coll similar to time signiture. these get multiplied by the length – but i want to constrain the the resolution of the length to a factor of the divider – using the lowest factor and the modulus of it – where each mod zero is an allowed length value. start position of the sample will use a similar technique.

I’ve built it to random/drunk these parameters but i’d like to quantise it to a signiture using this technique.

hope that makes it clearer.

#103419
May 3, 2007 at 9:38am

“8 = 2 9 = 3 10 = 5 7 = 1 etc.”

10 => 2 you must mean?

Anyway, fun question. Here’s a patch for just the lowest factor other than 1:

#P window setfont “Sans Serif” 9.;
#P window linecount 1;
#P newex 67 125 47 196617 t b i;
#P newex 67 151 27 196617 i;
#P newex 67 244 50 196617 print end;
#P newex 67 223 27 196617 i;
#P newex 67 196 32 196617 sel 0;
#P newex 67 174 27 196617 %;
#P newex 67 74 107 196617 t b 2 i 1;
#N counter 2 100;
#X flags 0 0;
#P newobj 67 101 74 196617 counter 2 100;
#P number 67 45 35 9 3 1024 3 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P connect 2 2 7 1;
#P connect 2 2 1 4;
#P connect 2 1 1 2;
#P fasten 8 1 5 1 109 217 89 217;
#P fasten 8 1 3 1 109 170 89 170;
#P connect 5 0 6 0;
#P connect 4 0 5 0;
#P connect 3 0 4 0;
#P connect 7 0 3 0;
#P connect 8 0 7 0;
#P connect 1 0 8 0;
#P connect 2 0 1 0;
#P connect 4 1 1 0;
#P connect 0 0 2 0;
#P window clipboard copycount 9;

It too seems to produce stack overflows when putting in larger primes. Comes from using counter too heavily, i presume. The patch below shows that it’s helpful to even have one % in the loop; the right one overflows sooner than the left one. What would be a good workaround?

#P window setfont “Sans Serif” 9.;
#P number 500 140 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P window linecount 1;
#P newex 149 115 72 196617 loadmess 500;
#P number 268 161 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 268 63 30 196617 t b b;
#P button 268 45 15 0;
#P newex 340 208 55 196617 print done;
#P newex 340 161 170 196617 if \$i1 == \$i2 then \$i1 else out2 \$i1;
#P message 288 85 33 196617 set 1;
#N counter 0 0 2000;
#X flags 0 0;
#P newobj 268 110 89 196617 counter 0 0 2000;
#B color 5;
#P number 41 161 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P number 149 142 35 9 0 0 0 3 0 0 0 221 221 221 222 222 222 0 0 0;
#P newex 41 63 30 196617 t b b;
#P button 41 45 15 0;
#P newex 113 208 55 196617 print done;
#P newex 113 186 32 196617 sel 0;
#P newex 113 161 46 196617 % 1000;
#P message 61 85 33 196617 set 1;
#N counter 0 0 2000;
#X flags 0 0;
#P newobj 41 110 89 196617 counter 0 0 2000;
#B color 5;
#P connect 16 0 7 0;
#P fasten 16 0 17 0 154 136 505 136;
#P connect 17 0 11 1;
#P connect 5 0 6 0;
#P connect 3 1 0 0;
#P fasten 1 0 0 0 66 105 46 105;
#P connect 6 0 0 0;
#P connect 0 0 8 0;
#P connect 6 1 1 0;
#P connect 0 0 2 0;
#P connect 2 0 3 0;
#P connect 3 0 4 0;
#P connect 7 0 2 1;
#P connect 13 0 14 0;
#P connect 11 1 9 0;
#P connect 14 0 9 0;
#P fasten 10 0 9 0 293 105 273 105;
#P connect 9 0 15 0;
#P connect 14 1 10 0;
#P connect 9 0 11 0;
#P connect 11 0 12 0;
#P window clipboard copycount 18;

A patch to get the lowest common denominator off a list of unknown length sounds good too, maybe some other time…

#103421
May 3, 2007 at 10:09pm

not that i would know it offhand now … but there
is some very funny trick how to check this with
simple algebra, isnt it?
maybe someone knows what i mean ..

#103422
May 3, 2007 at 10:26pm

That’s what the deferlow object is for! Always always insert deferlow in your loop back– in this case, the right outlet of “select 0″ would connect to a deferlow, and that connects back to the counter. I’m by no means a programming expert, I just stumbled upon this. Deferlow, I guess, is like a ‘Yield’ sign for Max, letting the system do required maintenance while your patch is running. (Wow, I actually had a fresh bit of useful info for the Max list!)

#103423
May 3, 2007 at 10:27pm

Quote: pechnatunk wrote on Thu, 03 May 2007 04:05
—————————————————-
> yes, now that i think about it I want the lowest factor –
>
> 8 = 2 9 = 3 10 = 5 7 = 1 etc.
—————————————————-

You want to single out the lowest prime factor.

There is a prime number generator in Tap.Tools that might help.

Also, the Sieve of Erastosthenes is the traditional efficient method for finding primes. Googling on the term should give you some ideas. (Sorry, I haven’t looked at patches submitted in detail, but the stack overflows leave me thinking they’re not Erastosthenes).

Hope this helps,
P.

#103424
May 4, 2007 at 6:24pm

David Wright schrieb:
> That’s what the deferlow object is for! Always always insert deferlow
> in your loop back– in this case, the right outlet of “select 0″
> would connect to a deferlow, and that connects back to the counter.
> I’m by no means a programming expert, I just stumbled upon this.
> Deferlow, I guess, is like a ‘Yield’ sign for Max, letting the system
> do required maintenance while your patch is running. (Wow, I actually
> had a fresh bit of useful info for the Max list!)

Yes, and no, in the patch which would overflow the stack on big numbers,
it might be fine if you can guarantee that the number stays low.
deferlow is slowing down things by using the scheduler queue instead of
the stack.
In the patch I posted recently for finding the occurance of more than
the half of its elements being in a certain range, there is recursion
(which means feedback) but no deferlow. And its not needed, because the
condition to break the recursion has a max of 256 steps (in theory, and
only because of the limitation of zl). That’s not dangerous. Also as the
calculation doesn’t put out anything before the result is found, the
stack size needed is not too high.

One thing to look at if a stack overflow only happens with big numbers
is, optimization. You might not need the feedback for all cases etc,
Sometimes you can just “turn around” the calculation instead of starting
with low numbers going up, you could go down from high numbers…

Peters quote is correct I guess:
Peter Castine schrieb:
> (Sorry, I haven’t looked at patches submitted in detail, but the
> stack overflows leave me thinking they’re not Erastosthenes).

If you do not need the calculation fast, a deferlow might be fine
though… (In this case Erastosthenes is better… ;-)

Stefan

Stefan Tiedje————x——-
–_____———–|————–
–(_|_ —-|—–|—–()——-
– _|_)—-|—–()————–
———-()——–www.ccmix.com

#103425
May 5, 2007 at 4:57am

Thanks for that info, Stefan… I made 3 mistakes, writing the word “always,” writing the word “always” again, and pretending I really knew what I was talking about…

Stefan wrote:
> Sometimes you can just “turn around” the calculation instead of
> starting with low numbers going up, you could go down from high
> numbers…

Yes, I noticed recently that works.

“You can’t go back. The answer is No. And wishing for it only makes it bleed.” — Tom Waits

#103426
May 5, 2007 at 8:38am

Quote: Bas van der Graaff wrote on Thu, 03 May 2007 19:38
—————————————————-

> 10 => 2 you must mean?

Sort of,

Peter you’re right I need to find the prime factors and then be able to switch between them eg. if divided into 24 it may be useful to use either 2 or 3 etc. thats why I said 10 = 5 – i was thinking of a sample in 5/4.

Anyway thanks for all the help – for various reasons I was only able to open the patch from robtherich but I had a look at Erastosthenes and it makes sense but will take a while – I have very limited math syntax knowledge, and recursion in Max is something I’m yet to grasp.

#103427
May 8, 2007 at 3:46am

OK – I’m gonna try this without recursion.

But first …

I need to construct a list of n values which is consecutive numbers from 1 -> n.

after that i should be able to solve this – but will probably be quite clunky.

#103428
May 13, 2007 at 11:11am

sorry, should have specified that previous post was a question

does anyone know how to construct a list of consecutive numbers.

to the value n.

it would be very easy in Scheme – but Max… ?

#103429
May 13, 2007 at 11:45am

#103430
May 13, 2007 at 6:44pm

#103432
May 13, 2007 at 7:14pm

i don’t really use javascript in max that much, so i’m not familiar
with it’s drawbacks… but couldn’t this whole lowest common factor
thing be solved very simply with a js patch like the one below?

function msg_int (x) {
var i=0;
var quotient;
var divisor = 0;
for (i =2; i < = Math.floor(x/2); i++) {
quotient = x/i;
if (quotient == Math.floor(quotient)) {
divisor = i;
break;
}
}
if (divisor > 0) {
outlet(0,divisor);
} else {
outlet(0,1);
}
}

On 5/13/07, Emmanuel Jourdan wrote:
> On 13 mai 07, at 13:45, jose manuel berenguer wrote:
>
> > for shure, you will find a better and shorter way to do it, but
> > here is a possibility
>
> zl group?
>
> ej
>
>
> #P window setfont “Sans Serif” 9.;
> #P user textedit 416 203 612 240 32896 3 9 1;
> #P window linecount 1;
> #P newex 416 176 62 196617 prepend set;
> #P newex 386 76 76 196617 t i i;
> #P number 386 59 35 9 0 0 64 3 0 0 0 221 221 221 222 222 222 0 0 0;
> #P newex 386 97 40 196617 uzi;
> #P newex 416 132 46 196617 zl group;
> #P connect 2 0 3 0;
> #P connect 3 0 1 0;
> #P connect 3 1 0 1;
> #P connect 0 0 4 0;
> #P connect 1 2 0 0;
> #P connect 4 0 5 0;
> #P window clipboard copycount 6;
>

#103433
May 13, 2007 at 11:02pm

Quote: mcartwright@gmail.com wrote on Mon, 14 May 2007 05:14
—————————————————-
> i don’t really use javascript in max that much, so i’m not familiar
> with it’s drawbacks… but couldn’t this whole lowest common factor
> thing be solved very simply with a js patch like the one below?
>
> function msg_int (x) {
> var i=0;
> var quotient;
> var divisor = 0;
> for (i =2; i < = Math.floor(x/2); i++) {
> quotient = x/i;
> if (quotient == Math.floor(quotient)) {
> divisor = i;
> break;
> }
> }
> if (divisor > 0) {
> outlet(0,divisor);
> } else {
> outlet(0,1);
> }
> }

Cool thanks,

seems like I should take a look at java script.
however – the reason I asked about constructing a list of consecutive numbers is because I realised I not only wanted to find the lowest factor but all prime factors – this would allow a changable resolution in quantisation.
But it looks like making a java object to do this is the neatest technique – especially since I didn’t want my divider limited to 256 – which is what happens with the above two solutions – due to the limitations of Max message and text boxes, but of course thanks anyway.

#103434
Mar 10, 2009 at 5:03am

OK I’m re-opening this can of worms.

I left this problem ages ago and have recently gone back to it.

I’d like to get a list of say, the lowest 3-5 prime factors of a number.
I’ve tried using the explaination of the Sieve of Eratosthenes algorithm on wikipedia

But I’m approaching 2 brick walls – I’d like to use it with numbers above 256 (entry limit on message and text boxes)

also – I’m having trouble recursively truncating the list and applying the maths.

Thanks heaps to Jose and Emmanuel for the list generating patches.

And thanks mcartwright – but I can’t adapt your java script for the life of me.

So yeah – It would be great to be able to get the lowest 3 – 5 prime factors of an integer instead of only the lowest.

thanks.

#103435
Mar 10, 2009 at 10:42am

This js will give you all the prime factors.
Just getting the first few can be done using [zl thin] and [zl slice].

function msg_int(v)
{
while (v%2==0)
{
outlet(0,2);
v/=2;
}
var i=3;
while (i*i1) outlet(0,v);
}

And a patch, save the js as primes.js

– Pasted Max Patch, click to expand. –

Edit: tabs are not stored?

#103436
Mar 10, 2009 at 10:57pm

Beautiful!!
It works a charm.
Thanks.

#103437

You must be logged in to reply to this topic.