CLICK HERE TO SEE THE ORIGINAL PUZZLE
Scroll down for the Solution and the Mystery Prize,
or read on for a discussion of the puzzle.
THANK YOU
Thank you to everyone who took part in the sequence challenge. The response was brilliant and far greater than I had imagined. There were 55 rule guesses in total, spread over 19 days, ranging from the mathematically sophisticated (the output of a linear feedback shift register), through the musical (the number of notes at the nth beat of Chopin’s Funeral March), to the ridiculous (the number of weetabix that I had eaten that morning), via the frustrated (flipping a coin).
THE SUGGESTIONS
A popular early suggestion (first proposed by Troy R in the very first comment) was that the nth term was equal to the number of 1s in the binary representation of n. As we will see, this was actually pretty close to the true solution, but since this rule only matched the first six terms, it was quickly discarded.
Another rule that was suggested multiple times (first by Michael Bench-Capon on Day 1) was that the sequence represented the number of odd divisors of n. This rule was slightly ‘better’ than the number of binary ones idea, in that it matched the first eight terms of the sequence.
These two rule suggestions set the tone for much that followed, in that the two persistent angles of attack from those thinking about the puzzle seemed to be that the solution was either something to do with factors or something to do with binary. I find it rather intriguing that these two quite different mathematical approaches were both able to provide a number of potential rules that matched the sequence for significant numbers of terms.
One suggestion from the binary strand that turned up a few times (first from BurHanSolo on Day 3) was that the sequence represented the number of divisors of n that are also suffixes of n in binary representation. I was pretty confident that this delightfully obscure rule would be suggested at some point, because it happens to be the OEIS sequence that agrees with the challenge sequence longer than any other, matching the first twenty-two terms. However, as I had made sure not to choose something from the OEIS (because I didn’t want the answer to be something that you could find on Google), this rule was never going to be the solution.
On the factor side, another rule that got a few outings (first suggested by Simon K on Day 4) was the idea that the sequence was the number of prime factors of 2n + 1, including repeated factors. This matched the challenge sequence for the first eight terms.
At this point, with nine terms on the board, people started to focus on one particular property of the sequence that was becoming fairly obvious. All of the terms were 1s and 2s (this would later prove not to be a general property of the sequence) and the 1s seemed to appear at precisely the positions of the sequence that were powers of two (this was a general property). Application of Occam’s razor thus led Troy R (on Day 4) and many others to suggest that the rule might be exactly this: the nth term is a 1 if and only if n is a power of two, otherwise it is a 2. This rule matches the challenge sequence for the first fourteen terms (i.e. until the arrival of the first 3).
The marginally more elegant suggestion that the nth term represents the number of distinct binary digits of n, starting from n = 0, which was also suggested several times (first by BurHanSolo on Day 5), is actually completely equivalent to the powers of two rule described above, as pointed out by Michael Bench-Capon on Day 7.
A hopeful adaptation of the powers of two rule was that the sequence was simply a series of 1s, separated by consecutive triangle numbers of 2s (first suggested by by Michael Bench-Capon on Day 7). Again, this idea cropped up a few times, but it also agrees with my sequence for only the first fourteen terms.
The arrival of the first 3 at term 15 forced a rethink from many who were following the puzzle. One new suggestion was a clever factor-based idea (first proposed by Peter Baudains on Day 11), which had significant similarities to the earlier number-of-odd-divisors idea. The suggested rule was simply 1 + the number of distinct odd prime factors of n. This rule – presumably deduced through consideration of which unique properties of 15 (the first product of distinct odd primes) could have given rise to the rogue 3 – matches my sequence for a very respectable twenty terms.
In fact, the above rule is equivalent to the number of prime factors of 2n, first suggested by Ed Southall (of Solve My Maths, also on Day 11), and the number of non-composite odd factors of n, another suggestion from Troy R (on Day 12).
From Day 12 onward, with sixteen terms revealed, people began to flirt ever more closely with the correct answer. The first such flirtation came from Jesse Thompson, who proposed quite a complicated solution, which agreed with my sequence for the first twenty-two terms, and which involved the function “floor(log₂n)+1”. This function simply calculates the number of binary digits of n, an idea that forms a key part of the true solution (though the way that Jesse had used it was admittedly a dead end).
However, Jesse Thompson got even closer to a correct answer on Day 13 with the suggestion that the rule might be “f(n) = ceil(hamming_weight(n) * k)”, for some suitable constant k. This rule is basically saying that the sequence is proportional to the number of 1s in the binary representation of n, rounded up. With an appropriate value of k (e.g. k = 0.51), this rule could match my sequence for an impressive sixty-two terms, by far the ‘best’ suggestion, other than the correct answer. Moreover, if Jesse had combined this idea with his previous guess, he would have had all the ingredients required to solve the puzzle.
The third close call came from Tom Flowerdew (on Day 16, with twenty terms revealed), who managed to combine the binary and factor lines of attack to create a rule that matched mine up to term 30, suggesting that the nth term was the number of factors of the number of 1s in the binary representation of n. Given how close they were getting, I imagine that either Tom or Jesse (and probably one or two other people mentioned above) would have hit upon the correct solution had the challenge continued for a few more days.
Honourable mentions go to all those other ingenious solutions that were submitted, which I haven’t had time to mention, particularly this one from Chris, this one from Aditya Sharad, this one from John G, and this one from Dan.
THE SOLUTION
Appropriately, having submitted the very first suggestion on Day 1, the winner of the contest was Troy R, who came up with the correct rule on Day 18, with twenty-two terms of the sequence revealed.
A massive well done for Troy for being the
first to guess the rule, after 18 days of trying!
Here is Troy’s winning suggestion:
The rule could also be expressed as follows:
The nth term is equal to the number of binary digits
of the number of 1s in the binary representation of n.
In other words: take n; express it in binary; count the 1s; express that number in binary; count the digits; that’s the nth term.
In some ways, it was a shame that the challenge was solved when it was (after term 22 was revealed), as we were about to see only the second 3 (term 23), followed by a run of eight terms involving several more 3s, which would have given a lot more information to those seeking the solution. As it was, after the five terms originally given on Day 1, fourteen of the seventeen terms that I revealed were 2s.
Troy R also finished top of the leader board for correctly predicting the next term on more days (11) than anyone else, so many congratulations to him on several fronts! Second place went to Jesse Thompson (9) and third to Aaron Percival (8).
SOME FACTS ABOUT THE SEQUENCE
- Every positive integer appears in the sequence infinitely many times…
- … but the terms grow extremely slowly: the maxima grow like 1 + log2(log2(n+1)).
- The first 4 would have been posted on Sunday, 08 May 2016, appearing at term 255
(because 255 is the first number whose binary representation contains eight 1s, and 8 is the first number with four binary digits). - The first 5 would have been posted on Friday, 30 January 2195, appearing at term 65535
(because 65535 is the first number whose binary representation contains sixteen 1s, and 16 is the first number with five binary digits). - 1s occur at positions that are powers of two and nowhere else…
- … and the sequence continues in an identical fashion after every 1 (until interrupted by another 1).
THE MYSTERY PRIZE
The mystery prize is completely unrelated to the puzzle itself. However, there was a clue to its identity (though an admittedly impenetrable one) in the purple bars used to frame the sequence on the puzzle page.
Those bars were details from the photo on the right, which pictures the discharge from a Tesla coil at the Vienna Technical Museum.
.
The prize is a copy of the book:
The Man who Invented the Twentieth Century:
Nikola Tesla, Forgotten Genius of Electricity
by Robert Lomas
I found this on my bookshelf, unread, and figured that I probably never would get round to reading it, so I decided to offer it as a prize. However, it actually has very good reviews on Amazon (see the link above), so now I wonder whether I have perhaps been too hasty and might need to buy a new copy for myself so that I can read it after all.
Thanks again for taking part everyone.
.
.
IMAGES
Tesla coil: Creative Commons – Wikimedia Commons – Manfred Werner
Book cover: From the Amazon listing. I claim fair use, since this amounts to a recommendation.
Click here to return to the Puzzles page
Thomas Oléron Evans, 2015