## Aronson’s Sequence

### June 22, 2021

Aronson’s sequence 1, 4, 11, 16, 24, 29, 33, 35, 39, … (A005224) is an infinite self-referential sequence defined as:

T is the first, fourth, eleventh, … letter in this sentence.

Your task is to write a program that generates Aronson’s sequence and use it to compute the first hundred members of the sequence. 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.

## Cardinal And Ordinal Numbers

### June 15, 2021

Cardinal numbers are those used for counting; spelled in letters, they are one, two, three, four, and so on.

Ordinal numbers are those used for ranking: spelled in letters, they are first, second, third, fourth, and so on.

Your task is to write a program that takes a number and returns the spelled-out cardinal and ordinal forms of that number. 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.

## Approximate Squaring

### June 8, 2021

Lagarias and Sloane study the “approximate squaring” map *f*(*x*) = *x*⌈*x*⌉ and its behavior when iterated in this paper.

Consider the fraction *x* = *n* / *d* when *n* > *d* > 1; let’s take 8/7 as an example. In the first step, the smallest integer greater than 8/7 (the “ceiling”) is 2, and 8/7 × 2 = 16/7. In the second step, the ceiling of 16/7 is 3, so we have 16/7 × 3 = 48/7. And in the third step, the ceiling of 48/7 is 7, so we have 48/7 × 7 = 48. Now the denominator is 1 and the result is an integer, so iteration stops, and we say that 8/7 goes to 48 in 3 steps.

Study shows the iteration is chaotic; sometimes the iteration stops in just a few steps, as in 8/7, sometimes it takes longer (6/5 goes to a number with 57735 digits in 18 steps), and sometimes it’s just ridiculous (200/199 goes to a number with 10^{435} digits). It is conjectured but not proven that iterated approximate squaring always terminates in an integer.

Your task is to write a program that iterates approximate squaring. 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.

## 100011322432435545

### May 18, 2021

I had an email from a reader who found my factoring program on Stack Overflow:

Python 2.7.13 (default, Mar 13 2017, 20:56:15) [GCC 5.4.0] on cygwin Type "help", "copyright", "credits" or "license" for more information. >>> def isPrime(n, k=5): # miller-rabin ... from random import randint ... if n < 2: return False ... for p in [2,3,5,7,11,13,17,19,23,29]: ... if n % p == 0: return n == p ... s, d = 0, n-1 ... while d % 2 == 0: ... s, d = s+1, d/2 ... for i in range(k): ... x = pow(randint(2, n-1), d, n) ... if x == 1 or x == n-1: continue ... for r in range(1, s): ... x = (x * x) % n ... if x == 1: return False ... if x == n-1: break ... else: return False ... return True ... >>> def factors(n, b2=-1, b1=10000): # 2,3,5-wheel, then rho ... def gcd(a,b): # euclid's algorithm ... if b == 0: return a ... return gcd(b, a%b) ... def insertSorted(x, xs): # linear search ... i, ln = 0, len(xs) ... while i < ln and xs[i] < x: i += 1 ... xs.insert(i,x) ... return xs ... if -1 <= n <= 1: return [n] ... if n < -1: return [-1] + factors(-n) ... wheel = [1,2,2,4,2,4,2,4,6,2,6] ... w, f, fs = 0, 2, [] ... while f*f <= n and f < b1: ... while n % f == 0: ... fs.append(f) ... n /= f ... f, w = f + wheel[w], w+1 ... if w == 11: w = 3 ... if n == 1: return fs ... h, t, g, c = 1, 1, 1, 1 ... while not isPrime(n): ... while b2 <> 0 and g == 1: ... h = (h*h+c)%n # the hare runs ... h = (h*h+c)%n # twice as fast ... t = (t*t+c)%n # as the tortoise ... g = gcd(t-h, n); b2 -= 1 ... if b2 == 0: return fs ... if isPrime(g): ... while n % g == 0: ... fs = insertSorted(g, fs) ... n /= g ... h, t, g, c = 1, 1, 1, c+1 ... return insertSorted(n, fs)

He complained that the program failed to factor the number 100011322432435545, entering an infinite loop instead of returning a list of factors.

Your task is to figure out what is wrong, and fix it. 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.

## Potholes

### May 11, 2021

Today’s exercise comes from one of those online code exercises, via Stack Overflow:

There is a machine that can fix all potholes along a road 3 units in length. A unit of road will be represented by a period in a string. For example, “…” is one section of road 3 units in length. Potholes are marked with an “X” in the road, and also count as 1 unit of length. The task is to take a road of length N and fix all potholes with the fewest possible sections repaired by the machine.

The city where I live needs one of those machines.

Here are some examples:

.X. 1 .X...X 2 XXX.XXXX 3 .X.XX.XX.X 3

Your task is to write a program that takes a string representing a road and returns the smallest number of fixes that will remove all the potholes. 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.

## Remove Multiples

### April 27, 2021

Today’s exercise comes from Stack Overflow:

Given a number

Nand a set of numbers s = {s1, s2, …, sn} where s1 < s2 < … < sn <N, remove all multiples of {s1, s2, …, sn} from the range 1..N.

You should look at the original post on Stack Overflow. The poster gets the answer wrong (he excludes 3), he get the explanation of his wrong answer wrong (he excludes 10 as a multiple of 2), and his algorithm is odd, to say the least. I’m not making fun of him, but I see this kind of imprecision of thought all the time on the beginner-programmer discussion boards, and I can only think that he will struggle to have a successful programming career.

Your task is to write a program that removes multiples from a range, 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.

## Geothmetic Meandian

### April 13, 2021

In mathematics, the arithmetic geometric mean of two positive real numbers is computed by repeatedly taking half their sum and the square root of their product until the two numbers converge. For instance, the arithmetic geometric mean of 24 and 6 is 13.456171…, with the iterative steps computed as follows:

0 24 6 1 15 12 2 13.5 13.416407864998738175455042 3 13.458203932499369089227521 13.458139030990984877207090 4 13.458171481745176983217305 13.458171481706053858316334 5 13.458171481725615420766820 13.458171481725615420766806

The arithmetic geometric mean was invented by Lagrange and studied by Gauss, and is used today to compute various transcendental functions because it converges so quickly.

In the world of Randall Munroe, the geothmetic meandian of any set of positive numbers is computed by iterating three sequences — the arithmetic mean, the geometric mean, and the median — until they converge. For instance, the geothmetic meandian of the set (1,1,2,3,5) is 2.089, computed as follows:

1 2.4 1.9743504858348200 2 2 2.1247834952782734 2.1161924605448084 2 3 2.0803253186076938 2.0795368194795802 2.1161924605448084 4 2.0920181995440275 2.0919486049152223 2.0803253186076938 5 2.0880973743556477 2.0880901331209600 2.0919486049152223 6 2.0893787041306098 2.0893779142184865 2.0880973743556477 7 2.0889513309015815 2.0889512436159920 2.0893779142184865 8 2.0890934962453533 2.0890934865653277 2.0889513309015815 9 2.0890461045707540 2.0890461034958396 2.0890934865653277

[ I hate the damned new editor at WordPress; I struggle with it every time I post an exercise. I could not figure out how to embed the image from XKCD in this blog post. You can see it here. ]

Your task is to write programs that compute the arithmetic geometric mean and geothmetic meandian. 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.

## Greedy Text Justification

### March 30, 2021

Today’s exercise would make a good interview question, though I don’t know of anyone doing that; you should answer as if you are standing at a whiteboard explaining your code as you go:

Given a string and a line width, split the string into words (a maximal run of characters excluding spaces) and write the words onto successive lines with spaces added between the words so that each line is the requested width. Words should be added to lines greedily (as many words as will fit) and extra spaces should be assigned to the left of the output string. The last line should not have spaces added, so it may be shorter than the other lines.

For example, the string “This is an example of text justification” is written with a line width of 16 like this:

----+----+----+- This is an example of text justification. ----+----+----+-

Your task is to write a program that greedily justifies text. 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.

## Fizzbuzz

### March 23, 2021

I’ve seen several recent posts on the beginning-programmer forums about how to solve the fizzbuzz problem, so let’s talk about that today:

Enumerate the numbers from 1 to N by writing “Fizz” if the number is divisible by 3, “Buzz” if the number is divisible by 5, “FizzBuzz” if the number is divisible by both, and the number itself if the number is divisible by neither. For instance, counting from 1 to 25 works like this: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11. Fizz, 13, 14, FizzBuzz, 16, 17, Fizz, 19, Buzz, Fizz, 22, 23, Fizz, Buzz.

FizzBuzz also appears as the first problem in Project Euler, where they characterize the problem like this:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

Your task is to solve the two versions of the FizzBuzz problem, for all numbers up to *N*; you can use a simple method, but it is more fun to be a little bit clever. 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.

## Bigger To The Right

### March 9, 2021

Given a list of integers, calculate a list of integers that contains, at each item of the list, the count of integers in the original list that are greater than the item at the current position of the original list. For example, given the input list (10 12 8 17 3 24 19), the desired output is (4 3 3 2 2 0 0), because at the first item in list, 10, there are four items (12 17 24 19) greater than 10, at the second item in the list, 12, there are three items (17 24 19) greater than 12, at the third item in the list, 8, there are three items (17 24 19) greater than 8, at the fourth item in the list, 17, there are two items (24 19) greater than 17, at the fifth item in the list, 3, there are two items (24 19) greater than 3, at the sixth item in the list, 24, there are 0 items () greater than 24, and at the seventh item in the list, 19, there are 0 items greater than 19.

Your task is to write a program to calculate the list of counts of greater than the current item; is there an O(*n*) solution? When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.