Member Avatar for kiddo39

I'm trying to use this code for a fibonocci sequence where I'm setting the starting numbers
as b= and c=. What I'd like to do though is have it stop after so many numbers are added together, in this case it would be 53rd (a=53). I've tried a 'for i in range(53):'loop but
that doesn't work for this. The a,b,c numbers can be randomly choosen, which I
have working, but for this snippet I'm setting them as static. Suggestions?

a =  53
b = 7
c = 18


k, l = b, c
while l < 9999999999999999:
    xa = l
    k,l = l, k+l
    print xa,

   #for i in range(a):
         #print i

    #for x in xa: ??
  • 4 Contributors
  • 5 Replies
  • 261 Views
  • 21 Hours Discussion Span
  • Latest Post Latest Post by HiHe

Dani AI

Generated

A few focused points that expand on the thread and give a direct, efficient way to get the 53rd (or any nth) term when the first two terms are arbitrary.

Indexing and a simple formula
When the starting values are S1 = b and S2 = c (the OP pattern), the recurrence Sn = S{n-1} + S_{n-2} implies, for n >= 2:
Sn = b * F{n-2} + c * F_{n-1},
where F_k is the standard Fibonacci sequence with F_0 = 0, F_1 = 1. That formula removes off-by-one confusion: handle S1 and S2 as special cases, then use the formula for higher n. See the Fibonacci definition for the F_0/F_1 convention. (Fibonacci sequence)

Compute the nth term in O(log n)
If you only need the 53rd element (or a very large index) you do not need to iterate the whole sequence. Use the fast-doubling method to compute Fibonacci numbers in O(log n) time and then apply the linear combination above. Example Python (original, not repeating code already posted):

def fib_pair(n):
    # returns (F_n, F_{n+1})
    if n == 0:
        return (0, 1)
    a, b = fib_pair(n // 2)
    c = a * (2 * b - a)
    d = a * a + b * b
    if n % 2 == 0:
        return (c, d)
    else:
        return (d, c + d)

def nth_term_from_seeds(b, c, n):
    if n == 1:
        return b
    if n == 2:
        return c
    f_nm2, f_nm1 = fib_pair(n - 2)
    return b * f_nm2 + c * f_nm1

# usage: b=7, c=18, n=53
# print(nth_term_from_seeds(7, 18, 53))

When to use which approach
For small n a simple for-loop (as suggested) or a generator + islice (as and recommended) is perfectly fine and very readable. For very large n or when you need the result fast (or modulo some M), use fast doubling — it is standard and runs in logarithmic time. See an explanation and modular variants of the method for reference. (Fast doubling method)

Notes: be explicit about whether S1 is your first element; Python integers are arbitrary-precision so overflow is not a concern unless you want a modulus. Avoid single-character names like l for clarity (echoing ).

Recommended Answers

All 5 Replies

Member Avatar for woooee

I've tried a 'for i in range(53):'loop but
that doesn't work for this

Why not? It seems like the proper way to do this. Note that you salt the variables with the first 2 numbers, so the loop would run 2 less than the number of the total sequence.

Also, do not use i, O, l, etc. as variable names as they look like numbers, i.e. k+l, is that k+el or k+one?

a =  23
b = 7
c = 18

print 1, b
print 2, c
for ctr in range(a-2):
    b, c = c, b+c
    print ctr+3, c
Edited by woooee
Member Avatar for kiddo39

I see...I was apparently doing something wrong because my 'for' loop kept throwing an 'index out of range' error for me. Thanks, that works the way I need it to and point taken on the variables! :)

Member Avatar for HiHe

Why not simply use itertools.islice and a fibonacci generator?

Member Avatar for snippsat

wooee show that range() work fine,another good and pythonic way is to use a generator.
If also use itertools.islice() can make it even more versatile.

from itertools import islice

def fib(a=7, b=18):
    yield a
    while True:
        yield b
        a, b = b, a + b

fib_numb_1 = list(islice(fib(),15))
# Slice out last 3 number
fib_numb_2 = list(islice(fib(),12,15))
# Slice out number with a step of 2
fib_numb_3 = list(islice(fib(),0,23,2))
#---
print fib_numb_1
print fib_numb_2
print fib_numb_3

'''Output-->
[7, 18, 25, 43, 68, 111, 179, 290, 469, 759, 1228, 1987, 3215, 5202, 8417]
[3215, 5202, 8417]
[7, 25, 68, 179, 469, 1228, 3215, 8417, 22036, 57691, 151037, 395420]
'''

No list output,is of course just to loop over generator object.

for i in islice(fib(),15):
    print i

7
18
25
43
68
111
179
290
469
759
1228
1987
3215
5202
8417

With count trow in enumerate().

for index, item in enumerate(islice(fib(),15), 1):
    print '{} -> {}'.format(index, item)

1 -> 7
2 -> 18
3 -> 25
4 -> 43
5 -> 68
6 -> 111
7 -> 179
8 -> 290
9 -> 469
10 -> 759
11 -> 1228
12 -> 1987
13 -> 3215
14 -> 5202
15 -> 8417
Edited by snippsat
Member Avatar for HiHe

The xfibo() function is fast, so you might as well use:

import itertools

def xfibo():
    """
    a generator for Fibonacci numbers, goes
    to next number in series on each call
    """
    current, previous = 0, 1
    while True:
        yield current
        # use a tuple swap
        current, previous = previous, current + previous

# to get selected results of a generator function use
print( "show Fibonacci series 77 through 80:" )
for k in itertools.islice(xfibo(), 77, 81):
    print( k )

"""my result -->
    show Fibonacci series 77 through 80:
5527939700884757
8944394323791464
14472334024676221
23416728348467685
"""
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.