Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Characteristic value of Fibonacci Sequences

  1. Feb 24, 2009 #1
    [tex] C(a,b) = a^2 + ab -b^2[/tex]

    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

    [tex]C(a,b)^n = C(A_{n},-B_{n})[/tex]

    Opps the last two equations are sums as i goes from 0 to n
    [tex]F_i[/tex] ={-1,1,0,1,1,2,3...} with [tex]F_{0}= 0[/tex]
    nCi are the binominal coefficients
    Last edited by a moderator: Feb 24, 2009
  2. jcsd
  3. Feb 28, 2009 #2
    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.
  4. Mar 1, 2009 #3
    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.
  5. Mar 1, 2009 #4
    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 [Broken] 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.
    Last edited by a moderator: May 4, 2017
  6. Mar 1, 2009 #5
    I improved upon the last equation so that the Fibonacci series can be other than the standard Fibonacci series.
    Let x and y be [tex]F_0[/tex] and [tex]F_1[/tex] respectively and [tex]F_{n}=F_{n-2}+F_{n-1}[/tex]


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

    [tex]A_{n} = \sum_{i=0}^{n}F_{i}nCia^{n-i}b^{i}[/tex]

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

    Now given that [tex]pCi = 0[/tex] mod p(prime) except for [tex]i=0[/tex] and [tex]i=p[/tex]; 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.
    Last edited: Mar 1, 2009
  7. Mar 2, 2009 #6
    I have checked out this "new property" using the standard Fibonacci series but with "F_0" = [tex]F_{-(N+1)/2}[/tex] such that "F_n+1" = [tex]F_{(n+1)/2}[/tex] and set a=b=1. I figured that since the characteristic value of that series was 1 and since a = b = 1, and since [tex]F_{-n} = -1^{n+1}F_{n}[/tex] 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 [tex]C(-F_{C},F_{B}) = C(-F_{A},F_{D}) \mod N[/tex]

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

    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.
  8. Mar 21, 2009 #7
    To: ramsey 2879

    Quoting ramsey 2879
    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!

  9. Mar 22, 2009 #8


    User Avatar
    Science Advisor
    Homework Helper

    This looks like the Lucas test, so I imagine the first failure will be at n = 705.
  10. Mar 24, 2009 #9
    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.
  11. Mar 24, 2009 #10
    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.
  12. Mar 26, 2009 #11
    To: Ramsey 2879,

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


  13. Mar 31, 2009 #12
    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
    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.
  14. Mar 31, 2009 #13


    User Avatar
    Science Advisor
    Homework Helper

    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).
  15. Mar 31, 2009 #14


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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. :frown:
  16. Mar 31, 2009 #15


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

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

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

    This test computes

    [tex]A = \frac{(1-u) u^E - (1-v) v^E}{v - u}[/tex]

    [tex]B = \frac{u^E - v^E}{v - u}[/tex]

    where E = (N - 1) / 2
  17. Mar 31, 2009 #16


    User Avatar
    Science Advisor
    Homework Helper

    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
  18. Mar 31, 2009 #17
    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.
    Last edited: Mar 31, 2009
  19. Mar 31, 2009 #18
    Sorry for the confusion, I did not know the convention to put this operator in brackets.
  20. Mar 31, 2009 #19
    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.
  21. Mar 31, 2009 #20
    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.
    Last edited: Mar 31, 2009
  22. Mar 31, 2009 #21


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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".

    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)
    Last edited: Mar 31, 2009
  23. Mar 31, 2009 #22


    User Avatar
    Science Advisor
    Homework Helper

    I tried implementing yours directly:
    Code (Text):
        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.
  24. Mar 31, 2009 #23
    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
  25. Apr 8, 2009 #24
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook