© Copyright 1998 by
Heiner Marxen
The Year Puzzle
Contents
Introduction
Usually, the "Year Puzzle" challanges you to connect the four digits
of the current year (in that order) with the usual arithmetic operators,
in order to form expressions which yield all the values from
(say) 1 to 100.
The "Four 4's" puzzle is exactly the same for the year 4444.
Both forms have appeared repeatedly e.g. in the
news group sci.math.
While this puzzle is fun for the beginner,
discussing the more difficult cases
(how do you build a 39 with four 4's?)
rapidly exhibit the need for more exact rules of the game.
There seems to be no generally accepted rule set.
The following rules seem to be generally accepted:

The four digits of the year (say 1, 9, 9, 8) have to appear
in the exact original order, as in
16 = 1*9 + 9 + 8.
All digits must appear exactly once.

You may use the four basic binary arithmetic operators
"+", "", "*" and "/"
(for addition, subtraction, multiplication and division).

You may use the unary negation operator "".

You may use parantheses for grouping.
The following rules seem to be accepted by most, but not all:

You may use the binary exponentiation operator "^", as in
18 = 1^9+9+8.

You may use the concatenation of digits, as in
91 = 18+98.

You may use the unary factorial operator "!", as in
19 = 1 + 9 + 9!/8!.

You may use square roots, as in
4 = 1 + sqrt(9/9 + 8).
The following rules seem to be accepted by some, but not many (I like them):

You may use decimal points "." before and between digits, as in
33 = 4! + 4 + sqrt(4)/.4

You may use the unary odd factorial operator "!!",
which multiplies the odd natural numbers upto and including
its argument, i.e. 5!! = 1*3*5.
This is allowed for odd arguments, only.

You may use the unary even factorial operator "!!",
which multiplies the even natural numbers upto and including
its argument, i.e. 6!! = 2*4*6.
This is allowed for even arguments, only.
The following operators are generally not accepted.

Repeating decimal fractions: .(4) = 0.444... = 4/9.

Logarithms log(x). Logarithms to other bases, as in
0.5 = log4(sqrt(4)).

Exponential function exp(x).

Trigonometric function like sin(x) and atan(x).
Some operator combinations even allow to systematically
construct all numbers, which makes the puzzle quite boring.
My Approach
When I first tried to solve the four 4's with paper and pencil,
I failed to find solutions for such small values as 33 and 39.
Then I started to systematically list all partial expressions
with just two of the four fours and to tabulate the resulting values.
I soon realized that this is a job for a computer program,
not for a programmer :).
Hence I started to write a program, which should perform
that systematic search.
I used "awk" (i.e. "nawk") for it,
and I have extended the first experimental version since then,
such that I am very satisfied with the results.
A few minutes on a typical workstation are enough to yield
a list of solutions, which is as complete as I could do myself.
No, sorry, my awk program is not in the public domain.
But I'll share some of my ideas. Let's take "1998" as an example.

Before building expressions with all the four digits in it,
we build all potential partial expressions,
and tabulate them by value.

We start to build the (trivial) expressions for signatures
of length 1, i.e. for "1", "9" and "8".
Using binary operators we then build expressions for signatures
of length 2, i.e. for "19", "99" and "98".
And so on, until we reach length 4, and print the results.
E.g. from "10 = 1+9" and "1 = 98" we build
 11 = (1+9)+(98),
 9 = (1+9)(98),
 10 = (1+9)*(98),
 10 = (1+9)/(98) and
 10 = (1+9)^(98).

If we have two expressions with the same value for the same signature,
we keep the shorter or more simple expression and discard the other.
E.g. we keep "4*4" and discard "sqrt(4^4)".

If concatenation is allowed,
we just allow signatures of length greater than 1 to trivially yield
an expression.

We store all intermediate values as normalized rational numbers.

We restrict nominator and denominator of intermediate values
to some suitable range. At least we have to take care of overflows.

Whenever we invent a new expression with a new value,
we recursively try all unary operators to yield further values.
Exponentiation with rational numbers may be a bit tricky.
This pretty much sums up my method.
My Results
I let my awk program run for some of the interesting years,
for the four 4's, and also for four other digits.
You can look at the respective output, for the range 0200.
Other Resources (English)
Other Resources (German and Dutch)

In ihrem Sommerrätsel 1998 hat Cathie
nach Lösungen für die Vier Vieren gefragt.
Die Lösungstabelle
stimmt gut mit meinen eigenen Ergebnissen überein.
Zum Jahreswechsel hat Cathie dann nach
Lösungen für das Jahr 1998
gefragt.
I appreciate to receive
suggestions and hints to further resources.
Back to the
Puzzle Overview.
Back to the
home page of Heiner Marxen.
$Date: 2008/06/02 19:21:13 $