Like Tree2Likes
  • 2 Post By Sebastiani

A generalized algorithm for Collatz-like "hailstone" sequences

This is a discussion on A generalized algorithm for Collatz-like "hailstone" sequences within the General Discussions forums, part of the Community Boards category; I've always been fascinated with Collatz sequences . Well today, while thinking about multiplicative groups , I realized that under ...

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708

    Lightbulb A generalized algorithm for Collatz-like "hailstone" sequences

    I've always been fascinated with Collatz sequences. Well today, while thinking about multiplicative groups, I realized that under certain constraints they too could be used to generate similar "hailstone" sequences. Moreover, it *should* be fairly easy to prove that all such sequences eventually reach one and that no intervening sequences are cyclic. Unfortunately, my forte is definitely *not* mathematical proofs, so I'll just have to leave it up to someone else to work that out! Another interesting property of the generator is that it can be used to calculate primitive roots - not efficiently, mind you, but it does at least demonstrate the connection with multiplicative groups...

    Anyway, here's a basic overview of how it works:
    (1) Pick a natural number, and call it the "divisor".
    (2) Pick another natural number coprime to divisor and call it "counter".
    (3) Set "accumulator" to one.
    (4) Add the counter to the accumulator.
    (5) Divide accumulator by divisor until the two are coprime.
    (6) If the accumulator equals one, increment the counter until it is coprime with the divisor.
    (7) Return the value of the accumulator.
    (8) Go to step (4) to obtain next value in the sequence.

    See below for a link to an implementation of the generator and demo program. Note that for sake of clarity, initialization of the generator and incrementation of the counter is done in a very simple fashion. If desired, these could be modified (using GCD calculations) to increase the overall period of the generator (besides allowing it to reveal more primitive roots); the important thing to remember is that the divisor and counter must always be coprime...

    Cheers!
    Last edited by Sebastiani; 10-24-2013 at 10:32 PM. Reason: Wikified
    SirPrattlepod and TheBigH like this.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Whoops - there was an error of premature calculation in the demo program affecting primitive root identification.

    Fixed.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Having given it some thought, I've decided to implement a GCD-based incrementation strategy. After all - what's the fun of seeing primitive roots if you can't see all of them? Plus, this way the generator gets to cycle through the fullest range of numbers possible.

    Cheers!
    Attached Files Attached Files
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 06-02-2011, 03:00 PM
  2. Replies: 0
    Last Post: 03-09-2009, 11:15 PM
  3. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 08:25 AM
  4. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 07:59 AM
  5. "color degradation" algorithm code
    By madsmile in forum C++ Programming
    Replies: 0
    Last Post: 03-22-2002, 08:42 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21