' Puzzlet #061
' Find all Fibonacci numbers less than
' 1 billion (10^9) which are also prime
' numbers
' By Dave Ellis.

declare InitFibArray()
declare UpdateFibArray()
declare IsPrime(p: int)
declare PrintResult(f: int)
def fibArray[4]: int

openconsole
print "Searching ...": print
InitFibArray()
PrintResult(FibArray[3])

do
    UpdateFibArray()
    if IsPrime(fibArray[3])
        PrintResult(fibArray[3])
    endif
until fibArray[3] > 999999999

print: print "No More!"
print: print "Press any key ... ",
do: until inkey$ <> ""
closeconsole
end

sub InitFibArray
' places the first 3 fibonacci numbers
' into cells 1 to 3 of fibArray
def it: int
fibArray[1] = 1
for it = 1 to 2
    fibArray[it + 1] = it
next it
return

sub UpdateFibArray
' puts cell 2 into cell 1, cell 3 into
' cell 2, and the next higher fib nr
' into cell 3 of fibArray
def it: int
for it = 1 to 2
    fibArray[it] = fibArray[it + 1]
next it
fibArray[3] = fibArray[1] + fibArray[2]
return

sub IsPrime(p)
' if p is prime, returns 1,
' otherwise returns 0
def flag, i, root: int
if p = 2 | p = 3
    flag = 1
else
    if p % 2 = 0 | p < 2
        flag = 0
    else
        root = sqrt(p)
        i = 3
        flag = 1       
        do
            if p % i = 0
                flag = 0
            else
                i = i + 2
            endif
        until flag = 0 | i > root
    endif
endif
return flag
   
sub PrintResult(f)
' pretty printer
print using ("##########", f)
return

PROGRAM NOTES

An array, FibArray[] is set up to hold a snapshot of the last three Fibonacci numbers generated. The program then commences by initialising these three cells using subroutine InitFibArray() with values 1, 1, and 2 in order.

We are searching for Fibonacci numbers which are also prime.  Well, the third cell in FibArray[] already holds a prime number - 2.  So, this can immediately be printed to the screen by sending that value as parameter to the subroutine PrintResult().

Now the main DO loop begins.  The first task is to update the contents of FibArray[].  Subroutine UpdateFibArray() takes care of this task. It dumps cell 2 into cell 1, cell 3 into cell 2, then adds cell 1 and cell 2 together to generate the next Fibonacci number in the series and saving it into cell 3.

This new value is sent as parameter to the function IsPrime(). The latter will either return 1 (TRUE) or 0 (FALSE).  If TRUE is returned we have another valid solution, and the value in FibArray[3] is sent as parameter to PrintResult() for output to the screen.

If the value in FibArray[] is less than 1 billion, the loop is executed again.  If it's a billion or more, the program ends.

When you run the code, it generates the screen shown inset.   As you can see, there are only ten solutions in total, of which most are relatively small. Clearly, many Fibonacci numbers are prime, but not many primes are Fibonacci numbers!

Searching ...                2                3                5              13              89            233           1597         28657       514229  433494437 No more! Press a key ...