2022 Developer Survey is open! Take survey.
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 ...
user avatar
  • 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.
user avatar
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$. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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,...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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)...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar
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 ...
user avatar
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^...
user avatar
  • 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 (...
user avatar
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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 33.1k

Only top scored, non community-wiki answers of a minimum length are eligible