# Sunday Times Teaser 3042 – A Question of Scale

*by Colin Vout*

#### Published Sunday January 10 2021 (link)

The modernist music of Skaredahora eschewed traditional scales; instead he built scales up from strict mathematical rules.

The familiar major scale uses 7 notes chosen from the 12 pitches forming an octave. The notes are in (1) or out of (0) the scale in the pattern 101011010101, which then repeats. Six of these notes have another note exactly 7 steps above (maybe in the next repeat).

He wanted a different scale using 6 notes from the 12 pitches, with exactly two notes having another note 1 above, and one having another 5 above. Some notes could be involved in these pairings more than once.

His favourite scale was the one satisfying these rules that came first numerically when written out with 0s & 1s, starting with a 1.

What was Skaredahora’s favourite scale?

This is an interesting but straightforward teaser for which there are quite a few different approaches. My first approach used a pretty standard approach but after seeing Jim Randell’s solution I adopted his neat trick of generating scales in numerical order in my second solution. I then decided to compare the speed of my two versions and Jim’s version (with a small speed improvement) using a timer that is available here.

I have now added Jim’s second version to this speed comparison. For the ‘bit hack’ it uses see this page I have also added two versions provided by Frits and my latest version below.

Here is my fastest version:

It runs in 28 microseconds on my system.

The following function is faster:

Very nice, is the version with the Python 3.10 bit_count function even faster?

In line 21 (b2 right shift 5) is always the same as b.

If I understand correctly in line 20 you also could have used left shift iso right shift?

Line 20 gives an incorrect bit count of 2 for an entry like 0b110010101010 as b2 contains 17 bits iso 13.

I checked quite a few bit count functions and yours seems to be the fastest.

Thanks for checking my latest version out. The Python 3.10 version of bit_count is a lot slower but its new and 3.10 is currently in its alpha release so its almost certainly not optimised yet. On the error in bit counting I fear that I am clearly a bit rusty on this stuff (I used to do a lot of it). I have now tried again and, fortunately, its actually fractionally faster on my system (but, sadly, its not as well tested as it should be).

Until we have [[ int.bit_count() ]] the fastest way to count set bits I have found in Python is:

Thanks Jim. Although this makes no measurable difference here because the integers are very short, this is a great deal faster as a general purpose bit_count function.

Hi John,

I find your first solution above has very clear code and is nicely presented, making it easy to follow.

I also prefer your output, using spaces between the notes of the scale to higlight individual notes.

Without the spaces, the output, in my view, looks more like a binary number – although we know the ‘1’s are the white notes and the ‘0’s are the black notes.

The twelve notes in the starting scale could be, for the piano:

C, C#, D, D#, E, F, F#, G, G#, A, A#, B

(1 0 1 0 1 1 0 1 0 1 0 1)

A second version of my solution drawing on elements from my solution and from Brian’s and using negative indexing to avoid modular arithmetic.

It would probably be faster to generate and test scales on the fly rather than generating all possible scales and then testing them but it would require more lines of code.

Hi John,

You are right about the speed as it is more than twice as fast but it does not require more lines of code:

Neat indexing, John, apologies for the earlier mistranslation.

With a faster bit count function (special version) and a faster “another note 1 above” check.

Here is a version which does not use conversion of numbers to strings: