Home > Math News Archive Detail

<< Prev 3/24/2013 Next >>

Some Functions Are Amazing

Rather than give prime numbers all the attention, let me share something about composite numbers. Sir down, as this may be a shocker...at least it was for me.

Believe it or not: A simple formula, in closed form, can produce all of the composite numbers...and skips all the prime numbers! Again, the formula is a function of the natural numbers, with the range being the set of composite numbers.

First, create the auxiliary function H(n) = ceiling([SQRT(8n+1)-1]/2), where ceiling(x) means the first integer greater than or equal to x. For example, ceiling(2.7) = 3, ceiling (3.00001) = 4, and ceiling(3) = 3.

Now, define this unusual function C(n) of natural numbers n:

C(n) = (n+1) + (n+1.5)*H(n) - 0.5H3(n).
It is time for you to try some calculations using this function C(n)...and you should get the given output values:
  • C(1) = 4
  • C(2) = 6
  • C(3) = 9
  • C(4) = 8
  • etc.
Thus, the first four composite numbers have already been produced. Note that C(n) does not necessarily produce the composite numbers in their given order. In fact, repetitions may even occur for higher values of n.

Clever formula, but you perhaps wonder why it works...or even how one could prove that C(n)'s range is the set of composite numbers.

The proof is based on two "elementary" facts:

  • H(n) is the nth term of the sequence {1,2,2,3,3,3,4,4,4,4,...}, a sequence "intimately related" to two other sequences: {2,3,3,4,4,4,5,5,5,5,...} and {2,2,3,2,3,4,2,3,4,5,...}
  • When these last two sequences are multiplied term-by-term, the result is C(n) or the set of composite numbers
Wow...you need to play further with these two ideas before more understanding appears, let alone a "proof."

So, now if only we had a function that could generate all the prime numbers...hmmm!

Source: B. Ralston, "Elemental Complete Composite Number Generators." Fibonacci Quarterly. May 1985