## Searching For Hypotenuses

### October 9, 2015

Hypotenusi?

Your task is to write a program that returns all the numbers less than some limit (think somewhere in the millions or tens of millions) that can be the hypotenuse of a right triangle with integer sides; strive for the minimum possible run time for your program. 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 Iron Bar

### October 6, 2015

Three physicists recently published an article showing that an inert iron bar is capable of making decisions. They attach the bar between two slot machines, repeatedly play one of the machines, pull the bar toward the machine when it winds and push the bar away from the machine when it loses. After enough plays, the iron bar can decide whether to play one machine or the other in hopes of a better payoff. Then they say “The most important implication that we wish to claim is that the proposed scheme will provide a new perspective for understanding the information-processing principles of certain lower forms of life.” The physicists also claim the iron bar can determine the probabilities of winning on both slot machines even though it only plays one. I’m not sure I understand the article, though I will happily agree that an inert iron bar has more intelligence than the spammers that regularly bedevil my blog.

The iron bar recalls an old-time method for calculating the median of a stream; for instance, consider finding the median of a list of a thousand occurrences of the numbers 1 to 100. Initialize the median to the first number in the list. Then, at each subsequent number, increase the median by 1 if the number is higher than the current median and decrease the median by 1 if the number is lower than the current median. At the end of the list, the approximate median calculated in this way ought not to significantly differ from the actual median. This is essentially the same calculation as that of the iron bar.

Your task is to write a program that calculates approximate medians in the manner of an iron bar. 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 Hot Hand

### October 2, 2015

A recent article in the *Wall Street Journal* discusses the “hot hand” paradox. Basketball players especially believe in the hot hand, when making a shot you can suddenly have a hot hand and make several more shots in a row. The *Wall Street Journal* proposes this experiment:

Toss a coin four times. Write down the percentage of heads on the flips coming immediately after heads. Repeat that process one million times. On average, what is that percentage?

The article claims that the correct percentage is 40%, not the 50% that you would expect from an unbiased coin, and that this is proof that the hot hand exists, even from such a random source as coin flips. If you’re interested, you can read the academic article that the *Wall Street Journal* account is based on, or see discussion of it at *Hacker News*.

Your task is to write a program to confirm the 40% figure. 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.

## Making A Palindrome

### September 29, 2015

We have today a small exercise in string manipulation: Given an input string, either return a string containing the same characters but arranged to form a palindrome, or indicate that no such rearrangement is possible.

Your task is to write the program that creates a palindrome. 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.

## Multiply Perfect Numbers

### September 25, 2015

As regular readers know, I greatly enjoy problems at the intersection of recreational mathematics and number theory. Today’s exercise is an example of that.

As was known to the ancient Greeks, perfect numbers such as 6 and 28 are equal to the sum of their aliquot divisors (those divisors less than the number itself); for instance, 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. Mathematicians refer to these as P_{2} numbers the sum of the divisors, including the number itself, is twice the number.

Multiply perfect numbers are numbers such that the sum of their divisors are some multiple of the number; perfect numbers have divisor-sums twice the number, triply perfect numbers P_{3} have divisor-sums thrice, the number, and so on.

Your task is to write a program that finds multiply perfect 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 More Homework Problems

### September 22, 2015

I can tell from my statistics that people like the homework problem exercises, I suppose because they are short and provide simple drill. I can also tell, from reading some of the beginning-programmer message boards, that students seem to be quicker that they used to be to post their homework problems on-line rather than figuring out the solutions themselves, either because they are lazy or because their teachers aren’t providing sufficient help. So today we have three more homework problems:

1) Given a list of integers, return a list in which all the duplicates have been removed. For instance, given the input list [3, 2, 4, 2, 7, 3, 5, 1, 3] return the output list [3, 2, 4, 7, 5, 1].

2) Given two lists of integers, each sorted in ascending order, return a list of the integers common to the two lists; the output list must also be in ascending order. For instance, give the input lists [2, 3, 5, 5, 6, 7, 8, 9] and [1, 2, 4, 5, 5, 7] return the output list [2, 5, 5, 7].

3) Given a positive integer, determine if it is a perfect cube. For instance, the integer 125 is a perfect cube, 5*5*5, but the integer 121 is not.

Your task is to write programs that solve the three homework problems. 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

### September 18, 2015

We have three simple exercises today to help beginning programmers with their homework; all three exercises have appeared on beginning-programmer forums in the last week:

1) Write a recursive function to find the sum of the first

nodd integers. For instance, ifn= 2, the first two odd integers are 1 and 3, and their sum is 4.2) Write a function to count the frequence of characters in a string. For instance, given the string “hello” the function should return counts of 1, 1, 2 and 1 for h, e, l and o.

3) Write functions that encrypt and decrypt messages in a Caesar cipher. Input consists of upper-case letters and spaces; the “key” is an integer giving the number of letters to shift. For instance, the message ATTACK AT DAWN with a shift of 5 is enciphered as FYYFHP FY IFBS.

Your task is to solve the three homework exercises given 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.

## Time Arithmetic

### September 15, 2015

The Standard Prelude provides functions `julian`

and `gregorian`

for performing date arithmetic. In today’s exercise we will extend those functions to provide arithmetic on times as well. The parameters provided to `julian`

will be year, month, day, hour, minute, and second, and the same parameters will be returned by `gregorian`

.

Your task is to write the new `julian`

and `gregorian`

functions. 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.

## Finding The Median

### September 11, 2015

The median of an array is the value in the middle if the array was sorted; if the array has an odd number of items *n*, the median is the (*n*+1)/2’th largest item in the array (which is also the (*n*+1)/2’th smallest item in the array), and if the array has an even number of items *n*, the median is the arithmetic average of the *n*/2’th smallest item in the array and the *n*/2’th largest item in the array. For instance, the median of the array [2,4,5,7,3,6,1] is 4 and the median of the array [5,2,1,6,3,4] is 3.5.

Your task is to write a program that takes an array of 8-bit integers (possibly but not necessarily in sort) and finds the median value in the array; you should find an algorithm that takes linear time and constant space. 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.

## Fermat’s Divisors Challenges

### September 8, 2015

Pierre de Fermat issued these two challenges in 1657: First, find a cube that, when increased by the sum of its aliquot divisors, becomes a square; for instance, 7^{3} + (1 + 7 + 7^{2}) = 20^{3}. Second, find a square that, when increased by the sum of its aliquot divisors, becomes a cube. I would guess that Fermat knew the answer to the first challenge but not the second.

In the days before computers, challenges such as this were frequently issued by one mathematician or group of mathematicians to their competing colleagues; for instance, the French mathematicians might challenge the German mathematicians. Once the challenge was met, the solving group would issue a new challenge to the original challengers. It was considered un-gentlemanly to issue a challenge to which you did not have a solution, though Fermat was probably respected enough to get away with it. Times have changed.

Your task is to write programs that find solutions to the two challenges. 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.