mscroggs.co.uk
mscroggs.co.uk

subscribe

Blog

 2019-06-19 
Last night at MathsJam, Peter Kagey showed me a conjecture about OEIS sequence A308092.
A308092
The sum of the first \(n\) terms of the sequence is the concatenation of the first \(n\) bits of the sequence read as binary, with \(a(1) = 1\).
1, 2, 3, 7, 14, 28, 56, 112, 224, 448, 896, 1791, 3583, 7166, ...
To understand this definition, let's look at the first few terms of this sequence written in binary:
1, 10, 11, 111, 1110, 11100, 111000, 1110000, 11100000, 111000000, ...
By "the concatenation of the first \(n\) bits of the sequence", it means the first \(n\) binary digits of the whole sequence written in order: 1, then 11, then 110, then 1101, then 11011, then 110111, and so on. So the definition means:
As we know that the sum of the first \(n-1\) terms is the first \(n-1\) digits, we can calculate the third term of this sequence onwards using: "\(a(n)\) is the concatenation of the first \(n\) bits of the sequence subtract concatenation of the first \(n-1\) bits of the sequence":

The conjecture

Peter's conjecture is that the number of 1s in each term is greater than or equal to the number of 1s in the previous term.
I'm going to prove this conjecture. If you'd like to have a try first, stop reading now and come back when you're ready for spoilers. (If you'd like a hint, read the next section then pause again.)

Adding a digit

The third term of the sequence onwards can be calculated by subtracting the first \(n-1\) digits from the first \(n\) digits. If the first \(n-1\) digits form a binary number \(x\), then the first \(n\) digits will be \(2x+d\), where \(d\) is the \(n\)th digit (because moving all the digits to the left one place in binary is multiplying by two).
Therefore the different is \(2x+d-x=x+d\), and so we can work out the \(n\)th term of the sequence by adding the \(n\)th digit in the sequence to the first \(n-1\) digits. (Hat tip to Martin Harris, who spotted this first.)

Carrying

Adding 1 to a binary number the ends in 1 will cause 1 to carry over to the left. This carrying will continue until the 1 is carried into a position containing 0, and after this all the digits to the left of this 0 will remain unchanged.
Therefore adding a digit to the first \(n-1\) digits can only change the digits from the rightmost 0 onwards.

Endings

We can therefore disregard all the digits before the rightmost 0, and look at how the \(n\)th term compares to the \((n-1)\)th term. There are 5 ways in which the first \(n\) digits could end:
We now look at each of these in turn and show that the \(n\)th term will contain at least as many ones at the \((n-1)\)th term.

Case 1: \(00\)

If the first \(n\) digits of the sequence are \(x00\) (a binary number \(x\) followed by two zeros), then the \((n-1)\)th term of the sequence is \(x+0=x\), and the \(n\)th term of the sequence is \(x0+0=x0\). Both \(x\) and \(x0\) contain the same number of ones.

Case 2: \(010\)

If the first \(n\) digits of the sequence are \(x010\), then the \((n-1)\)th term of the sequence is \(x0+1=x1\), and the \(n\)th term of the sequence is \(x01+0=x01\). Both \(x1\) and \(x01\) contain the same number of ones.

Case 3: \(01...10\)

If the first \(n\) digits of the sequence are \(x01...10\), then the \((n-1)\)th term of the sequence is \(x01...1+1=x10...0\), and the \(n\)th term of the sequence is \(x01...10+1=x01...1\). \(x01...1\) contains more ones than \(x10...0\).

Case 4: \(01\)

If the first \(n\) digits of the sequence are \(x01\), then the \((n-1)\)th term of the sequence is \(x+0=x\), and the \(n\)th term of the sequence is \(x0+1=x1\). \(x1\) contains one more one than \(x\).

Case 5: \(01...1\)

If the first \(n\) digits of the sequence are \(x01...1\), then the \((n-1)\)th term of the sequence is \(x01...1+1=x10...0\), and the \(n\)th term of the sequence is \(x01...1+1=x10...0\). Both these contain the same number of ones.

In all five cases, the \(n\)th term contains more ones or an equal number of ones to the \((n-1)\)th term, and so the conjecture is true.
                        
(Click on one of these icons to react to this blog post)

You might also enjoy...

Comments

Comments in green were written by me. Comments in blue were not written by me.
 Add a Comment 


I will only use your email address to reply to your comment (if a reply is needed).

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li> <logo>
To prove you are not a spam bot, please type "w" then "i" then "d" then "t" then "h" in the box below (case sensitive):
 2016-12-28 
More than ten correct solutions to this year's Advent calendar puzzle competition were submitted on Christmas Day, so the competition is now over. (Although you can still submit your answers to get me to check them.) Thank-you to everyone who took part in the puzzle, I've had a lot of fun watching your progress and talking to you on Twitter, Reddit, etc. You can find all the puzzles and answers (from 1 January) here.
The (very) approximate locations of all the entries I have received so far are shown on this map:
This year's winners have been randomly selected from the 29 correct entries on Christmas Day. They are:
1Jack Jiang
2Steve Paget
3Joe Gage
4Tony Mann
5Stephen Cappella
6Cheng Wai Koo
7Demi Xin
8Lyra
9David Fox
10Bob Dinnage
Your prizes will be on their way in early January.
Now that the competition has ended, I can give away a secret. Last year, Neal suggested that it would be fun if a binary picture was hidden in the answers. So this year I hid one. If you write all the answers in binary, with each answer below the previous and colour in the 1s black, you will see this:
I also had a lot of fun this year making up the names, locations, weapons and motives for the final murder mystery puzzle. In case you missed them these were:
#Murder suspectMotive
1Dr. Uno (uno = Spanish 1)Obeying nameless entity
2Mr. Zwei (zwei = German 2)To worry others
3Ms. Trois (trois = French 3)To help really evil elephant
4Mrs. Quattro (quattro = Italian 4)For old unknown reasons
5Prof. Pum (pum = Welsh 5)For individual violent end
6Miss. Zes (zes = Dutch 6)Stopping idiotic xenophobia
7Lord Seacht (seacht = Irish 7)Suspect espied victim eating newlyweds
8Lady Oito (oito = Portuguese 8)Epic insanity got him today
9Rev. Novem (novem = Latin 9)Nobody in newsroom expected

#LocationWeapon
1Throne roomWrench (1 vowel)
2Network roomRope (2 vowels)
3Beneath reedsRevolver (3 vowels)
4Edge of our gardenLead pipe (4 vowels)
5Fives courtNeighbour's sword (5 vowels)
6On the sixth floorSuper banana bomb (6 vowels)
7Sparse venueAntique candlestick (7 vowels)
8Weightlifting roomA foul tasting poison (8 vowels)
9Mathematics mezzanineRun over with an old Ford Focus (9 vowels)
Finally, well done to Scott, Matthew Schulz, Michael Gustin, Daniel Branscombe, Kei Nishimura-Gasparian, Henry Hung, Mark Fisher, Jon Palin, Thomas Tu, Félix Breton, Matt Hutton, Miguel, Fred Verheul, Martine Vijn Nome, Brennan Dolson, Louis de Mendonca, Roni, Dylan Hendrickson, Martin Harris, Virgile Andreani, Valentin Valciu, and Adia Batic for submitting the correct answer but being too unlucky to win prizes this year. Thank you all for taking part and I'll see you next December for the next competition.
                        
(Click on one of these icons to react to this blog post)

You might also enjoy...

Comments

Comments in green were written by me. Comments in blue were not written by me.
Thanks for the prizes. Fascinating books!
Steve Paget
×1                 Reply
I got my prize in the mail today. I really liked the stories from Gustave Verbeek; I thought that was pretty clever. I really appreciate you being willing to send the prizes internationally.

Thanks for setting this all up; I had a lot of fun solving the puzzles every day (and solving half them again when my cookie for the site somehow got deleted). I'll be sure to participate next time too!
SC
×1                 Reply
Thanks, Matthew! The puzzles were really fun, and piecing the clues was very interesting too!
Jack
×1                 Reply
 Add a Comment 


I will only use your email address to reply to your comment (if a reply is needed).

Allowed HTML tags: <br> <a> <small> <b> <i> <s> <sup> <sub> <u> <spoiler> <ul> <ol> <li> <logo>
To prove you are not a spam bot, please type "z" then "e" then "r" then "o" in the box below (case sensitive):

Archive

Show me a random blog post
 2024 

Feb 2024

Zines, pt. 2

Jan 2024

Christmas (2023) is over
 2023 
▼ show ▼
 2022 
▼ show ▼
 2021 
▼ show ▼
 2020 
▼ show ▼
 2019 
▼ show ▼
 2018 
▼ show ▼
 2017 
▼ show ▼
 2016 
▼ show ▼
 2015 
▼ show ▼
 2014 
▼ show ▼
 2013 
▼ show ▼
 2012 
▼ show ▼

Tags

accuracy video games map projections hannah fry hyperbolic surfaces geogebra pi zines finite group binary quadrilaterals martin gardner menace reddit pi approximation day manchester science festival folding paper fonts platonic solids phd big internet math-off sound craft bodmas databet numerical analysis inline code propositional calculus royal baby european cup arithmetic golden ratio a gamut of games national lottery people maths cambridge graph theory determinants data php harriss spiral chebyshev polynomials christmas card hats mathslogicbot triangles logic dinosaurs frobel programming graphs weather station logs london signorini conditions anscombe's quartet gather town data visualisation coins javascript python boundary element methods probability statistics game show probability stirling numbers latex estimation cross stitch dragon curves sport realhats wool edinburgh games finite element method matrix of minors light mean books bubble bobble guest posts matt parker reuleaux polygons inverse matrices errors asteroids palindromes christmas pythagoras curvature hexapawn youtube oeis golden spiral 24 hour maths live stream ternary sobolev spaces matrices dataset noughts and crosses world cup game of life sorting preconditioning trigonometry matrix multiplication numbers plastic ratio matrix of cofactors weak imposition the aperiodical fractals approximation raspberry pi countdown pac-man football turtles mathsjam bempp chess go correlation crochet squares error bars final fantasy rugby nine men's morris radio 4 wave scattering interpolation ucl rhombicuboctahedron runge's phenomenon london underground pizza cutting news tmip puzzles machine learning draughts mathsteroids braiding royal institution fence posts logo crossnumber tennis electromagnetic field speed advent calendar computational complexity manchester exponential growth talking maths in public standard deviation stickers folding tube maps datasaurus dozen misleading statistics flexagons geometry newcastle captain scarlet gaussian elimination gerry anderson chalkdust magazine simultaneous equations dates convergence recursion pascal's triangle

Archive

Show me a random blog post
▼ show ▼
© Matthew Scroggs 2012–2024