Approximate Squaring

June 8, 2021

Lagarias and Sloane study the “approximate squaring” map f(x) = xx⌉ 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 10435 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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

Remove Multiples

April 27, 2021

Today’s exercise comes from Stack Overflow:

Given a number N and 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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

Trailing Comments

February 23, 2021

Today’s exercise is based on a blog entry that Reddit pointed me to. Sean is trying to write a program that finds lines of code in his Python programs that have trailing comments at the ends of lines, which he considers bad style. His naive program improperly flagged a line as containing a trailing comment when the comment marker is embedded in a quoted string:

x = "# This is fine"
"This \# is fine too"
x = "" # This is not

Sean gets a little bit sidetracked in his blog entry, and never quite solves the problem; I’m not convinced the code he writes is correct (though he seems to think it is), and I’m also not convinced that trailing comments are a bad thing. Nevertheless, the task makes an interesting exercise, especially when we also handle quoted escape sequences.

Your task is to write a program that identifies lines of code with trailing comments. 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.

Pages: 1 2

Local Maxima

February 16, 2021

A local maximum of a list of integers is an element of the list at which the adjacent list elements are either less than or equal to the current element; for instance, in the input list (1 2 1 2 3 4 3 2 3 2 1) there are three local maxima, one at the first 2, one at the 4, and one and the last 3. The elements at either end of a list should be considered as greater than the boundary. Only one maximum should be reported for a plateau (consecutive equal maxima).

Your task is to write a program that finds the local maxima of a list of integers. 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.

Pages: 1 2