2^2x+1 problem

From AJS.COM

The 2^2x+1 problem is my name for this rather interesting math puzzle that someone got from a math newsletter that's apparently related to some test that someone gives. At work, we have a Math Lunch every week and sometimes we discuss these problems. This problem took the rough form of:

Find all integer pairs (x,y) such that:

2^2x+1 + 2^x + 1 = y²

NEW! this has now been solved.

First steps

We immediately found two solutions:

(0,2) and (4,23)

but then we were stumped. We were not able to find more, nor were we immediately able to demonstrate why these would be the only results.

My thoughts

I turned up two pieces of information. First, using the Perl code in appendix A, I demonstrated that there are no other values of x lower than 4600 that have a corresponding integer y:

A gnuplot of the formula from the problem and a simplification that converges rapidly on the same result.

Second, I demonstrated with gnuplot (image right) that y as a function of x converged on:

which struck a nerve because it's very easy to see that the above can never generate an integer result from an integer value of x. This is because the above can be simplified to:

and of course, being a known irrational number, when multiplied by any integer is still going to be irrational.

Sadly, that's as far as I've gotten, though, and I still have no proof that x = 0 and x = 4 are the only valid solutions.

Solution

A co-worker solved this. I won't repeat his whole proof here because he's not given me permission to do so, but he simplified the formula first to:

where

w = x − 2

and

y = 2h + 1

This, he then reduces and chases down to all of its possible constituents, proving that the only valid integer values of x and y are (0,+/-2) and (4,+/-23).

Appendix A: Perl code

This code finds (x,y) pairs which satisfy the formula:

#!/usr/bin/perl

use Math::BigInt;
use Time::HiRes qw(time);

$|=1;

my $start = time();
my $since = $start;
my $one = Math::BigInt->new(1);
my $two = Math::BigInt->new(2);
my $four = Math::BigInt->new(4);
my $freq = 10;

my($lasty,$iter);

my $r = $one; # The first step of 2^x. At each subsequent step, just *=2
my $n = $two; # The first step of 2^(2x+1). At each subsequent step, just *=4

for(my $x=0;;$x++) {
    # This is all of the real work:
    my $result = $n + $r + $one;
    my $y = sqrt($result);
    if ($y*$y == $result) {
       print "(x,y) = ($x,$y)\n";
       print "(x,y) = ($x,-$y)\n";
    }

    # Print stats as we go
    if ($x && $x%$freq==0) {
       my $now = time();
       my $spent = $now-$start || 1;
       printf "** x=%d averaging %f/s with the last %d taking %.1fs\n",$x,$x/$spent,$freq,$now-$since;
       $since = $now;
    }

    # Increment the terms
    $r*=$two;
    $n*=$four;
}

Appendix B: Gnuplot code

The following gnuplot input will generate a chart showing the the values of:

set grid;
set xlabel "X";
set ylabel "Y";
set logscale y 2;
set label "(4,23)" at 4,23 point lt 1 pt 2 ps 3 offset 1,-1;
set label "(0,2)" at 0,2 point lt 1 pt 2 ps 3 offset 1,-1;
plot [x=-5:20] [:] sqrt(1+2**x+2**(2*x+1)), 2**((2*x+1)/2)+1;