14
But infinity isn't an integer. Since there is no integer $n$ such that $n=n+1$, you're right that the set is empty.
13
If the state of the PRNG is finite, then it has a finite period. (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite. For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.)
In practice, worrying about the period of the ...
13
Here I assume $0\in \mathbb N$. If you disagree start with $105$.
Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order.
Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along ...
13
A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $m∗m=n$. If so, terminate. Otherwise, if $m∗m>n$ reduce the upper bound to $m$, else increase the lower bound to $m$. If the upper bound and the lower bound become ...
12
Shoup (Section 3.3.5, Theorem 3.3, p. 62) gives a bound for computing the residue $r$ in time $O(n\log q)$ where $a = q\cdot p +r$ and $\log a = n$.
I guess that if $p$ and $a$ are both roughly $n$ bit numbers, then $q$ (and hence $\log q$) should be rather small, giving $O(n)$.
If $a$ is an $n$-bit number, and $p$ is relatively small, then the ...
10
The statement is about infinitely many numbers, but its demonstration (or refutation) would have to be a finite exercise. If possible.
The surprise may come from the (false) assumption that finding BB(100) would be a "theoretically easier" problem, only made impossible for practical reasons - since there are so many machines, and they can run for such a ...
9
The idea from the author was that you can write a program in 100 lines (any fixed finite number here) which does the following: takes number x, tests conjecture. If not true then stop else continue on the next number.
Knowing busy beaver number you can simulate this machine for that number of steps and then decide if it halts or not. From above, if it halts ...
9
The advantage in using base 2 is that we know all of the psp's base 2 up to $2^{64}$. It has been verified that none of these psp(2)'s passes a Lucas test when the parameters $P, Q$ are chosen in accord with any of the methods in the Baillie/Wagstaff paper.
If you choose a random base, there might be some composite $n$ that passes both the Fermat and Lucas ...
8
Aaronson has recently expanded in detail on this musing/ idea here working with Yedidia.[1] they find an explicit 4888 state machine for the Goldbachs conjecture. you can read the paper to see how it was constructed. TMs are rarely constructed but those that have been tend to be compiler-like based on high level languages and the compilers add many states. a ...
7
The function $\log^\ast$ ("log-star", iterated logarithm), which shows up in complexity theory, is exactly the number of applications of $\log$ which reduce a number below some constant.
(Confusingly, in information theory the same notation is used for the function $\log + \log\log + \log\log\log + \cdots$.)
6
Consider a weighted, directed graph, with a vertex $v_i$ for $i\in\mathbb{N}$. There is an edge with weight $j-i$ from $v_i$ to $v_j$ if $j\in\{3i,5i,7i\}$.
Now run Dijkstra's shortest path algorithm. It will expand exactly the nodes from your sequence and do so in order. This gives an $n\log n$ algorithm to enumerate the first $n$ elements, since the graph ...
6
It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, the answer to your second question is "yes".
For your third question, the answer is "no". Consider the regular language denoted by $1(10)^*0$. This language ...
6
It is possible to improve on your second algorithm by using better algorithms for integer factorization.
There are two algorithms for integer factorization that are relevant here:
GNFS can factor an integer $\le C$ with running time $O(L_C[0.33,1.92])$.
ECM can find a factors $\le n \log C$ (if any exists) with running time $O(L_{n \log C}[0.5,1.41])$; ...
6
Your intuition is exactly right. Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$. The reason why it works is exactly the interpolation theorem for finite fields.
$k$-wise independent basically means "it behaves like a perfect hash function, if you only feed it $k$ inputs" or "it behaves like a perfect hash function, as far as ...
6
This isn't really computer science...
You create a table d where you store the sum of the divisors of k, for k = 1 to M, where M = $5 · 10^6$. That's the part that is time critical. Then you create a table s where you store the sum of divisors for all 1 ≤ j ≤ k, for k = 1 to M. That's easy, $s_0 = 0$, $s_{k+1} = s_k + d_{k+1}$. And then f (L, R) = $s_R - s_{...
6
In short: we don't know :-)
There is a ((very) little) chance that the Collatz sequence is Turing complete (with probably some caveats like in the case of Two-counter Machines); i.e. there is an algorithm which for every turing machine $M$ outputs an $x$ such that:
$Collatz(x)$ is on a divergent trajectory if and only if $M$ doesn't halt on empty tape
in ...
6
Here is a general solution for the following problem:
Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$.
Let $n$ be the length of $m$ in bits (so $n = \Theta(\log m)$). If $2^b > m$ then there is no point to check any $b_0 > b$, hence we only need to check $O(\log m) = O(n)$ many ...
6
As far as we know there is no efficient way to do that. Such a way would constitute a break of the DSA scheme, and no break of the DSA is known. In particular, DSA is believed to be secure, so it is believed that no efficient algorithm for this exists.
If you only want to do it for small numbers, you can just use brute force and try all possible values of ...
6
Consider the language
$$
L = \{ 0^{m^k} : m \geq m_0 \}.
$$
Since $m_0$ and $m_0+1$ are relatively prime, so are $m_0^k$ and $(m_0+1)^k$. Hence every large enough integer is a non-negative integer combination of $m_0^k$ and $(m_0+1)^k$, implying that
$$L^* \supseteq \{ 0^m : m \geq M_0 \}$$
for some $M_0$, and so $L^*$ is regular. Using the classical formula ...
5
The continued fraction algorithm is easy enough to implement. The first step is to compute the continued fraction of the input $x = [c_0;c_1,\ldots]$. You start with $x_0 = x$, and use the recurrence $c_i = \lfloor x_i \rfloor$, $x_{i+1} = 1/(x_i - c_i)$. You stop when $x_i - c_i$ is "small enough". The next step is to compute the convergent of the continued ...
5
Computation with large integers is one of the topics of Knuth's "Seminumerical Algorithms" (volume 2 of "The Art of Computer Programming"). Results in elementary number theory, like the properties of modular arithmetic, the Chinese Remainder Theorem, Fermat's little theorem/Euler's theorem are critical here.
As commented, this operation is central in ...
5
Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)[x]$.
For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.
If $p,q$ are $r$ bits long, this polynomial ...
5
Idea: Count explicitly how many factors $2$ the numbers in $[1..n]$ contribute to $n!$.
Observe that every other number adds one (the even numbers), every fourth adds another (those divisible by four), every eighth another, and so on.
Hence, the number $\#_2(n!)$ of factors $2$ in $n!$ fulfills
$\qquad\displaystyle\begin{align*}
\#_2(n!) &\leq \sum_{...
5
You are completely right, and your algorithm is a randomized polynomial time algorithm for finding a quadratic non-residue modulo a prime. A major open question in algorithmic number theory is finding a quadratic non-residue deterministically in polynomial time. This is possible assuming the generalized Riemann hypothesis, but unknown unconditionally. It is ...
5
Let me start with a counterexample where your algorithm gives the wrong answer: i.e., where $N$ is composite but your algorithm concludes it is prime. Suppose $N=91$ and $a=9$. Then $a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$, so $a$ passes your check to be a QR. Also, $a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$ and $81^2 \equiv 9 \pmod{91}$, so this passes ...
5
Notice that with the mod operator ($\%$), you're using integer division, much as you are when you use the division operator ($/$) with two ints (at least in most (all?) C style languages). So $3/5$ gives the result of $0$, $7/5$ gives $1$. It's essentially the old kindergarten division - "how many times does five go into three".
Now $\%$ then provides the ...
5
As D.W. pointed out there should be some kind of recurrence involving the $\tau$ function. Turn's out there is, let us again look at the $\tau$ function series, the first few terms are
$$3,6,8,11,14,16,19,21.... \; \;(1)$$
Now let us look at the difference between consecutive terms of the series,
$$3,2,3,3,2,3,2..... \; \; (2)$$
Turns out sequence $(2)$...
5
"Numerical stability" is a much vaguer term than most people realise. We typically use it when referring to an approximation method, such as some kind of linear analysis, or numeric quadrature, or solving (possibly partial) differential equations. It refers to the property that given some appropriate assumptions (e.g. the inputs are reasonable), the ...
5
Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating.
Since the numbers are mutually co-prime, each prime number p is a factor of at most one element of S. On the other hand, if p is small enough then a number could have a factor $p^2$, $p^3$, $p^4$ ...
5
References for the test:
Pomerance, Selfridge, Wagstaff, "The Pseudoprimes to 25 x 10^9", July 1980. Page 1024-1025, Check if n is a strong probable prime base 2. Check whether n is a Lucas probable prime using method A (Selfridge) or B. The authors offer $30 to the first finder of a counterexample or proof of non-existence. It references the next paper ...
Only top voted, non community-wiki answers of a minimum length are eligible
