Duncan's blog

January 22, 2015

Animated paths with Google Maps

Filed under: Google Maps,Javascript — duncan @ 6:39 pm
Tags: , ,

I saw this question on StackOverflow a few days ago.  There was a map with animated polylines being drawn along a set of coordinates, with a minor bug in it.  The very next day I saw another question asking how to animate a route on a map.  I thought the approach I’d seen the day before was ideal, and posted a slightly re-written version of it as an answer. I thought there was enough merit in the technique used to turn it into a blog post.  Thanks to the OP Alex Man for the original version of the code.

Version 1


function initialize() {
	var map = new google.maps.Map(document.getElementById("map"), {
	  center: {lat: pathCoords[0].lat, lng: pathCoords[0].lng},
	  zoom: 11,
	  mapTypeId: google.maps.MapTypeId.ROADMAP

function moveMarker(map, marker, latlng) {

function autoRefresh(map) {
	var i, route, marker;
	route = new google.maps.Polyline({
		path: [],
		geodesic : true,
		strokeColor: '#FF0000',
		strokeOpacity: 1.0,
		strokeWeight: 2,
		editable: false,
	marker=new google.maps.Marker({map:map,icon:"http://maps.google.com/mapfiles/ms/micons/blue.png"});

	for (i = 0; i < pathCoords.length; i++) {
		setTimeout(function (coords)
			var latlng = new google.maps.LatLng(coords.lat, coords.lng);
			moveMarker(map, marker, latlng);
		}, 200 * i, pathCoords[i]);

google.maps.event.addDomListener(window, 'load', initialize);

var pathCoords = [
	"lat": 8.893260000000001,
	"lng": 76.61427
	"lat": 8.894430000000002,
	"lng": 76.61418
	// etc for hundreds more coordinates

View full code

The interesting bit here is the ‘autoRefresh‘ function.  That creates an empty polyline, then loops over the global pathCoords array.  For each set of coordinates, it creates a call to this anonymous function, at 200 millisecond intervals:

function (coords) {
	var latlng = new google.maps.LatLng(coords.lat, coords.lng);
	moveMarker(map, marker, latlng);

So every 200 milliseconds it calls that function.  When using setTimeout I pass in a third parameter, which is a single set of coordinates.  I’m not sure this is an ideal approach, for instance if something in that function took longer than 200ms to execute, things could get a bit disjointed looking.  But it seems to work for now.

For each set of coordinates, it adds it to the current polyline’s path.  You might have thought I’d have to use setPath, but just pushing it onto the array that getPath returns works.

Then I update the position of the marker to the current point, and pan the map.

One thing worth noting: Google Maps have started accepting coordinates in this format in a lot of places:

	{lat: 1.234, lng: 2.345}

instead of having to always create new LatLng objects each time:

	new google.maps.LatLng(1.234, 2.345)

In the example above, the coords object was fine when passed straight to the moveMarker function, i.e. for setting the marker and panning the map.  However it didn’t work when pushing it into the array of the polyline’s path.  So I still had to create a LatLng object for that.  Possibly if I’d saved the polyline path from getPath into a variable, appended the coords parameter, then done setPath with the full array, it would have been fine.

See the map working here

Version 2


Instead of having to hardcode hundreds of coordinates in our javascript, we can use the DirectionsService, simply specifying a start and end point.  The data it returns includes a list of all the coordinates we’d need.  Then instead of rendering the directions, we can simply use those coordinates to draw our own animated path.

function initialize() {
    var map = new google.maps.Map(document.getElementById("map"), {
      center: {lat: 51.5087531, lng: -0.1281153},
      zoom: 7,
      mapTypeId: google.maps.MapTypeId.ROADMAP

function moveMarker(map, marker, latlng) {

function autoRefresh(map, pathCoords) {
    var i, route, marker;
    route = new google.maps.Polyline({
        path: [],
        geodesic : true,
        strokeColor: '#FF0000',
        strokeOpacity: 1.0,
        strokeWeight: 2,
        editable: false,
    marker=new google.maps.Marker({map:map, icon:"http://maps.google.com/mapfiles/ms/micons/blue.png"});

    for (i = 0; i < pathCoords.length; i++) {                
        setTimeout(function(coords) {
            moveMarker(map, marker, coords);
        }, 200 * i, pathCoords[i]);

function getDirections(map) {
    var directionsService = new google.maps.DirectionsService();

    var request = {
        origin: new google.maps.LatLng(51.5087531, -0.1281153),
        destination: new google.maps.LatLng(48.8583694, 2.2944796),
        travelMode: google.maps.TravelMode.DRIVING
    directionsService.route(request, function(result, status) {
        if (status == google.maps.DirectionsStatus.OK) {
            autoRefresh(map, result.routes[0].overview_path);

google.maps.event.addDomListener(window, 'load', initialize);

See the second map working here

Again, I wasn’t able to just use a coords struct, I had to create LatLng objects for passing into the DirectionsService request. The directions service happens asynchronously, so I have to wait for when it returns back an ‘OK’ status before creating the path.

Apart from replacing the array of coordinates with the value returned by the DirectionsService’s overview_path property, the code for drawing the path is basically the same as before.

Further ideas:

  • Instead of just creating a polyline from all the coordinates in the overview_path, we could loop over all the legs of the route.  This would give us more flexibility to amend the polyline, e.g. you could examine the duration property of each DirectionsStep and change the colour of the polyline.
  • We could use the bounds property of the DirectionsRoute to update the map’s bounds so the entire route is always visible.  Doing this you wouldn’t need to constantly pan the map centre.

January 5, 2015

Bristol coffee shops

Filed under: Coffee — duncan @ 8:00 am
Tags: , , ,

After a recent trip to Bristol, in keeping with previous articles on coffee shops in Dublin, New York, Zagreb and  New Zealand and Australia, I thought I’d do a write-up for some cafés we went to.

Playground Coffee House

45 St. Nicholas Street

The first place we called at was the Playground Coffee House.  It hadn’t opened for the morning, we were slightly too early, but we were still able to get some very nice coffees.  It looked like a fun place to go; from the usual like board games, to the unusual like, er, swings for seats.  Which come with their own warning, they maybe don’t mix too well with hot drinks!

The barista was very friendly, and recommended to us a few of the other best coffee shops in town.

P1010287 P1010288 P1010289 P1010291 P1010293

Facebook / Twitter


Bear Pit Social

St. James Barton Underpass

This place is housed in a converted shipping container, in the, er, interesting location of the Bearpit, aka the St. James Barton Roundabout underpass… not as bad as it sounds.  In fact they had quite a nice little seating area in one corner, and they were doing food in addition to the coffees.


Facebook / Twitter


Spicer and Cole

1 Queen Square Avenue

Spicer and Cole was listed on our map, out in Clifton.  We didn’t go there, but they also had a branch in the centre, on Welsh Back, very close to Queen Square.  I overheard someone in the street raving about it to a couple who were looking for somewhere to eat.  I went there a couple of times; the coffee was ok; we had some nice Sunday breakfast.

P1010463 P1010465 P1010466

Website / Facebook / Twitter


Full Court Press – Speciality Coffee

59 Broad Street

Full Court Press I visited a couple of times.  The name’s apparently a basketball reference.  They seemed to take their coffee pretty seriously (as their sub-title would imply), and both times the baristas gave me good descriptions of the choice of beans available.

P1010434 P1010435 P1010585 P1010586

WebsiteFacebook / Twitter / Pinterest


I intended to visit some of these too, but unfortunately they were all closed on the Sunday:

  • Didn’t You Do Well
  • Workhouse Cafe
  • Small Street Espresso

The coffee map I bought in Playground was very useful; I’d recommend it if you were on a trip to Bristol and wanted to visit a few different cafés.  It listed 24 different places to go, with lots of information and an attractively-designed map.

Website / Twitter

(when I first checked the website was fine; but it seems be offline right now).

January 1, 2015

2014 in review

Filed under: Uncategorized — duncan @ 7:00 am

The WordPress.com stats helper monkeys prepared a 2014 annual report for this blog.

Here’s an excerpt:

The concert hall at the Sydney Opera House holds 2,700 people. This blog was viewed about 37,000 times in 2014. If it were a concert at Sydney Opera House, it would take about 14 sold-out performances for that many people to see it.

Click here to see the complete report.

December 18, 2014

Project Euler: problem 46 – Goldbach’s other conjecture

Filed under: PHP,Project Euler — duncan @ 11:57 pm
Tags: , , ,

46I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code

Problem 46:

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

This was another of those problems that I’d initially passed over, having decided it looked a bit tricky.  Then looking at it again realised it probably wasn’t too difficult.  And I turned out to be right!

A composite number is basically any positive integer that isn’t a prime number.

My logic is simply:

  • Loop through odd numbers, from 3 upwards.
  • For each number, if it’s prime, add it to an array of primes for later reference.
  • If it’s not prime, work out if it matches the conjecture:
    • Subtract the next largest prime, then examine the remainder
    • Divide the remainder by 2.  if it’s a square number then we’re meeting the conjecture.  Move onto the next odd number.
    • Otherwise keep subtracting the primes, checking the remainders.
    • If we’ve looped through all the primes then we must have reached a number that doesn’t meet the conjecture.

This runs in about 40ms:

$primes = [2];

$i= 1;

while (true) {
	$i+= 2;

	if (isPrime($i)) {
		$primes[] = $i;
	} else {
		for($j = count($primes)-1; $j > 0; $j--) {
			$remainder  = $i - $primes[$j];
			$remainder = $remainder / 2;
			$root = sqrt($remainder);
			if ((int) $root == $root) {
				continue 2;
		echo $i;

function isPrime($x)
	$root = sqrt($x);
	for ($i = 3; $i <= $root; $i += 2) {
		if ($x % $i == 0) {
			return false;
	return true;

I’m using a modified version of my original isPrime function, just because I know I don’t need to check for even numbers.

The loop backwards through the primes was maybe a bit of overkill; using a simple foreach loop through the primes in ascending order took more like 100ms.

What else… I check if a square root is the same as when it’s cast to an integer (not sure this is the best approach).  Then use continue 2; to get out of our inner-most loop and move onto the next value in our parent loop.

December 14, 2014

Project Euler: problem 33 (PHP) – Digit cancelling fractions

Filed under: PHP,Project Euler — duncan @ 10:54 pm
Tags: ,

Picture by jessicakelly

I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code

Problem 33:

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

It took me a couple of tries to get this, I think as the question doesn’t give enough details about what the rules are for anomalous fraction cancellation.

Supposing we say our fractions are of the form ab / cd.  Initially I was checking each of the following:

  • a / c = ab / cd
  • a / d = ab / cd
  • b / c = ab / cd
  • b / d = ab / cd

i.e. each possible combination of the first and second numerator and denominator digits.

Then I realised I could omit two of these, as we didn’t want to look at those cases where it’s the first numerator digit divided by the first denominator digit, or the second numerator digit divided by the second denominator digit.  Reducing what I was checking down to:

  • a / d = ab / cd
  • b / c = ab / cd

So I was now just looking at the first numerator over the second denominator, and the second numerator over the first denominator.  However this was still giving me too much possible fractions.  Further reading illustrated that the example given, 49 / 98, where the second numerator digit and the first denomator digit are cancelled out, is the rule for all cases.  Reducing what I was checking to just:

  • a / d = ab / cd

The question also doesn’t really explain what else you can ignore.  Firstly if either digit is zero.  Secondly, the trivial examples include where a = b and c = d, e.g. 11 / 22.

And finally, I thought you could look at any values for ab and cd, e.g. I’d got 16 / 96 = 1 / 6.  But this meant I’d still got more than four ‘matching’ fractions.  What the question failed to mention is that the digits being cancelled out had to be identical, so really what I was checking was changed to:

  • a / c = ab / bc

Once I’d got all that cleared up, it was easy.

$product = 1;

for ($numerator = 10; $numerator <= 99; $numerator++) {
	for ($denominator = $numerator+1; $denominator <= 99; $denominator++) {
		$fraction = $numerator / $denominator;
		$numeratorAsString = (string)$numerator;
		$denominatorAsString = (string)$denominator;
		if (
			!isTrivial($numeratorAsString, $denominatorAsString) && 
			$numeratorAsString[1] == $denominatorAsString[0] && 
			$numeratorAsString[0] / $denominatorAsString[1] == $fraction
		) {
			$product *= $fraction;

function isTrivial($numerator, $denominator) {
	if ($denominator[1] == 0) {
		return true;
	if ($numerator[0] == $numerator[1]) {
		return true;
	return false;

echo $product;

I cast my numerators and denominators to strings, enabling me to then reference the digits within each using array notation.

Some useful links:

December 10, 2014

Project Euler: problem 27 (PHP) – Quadratic primes

Filed under: PHP,Project Euler — duncan @ 8:00 am
Tags: , ,

Photo by Ianqui Doodle

I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 27:

Euler discovered the remarkable quadratic formula:

n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

The incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000
where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

This was another puzzle I’d ignored previously, then looked at it again and realised it wasn’t that hard after all.  First time I’ve really done anything with quadratics since school probably!

include 'isPrime.php';

$maxPrimes = 0;
$maxCoefficients = [];

calculatePrimes(1, 1);
calculatePrimes(1, -1);
calculatePrimes(-1, 1);
calculatePrimes(-1, -1);

function calculatePrimes($incrementA, $incrementB) {
	global $maxPrimes;
	$a = 0; 
	while (abs($a) < 1000) {
		$b = 0;
		while (abs($b) < 1000) {
			$n = 0;

			while (true) {
				$q = ($n * $n) + ($n * $a) + $b;
				if (!isPrime($q)) {
					if ($n > $maxPrimes) {
						$maxPrimes = $n;
						setMaxCoefficients($a, $b);
			$b+= $incrementB;
		$a+= $incrementA;

function setMaxCoefficients($a, $b) {
	global $maxCoefficients;
	$maxCoefficients = [$a, $b];

echo $maxCoefficients[0] * $maxCoefficients[1];

So I’ve wrapped up most of the code into one function, which I call four times.  Each time I’m either adding or subtracting 1 from each of the two coefficients.  Then there’s nested loops so we’re going from zero to +/- 999 for both coefficients.  Within that we loop again, incrementing $n until our quadratic equation doesn’t return a prime number.  At that point, we check if the value of $n is more than the previous maximum number of primes.  And if it is, I update a global array with those coefficients.

After we finish looping, I then calculate the production from those stored coefficients.  Simple, but not particularly fast.

December 3, 2014

Project Euler: problem 32 (PHP) – Pandigital products

Filed under: PHP,Project Euler — duncan @ 1:24 pm

Photo by Lars Dahlin

I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 32:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

This if the first one of these Project Euler puzzles I’ve completed in the last month.  I’d been sidelined by a much harder one, given up on it for now, and tried this instead for the first time.  It wasn’t too hard either; I’m not sure why I hadn’t attempted it previously.

$sums = [];

for ($i = 1; $i < 9; $i++) {
	for ($j = 1234; $j < 9876; $j++) {
		getPandigitalProduct($i, $j, $sums);

for ($i = 12; $i < 98; $i++) {
	for ($j = 123; $j < 987; $j++) {
		getPandigitalProduct($i, $j, $sums);

echo array_sum($sums);

function getPandigitalProduct($multiplicand, $multiplier, &$sums) {
	$product = $multiplicand * $multiplier;
	$number =  $multiplicand . $multiplier . $product;
	if (isPandigital($number)) {
		$sums[$product] = $product;

function isPandigital($number) {
	$length = strlen($number);
	if ($length != 9) {
		return false;
	for ($i = 1; $i <= $length; $i++) {
		if (strpos($number, (string)$i) === false) {
			return false;
	return true;

Not the cleanest code, but it’s reasonably fast.  In the isPandigital function I just loop from 1 to 9, checking that each of those digits is present in the number (after checking that it’s 9 digits long of course).

The important thing to understand is why I’m doing two separate nested loops.  The first one is for getting 9-digit identities which look like:

1 * 2345 = 6789

The second one is for getting identities which look like:

12 * 345 = 6789

Initially I had it in one set of nested loops, like:

for ($i = 1; $i < 99; $i++) {
	for ($j = 1; $j < 9999; $j++) {

However that made 979804 iterations!  Doing it this way there’s a total of 143440 iterations (still way too many of course).

Also note I’m explicitly passing the $sums array by reference by specifying the ampersand before the argument in the function declaration.

What else… I had to cast the value of $i to a string before being able to use it succesfully with the strpos function.

November 8, 2014

New Zealand and Australian coffee shops

Filed under: Coffee — duncan @ 11:16 pm
Tags: , , , , ,

I had a brilliant 3-week holiday in New Zealand and Australia with my girlfriend recently. I thought I’d list some of the decent coffee shops we visited, similarly to how I’ve done it before with New York and Zagreb. This is far from comprehensive; we only went to a few cities, and didn’t try specifically to seek out the best cafés, they were more just those we came across in our wanderings. In summary I was very impressed with the quality of coffee shops in both New Zealand and Australia.

New Zealand

We were briefly in Auckland, then the rest of the time in the South Island, including a couple of visits to Christchurch.



1 Wellesley Street West, Auckland CBD, Auckland 1010 (map)

A quirky little place with lots of things to keep you distracted in the cafe, like books, board games and an arcade machine, making it a fun place to hang out. But the important thing is the coffee, which was good.

Good One

42 Douglas Street, Ponsonby, Auckland 1011 (map)

Slightly off the main Ponsonby Road, down what is otherwise mostly a residential street, tucked away in a small light industrial unit. It’s worth discovering though; it’s a decent size inside with plenty of seating areas. A huge collection of National Geographics provides some colour in keeping with their yellow theme.


Coffee Lovers

25 New Regent Street, Christchurch (map)

One of several cafes on the funky little pastel-coloured New Regent Street, right outside where the historic tram currently stops. A small seating area upstairs, reasonable coffee.

Crafted Coffee Company

Re:Start Container Mall, Cashel Street, Christchurch (map)

In the centre of Christchurch, following the devastating earthquake of 2011, they’ve constructed a pop-up space of shops and cafes made from shipping containers, ‘Re:Start‘, very similar to the Boxpark in Shoreditch, London.  In one of those units is Crafted Coffee, in a two-storey affair (although the upper area was closed when we were there).  It’s a decent little cafe, and I thought they displayed good customer service.

There were a couple other coffee shops in Re:Start, and given enough time I’d have tried them all.

Robert Harris, Christchurch

YMCA Building, 12 Hereford Street, Christchurch 8013 (map)

In the ground floor of the YMCA youth hostel is a decent sized Robert Harris cafe, doing reasonable coffees and teas and food.  Not quite pure artisan coffee, but a step up from global chains like Starbucks.

Vespa Bar

225 High Street, Christchurch (map)

The original Vespa Bar got destroyed in the earthquake, but has been able to re-open in a new building nearby to their original location.  It was more of a bar than a coffee shop, but the food and coffee we had was perfectly fine.




Vudu Cafe

23 Beach Street, Queenstown 9197 (map)

In Queenstown there are two Vudu’s, presumably reasonably similar… don’t confuse this Vudu Cafe with Vudu Cafe & Larder round the corner!  We only went to this one, twice.  The coffees were good, and the food was beautifully presented yumminess.  It was quite popular and busy, although there was a semi-covered side-area which didn’t seem to get so crowded.

Post Office Cafe

19 Ballarat Street, Queenstown 9348 (map)

aka The Exchange, a large coffee shop just round the corner from, er, the post office.


Relishes cafe, Wanaka

1/99 Ardmore Street, Wanaka 9305 (map)

There seemed to be several decent looking places along the lakeside in Wanaka; we just chanced on this one.  I had a delicious ‘free range pulled pork shoulder in a Turkish bun with apple slaw‘.  Never heard of Turkish bun before, but it just turned out to be a big soft roll, I think with some herbs and spices.

Cafe Mondo, Arrowtown

4/14 Buckingham Street, Arrowtown 9196 (map)

Arrowtown is an interesting little place near Queenstown where the town centre looks like something from the Wild West, having been an old gold mining settlement.  Not sure how much of that is genuinely old and how much is retro-fitted.  Cafe Mondo looked like about the best spot for coffee.  Friendly service.


We were in Melbourne for a few days, but less than 48 hours in Sydney.


Cheeky Monkey

89A Swan Street, Richmond VIC 3121 (map)

Melbourne as a whole is full of good coffee shops, although there didn’t seem to be that many around this area; I recall walking down Swan Street looking for anywhere decent, then finding Cheeky Monkey and opposite it was Book Talk Cafe (a ‘cafebreria‘) which also looked good.

Sacred Alley espresso bar

12 Equitable Place, Melbourne, VIC 3000 (map)

This little alleyway in the Melbourne CBD laneways is full of cafes and restaurants, many of which looked like they’d be good for coffee, and we just opted for this one, which was perfectly good.

Jasper Coffee

Stall 105, 163 Commercial Road, Prahran, Victoria 3181 (map)

Prahran has a large indoor market full of fresh meat, fish, fruit + veg stalls.  Towards the back is this little coffee stand, with an impressive selection of beans available for purchase.  Quite busy, at least at the weekend, but good coffee.

Market Lane is another coffee shop in the Prahran Market that looks very good.

Huckleberry Finn

538 Glenferrie Road, Hawthorn, Victoria (map)

Came across this little place by luck, as we had a few minutes while changing trams and got some takeaway coffees here.  Lovely teal La Marzocco machine.


157 Brunswick Street, Fitzroy, Victoria 3065 (map)

This was in the Fitzroy area, towards the southern end of Brunswick Street.  They had an open fire in the back, a sort of long narrow affair with different seating areas.  I had some ‘baked eggs in spicy napoli sauce with chorizo & feta’ which was quite nice, and the coffees were very good.  It was indeed nice inside.

Miss Frank cafe

200 Through Road, Camberwell, Victoria 3124 (map)

This coffee shop was out in Camberwell, luckily quite close to where we were staying.  It’s a good size inside, with friendly service.  Nice food, good coffees, much better than I would expect to typically find out in the suburbs.

Sensory Lab

297 Little Collins Street, Melbourne VIC 3000 (map)

Based in the ground floor of department store David Jones.  They seemed to know what they were doing.



Ground Control cafe

Alfred Street, Sydney, NSW 2000 (map)

A small coffee shop conveniently located in the ground floor under the Circular Quay train station.  Small seating area, reminded me of Dose in London.

Social Brew cafe, Sydney

Harris Street, Pyrmont, NSW 2009 (map)

This coffee shop is near the Sydney Fish Market in Pyrmont (which is worth a visit).  We went there on a Saturday lunch time, and it was very busy with people enjoying brunch, but we were only having coffees, which were good.

AquaBar, Bondi

4/266 Campbell Parade, Bondi Beach, NSW 2026 (map)

On a wet and windy day we took refuge here at the far end of Bondi Beach.  There were about three cafes here all grouped together.  The coffee was ok, and I had a delicious ‘Mediterranean Eggs‘ (poached eggs, lime-infused zatar, feta, pine nuts, Israeli salad with sourdough).

November 2, 2014

Project Euler: problem 95 (PHP) – Amicable chains

Filed under: PHP,Project Euler — duncan @ 3:50 pm

bike chainI’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 95:

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

This puzzle took me a while to get right.  The question doesn’t really give you enough details I think, so it pays to do a bit of research into what perfect numbers, amicable pairs and amicable chains are.  Perfect numbers are an amicable chain with length = 1, and amicable pairs are amicable chains with length = 2.

Continuously adding up the divisors of numbers (the factors of a number apart from the number itself) is called the Aliquot sequence.  Eventually you should either end up running into an amicable chain, or you’ll reach a prime number (i.e. its divisors = 1, and you can’t go any further).  However there are theoretically numbers who’s Aliquot sequence never terminates.  I guess that’s why this question makes sure we don’t have any individual numbers over 1 million.

One thing that’s useful to know, the question doesn’t give you a clue on when you’ll know you’ve reached the longest amicable chain; I assumed it might be into the hundreds.  Fortunately the Wikipedia article on sociable numbers reveals that the longest one is a chain of only 28 numbers in length.


$start = microtime(true);

$number = 1;
$limit = 1000000;
$amicableChains = []; 
$length = 0;
$maxLength = 28;

while ($length < $maxLength) {
	$chain = [];
	$currentNumber = $number;

	while (true) {
		$divisors = getDivisors($currentNumber);
		$currentNumber = array_sum($divisors);
		if (array_key_exists($currentNumber, $amicableChains)) {
			$amicableChains[$number] = $amicableChains[$currentNumber];
		if ($currentNumber == 1) {
		// break out if we're over a certain length of number
		if ($currentNumber > $limit) {
		if (in_array($currentNumber, $chain)) {
			$key = array_search($currentNumber, $chain);
			$amicableChains[$number] = array_slice($chain, $key);
			$length = count($amicableChains[$number]);
		$chain[] = $currentNumber;

uasort($amicableChains, function($a, $b) {
	return count($a) > count($b);

echo min(end($amicableChains));

$end = microtime(true);
printf("<br>Execution time: %dms", ($end - $start) * 1000);

function getDivisors($number) {
	$factors = [1];
	$root = sqrt($number);
	for ($i = 2; $i <= $root; $i++)
		if ($number % $i == 0)
		{	// it's a factor
			$factor1 = $i;
			$factor2 = $number / $i;
			$factors[] = $factor1;
			if ($factor1 != $factor2) {
				$factors[] = $factor2;
	return $factors;

So we loop until we’ve reached a chain with a length of 28+.

Within that loop we have an inner loop, where we calculate the sum of the divisors.  We break out of that inner loop if:

  • we reach a value we already have the amicable chain for
  • the sum of divisors reaches 1
  • we have a value that exceeds one million
  • we get to a value that we already have in the current chain, i.e. we’ve reached a new amicable chain

Initially I had some logic in that inner loop to break out if the current number equalled the previous number, i.e. we had reached a perfect number, an amicable chain of length = 1.  However that wasn’t really required, as the final if statement further down covered it anyway, and it didn’t really slow things down to just use that.

Once we get an amicable chain, I store that chain keyed on the number we’re currently looping over.  N.B this number may not be part of the chain itself.  For instance the divisors of 562 are 1, 2 and 281.  The sum of these is 284.  We already know that 284 is part of the amicable chain 220 → 284.  So the aliquot sequence for 562 is 220 → 284.

Once we’ve reached our limit of a chain with length of 28, I then use the uasort() function to have a user-defined function which sorts my array of amicable chains based on the length of each array within it.  Then I use end() to get the last of those amicable chains, i.e. the longest.  And min() to get the smallest value within that chain.

Job done, running time about 1.5 seconds on average.


October 29, 2014

Project Euler: problem 99 (PHP) – Largest exponential

Filed under: PHP,Project Euler — duncan @ 7:00 am

99I’m doing these Project Euler mathematical puzzles as a simple practical exercise for teaching myself PHP, and I’d appreciate any feedback on my code.

Problem 99:

Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.

However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt, a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

Interesting, sounds quite difficult.  At first I thought I could use the BC Math functions which have proven so useful in many of the previous puzzles and “support numbers of any size and precision”.  However they didn’t seem to work; according to this StackExchange question they “can handle numbers greater than 2^1000000 (which is 301,030+ digits)“. We’re dealing with numbers here that are ten-fold of that!  So I used the GMP functions instead, which “allow you to work with arbitrary-length integers”.

$pairs = file('p099_base_exp.txt');

$max = 0;

foreach($pairs as $key=>$pair) {
	$numbers = explode(",", $pair);
	$base = $numbers[0];
	$exponent = $numbers[1];

	$power = gmp_pow($base, intval($exponent));
	if (gmp_cmp($power, $max) > 0) {
		$max = $power;
		$lineNumber = $key;

echo $lineNumber+1;

I read the file in using file(), turning each line into an array element.  I then loop over those 1000 array elements, using explode() to split each line into its base and exponent parts.

Then I use the gmp_pow() function; however when I tried it initially simply using gmp_pow($base, $exponent) it threw up this error: “A non well formed numeric value encountered“.  It expects $exponent to be an integer, which to all intents and purposes, it seems to be.  However I had to explicitly cast it to an integer, using either intval($exponent) or (int)$exponent – both seemed to work.

Initially I thought I had to use a GMP number for the base, so was using gmp_init() to create one from $base.  However in the end that didn’t seem to be necessary.  So the gmp_pow() function is fussy about what kind of value it gets for the exponenent, but less-so for the base… curious.

After working out the power, I then compare it the maximum power so far, using gmp_cmp().  Each time I get a new maximum value I keep track of which line number that belongs to.  At the end when I output that I increment it by 1, due to PHP arrays being zero-indexed.

This is very slow code, taking close to 5 minutes!

PS: to get the GMP functions to work on my Windows environment I had to uncomment this line in php.ini:

Next Page »

The Rubric Theme. Create a free website or blog at WordPress.com.


Get every new post delivered to your Inbox.

Join 543 other followers