False Positives on an Integer Lattice
Python, 27,797,402
Just to set the bar a little higher...
from sys import argv
verbose = len(argv) &gt; 1
found = 0
for x in xrange(67108864, 94906266):
    found += 1
    if verbose:
        print &quot;(%d, 0) (%d, 1)&quot; % (x, x)
print found

It's easy to verify that for all 67,108,864 &lt;= x &lt;= 94,906,265 = floor(sqrt(253)) the pairs (x, 0) and (x, 1) are false positives.
Why it works: 67,108,864 = 226. Therfore, all numbers x in the above range are of the form 226 + x' for some 0 &lt;= x' &lt; 226.
For all positive e, (x + e)2 = x2 + 2xe + e2 = x2 + 227e + 2x'e + e2.
If we want to have  (x + e)2 = x2 + 1 we need at least 227e &lt;= 1, that is, e &lt;= 2-27
However, since the mantissa of double-precision floating point numbers is 52-bit wide, the smallest e such that x + e &gt; x is e = 226 - 52 = 2-26.
In other words, the smallest representable number greater than x is x + 2-26 while the result of sqrt(x2 + 1) is at most x + 2-27.
Since the default IEEE-754 rounding mode is round-to-nearest; ties-to-even, it will always round to x and never to x + 2-26 (where the tie-break is really only relevant for x = 67,108,864, if at all. Any larger number will round to x regardless).

C++, 75,000,000+
Recall that 32 + 42 = 52.
What this means is that the point (4, 3) lies on the circle of radius 5 centered around the origin.
Actually, for all integers n, (4n, 3n) lies on such circle of radius 5n.
For large enough n (namely, such that 5n &gt;= 226), we already know a false-positive for all points on this circle: (5n, 1).
Great! That's another 27,797,402 / 5 free false-positive pairs right there!
But why stop here? (3, 4, 5) is not the only such triplet.
This program looks for all positive integer triplets (a, b, c) such that a2 + b2 = c2, and counts false-positives in this fashion.
It gets to 70,000,000 false-positives pretty fast but then slows down considerably as the numbers grow.
Compile with g++ flspos.cpp -oflspos -std=c++11 -msse2 -mfpmath=sse -O3.
To verify the results, add -DVERIFY (this will be notably slower.)
Run with flspos. Any command-line argument for verbose mode.
#include &lt;cstdio&gt;
#include &lt;cmath&gt;
#include &lt;cfloat&gt;

using namespace std;

/* Make sure we actually work with 64-bit precision */
#if defined(VERIFY) &amp;&amp; FLT_EVAL_METHOD != 0 &amp;&amp; FLT_EVAL_METHOD != 1
#   error &quot;invalid FLT_EVAL_METHOD (did you forget `-msse2 -mfpmath=sse'?)&quot;
#endif

template &lt;typename T&gt; inline long long sqr(T x) { return 1ll * x * x; }
template &lt;typename T&gt;
T gcd(T a, T b) { while (b) { T t = a; a = b; b = t % b; } return a; }

int main(int argc, const char* argv[]) {
    const bool verbose = argc &gt; 1;

    const int min = 1 &lt;&lt; 26;
    const int max = sqrt(1ll &lt;&lt; 53);

    int found = 0;
    auto add = [=, &amp;found] (int x1, int y1, int x2, int y2) {
#ifdef VERIFY
        auto n1 = sqr(x1) + sqr(y1), n2 = sqr(x2) + sqr(y2);
        if (n1 == n2 || sqrt(n1) != sqrt(n2)) {
            fprintf(stderr, &quot;Wrong false-positive: (%d, %d) (%d, %d)\n&quot;,
                    x1, y1, x2, y2);
            return;
        }
#endif
        if (verbose) printf(&quot;(%d, %d) (%d, %d)\n&quot;, x1, x2, y1, y2);
        ++found;
    };

    for (int x = min; x &lt;= max; ++x) add(x, 0,    x, 1);

    for (int a = 1; a &lt; max; ++a) {
        auto a2b2 = sqr(a) + 1;
        for (int b = 1; b &lt;= a; a2b2 += 2 * b + 1, ++b) {
            int c = sqrt(a2b2);
            if (a2b2 == sqr(c) &amp;&amp; gcd(a, b) == 1) {
                int max_c = max / c;
                for (int n = (min + c - 1) / c; n &lt;= max_c; ++n)
                    add(n * a, n * b,    n * c, 1);
            }
        }

        if (a % 512 == 0) printf(&quot;%d\n&quot;, found), fflush(stdout);
    }

    printf(&quot;%d\n&quot;, found);
}