Mathematicians discover the Fibonacci numbers hiding in strange spaces | Hacker News Reader

Mathematicians discover the Fibonacci numbers hiding in strange spaces

quantamagazine.org

84 pointspseudolus33 comments

I tried reading it but could not understand the article (amazing, given its Quanta magazine).

But I’m fascinated by the Fibonacci series so was compelled to add some comment. Here’s a cool fact that I recently learned F_gcd(m,n) = gcd(F_m, F_n). You can use this fact to prove that every prime divides a Fibonacci number (https://math.stackexchange.com/questions/695979/does-every-p...)

While this fact about gcds is true, your link goes to a proof (incidentally, happens to be mine) that does not use this fact. :-)

Great to see you here and you're absolutely right: I got carried away with a comment (which, I now see, is yours, too :-) about Fibonacci numbers being a "strong divisibility sequence", this was the first time I've heard of this concept.

:-) Here's something else, almost entirely unrelated, that I like: we can prove that any two Fermat numbers 2^(2^n)+1 have gcd 1; this gives a proof (different from Euclid's) that there are infinitely many prime numbers: https://en.wikipedia.org/w/index.php?title=Fermat_number&old...

I believe this also implies that the Fibonomial (not a typo) coefficients are integers, which is neat

An excellent video series by Vi Hart on Fibonacci numbers hiding in other strange places (and spirals and plants):

Part 1: https://www.youtube.com/watch?v=ahXIMUkSXX0

Part 2: https://www.youtube.com/watch?v=lOIP_Z_-0Hs

Part 3: https://www.youtube.com/watch?v=14-NdQwKz9w

It revealed the existence of staircase-like structures with infinitely many steps. The size of each step in these “infinite staircases” was a ratio of Fibonacci numbers.

As the staircase ascended, the steps became smaller and smaller, the top of the staircase crushing up against the golden ratio. Neither the golden ratio nor the Fibonacci numbers has any apparent relationship to the problem of fitting a shape inside a ball. It was bizarre to find these numbers lurking within McDuff and Schlenk’s work.

Is it me, or is that terrible scientific writing? I don't understand what the author is actually trying to describe, and I kinda have my doubts whether the authors knows herself.

It sounds as if the author recorded an interview, did not understand much but inserted what he or she deemed interesting. I cannot parse that text either.

I think it is somewhat clear what they're getting at, and it's explained visually in the picture further down.

Though maybe "crushing against the golden ratio" is not a good way to phrase the situation. It sounds a little bit like the stairs form a converging series, but from the text further up and the picture it seems pretty obvious that the author intends to convey that the step size of the stairs approaches a (power of) the golden ratio from above.

In defense of the author, I have trouble wrapping my head around symplectic geometry, and my PhD research was in an adjacent area, semisimple Lie groups. I'd have to put in a considerable amount of effort to develop an intuition for this setting.

The 0,1 Fibonacci sequence is my favourite numerical series. I use it in backoff algorithms at work when I have systems that talk to each other (prefer it over exponential backoff because it doesn't grow too quickly). I even use it in gap thresholds for data that is expected to update irregularly. And it works pretty well.

Mine too. Hence my username of Irrational.

By exponential back-off, do you mean always doubling?

To be nitpicky, the Fibonacci sequence also grows exponentially, with successive terms tending to the golden ratio. You could equally well keep using exponential backoff, by replacing 2 with a smaller number (such as the golden ratio) instead.

True, exponential backoff doesn't necessarily mean doubling, it's just the common understanding. Using Fibonacci explicitly gives me easy-to-use whole numbers.

My ten year old found Fibonacci numbers in the reciprocal of 89.

That's excellent!

I think it's pretty interesting that this sequence can be hiding within the 44 repeating digits of the decimal expansion of 1/89:

0.1123595505617977528089887640449438202247191011235… [1]

A proof can be found here: https://www.cantorsparadise.com/why-does-1-89-represent-the-...

[1] I couldn't easily find this many digits online, but here's a Python program to calculate them:

  num = int(input('numerator: '))
  denom = int(input('denom: '))
  sig = int(input('significant digits: '))
  
  div = num // denom
  rem = num % denom
  
  print(f'{div}.{(rem*(10**sig))//denom}')

0.01123595505617977528089887640449438202247191011235955056179775280898876404494382022471910112359550561797752808988764044943820224719101123595505617977528089887640449438202247191011235955056179775280898876404494382022471910112359550561797752808988764044943820...

Off by an OoM.

Oops yeah, I should have used some left zero padding. ;)

okay, so i'm confused

  1+1 = 2
  1+2 = 3
  2+3 = 5
  3+5 = 9???

3+5=8

8+5=13

I assume the '1' of the '13' carries into the 8 => 8+1=9

Same for the numbers after that.

Ha! In four lines, you described much more simply than whatever the sibling commenter decided to do ;)

Yet again, foiled by forgetting to carry the one!!!! Those are the kinds of "finds" that I'm way too out of practice in searching for patterns to have noticed the answer. Or I'm just too lazy and out of practice and called it quits too quickly. Now, show me a syntax error of missing }, ), ], etc, and I'll find that pattern with/without an IDE!

There is a carry from the 5+8=13.

Add these up and you get closer and closer to 1 / 89:

    0.0
    0.01
    0.001
    0.0002
    0.00003
    0.000005
    0.0000008
    0.00000013
    0.000000021
    0.0000000034
    0.00000000055
    0.000000000089
    0.0000000000144
    0.00000000000233
    0.000000000000377
    0.0000000000000610
    0.00000000000000987
    0.000000000000001597
    0.0000000000000002584
    0.00000000000000004181
    0.000000000000000006765
    0.0000000000000000010946
    0.00000000000000000017711
    0.000000000000000000028657
    0.0000000000000000000046368
    0.00000000000000000000075025
    0.000000000000000000000121393
    0.0000000000000000000000196418
    0.00000000000000000000000317811
    0.000000000000000000000000514229
    0.0000000000000000000000000832040
    0.00000000000000000000000001346269
    0.000000000000000000000000002178309
    0.0000000000000000000000000003524578
    0.00000000000000000000000000005702887
    0.000000000000000000000000000009227465
    0.0000000000000000000000000000014930352
    0.00000000000000000000000000000024157817
    0.000000000000000000000000000000039088169
    0.0000000000000000000000000000000063245986
    0.00000000000000000000000000000000102334155
    0.000000000000000000000000000000000165580141
    0.0000000000000000000000000000000000267914296
    0.00000000000000000000000000000000000433494437
    0.000000000000000000000000000000000000701408733
    0.0000000000000000000000000000000000001134903170
    0.00000000000000000000000000000000000001836311903
    0.000000000000000000000000000000000000002971215073
    0.0000000000000000000000000000000000000004807526976
    0.00000000000000000000000000000000000000007778742049
    0.000000000000000000000000000000000000000012586269025
    0.0000000000000000000000000000000000000000020365011074
    0.00000000000000000000000000000000000000000032951280099
    0.000000000000000000000000000000000000000000053316291173
    0.0000000000000000000000000000000000000000000086267571272
    0.00000000000000000000000000000000000000000000139583862445
    0.000000000000000000000000000000000000000000000225851433717
    0.0000000000000000000000000000000000000000000000365435296162
    0.00000000000000000000000000000000000000000000000591286729879
 +  0.000000000000000000000000000000000000000000000000956722026041
    --------------------------------------------------------------
    0.011235955056179775280898876404494382022471910112174867308031 ≈ 1 / 89
    ==============================================================

For those interested in running this with more iterations, here is a Python script:

    from decimal import *
    
    n = 60

    getcontext().prec = n
    t = Decimal(0)
    p, q = 0, 1
    for i in range(1, n+1):
        s = f'0.{p:0{i}}'
        print(s)
        t += Decimal(s)
        p, q = q, p+q
    print('-' * (n + 2))  
    print(t, '≈ 1 / 89')
    print('=' * (n + 2))
    print()
    print(1 / t)

> couldn't easily find this many digits

I still find 'bc' usefull when needing many digits

  $ echo 'scale=100;1/89'|bc

That's because the infinite sum of F(n) x^n, also known as its generating function, is x/(1 - x - x^2). If you substitute x = 10^-1 you get 10/89, but also

    F(1) 10^-1 + F(2) 10^-2 + F(3) 10^-3 + F(4) 10^4 + F(5) 10^5 + ...

    1 * 0.1 + 1 * 0.01 + 2 * 0.001 + 3 * 0.0001 + 5 * 0.00001 + ...

So it's no surprise that the first digits of 1/89 contain the Fibonacci series as it's just 10/89 shifted by one decimal place.

The pattern breaks down eventually because you overflow a single digit. But you can delay how long until this occurs by substituting in smaller powers of 10. For example if we substitute x = 10^-3 we get 1000/998999 or

    0.0010010020030050080130210340550891442333776109885995881...

I have also used this neat fact to make this golfed loopless/recursionless exact (no floating-point arithmetic) Python implementation of Fibonacci, by substituting in binary powers instead:

    F=lambda n:(4<<n*(3+n))//((4<<2*n)-(2<<n)-1)&~-(2<<n)

If someone is not aware of generating functions it's essentially impossible to understand why this generates Fibonacci.

> So it's no surprise that the first digits of 1/89 contain the Fibonacci series as it's just 10/89 shifted by one decimal place.

>If someone is not aware of generating functions it's essentially impossible to understand why this generates Fibonacci.

Maybe "it's no surprise" is a poor choice of idiom in this context in hindsight.

A one-dimensional cellular automaton using binary addition as its only rule produces the Fibonacci series from the 0 and 1 identities, which is sort of fascinating.

It's interesting, for a while the wisdom was that seeing Fibonacci numbers everywhere was a real stretch and they aren't as common as they're presented in popular culture. Guess the pendulum's swinging back a bit.

I think that's more the golden ratio and Fibonacci spirals (not found in a nautilus shell as is so often claimed). Wikipedia has a section on it: https://en.wikipedia.org/wiki/Golden_ratio#Disputed_observat...

Fibonacci numbers are everywhere because they are the simplest 2-level recurrence relationship. Anywhere things combine and also survive, is a Fibonacci sequence.

> The size of each step in these “infinite staircases” was a ratio of Fibonacci numbers.

On the other hand, it would probably be an interesting exercise to see if there is a pattern in the ratios of various Fibonacci numbers…

As you iterate through the series, the ratio of adjacent numbers approaches the golden ratio, 1.618...

Previously (and posted 64000/89 days ago):

https://news.ycombinator.com/item?id=24929726

Reply on news.ycombinator.com