Month: 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.

Continue reading