## Fetch OEIS Sequences

### May 21, 2019

I needed to fetch several sequences from the OEIS the other day. We’ve done that in a previous exercise, in Scheme, but I wanted something I could run from the command line. So I wrote a program.

Your task is to write a program, called from a normal shell command line, that fetches a sequence from OEIS. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Is This Insane?

### May 17, 2019

[ I’ve been very busy at work this week, and don’t have time to write a proper exercise. My apologies. ]

I stumbled across Twitter account ed1conf that included this method of collaborating with another user on an `ed(1)`

session:

Have two ed(1) sessions open concurrently and want to easily transfer lines between them? $ ed -p"a)" a.txt in another shell $ mkfifo fifo $ ed -p"b)" b.txt then a) 15,21 w fifo then b) 13r fifo Can reuse the same fifo bidirectionally. Finally !rm fifo

I’m not sure if that’s brilliant or insane! Actually, I’m not even sure if a whole Twitter account devoted to `ed(1)`

is brilliant or insane.

Perhaps you would like to share with us some other examples of brilliant insanity.

## The Rat Eats The Cheese

### May 14, 2019

A square maze contains cheese wedges on some of its squares:

· · · 🧀 · · · · · · · 🧀 · 🧀 🧀 · · 🧀 · 🧀 · · · · ·

[ Did you know there is a cheese-wedge character in Unicode? I didn’t. The center-dot is & # 183 ;, the cheese is & # 129472 ;, and I had to sprinkle in a few & thinsp ; characters to line things up. And of course to type those I had to add extra spaces, because WordPress is aggressive about turning them into characters. ]

A rat, starting at the lower left-hand corner of the maze, can move only up or right. What is the maximum amount of cheese the rat can eat?

Your task is to write a program to determine how much cheese the rat can eat. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Common Characters

### May 14, 2019

Today’s exercise comes from a coding challenge site:

Given a list of words containing only lower-case letters, return a list of characters that appear in all the words, with multiplicity. For instance, given the words BELLA, LABEL and ROLLER, the characters E, L and L appear in all three words.

Your task is to return a list of characters that appear in all words of an input list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## The Recamán Sequence

### May 10, 2019

I’ve been watching Numberphile again, specifically their episode about the Recamán sequence 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, … A005132, defined as follows:

The Recamán sequence is an integer sequence

RwithR_{0}= 0 andR_{n}=R_{n−1}−nifR_{n}=R_{n−1}−nis positive and not already in the sequence andR_{n−1}+notherwise.

Your task is to write a program that generates the Recamán sequence; use your program to compute *R*_{1000000} (the one-million-and-first element). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Identifying Squares, Revisited

### May 7, 2019

Some algorithms require the ability to rapidly identify numbers such as 36 and 121 that are squares; for instance, in Fermat’s factoring algorithm, and variants derived from it, identifiying squares is the performance bottleneck of the procedure. A naive program computes the integer square root of the target number, squares it, and reports a square if it is equal to the original target:

def isqrt(n): if n < 1: return 0 u, s = n, n+1 while u < s: s = u t = s + n // s u = t // 2 return s

def isSquare(n): # naive s = isqrt(n); return s*s == n

(We are using Python instead of Scheme for this exercise because bit-operators like `&`

are easier to type than functions like `bitwise-and`

.)

This is very slow because the calculation to compute the integer square root takes a long time. In a previous exercise, we looked at a method for reducing the number of integer square roots that need to be computed:

def isSquare(n): # fenderbender m = n & 127 if ((m*0x8bc40d7d) & (m*0xa1e2f5d1) & 0x14020a): return False largeMod = n % (63*25*11*17*19*23*31) m = largeMod % 63 if ((m*0x3d491df7) & (m*0xc824a9f9) & 0x10f14008): return False m = largeMod % 25 if ((m*0x1929fc1b) & (m*0x4c9ea3b2) & 0x51001005): return False m = 0xd10d829a * (largeMod % 31) if (m & (m+0x672a5354) & 0x21025115): return False m = largeMod % 23 if ((m*0x7bd28629) & (m*0xe7180889) & 0xf8300): return False m = largeMod % 19 if ((m*0x1b8bead3) & (m*0x4d75a124) & 0x4280082b): return False m = largeMod % 17 if ((m*0x6736f323) & (m*0x9b1d499) & 0xc0000300): return False m = largeMod % 11 if ((m*0xabf1a3a7) & (m*0x2612bf93) & 0x45854000): return False s = isqrt(n); return s*s == n

This is wicked fast because it computes residue classes based on small primes and quickly identifies numbers that cannot possibly be a square; fenderbender eliminates the expensive square root calculation in 99.92% of cases. But all those magic numbers make the function wicked, as well as wicked fast, and it is easy to make an editing error when copying the function to a new program (you will quickly and accurately guess how I know that).

Your task is to write a program that quickly identifies squares without all the magic numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Three Homework Problems

### May 3, 2019

The end of the school year is approaching in many places, and students are submitting their final homework assignment, so they ask questions on the internet. Here are three questions I have seen recently:

- Write a function
`adjoin-set`

that given a set of integers stored in a linked list in increasing order, and an integer to be inserted in the set, adjoins the integer to the set if it is not already in the set and returns the updated set. - Write a function
`list-index`

that finds the index within a list where a given item occurs, or returns -1 if the item is not in the list. - Write a function
`update-count`

that takes a list of key/count pairs and a key and increments the count of the given key, or adds a new key/count pair with count = 1 if the key is not present in the list.

Your task is to solve the three problems posed above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.