Collatz Conjecture: Follow Up

Well I was completely wrong. I just had such a sure feeling when I woke up Friday morning, my intuition felt so sound. I didn’t even bother running the simple experiments that would have told me I was on the wrong track. I just dove right in to updating my code to display trees of different collatz functions with different values for divisor, multiplier, and offset.

There’s a lesson here, I just know it. Something about looking before you leap . . . nah, that’s not it. If at first you don’t succeed, try, try, again? That doesn’t sound right either. Oh yeah – I got it: Don’t worry, be happy. That’s the moral to every story, right?

Not knowing swift, it went more slowly than expected. Still, I had been wanting a little project that was a good excuse to learn swift on, and this was a perfect one to do it. All in all, there was no real loss. I spent a lot of my time porting an implementation of the Reingold-Tilford layout algorithm from C# to swift. I’ll get my code posted to github soon, and if someone wants to make a swift package for the layout they are welcome to do so (or I may do it myself if I find the time).

Collatz Conjecture: A New Hypothesis

Monday, August 8th, I was introduced to the Collatz conjecture from a link on Daring Fireball. That brief article links to a great video by David Eisenbud that does an excellent job of explaining the mathematical problem and the reason it’s interesting. On Tuesday, August 9th, I again saw a link to it from kottke.org, another blog I regularly read.

For those of you who don’t know, I got my Bachelor of Arts in Mathematics from Reed College in Portland, Oregon. The title of my thesis was “Applications of Counting the Number of Solutions to Linear Equations”, so playing with whole numbers has always been an interest of mine. Since graduation (in 1993) I have largely ignored mathematics, instead focusing on computer software development (I refuse to call it a science or engineering, since to my mind it does not meet the criteria for either of those disciplines).

On Thursday, August 11th, I spent the day at home doing nothing but exploring this problem, and this morning I have some ideas I’d like to share. The explanation below assumes you are familiar with the Collatz conjecture. If not, take time to watch the video linked above, or skim the Wikipedia article.

David Eisenbud really gave me everything I needed to reach this idea – at the very end of the video he asks why 3n + 1, why not 3n - 1?

Starting from this question I asked myself, what is the generalized form of this formula? The original formula as given in the video is:
if n even then n → n/2 if n odd then n → (3 × n) + 1
Lets tweak the definition a little. First lets replace the if n odd with a simple else. Now we have:
if n even then n → n/2 else n → (3 × n) + 1
Second, lets replace the test for evenness with something more generic and more computable. How about using the modulo operator. Then we have:
if n modulo 2 equal 0 then n → n/2 else n → (3 × n) + 1
Now I think we are ready for the generic form. I see three constants that can be replaced by variables. There is the divisor, which I will call d. There is the multiplier, which I will call m. Finally, there is the offset, which I will call o. Substituting those variable names gives us:
if n modulo d equals 0 then n → n/d else n → (m × n) + o
Look at the original formula values and how they relate. In the original formula d=2, m=3, and o=1. and if we look at the simplest sequence, starting from 1, we see 1 → 4 → 2 → 1. From this I have three hypotheses.

  • Hypothesis One: To make a valid Collatz function it must be the case that m + o is a power of d. This is driven by the notion that when you get to one, you want to stay at one, and given that 1 modulo d will never be zero, you need (m × 1) + o to be something that is guaranteed to get right back to one. Clearly m + o has to be a power of d.
  • Hypothesis Two: For the Collatz function to tend towards one, it must be the case that m has a greater absolute value than d. This is just probabilities. Adding an offset after a multiplication means you could end up anywhere (in terms of factors). For it to tend downward you need the divisor to be small compared to your multiplier. You want it to be more likely to hit the divisor than to miss it. A larger divisor is less likely to be a factor of n.
  • Hypothesis Three: For the Collatz function to work, it must be the case that d, m, and o are positive numbers. For d and m this is because of how negative numbers can flip sign on multiplication and division, but addition of the offset is always going the same direction. For o the reason to keep it positive is so that there is no chance that (m × n) + o could ever go negative or to zero.

It has been a long time since I have written a proof, and I don’t know that I’m capable anymore of creating a rigorous proof of my hypotheses, but I plan to spend today trying to write some programs to gather empirical evidence to suggest whether my hypotheses are correct or not, then if reality seems to align with theory, I may take a stab at a proof.

I’m a little concerned that this may end up being equivalent to the halting problem, in which case it won’t be provable, but it seems like this is a simpler case that could be provable on its own.

Thoughts on “The Deployment Age”

I recently read a very interesting post called The Deployment Age by Jerry Neumann. In that post he summarizes the theories of Carlota Perez, drawing from her book Technological Revolutions and Financial Capital: The Dynamics of Bubbles and Golden Ages. He also references As Time Goes By: From the Industrial Revolutions to the Information Revolution by Chris Freeman and Francisco Louçã.

Jerry Neumann goes into a fair bit of detail about these theories, which I will condense even further to this basic idea:

    Technological advancement proceeds in predictable cycles.
    The initial phase is characterized by the emergence of interesting technologies without clear market fit.
    A critical juncture is reached when the right technologies come together to form a “Constellation” or “System”. The combination of technologies is such that together they enable something truly transformative.
    At this point the “Installation” phase begins. I disagree with this word choice, I would call it the Innovation phase. At this point there is huge growth, and the bubble begins. The technology is so new and revolutionary that new applications for it are being discovered all the time.
    Eventually the bubble bursts because of over optimism, over investment, and over reach of all sorts. Although these financial impacts seem to be of central concern to Carlota Perez, for my purposes I find them irrelevant.
    Now begins the phase of “Deployment”, where the revolutionary technology becomes ordinary and commonplace. Again I disagree with this word choice and would call this the Adoption phase. In this phase all businesses adopt the technology and it becomes the new normal.
    Now the cycle begins to repeat, with new disconnected technologies slowly emerging until a new system comes together, and it begins again.

In general I find this theory very compelling, and I think it matches up well with history. If you want to see the many historical examples explored in more detail, I encourage you to go back to Jerry Neumann’s blog post, or to the books I mentioned at the start.

Where this theory gets interesting is when we try to apply it to the modern day, and try to determine how we should conduct business based on this theory.

It is at this point that I think Jerry Neumann loses his way. He takes the long view that we are in the midst of a single revolution, the “Information and Communications Technology Revolution”, which he identifies as starting in 1971. As the “system” of this revolution he identifies semiconductors, integrated circuits, computers, software, computer networking, and mobile phones. He then goes on to postulate that we have passed the bubble, and are now in the “Deployment” phase of the revolution.

I think that it is quite possible that 200 years from now, and with the benefit of hindsight, this is exactly how historians will think about this revolution. From my perspective this is not only a useless point of view, but a dangerous one as well. I say useless because I think it actually gives little helpful insight into understanding the past 45 years, and dangerous because if you accept his postulate that we are in the “Deployment Age” you are likely to miss the technology disruptions that are emerging right now.

My thesis is that we are seeing a series of technology cycles that have started to come so fast and close together that they are actually overlapping now, and so we are not able to complete the adoption phase of one cycle before the next revolution begins.

Here are what I would identify as the major revolutions of the past 45 years, and what I see as the key “system” that triggered each one. In this analysis I am focusing exclusively on the US market. If you take a global view, it is a very different picture, but the US is what I care about for now.

    Business Computers. Although this was called the personal computer revolution, I’m reserving that term for a later evolution. Here I see the revolution starting in August of 1981 with the release of the IBM PC. The key components of this system were the 8088 microprocessor, PC DOS operating system, VisiCalc followed by Lotus 1-2-3, and the amazingly low price point. This revolution was so swift and uptake was so rapid that there was no bubble burst (that I know of). Overnight computers in all businesses were the new normal. Certainly this was preceded by an amazing period of innovation in personal computers, but none had quite created the system that IBM launched.
    Home Computers and the Internet. The Internet existed for a long time, but my belief is that the system to make it truly revolutionary and transformative didn’t emerge until late 1995. Of course I had been on the Internet long before then, sending email and making websites, but I think what took it mainstream was the system of Pentium processors, Windows 95, Internet Explorer, and 28.8k modems. Where previously home computers hadn’t really had a purpose other than for gaming and nerds, they suddenly gained broad mainstream appeal. This bubble grew amazingly quickly and popped quickly too in 2001. It didn’t take long for the adoption phase to kick in, and I think today it is hard to find a business that doesn’t have an internet presence. Sure there are still some sole proprietorships that don’t have a custom domain, but by and large even these are listed on several directory type sites.
    Personal Computers. I think the first computer that truly deserves the name of personal computer is the iPhone. Obviously the iPhone relied heavily on everything that had come before it, but it was also a truly novel and revolutionary device in a way that the existing smart phones to that point had not achieved. The essential components of this system were the ARM processor, iOS, lithium-ion batteries, capacitive touchscreens, the cellular phone network, the Internet, the Apple app store. Arriving in 2007, the iPhone kicked off a revolution whose impacts extend well beyond the US market. Although I agree that we are reaching the end of the innovation phase for Personal Computers, just like the original Business Computer revolution I don’t see a bubble popping, an imminent recession, or similar effect that Carlota Perez might predict. I think we are transitioning smoothly into the adoption phase. I agree wholeheartedly with Jerry Neumann’s assertion that soon there will no longer be a distinction between “Internet/Mobile” taxi companies and “Legacy” taxi companies. All taxis will be hailable by smart phone. All web sites will be optimized for the mobile web. All companies will have apps, or be partnered with app providers in ways that allow them to deliver excellent mobile experiences.

So looking at this list you will undoubtedly note that I have omitted some things. For example the 2008 recession is not mentioned. This is because I do not think the 2008 downturn was the result of a technology bubble. Yes technology was an enabling factor, but I feel the housing mortgage crisis formed mostly from greed, poor ethics, outright fraud, and weak regulatory oversight. This was not a technology bubble popping. These same factors were in evidence in the Savings and Loan Crisis that started in 1986, and I think everyone can agree that the S&L crisis was not a technology bubble either.

Another thing I have omitted is the Desktop Publishing revolution. Starting in early 1985 with the Apple Macintosh, the Apple LaserWriter, and Aldus PageMaker this system was revolutionary in its own right and disruptive to existing industries. I left it off the list because it just seemed to me to have less of an impact than the other revolutions.

One thing that all of these revolutions share is that they were highly disruptive to existing businesses and entire industries. They each created major new opportunities for new businesses. Companies that led one revolution often were not well prepared for the next one. Although each revolution was in a very broad sense an iterative improvement on what came before, each revolution was also in a practical sense completely novel. Each revolution brought about new capabilities that were simply not possible before and transformed society in unexpected ways. Each revolution leveraged infrastructure that had been built by the previous revolution, yet each was built on completely new hardware, software, and had dramatically different interfaces. (The only constant has been the networking protocol, TCP/IP).

It is tempting to believe that the web is now “mature”, and that we are about to enter a period of technology stability. See, for example, Web Design: The First 100 Years a well written article by Maciej Cegłowski comparing the history of the web to the history of aviation. As appealing as this fantasy is, it is simply not the case now, nor is his passionate plea likely to make it so. There are two very disruptive technologies that are already so close to becoming a successful “system” that they seem nearly inevitable. The first I expect to achieve mass adoption is the Intelligent Digital Assistant. I will publish an article explaining what I mean by this in the next few days. The other imminent revolution is Ubiquitous Computing, also known as the Internet of Things, or simply IoT. Some might argue that this is already here, but I think what we have today is but a preview of what a fully realized “system” will look like.

Announcing solr-rpm

I’ve been playing with rpm files at work recently. They are basically standardized Linux installer packages. There is no Apache produced rpm for Apache solr, so I decided to make my own. It’s based on the install script that they provide, but rpm files offer a lot of advantages over install scripts, even if they can’t offer the same level of customizable options. The two biggest advantages of using rpms to install are the ease of upgrading, and the ease of uninstalling.

I’ve made my project available on GitHub at github.com/sagevoice/solr-rpm. It is licensed under the Apache License 2.0, the same as solr. Eventually I hope to have it accepted as an official part of the solr product, but for now I still have a few little bugs to fix.

Please check it out if you’re a Linux or solr enthusiast, or if you want to see a sample of my work.