Number Theory Example

When introducing a new programming language, it is a long-standing traditional to demonstrate it by generating prime numbers. (This tradition predates the appearance of text in software, and a newer tradition of generating "Hello, Word!", which Hava cannot do.) Prime numbers also provide an excuse to reference some jokes from this website.

Prime Numbers

A prime number (or a prime) is an integer that is divisible only by 1 and itself. By convention, the integer one is not considered to be prime. We shall use Hava to enumerate all prime numbers up to 100.

We proceed in three steps:

Determine whether one integer is divisible by another. To do so, we compare their fractional ratio to that same ratio rounded to the nearest whole number:
function isDivisible(n, k) = n/k==round(n/k);
For example, 11/5 is 2.2, but round(11/5) is 2, so 11 is not divisible by 5. This is designated a function because the calculation is simple enough - no significant execution time will be saved by retaining the result for future use. There is also a more subtle reason: It happens that each result will be needed only once!
Determine whether some candidate integer is prime. To do so, we attempt to divide it by every integer that might be a factor:
function isPrime(n) = first(k=2 to floor(sqrt(n)) | isDivisible(n,k)) {ERROR} != ERROR;
In principle, the candidate factors range from 2 to n-1, but we can stop at floor(sqrt(n)) because, if n is divisible by no number less than or equal to its square root, it certainly won't be divisible by anything else. Or, put differently, if it is divisible by some number k=k'>sqrt(n), then it is also divisible by n/k'<sqrt(n). Of these candidates, we only consider those that are divisible into n. And if we find one, we return ERROR, which causes isPrime to take the value false. On the other hand, if we find none, then first will evaluate to IGNORE, which causes isPrime to take the value true. And this is as it should be.
Check every integer from 2 to 1000, and retains those that are prime.
table PrimeNumbers = collect(n=2 to 1000 | isPrime(n)) {n};
The prefix table causes the elements of the list PrimeNumbers to appear on separate lines.

Click here to view this Hava program.

Prime Factorization

The prime factorization problem is to express a given integer as a product of prime numbers. For example, 12 = 2 × 2 × 3. The integer k is a prime factor of n if two conditions hold: it is prime, and it is a factor of n. However, it is not enough to determine whether k is a prime factor of n; we must also determine how many times it can be divided into n. Click here to view a Hava program that performs prime factorization (three different ways!).

Perfect Numbers

A perfect number is a positive integer that is the sum of its positive divisors (excluding the number itself).
Click here to view a Hava program that finds perfect numbers.

Fibonacci Numbers

The Fibonacci numbers are the following sequence of numbers:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

The first two Fibonacci numbers are given, and each remaining number is the sum of the previous two. In Hava, this can be expressed as:

F(n) = if (n>1) {F(n-2)+F(n-1)} else if (n==1) {1} else {0};

(By convention, the zero-th Fibonacci number is zero, but the first two are one.)

The n-th Finonacci number can also be interpreted as the number of sequences of 1s and 2s that sum to n-1. Here the order of the summands matters. For example, 1 + 2 and 2 + 1 are considered two different sums. As an exercise, let's use Hava to test whether these two definitions are equivalent (at least, for the first ten values).

It's easy to test whether a given sequence S of 1s and 2s sums to a given value:

function isSeqValid(S, n) = (seqSum(S) == n-1);
function seqSum(S) = sum(j in S) {j};

Let S(k) denote the list of all sequences of 1s and 2s of length k. In terms of S(k),

G(n) = sum(k = 0 to n-1, S in S(k)) {isSeqValid(S, n)};

It remains to generate each S(k). This can be done recursively by joining either a 1 or 2 to each element in S(k-1).

S(n) = 
  if (n>0) 
    {collect(S in S(n-1), s=1 to 2) {join(S, s)}} 
  else 
    {collect(())};

The final step is to check whether G(n) equals F(n).

Click here to view the program that compares these two ways to generate Fibonacci numbers.