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.
  • 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 Offline
      J Offline
      jon-nyc
      wrote on 15 Sept 2020, 14:01 last edited by
      #13

      What language is that?

      They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

      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 Offline
          J Offline
          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?

          They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

          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 Offline
              J Offline
              jon-nyc
              wrote on 15 Sept 2020, 17:56 last edited by
              #17

              I use 8086 assembler for such tasks.

              They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

              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 Offline
                    J Offline
                    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.

                    They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

                    K 1 Reply Last reply 15 Sept 2020, 22:06
                    • J jon-nyc
                      15 Sept 2020, 21:44

                      @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.

                      K Offline
                      K Offline
                      Klaus
                      wrote on 15 Sept 2020, 22:06 last edited by Klaus
                      #21

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

                      @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.

                      Can you explain? You mean that the cycle length of Fib mod (2^n) is the same as Fib mod (3*2^(n-1))? That doesn't seem to be true.

                      I uploaded the first 10,000 cycle lengths here, if you want to check this yourself.
                      https://www.heypasteit.com/clip/0IV18W

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

                        No, the cycle length of Fib mod (2^n) = 3*2^(n-1))

                        Check Fmod2, Fmod4, Fmod8, Fmod16 etc for their cycle lengths. You’ll get 3,6,12,24,48 etc. I’m wondering if it holds. I think it will.

                        They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

                        1 Reply Last reply
                        • K Offline
                          K Offline
                          Klaus
                          wrote on 15 Sept 2020, 22:31 last edited by
                          #23

                          Here's a list of pairs where the first number shows the "n" (but only for powers of 2) and the second one the associated cycle length. Maybe I missunderstood something but your conjecture doesn't seem to hold.

                          [(2,6),(4,24),(8,60),(16,24),(32,36),(64,120),(128,420),(256,264),(512,516),(1024,72),(2048,600),(4096,1368),(8192,720)]
                          
                          1 Reply Last reply
                          • J Offline
                            J Offline
                            jon-nyc
                            wrote on 16 Sept 2020, 00:00 last edited by jon-nyc
                            #24

                            But your original list is this one:

                            (left side numbering mine, right side list yours)

                            3e9774ed-e059-4cd4-956f-c8646a08d27b-image.png

                            They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

                            1 Reply Last reply
                            • K Offline
                              K Offline
                              Klaus
                              wrote on 16 Sept 2020, 09:05 last edited by
                              #25

                              Ah, looks like an "off by two" error somewhere. Hmm....

                              1 Reply Last reply
                              • K Offline
                                K Offline
                                Klaus
                                wrote on 16 Sept 2020, 09:11 last edited by Klaus
                                #26

                                Turned out to be two "off by 1" errors that have to do with indices starting at 0 and not 1.

                                What about this result?

                                [(2,3),(4,6),(8,12),(16,24),(32,48),(64,96),(128,192),(256,384),(512,768),(1024,1536),(2048,3072),(4096,6144),(8192,12288)]
                                
                                1 Reply Last reply
                                • K Offline
                                  K Offline
                                  Klaus
                                  wrote on 16 Sept 2020, 09:15 last edited by Klaus
                                  #27

                                  It looks like linear relations between the cycle length happen quite frequently. This is a scatter plot of the cycle lengths I computed above (haven't used R in a while - fun for plotting data!). Observe all the dotted lines. The points you identified are on one of those lines. Also interesting to see a few outliers.

                                  440d6f5b-c0a6-4d2d-b301-7d3d66c1fafd-image.png

                                  I have marked the points you are interested in in red. You see that there are way more points on that line.

                                  1 Reply Last reply
                                  • J Offline
                                    J Offline
                                    jon-nyc
                                    wrote on 16 Sept 2020, 10:45 last edited by
                                    #28

                                    Interesting.

                                    So it turns out Fibonacci cycle lengths a thing people study. They’re called Pisano numbers and understanding them is really about understanding Pisano numbers for prime powers.

                                    A neat property is that if n and m are coprime then period(mn) is least common multiple of period(n) and period(m).

                                    They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

                                    1 Reply Last reply
                                    • J Offline
                                      J Offline
                                      jon-nyc
                                      wrote on 16 Sept 2020, 10:48 last edited by
                                      #29

                                      Wait a minute, is that really your graph up there? This is from Wiki

                                      396851CA-71EE-4E8B-AB14-42964B4121AC.png

                                      They’ll end up, after a lot of drama, with the same formula they use every time they have a trifecta: take away health care and food assistance from low income families and use the money to fund tax cuts for their donors.

                                      1 Reply Last reply
                                      • K Offline
                                        K Offline
                                        Klaus
                                        wrote on 16 Sept 2020, 10:59 last edited by Klaus
                                        #30

                                        Yes, it's my graph. I haven't seen the WIki graph yet, but it shows the same data, so of course it's similar. It's an interesting coincidence that they also cut off at 10,000.

                                        1 Reply Last reply
                                        • K Offline
                                          K Offline
                                          Klaus
                                          wrote on 16 Sept 2020, 11:37 last edited by
                                          #31

                                          Just for fun, here's the continuation of the dataset for cycle lengths up to 20000.

                                          1549ea7c-ea85-4eca-aea0-3b73c980f9aa-image.png

                                          1 Reply Last reply
                                          Reply
                                          • Reply as topic
                                          Log in to reply
                                          • Oldest to Newest
                                          • Newest to Oldest
                                          • Most Votes

                                          21/31

                                          15 Sept 2020, 22:06


                                          • Login

                                          • Don't have an account? Register

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