[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

545.0. "<><><> Fibonacci Numbers <><><>" by THEBUS::KOSTAS (An investment in knowledge pays the best interest.) Sun Jul 27 1986 15:58

    Hello,

        This note will provide information related to the Fibonacci numbers.
    I will like to reserve then this note for problems related to Fibonacci
    numbers. If you are going to add more problems, please number them
    with the last problem of this entry plus one.
    

    Leonardo of Pisa, who wrote under the name of Fibonacci - a contraction 
    of filius Bonacci, that is, son of Bonacci. Fibonacci posed the following
    problem dealing with the number of offspring generated by a pair of rabbits
    conjured up in the imagination:

        "A man put one pair of rabbits in a certain place entirely
        surrounded by a wall. How many pairs or rabbits can be 
        produced from that pair in a year, if the nature of these 
        rabbits is such that every month each pair bears a new pair
        which from the second month on becomes productive?"

    Assuming that none of the rabbits dies, then a pair is born during the
    first month, so that there are two pairs present.
    When continued indefinitely, the sequence encountered in the rabbit 
    problem is:

        { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... }

    and is called the Fibonacci sequence and its terms the Fibonacci numbers.

    Let  U(n)  denote the  nth  Fibonacci number then the general rule
    of formulation should be:

        U(1) = U(2) = 1

        U(n) = U(n-1) + U(n-2)     for  n >=3




    Theorems related to Fibonacci numbers:

    Theorem 1:  For the Fibonacci sequence,  gcd( U(n), U(n+1) ) =1
                for every  n >= 1

    Theorem 2:  For  m, n >= 1
                U(mn) is divisible by U(m).

    Theorem 3:  The greatest common divisor of two Fibonacci numbers is 
                again a Fibonacci number, specifically,

                     gcd( U(m), U(n) ) = U(d), where  d = gcd(m, n)

                An example: 

                gcd(U(16),U(12)) = gcd(987,144) = 3 = U(4) = U(gcd(16,12))



    Problems:

       [1]  Show that the sum of the first  n  Fibonacci numbers with odd
            indices is given by the formula:

              U(1) + U(3) + U(5) + ... + U(2n-1) = U(2n)

            and that the sum of the first  n  Fibonacci numbers of even 
            indices is given by the formula:

              U(2) + U(4) + U(6) + ... + U(2n) = U(2n+1) - 1

       [2]  Let  a = 1/2 * (1 + sqrt(5)) and  b = 1/2 * (1 - sqrt(5)),
            so that  a  and  b  are both roots of the equation  
            x^2 = x + 1.
            Show by induction that the Binet formula

                            a^n - b^n
                    U(n) = -----------
                             sqrt(5)

            holds fo  n >= 1.

       [3]  In 1876, Lucas discovered the following formula for the 
            Fibonacci numbers in terms of the binomial coefficients:
            
            
                       n-1     n-2     n-3           n-j     n-j-1
               U(n) = (   ) + (   ) + (   ) + ... + (   ) + (     )
                        0       1       2            j-1       j
            
            where  j  is the largest integer less than or equal to  
            (n-1)/2.  
            Derive this result.
            
            

    Enjoy,

    Kostas G.

T.RTitleUserPersonal
Name
DateLines
545.1It's pretty well worked overMODEL::YARBROUGHMon Jul 28 1986 14:573
    There is an international Fibonacci Bulletin devoted to this topic.
    Stan used to make contributions to it. I don't know of any extant
    copies, though.
545.2MAPLE does this well.MODEL::YARBROUGHMon Jul 28 1986 16:434
    Fibonacci(n) is a built-in function in MAPLE. It will compute f(n)
    usually in less time than it takes to write it on the screen. N can be
    arbitrarily large. It requires that you type "readlib(fibonacci);"
    before using it.
545.3DiagonalsGALLO::JMUNZERMon Aug 04 1986 15:1759
		Proof by Induction of Problem 3 of 545.0

Build a pyramid of binomial coefficients:

		  1                         0
                                            0
	        1   1    	      	  1   1
                                          0   1
	      1   2   1         =       2   2   2
	                                0   1   2
	    1   3   3   1             3   3   3   3
	                              0   1   2   3
	  1   4   6   4   1         4   4   4   4   4
	                            0   1   2   3   4
	1   5  10  10   5   1     5   5   5   5   5   5
	                          0   1   2   3   4   5
and annotate it:
         			    A0
			          B0  C1
			        C0  D1  E2
		              D0  E1  F2  G3
		            E0  F1  G2  H3  I4
                          F0  G1  H2  I3  J4  K5

Then Problem 3 of 545.0 can be restated as:

	U(1) = sum of Aj = 1
	U(2) = sum of Bj = 1
	U(3) = sum of Cj = 1 + 1 = 2
	U(4) = sum of Dj = 1 + 2 = 3
	U(5) = sum of Ej = 1 + 3 + 1 = 5
	U(6) = sum of Fj = 1 + 4 + 3 = 9
	etc.

All over the pyramid, each number is the sum of the two numbers diagonally
above it:
		(letter, j) = (previous_previous_letter, j - 1)
			      + (previous_letter, j)

So:
	sum of (letter, j) = sum of (previous_previous_letter, j - 1)
			     + sum of (previous_letter, j)

(for example:  sum of Fj = sum of Dj + sum of Ej

	 	       		    ..
			          ..  ..
			        ..  D1  E2
		              D0  E1  F2  ..
		            E0  F1  ..  ..  ..  
                          F0  ..  ..  ..  ..  ..  )

[Each sum goes from j = 0 to j = floor ( (appropriate_letter - A) / 2), which
 turns out to be what was asked for.]

Then, by induction, the sums of Gj, Hj, Ij, ... continue to track the
Fibonacci numbers.

John
545.4solution to the first half of problem [1] in .0THEBUS::KOSTASWisdom is the child of experience.Wed Aug 06 1986 17:3570

Let see if we can solve the first problem in .0

Recall:

    >   [1]  Show that the sum of the first  n  Fibonacci numbers with odd
    >        indices is given by the formula:
    >
    >         U(1) + U(3) + U(5) + ... + U(2n-1) = U(2n)
    >
    >        and that the sum of the first  n  Fibonacci numbers of even 
    >        indices is given by the formula:
    >
    >         U(2) + U(4) + U(6) + ... + U(2n) = U(2n+1) - 1


    well the Fibonacci sequence is

        { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... }

    and 

        U(1) = U(2) = 1

        U(3) = U(4) - U(2) = 2

        U(5) = U(6) - U(4) = 3
                  .
                  .
                  .
        U(n) = U(n+1) - U(n-1)


    so to show that 

        U(1) + U(3) + U(5) + ... + U(2n-1) = U(2n)
 
    substitute  
                U(2)            for   U(1)   
                U(4)-U(5)       for   U(3)
                U(6)-U(4)       for   U(5)
                ... etc

    we get

       U(2) + (U(4)-U(2)) + (U(6)-U(4)) + ... + (U(2n)+U(2n-2)) = U(2n)

       and U(2) cancels with -U(2), ... etc.
 
    so 

       U(1) + U(3) + U(5) + ... + U(2n-1) = U(2n)


    I will let someone else show the second half of [1]
    i.e. 

    >  [1]b  
    >        and that the sum of the first  n  Fibonacci numbers of even 
    >        indices is given by the formula:
    >
    >         U(2) + U(4) + U(6) + ... + U(2n) = U(2n+1) - 1



    Enjoy,

    Kostas G.

545.5U(x+y)DRUMS::FEHSKENSWed Apr 27 1988 18:5477
    There hasn't been a whole lot of talk about Fibonacci numbers for
    a while, so I'll toss out this result that I literally stumbled
    upon (looking for something else) some time ago.  I don't know if
    this is common knowledge among Fibonaccians, but I've never seen
    it anywhere.  My apologies for using a slightly different
    representation of the sequence; starting at zero made things easier
    for me with respect to the other problem I was working.  By the
    way, the other problem had to do with musical applications - how
    many rhythmic patterns are there of a given length obeying a certain
    contraint.  I have also discovered the sequence plays a quite prominent
    role in the analysis of paradiddles, i.e., strings on the alphabet
    {1, 2} with the constraint that the same character may occur no
    more than twice in succession.
    
    If any of this seems naive, please bear with me, I am not a
    mathematician and have only been trained in traditional engineering
    mathematics.  I do, however, enjoy fooling around with mathematics.
     
    Let F(x) be the x'th Fibonacci number [F(x) = U(x+1) using the notation
    prevalent in this note]:
   
     F(0) = 0
   
     F(1) = 1
   
     F(i) = F(i-1) + F(i-2) for i > 1
   
    Note that you can define F(i) for i < 0 as F(i-1) = F(i+1) - F(i);
    the result is
   
     F(-i) = (-1)^(i-1) * F(i)


    Then
   
     F(x+y) = F(x-1)*F(y) + F(x)*F(y+1)

    Note that since x+y = y+x, this means that it's also true that

     F(x+y) = F(y-1)*F(x) + F(y)*F(x+1)

    The two possible forms are thus:
   
     F(x+y) = F(x-1)*F(y) + F(x)*F(y+1)
   
     F(x+y) = F(x+1)*F(y) + F(x)*F(y-1)
   
    It is straightforward to demonstrate that these two expressions are equal.

      
    Proof by induction:
   
     F(x+i) = F(x-1)*F(i) + F(x)*F(i+1)

    This is easily demonstrated to be true for i = 0 and 1:
   
     F(x+0) = F(x-1)*F(0) + F(x)*F(1) = F(x)
   
     F(x+1) = F(x-1)*F(1) + F(x)*F(2) = F(x-1) + F(x),
   
    since F(1) = 1 and F(2) = 1.
 
    Now demonstrate that it's also true for i+1.  This is easily done:

     F(x+(i+1)) = F((x+i)+1) = F((x+i)-1)*F(1) + F(x+i)*F(2)

    As noted above, F(1) = 1, F(2) = 1, so

     F(x+(i+1)) = F((x+i)+1) = F((x+i)-1) + F(x+i),
   
    which is true by definition (i.e., F(n+1) = F(n) + F(n-1).)
   

   
    len.
    
545.6Ho Hum?DRUMS::FEHSKENSThu Nov 10 1988 18:186
    I posted the previous reply about 6 months ago and there hasn't
    been any reaction.  Is this an obvious result known to all?
    How would I find out if this is old hat or something new?
    
    len.
    
545.7It's old hat. Sorry!AKQJ10::YARBROUGHI prefer PiThu Nov 10 1988 19:156
See Knuth, "The Art of Computer Programming", Vol. I, P. 80, formula (6).

(By the way, there is a misprint in the formula, in the 1st edition. 
'm+1' should be 'm-1'.) 

Lynn Yarbrough 
545.8CTCADM::ROTHIf you plant ice you'll harvest windFri Nov 11 1988 20:266
545.9I Didn't Think I Was Clever Enough...DRUMS::FEHSKENSMon Nov 14 1988 14:566
    Aha, thanks!  Should have just looked it up (wouldn't have expected
    to find it in Knuth though) rather than burn out all those neurons
    deriving it...
    
    len.
    
545.10Error? What error?AKQJ10::YARBROUGHI prefer PiMon Nov 14 1988 15:449
545.11BEING::EDPAlways mount a scratch monkey.Tue Oct 29 1991 11:4624
Article: 22027
From: clong@remus.rutgers.edu (Chris Long)
Newsgroups: rec.puzzles,sci.math
Subject: Molly's Rabbit Farm
Message-ID: <Oct.26.03.03.47.1991.9621@remus.rutgers.edu>
Date: 26 Oct 91 07:03:47 GMT
Organization: Rutgers Univ., New Brunswick, N.J.
 
 
Molly, Waldo's niece, wants to become a millionaire.  Not an
easy thing to do, but she has a plan - she's going to raise and
sell rabbits.  Not just any rabbits, but Fibonacci rabbits.  These
are very special rabbits!  They are immortal, they mature in only
one day, and mature Fibonacci rabbits produce (asexually) exactly
one offspring per day.
 
Assuming she has a buyer who will pay her $1 per rabbit, but only once,
what is the minimum number of rabbits she would need to have initially
in order to make a million dollars exactly?
-- 
Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ  08901  (908) 846-5569
 
"The proofs are so obvious that they can be left to the reader."
Lars V. Ahlfors, _Complex Analysis_
545.12Enough *&&^$^%$#$ rabbits. thanks!CIVAGE::LYNNLynn Yarbrough @WNP DTN 427-5663Tue Oct 29 1991 15:469
>...			They are immortal, they mature in only
>one day, and mature Fibonacci rabbits produce (asexually) exactly
>one offspring per day.

If I interpret this correctly, if we start with 1 rabbit we will have 1, 2,
4, 8, ... 2^n rabbits after n days. To avoid fractional rabbits, we can
only deal with as many reproductions are there are powers of 2 in
1,000,000: 6. So we have to start with 5^6 = 15625 to get there. The total
for each day is 15625, 31250, 62500, 125000, 250000, 500000, 1000000. 
545.13They are FIBONACCI rabbits!UNTADH::TOWERSWed Oct 30 1991 09:4616
    .12 is clearly wrong. The author misses the point of a Fibonacci rabbit
    taking one day to mature. The sums go like this -
    
    Day  Baby rabbits  Mature rabbits  Total
    ---  ------------  --------------  -----
    
    1         1               0          1
    2         0               1          1
    3         1               1          2
    4         1               2          3
    5         2               3          5
    6         3               5          8
    
    etc. Hence the name "Fibonacci" rabbit.
    
    Brian
545.14Either way, whateverCIVAGE::LYNNLynn Yarbrough @WNP DTN 427-5663Wed Oct 30 1991 13:1218
>...			They are immortal, they mature in only
>one day, and mature Fibonacci rabbits produce (asexually) exactly
>one offspring per day.

It's not all that clear. If we start with 1 rabbit, it has another on the 
first day. On the second day *both* are mature and have another pair. On 
the 3rd day all 4 are mature and have 8 ...

Anyhow, let's assume that the growth rate is indeed Fibonaccian. The ratio 
of terms in a F-series is (1+5^.5)/2, so on day n-1 we would have 1000000
* .6180339 = 618034 and on day n-2, 381966, ... Continuing to work 
backwards, we arrive at 144 and 298 as the lowest positive increasing
numbers in the sequence. So we must start with 154 immature bunnies and 144
mature ones that reproduce on the first day, and everybody contributing as 
they mature on later days. The complete sequence is 

(154, 144)= 298, 442, 740, 1182, 1922, 3104, 5026, 8130, 13156, 21286, 34442,
55728, 90170, 145898, 236068, 381966, 618034, 1000000.
545.15ELIS::GARSONV+F = E+2Mon Nov 04 1991 08:3814
    
    Silly me...I interpreted the question in yet a third way viz. that our
    rabbit raiser starts off with only young ones. Whereas the answer to
    the question is then very easy, it leads to some interesting side
    problems if one considers generalising 1000000 to some other target. (BTW
    I haven't actually solved any of these other problems.)
    
re .14
    
>The ratio of terms in a F-series is (1+5^.5)/2
    
    This is the asymptotic ratio of consecutive terms of the sequence.
    
    Can you give some justification for your procedure?
545.16No rigor, just figgerCIVAGE::LYNNLynn Yarbrough @WNP DTN 427-5663Mon Nov 04 1991 13:1715
>    Can you give some justification for your procedure?

Hmm. Well, actually I did a bit of inspired guessing. I assumed 1000000 is 
large enough so that the actual ratio and the asymptotic ratio were close 
enough for gov't work, and thus that the previous head count was 1000000/
((1+5^.5)/2) ~= 618034. I worked backward from that figure to get the
results in .-2, then checked the possibilities 618033 and 618035, and found
that they indeed are worse (i.e. larger initial headcount). I then asssumed
that numbers still farther from 618034 would be still worse, and didn't
check them. 

The last three positive terms in the sequence, 298, 144, 154, are followed 
by -10. After considering how these numbers might be used to describe the 
initial state, I decided that 298 rabbits, 144 adults and 154 juveniles,
made sense but that no smaller combination did.
545.17ELIS::GARSONV+F = E+2Tue Nov 05 1991 08:3513
    re .the original question (yet another misinterpretation)
    
    I make the answer 5 (babies).
    
    The largest Fibonacci number not greater than our target population of
    1000000 is 832040. This latter amount can be generated from just one
    baby. Subtracting this leaves a remainder of 167960. Repeating the
    process a few more times gives 55 which is a Fibonacci number. Thus by
    the timely addition of single babies it can be shown that the rabbit
    raiser needs only 5 babies to make her million.
    
    (Yes, I realise the original question implied that the initial rabbits
     were purchased all at the same time.)
545.18Divisibility propertiesBALZAC::QUENIVETMargins are often too small.Thu Nov 24 1994 10:10203
545.19Factorizing Fibonacci numbersBALZAC::QUENIVETMargins are often too small.Thu Nov 24 1994 10:11209
This is the list of a program for factorizing Fibonacci numbers. This program
executes on an alpha axp OSF/1 system.

To compile:

# cc fib.c -o fib
# fib 93

Note: f_93 is the largest Fibonacci which fits in our alpha chip 64 bits 
register.

I apologize for the poor comments: this is only a hobbyist program.
But when I write a program in a professional purpose, I usually try to 
self document it with as many comments as possible. 

There exist perfect numbers, but not perfect programmers...



#include	<stdio.h>
main (argc, argv)
int	argc;
char	*argv[];
{
unsigned long int	f0, f1, f2, i, n;	/* These are 64 bits alpha */
						/* axp integers            */

if(argc < 2) exit(0);		
n = atoi(argv[1]);	/* Tell how many numbers you want in command line */
f0 = 0;
f1 = 1;
printf("f0 = 0\nf1 = 1\n");
for(i = 2; i <= n; i++)
{
    printf("f%d = %lu", i, f2 = f1 + f0); 
    if(f2 >1)
	{
	    printf(" = ");
	    dfp(f2,i);		/* Call the factorization routine */
	}
    printf("\n");
f0 = f1;
f1 = f2;
}

}

dfp(n,x)		/* Factorise the number n, which is the x-th fibo*/
unsigned long int n,x;
{
unsigned long int	d,q,r,a;

if(testp(x))		/* checks whether the rank is prime */
   {
	d = 2 * x - 1;
	a = 2;
   }
else
   {
    d=2;
    a=0;
   }
while( n > 1)
{
q = n/d;
if(q < d)
   { 
	printf("%lu", n); 	/* found last divisor, and it is prime */
	return;
   }
r=n%d;
if(r==0)
    {
	printf("%lu ", d);	/* found a divisor */
	fflush(stdout);
	n = q ;
    }
else
   {
	if(a==0)		/* The rank is not prime, so we */
				/* clumsily try to divide the number by */
				/* all integers less than its sqrt */
    	    d++;
	else			/* The rank is prime, so we try to divide */
				/* the number only by the numbers in the */
				/* form k*x-1 or k*x+1 - see note .-1,theorem 5*/
            {
	      d += a;
	      a = 2*x - a;
	    }
   }

}

}

testp(x)			/* Checks whether x is an (odd) prime */
unsigned long int x;
{
int d;
if(x <= 2) return 0;		/* x is not odd */

for(d=2;;d++)
{
if(x/d < d) return 1;		/* x is prime */
if(x%d == 0) return 0;		/* x is not prime */
}
}


Here is the output of the program (took about 30 seconds of computing time 
on a DEC3000)

f0 = 0
f1 = 1
f2 = 1
f3 = 2 = 2
f4 = 3 = 3
f5 = 5 = 5
f6 = 8 = 2 2 2
f7 = 13 = 13
f8 = 21 = 3 7
f9 = 34 = 2 17
f10 = 55 = 5 11
f11 = 89 = 89
f12 = 144 = 2 2 2 2 3 3
f13 = 233 = 233
f14 = 377 = 13 29
f15 = 610 = 2 5 61
f16 = 987 = 3 7 47
f17 = 1597 = 1597
f18 = 2584 = 2 2 2 17 19
f19 = 4181 = 37 113
f20 = 6765 = 3 5 11 41
f21 = 10946 = 2 13 421
f22 = 17711 = 89 199
f23 = 28657 = 28657
f24 = 46368 = 2 2 2 2 2 3 3 7 23
f25 = 75025 = 5 5 3001
f26 = 121393 = 233 521
f27 = 196418 = 2 17 53 109
f28 = 317811 = 3 13 29 281
f29 = 514229 = 514229
f30 = 832040 = 2 2 2 5 11 31 61
f31 = 1346269 = 557 2417
f32 = 2178309 = 3 7 47 2207
f33 = 3524578 = 2 89 19801
f34 = 5702887 = 1597 3571
f35 = 9227465 = 5 13 141961
f36 = 14930352 = 2 2 2 2 3 3 3 17 19 107
f37 = 24157817 = 73 149 2221
f38 = 39088169 = 37 113 9349
f39 = 63245986 = 2 233 135721
f40 = 102334155 = 3 5 7 11 41 2161
f41 = 165580141 = 2789 59369
f42 = 267914296 = 2 2 2 13 29 211 421
f43 = 433494437 = 433494437
f44 = 701408733 = 3 43 89 199 307
f45 = 1134903170 = 2 5 17 61 109441
f46 = 1836311903 = 139 461 28657
f47 = 2971215073 = 2971215073
f48 = 4807526976 = 2 2 2 2 2 2 3 3 7 23 47 1103
f49 = 7778742049 = 13 97 6168709
f50 = 12586269025 = 5 5 11 101 151 3001
f51 = 20365011074 = 2 1597 6376021
f52 = 32951280099 = 3 233 521 90481
f53 = 53316291173 = 953 55945741
f54 = 86267571272 = 2 2 2 17 19 53 109 5779
f55 = 139583862445 = 5 89 661 474541
f56 = 225851433717 = 3 7 7 13 29 281 14503
f57 = 365435296162 = 2 37 113 797 54833
f58 = 591286729879 = 59 19489 514229
f59 = 956722026041 = 353 2710260697
f60 = 1548008755920 = 2 2 2 2 3 3 5 11 31 41 61 2521
f61 = 2504730781961 = 4513 555003497
f62 = 4052739537881 = 557 2417 3010349
f63 = 6557470319842 = 2 13 17 421 35239681
f64 = 10610209857723 = 3 7 47 1087 2207 4481
f65 = 17167680177565 = 5 233 14736206161
f66 = 27777890035288 = 2 2 2 89 199 9901 19801
f67 = 44945570212853 = 269 116849 1429913
f68 = 72723460248141 = 3 67 1597 3571 63443
f69 = 117669030460994 = 2 137 829 18077 28657
f70 = 190392490709135 = 5 11 13 29 71 911 141961
f71 = 308061521170129 = 6673 46165371073
f72 = 498454011879264 = 2 2 2 2 2 3 3 3 7 17 19 23 107 103681
f73 = 806515533049393 = 9375829 86020717
f74 = 1304969544928657 = 73 149 2221 54018521
f75 = 2111485077978050 = 2 5 5 61 3001 230686501
f76 = 3416454622906707 = 3 37 113 9349 29134601
f77 = 5527939700884757 = 13 89 988681 4832521
f78 = 8944394323791464 = 2 2 2 79 233 521 859 135721
f79 = 14472334024676221 = 157 92180471494753
f80 = 23416728348467685 = 3 5 7 11 41 47 1601 2161 3041
f81 = 37889062373143906 = 2 17 53 109 2269 4373 19441
f82 = 61305790721611591 = 2789 59369 370248451
f83 = 99194853094755497 = 99194853094755497
f84 = 160500643816367088 = 2 2 2 2 3 3 13 29 83 211 281 421 1427
f85 = 259695496911122585 = 5 1597 9521 3415914041
f86 = 420196140727489673 = 6709 144481 433494437
f87 = 679891637638612258 = 2 173 514229 3821263937
f88 = 1100087778366101931 = 3 7 43 89 199 263 307 881 967
f89 = 1779979416004714189 = 1069 1665088321800481
f90 = 2880067194370816120 = 2 2 2 5 11 17 19 31 61 181 541 109441
f91 = 4660046610375530309 = 13 13 233 741469 159607993
f92 = 7540113804746346429 = 3 139 461 4969 28657 275449
f93 = 12200160415121876738 = 2 557 2417 4531100550901

    
545.20Last digit of a Fibonacci numberBALZAC::QUENIVETMargins are often too small.Thu Nov 24 1994 10:1257
545.21AUSSIE::GARSONachtentachtig kacheltjesThu Nov 24 1994 19:5698
    re .19
    
    For those of us who still swear by VMS here's the same program editted
    to compile on Alpha VMS. (Took 40 CPU seconds on my DEC 4610.)
    
#include <stdio.h>
#include <stdlib.h>
#include <ints.h>

testp(x)			/* Checks whether x is an (odd) prime */
uint64 x;
{
int d;
if(x <= 2) return 0;		/* x is not odd */

for(d=2;;d++)
{
if(x/d < d) return 1;		/* x is prime */
if(x%d == 0) return 0;		/* x is not prime */
}
}

dfp(n,x)		/* Factorise the number n, which is the x-th fibo*/
uint64 n,x;
{
uint64	d,q,r,a;

if(testp(x))		/* checks whether the rank is prime */
   {
	d = 2 * x - 1;
	a = 2;
   }
else
   {
    d=2;
    a=0;
   }
while( n > 1)
{
q = n/d;
if(q < d)
   { 
	printf("%Lu", n); 	/* found last divisor, and it is prime */
	return;
   }
r=n%d;
if(r==0)
    {
	printf("%Lu ", d);	/* found a divisor */
	fflush(stdout);
	n = q ;
    }
else
   {
	if(a==0)		/* The rank is not prime, so we */
				/* clumsily try to divide the number by */
				/* all integers less than its sqrt */
    	    d++;
	else			/* The rank is prime, so we try to divide */
				/* the number only by the numbers in the */
				/* form k*x-1 or k*x+1 - see note .-1,theorem 5*/
            {
	      d += a;
	      a = 2*x - a;
	    }
   }

}

}


main (argc, argv)
int	argc;
char	*argv[];
{
uint64 f0, f1, f2, i, n;	/* These are 64 bits alpha */
						/* axp integers            */

if(argc < 2) exit(0);		
n = atoi(argv[1]);	/* Tell how many numbers you want in command line */
f0 = 0;
f1 = 1;
printf("f0 = 0\nf1 = 1\n");
for(i = 2; i <= n; i++)
{
    printf("f%d = %Lu", i, f2 = f1 + f0); 
    if(f2 >1)
	{
	    printf(" = ");
	    dfp(f2,i);		/* Call the factorization routine */
	}
    printf("\n");
f0 = f1;
f1 = f2;
}

}
545.22CSC32::D_DERAMODan D'Eramo, Customer Support CenterMon Nov 28 1994 15:098
        re .18
        
        The proofs of these are very similar to a proof of one
        direction of the Lucas-Lehmer test for primality of Mersenne
        numbers (see note 2.5).  There you extend F_p with sqrt(3) if
        q is an odd prime and p = 2^q - 1 is prime.
        
        Dan
545.23Prime Fibonacci numbers ?BALZAC::QUENIVETMargins are often too small.Tue Nov 29 1994 07:0622
545.24CSC32::D_DERAMODan D'Eramo, Customer Support CenterTue Nov 29 1994 14:4335
        Just like the Fibonacci numbers come from a recurrence, you
        can also define the recurrence
        
        	A(0) = 2
        	A(1) = 4
        	A(n+2) = 4A(n+1) - A(n)			n = 0,1,2,...
        
        Solving this yields
        
        	A(n) = (2 + sqrt(3))^n + (2 - sqrt(3))^n
        
        and a minor manipulation shows that
        
        	A(2n) = (A(n))^2 - 2
        
        The Lucas-Lehmer test uses the sequence
        
        	LL(0) = 4
        	LL(n+1) = (L(n)^2 - 2)   (in real life, take this mod 2^q - 1)
        
        and can be seen to be really computing LL(n) = A(2^n).  For
        odd primes q, N = 2^q - 1 is prime iff L(q-2) = A(2^(q-2))
        = A((N+1)/4) is 0 modulo N.
        
        You can compute the n-th element of any linear recurrence in a
        number of "steps" proportional to log(n), just as the above
        computes A(2^k) by taking the steps A(1), A(2), A(4), A(8), ....
        But where n is not a power of 2 you have a lot more overhead
        than when n is a power of 2.  And computing residues modulo 2^q - 1
        is a lot easier on a binary machine than computing residues modulo
        an arbitrary number.  Both of these should combine to make the
        Lucas-Lehmer test for a k-bit Mersenne number faster than a
        similarly motivated test for a k-bit Fibonacci number.
        
        Dan