The string that you emailed me:

(20P) Who is a jerk? (according to pp. 75-81)

(100P) (Due at the second last class, partial credits) Choose one of the two options:**Figure and Ground project**: Compose some art in which both the figure and the ground are interesting.**Tessellation project**: Compose a nice tessellation.

We extended the pq-system to contain more typographical patterns such as (t,q) and DND (doesn't divide). When you're asked to define things, you're free to use **(p,q), (t,q) **and** DND** as if they are already defined correctly, plus any **previous** **definition** (doesn't matter whether you defined that correctly).

For format's sake, let's say we defined (p,q) as follows: (you can omit the periods in your definitions)

```
xp-qx-.
```

xpyqz -> xpy-qz-.

(15P) In 1 line, define LT such that "(*x hyphens*)LT(*y hyphens*)" is a theorem iff *x* < *y*.

(25P) Define P such that "P(*x hyphens*)" is a theorem iff *x* is a prime. (Recall: do a bounded search using DND.)

(40NP) Define POT such that "POT(*x hyphens*)" is a theorem iff *x* is a power of 10.

(70NP) Define SF such that "SF(*x hyphens*)" is a theorem iff *x* is square free.

(200NP) In view of this week's topic (Figure and Ground), try to figure out how the following sequence is generated (no need to explain):

`1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, ...`

Then define HOFSEQ such that "HOFSEQ(*x hyphens*)" is a theorem iff *x* is in this sequence.

(?NP) I would really like to see the following:

1. "PERF(*x hyphens*)" is a theorem iff *x* is a perfect number.

2. "BACHRIGHT" is a theorem iff Goldbach's conjecture is true.

3. "BACHWRONG" is a theorem iff Goldbach's conjecture is false.

4. "COLLATZRIGHT" is a theorem iff the 3x+1 conjecture is true.

5. "COLLATZWRONG" is a theorem iff the 3x+1 conjecture is false.

Play around. If your answer is nonempty and provably-correctly defines *k* of them, you will get 15^kNP. (Hence you get some small reward by simply reading this.)

(16NP) Consider a programming language which represents the memory as an integer list (denoted as A[1], A[2], ...), and has three kinds of instructions (all of which takes up a whole line):

`+ i j `

: increment A[*i*] by 1, and go to line *j*`- i j k `

: if A[*i*] is positive, decrement A[*i*] by 1 and go to line *j*; otherwise, go to line *k*`H `

: halt

i

When a program is executed, the memory is set to all zeros; then the instruction at line 1 is executed. A program is said to output *x* if it terminates with A[1] = *x*, A[2] = A[3] = ... = 0.

Here are two sample programs:`+ 1 2`

+ 1 3

- 2 5 4

+ 2 1

H // outputs 4 (order: L1->L2->L3->L4->L1->L2->L3->L5)

`+ 2 2`

+ 2 3

+ 1 4

- 2 5 10

- 1 6 8

+ 3 7

+ 3 5

- 3 9 4

+ 1 8

H // outputs 4

Within 15 lines, write a program whose output is greater than .