Home > Analysis, Combinatorics, Geometry, Linear Algebra, puzzles, TeX/LaTeX > Where are the powers of two?

Where are the powers of two?

The following construction gives an interesting pairing map between the positive integers and the lattice of integer-valued points in the plane:

  • Place \boldsymbol{z}=1 at the origin.
  • For each level n \in \mathbb{N}, populate the 4n points of the plane on the square with vertices \big\{ (\pm n, 0), (0, \pm n) \big\}, starting from z=2(n^2-n+1) at the position (n,0), and going counter-clockwise.

    mypfschema

After pairing enough positive integers on the lattice, pay attention to the powers of two: they all seem to be located on the same two horizontal lines: y=0 and y=2.

mypfproofofconcept

Is this statement true?

Note for example, the sequence of numbers on the axes:

  • On the negative branch of the x—axis we have the sequence w_n= 2(n^2+n+1)+2n+2. For n \geq 1, subtracting two units to these numbers will give us the values on the negative branch of the line y=2: \big\{ 8, 18, 32, 50, 72, 98, 128, \dotsc \big\}.

    Note the expression of these values: 2(n^2+n+1)+2n = 2n^2+4n+2. Assume there is a power of two that belongs to this sequence, say 2^m for some m \in \mathbb{N}. If this is the case, a simple solution of the quadratic equation 2n^2+4n+2 = 2^m gives: n = -1 \pm 2^{(m-1)/2}.

    In particular, one of those two solutions is always a positive integer, provided the exponent m is odd: 2^{(m-1)/2}-1.

    This proves that any power of two (greater than 4) with odd exponent m does indeed belong in the line y=2.

    How would the reader calculate its precise position in the lattice?

  • On the positive branch of the x—axis we have by construction, the sequence e_n = 2(n^2+n+1). For n \geq 1, adding two units to these numbers will give us the values on the positive branch of the line y=2: \big\{8, 16, 28, 44, 64, 88, 116, \dotsc \big\}

    And here is the challenge:

    Is is true that all powers of two (greater than 4) with even exponent belong to the sequence with general term 2n^2+2n+4?

    If it is not the case:

    Is there a well-defined geometric structure (a set of lines, a parabola, etc) where all these powers of two belong?

    The reader has surely realized that all even numbers are located in the even horizontal lines: lines of the form y=2k for any value of k \in \mathbb{N}. If it is not the case that all powers of two greater than 4 belong in the line y=2 alone, then an answer to the previous question is obviously the set of even lines. But we want to do better than that:

    What is the minimal structure that contains them all?

Miscellaneous

Find below a \LaTeX code to represent arbitrarily large of paired integers on the grid following this scheme. It uses the tikz libraries:

\def\mypf#1{
	% Compute the maximum width of the box that contains all values from 0
	% to #1
	\pgfmathparse{floor(0.5*(sqrt(2*#1-3)-1))}
	\let\width\pgfmathresult
	% Generate a grid big enough to hold all values
	\draw (-1*\width cm - 1.75cm, -1*\width cm - 1.75cm) 
		grid[step=1cm, ultra thin, gray]
	 	(\width cm + 1.75cm, \width cm + 1.75cm);
	% Place all integers in the lattice
	\filldraw (0,0) circle (2pt) node[below right]{$1$};
	\foreach \n in {0,..., \width}
	{
		\foreach \k in {0,..., \n}
		{
			\pgfmathparse{\n+1-\k}
			\let\xa\pgfmathresult
			\let\yb\pgfmathresult
			\pgfmathparse{\k}
			\let\ya\pgfmathresult
			\let\xd\pgfmathresult
			\pgfmathparse{-1*\k}
			\let\xb\pgfmathresult
			\let\yc\pgfmathresult
			\pgfmathparse{\k-\n-1}
			\let\xc\pgfmathresult
			\let\yd\pgfmathresult
			\pgfmathparse{int(2*(\n^2+\n+1)+\k)}
			\let\za\pgfmathresult
			\pgfmathparse{int(2*(\n^2+\n+1)+\n+1+\k)}
			\let\zb\pgfmathresult
			\pgfmathparse{int(2*(\n^2+\n+1)+2*\n+2+\k)}
			\let\zc\pgfmathresult
			\pgfmathparse{int(2*(\n^2+\n+1)+3*\n+3+\k)}
			\let\zd\pgfmathresult
			\filldraw(\xa cm,\ya cm) circle (2pt) 
				node[below right]{$\za$};
			\filldraw(\xb cm,\yb cm) circle (2pt) 
				node[below right]{$\zb$};
			\filldraw(\xc cm,\yc cm) circle (2pt) 
				node[below right]{$\zc$};
			\filldraw(\xd cm,\yd cm) circle (2pt) 
				node[below right]{$\zd$};
		}
	}
}
Advertisements
  1. RV
    July 5, 2011 at 4:39 pm

    256 and 1024 do not “reside” on y=2.

    I doubt there is a finite degree polynomial curve “covering” all powers of two.

    Proving that no finite collection of lines “covers” all powers of two involves (or is equivalent) to showing that one cannot “approximate” the odd powers of 2 by perfect squares, within a given range (i.e. there should not exist an S>0 with the property that, for all M>0 there should exist a n_M>0 such that -S < 2^{2M+1} - n_M^2 < S).

    Interesting…

    • July 7, 2011 at 9:28 am

      I see what you are trying. Also equivalently, if there is a horizontal line y=2k where an even-power of two 2^{2m} belongs, then the quantity 2^{2m+1}+1-4k must be a perfect square—as a matter of fact, an odd perfect square.

      In that case, every odd-power of two 2^{2m+1} can be written as an odd perfect square (congruent with one modulo 4) plus an odd positive integer (congruent with 3 modulo 4).

      Fun…

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: