Output: Standard Output
Time Limit: 2 Seconds
One of the biggest, most mathematicians
would call it THE biggest, unsolved problems in mathematics is the proof of the
Riemann Hypothesis: "All non-trivial zeros of the zeta function have real
part one-half". Now your task is simple: For any natural number N, give
the Nth zero... nah, just kidding! That would be a much too complex problem for
an online contest. We'll leave Riemann and the zeta function and concern
ourselves with the closely related, but much easier to calcultate Mertens's
function. For those interested in the subject I can heartly recommend
Derbyshire's book (see the epilogue).
Every positive natural number greater than
1, can be uniquely decomposed into it's prime factors. Some numbers have only
one factor, namely the number itself, like 2, 11 and 71, and are caled prime
numbers. Others have more than one factor, like 4 (2x2), 15 (3x5) and 144
(2x2x2x2x3x3), and are called composite numbers. If a number contains all it's
prime factors only once, it is called square free. All prime numbers are square
free. Some composite numbers are square free, like 21 (3x7) and 187 (11x17),
others are not, like 9 (3x3) and 98 (2x7x7).
Let's define the Mobius function mu(N), for
all positive natural numbers N:
Now we can define Mertens's function M(N)
as the sum of all mu() for 1 up to and including N:
M(N) = mu(1) + mu(2) + ... + mu(N).
The first 20 values for both functions are
in this table:
|
N |
factors |
mu(N) |
M(N) |
|
1 |
- |
1 |
1 |
|
2 |
2 |
-1 |
0 |
|
3 |
3 |
-1 |
-1 |
|
4 |
2 2 |
0 |
-1 |
|
5 |
5 |
-1 |
-2 |
|
6 |
2 3 |
1 |
-1 |
|
7 |
7 |
-1 |
-2 |
|
8 |
2 2 2 |
0 |
-2 |
|
9 |
3 3 |
0 |
-2 |
|
10 |
2 5 |
1 |
-1 |
|
11 |
11 |
-1 |
-2 |
|
12 |
2 2 3 |
0 |
-2 |
|
13 |
13 |
-1 |
-3 |
|
14 |
2 7 |
1 |
-2 |
|
15 |
3 5 |
1 |
-1 |
|
16 |
2 2 2 2 |
0 |
-1 |
|
17 |
17 |
-1 |
-2 |
|
18 |
2 3 3 |
0 |
-2 |
|
19 |
19 |
-1 |
-3 |
|
20 |
2 2 5 |
0 |
-3 |
We want you to calculate mu(N) and M(N) for
some values of N.
Up to 1000 numbers between 1 and
1000000 (one million), both included, each on a line by itself. The numbers are
in random order and can appear more than once. Input is terminated by a line,
which contains a single zero. This line should not be processed.
For each number in the input print that number, the value of mu() for that number and the value of M() for that number, all three on one line, right justified in fields of width 8. The input order must be preserved.
|
20 1 144 73 0 |
20 0 -3 1 1 1 144 0 -1 73 -1 -4 |
Problemsetter: Joachim
Wulff (aka Little Joey)
Special Thanks: Shahriar
Manzoor, EPS
The zeta function can be defined as the infinte sum:
zeta(s) = 1 + 2^(-s) + 3^(-s) + 4^(-s) + etc.
s can be any complex number.
The zeta function has many zeros (values of s for which zeta(s)=0). For some of them, the non-trivial ones, Riemann in 1859 conjectured that the real part of s should always be exactly one-half. The imaginary part can have any value. Many zeros have been found so far, all with real part one-half, but no one was ever able to prove (or disprove) the conjecture. This now famous Riemann Hypothesis has many corollaries in all fields of mathematics (and beyond); many theorems are based on the fact that the hypothesis is true, so whoever disproves it (one counter example is enough), would make a ruin of modern mathematics!
One way to prove the hypothesis, would be to prove that the Mertens's function is bounded by the square root of it's argument: M(N) = O(sqrt(N)), where O stands for the big-oh notation, which means that for big enough N, the absolute value of M(N) will never exceed sqrt(N). This is never proved, but if it's true, the Riemann Hypothesis is true (don't ask me why).
This, and much more, can be found in the excelent book "Prime Obsession" by John Derbyshire, a mathematical, biographical and historical account of the Riemann Hypothesis. Very readable, also for mathematical laymen like myself.