Each of the positive integers $1,2,\dots,n$ is colored in one of the colors red, blue or yellow regarding the following rules:
(1) A Number $x$ and the smallest number larger than $x$ colored in the same color as $x$ always have different parities.
(2) If all colors are used in a coloring, then there is exactly one color, such that the smallest number in that color is even.
Find the number of possible colorings.
To solve this problem, we need to determine the number of possible colorings of the integers \(1, 2, \ldots, n\) using three colors (red, blue, yellow) under the given rules. Let's denote the number of such colorings by \(a_n\).

### Step 1: Understanding the Rules
1. **Parity Rule**: A number \(x\) and the smallest number larger than \(x\) that is colored the same as \(x\) must have different parities. This means if \(x\) is even, the next number of the same color must be odd, and vice versa.
2. **Color Usage Rule**: If all three colors are used, exactly one color must have its smallest number as even.

### Step 2: Establishing the Recursive Formula
We need to show that:
\[ a_n = 2a_{n-1} + 3 \]

### Step 3: Base Case
For \(n = 1\), we have three possible colorings (one for each color):
\[ a_1 = 3 \]

### Step 4: Recursive Step
Assume the formula holds for \(n\). We need to show it holds for \(n+1\).

#### Case 1: Using Two Colors
If we use only two colors, the parity rule must be satisfied. For \(n\) numbers, there are \(a_{n-1}\) valid colorings. When we add the \((n+1)\)-th number, it can be colored in two ways (either of the two colors used). Thus, we have:
\[ 2a_{n-1} \]

#### Case 2: Using Three Colors
If we use all three colors, the smallest number in one of the colors must be even. For \(n\) numbers, there are \(a_{n-1}\) valid colorings. When we add the \((n+1)\)-th number, it can be colored in three ways (one for each color). However, we need to ensure that the smallest number in one color is even. This adds an additional 3 valid colorings:
\[ 3 \]

Combining both cases, we get:
\[ a_n = 2a_{n-1} + 3 \]

### Step 5: Solving the Recurrence
To find a closed form for \(a_n\), we solve the recurrence relation:
\[ a_n = 2a_{n-1} + 3 \]

We can use the method of characteristic equations or iterate the recurrence to find a pattern.

#### Iteration:
\[ a_1 = 3 \]
\[ a_2 = 2a_1 + 3 = 2 \cdot 3 + 3 = 9 \]
\[ a_3 = 2a_2 + 3 = 2 \cdot 9 + 3 = 21 \]
\[ a_4 = 2a_3 + 3 = 2 \cdot 21 + 3 = 45 \]

We observe that:
\[ a_n = 3 \cdot 2^n - 3 \]

### Step 6: Verification
We verify by induction:
- Base case: \(a_1 = 3\)
- Inductive step: Assume \(a_k = 3 \cdot 2^k - 3\). Then:
\[ a_{k+1} = 2a_k + 3 = 2(3 \cdot 2^k - 3) + 3 = 6 \cdot 2^k - 6 + 3 = 6 \cdot 2^k - 3 = 3 \cdot 2^{k+1} - 3 \]

Thus, the formula holds by induction.

The final answer is \( \boxed{ 3 \cdot 2^n - 3 } \)