Assignment 1 : Prime-Factor Encoding of 3-Digit Integers

Computer Science 320SC
Programming Assignment 1

Version 1.01, 2018-07-17: corrected day of week in the due date
Version 1.1, 2018-07-18: adjusted output spec of problem 1 for consistency; fixed two typos
Version 1.11, 2018-07-18: corrected values of pfe(3) and pfe(13) in textual description
Version 1.12, 2018-07-19: adjusted the introduction in Problem 1 to emphasise that the prime factors
must be listed in strictly-increasing order
Requirements
This first assignment lets you get familar with submission of correct and efficient implementations of
simple (but not quite trivial!) algorithms to the CompSci 320 automated marker. You may implement
your algorithms in any language accepted by the automarker e.g. Java, Python 3, Python 2, C or C++.
This assignment is worth 5% of your total course marks. Future programming assignments will require
much more work to obtain the same number of marks, so you are encouraged to make a serious attempt
on this one!
Problem Statement 1: Prime-Factor Encoding of 3-Digit Integers
The input to your program is single non-negative integer n < 1000.
The output to your program is in tabular form, with a single-line header followed by n lines of output,
where the k-th line of output indicates how the integer k can be expressed in two different ways as a
string.
The first line of output should be the 10-character string " k pfe(k)", where there are two spaces
before the "k" and one space after the "k".
The first string on the (k+1)-st line of output (1 ≤ k ≤ n) is the value of k expressed as a right-adjusted
decimal string d(k) that is exactly three characters long, for example d(1) = " 1" and d(999) = "999".
The second string on the k-th line of output is its prime-factor encoding pfe(k). We’ll start with some
examples of this encoding, rather than a formal definition: pfe(2) = "2", pfe(4) = "2^2", pfe(6) =
"2*3", pfe(8) = "2^3", and pfe(12) = "2^2*3". Please note that the exponentiation operator "^"
takes precedence over the multiplicative operator "*". Also note that the factors are listed in strictlyincreasing order, e.g. "3*3" is not a pf-encoding of any integer, because the factor 3 appears twice.
The integer 9 is pf-encoded as "3^2".
Exponents ei are encoded as decimal strings d(ei) however the bases bi are coded somewhat more cleverly
– as the decimal encoding d(j) of the index j of this prime factor pj = bi
. Accordingly, pfe(1) = "1",
pfe(2) = "2", pfe(3) = "3", pfe(5) = "4", pfe(7) = "5", pfe(11) = "6", pfe(13) = "7". Note that I
have introduced pfe(1) = "1" as a special case in our encoding – because I want to have a non-null
representation of the integer 1.
The two strings on the (k + 1)-st line of output (1 ≤ k ≤ n) should be separated by a single space.
1
The input should be taken from keyboard/stdin/System.in.
Sample Input:
17
Your program’s precisely-formatted output should be sent to console/stdout/System.out.
Sample Output:
k pfe(k)
1 1
2 2
3 3
4 2^2
5 4
6 2*3
7 5
8 2^3
9 3^2
10 2*4
11 6
12 2^2*3
13 7
14 2*5
15 3*4
16 2^4
17 8
As far as I know, pf-encoding has not been studied previously – so you’re exploring some novel territory
for algorithmics! If you’re intrigued to know more about the underlying mathematics, please see Sum
of Prime Factors in Wolfram’s online MathWorld resource; and if you want to dig even deeper, please
see A001414 Integer log of n: sum of primes dividing n (with repetition).
Formally: the pf-encoding of a positive integer k is the concatenation of strings si
, where each string
is a factor of k of the form ji (if the exponent ei = 1) or of the form ji^ei (if the exponent ei 1).
The ji values are indices into the monotonically-increasing sequence of primes starting from 1. The ei
values are exponents. Both ji and ei are encoded as decimal strings. Adjacent strings are separated by
asterisk characters "*". The ji values are monotonically increasing, for example pfe(6) = "2*3", and
the string "3*2" is not a pf-encoding of any integer.
If you’re struggling to understand this problem, please ask for help among your classmates or attend
your tutorial session. This is not a course in algebraic number theory. I will not be examining you
on the (as-yet unexplored) properties of pfe(). Instead I’m trying to give you some experience with
a formally-specified problem statement. Without some formalism, it is impossible to specify exactly
what an algorithm “should” be doing, making it impossible to prove its correctness. However even in
a formal statement there is room for ambiguity or confusion – so please please please ask questions
until you know what your algorithm “should” be doing, before you try to design it and implement it.
And, unless you’re truly wizardly, you’ll have to debug your implementation before it does what you
think it should be doing. When you submit your implementation to the automarker, it will test your
implementation on a (secret) value of input – to determine whether or not your implementation runs
this particular case correctly.
2
Problem Statement 2: PF-Compressibility
The input format for this problem is the same as in Problem 1: a single positive integer n < 1000
expressed as a decimal string.
The output format for this problem is similar to Problem 1, but possibly with fewer lines of output.
Your program should print only the lines for which the length of the pf-encoded representation of an
integer k is shorter than the length of its representation d(k) as a decimal string.
The input should be taken from keyboard/stdin/System.in.
Sample Input:
17
Your program’s precisely-formatted output should be sent to console/stdout/System.out.
Sample Output:
k pfe(k)
11 6
13 7
17 8
Problem Statement 3: Efficient Multiplication
The input format for this problem is a space-separated series of pf-encoded integers pfe(vi), where
every integer value vi
is of bounded size vi < 1000. The input line may be arbitrarily long. However
your implementation may have OS-dependencies which effectively put an upper bound on the length
of its input lines, so (to save you the trouble of diagnosing and eliminating any such dependencies) our
automarker will test your implementation with an input line of at most 2000 characters.
The output format for this problem is a single line: the pf-encoding of the product Q
vi of all values vi
in its input.
Your implementation must be efficient: it should run in O(n) time on an n-character input.
The input should be taken from keyboard/stdin/System.in. Note that the spacing of the input may be
irregular.
Sample Input:
2^3 17 3*4
Your program’s precisely-formatted output should be sent to console/stdout/System.out.
Sample Output:
2^3*3*4*17
Submission
For each of the problems in this assignment, name your source code gcd.ext, where ext denotes one
of { java, cpp, py2, py3, cs } indicating its language (Java, C++, Python 2, Python 3, mono).
You must use exactly one source file per problem, with your submission for problem j named probj.ext.
Two marks are awarded for Problem 1, one mark for Problem 2, and two marks for Problem 3.
3