A Suspicious Series

Does the series

converge?

At first, you may be reminded of the harmonic series that diverges, because of the divisor following the same progression, and may conclude that this suspicious series diverges because its terms do not go to zero fast enough. But we need to investigate how the part behaves.

Fibonacci rabbits as a rewrite system

In my discrete mathematics class, I often use the Fibonacci rabbits example, here to show how to resolve a recurrence, there a variant where some rabbits go away, here again for rewrite systems.

What are rewrite systems? Not unlike context-free grammars, they provide rules generate “words” in a “language”. Turns out the Fibonacci rabbit population problem is super-easy to model as a rewrite system.

Lissajous Curves.

Many of this blog’s entries seem … random and unconnected. This is another one, despite it being quite connected to some research I’m presently conducting. This week, we discuss Lissajous curves.

We’ll see the formulas, and how to select “nice” parameters.

Stirling’s series

Last week, we had a look at how g++ handles tail-recursion. Turns out it does a great job. One of the example used for testing the compiler was the factorial function, .

We haven’t pointed it out, but the factorial function in last week’s example computed the factorial modulo the machine-size (unsigned) integer. But what if we want to have the best possible estimation?

Pruning Collatz, somewhatz

I’ve visited the Collatz conjecture a couple of times before. I’ve played with the problem a bit more to understand how attractors work in the Collatz problem.

So what is the Collatz conjecture? The conjecture is that the function

Always reaches one. But the catch is, nobody actually figured out how to prove this. It seems to be true, since for all the ever tried the function eventually reached 1. While it is very difficult to show that it reaches 1 every time, it’s been observed that there are chains, let’s call them attractors, such what when you reach a number within that chain, you go quickly to 1. One special case is the powers-of-two attractor: whenever you reach a power of two, it’s a downward spiral to 1. Can we somehow use this to speed up tests?

The Zero Frequency Problem (Part I)

In many occasions, we have to estimate a probability distribution from observations because we do not know the probability and we do not have enough a priori knowledge to infer it. An example is text analysis. We may want to know the probability distribution of letters conditional to the few preceding letters. Say, what is the probability of having ‘a’ after ‘prob’? To know the probability, we start by estimating frequencies using a large set of observations—say, the whole Project Gutenberg ASCII-coded English corpus. So we scan the corpus, count frequencies, and observe that, despite the size of the corpus, some letter combinations weren’t observed. Should the corresponding probability be zero?

Jouette’s Attractor

I have been reading a lot of mathematical recreation books of late. Some in English, some in French, with the double goal of amusing myself and of finding good exercises for my students. In [1], we find the following procedure:

Take any number, digits long, make this number . Make the number made of the sorted (decreasing order) digits of , and , the number made of the sorted (increasing order) digits of . Subtract both to get : . Repeat until you find a cycle (i.e., the computation yields a number that have been seen before).

Jouette states that for 2 digits, the cycle always starts with 9, for 3 digits, it starts with 495, for 4 digits, 6174, and for 5 digits, 82962. For 2, 3, and 4 digits, he’s mostly right, except that the procedure can also reach zero (take 121 for example: 211-112=99, 99-99=0). For 5 digits, however, he’s really wrong.

Take That, Fermat!

You’ve certainly heard of Fermat’s last theorem stating that

has no integer solutions for . Well, guess what:

.

Take that, Fermat!

Suggested Reading: The Simpsons and their Mathematical Secrets

Simon Singh — The Simpsons and Their Mathematical Secrets — Bloomsbury, 2013, 255 pp. ISBN 978-1-62040-277-1

(Buy at Amazon.com)

Using, as an excuse, the fact that The Simpsons (and their sister series Futurama) use mathematics as part of the plot or as a “frame freeze gag” (a gag that is so short that unless you look at the show frame by frame, you might miss it), Singh (which you may remember from books such as The Code Book and Fermat’s Last Theorem) brings us along a mathematical walk, presenting us the mathematically-inclined writers of the shows. But, as I said, The Simpsons are merely a convenient excuse to introduce mathematics and theorems: if you expect to learn a lot about The Simpsons themselves, you’d be disappointed. The book is about the mathematics and the writers.

However, it’s an interesting read: prime numbers, , combinatorics, computation and algorithmics. I especially liked the Futurama Theorem that describes how, using a mind-swapping machine that can swap minds between two same individuals once only, we can un-scramble minds and bodies and put every one in their rightful body (not a new plot device, Stargate did it first, in s02e18).

Suggested Reading: How Mathematics Happened: The First 50000 Years

Peter S. Rudman — How Mathematics Happened: The First 50000 Years — Prometheus Books, 2006, 314 pp. ISBN 978-1-59102-477-4

(Buy at Amazon.com)

What first got me interested in this book is the “50000 years” part. I was preparing lectures notes for my course on discrete mathematics and I wanted my students to have an idea of what prehistoric maths might have been, say, 20000 years ago. Unfortunately, you wont learn much about this in this book

The book does hint about what mathematics might have been in hunter-gatherer times, and how it might have affected later developments. But that lasts for about a chapter or so, and the remainder is devoted to historical mathematics: Ancient Egyptian, Babylonian, and Classical Greek. All kinds of numerical algorithms are covered, presented in great detail, making the book more technical than historical. Some part are speculative as the historical record is incomplete at best, but it is speculative in the best way possible, with every assumption backed by an actual historical observation.