Highly Abundant Numbers

December 20, 2016

We studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: highly abundant numbers (A002093).

Highly abundant numbers are those numbers n such that sigma(m) < sigma(n) for all m < n, where m and n are positive integers and sigma(n) is the sum of the divisors of n. For instance, 12 is a highly abundant number since the sum of its divisors is 1 + 2 + 3 + 4 + 6 + 12 = 28, and no number less than 12 has a greater sum of divisors.

Your task is to compute the sequence of highly abundant 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.

Pages: 1 2

SQL Insert Syntax

December 16, 2016

When I’m not writing exercises for Programming Praxis, my day job has me writing SQL and PL/SQL code for a large Oracle database. One task I frequently perform is inserting records into a table, using the following syntax:

insert into tablename (
    field_1,
    field_2,
    field_3,
    ...)
values (
    value_1,
    value_2,
    value_3,
    ...)

Here, tablename is replaced by the name of the database table into which records are being inserted, each field is the name of a field in the table, and each value is the value to be inserted. The correspondence between field name and value is positional.

I can’t tell you how many times over the years I wrote that wrong. When I inadvertently skip a field, an error message politely tells me of my mistake. But when I transpose two fields, both of the same type, there is no error message, and I happily go on my way with bad data in the database.

I finally decided to do something about the situation; I wrote a program that converts the syntax shown below, which makes it easy to see the correspondence between fields and values, to the Oracle syntax shown above:

insert into tablename (
    field_1 => value_1,
    field_2 => value_2,
    field_3 => value_3,
    ...)

That’s much better: Easy to get right, much harder to get wrong. A significant payback on a few minutes of effort. Why didn’t I do this years ago!?

Your task is to find something annoying in your programming environment, and fix it; you can borrow my annoyance in the unlikely event you have none of your own. 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

List Swap

December 13, 2016

We have today an exercise for students who work with linked lists:

Given a linked list and an integer k, swap the two list items that are at distance k from the beginning of the list and distance k from the end of the list. Be sure to consider the case where the k cross, so that the item k from the beginning of the list is after the item k from the end of the list. For instance, given the list (1 2 3 4 5 6 7) and k = 2, you should return the list (1 6 3 4 5 2 7), and likewise if k = 6. The solution must run in O(n) time, where n is the length of the list.

Your task is to write the list-swapping code 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

Searching An Infinite Array

December 9, 2016

Given an array of positive integers in ascending order, of infinite size, find the index of an integer k in the array, or determine that it does not exist. Your solution must work in time logarithmic in the index of the requested integer.

Your task is to write a program that finds the requested integer. 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

Career Cup

December 6, 2016

Regular readers know that I sometimes find inspiration for these exercises at Career Cup:

Given two sorted arrays, efficiently find the median of the combined array.

Your task is to write the indicated 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.

Pages: 1 2

Beale’s Cipher

December 2, 2016

In the early 1800, Thomas J. Beale mined a large quantity of gold and silver, secretly, some place in the American West, and brought the gold, silver, and some jewels purchased with the treasur to Virginia, where he buried it. He wrote three coded documents that described the location of the buried treasure, the nature of the treasure, and the names of the owners. He never came back to retrieve the treasure. Only the second of those documents has been decoded, and many people, even today, are scouring Bedford County, Virginia, looking for buried treasure. Or so the story goes.

Beale used a variant of a book cipher. He chose a long text as a key, numbered each of the words in the text sequentially, starting from 1, and formed a message by choosing from the key text a word for each character of plain text having the same initial letter as the plain text; the cipher text consists of a list of the sequence numbers of the chosen words. For instance, if the key text is “now is the time” and the plain text is “tin”, then either (3 2 1) or (4 2 1) are valid encipherments. If the key text is long, there will be many duplicates, as we saw with the letter “t”, and the resulting cipher will be reasonably secure. Beale used the 1322 words of the Declaration of Independence as the key text for the second document; the key texts associated with the first and third documents are unknown.

Your task is to write programs that encipher and decipher messages using the Beale cipher; use it to decode the second document. 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 3

In many of our programs involving prime numbers and number theory, we need to be able to determine if a number n is a perfect square. One way to do that is to determine the integer square root of the number, using Newton’s method, then multiply to determine if the original number is a square. But that’s slow. In a previous exercise, we used a method devised by Henri Cohen to calculate the quadratic residues of n to various moduli, which can quickly determine that some n cannot be perfect squares.

Over at Mersenne Forum, fenderbender extends Cohen’s idea to make a ridiculously fast square predicate: he precalculates multiple moduli to reduce the operation from big integers to 32-bit integers, chooses the moduli after extensive testing, and tests the quadratic residues using a 64-bit bloom filter. The result is impressive. Where Cohen eliminates the expensive square root calculation in 99% of cases, fenderbender eliminates the expensive square root calculation in 99.92% of cases, and does it faster than Cohen. Go read fenderbender‘s explanation to see a beautiful combination of number theory, wonky programming, and sheer artistry.

Your task is to implement fenderbender‘s square predicate. 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

These three questions come from Career Cup:

First: A kidnapper wants to write a ransom note by cutting characters from the text of a magazine. Given two strings containing the characters of the ransom note and the characters of the magazine, write a program to determine if the ransom note can be formed from the magazine.

Second: Write a program that operates in linear time that finds the item in a list that appears the most times consecutively.

Third: Given two finite streams of integers that are too large to fit in memory, write a program that finds the integers that appear in both streams; it must operate in time linear in the length of the longer of the two streams.

Your task is to write the three programs 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

Missing Items

November 22, 2016

We have today a simple exercise; we’ve seen variants of it previously.

Given two lists, find all the items in the first list that are not present in the second list. For instance, if (5 15 2 20 30 40 8 1) is the first list and (2 20 15 30 1 40 0 8) is the second list, the item 5 is present in the first list but not in the second list.

Your task is to write a program to find missing items. 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

RIP Leibniz

November 18, 2016

Gottfried Wilhelm Leibnez was a German mathematician and philosopher, and a developer, independently of Isaac Newton, of calculus; it was he who invented the d/dx notation used in writing integrals. He died three hundred years ago, on November 14, 1716, so today (a few days late, sorry) we have an exercise about calculus:

Write a program that computes the average number of comparisons required to determine if a random sequence is sorted. For instance, in the sequence 1 2 3 5 4 6, the first inversion appears between 5 and 4, so it takes four comparisons (1<2, 2<3, 3<5, 5<4) to determine that the sequence is not sorted.

Your task is to write a program 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