From:_________________HJSmith@ix.netcom.com (Harry J. Smith)
To:_______________MWE1@psu.edu (Dr. Michael W. Ecker)
Subject:__________Lucas Sequences, was (Fwd) Re: Checked out your web site
Date sent:________Sun, 21 Jul 1996 14:14:47 -0800
Mike,
Here is an interesting note, I think, on Lucas sequences.
Harry
------- Forwarded Message Follows -------
From:__________HJSmith@ix.netcom.com (Harry J. Smith)
To:____________DaleKoepp@aol.com
Subject:_______Re: Checked out your web site
Date:__________Sat, 20 Jul 1996 07:48:49 -0800
> From:__________DaleKoepp@aol.com
> Date:__________Sat, 20 Jul 1996 00:06:36 -0400
> To:____________HJSmith@ix.netcom.com
> Subject:_______Checked out your web site
>
> Harry,
>
> I checked out your new web site. There's a lot of interesting stuff
> there.
> I'll have to explore it more.
I threw it together kind of fast after I found out that Netcom allowed it. I hope it is not too disorganized.
> I noticed one of your topics was Fibbinacci numbers. I have for a
> long time been interested in a similar number sequence. That is, if
> the Fibbinacci sequence is F(i+1) = F(i) + F(i-1), then my sequence
> is K(i+1) = 2*K(i) + K(i-1). If the first two numbers are 0 and 1,
> then the sequence goes: 0, 1, 2, 5, 12, 29, 70, 169, etc. I was
> wondering if any research has been done on this sequence in
> particular.
Yes, Fibonacci Numbers:
____________n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
__________F(n) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... It
is important that F(0) be defined = 0 for some of the properties like:
If F(n) is prime then n is prime.
Your sequence is one of the two Pell sequences. 0, 1, 2, 5, ... and 2, 2, 6, 14, ... The closed form for your sequence is:
K(n) = ((1+Sqrt(2))^n - (1-Sqrt(2))^n) / (2*Sqrt(2)).
There also is a companion sequence to the Fibonacci numbers: 2, 1, 3, 4, ...
These are all Lucas sequences:
U(0) = 0, U(1) = 1, U(n) = P * U(n-1) - Q * U(n-2)
V(0) = 2, V(1) = P, V(n) = P * V(n-1) - Q * V(n-2)
The closed forms are:
U(n) = (a^n - b^n) / (a - b)
V(n) = a^n + b^n.
where a and b are the roots of the polynomial x^2 - P x + Q.
For Fibonacci numbers, P = 1, Q = -1. For Pell numbers P = 2, Q = -1.
> The interesting thing about this sequence is its relationship to
> Pythagorean triples, i.e. (a,b,c) such that a**2 + b**2 = c**2. More
> specifically, it has a relationship with the special Pythagorean
> triples such that (a - b) = 1 or (b - a) = 1. When I was in college
> (way back in the early 70's) I wrote a paper that generated such
> triples, and proved that it generated all such triples. (There are
> an infinite number of these, but the numbers grow pretty fast.)
> These are: (1, 0, 1) (3, 4, 5) (21, 20, 29) (119, 120, 169) (697,
> 696, 985) etc.
>
> The interesting thing is that every other element in my
> Fibbinacci-similar series is the c value in this sequence of special
> Pythagorean triples. I think I could come up with a proof if
> anybody was interested.
>
> By the way, I am being moved into the SI division of PRC. I am
> pretty optimistic that things will be better under PRC than they
> were under LCS.
> For the most part, people are happy about the change here in
> Colorado
> Springs.
>
> Which division of PRC will you be in?
SI division also.
> Until later....
>
> Dale
I will attach two letters that I wrote about Pythagorean Triples.
Harry
Attachments:
d:\letters.my\mikecker\ptriples.let
d:\letters.my\mikecker\ptriplep.let
--------
91/11/11
To: Dr. Michael W. Ecker
REC, 909 Violet Terrace, Clarks Summit, PA 18411
From: Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070
Enclosure: MS-DOS disk (PTriples)
Dear Mike,
Your article "A New Way to Generate Pythagorean Triples?" in REC Sep/Oct/Nov 1991 inspired me to investigate these triples. In running your program I noticed that if you start with two integers that were not the first two integers of a P-triple (Pythagorean triple), all even powers, but only the even powers, would form a P- triple.
I took the liberty to make a modified version of your program that I called PTrips1.Bas. This modification is based on the fact that the square of any complex integer a + bi, a and b both integers, forms a P-triple. If we do not want zeros in our triples, we must take a and b non-zero and |a| not equal to |b|.
Take any complex integer (a, b) and square it. (x, y) = (a, b)^2 = (a^2 - b^2, 2ab). r = |(x, y)| = a^2 + b^2. Since x, y, and r are all integer, (|x|, |y|, r) is a P-triple.
Given any two P-triples, (a, b, c) and (x, y, r), the product of their complex integers (a + bi)(x + yi) is (ax-by, ay+bx), with modulus cr. The product forms a new P-triple (|ax-by|, |ay+bx|, cr).
The program PTrips1.Bas forces the input to be two non-zero integers that do not have the same absolute value. This input is considered to be a complex integer and is squared to form z and the first P-triple. Consecutive powers of z are then computed to generate more P-triples.
This program was interesting but a lot of good P-triples were being missed and some non-primitive ones were being generated. The classical result is, if we regard (a, b, c) and (b, a, c) as the same triple, all primitive Pythagorean triples are generated by the equations
a = u^2 - v^2, b = 2uv, c = u^2 + v^2,
where u > v are relatively prime integers of opposite (odd/even) parity. Further, all such triples are primitive P-triples. This is fine, but my intention was to write a program that would generate "all" primitive Pythagorean triples. "All" in the sense that, if given enough time and memory, and if numbers were kept to a high enough precision, any given primitive P-triple would be generated.
My program PTriples.Pas does just that...
A Pythagorean triple is a triple of positive integers (a, b, c) satisfying a^2 + b^2 = c^2. When the integers have greatest common divisor 1, we call the triple primitive.
Given a primitive Pythagorean triple (a, b, c), three new primitive Pythagorean triple can be generated by the transforms:
(d, e, f) = (a, b, c) * U
(g, h, i) = (a, b, c) * A
(j, k, l) = (a, b, c) * D
where U, A, and D are the three matrices:
-- -- -- -- -- --
| 1 2 2 | | 1 2 2 | | -1 -2 -2 |
U = | -2 -1 -2 | A = | 2 1 2 | D = | 2 1 2 |
| 2 2 3 | | 2 2 3 | | 2 2 3 |
-- --, -- --, -- --.
It follows then that every primitive Pythagorean triple is in the
infinite array:
( 7, 24, 25)
( 5, 12, 13) ( 55, 48, 73) ...
( 45, 28, 53)
( 39, 80, 89)
(3, 4, 5) (21, 20, 29) (119, 120, 169) ...
( 77, 36, 85)
( 33, 56, 65)
(15, 8, 17) ( 65, 72, 97) ...
( 35, 12, 37)
My program generates each column of this array one after the other starting at the first one on the left.
After finishing the program PTriples.Pas, I converted it from Pascal to Basic. The converted program is called PTrips2.Bas and was written using MS-DOS QBasic that comes with MS-DOS 5.0.
Sincerely,
Harry
--------
91/11/16
To: Dr. Michael W. Ecker
REC, 909 Violet Terrace, Clarks Summit, PA 18411
From: Harry J. Smith, 19628 Via Monte Dr., Saratoga, CA 95070
Enclosure: MS-DOS disk (PTripleP - Pythagorean Triples Plotted)
Dear Mike,
This is a follow-up to the letter I wrote you about your article "A New Way to Generate Pythagorean Triples?" in REC Sep/Oct/Nov 1991. I thought it would be interesting to plot the results of my program PTriples.Pas since it claims to generate "All" primitive P-Triples (Pythagorean triples), so I wrote PTriplesP.Pas.
The plotted output on the screen showed that while the matrix transform method may eventually generate any given primitive P- triple, many very large ones are generated before some relatively small ones. The method is not efficient for filling a given square with the origin in the lower left hand corner.
I added a second method to PTripleP.Pas for generating the primitive P-Triples. The algorithm for this method is:
_"Fast exhaustive search method":
__u = 1;
__while (u < S) do begin "S = Size of square"
____v = 1;
____while (v < u) do begin
______if (Odd(u) <> Odd(v)) and (GCD(u, v) = 1) then begin
________a = u*u - v*v; b = 2*u*v;
________if (b < S) and (a < S) then Plot(a, b);
________else begin
__________if (b >= S) then begin
____________v = S;
____________if (a >= S) then u = S; "Break-out of loop"
__________end;
________end;
______end;
______v = v + 1;
____end;
____u = u + 1;
__end;
This algorithm is very fast and the plotted output shows interesting regions and curved lines where primitive P-triples are missing.
Sincerely,
Harry
--------
Return to Fibonacci Numbers
Return to Number Theory, Algorithms, and Real Functions
Return to Harry's Home Page
times since October 20, 2004.