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.