# Tag Info

0

The property $p\in B$ is decidable, just run a Turing machine which tests $p$ and $p+2$ for being prime numbers. This machine will definitely give you a result (either way) and thus decide whether $p\in B$ or $p\notin B$. For the other set $A$: If there are infinitely many twin primes, then $A$ would be empty by definition (i.e. there is no largest twin). ...

1

This is a special case of a previous problem I proposed and partially solved: If $T(n) = un + \sum_i T(\lfloor r_i n \rfloor)$, show that $T(n) = \Theta(n)$ My solution there does show that $T(n) = \Theta(n)$ and conjectures that $\dfrac{T(n)}{n} \to 2^k$.

2

This can be done with the Akra-Bazzi method. Using Wikipedia's notation, the setup is \begin{eqnarray*} a_i \equiv 1 \\ b_i = 2^{-i} \\ h_i(x) \equiv 0 \\ g(x) = x \\ \end{eqnarray*} The next step would be to solve $$f(p) \equiv \sum_{i=1}^k 2^{-ip} = 1$$ for $p$. But in this particular case we don't need to know what $p$ is. All we need to know is that ...

1

We can solve another closely related recurrence that admits an exact solution and makes it possible to get precise bounds. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = n + \sum_{q=1}^p T(\lfloor n/2^q \rfloor).$$ Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Then ...

0

By way of enrichment we solve another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 4 T(\lfloor n/2 \rfloor) + n^2.$$ Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Then we can unroll the recurrence to ...

1

There is a combinatorial identity used to count the ways $n$ identical objects can be distributed among $k$ distinct boxes. $$\#d = \binom{n+k-1}{k-1} = \binom{n+k-1}{n}$$ To see this, imagine we line up the $n$ items in a long row. Now, we designate each item to a box in the following way: 1) Place $k-1$ dividers between the ...

1

This is a classic counting reasoning, although I'm not sure about how the thesis was done. You want to compute the number of different states of the game. The way I see it: you sum on the total number of armies, because you need to have at least one army on each territory. you cannot have less armies than the number of territories, which is why you start ...

3

The algorithm says to return $d$ if $\lceil q\rceil=q$. In your case, $\lceil q\rceil\ne q$, so we proceed to the "else" part of the statement instead of returning $d$.

0

Your proof is on the right track. These pumping lemma questions end up being proof by contradiction. So, we first must assume something, then contradict it. Here we will assume the $L$ is regular, then get a contradiction. Here is a detailed proof below. The basic idea is we choose a string long enough so that the $y$ in the pumping lemma only had the letter ...

1

The simbology is not so clear to me, but I think that, basically, we have that the conjunct $T_i$ in the $k$-CNF is a disjunction of literals : i.e. boolean vars or negated boolean vars. I assume that the variables $x_j$ are the boolena variables; if so, they occur into $T_i$ as is or negated. We introduce an "auxiliary" function $a_i$ associated to $T_i$ ...

2

Donald Knuth is a mathematician who defined modern computer science. You are looking for his book "The Art of Computer Programming." Be warned though, it is a very challenging book to read. Another book that covers combinatorics and has a chapter on algorithms and algorithmic complexity would be Miclos Bona's "A Walk through Combinatorics," if you want ...

2

Two standard books are Introduction to the Theory of Computation by Michael Sipser and Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft et al. Both follow the standard format of definition, theorem and example. You can't go wrong with either of them.

1

If you can do this in time $O(f(n))$, then you can factor semiprimes (i.e., $n$ of the form $pq$, where $p$ and $q$ are both primes) in time $O(f(n)\log n)$. To see this, note that if $n=pq$ (with $p<q$), then for all $b<p$, the number of divisors of $n$ less than or equal to $b$ is odd (just $1$), whereas if $p\leq b < \sqrt{n}$, then the number of ...

0

Not an answer, but it must be formatted in a way that a comment cannot hold. If you continue reading, the author defines this notation: Here, $\langle \cdot \rangle_q$ means the expectation or mean under the density $q$ and $D(\cdot\ ||\ \cdot)$ is the cross-entropy or Kullback-Leibler divergence between the two densities. I have taken ...

0

In addition to martini's answer, it's also useful to write that $n = e^{\log n} = o(\log n ^{\log n})$ because essentially as $n \to \infty \ \frac{f_1(n)}{f_2(n)}$ converges to $0$, so $f_1(n)$ is of a lesser order than $f_2(n)$.

0

The question is, wheter $n$ can be written as $n = f(n)^{\log n}$ where $f$ is a function such that $f\in O(\log)$. This is true, as $$n = 2^{\log n}$$ an the constant function $f(n) := 2$ has $f \in O(\log)$ as $\log$ is unbounded.

2

Assuming $k,n \in \mathbb{Z}_{>0}$ throughout. X(n) $$\ln n = \int_{1}^n \frac{\mathrm{d}x}{x} \leq \sum_{k=1}^n \frac{1}{k} \leq 1+\int_{1}^{n-1}\frac{\mathrm{d}x}{x} = 1+ \ln (n-1) < 1+\ln(n)$$ Therefore $X(n) \in O(\log n)$. Y(n) We find the largest possible value of the summand by finding the largest possible value of the expression as if the ...

0

I don't know how to use the integral test. As suggested by @Eric and others, I am trying to answer my question. $$$$\begin{split}1\leqslant k\leqslant n&\Leftrightarrow\dfrac{1}{n}\leqslant \dfrac{1}{k}\leqslant 1\\&\Leftrightarrow1\leqslant X(n)\leqslant n\\&\Rightarrow X(n)\in\cal{O}(n).\end{split}$$$$ which is ...

0

The halting set $K = \{e \mid \varphi_{e}(e) \downarrow\} \subset \mathbb{N}$ is not many-one reducible to its complement. For if it were, that is if there were a total computable $f\colon \mathbb{N} \to \mathbb{N}$ such that $x \in K \Leftrightarrow f(x) \notin K$, then we could decide if $e \in K$ by simultaneously watching $\varphi_{e}(e)$ and ...

3

Let us consider the more general case of the equation $$x \log(x)=n$$ As mentioned by user1337, almost from definition, the solution is given by Lambert function $$x=\frac{n}{W(n)}$$ Now, let us consider the case where $n$ is just huge as in your case. There are quite good approximations of Lambert function for such a case. For example, $$W(n) \simeq ... 1 The solution can be expressed in terms of the Lambert W function as:$$n=\frac{1000000000 \log (2)}{W(1000000000 \log (2))} \approx 3.96201\times 10^7.

-1

There are $64^3 = 262144$ bits, so that there are only $2^{262144}$ possible cubes, which is around $10^{79000}$. Thus, it's not very feasible to do any sort of computation involving looping over all possible cubes.

Top 50 recent answers are included