Solving the Project Euler Problems – Problem 3

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

This problem is the first one that has taken some real effort, as no language seems to have any built-in function for determining whether or not a number is prime.

Part of my memory however is convinced that the R language, which I first worked with all the way back in university, did have a function to list all the prime factors of a number, so either my memory is corrupted or, well, chances are it is, as even after sending hopeful texts to people I’m still in touch with from that same course I came up dry. Relearning R is something for another day though, so for this problem, Python it is!

The reason for Python over PHP, as I could just as unhappily do this one in PHP, is that the point of doing these exercises is to expand my knowledge of multiple languages rather than just “solve them”.

Going forward I will likely solve these in a number of languages, but I certainly envisage the main 2 being PHP and Python.

No gists found

Trying to work out a function that would return the prime factors of a number has turned out to be a huge pain, and even then by looking at the code you’ll see I still haven’t managed it! This function does however iterate through the number, reducing it down to its highest prime factor, also covering the case where our number itself is prime.

I even tried venturing into the world of generators and using yield rather than return – definitely something to leave for another day frankly, maybe later in these problems, who knows?

Solving the Project Euler Problems – Problem 2

The main consideration here was how to calculate the Fibonacci sequence without taking up too many resources, a common danger with recursive functions which are often touted as the solution for working out the sequence and other things like factorials. It turns out the Fibonacci sequence as a recursive function is fine up until about the 10th term, but any further than that? Not advisable!

No gists found

The much quicker solution that I’ve found is to do it as an array, which takes simple values for its calculations rather than calling a recursive function again and again and again.

The second performance optimisation is checking whether our Fibonacci number is even, which when doing it a limited number of times, is fine to do just by checking if n modulo 2 is 0, but how many times will we be doing this? Off the top of your head which Fibonacci term is the largest below 4,000,000? The 10th? The 50th? The 1,000th? We don’t know how many until we actually do it. As it happens it’s the 32nd term, 3,524,578. Run that recursive function 32 times!

As division is slow and all we’re using it to do is check if a number is even, is there a better way? Well kind of, we can check if it isn’t odd. This is done by using the bitwise AND operator. This takes the binary representation of a number – 2019’s would be 11111100011 – and it’s that final bit we’re interested in, if it’s 1 then the number is odd and if it’s 0 it’s even. So using the bitwise AND operator to compare any number to 1 checks only 2 bits and avoids division.

Solving the Project Euler Problems – Problem 1

After stumbling across an article on Medium by Bennett Garner, I discovered the Project Euler problems and that it would be a good idea to showcase my skills in solving them in a variety of ways, as a good starting point to get a code portfolio going, so here goes with – as natural a starting point as any – problem 1!

All of the Project Euler Problems can be found at ProjectEuler.net.

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.

No gists found

There were 2 ways I considered to tackle this:

  • Loop from 1 to 1000 (or as in the code, n) and check each number for dividing by 3 and 5 respectively, adding them to the result if either is true
  • Reduce the number of loops by 47% and run our loop n/3 + n/5 times (for those interested, 1/3 + 1/5 = 8/15, so this reduction percentage works for any integer), by dividing n by 3, running that loop, adding 3 times each number to the result – which takes division out of the loop as well – then doing the same again, only now having to check (on a smaller loop) if our result was already added as being a multiple of 3.

CSS nth-child selectors

You can do all sorts of thing with nth-child selectors, such as selecting the first child element, 5th, 10th, 14th or even last, 2nd-last etc.and primarily that is what it was used for, but there are so many more thing you can (and probably would want to in certain situations) do besides…

Now I haven’t ever really come across anywhere on the web that has everything you can do with CSS nth-child selectors all in one place, so this is what I’m aiming to achieve.

Now there are 2 main flavours of child selectors in CSS, they are :nth-child(n) and :nth-of-type(n). :nth-child can be used on its own as it can simply select the nth child of, say a div element. Each of these can be used along with a selector, say, p:nth-of-type(n) or li:nth-child(n).

So what would be the difference be between p:nth-child(3) and p:nth-of-type(3)?

  • p:nth-child(3) will select a p element that is the 3rd element of its parent element. If the 3rd child of that parent element isn’t a p element, it simply won’t select anything.
  • p:nth-of-type(3) will select the third p element within the parent element, even if it is not the 3rd child, it could be the 4th, or the 15th. If there are fewer than 3 p elements within the parent element, it simply won’t select anything.
  • p:nth-child(3) and p:nth-of-type(3) will select the same p element if, and only if, we start off our parent element with 3 uninterrupted p elements.

So now that that’s out of the way, on to what we can do with the selectors!

Selecting all child elements

You may have, say, a div tag where you want to do something to each of its children, but not the div itself, for this you simply combine the div with the universal selector, which is *, for a result of div * {your style here}.

Selecting a certain child

The most simple thing to do is select a single child element based on its position within its parent element, for this we would use, for example, nth-child(4) to select the 4th child element.

A couple of important shortcuts are below with any more to follow:

  • :nth-child(1) = :first-child
  • :nth-of-type(1) = :first-of-type

Now we go on to selecting a subset of child elements. This is where the real fun begins…

Selecting a subset of child elements

Starting off with a really simple and common example – we have a table with a header row, and a few rows where we want to alternate the background colours.

The term itself – nth – has its roots in calculus, and as such we can use an expression such as 2n to select every even child element of a parent, a popular example is styling alternate rows in a table, for which you would use table tr:nth-child(2n). This means that our styling will apply to 2 x 0 = the 0th child (no such thing), the 2 x 1 = 2nd child, the 2 x 2 = 4th child, and so on until the 2nth child doesn’t exist i.e. we’ve reached the end of the table.

To select all the odd rows instead we can replace the 2n with 2n+1, so our styling will now apply to 2 x 0 + 1 = the 1st child, 2 x 1 + 1 = 3rd child, 2 x 2 + 1 = 5th child and so on, again until the 2n+1th child doesn’t exist.

As you may be suspecting at this point however, we again have some useful shortcuts:

  • :nth-child(2n) = :nth-child(even)
  • :nth-child(2n+1) = :nth-child(odd)
  • :nth-of-type(2n) = :nth-of-type(even)
  • :nth-of-type(2n+1) = :nth-of-type(odd)

Of course however there are far more subsets then just even and odd, what if we are wanting something a bit more advanced, like selecting every 4th child, or selecting every 5th child, starting at the 2nd one (so 2nd, 7th, 12th etc.)?

Luckily the 2 in 2n and 1 in, uh, 1, can be replaced by any integer, so if we wanted to select every 4th child it would simply be :nth-child(4n), if we wanted to select every 5th child starting from the second we’d start with :nth-child(5n) but then we’d need to “shift” it by adding -3, as 5 – 3 = 2, so our final result would be :nth-child(5n-3).

There aren’t any shortcuts for these particular setups unfortunately. However we can use them to create another 2 subsets: the first few child elements or all but those first few:

Selecting all but, or only, the first or last few elements

The way to select the first 5 child elements seems a bit counterintuitive, but it would be :nth-child(-n+5), as it would go through -0 + 5 = 5th child, -1 + 5 = 4th child, -2 + 5 = 3rd child and so on until it arrives at the 0th child which of course doesn’t exist. For selecting all but the first 5, we essentially want to start our selection at the 6th child, so this is a much simpler :nth-child(n+6).

Now we know how to select single child elements and subsets of those child elements, however there is one other thing that I myself have recently run into. All of our subsets have either started at the beginning or ended at the end, but what if we want a subset that starts and ends somewhere in the middle?

I came across this when doing a piece on SVG transformations and in particular matrices, a mathematical concept that is essentially a grid of numbers, so I used CSS grid to create my matrix, being a 3×3 matrix I simply called it matrix-3:

.matrix-3 {
    display: inline-grid;
    grid-template-columns: repeat(3, auto);
    grid-template-rows: repeat(3, auto);
}

Now I will want the first 3 children on the first row, the next 3 on the second and the final 3 on the third, as well as this I will want the 1st, 4th and 7th children in the 1st column, the 2nd, 5th and 8th children in the 2nd column, and the 3rd, 6th and 9th children in the 3rd column.

Now I could go through each child element, tell the first child to be in row 1 column 1, tell nth-child(2) to be in row 1 column 2 etc. or I could reduce 9 statements into 6 by starting off with nth:child(3n+1) {grid-column: 1;} to tell the first, 4th and 7th elements their column, then nth:child(3n+2) {grid-column: 2;} and finally nth:child(3n) {grid-column: 3;}.

Now we can select our first 3 elements no problem, and tell them to go into row 1, :nth-child(-n+3) {grid-row: 1;}, and our last 3 elements we can tell to go into row 3, :nth-child(n+7) {grid-row: 3;}. But how do we now select our middle 3?

Selecting a central subset of elements

i.e. one that doesn’t start at the beginning of our parent, or end at the end

The neatest (and so far only, so also messiest) way I have found of doing this is by doubling-up on our selectors, so starting with :nth-child(n+4) to give us the last 6 elements we can now add :nth-child(-n+6) to pick those elements that are also in the first 6, so we basically end up with :nth-child(n+4):nth-child(-n+6) {grid-row: 2;}. So think of it as chaining multiple nth-child selectors together as a sort of AND statement if you will.

So there we have it, everything (that I can think of at least) that you may want to do with CSS nth-child selectors!

Questions or comments? Or anything that you’d want to do with nth-child selectors that perhaps doesn’t appear in this post? Let me know in the comments below!