UHSSC 2013 Challenges

Roundness:

Hoffman (1998, p. 90) calls the sum of the exponents in the prime factorization of a number its roundness. The first few values for n=1, 2, ... are 0, 1, 1, 2, 1, 2, 1, 3, 2, 2, ... (Sloane's A001222). From: http://mathworld.wolfram.com/Roundness.html

The Challenge:

This year's UHSSC challenge requires that each team write an application to evaluate the "roundness" of a range of integers from a given minimum value to a given maximum value, where the minimum value is greater than zero and the maximum value is less than 10 million. The application should sort these numbers first by roundness, then by numerical value.

This sorted list of integers should then be written to a disk file named "uhssc.out". An example follows for the range of numbers from 7 to 15:

Number	Pime Factors	Roundess	"uhssc.out"
7	7	1	8
8	2,2,2	3	12
9	3,3	2	9
10	2,5	2	10
10	2,5	2	10
11	11	1	14
12	2,2,3	3	15
13	13	1	7
14	2,7	2	11
15	3,5	2	13

The output file will be compared using "diff" to the corresponding file produced by the reference code "UHSSCref.c". Four different ranges of integers will be tested, each range four times. The cumulative execution time will be recorded. The team that produces the correct output files with the least cumulative execution time will be declared the winner of the Software Optimization Challenge.

This application will be called "UHSSCopt". The command line for this application should look like: where "time" is the linux time command, <min> is the smallest number in the range and <max> is the largest number in the range with 0 < min < max <= 10000000 .

Sample Output

Following is sample output from the program:

$ ./UHSSCref 7 20

Prime Factorization Table:
<integer> <F1>,<F2>,... (<roundness>)
(Not required for UHSSC)

7  7 (1)
8  2,2,2 (3)
9  3,3 (2)
10  2,5 (2)
11  11 (1)
12  2,2,3 (3)
13  13 (1)
14  2,7 (2)
15  3,5 (2)
16  2,2,2,2 (4)
17  17 (1)
18  2,3,3 (3)
19  19 (1)
20  2,2,5 (3)


Integers sorted by roundness:
<integer> (<roundness>)
(Required for UHSSC)

7 (1)
11 (1)
13 (1)
17 (1)
19 (1)
9 (2)
10 (2)
14 (2)
15 (2)
8 (3)
12 (3)
18 (3)
20 (3)
16 (4)