## Highly Composite Numbers, A Sieving Approach

### July 19, 2016

We’ve seen programs to compute the sequence of highly composite numbers in two previous exercises. Today, we look at a third algorithm, based on the Sieve of Eratosthenes.

If you have to find a the divisors of a number, or count them, you can employ the brute-force method of testing each possible divisor from 1 to *n*, as in the first solution to this problem, or you can factor *n* and compute the divisors, as we have done in a previous exercise. But if you have to find the divisors of a bunch of numbers, in sequence, you can sieve for them; we also did that in a previous exercise. Once you know the divisor-count for each number from 1 to *n*, a simple sequential scan looking for successive records will create the list of highly composite numbers.

Your task is to write a program to calculate highly composite numbers less than a limit *n* using a sieving algorithm. 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.

## Highly Composite Numbers, Using Priority Queues

### July 15, 2016

A different solution to the previous exercise exploits the form of highly composite numbers, which always consists of small primes to large exponents, so we can specify the highly composite number using only the exponents; for instance, 64221111 represents the number 2^{6} · 3^{4} · 5^{2} · 7^{2} · 11^{1} · 13^{1} · 17^{1} · 19^{1} = 293318625600. Since the exponents must be non-increasing, there are five possibilities for a larger highly composite numbers, represented using the power-notation as 74221111, 65221111, 64321111, 64222111, and 642211111. Thus, we find composite numbers by starting with the null power-list, which equates to the number 2^{0} = 1, then add all possible successors to a priority queue, pop the successors in order, check each for a new record number of divisors, and push the successors of that number back on to the priority queue.

Your task is to generate the sequence of highly composite numbers using a priority queue. 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.

## Highly Composite Numbers

### July 12, 2016

[ Today’s exercise was written by Zacharias Voulgaris, based on a Numberphile video. Guest authors are always welcome; contact me if you wish to write an exercise. ]

A highly composite number, also called an anti-prime, is a number *n* for which d(*m*) < d(*n*) for all *m* < *n*, where d(*x*) is the *divisor* function that gives a count of the number of divisors of *x*; in other words, a highly composite number has more divisors than any smaller number. Thus, a highly composite number, which has many divisors, is the opposite of a prime number, which has only two divisors. The sequence of highly composite numbers, which begins 1, 2, 4, 6, 12, 24, 36, … (A002182), has been studied by Ramanujan and Erdös, among others, and is a continuing object of study by number theorists. A famous highly composite number, known to Plato, is 5040.

Your task is to write a program that returns all highly composite numbers less than a given limit. 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.

## Greek Time

### July 8, 2016

The modern day is divided into 24 hours, each with an equal number of minutes. In ancient times, before the invention of mechanical timepieces, the day was also divided into 24 hours, but not of equal length; there were 12 daytime hours, each of equal length, and 12 nighttime hours, each of equal length, but the length of a daytime hour and a nighttime hour differed, except on the two equinoxes.

For example, today, where I live, the sun will rise at 5:45 and set at 20:29, giving 884 minutes of sunlight, so there will be 73 2/3 minutes per daylight hour. Starting from sunrise at 5:45, the hours are 6:59, 8:12, 9:26, 10:40, 11:53, 13:07, 14:21, 15:34, 16:48, 18:02, and 19:15, with sunset at 20:29.

Your task is to write a program that calculates the daylight hours of the greek clock. 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.

## Depth Charge

### July 5, 2016

Creative Computing was a staple of my programming education; I remember typing in the games to run on a friend’s computer. Here’s a game from the very first issue of the magazine, written by 18-year old Dana Noftle:

In this program, you are the captain of the destroyer, USS Digital. An enemy submarine has been causing trouble and your mission is to destroy it. You may select the size of the “cube” of water you wish to search in. The computer then determines how many depth charges you get to destroy the submarine.

Each depth charge is exploded by you specifying a trio of numbers; the first two are the surface coordinates, the third is the depth. After each depth charge, your sonar observer will tell you where the explosion was relative to the submarine.

Here’s a sample game:

DEPTH CHARGE GAME DIMENSION OF SEARCH AREA? 10 YOU ARE CAPTAIN OF THE DESTROYER USS DIGITAL. AN ENEMY SUB HAS BEEN CAUSING YOU TROUBLE. YOUR MISSION IS TO DESTROY IT. YOU HAVE 4 SHOTS. SPECIFY DEPTH CHARGE EXPLOSION POINT WITH A TRIO OF NUMBERS -- THE FIRST TWO ARE THE SURFACE COORDINATES; THE THIRD IS THE DEPTH. GOOD LUCK ! TRIAL # 1 ? 5,5,5 SONAR REPORTS SHOT WAS SOUTHEAST AND TOO HIGH. TRIAL # 2 ? 3,7,7 SONAR REPORTS SHOT WAS SOUTHEAST AND DEPTH OK. TRIAL # 3 ? 1,9,7 SONAR REPORTS SHOT WAS NORTHEAST AND DEPTH OK. TRIAL # 4 ? 0,8,7 B O O M ! ! YOU FOUND IT IN FOUR TRIES!

The first coordinate is east/west, the second coordinate is north/south. Here is the program that appeared in *Creative Computing* (pages 18-19):

10 PRINT "DEPTH CHARGE GAME" \ PRINT 20 INPUT "DIMENSION OF SEARCH AREA"; G \ PRINT 30 N = INT(LOG(G)/LOG(2))+1 \ RANDOMIZE 40 PRINT "YOU ARE CAPTAIN OF THE DESTROYER USS DIGITAL." 50 PRINT "AN ENEMY SUB HAS BEEN CAUSING YOU TROUBLE. YOUR" 60 PRINT "MISSION IS TO DESTROY IT. YOU HAVE"N"SHOTS." 70 PRINT "SPECIFY DEPTH CHARGE EXPLOSION POINT WITH A" 80 PRINT "TRIO OF NUMBERS -- THE FIRST TWO ARE THE" 90 PRINT "SURFACE COORDINATES; THE THIRD IS THE DEPTH." 100 PRINT \ PRINT "GOOD LUCK !" \ PRINT 110 A=INT(G*RND) \ B=INT(G*RND) \ C=INT(G*RND) 120 FOR D=1 TO N \ PRINT \ PRINT "TRIAL #"D, \ INPUT X,Y,Z 130 IF ABS(X-A)+ABS(Y-B)+ABS(Z-C)=0 THEN 300 140 GOSUB 500 \ PRINT \ NEXT D 200 PRINT \ PRINT "YOU HAVE BEEN TORPEDOED! ABANDON SHIP!" 210 PRINT "THE SUBMARINE WAS AT"A","B","C" \ GOTO 400 300 PRINT \ PRINT "B O O M ! ! YOU FOUND IT IN "D"TRIES!" 400 PRINT \ PRINT \ INPUT "ANOTHER GAME (Y OR N)", A$ 410 IF A$="Y" THEN 100 42O PRINT "OK. HOPE YOU ENJOYED YOURSELF." \ GOTO 600 500 PRINT "SONAR REPORTS SHOT WAS ", 510 IF Y>B THEN PRINT "NORTH", 520 IF Y<B THEN PRINT "SOUTH", 530 IF X>A THEN PRINT "EAST", 540 IF X<A THEN PRINT "WEST", 550 IF Y<>B OR X<>A THEN PRINT " AND", 560 IF Z>C THEN PRINT " TOO LOW." 570 IF Z<C THEN PRINT " TOO HIGH." 580 IF Z=C THEN PRINT " DEPTH OK." 590 RETURN 600 END

Your task is to rewrite the program in your favored programming language. 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.

## Clock Angles

### July 1, 2016

We have a fun little program for a lazy summer Friday:

Write a program that, given a time as hours and minutes (using a 12-hour clock), calculates the angle between the two hands. For instance, at 2:00 the angle is 60°.

Your task is to write a program that calculates clock angles. 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.

## Curious Numbers

### June 28, 2016

Today’s exercise is in the style of Project Euler, so the rules are that your solution must not use more than a minute of computer time and that you can’t peek at the solution until you have the answer yourself.

Some numbers have the curious property that when they are squared, the number appears in the least-significant digits of the product. For instance, 625

^{2}= 390625, and 7106376^{2}= 50543227109376.What is the sum of all numbers less than 10

^{20}that have this curious property?

Your task is to find the sum 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.

## Phone Numbers And Prime Factors

### June 24, 2016

John Cook is a mathematician and programmer who runs a fascinating blog that I frequent.

Cook recently had an article about the prime factors of telephone numbers. He explained that, for 10-digit telephone numbers as used in the United States, the average number of distinct prime factors is 3.232 and the distribution is between 1 and 5 distinct prime factors about 73% of the time.

Your task is to write a function that determines the number of distinct prime factors of a number, and use that function to explore the distribution of the number of distinct prime factors in a range of telephone 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.

## Two Interview Questions

### June 21, 2016

I like to read a web site called Career Cup, both to enjoy solving some of the programming exercise given there and to find exercise for Programming Praxis. As I write this exercise, here are the two most recent exercises on Career Cup:

- Given a function
`rand2`

that returns 0 or 1 with equal probability, write a function`rand3`

that returns 0, 1 or 2 with equal probability, using only`rand2`

as a source of random numbers. - Given a set of characters and a dictionary of words, find the shortest word in the dictionary that contains all of the characters in the set. In case of a tie, return all the words of the same (shortest) length.

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

## Tomohiko Sakamoto’s Day-Of-Week Algorithm

### June 17, 2016

Here is Sakamoto’s algorithm for calculating the day of the week, taken from the comment that introduces the code:

Jan 1st 1 AD is a Monday in Gregorian calendar.

So Jan 0th 1 AD is a Sunday [It does not exist technically].Every 4 years we have a leap year. But xy00 cannot be a leap unless xy divides 4 with reminder 0.

y/4 – y/100 + y/400 : this gives the number of leap years from 1AD to the given year. As each year has 365 days (divdes 7 with reminder 1), unless it is a leap year or the date is in Jan or Feb, the day of a given date changes by 1 each year. In other case it increases by 2.

y -= m So y + y/4 – y/100 + y/400 gives the day of Jan 0th (Dec 31st of prev year) of the year. (This gives the reminder with 7 of the number of days passed before the given year began.)

Array t: Number of days passed before the month ‘m+1’ begins.

So t[m-1]+d is the number of days passed in year ‘y’ upto the given date.

(y + y/4 – y/100 + y/400 + t[m-1] + d) % 7 is reminder of the number of days from Jan 0 1AD to the given date which will be the day (0=Sunday,6=Saturday).

int dow(int y, int m, int d) { static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4}; y -= m < 3; return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7; }

Another description is given here.

Your task is to write a program that implements the day-of-week algorithm 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.