Hofstadter sequence

On the book Gödel, Escher, Bach: an Eternal Golden Braid, on Chapter III page 73 there is a puzzle on a sequence of numbers:

1  3  7  12  18  26  35  45  56  69  …

The puzzle is about characterising the sequence of numbers, that is, coming up with a way to find the next number of the sequence. You may want to try it yourself before reading the rest of the post.

The section of the chapter where this puzzle belongs talks about Recursive Enumerable Sets vs Recursive Sets. The main point of the chapter is that:

There exist formal systems whose set of non-theorems is not the set of theorems of any formal system.

When the author presents the puzzle, he calls for some reflection on the chapter in order to find a formula that describes the sequence.

Trying to solve that, I started observing the differences between subsequent numbers, which in our case is

2  4  5  6  8  9  10  11  13

And then again I looked at the differences of between those numbers

2  1  1  2  1  1  1  2

Now, this sequence rings a bell. The notes in music have differences in tones and semitones:

si (1/2) do (1/1) re (1/1) mi (1/2) fa (1/1) sol (1/1) la (1/1) si

where 1/2 represents a semitone and 1/1 represents a tone.

If we look carefully, we notice that the last sequence of differences that we found is the same one as the one in tones and semitones where the fractions are reversed.

I thought this could be a solution since one of the main topics of the book is the interplay of music and maths. On the other hand, the discussion on the chapter was not used. By looking up the description of the sequence on the web, I found the Hofstadter sequence. Looking at the sequence, I had doubts that I had found an equivalent definition.

Finally, a simple Python script to check whether the two sequences are the same.

Apparently, they are not equivalent. Moreover, we don’t even know whether the Hofstandter sequence is defined for all n.

Nevertheless, the beginning of the sequence presents a funny coincidence and writing the Python code to check the non-equivalence of the two sequences made me appreciate even more the power of generators in Python.

On diversity

“The people of the Settlements select themselves. They select people like themselves. There’s a shared culture, even, to some extent, a shared physical appearance on each Settlement. Earth, on the other hand, is, and through all of history has been, a wild mixture of cultures, all enriching each other, competing with each other, suspicious of each other. Tanayama and many other Earthmen– myself, for instance–consider such a mixture to be a source of strength, and feel that cultural homogeneity on the Settlements weakens them and, in the long run, shortens their potential life span.”

From the book Nemesis by Asimov, page 123.

Floating number operations

Because of how floating numbers work, we can have some surprising results. Can you guess what the next snippet is printing?

from __future__ import print_function

print("The answer is:", int((0.1 * 3 - 0.3) ** -0.1))

Exercise for the reader.

Can you use the fact that:

import numpy as np

v = np.spacing(np.single()) / 2
s = 1.0
s + v   # prints 1.0
s = 0.0
s + v   # prints > 0.0

To make a statement that 1.0 + 1.0 = 2.0 sometimes while 1.0 + 1.0 = 1.0 some other times?

Hint: Use a loop.

If someone requests it, I will post the solution. Credits to Prof. Gallopoulos for this second exercise.

A child can teach an adult three things…

“A child can teach an adult three things: to be happy for no reason, to always be busy with something, and to know how to demand with all his might that which he desires.” – Paulo Coelho

Two volumes of Pushkin [math problem]

Two volumes of Pushkin, the first and the second, are side-by-side on
a bookshelf. The pages of each volume are 2 cm thick, and the cover – front
and back each – is 2 mm. A bookworm has gnawed through (perpendicular to
the pages) from the first page of volume 1 to the last page of volume 2. How
long is the bookworm’s track?

[This topological problem with an incredible answer – 4 mm – is absolutely
impossible for academicians, but some preschoolers handle it with ease.]

Then the author of the problem 13 writes at the end:

I tried to illustrate with this problem the difference in approaches to tasks by mathematicians and physicists, in my invited paper in the journal “Physics – Uspekhi” for the 2000 Christmas jubilee. My success surpassed by far what I intended: the editors, unlike preschoolers, on whom I had been basing my experience, failed to solve the problem, and therefore altered it to match my 4mm answer as follows: instead of from the first page of volume 1 to the last page of volume 2″ they typeset from the last page of volume 1 to the rst page of volume 2. This true story is so implausible that I am including it here: the proof is the editors’ version published by the journal.

If you still can’t figure out why that holds and the “obvious” answer is incorrect, then as hint: the first book is on the left and the second book is on the right.

Psycho Pass (anime)

The quote at the end of the episodes:

“A world where humans’ state of mind and the tendency of personalities can be quantified. While all sorts of inclinations are recorded and policed, these measured numbers used to judge people’s souls are commonly called “Psych-Pass”. This story is fiction. The names of all individuals and organizations that appear in the show are fictitious, and have no relation to those in existence in the real world.”

In the future, there is a Sibyl system. It provides guidance to select a career. It can tell good art from bad art. It can tell whether you are criminal or not. The administration of society is outsourced to that. It follows the ideal of selfless, rational bureaucrat. Society is convinced by that.

Nevertheless, there is room for improvement in the long tail. We see that through the clash of three main different characters:

  • Akane Tsunemori. She is devoted to the system. She believes that stability and happiness are of the uttermost importance and they trump personal freedom.
  • Shinya Kogami. He is an idealist who is guided by his feeling of justice. He acts boldly and he defies the judgemental nature of the society as too superficial.
  • Shogo Makishima: He is the impersonation of the opposition force towards the system. He is labeled as anarchist who deviates from the ideal due to the use of excessive violence.

These three characters have their trajectories met multiple times. They develop a level of understanding between each other in their effort to achieve their goal. The lines between good and bad are thin. The viewer is left with room for his own judgement about good and bad, a decision that may change about the character depending on the context. The characters themselves exhibit seem to oscillate between what is good and what is bad.

To help the viewer to understand the motivation of the acts, sometimes raw quotes from known works are presented. They provide a context of reference that we are familiar to while, still, projecting into the (dystopian?) future that is described in the series.

Some interesting quotes:

When you entrust so much of your everyday life to those electronic devices, the argument that you aren’t a cyborg isn’t very convincing. To you, those portable terminals are already your second brain. Isn’t that right? It can be said that the history of science is a history of the expansion of the human body’s functionality, in other words, the history of man’s cyberization. That’s why it’s a matter of degree.

Solitude? Does that only apply to me? Who isn’t alone in this society? The time when our connection to others was the basis of our selves is long gone. In this world where everyone is watched over by the system and live within the system’s standards, a community isn’t necessary. Everyone just lives in their own cell, and the system tames them by giving them each their own personal serenity.

Isn’t using the net just like using knives for cooking or using paper to write things down? It has nothing to do with good or bad. It’s like, it’s there, so we accept and use it.

It’s not the final judgement of “good” and “evil” that’s important. What matters is that you come to that decision yourself. That you agonize over it and eventually accept it.

I think the only time people really have value is when they act according to their own will.

Everyone is alone. Everyone is empty. People no longer have need of others. You can always find a spare for any replacement. Any relationship can be replaced.

Part of exercise 12.4-1 in CLR

For CLR, exercise 12.4-1 in case you are lazy to do the math.

from __future__ import print_function

def quadratic_probing(k, i, m, h1, c1, c2):
	return (k + h1(k, m) + c1 * i + c2 * i**2) % m

def double_hashing(k, i, m, h1, h2):
	return ((h1(k, m) + i * h2(k, m))) % m

def main():
	m = 11
	k = input("Insert next key (k): ")
	print("Printing the first 10 possible positions for the key...")
	print("quadratic_probing")
	for i in range(10):
		print(quadratic_probing(k, i, m, lambda k, m: k % m, 1, 3))
	print("quadratic_probing")
	for i in range(10):
		print(double_hashing(k, i, m, lambda k, m: k % m, lambda k, m: 1 + (k % (m - 1))))

if __name__ == '__main__':
	main()

The code snippet does not generate the solutions though because it is instructive to see how the table gets different by using different methods of collision resolution.