05 November 2012

An unusual primality test

A few years ago, I came across The Computist Quiz, and one question in particular led to some interesting mathematics:

Amphibious Discursion

A predicate on positive integers:

boolean isToad(int n)
{
  return (
    (n == 2)
    || (n == frog(4, floor((n - 1) / 2), 1, 0) - 1));
}

is defined with the aid of the following helper method:

int frog(int q, int r, int s, int t)
{
  if (r < t)
    return 0;
  else if (r == t)
    return 1;
  else if (q == 0)
    return 0;
  else
    return (frog(q, r, s + 1, s + t)
            + frog(q - 1, r - t, 1, 0));
}

Which integers are toads? Describe what the frog method does. Can you explain why this code works?

© 2004 Marc LeBrun, Fixpoint Inc.
May be freely reproduced with this notice.

The peculiar recursive frog function counts sums of triangular numbers; doing so turns out to be closely related to primality. I spent a while digging into this, and got to the point of finding a proof which I could follow. Mostly to collect the pieces in one place, I have finally written it up:

An unusual primality test [pdf].

Epilogue

While putting this post up, I re-checked the sources, and found that there are answers available to the Computist Quiz. The answer for this question is:

Amphibious Discursion

Examining the output of the program quickly reveals that the “toads” are the primes. But then things get interesting. Many computists assume that the frog program must be doing some kind of division by iterated subtraction, much like in the “Parody Bit” question. However it isn’t, so part of the challenge of this exercise is to set aside these preconceptions and accurately describe what it actually is doing.

Despite the false similarity to division, the frog program is counting the ways a number n can be represented as the sum of four triangular numbers. Of course even after carefully figuring this out most people will still wonder what the heck that has to do with primes! A theorem (Legendre, 1752–1833) says that this count is equal to the sum of the divisors of 2n+1. But (unless you’re an analytic number theory geek) asking a computist to reverse engineer this alien technology is, of course, a completely unfair quiz question! Nonetheless we think it makes for an interesting diagnostic “problem solving” exercise, and a lesson in (to parody Wigner’s phrase)

“The effective unreasonableness of mathematics.”

© 2004–2005 Marc LeBrun, Fixpoint Inc.
May be freely reproduced with this notice

Comments are closed.