In contrast with other programming languages from its time, Pascal (the programming language)
also supports a set type, implemented as a bit pattern. The bit patterns associated with
the Pascal set type are $256$ bits wide, but this limitation is not essential and can been replaced
with other (larger) values eventually.
See Wikipedia for a reference.
A rather detailed description of the set type implementation can be found
as well .
So we have the following practice:
- a bit pattern in a computer is a set type
We also know that
- a bit pattern in a computer is a natural number type
Indeed, everybody knows that a natural number can be represented as a binary i.e. a bit pattern.
The word "type" has been employed here in order to avoid confusion with other
(i.e the standard mathematical) "set" and "number" definitions.
More precisely: the
hereditarily finite sets
are in one-to-one correspondence with the natural numbers. And the latter fact is independent of
computers.
Examples.
$$
\begin{array}{l}
0 = 000 = \{\} \\
1 = 001 = \{0\} = \{\{\}\} \\
2 = 010 = \{1\} = \{\{\{\}\}\} \\
3 = 011 = \{0\; 1\} = \{\{\}\{\{\}\}\} \\
4 = 100 = \{2\} = \{\{\{\{\}\}\}\} \\
5 = 101 = \{0\; 2\} = \{\{\}\{\{\{\}\}\}\} \\
6 = 110 = \{1\; 2\} = \{\{\{\}\}\{\{\{\}\}\}\} \\
7 = 111 = \{0\; 1\; 2\} = \{\{\}\{\{\}\}\{\{\{\}\}\}\} \\
\cdots
\end{array}
$$
The above is related to the following reference, by Alexander Abian and Samuel LaMacchia:
If the curly brackets $\{\}$ are replaced by square brackets $\left[\,\right]$ then another
important fact is observed:
- a set type is is a natural number type is a sorted natural numbers array type
If now we devise
an equivalent of the elementary number operations with sorted arrays,
then we have virtual unlimited precision at our disposal. That this approach indeed works, shall be demonstrated at hand of the OP's question.
Here is a link to the complete (Delphi Pascal) program that does the job:
And here is a link to the number $3^{100000}$ itself, which is too large to fit into
MSE's margins:
The screen output of the program is the number of digits, the first, the middle and the last digit:
47713
1 2 1
So, indeed, as
Lucian says in a comment: it's "obvious" that the digit in the middle is a $\large\, 2$ .
Note. A power like $\,3^{100000}\,$ sounds quite impressive, but with a smart
algorithm, the number of operations is only $\,\ln_2(100000)\approx17$ . For
real numbers $\,x\,$ and a natural $\,n\,$ it goes as follows:
function power(x : double; n : integer) : double;
var
m : integer;
p, y : double;
begin
m := n; y := x; p := 1;
while m > 0 do begin
if (m and 1) > 0 then p := p * y;
m := m shr 1; { m := m / 2 }
y := y * y;
end;
power := p;
end;
Wikipedia reference:
Efficient computation with integer exponents .
BONUS. In view of the above, the following answer is interesting:
Reference is made to a
paper by Kaye and Wong,
where on page 499 we read:
It was observed in 1937 by Ackermann [1] that $\mathbb{N}$ with the membership relation
defined by
$n \in m$ iff the $n$th digit in the binary representation of $m$ is $1$
satisfies ZF$-$inf. This interpretation, formalized in ZF with $\omega$ in place of $\mathbb{N}$
yields a bijection between $\omega$ and the collection $V_\omega$ of hereditarily finite sets.
Your definition of the complexity class NP is not quite correct. In fact, P is a subset of NP -- any problem that lies in P, also lies in NP. The formal definition is the set of problems solvable by a non-deterministic Turing machine in time (number of steps) bounded by a polynomial in the size of the input. In fact, this already implies that it can be solved only an ordinary Turing machine in exponential time, so that part is redundant. The informal formulation of this, is that if you have an oracle which presents you with a 'potential solution', then you can check it in polynomial time: namely, the oracle says which of the possibilities of the non-deterministic Turing machine is the "right" one.
Your definition of the TSP problem is also not quite correct (although people are often imprecise about this). In the common formal formulation of classes like P and NP, they contain only decision problems: that is, programs which should output true or false. Then the travelling sales person problem is presented as follows:
Given a complete weighted graph of $n$ vertices, and a number $k$, does there exist a path through all vertices which has total weight at most $k$?
In this formulation, you can see that it is easy to verify a potential solution: just add up the weights. Also note that it is easy to find the length of a shortest path if you can efficiently solve the above problem by doing a binary search to determine the optimal number $k$.
Since, like with most NP problems that we do not expect to be in P, we do not know of any better way of getting the answer than "trying all possibilities", this problem often feels equivalent to actually producing a shortest path, and it gets talked about as if it is. But technically, it is not.
Best Answer
Supposing $b > 1$ and $x \geq 1$, the pseudocode algorithm
returns $\lfloor \log_b x \rfloor$. (CS aside: If $b$ is an integer, this gives an exact result when all variables have type
int. If the variables have type, e.g.,float, possibly this algorithm can suffer from rounding errors.) For any $x$ the while loop is run $\lfloor \log_b x \rfloor + 1$ times, so this algorithm has complexity $O(\log x)$ in $x$.