## 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.