0

Given a number and a ratio, how do I create an exponentially growing list of numbers, whose sum equals the starting number?

>>> r = (1 + 5 ** 0.5) / 2
>>> l = makeSeq(42, r)
>>> l
[2.5725461188664465, 4.162467057952537, 6.735013176818984,
10.897480234771521, 17.63249341159051]
>>> sum(l)
42.0
>>> l[-1]/l[-2]
1.6180339887498953
>>> r
1.618033988749895
s4w3d0ff
  • 1,091
  • 10
  • 24
  • 5
    Expecting a fibonacci series like `0.12, 0.24, 0.36, 0.60, 0.96` is fundamentally wrong. Fibonacci series in concept starts with 0. – MohitC Apr 30 '16 at 19:39
  • 1
    you can create such a sequence for every length and every end result. some of these might even be similar to the fibonacci sequence. but what is exactly the question here? – Andreas Grapentin Apr 30 '16 at 19:39
  • A). You would have to define the interval for smaller numbers, which is not a Fibonacci sequence, and B). There are already ways to invert the standard Fibonacci sequence, however, do not guarantee a good result: http://stackoverflow.com/a/5162856/4131059 – Alex Huszagh Apr 30 '16 at 19:42
  • @MohitC Yes, a basic fib series starts with 0... I'm asking for the reverse, so there more than likely wont be a 0 (and I wont be needing it anyway). I just need the sum of the sequence to be as close to the start number as possible. The size of the sequence can be dynamic depending on the number. – s4w3d0ff Apr 30 '16 at 20:18
  • 1
    chepner's answer is correct but you can also easily get a sequence of a given length that is exactly exponential if you want. Do you? – Alex Hall Apr 30 '16 at 20:23
  • @AlexHall can I control the sum of the sequence to some degree? – s4w3d0ff Apr 30 '16 at 20:27
  • Yes, based on the length of the sequence and the total the first term can be calculated. – Alex Hall Apr 30 '16 at 20:34
  • @AlexHall ya that might be what I need – s4w3d0ff May 01 '16 at 01:41
  • It's unclear what you consider to be a "Fibonacci" sequence, as your second example appears to be more of a [generalized Fibonacci sequence](https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers) that doesn't start with 0, 1. Furthermore, there is more than one way to form the desired sum, especially if you haven't specified the length. In any case, this would be more of a question for [math.se], since it's not a programming problem. – 200_success May 01 '16 at 05:23
  • @200_success "I really just want to split a number into a list that has exponential growth and preferably as close to the "golden ratio" (1.618033988749...) such as a Fibonacci sequence." I apologize for my lack of knowledge in mathematical terminology/theory.... Serves me right for mindlessly posting shit questions on SO – s4w3d0ff May 03 '16 at 04:10

5 Answers5

5

A discrete sequence of exponentially growing numbers is called a geometric progression. The sum is called a geometric series. The formula here can easily be solved to produce the sequence you need:

>>> n = 5
>>> r = (1 + 5 ** 0.5) / 2
>>> r
1.618033988749895
>>> total = 2.28
>>> a = total * (1 - r) / (1 - r ** n)
>>> a
0.13965250359560707
>>> sequence = [a * r ** i for i in range(n)]
>>> sequence
[0.13965250359560707, 0.22596249743170915, 0.36561500102731626, 0.5915774984590254, 0.9571924994863418]
>>> sum(sequence)
2.28
>>> sequence[1] / sequence[0]
1.618033988749895
>>> sequence[2] / sequence[1]
1.618033988749895
>>> sequence[2] / sequence[1] == r
True

It's also worth noting that both this problem and the original problem of the Fibonacci could be solved using a binary search / bisection method.

Alex Hall
  • 34,833
  • 5
  • 57
  • 89
  • Wonderful! This is what I was looking for, sorry if I am horrible at explaining my intent, and thanks everyone for "schooling" me on what a "real" Fibonacci series is... Looks like I will be studying geometric progression for awhile. – s4w3d0ff May 01 '16 at 01:55
3

Pick any sequence of Fibonacci numbers you want. Add them up, and divide your target number by the sum to get a scaling factor. Multiply each number in your chosen sequence by the scaling factor, and you'll have a new sequence that sums to your target, and has the same ratio of adjacent terms as the original sequence of Fibonacci numbers.

To generate the example in your question, note that 1 + 2 + 3 + 5 + 8 = 19, and 2.28/19 = 0.12.

chepner
  • 497,756
  • 71
  • 530
  • 681
  • While this is a valid answer, very "eye-opening" in terms of what I was trying to do, and it does ultimately solve my problem, Alex Hall's answer was more along the lines of what I needed and he had working code. Thank you for your answer. – s4w3d0ff May 01 '16 at 02:08
2

The Fibonacci sequence goes as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... etc. As you may have already seen in the comments on your question, the Fibonacci sequence itself doesn't "scale" (i.e., fib_seq * 0.12 = 0, 0.12, 0.12, 0.24, 0.36, 0.60, 0.96 ... etc. isn't the Fibonacci sequence any longer), so you you can really only make a Fibonacci series in the order the values are presented above. If you would like to make the Fibonacci sequence dynamically scalable depending on some criteria, please specify further what purpose that would serve and what you are having trouble with so that the community can help you more.

Now, let's start with the basics. If you've had trouble with implementing a function to print the Fibonacci Sequence in the first place, refer to the answer @andrea-ambu gives here: https://stackoverflow.com/a/499245/5209610. He provides a very comprehensive explanation of how to not only implement the Fibonacci Sequence in a function in any given language, but even goes further to explore how to do so efficiently!

I presume that you are trying to figure out how to write a function that will take a user-provided integer and print out the Fibonacci series that sums up to that value (i.e., print_fib_series(33) would print 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13). This is fairly easily achievable by just incrementally adding the next value in the Fibonacci series until you arrive to the user-provided value (and keeping track of which values you've summed together so far), assuming that the user-provided value is a sum of Fibonacci series values. Here's an easy implementation of what I just described:

# Recursive implementation of the Fibonacci sequence from the answer I linked
def fib_seq(ind):
    if ind == 0: 
        return 0;
    elif ind == 1: 
        return 1;
    else: 
        return fib_seq(ind - 1) + fib_seq(ind - 2);

def list_fib_series(fib_sum, scaling_factor):
    output_list = [];
    current_sum = 0;
    for current_val in fib_seq():
        current_sum += current_val * scaling_factor;
        output_list.append(current_val);
        if current_sum == fib_sum:
            return output_list;
        elif current_sum > fib_sum: 
            return 0; # Or you could raise an exception...


fib_list = list_fib_series(2.4, 0.12):
print ' + '.join(map(str, fib_list));

So, considering the decimal value of 2.4 you could apply a linear scaling factor of 0.12 to the Fibonacci series and get the result you indicated in your question. I hope this helps you out!

Community
  • 1
  • 1
Vladislav Martin
  • 1,504
  • 2
  • 15
  • 34
  • If you scale the sequence it's not called the Fibonacci sequence any longer but that still seems to be what OP wants. – Alex Hall Apr 30 '16 at 20:37
  • In that case, I'd make a small change to the code I provided in my answer. Instead of `current_sum += current_val` I'd write `current_sum += current_val * scaling_factor`, making `scaling_factor` a second input parameter to the `list_fib_series(fib_sum, scaling_factor)` function. That would apply whatever scale the OP would like to apply, while keeping the logic consistent. – Vladislav Martin Apr 30 '16 at 20:40
0

Forget about the decimal numbers, like julienc mentioned program would never know where to start from if you bend the 'definition of Fibonacci series' like the way you wish to. You must be definitive about fibonacci series here.

For whole numbers and actual definition of fibonacci series, best you can do is make a program which takes number as input and tells whether the number sums up to some fibonacci series. And if it does then print the series. Assuming this is what you want.

a = 33

f_list = []

def recur_fibo(n):
    if n <= 1:
        return n
    else:
        return(recur_fibo(n-1) + recur_fibo(n-2))

i=0
total = 0
while True:
    num = recur_fibo(i)
    total += num
    f_list.append(num)
    if total > a:
        print "Number can not generate fibonacci series"
        break
    elif total == a:
        print "Series: %s" % f_list
        break
    i +=1

Output:

Series: [0, 1, 1, 2, 3, 5, 8, 13]
MohitC
  • 4,541
  • 2
  • 34
  • 55
0

Based off of Alex Hall's answer, this is what I ended up using:

def geoProgress(n, r=(1 + 5 ** 0.5) / 2, size=5):
    """ Creates a Geometric Progression with the Geometric sum of <n>
    >>> l = geoProgress(42)
    >>> l
    [2.5725461188664465, 4.162467057952537, 6.735013176818984,
    10.897480234771521, 17.63249341159051]
    >>> sum(l)
    42.0
    >>> l[-1]/l[-2]
    1.6180339887498953
    """
    return [(n * (1 - r) / (1 - r ** size)) * r ** i for i in range(size)]
s4w3d0ff
  • 1,091
  • 10
  • 24