Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
Skins
  • Light
  • Cerulean
  • Cosmo
  • Flatly
  • Journal
  • Litera
  • Lumen
  • Lux
  • Materia
  • Minty
  • Morph
  • Pulse
  • Sandstone
  • Simplex
  • Sketchy
  • Spacelab
  • United
  • Yeti
  • Zephyr
  • Dark
  • Cyborg
  • Darkly
  • Quartz
  • Slate
  • Solar
  • Superhero
  • Vapor

  • Default (No Skin)
  • No Skin
Collapse

The New Coffee Room

  1. TNCR
  2. General Discussion
  3. Puzzle time - the Fibonacci numbers

Puzzle time - the Fibonacci numbers

Scheduled Pinned Locked Moved General Discussion
31 Posts 4 Posters 310 Views
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • J Online
    J Online
    jon-nyc
    wrote on 14 Sept 2020, 12:26 last edited by
    #1

    Show that every positive integer has a multiple that is a Fibonacci number.

    Only non-witches get due process.

    • Cotton Mather, Salem Massachusetts, 1692
    1 Reply Last reply
    • K Offline
      K Offline
      Klaus
      wrote on 14 Sept 2020, 13:03 last edited by Klaus
      #2

      Hm, interesting.

      I was browsing the Wikipedia article on Fibonacci numbers to look up some of the identities given there, and I believe I regrettatably already stumbled upon a major part of the solution.

      ||667eecb8-d29f-4081-aa22-9ae23d0cc1c9-image.png

      The snippet above illustrates the situation for prime numbers, but any number is a product of prime numbers, so presumably it can be made to work for non-prime numbers (but the details are not yet clear to me).
      ||

      But the Wikipedia article leaves out the derivation/proof. Slackers.

      1 Reply Last reply
      • K Offline
        K Offline
        Klaus
        wrote on 14 Sept 2020, 13:19 last edited by
        #3

        Actually, there's a trivial solution, too : The first Fibonacci number is 0. 0 is a multiple of any number.

        1 Reply Last reply
        • J Online
          J Online
          jon-nyc
          wrote on 15 Sept 2020, 02:52 last edited by
          #4

          Haha. Let’s agree to go for the non-trivial solution.

          Only non-witches get due process.

          • Cotton Mather, Salem Massachusetts, 1692
          1 Reply Last reply
          • K Offline
            K Offline
            Klaus
            wrote on 15 Sept 2020, 08:03 last edited by
            #5

            Do you (already) know the solution? Does it involve advanced math? Even the partial statement that your proposition holds for prime numbers isn't exactly trivial to show.

            1 Reply Last reply
            • J Online
              J Online
              jon-nyc
              wrote on 15 Sept 2020, 10:43 last edited by
              #6

              I know a very elegant solution that requires no advanced math.

              Hint?

              Only non-witches get due process.

              • Cotton Mather, Salem Massachusetts, 1692
              1 Reply Last reply
              • J Online
                J Online
                jon-nyc
                wrote on 15 Sept 2020, 10:46 last edited by
                #7

                Explore the Fibonacci numbers mod n for a few n

                Only non-witches get due process.

                • Cotton Mather, Salem Massachusetts, 1692
                1 Reply Last reply
                • K Offline
                  K Offline
                  Klaus
                  wrote on 15 Sept 2020, 11:18 last edited by
                  #8

                  Well, the "mod n" sequences seem to loop. In particular, they always seem to come back to 0. Which means that those "0" points can be divided by n.

                  So if "zero(n)" is the index of the first fibonacci number (different from 0) where Fib(zero(n)) mod n = 0, then n divides the zero(n)-th Fibonacci number.

                  However, it's not so clear why the "mod n" sequences have that looping structure.

                  1 Reply Last reply
                  • J Online
                    J Online
                    jon-nyc
                    wrote on 15 Sept 2020, 11:27 last edited by jon-nyc
                    #9

                    You’re on track, and one small insight from a solution.

                    Only non-witches get due process.

                    • Cotton Mather, Salem Massachusetts, 1692
                    1 Reply Last reply
                    • K Offline
                      K Offline
                      Klaus
                      wrote on 15 Sept 2020, 11:34 last edited by
                      #10

                      I think the proof of looping can be seen from the congruence property of modular arithmetic. In particular, "modulo" is a congruence with respect to Fibonacci numbers:

                      Fib(n) mod m = (Fib(n-1) mod m) + (Fib(n-2) mod m) (for n >= 2)

                      Since there are only about m^2 possible pairs of numbers in the "mod n" ring, and Fib(n) mod m only depends on the pair of previous numbers (mod m), it follows that the sequence must necessarily loop.

                      1 Reply Last reply
                      • J Online
                        J Online
                        jon-nyc
                        wrote on 15 Sept 2020, 11:36 last edited by
                        #11

                        That’s right. The process is totally reversible so the 0,1,1 must eventually repeat.

                        Only non-witches get due process.

                        • Cotton Mather, Salem Massachusetts, 1692
                        1 Reply Last reply
                        • K Offline
                          K Offline
                          Klaus
                          wrote on 15 Sept 2020, 13:36 last edited by Klaus
                          #12

                          I did a tiny bit of programming, and I think it's a nice programming exercise to come up with an elegant way to compute the cycle length of "Fib mod n" sequences.

                          Here's a 4-liner I came up with.

                          fibsmod n = map ((`mod` n) . fst) $ iterate (\(a,b) -> (b,a+b)) (0,1)
                          pairIndex a b (x:y:ys) m = if (a == x) && (b == y) then m else pairIndex a b (y:ys) (m+1)
                          p (x:y:ys) = pairIndex x y ys 2
                          take 100 $ map (p . fibsmod) [2..]
                          

                          It computes the first 100 cycle length:

                          [3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60,16,30,48,24,100,84,72,48,14,120,30,48,40,36,80,24,76,18,56,60,40,48,88,30,120,48,32,24,112,300,72,84,108,72,20,48,72,42,58,120,60,30,48,96,140,120,136,36,48,240,70,24,148,228,200,18,80,168,78,120,216,120,168,48,180,264,56,60,44,120,112,48,120,96,180,48,196,336,120,300,50]
                          
                          1 Reply Last reply
                          • J Online
                            J Online
                            jon-nyc
                            wrote on 15 Sept 2020, 14:01 last edited by
                            #13

                            What language is that?

                            Only non-witches get due process.

                            • Cotton Mather, Salem Massachusetts, 1692
                            K 1 Reply Last reply 15 Sept 2020, 17:22
                            • H Offline
                              H Offline
                              Horace
                              wrote on 15 Sept 2020, 14:59 last edited by
                              #14

                              It's a computer language. Computer programmers use computer languages to "talk" to computers and tell them what to do!

                              Education is extremely important.

                              1 Reply Last reply
                              • J Online
                                J Online
                                jon-nyc
                                wrote on 15 Sept 2020, 15:17 last edited by
                                #15

                                Interesting observation:

                                Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?

                                Only non-witches get due process.

                                • Cotton Mather, Salem Massachusetts, 1692
                                J 1 Reply Last reply 15 Sept 2020, 21:44
                                • J jon-nyc
                                  15 Sept 2020, 14:01

                                  What language is that?

                                  K Offline
                                  K Offline
                                  Klaus
                                  wrote on 15 Sept 2020, 17:22 last edited by Klaus
                                  #16

                                  @jon-nyc said in Puzzle time - the Fibonacci numbers:

                                  What language is that?

                                  Haskell.

                                  I bet if you do the same thing in your favorite language you need at least twice as much code, and the code will be less extensible. (throws gauntlet)

                                  1 Reply Last reply
                                  • J Online
                                    J Online
                                    jon-nyc
                                    wrote on 15 Sept 2020, 17:56 last edited by
                                    #17

                                    I use 8086 assembler for such tasks.

                                    Only non-witches get due process.

                                    • Cotton Mather, Salem Massachusetts, 1692
                                    1 Reply Last reply
                                    • D Offline
                                      D Offline
                                      Doctor Phibes
                                      wrote on 15 Sept 2020, 19:09 last edited by
                                      #18

                                      Are you two about to have a 'my dick is smaller' contest?

                                      I was only joking

                                      K 1 Reply Last reply 15 Sept 2020, 19:18
                                      • D Doctor Phibes
                                        15 Sept 2020, 19:09

                                        Are you two about to have a 'my dick is smaller' contest?

                                        K Offline
                                        K Offline
                                        Klaus
                                        wrote on 15 Sept 2020, 19:18 last edited by
                                        #19

                                        @Doctor-Phibes Did you know that dick sizes have a Fibonacci distribution? It's a distribution with a very long tail...

                                        <insert @George-K rimshot image macro here>

                                        1 Reply Last reply
                                        • J jon-nyc
                                          15 Sept 2020, 15:17

                                          Interesting observation:

                                          Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?

                                          J Online
                                          J Online
                                          jon-nyc
                                          wrote on 15 Sept 2020, 21:44 last edited by
                                          #20

                                          @jon-nyc said in Puzzle time - the Fibonacci numbers:

                                          Interesting observation:

                                          Cycle lengths 2^n = 3*2^(n-1) at least within the first 100. Does that continue?

                                          bump for Klaus and his little 4 line program.

                                          Only non-witches get due process.

                                          • Cotton Mather, Salem Massachusetts, 1692
                                          K 1 Reply Last reply 15 Sept 2020, 22:06
                                          Reply
                                          • Reply as topic
                                          Log in to reply
                                          • Oldest to Newest
                                          • Newest to Oldest
                                          • Most Votes

                                          9/31

                                          15 Sept 2020, 11:27

                                          22 unread

                                          • Login

                                          • Don't have an account? Register

                                          • Login or register to search.
                                          9 out of 31
                                          • First post
                                            9/31
                                            Last post
                                          0
                                          • Categories
                                          • Recent
                                          • Tags
                                          • Popular
                                          • Users
                                          • Groups