Problem 5 - Least Common Multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Of the early problems, I think this one was the easiest to solve. An integer is just a collection of prime factors multiplied together so to see what I was working with, I looked at the factorization of the integers 1 through 10:

({|i|i+1}!10).collect(_.factors);

[ [ 0 ], [ 2 ], [ 3 ], [ 2, 2 ], [ 5 ], [ 2, 3 ], [ 7 ], [ 2, 2, 2 ], [ 3, 3 ], [ 2, 5 ] ]

I feel like Supercollider should really return [1] for 1.factors instead of [0] but that's the default behavior - technically 1 has no prime factors but multiplying by the factors of 1 should also not return 0. Otherwise, this code is a great example of the conciseness of sclang and - the first expression generates an array of the integers 1 through 10 - then collect iterates a function over that array and returns a new array. the underscore _ character is the "anonymous argument" for simple functions - we take each integer and return its factors using the factors method.

Anyway, now let's break down 2050 into its prime components and see how it compares:

2520.factors;

[ 2, 2, 2, 3, 3, 5, 7 ];

So the distinct factors of 1..10 appear in 2050 at least once (which they would have to) and some of them appear more than once. I took a guess that this had to do with the maximum number of distinct factors in each of the numbers 1..10 and tried this:

({|i|i+1}!10).collect(_.factors).reject(_==[0]).reject({|i|i[0] != i.reverse[0]}).flatten.product;

This expression generates the factors 1 through 10, rejects any elements containing 0 from the list (to make up for the idiosyncracy of 1.factors = [0]) and then tests to see which numbers only have a single distinct prime factor. I do this using the .reject method. Since .factors returns a sorted array of factors, we can assume that if the first and last elements of a sorted array are the same value, then all elements in the array are the same value - we reject any arrays that fail this test. Finally, use .flatten to take the array of arrays and turn them into a single array of one dimension, and use the .product method (a kind of map/reduce shorthand) to multiply the elements of the array together.

Which returns 60480 - a little higher than what we were looking for. If we divide this result by our target value 2520, we get 24, and 24.factors is [2,2,2,3] - so these are the surplus factors that our current algorithm finds. I realized that those extra factors could be eliminated by only returning the first factor of any number that only had one value for its factors, and came up with this function:

~f = {|n|({|i|i+1}!n).collect(_.factors).reject(_==[0]).reject({|i|i[0] != i.reverse[0]}).collect({|i|i[0]}).flatten.product};

~f(10) will return 2520 and ~f(20) returns the correct answer for this problem.

I think this is my best example so far of solving one of these problems by generating a large collection and then filtering it down to find the answer.

Problem #4 - More Sonifications

I decided for this sonification to treat the digits 0..9 something like a major-9th chord. The frequency ratio 4:5:6:7:8:9 is a major ninth in 7-limit just intonation. Since we can't multiply frequencies by 0, I add 1 to all of the digits, so our pitch ratio is 1:2:3:4:5:6:7:8:9:10 which is essentially a power chord underneath a major 9th, topped off with an extra mediant (and also the first 9 overtones of the lowest pitch). Ok.

In the first sonification I posted, there are only 5 distinct pitches, which play at different octaves - I decided to make things more interesting by transposing these pitches according to some other base pitch - this kind of parallel harmonization, called "chord planing" became kind of a cliche in early 20th century music by composers like Debussy and Ravel (in a funny way this reminds me of the time my undergrad composition teacher Rob Constable, who studied with Ligeti, played us the opening of an intensely polyrhythmic and polytonal piece like Lotano and then said that "Ligeti would sail across the Atlantic and kill me for saying this but you can really hear the Ravel in the there").

So this next version tweaks the previous version by playing a parallel harmony at some overtone based on the sum of the digits in the palindomic number being played - for example, if the notes in the melody are 975579 then the pitches are 42 *.x [9,7,5,5,7,9];

I brough down the base frequency from the key of 16hz to the key of 11000/768 hz, and then made the wait time as the iterator counted down be 64 times that frequency. (So the rhythms are still related at an octave ratio to the pitches to try to squeeze out some interesting phase-cancellation effects in how the pitches overlap).

(
//set up a Routine that will iterate 999 * 999 times.
Routine{
999.do({|j| 
 var jj = 999-j;
 999.do({|i|
             
      var n =((999-j) * (999-i)).asString,c=0,s;
   //test if the string representation of n is a palindrome
                 (n.reverse==n).if ({
    //it is - let's play some notes
   Routine {
     /* we'll use the sum of the 
    digits of n as a musical parameter  */
    var sumDigits=0;
    n.size.do({|d|
     sumDigits = sumDigits + n.at(d).digit;
    }); 
   
     //step through each of the digits of n
    n.size.do({|k|
      //we'll play 2 notes for each digit
      var s = [1,0], freq, octave;
      //a pair of notes, in a base octave, and harmonized at an overtone
      octave =   [{((1/((12/11)/1000))/64) * sumDigits},{((1/((12/11)/1000))/128)  * (2**sumDigits.log2.floor)}];
      //iterate through [0,1] and play the 2 notes
      s.collect({|t|
        var ss;
        ss = Synth("sine");
        //the frequency is octave * kth digit of n
        freq = (n.at(k).digit +1) * (octave[t]);                                   
        /*  amplitude follows a pink noise curve, release gets longer as the sequence progresses, 
            and pan spreads more as the sequence progreses.  The amplitude envelope is a sharp percussive curve.  */
           ss.set(\freq,freq ,\atk,0.001,\rel,((i+3).log + (j+3).log).clip(0.1,7)*2/3,
              \pan,(j/1000)* (-1**i) *2/3,\amp,0.3  * (1/(freq+128)),\sus,-32,\gate,1);
       });
     //change the rhythm of the notes - each palindomic melody is based on a factor of the palindromic number
     ((1/ (jj.factors.wrapAt(i)).log2.ceil)).wait;
    });
   }.play;
   p.add([999-j,999-i,n.asInt]);
  });
  ((12/11) / 1000).wait; 
 });

});
}.play;
)

4.0 by Backtrace


Even with all of the rhythmic complexity, it feels like the notes come in clusters - around every 11th time through the loop, for example. This got me thinking into what it is that actually makes a number palindromic, and if it has anything to do with it being the product of numbers that must have palindromic prime factors.


The next sonification I made was rhythmically simpler, but harmonically the same - as the outer iterator counts down, if any products in the inner loop of 999 numbers contain palindromes, it plays all of them at once, waits for 1 second, and then moves to the next in the list (if there are no palindromes, it gets skipped with no wait). The rhythms of the palindromic melodies are also simpler - just 1 beat per second divided by the number of digits, so a melody is always 1 second long.

(
Routine{
999.do({|j| 
 var jj =999-j, doWait = 0;
 (jj).post;
 jj.factors.postln;

 999.do({|i|
  var n =((jj) * (999-i)).asString,c=0,s;
  (n.reverse==n).if ({
   n.postln;
   doWait = 1;
   Routine {
    var sumDigits=0;
    n.size.do({|d|
     sumDigits = sumDigits + n.at(d).digit;
    }); 
   
    n.size.do({|k|
     var s = [1,0], freq, octave;
     octave =   [{16 * sumDigits},{8* (2**sumDigits.log2.floor)}];
     s.collect({|t|
      var ss;
      ss = Synth("sine");
      freq = (n.at(k).digit +1) * (octave[t]);
      ss.set(\freq,freq ,\atk,0.001,\rel,n.size,\pan,(j/1000)* (-1**i) *2/3,\amp,(jj.log10 /10)  * (1/(freq+128)),\sus,-32,\gate,1);
     });
     (1/n.size).wait;
    });
   }.play;
   p.add([999-j,999-i,n.asInt]);
  },{
   0.wait
  });

 });
 doWait.wait;
});
}.play;
)

4.1 by Backtrace

Problem 4 - Palindromic Numbers

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
Find the largest palindrome made from the product of two 3-digit numbers.

My first attempt at this is pretty straightforward brute-force code:
Start with 999 * 999 and iterate downward (999 * 998, 999* 997, 999 * 996 ... 999 * 1, 998 *999, 998 * 998) It's even less efficient than 999-squared since it doesn't remember that multiplication is reversible, so it would do both 999 * 998 and 998 * 999.

The algorithm coverts the digits into a string, then does a comparison w/ the reverse of the string, and if they match, adds them to a List. I only do 10,000 checks since my assumption was that the winning number, being the highest sum of digits, it would have to have a lot of 9's in it, probably beginning and ending w/ a 9.

(
var p=(List());
100.do({|j| 
 100.do({|i|
  var n =((999-j) * (999-i)).asString,c=0,s;
  (n.reverse==n).if ({
   p.add([999-j,999-i,n.asInt]);
  });
 });
});
p.sortBy(2).reverse;
)

I save both multiples that product the number, along with the product, then use sortBy to sort the resulting array by the 2nd key.

This is the first sonification I've done for Project Euler so far that I've really liked - here's the code + a recording of the first one. I'll post more details in a later post.

(
Routine{
500.do({|j| 
 j.postln;
 999.do({|i|
  var n =((999-j) * (999-i)).asString,c=0,s;
  (n.reverse==n).if ({
   Routine {
    n.size.do({|k|
     var s,freq;
     s = Synth("sine");
     freq = (n.at(k).digit +1) *(4096  / (2**i.log.ceil));
     s.set(\freq,freq ,\atk,0.001,\rel,((i+3).log + (j+3).log),\pan,(j/1000)* (-1**i) *2/3,\amp,0.3  * (1/(freq+128)),\sus,-32,\gate,1);
    (1/ 8).wait;
    });
   }.play;
  });
 (1/1024).wait;
 });
});
}.play;
)

4.2 by Backtrace

Problem 3 -The Largest Prime Factor of a Composite Number

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

This one had me stumped for a while but mostly because of some type-casting issues with Supercolllider. sclang comes with an Integer.factors method that works great for 32-bit integers, up to a point.
So while

13195.factors 

correctly returns

[5, 7, 13, 29]

If you ask

600851475143.factors

it curiously returns

[ 2147483647 ]

which is probably not coincidentally the Mersenne Prime (2**31)-1 and probably has something to do with sclang overflowing the bit register for a 32-bit integer.

So after a few hrs of fighting w/ sclangs weird type-casting issues I came up with the following recursive function:

//function to find distinct factors of num, not complete factorization
//factors is an empty Array that we can add to

~f = {|num, f=2,factors=([])|
 /*
 break if we've already gotten to the square root of num 
 the final value of num is the last factor 
 because it was the last even divisor of num/f
 */
 (f>num.sqrt).if({factors.add(num);factors.postln;^factors});

 ((num%f)==0).and(factors.detect({|c|f%c==0})==nil).if({
  ~f.(num/f, f+1,factors.add(f));  
 },{
  ~f.(num, f+1,factors); 
 });
};


//number in question has to be cast as a Float for 64-bit precision
~f.(600851475143.0);

It's pretty fast, though not tail-recursive (and the 2 function calls seems like bad form. There's probably also a better way to do recursive functions than with the pseduo-global ~variable stuff). It doesn't do a complete factorization, just finds the unique factors of the number. The trick to gaining speed is that once you find a factor of composite num, you divide by the factor so that the number that you continue to factor is a little smaller, and even if you're just testing every integer sequentially for divisibility, your factor catches up with num pretty quickly. It probably helps that in this case, the test number has no repeating factors and most of the factors are pretty large.

Problem 2 - the even Fibonacci Numbers

Problem 2:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.



I solved this using a basic recursive function - it's a fairly brute-force solution.

~f = {|a=1,b=2,e=2|
 var c = a+b;
 (c<4000000).if ({
  //add any even term to e
  e = e+(c%2==0).if({c},{0});
  ~f.(b,c,e);
 }, {
  e;
 }); 
};
~f.();

Here's the code for a sonification that generates a spooky little overture:
It uses the sine tone generator from Problem 1

~f = {|a=1,b=2,e=0|
 var c = a+b;
 (c<4000000).if ({
  //add any even term to e
  e = e+ (c%2==0).if({c},{0});
  e.log.postln;
  (e>0).if ({
   Routine {
    var s1,s2;
    //put the wait at the front - rhythms accumulate as a duration of silence before the note
    c.log.wait;
    s1 = Synth("sine");
    s1.set(\freq,64 * e.log,\atk,0.01,\rel,64 - c.log,\amp,0.1,\gate,1);
   }.play;
  });  
  ~f.(b,c,e);
 }, {
  e;
 }); 
};
~f.();

One thing that the sonification of this solution makes really apparent is how the ratio of adjacent members of the Fibonacci series approaches the same value. The function pre-generates all of the notes before they are played, each one waiting it s turn to play as determined by the value of c.log.wait in the beginning of the Routine. I usually like a lot of symmetry in my music, which means I usually do things in integers or ratios of integers yet in this sequence, the notes all sound at very regular intervals even though their start times are not based on an integer. The pitch is determined by logarithm of the value of the variable e, the running sum of even numbered terms of the sequence - which always increases every 3rd term.

For a relatively small number of pitches this generates a pretty rich sound - there's more for me to explore here.

Some Sonifications of Problem 1.

First - boot the server and create a really basic sine wave synth:

z = Server.internal;

SynthDef("sine",{ |freq=100, atk=1, rel=1,sus=1, amp=0.005,pan =0,gate=0 |
Out.ar(0,Mix.ar(Pan2.ar(SinOsc.ar( freq * [1,1],0,amp),pan)) * EnvGen.ar(Env.perc(atk,rel,sus),gate, doneAction:2) );
}).load(z);


The first sonification is really basic - just run through the sequence of frequencies returned by the series and if the frequency f is greater than 0, then play the note at that pitch (times 8 so that the lowest notes are audible). The amplitude is scaled back over a pink noise curve (1/f) so that the low freqs are nice and full and the high freqs are not piercing.

(
Routine {
       //generate our numbers
 ({|i|i}!1000).collect({|i|((i%3==0).or(i%5==0)).if({i},{0})}).collect({|f,i|
  var s;
  f.postln;
  (f != 0).if({
          //allocate a sinewave synth
                 s = Synth("sine");
                       //frequency
   s.set(\freq,f*8);
                       //scale back the amplitude
   s.set(\amp,0.001,\atk,0.001,\rel, 1/3 ,\sus,-32,\gate,1, \amp, 1/(f+1) * 1/16);
  },{});
  (1/12).wait;
 }).sum;
}.play;

)

You can hear the 3/5 rhythm really clearly in this example:


1.0 by Backtrace

In the second sonification, I leave the notes on a long release so that many of them play simultaneously, and I lock the pitches to a single octave. As the notes build up, you can hear the same 3/5 rhythm, only this time as a differnce tone between frequencies.

(
Routine {
 ({|i|i}!1000).collect({|i|((i%3==0).or(i%5==0)).if({i},{0})}).collect({|f,i|
  var s, freq;
   freq = f*(512/ (2**f.log2.ceil));
  f.postln;
  (f != 0).if({
   s = Synth("sine");
   s.set(\freq,freq );

   s.set(\amp,0.001,\atk,0.001,\rel,(1000-i)/8,\sus,-32,\gate,1,  \amp,(1/ freq )*1/12);
  },{});
  (1/12).wait;
 }).sum;
}.play;
)

1.1 by Backtrace

Problem 1 - Multiples of 3 and 5

Problem 1:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This is essentially FizzBuzz revisited - in Supercollider you can find the solution with one line of code:

({|i|i}!1000).collect({|i|((i%3==0).or(i%5==0)).if({i},{0})}).sum;

({|i|i}!1000)

Generates the integers 0 to 999

.collect({|i|((i%3==0).or(i%5==0)).if({i},{0})})

.collect is an iterator method that maps an anonymous function over a Collection and returns a new collection - in this case we test to see if i modulo 3 or 5 is 0 - if it is, we return the value of i. Otherwise, we return o (which won't be accounted for when we sum to get the final answer).

In Supercollider, any expression is a Boolean so you can write a conditional as (expression).if({true},{false}) - where if is a method that takes 2 functions as arguments, for the true and false conditions.

.sum

Finally, we call the .sum method on the collection to return the sum of the collection's elements.

In the next post I'll post some sonifications of this algorithm.

Hi.

This will be a blog about Supercollider and music and using Supercollider to work my way through the problems on Project Euler.