Algorithms 1: 196/reverse-then-add, and more

I've decided that I'm going to start a series of posts on algorithms. It's been too long for me since I've studied data structures and algorithms, so I'm going to get Knuth's books and work my way through them, posting summaries/reviews/interesting Knuthbits (they're like tidbits, only more Knuthy) here. I will also be going over random algorithms and other things of interest that I've found over the years, because why not?

As an introduction to this series of posts, I'd like to talk about the 196-algorithm. It's also known as the reverse-then-add algorithm. In this post, I will be discussing the algorithm itself, and a few properties I've recently found of the numbers in the algorithm, and then in the next post I will talk about the code for the program I've mentioned below. The essential idea is this:

1) Take any positive number
2) Reverse the digits in the number
3) Add the numbers from 1 and 2 together
4) Repeat

Eventually, following those steps, you will probably get a palindrome number, which is to say a number whose digits are the same written forward as they are backward.

I've always been fascinated by this algorithm because I love words, and palindromes are super-interesting in written form, to me. I also have a strong interest in synesthesia and other neurologically bizarre-but-really-cool conditions. The reason this is relevant is that I wondered the following question: For a number-color synesthete (they see numbers as colors, and often not just numbers, but all "graphemes", or symbols which represent something written out), what do palindromic numbers look like? Do they look like a gradient that goes from one color to another? Is it a series of images that travel from one end of reality to the other? (It's not always specifically colors, but often stark, vivid images that they see.) I may have to ask V.S. Ramachandran this very question, because if anyone would know, it's surely him!

So, I set out to formulate what they might see with a long palindromic number. I also wanted to see if maybe there was a chance that a number-color synesthete would be able to identify whether or not a number was a palindrome faster than someone without synesthesia, and felt a program which let them see the algorithm working would be a pretty good way to test the idea. In-so-doing, I stumbled upon a few really interesting properties of the algorithm and of numbers contained in the 196 series.

The reason 196 is relevant is because it is what's called a Lychrel number; it is, in fact, the first candidate Lychrel number (a number that is proposed to be a Lychrel, but there's no proof for it yet). Wikipedia has a decent page on these, but basically, they are numbers which, when this algorithm is run, do not appear to ever converge to a palindrome. It is conjectured that they never will, but it's never been proven, either, and last I checked, this is one of the unsolved proofs of mathematics.

First, I'll show you a few normal numbers run through the algorithm and you can see them become palindromes. I had some trouble deciding on a format; if you prefer a different one in the future, let me know in the comments. The format is: Starting number: {iterations} = palindrome number

2: {4} = 4
6: {12, 33} = 33
19: {110, 121} = 121 (this one is interesting because the 0 at the end means the resulting reversed number is one fewer digits than the other)
21300: {21612} = 21612

The set notation here is not coincidental; I chose this because the sets of numbers which lead to the palindrome number can have very interesting properties. As mentioned, if we start with 196, it appears that the cardinality (size, to non-mathematicians) of the set is infinite. Here are the first several numbers of the 196 set:

196: {887, 1675, 7436, 13783, 52514, 94039, 187088, 1067869...} = ???

On Friday, October 18th, 2013, I was looking at these numbers and wondering how we might determine any that ARE Lychrel numbers, but that are not strictly in the set above (outside of brute-force). In retrospect, it's incredibly easy, and I believe I found a paper at least implying that it can be done, but haven't been able to read the paper yet to know, so I thought I'd write my own findings here. Furthermore, after a bit more research, there do seem to be other numbers that aren't able to be produced by the following, and are not within the 196 set specifically (879 is an example).

The construction goes as follows: Take any Lychrel number and, starting on one side, add one to the digit. Starting on the other side, subtract one from the digit. You can continue this method to produce more, unique Lychrel's, and interestingly, for the next step in the process, they will produce the next number within the 196 set. This is a fairly trivial proof. You don't even have to do the same operation each time you move to a new digit, as long as you're doing the opposite one to the match on the other side.

This proof relies on the fact that all numbers have an odd or even number of digits; it is a piecemeal algebraic proof.

Suppose you have some number with digits (X₀) (X₁) (X₂)...(X_n)

I put the digits into parentheses because it's annoying to look at numbers this way otherwise. This number has one of two properties. It has either an even number of digits, or an odd number of digits. If n is even (corresponding to an odd number of digits, since we're starting at zero), then:

1) It has a pivot number in the middle around which the number could be a palindrome, e.g. 11911
2) The pivot number cannot be changed and necessarily maintain the values of the result (I won't prove this unless this comes to a paper; it just seems fairly easy to see that if it's less than 4 and you move it to a 5, you're changing the next digit to the left, so it can throw a big wrench in the works)

Conversely, if n is odd, it has no pivot number.

Consider a number of three digits:

1) (X₀) (X₁) (X₂)

This is a palindrome if X₀ = X₂ regardless of what X₁ is (it's the pivot number). Reversed, it is simply (X₂) (X₁) (X₀).

Digits in base 10 must always be strictly less than 10 and greater than or equal to 0. The result of running the algorithm on the above may have to carry values throughout, so I'll include a + C value for that, which then it looks like:

2) (C₀) (X₀ + X₂ + C₁) (X₁ + X₁ + C₀) (X₀ + X₂) 

Due to this, it's easy to see that the resulting number is not necessarily a palindrome, but it's also trivially easy to see how to construct the other numbers. Note that I use C₀ twice in the equation because both times, if there's a carry, the value from (X₀ + X₂) will be the same both times, and strictly never more than one (that's true of any digits carried here, as the highest sum of any numbers in the set is 19, or 9 + 9 + 1 carried from before).

If we add one to the first digit and subtract one from the last digit, or vice versa, as long as the resulting digit is less than 10 or greater than or equal to 0, we've made a valid operation which will result in the same number as above. Here is the starting number using this construction:

3) (X₀ + 1) (X₁) (X₂ - 1)

Now, running the algorithm, we get:

4) (C₀) (X₀ + 1 + X₂ - 1 + C₁) (X₁ + X₁ + C₀) (X₂ - 1 + X₀ + 1)

Simplify by canceling the + 1 - 1 values, and you have the exact same number as before. Obviously, any number which can be constructed this way can have it repeated and you can use higher numbers as well, so long as the restriction that the resulting digit is strictly less than 10 or greater than or equal to 0 is enforced. The reason for that requirement is simple: Otherwise, you could accidentally force a carry where normally there would be none (imagine adding 9 to a 9 at the front of the digit, causing it to go over, and subtracting 9 from the final digit, causing it to go...negative? Or something crazy anyway).

Using the above proof, you can easily show that there are infinitely many Lychrel numbers which do not appear directly in the 196 set, but which, when the 196 algorithm is run on any one of them, will automatically produce the next number in the 196 set, and even further that any number you run this on will always converge to the next number in the starting number's set.

What's interesting about this algorithm is that you can do almost unlimited things with it. You can add one to the first digit, subtract one from the last, add three to the next one, subtract three from the second to last, and so on. You can skip all the way to the numbers around the pivot point if there is one (or to the ones next to each other in the middle) and add one to one of them, and subtract one from the other.

Finally, you can see via the construction that this works for numbers of any length, so long as it's more than one digit. With one digit, it's the pivot number and changing it inherently changes the palindromicity of the successive number, depending on if the changed value is greater than or equal to, or strictly less than 5.

Next time, I'll show some screenshots generated from my program and delve into how I very simply codified the algorithm, and more advanced ways of doing so for high-performance machines that will just run the algorithm over and over without requiring a human to look at it running.

Thanks for reading! Let me know what you think in the comments.

Advanced Tips for Developer Presentations

In a previous post, I wrote about the simpler things that could be done to get better at giving presentations. These were the very most basic tips that could be provided for anyone interested in honing their rhetorical abilities. Today, I'll delve into more specific tips for developers, and this will be in the form of an internet article. I hope you laugh.


Advanced tip #1: Unless it's the entire point of the presentation, do NOT show code.

This one will be met with heated debate, I'm sure. Master Debaters everywhere will attempt to justify their use of code in their presentations because they had done it and got so many compliments on the presentations.

Presenter: Here we see an thread safety issue wherein lies a serious problem. I have a framebroke that fixes it; hurr it is:

Me: what happened? I fell asleep after your ridiculous idea of showing a swatch of code that's totally irrelevant to the topic at hand.

You see, that's the problem. People think, "Ah-ha! If I show off my best code, I'll get hired by some company looking out there, and since I'm presenting, surely that makes me worth a lot of money. Suckers." Well guess what? No one really cares, jerk.

Unless code is the ONLY reason you're presenting, do not show code (and even then, you MUST be careful to explain it in detail, which gets boring). It's too easy to get lost. Provide a link to snippets from Gist if you absolutely have to, but for the love of all that is holy, do not put a bunch of code into your presentation. Hardcore devs will get it at a glance, but most people that go to these talks will just glaze over and fall out of their chair, out of a third story window and DIE. Is that what you want? You want people to die because they went to your presentation? I didn't think so.

Advanced tip #2: Know your presentation partner.

One of the things that's been happening a lot lately is partnered presentations. This is nowhere truer than at Google I/O. They've become obsessed with duo-presentations. One of the potential problems with this particular style is the lack of understanding of your partner.

If your partner jokes a lot, know and try to understand their humor, or at least smile/laugh/nod in appreciativeness when they hit the punch-line. If they don't joke, then make sure they get your sense of humor. If neither of you joke, then what happened to you?

Here's this guy. He has a perfect French accent, is totally hot, and has an amazing sense of humor. He's even named after a type of lettuce, for you vegan folk.

See this other guy - the one who looks like Patton Oswalt?

Lettuce-man finished talking and all the straight women and gay men in the audience had already removed their underwear. And most of the gay women and straight men had also gotten naked. Then Bizarro-Oswalt opened his mouth without realizing the French guy was joking and sucked all the air out of the room. This continued for the entire presentation, and it must surely go down as the best and simultaneously worst presentation in the history of all mankind. Funny, in that saddest-of-all-possible-worlds kind of ways.

Moral of the story? Know your partner's habits and presentation style, and be able to adapt. Don't let your nerves gum up the works.

Just so it's clear, Patton Jr. did do a decent job when it came to the presentation. He stuttered less, and presented better in general than did Romaine-Guy. He just seemed considerably more nervous, which is presumably what threw him off.

Advanced "tip" #3: How to enlarge your presentation in eighty-five easy steps that this homemaker found while doing her laundry! Big pharma doesn't want you to know!

What typically happens when you have a certain amount of time to give a presentation? You invariably fall short your first time. It happens to all of us the first time, trust me on that! Sometimes it happens regularly and our audience complains. Why is it that we always seem to have trouble getting the length we desire when giving presentations? Mary-Janice had these words to say:

"Be creative. Sometimes you have to dig deep and insert extra material. Insert wherever appropriate. It won't always fit at first, but you can slip it in easier by leading into it. Give examples, tell a joke, whatever, I'm just a homemaker."

This material that Mary-Janice recommends doesn't always have to fit perfectly. Sometimes it can be an anecdote, an example, or a longish joke you found that seemed vaguely relevant. Frankly, it can be whatever you want, but if the meat of your presentation isn't quite big enough, you can have a Q and A session toward the end. This is often the easiest way to handle length issues, just like it is in bed.

Advanced tip #4: Questions and answers

Many presentations have questions and answers during the presentation. This is a faux pas. Do not let people raise their hands during your presentation. It can block people behind them from viewing your pretty neckbeard, or prevent someone from watching you play with your hair incessantly like an egomaniacal Valley girl.

There are quite a few problems with having Q and A during the session. For one, it's really, really easy to field a question that is way too in-depth for the level of the presentation. In fact, I try to go out of my way to ask something that is too much work, just to see how the presenter responds. A good presenter will just brush it off as requires too much work to answer right now, but a bad one will either a) not know the answer, get flustered, and fumble the rest of the presentation, or b) know the answer and delve deep in the bowels of Hell.

Another problem is the possibility of causing you to go massively over-time with important information. It is much, much easier to pinch off the Q and A at the end than it is to leave out vital information that might happen to be near the end of your presentation, or attempting to hurry up the final, vital information.

Advanced tip #5: Alpha and omega

The beginning must grab them. The ending must leave them thinking. There can be no argument. What else is important about the beginning? It must contain most of the information you're trying to present. You should try to avoid really weighty information at the end of your presentation. For some, this is difficult, because there's just so much to present. The fact is, though, people have no attention spans these days. They're used to short-term goals that get them answers immediately; if you don't know the answer to a question in five minutes, you don't know it in thirty, right? 

This doesn't mean everything has to come at the beginning. In my experience, it's simply better to put the most important stuff first, and put stuff that's less useful/relevant toward the end. Some may argue this feels like you've lost the thread of your presentation, if they even notice, but at least for the majority of people, you will have given them the most useful stuff right away while they were capable of paying attention.

Advanced tip #6: Understand the time for your presentation, and gauge the material accordingly.

One of the hidden problems with giving conferences of the nature in discussion is having people give presentations near lunch, or near the end of the day. This is actually quite a serious problem. Typically, the only way you're going to keep someone's attention at those times (or in other words times when people are getting hungry) is to have someone who is really, really funny, or at least has good stories.

But what can you do? Know your place in time. If you're near the beginning of the day, you can't be too dense because no one has woken up yet. At the same time, you need to have it be as dense as possible, so that you can help them wake up by the end of it. At the beginning of the day, I tend to rely on little tips and tricks at the very beginning to grab their attention; for a specific example, one time it was 8 AM and I had to give a persuasive speech in college. I decided I'd do it on why women should weight lift: The topic itself is interesting, but not so deep that anyone would have trouble following. And to start it, I flexed my arms big (they were 15 inches around at the time), stretched, and let out a grunt of epic proportions. Then, I quietly said, "Good morning. How are you feeling? I can tell you I'm feeling amazing, all because I lifted this morning."

When you get closer to lunch or toward the end of the day, people can tend to get more annoyed with that type of gimmick. When they're hungry, they just want the info and fast. I typically find out if I can shorten the length of my talk so that people can have more time to eat, but sometimes they won't allow that. Incidentally, that's also a good way to boost the number of people that come to your talks on average; you'll become known as the person who lets people out early after giving a stellar knock-out of a presentation, and eventually you'll be worshiped as the god of rhetoric that you are.

With speeches at the end of the day, there's really not too much you can do except hope. With brain stress the way it works, you can't pack in nearly as much information into a speech as you'd want. It's also hard to do a gimmick or a joke to start off, because people just want to drank. My only advice to you is to make it shorter, if possible, and if that requires you putting an artificial Q and A at the end of a steaming pile of non-information, do it, because people won't ask many questions and then you can more easily justify them leaving that early to your organizers.

Here's a chart demonstrating this: It is loosely a time vs inverse length of attention span chart. This is science, folks.

That's all for now. Go forth and present! 

The Art of Rhetoric, or Tips for Developer Presentations

I consider myself to be a master presenter. I have given presentations to numerous audiences, and have a plethora of different subject areas presented on under my belt. I thought I'd list out a few tips I have for developers who have to give presentations, because I've noticed in the recent past that most of you suck at it, badly. Even people who are famous for giving good presentations are actually pretty awful at the art of rhetoric; I'll avoid names of course, but you'll know who you are based on these tips. ;)

Tip #1: Avoid stuttering, uhs, ahs; in fact, learn how to speak properly, damnit. No one cares if the presentation would change the world if they can't understand the concept because you interjected, "Ahh" ten million times. Stop moving your hands about like a goof, stop tapping the podium, and leave your glasses and  crustache alone. This doesn't take much effort, believe it or not. Just recite the presentation enough times to yourself so that you hammer out these little bits so you remain confident and don't need epic, ridiculous gestures, and ensure that your timing is good so that the extra "uhs" and "ahs" are unnecessary. Speaking of which...

Tip #2: Understand timing. Timing is one of the hardest principles to understand in giving presentations. It's the same way with jokes: If you don't understand where the punchline has to go, the joke will fail. With presentations, you need to correctly divvy up the presentation into the important parts and the details. Details can be important, but in general, they don't need any kind of emphasis or timing effort. The important parts need to have the point slammed home at just the right time. Every presentation should be like a poem or a story about what you're presenting. You need to grab your audience by the short hairs and never let go. This means you are required to break up the presentation into understandable chunks, which leads us to...

Tip #3: Make your presentation digestible. An hour long recitation on the most obscure subject will get you a reputation as a boring, even inconsequential presenter, and will help in making it so you're never invited to present again. Chunking up your presentation into digestible bites with a punchline at the end of each one helps to keep your audience engaged while not overloading them with information that otherwise could cause people to get lost in the details. Make sure that your punchlines work well, too; if they aren't very punchy, you end up just causing it to be a garbled mass of text which you're reading from a sheet of paper or a PowerPoint slide. Hm, I wonder what's next...

Tip #4: Dump PowerPoint for better tools. As Edward Tufte says, PowerPoint is more often used as a tool for the presenter to remember points they have to hit, rather than being helpful to the audience in any way. If you have to rely on a tool like this, then there's something wrong. Here's a surprising thing though: You do not have to know what you're presenting in order to do the presentation well. It becomes problematic if you have to answer questions, but as long as you know the presentation itself well, and as long as you speak with confidence and conviction, you will seem like you know what you're talking about. It's okay to not always know the details of the subject, as long as you present it well. And if you DO have to answer questions at the end, then you damned well better know the subject inside and out. And if PowerPoint is really genuinely useful for you, then at least put your slides online and let people browse them during your presentation; that way, they do not have to follow linearly with you; the person may not have a style of learning which supports linear thinking, so being able to browse back to slides you referenced before can really help. If one of your big problems is nerves, so having a tool like PowerPoint helps you focus, then you might...

Tip #5: Learn to befriend your audience. If everyone in the audience is your friend, then you don't need to feel nervous talking to them. Understand the level they're at and present to that level and that audience, but by all means, make jokes, be friendly, and above all, don't be afraid of mistakes. To err is human, and most audiences will not heckle or do anything like that if you make a mistake. Some people can even manage to seem more endearing when they make mitsakes, usually by coming up with a joke about it on the fly. I wonder if the phrase "on the fly" is derived from a reference to crotch zippers?


I may in the future post more tips as I come up with them, but for now, this should be good enough to start you on your way to better presentations. You don't need good luck; you just need to practice.

The Cost of a Compliment

What is the cost of a compliment? This question occupied my mind as I walked along the Hudson today on my way to work. I thought of it because there was a person dressed quite nicely and I wanted to say something, so I did. I said, "Your clothing looks amazing today." The person perked up immediately and smiled and, at least outwardly, looked much happier than they had been (looked kind of grumpy before that).

And what did that compliment cost me? The way I see it, it didn't really cost me much - some breath, and a tiny fraction of time. What was the benefit? Well, I potentially turned around a person's entire day. I certainly made them much happier - that much was evident from their demeanor before and after the compliment. And because I know that I at least made them happier, that, in turn, makes me happy, so I got something out of it too.

There's a lesson here. Compliments are good. Be sincere and thoughtful, and there's no force on earth which can stop you from going where you want to.

They Win Either Way

I've been thinking about the ridiculous stunt pulled by House Republican'ts a lot lately. To any sane person, we realize they just blew off their own foot with their own gun. But it's deeper than that, much deeper I think, and we need to be very wary of the maneuver.

Here's how it could go down: If half of the government can incense an entire group of people - say, young liberals who just get fed up so easily and quit when they can't win because they're used to short-term rewards - then that half inherently gets more votes next election time. This is because that half has the more curmudgeonly older generation who is largely ignorant of how the world has changed between their time and ours.

And that's what the shutdown works to do. It makes a lot of young, upstart kids feel like the government simply isn't functional and makes them decide to just not vote - that'll show 'em, right?! The problem with this reasoning is that not voting is not helpful in any way; it will just lead to the people who are causing the actual governmental dysfunctionality getting more power, and grinding it to a further halt, and then eventually reversing the progress our nation has made over the past several years.

Instead, young people, I implore you: Don't not vote! Yes, the government feels dysfunctional, but that's mostly because one half of it doesn't have empathy. It is an entire group of psychopaths and political aholes. I'm not saying that every Republican is one of those, but every Republican who toes their party's ridiculous line must surely be! If you look at the leaders, they all are (it's easy to tell if you are familiar with the Psychopath Test or the DSM).

Anyway, I'll climb down off my soapbox now. But if you value your country and what they do for you and for the rest of the world, you can never, in good conscience, vote Republican.

On Problem Solving

Welcome back to our regularly scheduled programming.

Recently, I was rereading an old, old post over at the GoodMath blog (http://scientopia.org/blogs/goodmath/) dealing with the Pumping Lemma and regular languages (http://scientopia.org/blogs/goodmath/2011/05/01/what-if-its-not-regular-pump-it/). I had read the post in the past, but really didn't understand it. I was overwhelmed by the notation and when I get overwhelmed, it's easy for me to skip past important parts. During that reading, it was frustrating and I didn't feel like I was smart enough to know what he was talking about, and that really made me annoyed. But I didn't really feel like there was anything I could do.

Today, I reread the post and even at a glance, I understood it much deeper than ever before. What had changed? There are a few things. This post is not about what changed, but rather how I went about figuring out how to solve problems of a much deeper kind from the normal bugs and defects I fix every day. My hope is that you will come to understand this process of discovery as well, and will benefit by applying it to your everyday lives too.

First off, what I noticed today is that instead of getting frustrated by notation, I simply saw the notation for what it really was: A tool for condensing a larger piece of information into a smaller one. Because of this, I knew that all I really had to do was remember what the notation stood for when reading the rest of the post in order to understand what it all meant; in a sense, I was compiling the meaning for each piece of notation into the new parts of the post and translating it thus.

Secondly, I broke everything down into idea-sized chunks and ensured that I knew the ideas in the order presented before moving on to the next idea. In a way, I view this as a form of ratiocination, or the art of thinking precisely. Always know that at any point in a particular paper or article or book or codebase that you know what exactly is happening at that point in time, and understand the inputs and the outputs at each level. Without that information - without even some trivial piece of context - it's possible that a wrench is thrown into the works, rendering any solution you come up with invalid.

With these two tools combined - ensuring that you know precisely the meaning of the symbols involved and breaking down the problem into smaller parts that you can prove connect to each other at points - I became intelligent today. I've never truly felt that way before. I'd felt the process of discovery as the most beautiful process on earth, but I never really felt like I was actually intelligent, because I didn't know to do the above.

I feel like heretofore, I had been simply taking it for granted that I understood what was happening, and, without trying, would know what the problem was at every point in time. This couldn't be further from the truth. What I realized, ultimately, I think, is that I cannot rely on intuition when trying to solve problems. I should instead always break it down with the steps above, and only then can I really understand and approach a problem intelligently.

I think that's a real issue for others as well. I think people think that an answer that is pulled more or less out of their asses is good enough, because hey, they're always the smartest person in the room anyway, right? That's just not how it works. The people you see and know to be really bright people, they don't get there by not working. The truly intelligent ones work hard to keep being good at what they're good at, and continue learning day by day, pushing themselves for bigger, better things. They're not simply complacent with what they know. And they approach problems in ways that work for them, which is what I really want this post to be about: Approach problems in a way that works for you and resolves to correct solutions, and push yourself. I know I have started doing that, and I'll never look back.