15
votes
How can I generate first n elements of the sequence 3^i * 5^j * 7^k?
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 ...
- 27.2k
14
votes
Accepted
What does the set {n | n is an integer and n = n + 1} represent?
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.
- 80.1k
13
votes
Accepted
Why is the set of perfect squares in P?
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$. ...
- 1,453
11
votes
Goldbach Conjecture and Busy Beaver numbers?
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 ...
- 3,246
9
votes
Goldbach Conjecture and Busy Beaver numbers?
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 ...
- 1,086
9
votes
More details about the Baillie–PSW test
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 ...
8
votes
Goldbach Conjecture and Busy Beaver numbers?
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 ...
- 10.8k
7
votes
Accepted
How to solve recurrences with transcendental terms?
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,...
- 269k
6
votes
Accepted
Determining if (infinite) binary language DFAs contain at least 1 prime?
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, ...
- 14.5k
6
votes
Least Common Non-Divisor
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 ...
D.W.♦
- 140k
6
votes
Accepted
Is the following intuition valid for understanding $k$-wise independent hash functions?
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 ...
D.W.♦
- 140k
6
votes
Sum of divisors summatory function with Erathosthenes' sieve
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 ...
- 24.9k
6
votes
Accepted
How to compute the sum of this series involving golden ratio, efficiently?
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,...
- 2,851
6
votes
Accepted
Is it computable if a particular number follows the Collatz conjecture?
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 ...
- 12.2k
6
votes
How to find the closest N to the power of X to the given number?
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$ ...
- 269k
6
votes
Accepted
Computation of discrete logarithm
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 ...
D.W.♦
- 140k
6
votes
Accepted
Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular
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 ...
- 269k
5
votes
Proving that $2^n$ does not divide $n!$
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)...
- 70.8k
5
votes
Quick calculation for $(x^y) \bmod z$
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 ...
- 13.6k
5
votes
How can I generate first n elements of the sequence 3^i * 5^j * 7^k?
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....
5
votes
Accepted
How does one find a non-quadratic residue modulo $p$?
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 ...
- 269k
5
votes
Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?
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^...
D.W.♦
- 140k
5
votes
Why does 3 % 5 give 3 in C ? % >(mod )
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 (...
- 17.7k
5
votes
Accepted
Numerical stability of linear interpolation
"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 ...
- 18.8k
5
votes
Accepted
set with maximum sum consisting of mutually co-prime numbers
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-...
- 24.9k
5
votes
More details about the Baillie–PSW test
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 ...
- 574
5
votes
Count numbers less than $x$ co-prime to $p$
There's a very fast method if p has few prime factors. Say p is a prime. Then the numbers co-prime with p are all numbers other than p, 2p, 3p, 4p etc. There are x-1 numbers less than x, and of those ...
- 24.9k
5
votes
Accepted
Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences
Yes. This generalizes to any linear recurrence. Suppose we have the linear recurrence
$$x_{n+1} = a_0 x_n + a_1 x_{n-1} + \dots + a_k x_{n-k}.$$
Define the column vector $v_n = (x_n,x_{n-1},\dots,...
D.W.♦
- 140k
5
votes
Accepted
Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5)
$n^2 + (n + 1)^2 = (n + 2)^2 \Rightarrow n^2 + n^2 + 2n + 1 = n^2 + 4n + 4 \Rightarrow 2n^2 2n + 1 = n^2 + 4n + 4 \Rightarrow n^2 - 2n - 3 = 0 \Rightarrow n = -1, 3$
Therefore, 3 is the only ...
- 233
5
votes
Accepted
Efficient Algorithm to Find the n-th Odious Number
Here is the recursive formula for odious numbers,
$$\begin{align}
a_1&=1,\\
a_{2n} &= 6n-3 -a_n,\\
a_{2n+1} &= a_{n+1} + 2n.
\end{align}$$
The formula can be proved easily by observing, as ...
- 33.1k
Only top scored, non community-wiki answers of a minimum length are eligible