Limie's blog

A question
By Limie, history, 5 hours ago, In English

How to quickly find the value of each item in the following sequence.

$$$a_n=\lfloor (1+\sqrt{3})^n \rfloor$$$

Calculated in the sense of taking a mode.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Limie (previous revision, new revision, compare).

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you want to calculate all the values from 1 to n? or just for specific large n values?
It looks like you got this from the formula a_n = 2*(a_(n-1)+a_(n-2)).
If you want all values from 1 to n that'l take at least O(n) anyway so then use the recurrence

→ Reply
  • »
    »
    5 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I only want to calculate one values.

    → Reply
    • »
      »
      »
      4 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      then given the fact we know its equal to this recurence, we can use matrix exponentiation to calculate values in O(logn)
      here's a post that explains about this a bit more.

      → Reply
      • »
        »
        »
        »
        3 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but $$$\lfloor (1+\sqrt{3})^n \rfloor$$$ is not equal to the formula a_n = 2*(a_(n-1)+a_(n-2)).

        → Reply
        • »
          »
          »
          »
          »
          3 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          True, i miscalculated, but here you can find the coefficients of a recurrence with the 4 previous elements. https://oeis.org/A080041

          → Reply
          • »
            »
            »
            »
            »
            »
            3 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            why a(n) = A080040(n) — (1+(-1)^n)/2？

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 hours ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              No idea, but there are coefficiebts writenn for the recurrnece. Which is a_n = 2a_(n-1)+3a_(n-2)-2(a_(n-3)+a_(n-4))

              → Reply
»
3 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

But it's fast enough, since it's exponiental, it will only be calculted in log(n). Or is the problem of float relative error, if yes can you provide the equation that have this number as solution?

→ Reply
  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry,I need to calculated in the sense of taking a mode.

    → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Limie (previous revision, new revision, compare).

→ Reply