## Triple Or Add Five

### July 27, 2018

By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite set of numbers can be generated. For instance, starting from 1, you can triple to get 3, then add five to get 8, and finally triple to get 24, so 24 is reachable. On the other hand, 15 is not reachable, as a little thought will show.

Your task is to write a program that determines if a number *n* is reachable by tripling or adding five, and if the number is reachable to give the sequence of operations by which it can be reached. 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.

## Fenwick Trees

### July 20, 2018

There are some algorithms in coding theory where cumulative frequency tables must be maintained. This requires two tasks to be performed on an array of integers:

1) Calculate the cumulative sum of the first *n* elements of the array.

2) Modify the value of an element of the array.

One approach is to maintain an array of the elements, so that an element can be modified in O(1) time but calculating the cumulative sum requires O(*n*)time. Another approach is maintain an array of the cumulative sumes, so that a cumulative sum can be calculated in O(1) time but modifying a single element of the array takes O(*n*) time.

A Fenwick tree performs both operations in O(log *n*) time. The tree is normally embedded in a 1-based array, with the children of node *i* at nodes 2*i* and 2*i* + 1. Each element with index *i* a power of 2 contains the sum of the first *i* elements. Each element with index *i* a sum of two powers of 2 contains the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, found by clearing the least-significant bit in the index. Wikipedia has a good description of Fenwick trees.

For example, to find the sum of the first 11_{10} = 1011_{2} items in the array, note that 11 has three bits set, so add elements 1000_{2}, 1010_{2}, and 1011_{2}. To modify the 11th element, modify 1011_{2}, 1100_{2}, 10000_{2}, and all higher powers of 2 up to the size of the array.

Your task is to implement Fenwick trees. 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.

## Top Heavy Perfect Powers

### July 17, 2018

Over at his blog, Ken is investigating top-heavy perfect powers to investigate increasing the breadth of the Cunningham project. He makes a list of 2413 perfect powers *b ^{n}* with

*b*≤

*n*in increasing order, up to a googol, omitting bases that are themselves perfect powers (for instance, 4

^{n}, 8

^{n}or 9

^{n}).

Your task is to make a list of the 2413 top-heavy perfect powers less than a googol. 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.

## Data Laundry, Again

### July 13, 2018

Data laundry is the act of cleaning data, as when it arrives in one format and must be translated to another, or when external data must be checked for validity. We looked at data laundry in a previous exercise. We return to it today because I have been doing data laundry all week, handling data from a new vendor. Today’s task is similar to one I have been doing this week; convert the input to the output shown below, changing all appearances of the string ABCDE to an incrementally-numbered string with a prefix:

ABCDE This is some text. This is more text. ABCDE, ABCDE. ABCDE And this is [ABCDE] still more text.

X1 This is some text. This is more text. X2, X3. X4 And this is [X5] still more text.

Your task is to write a program to perform the data laundry shown 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.

## 8/10 Palindromes

### July 10, 2018

Sometimes I enjoy browsing oeis.org (I might be a little bit weird). While browsing the other day, I found A029804, the sequence of numbers that are palindromes in both decimal and octal.

Your task is to write a program that writes the sequence of numbers that are palindromes in both decimal and octal. 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.

## Top Five Test Scores

### July 3, 2018

We frequently base exercises on student assignments. Today we have something for the teachers:

A student’s final store is the average of the five best test scores the student achieved during the school term. Given a list of student name/score pairs, determine the final score for each student. You may assume each student has at least five scores.

Your task is to write a program to determine each student’s final score, as described 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.

## Length

### June 29, 2018

Recently, at a beginning programmer’s forum, I saw a user asking about the function `length`

that finds the length of a list. He gave a simple version of `length`

, then used it find the lengths of two lists and determine which was shorter. He correctly realized that calculating the full lengths of both lists is inefficient if one list is much longer than the other, and he asked if there was a way to run through the lists simultaneously, stopping as soon as it is known which list is shorter.

Your task is to write `length`

and a function to determine which of two lists is shorter; your solution must use recursion. 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.

## Next Identical Popcount, Revisited

### June 26, 2018

In a comment on the prior exercise, Richard A. O’Keefe said:

This is just the “next k-subset of 1..n” problem. It is possible to go fairly directly from one popc-k integer to the next. Let the least significant 1 bit be at offset p. If bit(p+1) is 0, set it to 1 and clear bit(p). If bit(p+1) is 1, clear bit(p), set bit(0), advance bits (p+1..msb) to the next integer with k-1 bits.

The algorithm at the top of the page is spectacularly inefficient. Consider the case of 32-bit integers, bit(30) is on, and all the others are off. (k=1) The (next n) algorithm loops about 2**30 times.

Dr. O’Keefe is correct. My solution isn’t very good. In fact, it’s abominable.

Your task is to write a program to solve the next-identical-popcount problem in the manner Professor O’Keefe suggests. 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.

## Next Identical Popcount

### June 22, 2018

Today’s exercise is an interview question:

The binary weight of a positive integer is the number of 1-bits in its binary representation. For example, the decimal number 7, which is 111 in binary, has a binary weight of 3. The smallest integer greater than 7 that has the same binary weight as 7 is 11, which is 1011 in binary.

Your task is to write a program that, given a positive integer, finds the next larger integer that has the same binary weight. 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.

## Fibonacci Hash

### June 19, 2018

Hash tables are ubiquitous in computing, and we’ve both used and implemented hash tables on several occasions; there is even a hash table implementation in the Standard Prelude. Most hash tables nowadays use the elements of an array as the heads of linked lists that store key/value pairs, so to access (store or fetch) a particular element the procedure is to calculate the hash value based on the key, convert the hash value to an index into the array, and scan down the appropriate linked list until you find the desired item.

The usual way to convert the hash value to an array index is to choose the array size prime, then take the hash value modulo the prime. That can be slow, because the modulo operation requires a division, which is always slow compared to other primitive arithmetic operations. Fibonacci hash replaces the division with multiplication and a shift, which often takes less than half the time.

Fibonacci hash works like this: Choose *b* the number of bits in an integer, usually either 32 or 64. Then compute 2^{b} ÷ φ, where φ = (1 + √5) ÷ 2 ≈ 1.618; for *b* = 32 this quantity is 2654435769 and for *b* = 64 this quantity is 11400714819323198485. Then to compute the array index, multiply the hash value by the quantity shown above, allowing it to wrap around if the product exceeds the integer bounds, and shift right, leaving as many bits as desired. The array size should be a power of 2. Here is an implementation in C:

unsigned long long fibhash(unsigned long long h) { return (h * 11400714819323198485ull) >> 54 }

This returns a ten-bit value (since the 64 bit product is shifted right 54 bits) from 0 inclusive to 1024 exclusive, which is used as the index to the array. If you need more bits, just change the size of the shift.

Malte Skarupke describes the theory behind Fibonacci hash, which you should look at, because it includes some neat math; be sure not to miss the linked video from Vi Hart.

Your task is to implement Fibonacci hash in the language of your choice. 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.