If we're bit sneaky, we can gain our freedom the first day.
We can continually ask the warden a question in this form:
Given $n$ is the number of days you've been on the job, if I select an integer randomly from the range $[\lceil\frac{n-x}{n}\rceil, 1]$ and add it to $\lfloor\frac{n}{2^q}\rfloor$, will the sum be even?
Values for $q$ start at $0$ and increase by $1$ each question. For the first question, $x$ is $1$. For subsequent questions, if the answer to the previous question was "Yes", then $x = x' + 2^q$; if "No", then $x = x' + 2^q - 2^{q'}$.
We continue asking the warden questions of this form until he says "I don't know." Then we tell him that he has been here $x$ days, where the value of $x$ is the one used in the question that he couldn't answer.
The key to this is that $\lceil\frac{n-x}{n}\rceil=1$ when $1 \le x \lt n$ ensuring the random integer is $1$ in these cases. Once $x \ge n$, the random number is no longer restricted to $1$, so the question about the sum being even cannot be answered. But while the answers are "Yes" and "No", this indicates whether $2^q$ is or isn't in the the powers-of-two that sum to $n$. By summing the known powers-of-two in $n$ and adding the next-lowest possible power-of-two, we ensure that $x \le n$ for every question.
Example
The prisoner (P) informs the warden (W) that for purposes of his questions, $n$ is the number of days the warden has been on the job. If the warden has been on the job 73 days, the following would occur:
P: Sets initial value $x=1$ and asks "Is the sum of $\lfloor\frac{n}{1}\rfloor$ and a random integer in $[\lceil\frac{n-1}{n}\rceil, 1]$ even?"
W: Evaluates summing $73$ with a random integer in $[1, 1]$ and replies: "Yes."
P: Sets $x=1+2=3$ and asks "Is the sum of $\lfloor\frac{n}{2}\rfloor$ and a random integer in $[\lceil\frac{n-3}{n}\rceil, 1]$ even?"
W: Evaluates summing $36$ with a random integer in $[1, 1]$ and replies: "No."
P: Sets $x=3+4-2=5$ and asks "Is the sum of $\lfloor\frac{n}{4}\rfloor$ and a random integer in $[\lceil\frac{n-5}{n}\rceil, 1]$ even?"
W: Evaluates summing $18$ with a random integer in $[1, 1]$ and replies: "No."
P: Sets $x=5+8-4=9$ and asks "Is the sum of $\lfloor\frac{n}{8}\rfloor$ and a random integer in $[\lceil\frac{n-9}{n}\rceil, 1]$ even?"
W: Evaluates summing $9$ with a random integer in $[1, 1]$ and replies: "Yes."
P: Sets $x=9+16=25$ and asks "Is the sum of $\lfloor\frac{n}{16}\rfloor$ and a random integer in $[\lceil\frac{n-25}{n}\rceil, 1]$ even?"
W: Evaluates summing $4$ with a random integer in $[1, 1]$ and replies: "No."
P: Sets $x=25+32-16=41$ and asks "Is the sum of $\lfloor\frac{n}{32}\rfloor$ and a random integer in $[\lceil\frac{n-41}{n}\rceil, 1]$ even?"
W: Evaluates summing $2$ with a random integer in $[1, 1]$ and replies: "No."
P: Sets $x=41+64-32=73$ and asks "Is the sum of $\lfloor\frac{n}{64}\rfloor$ and a random integer in $[\lceil\frac{n-73}{n}\rceil, 1]$ even?"
W: Evaluates summing $1$ with a random integer in $[0, 1]$ and replies: "I don't know."
P: States: "You've been on the job $73$ days."
By looking at the binary values for $x$ as the questioning proceeds, we can see that the final answer is built up from the least- to most-significant bit. The bit value is $1$ for "Yes", $0$ for "No", and $1$ for the "Don't know" that also indicates the final value has been determined.
| x (dec) | x (bin) | Response |
|---------+---------+------------|
| 1 | 1 | Yes |
| 3 | 11 | No |
| 5 | 101 | No |
| 9 | 1001 | Yes |
| 25 | 11001 | No |
| 41 | 101001 | No |
| 73 | 1001001 | Don't know |
This method always uses $1+\lfloor log_2(n) \rfloor$ questions, which coincidentally (or not) is the maximum allowed per day.