We will solve the easy input first.

(o) (a) (e) (t) (c) (c) (r) (_) (_) (t) (_) (e) (n) (w) (_) (r) (o) (e) (s) (i) (h) (u) (e) (c) (d) (i) (r) (c) (i) (s) (r) (e) 1608168553 { 32 -3 roll exch 2 index 32 3 roll pop 17 5 roll 3 copy 7 2 roll 3 { pop } repeat -5 24 4 add exch roll 30 2 roll 15 5 roll exch 15 -4 roll dup 9 1 roll pop 6 index 8 -1 roll pop 20 -5 roll 5 -1 roll exch 5 1 roll 20 5 roll } repeat 1 1 32 { 15 mul 550 exch sub 800 moveto show } for showpage

This piece of code is pretty much straightforward. First we push some letters onto the stack, then we do an awful lot of operations with the stack and at the end we print the top 32 letters of the stack. (Note that the letters are printed from right to left.) The only problem: how does the middle part of code alter the stack? The easiest way to discover this is to modify the code and see what happens.

Instead of the original letters we push some unique strings (e.g. (1), (2), etc.) onto the stack. We won't run the cycle 1608168553 times, just once. After viewing the modified PostScript file we notice that the middle part of code is just a fixed permutation of the stack.

We want to determine the result after applying this permutation 1608168553 times. After we know the permutation, this can be done by hand. It suffices to split the permutation into disjoint cycles. Now we may rotate each of the cycles 1608168553 times (or equivalently (1608168553 modulo its length) times). An even more lazy solution is to use the following straightforward lemma:

Let **P** be a permutation, consisting of cycles with lengths
**l _{1}**, ...,

In our case the cycle lengths are 1, 5, 8 and 18. Their least common multiple is 360. Therefore applying the permutation 1608168553 times is equivalent to applying it only (1608168553 modulo 360) = 313 times. Now all we have to do is to take the original input file, replace 1608168553 by 313 and open the file in a PostScript viewer.

The hard input will be a bit more complicated. We define some variables, a procedure, an array and write some code. The first part of the code follows.

/last 0 def { /wherex 50 def /wherey 780 def 1200 { rand 2147483648 div /foo exch def /goo 0 def /next 0 def wherex wherey moveto { goo foo lt { goo prob last 27 mul next add get add /goo exch def next 1 add /next exch def } { exit } ifelse } loop upperbound 3 163 409 mul mul lt { upperbound 1 add /upperbound exch def } if next 1 sub dup /last exch def dup 0 gt { 9 add 36 tmpstring cvrs } { pop ( ) } ifelse dup stringwidth exch wherex add 2 add /wherex exch def wherex 500 gt { /wherex 50 def wherey exch sub 20 sub /wherey exch def } { pop } ifelse show } repeat showpage } loop

Note the last line of the code -- this part is an infinite loop. By deleting
it we may find out that this is the part generating the random words. Just for
the record, the array **prob** is a Markov transition matrix. Basically
the matrix contains the probabilities **Pr(next letter is X | this letter was Y)**.
The code generates the words using this transition matrix. However, we are
not interested in the words, also we may delete this part of code. Well, almost.
There is one interesting line hidden in the middle:

upperbound 3 163 409 mul mul lt { upperbound 1 add /upperbound exch def } if

What does this line do? Take the current value of **upperbound**.
Compare it with 3*163*409 = 200001. If it is less, increase **upperbound** by 1.
Clearly after the awful lot of words is generated and the infinite loop finishes ;-)
(well, already after after approx. 170 pages) **upperbound** will assume
the value 200001 and stop changing.

Now let's concentrate on the last part of the input file.

/j 1 def /k 0 def upperbound { j 1 add /number exch def j trick1 j add number mod j eq { k j add /k exch def } if j 1 add /j exch def } repeat k 50 750 moveto tmpstring cvs show showpage

We already know that this piece of code is repeated 200001 times. We may rewrite it
into pseudo-C-code as follows: (From the syntax we assume that the procedure
**trick1** takes the top of the stack as an argument and replaces it with
its output. Later we will show that **trick1** really behaves in this way.)

j=1; k=0; upperbound=200001; while (upperbound--) { number=j+1; if ( ((trick1(j)+j)%number) == j ) k+=j; j++; } print(k);

This code looks pretty simple. If only we knew, what does **trick1** compute, we would
be almost done. So let's take a look at the procedure.

/trick1 { /i exch def i 1 gt { i { i dup -1 add trick1 exch /i exch def } repeat i -1 add { add } repeat i i mul add i sub i sub number mod } { 0 } ifelse } def

On the first line the procedure takes the top of the stack and stores it in the variable **i**.
If **i<=1**, **trick1** pushes 0 onto the stack and returns. The other case is more
complicated. First of all, look at this part:

i dup -1 add trick1 exch /i exch def

First line: **i** is pushed, **i-1** is pushed.
Second line: we call **trick1** recursively. The value **i-1** is replaced by
**trick1(i-1)**.
Third line: Calling **trick1** in the previous line probably destroyed the contents
of the variable **i**. Therefore we stored it on the stack before calling the
procedure. Now we restore the original value of **i**. The value **trick1(i-1)**
remains on the stack.

The above code is repeated **i** times. Now we have **i** copies of the value
**trick1(i-1)** on the top of the stack. In the next line we add them together.
In the following lines we add **i ^{2}-2i** to this value and compute the
remainder after dividing it by

Let's forget for a while that we compute the values of **trick1** modulo **number**.
We now know a simple recurrence equation for the values returned by **trick1**:
**trick1(1)=0**, **trick1(n)=n.trick1(n-1)+n ^{2}-2n** for

The last step awaits us. Back to the piece of our pseudo-C-code.
We may rewrite it using the above result. Also note that **trick1** does
not change the value of **number**, therefore also after calling **trick1**
the value **j+1** is stored in **number**.

j=1; k=0; upperbound=200001; while (upperbound--) { if ( ( (j!)%(j+1) ) == j ) k+=j; j++; } print(k);

The code computes the sum of those values **j** from the set **{1,2,...,200001}**
for which the complicated condition holds. Let's take a look at the condition.
It is true iff **j!** gives the remainder **j** (or equivalently -1) modulo **j+1**.
Those of you with some mathematical background probably know this condition under the
name *Wilson's lemma*.

Lemma (Wilson). The number **p** is prime iff **(p-1)!** is congruent to -1 modulo **p**.

Also we add together all those values **j** for which **j+1** is prime. In other words,
the result is **(sum of primes in {1,2,...,200001}) - (count of primes in {1,2,...,200001})**.
Note that the knowledge of Wilson's lemma was not necessary. You could compute (either by hand
or by modifying the code) the first few values of **j** for which the condition holds and
guess the result.

If you liked this problem and you are now interested in PostScript, we may recommend some literature
to you. First of all, there is the *PostScript Language Reference* (and several other documents),
which can be downloaded at the Adobe website.

You may find the
*First
Guide to PostScript* useful.
Also you may download and take a look at one of the following books:
*Byram-Wigfield: Practical PostScript*,
*Reid: Thinking in PostScript*.

If you are fluent in Czech language, we recommend reading the project
*Vladimir Michl: PostScript*.
This document concentrates on one of the most powerful uses of PostScript -- drawing
simple graphics. In fact, PostScript may often be the best possibility if you
need to add a simple graphical output to your application!