COOL MATH: Very Triangular Numbers
James Tanton - November 29, 2016
This essay starts with a puzzle I posed on twitter, which led to a next puzzle, and a next. My thanks to @republicofmath and @sted304A for computing very very triangular numbers, and to @daveinstpaul for an elegant idea giving a proof.
OPENING PUZZLER:The sequence of numbers that are the sum of two distinct powers of two begins: \(3=1+2\) \(5=1+4\) \(6=2+4\) \(9=1+8\) \(10=2+8\) \(12=4+8\) What is the 50th number in this list? |
NUMBERS IN BINARY
The very first machine we discuss in the story of Exploding Dots is the \(1 \leftarrow 2\) machine. (See lessons 1.1 and 1.2 here.) There we learn that every counting number can be expressed in a code of \(0\)s and \(1\)s, which corresponds to writing each number as a sum of distinct powers of two. For instance,
\(13 \leftrightarrow 1101=8+4+(omit \space 2) +1\).
We call these representations of number binary or base two representations.
| Question: Is it obvious that each binary representation of a counting number is unique? |
We can conduct arithmetic in base two in much the same way as we conduct arithmetic in base ten: we just now “carry the two.”
| The second example suggests
\(1+1+2+2^2+2^3+\cdots+2^n=2^{n+1},\) which is a special case of the geometric series formula. (What’s the base-ten version of this observation?) We can also see this formula from repeatedly folding a strip of paper right to left.
|
The powers of two, \(1, 2, 4, 8, 16, \ldots\), are the numbers with precisely one \(1\) in each of their binary representations.
The opening puzzle asks for the fiftieth number with precisely two \(1\)s in its binary representation. The first \(1+2+3+4=10\) of these numbers are
\(11 \leftrightarrow 3\)
\(101 \leftrightarrow 5 \)
\(110 \leftrightarrow 6\)
\(1001 \leftrightarrow 9\)
\(1010 \leftrightarrow 10\)
\(1100 \leftrightarrow 12\)
\(10001 \leftrightarrow 17\)
\(10010 \leftrightarrow 18\)
\(10100 \leftrightarrow 20\)
\(11000 \leftrightarrow 24\).
In general, there are \(n\) such numbers with \(n+1\) digits in base two: have a \(1\) followed by \(n\) digits with just one of those digits a \(1\). There are thus \(1+2+3+\cdots +n\) numbers with two \(1\)s in their binary representations with at most \(n+1\) digits.
As \(1+2+3+\cdots + 8+9=45\), the 45th number in the desired list is ten digits long in binary and is
\(11 \space 0000 \space 0000 \leftrightarrow 512 + 128 = 640.\)
The fiftieth such number is eleven digits long in binary and is
\(100 \space 0001 \space 0000 \leftrightarrow 1024 + 16 = 1040\).
| Challenge: What is the fiftieth number that is the sum of three distinct powers of two? |
| Challenge: What is the million-and-first number with an odd number of s in its binary representation? |
VERY TRIANGULAR NUMBERS
The sequence of triangular numbers begins \(1, 3,6,10,15,\ldots\) and the \(N\)th triangular number is \(1+2+3+\cdots +N=\dfrac{N\left(N+1\right)}{2}\).
Let’s call a triangular number very triangular if it has a triangular number of \(1\)s in its binary representation
Very triangular numbers exist: \(1\), \(21\), \(28\), \(55\), and \(190\) are five examples. Are there more?
THEOREM: There are infinitely many very triangular numbers.
Proof: Look at the \(2^{n}+3\)th triangular number for \(n\geq 4\). It is
\(\dfrac{\left(2^{n}+3\right) \left(2^{n}+4\right)}{2}=\left(2^n+2+1\right)\left(2^{n-1}+2\right)\)
\(=2^{2n-1}+2^{n+1}+2^{n}+2^{n-1}+2^2+2^1\)
and has \(6\), a triangular number, of \(1\)s in its binary representation.
We can go further.
Each of the triangular numbers \(2^{2n-1}+2^{n+1}+2^{n}+2^{n-1}+2^2+2^1\) has, in binary, \(2n\) digits, six of which are \(1\)s leaving \(2n-6\) digits as zero.
And there are infinitely many even triangle numbers. Thus we can find infinitely many values \(n \geq 4\) with \(2n-6\) a triangular number. (For example, \(n=6\) gives \(2n-6=6\), and \(n=8\) gives \(2n-6=10\). )
| Challenge: There is a pattern to which values \(n\) give \(2n-6\) a triangular number. What is the pattern? |
This means that there are infinitely many very very triangular numbers, that is, infinitely many triangular numbers, which, when written in binary, have a triangular number of \(1\)s AND a triangular number of (non-leading) \(0\)s.
The smallest very very triangular number is \(276\), which is \(100010100\) in binary. Other examples include \(378\), \(435\), and \(2278\) (and this last one comes from placing \(n=6\) in our previous formula).
RESEARCH CORNER
As far as I am aware, no one has discussed the notion of very triangular and very very triangular numbers before. We’re now in (very) original research territory!
The sequence of very triangular numbers begins \(1\), \(21\), \(28\), \(55\), \(190\), \(ldots\). Is there a formula for the \(N\)th very triangular number? (The formula in this essay skips over most of these numbers.)
The sequence of very very triangular numbers begins \(1\), \(276\), \(378\), \(435\), \(2278\), \(2701\), \(ldots\). (Should we include \(1\)?) Is there a formula for the \(N\)th very very triangular number?
Explore very square and very very square numbers.
© 2016 James Tanton
