Characteristic value of Fibonacci Sequences

[ramsey2879]

C(a,b) = a^2 + ab -b^2

The characteristic value of a Fibonacci sequence is an interesting property.
1) C(a,b) = C(a,a-b)
2) C(a,b) * C(c,d) = C(ac+ad-bd,bc-ad)
3) C(a,b) * C(a,a-b) = C(2a^2-2ab+b^2,2ab-b^2) =(C(a,b))^2

C(a,b)^n = C(A_{n},-B_{n})
A_{n}=\sum_{i=0}^{n}F_{i-1}nCia^{i}b^{(n-i)}
B_{n}=\sum_{i=0}^{n}F_{i-2}nCia^{i}b^{(n-i)}

Opps the last two equations are sums as i goes from 0 to n
F_i ={-1,1,0,1,1,2,3...} with F_{0}= 0
nCi are the binominal coefficients

 

[ramsey2879]

C(a,b) = a^2 + ab -b^2

The characteristic value of a Fibonacci sequence is an interesting property.
1) C(a,b) = C(a,a-b)
2) C(a,b) * C(c,d) = C(ac+ad-bd,bc-ad)
3) C(a,b) * C(a,a-b) = C(2a^2-2ab+b^2,2ab-b^2) =(C(a,b))^2

C(a,b)^n = C(A_{n},-B_{n})
A_{n} = \sum_{i=0}^{n}F_{i-1}nCia^{i}b^{(n-i)}
B_{n} = \sum_{i=0}^{n}F_{i-2}nCia^{i}b^{(n-i)}

Opps the last two equations are sums as i goes from 0 to n
F_i ={-1,1,0,1,1,2,3...} with F_{0}= 0
nCi are the binominal coefficients

This one may or may not be proven by induction, base on my post earlier at 7 today it is proven for a=b but for "a" not equal to "b" there is more work to do.

 

[John Creighto]

Forgive me for this question but what is the:
Characteristic value of Fibonacci Sequences

I wasn't a math major when I was in university.

 

[ramsey2879]

Forgive me for this question but what is the:
Characteristic value of Fibonacci Sequences

I wasn't a math major when I was in university.

Good question since the only known posting on this before me was the posting of the sequence of characteristic values by another , Allan Wechsler http://www.research.att.com/~njas/sequences/A022344 that did not explain the sequence. Go to this link and see my added comments of February 2007. The absolute value of (a^2 +ab -b^2) where a,b are any sequential terms from the nth row of the Wythoff array A035513 which rows are each Fibonacci sequences. It is the absolute value of T(n,i-1)*T(n,i+1)-T(n,i)^2 that actually forms the terms a(n) of sequence A022344, but for some reason no one noted this until my comments. The sequence (which I "discovered" independently) has a formula the same as though the factors were arranged in determinant form which is probably why the sequence was called "Allan Wechsler's J-Determinant Sequence". I call this the "sequence of characteristic values" since it does not matter which adjacent terms from the nth row are used for the sequential terms a,b to compute the value a(n). Note, however, the order must be the order they appear in the nth row of Wythoff's array since C(a,b) is not the same as C(b,a) where a<>b.

 

[ramsey2879]

C(a,b) = a^2 + ab -b^2

The characteristic value of a Fibonacci sequence is an interesting property.
1) C(a,b) = C(a,a-b)
2) C(a,b) * C(c,d) = C(ac+ad-bd,bc-ad)
3) C(a,b) * C(a,a-b) = C(2a^2-2ab+b^2,2ab-b^2) =(C(a,b))^2

C(a,b)^n = C(A_{n},-B_{n})
A_{n}=\sum_{i=0}^{n}F_{i-1}nCia^{i}b^{(n-i)}
B_{n}=\sum_{i=0}^{n}F_{i-2}nCia^{i}b^{(n-i)}

Opps the last two equations are sums as i goes from 0 to n
F_i ={-1,1,0,1,1,2,3...} with F_{0}= 0
nCi are the binominal coefficients

I improved upon the last equation so that the Fibonacci series can be other than the standard Fibonacci series.
Let x and y be F_0 and F_1 respectively and F_{n}=F_{n-2}+F_{n-1}

Then

C(a,b)^{n} = C(A_{n},B_{n})/C(x,y)

A_{n} = \sum_{i=0}^{n}F_{i}nCia^{n-i}b^{i}

B_{n} = \sum_{i=0}^{n}F_{i+1}nCia^{n-i}b^{i}

Now given that pCi = 0 mod p(prime) except for i=0 and i=p; C(a,b)^(p)=C(a,b) mod p = C(xa +b* F_{p},ya + bF_{p+1}) /C(x,y) would seem to be a new property of Fibonacci series assuming that each of C(a,b), a and b <> 0 mod p.

This property is the next candidate for proof. Eventually proof of the whole might be found.

 

[ramsey2879]

I improved upon the last equation so that the Fibonacci series can be other than the standard Fibonacci series.
Let x and y be F_0 and F_1 respectively and F_{n}=F_{n-2}+F_{n-1}

Then

C(a,b)^{n} = C(A_{n},B_{n})/C(x,y)

A_{n} = \sum_{i=0}^{n}F_{i}nCia^{n-i}b^{i}

B_{n} = \sum_{i=0}^{n}F_{i+1}nCia^{n-i}b^{i}

Now given that pCi = 0 mod p(prime) except for i=0 and i=p; C(a,b)^(p)=C(a,b) mod p = C(xa +b* F_{p},ya + bF_{p+1}) /C(x,y) would seem to be a new property of Fibonacci series assuming that each of C(a,b), a and b <> 0 mod p.

This property is the next candidate for proof. Eventually proof of the whole might be found.

I have checked out this "new property" using the standard Fibonacci series but with "F_0" = F_{-(N+1)/2} such that "F_n+1" = F_{(n+1)/2} and set a=b=1. I figured that since the characteristic value of that series was 1 and since a = b = 1, and since F_{-n} = -1^{n+1}F_{n} that the above property could be set forth more clearly. I was rewarded by the following result .

My new hypothesis
Let N Be odd and define the subscripts A,B,C,D to be the sequential integers from (N-3)/2 to
(N+3)/2. Then the following equivalence holds if and only if N is Prime

If N = -1 mod 4 then C(-F_{C},F_{B}) = C(-F_{A},F_{D}) \mod N

If N = 1 mod 4 then C(F_{C},-F_{B}) = C(F_{D},F_{A}) \mod N

I check this as far as my excel program would allow (up to prime = 53). This may or may not be useful but it is an improvement on Wilson's Theory. The only doubt I have is the "and only if" part but neither part stands proven.

 

[Don Blazys]

To: ramsey 2879

Quoting ramsey 2879

My new hypothesis
Let N Be odd and define the subscripts A,B,C,D to be the sequential integers from (N-3)/2 to
(N+3)/2. Then the following equivalence holds if and only if N is Prime.

What a great hypothesis!

This is truly one of the most interesting results that I have ever seen, and I'm an "old timer"!

The "if and only if part" does indeed stand a very good chance of being correct
and from a purely theoretical standpoint, it is clearly of immense importance!

Please continue posting the results of your reasearch, investigations and other work on this
incredible discovery!

Don.

 

[CRGreathouse]

I check this as far as my excel program would allow (up to prime = 53). This may or may not be useful but it is an improvement on Wilson's Theory. The only doubt I have is the "and only if" part but neither part stands proven.

This looks like the Lucas test, so I imagine the first failure will be at n = 705.

 

[ramsey2879]

This looks like the Lucas test, so I imagine the first failure will be at n = 705.

After considering the actual values of the first few terms as computed from my expressions they are indeed the Lucus numbers and the test does appear to be an equivalent statement of the Lucus test. It is not the only test generated by the study of powers of the Characteristic function. The Lucus test is derived from letting a = 1 and b both = x and generating powers of C(1,1) by using each the formulas 1-3 as given in my first post in a particula manner. Basically, if you multiply (a,b)*(a,b) to get (A(2),B(2)) by operation 3 and continue doing so to get as per my first post you usually end up with A(n) and B(n) no longer being coprime even if a and b are coprime, but if you alternate the equivalent expressions by letting a= A(1),b=B(1) then doing the multiplication operation 3 of my first post with (a,a-b)*(A(1),B(1)) to get (A(2),B(2)) then use (a,b)*(A(2),B(2)) to get (A(3),B(3) , i.e. by alternating between (a,a-1) and (a,b) as the first ordered pair times the pair (A(n),B(n)) you get coprime A(n),B(n) whenever b is coprime to a. You can also let "a" = x+1 and "b" = x although this generates a triangular series of polynominals for similar to Pascal's triangle, the only similarity is that the generated terms for A(n) and B(n) in the relation C(A(n), B(n)) = C(A,B)^n are polynominals in the nth degree where the first and last term coefficients of A are both the Fibonacci number F(n) and the (first and last term coefficients of B sum to F(n) and also that the remaining terms are all divisible by n if n is prime. Since C(2,1) = 5, then 5*F(n)^2 = 5^n mod n if n is prime. This test (F(n)^2 = 1)is weaker than the Lucus test since there are more presudo primes but apparently holds for all primes other than 5 (this time I checked it out up to the 1,800 th prime). About half of the Lucus presudo primes are also presudo primes for this test, so you can't get a perfect test by a combination of these two tests. I tried other combinations for a and b, but the only apparent tests were variations of these two tests.

I have been limiting my investigation so far by chosing various other expresions in the first degree for a and b, and determining A(n) and B(n) as polynominals of degree n by the multiplication operation, relation 3 of my first post using alternative first order expresions (a,b) and (a,a-b) as above and determining the relation between a and b such that the polynominals of degree n give all terms divisible by n if n is prime with the exception of one or both of the first and last terms.

One way to speed the process is to determine the polynoninals for m = 2n by multiplying (A(n),B(n)) with (A(n),A(n)-B(n)) then multiplying these polynominals together using multiple operations 3. This is how I deduced the result given earlier in my thread with respect to the coefficients all being a combination of Fibonacci numbers and the Binominal coefficients.

 

[ramsey2879]

2879;2130859]After considering the actual values of the first few terms as computed from my expressions they are indeed the Lucus numbers and the test does appear to be an equivalent statement of the Lucus test. It is not the only test generated by the study of powers of the Characteristic function. The Lucus test is derived from letting a = 1 and b both = x[sic-a and b both = 1 per my post on March 2 at 9am)] and generating powers of C(1,1) by using each the formulas 1-3 as given in my first post in a particula manner. Basically, if you multiply (a,b)*(a,b) to get (A(2),B(2)) by operation 3[sic- operation 2] and continue doing so to get as per my first post you usually end up with A(n) and B(n) no longer being coprime even if a and b are coprime, but if you alternate the equivalent expressions by letting a= A(1),b=B(1) then doing the multiplication operation 3[sic, should be operation 2] of my first post with (a,a-b)*(A(1),B(1)) to get (A(2),B(2)) then use (a,b)*(A(2),B(2)) to get (A(3),B(3) , i.e. by alternating between (a,a-1)[sic -(a,a-b) and (a,b) as the first ordered pair times the pair (A(n),B(n)) you get coprime A(n),B(n) whenever b is coprime to a. You can also let "a" = x+1 and "b" = x although this generates a triangular series of polynominals for similar to Pascal's triangle, the only similarity is that the generated terms for A(n) and B(n) in the relation C(A(n), B(n)) = C(A,B)^n are polynominals in the nth degree where the first and last term coefficients of A are both the Fibonacci number F(n) and the (first and last term coefficients of B sum to F(n) and also that the remaining terms are all divisible by n if n is prime. Since C(2,1) = 5, then 5*F(n)^2 = 5^n mod n if n is prime. This test (F(n)^2 = 1)is weaker than the Lucus test since there are more presudo primes but apparently holds for all primes other than 5 (this time I checked it out up to the 1,800 th prime). About half of the Lucus presudo primes are also presudo primes for this test, so you can't get a perfect test by a combination of these two tests. I tried other combinations for a and b, but the only apparent tests were variations of these two tests.

I have been limiting my investigation so far by chosing various other expresions in the first degree for a and b, and determining A(n) and B(n) as polynominals of degree n by the multiplication operation, relation 3 of my first post using alternative first order expresions (a,b) and (a,a-b) as above and determining the relation between a and b such that the polynominals of degree n give all terms divisible by n if n is prime with the exception of one or both of the first and last terms.

One way to speed the process is to determine the polynoninals for m = 2n by multiplying (A(n),B(n)) with (A(n),A(n)-B(n)) then multiplying these polynominals together using multiple operations 3 [sic operations 2] to produce the result given earlier in my thread with respect to the coefficients all being a combination of Fibonacci numbers and the Binominal coefficients.

Sorry for the errors. I rushed through my post because I knew my wife was expecting me to take her to the doctor and I wasn't sure if I would have time later. When I get around to it I will post some more.

 

[Don Blazys]

To: Ramsey 2879,

You took a different approach than did Lucas, and that, in and of itself,
makes your discovery unique.

Thanks,

Don.

 

[ramsey2879]

To: Ramsey 2879,

You took a different approach than did Lucas, and that, in and of itself,
makes your discovery unique.

Thanks,

Don.

There is more to show that my approach has some merit.
I found another Prime Test much stronger than the Lucas Test

Input an odd number N not divisible by 5 greater than 1
A = 1
B = 0
P = 2
Do
C = A
D = A-B
A = C+D
B = -D
P = P + 2
Loop Until P> N
Now (A + (-1)^( N^2 = 1 mod 10)) = 0 Mod N if N is prime
Also (B +(N^2 = -1 mod 10) = 0 Mod N if N is prime

This two prong test yields only three presudo primes in the first thousand primes. The first presudo prime is 4181 but I haven't located the other two.

I think that an advantage to this test is that it only involves addition and subtraction.

The number of recursions could be shortened by multiplication as per method 3 of my first post in combination with the addition and subtraction

I would be glad to answer any questions concerning this test.

 

[CRGreathouse]

Your test takes n/2 steps, much worse than trial division.

I don't understand the final step in the test; can you give an example, perhaps for n = 101? I get (a, b, c, d) = (1500520536206896083277, -927372692193078999176, 573147844013817084101, 927372692193078999176).

 

[Hurkyl]

I reverse engineered it -- he's using the [.] operator where

[P] = 1 if P is true
[P] = 0 if P is false

except he's using parentheses for added confusion.

 

[Hurkyl]

I suppose since I calculated it, I should post it in case someone else wants to know: set

u = (3 + \sqrt{5}) / 2

v = (3 - \sqrt{5}) / 2

This test computes

A = \frac{(1-u) u^E - (1-v) v^E}{v - u}

B = \frac{u^E - v^E}{v - u}

where E = (N - 1) / 2

 

[CRGreathouse]

Thanks for posting that. Now I can post the first few pseudoprimes. My list matches (but exceeds) ramsey2879's list.

4181, 5777, 6479, 6721, 10877, 13201, 15251, 27071, 34561, 44099, 47519, 51841, 54839, 64079, 64681, 65471, 67861, 68251, 72831, 75077, 78089, 90061, 96049, 97921, 100127, 109871, 113573, 118441, 139359, 146611, 157079, 161027, 162133, 163081, 168299, 186961, 196559, 197209, 219781, 231703, 233519, 252601, 254321, 257761, 268801, 272611, 283361, 300847, 302101, 303101, 327359, 330929, 399001, 417601, 430127, 433621, 438751, 451979, 486359, 489601, 510719, 512461, 520801, 530611, 544159, 545279, 553679, 553839, 556421, 575599, 618639, 620279, 635627, 636641, 638189, 641199, 655201, 670879, 689359, 701569, 722261, 737471, 741751, 809999, 850541, 851927, 852841, 853469, 881011, 925681, 954239, 993509, 999941

 

[ramsey2879]

Your test takes n/2 steps, much worse than trial division.

I don't understand the final step in the test; can you give an example, perhaps for n = 101? I get (a, b, c, d) = (1500520536206896083277, -927372692193078999176, 573147844013817084101, 927372692193078999176).

The only confusing part I see in the final step as I set forth are the parenthetical true/false expressions.

If N = 3 or 7 mod 10 then (the expressions = 0,1) (-1)^0 = 1 so we have A+1 and B+1
If N = 1 or 9 mod 10 then (the expressions = 1,0) ...=-1 so we have A-1 and B+0

Interesting reverse engineering, but I actually based this on alternative type 2 multiplication by a = 1+x and b = 1+x or 0 alternatively, but I did only the constant x^(0) part.

 

[ramsey2879]

I reverse engineered it -- he's using the [.] operator where

[P] = 1 if P is true
[P] = 0 if P is false

except he's using parentheses for added confusion.

Sorry for the confusion, I did not know the convention to put this operator in brackets.

 

[ramsey2879]

I suppose since I calculated it, I should post it in case someone else wants to know: set

u = (3 + \sqrt{5}) / 2

v = (3 - \sqrt{5}) / 2

This test computes

A = \frac{(1-u) u^E - (1-v) v^E}{v - u}

B = \frac{u^E - v^E}{v - u}

where E = (N - 1) / 2

Thankyou for posting that. Interesting that such a straight forward recursion should match such a mathematical expression. Interesting that the number 3 pops in when I only used 1's and zeros as my multiplication operators. I will check my list for the presudo primes mention in the next post.

 

[ramsey2879]

Thanks for posting that. Now I can post the first few pseudoprimes. My list matches (but exceeds) ramsey2879's list.

4181, 5777, 6479, 6721, 10877, 13201, 15251, 27071, 34561, 44099, 47519, 51841, 54839, 64079, 64681, 65471, 67861, 68251, 72831, 75077, 78089, 90061, 96049, 97921, 100127, 109871, 113573, 118441, 139359, 146611, 157079, 161027, 162133, 163081, 168299, 186961, 196559, 197209, 219781, 231703, 233519, 252601, 254321, 257761, 268801, 272611, 283361, 300847, 302101, 303101, 327359, 330929, 399001, 417601, 430127, 433621, 438751, 451979, 486359, 489601, 510719, 512461, 520801, 530611, 544159, 545279, 553679, 553839, 556421, 575599, 618639, 620279, 635627, 636641, 638189, 641199, 655201, 670879, 689359, 701569, 722261, 737471, 741751, 809999, 850541, 851927, 852841, 853469, 881011, 925681, 954239, 993509, 999941

I do not get 6479 or 27071 as pseudoprimes. My list does not go any further than 27071. Are you sure they pass Hurkyl's tests with these numbers? If so that is not my test.

 

[Hurkyl]

Sorry for the confusion, I did not know the convention to put this operator in brackets.

For the record, the only place I remember seeing that operator is in Concrete Mathematics by Graham, Knuth, and Patashnik. I do not believe it is in widespread use (which is a shame, because it's really handy) -- thus the necessity to explain it if you intend to use it.

It is far more typical to state a test like yours in terms of cases -- e.g. "the answer is 1 in this case, and -1 in that case".

Thankyou for posting that. Interesting that such a straight forward recursion should match such a mathematical expression.

It's actually somewhat typical -- the closed form of a linear recurrence with constant coefficients is typically a sum of exponential terms. It's very much analogous to solving ordinary linear differential equations with constant coefficients.

Alternatively -- you can write your algorithm in terms of repeatedly multiplying by a matrix. Then, you just diagonalize the matrix, so you can compute (a closed form for) large powers easily. (u and v are the eigenvalues)

 

[CRGreathouse]

I do not get 6479 or 27071 as pseudoprimes. My list does not go any further than 27071. Are you sure they pass Hurkyl's tests with these numbers? If so that is not my test.

I tried implementing yours directly:

ram(n)={
	my(a=1,b=0,c,d,k,p);
	while(p<=n,
		c=a;
		d=a-b;
		a=c+d;
		b=-d;
		p+=2
	);
	k = (n^2%10)==1;
	(a + (-1)^k)%n == 0
};

but the output doesn't seem right at all. Would you verify the final condition? I imagine that's the root of the problem.

 

[ramsey2879]

I tried implementing yours directly:

ram(n)={
	my(a=1,b=0,c,d,k,p);
	while(p<=n,
		c=a;
		d=a-b;
		a=c+d;
		b=-d;
		p+=2
	);
	k = (n^2%10)==1;
	(a + (-1)^k)%n == 0
};

but the output doesn't seem right at all. Would you verify the final condition? I imagine that's the root of the problem.

Lets set the initial value of P to 2. The initial values a and b correspond to the first power, the subsequent values of a and b correspond to the 3rd, 5th, ... powers. To exit the loop with a,b at the "nth power", you need to set p to 2 initally so that p will always be 1 more than the current power of a and b

 

[ramsey2879]

I do not get 6479 or 27071 as pseudoprimes. My list does not go any further than 27071. Are you sure they pass Hurkyl's tests with these numbers? If so that is not my test.

My routine to get A and B appears to yield F(n) for A and -F(n-1) for B. Plugging that in my test becomes:
If N = 1,9 mod 10 (F(N)-1 = 0 Mod N and F(N-1) = 0 Mod N) if N is prime
If N = 3,7 mod 10 (F(N)+1 = 0 Mod N and F(N-1)-1 = 0 Mod N) if N is prime

I do have some confidence in Hurkyl's test but As you can see a well known formula for F(N) and F(N-1) also exists. I believe any discrepancy from my results may lie in the accuracy of the value of Sqr(5) to the Nth power. In my routine, I am continually reducing the value of A and B mod N as I am working with integers and therefore do not have to worry about large numbers of multiplications using an irrational number. As one can see this test is one step beyond the test F(n)^2 = 1 mod N which accounts for less pseudoprimes.