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$. ...
Denis Pankratov's 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 ...
André Souza Lemos's user avatar
10 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 ...
Robert Baillie's 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 ...
Eugene's user avatar
  • 1,086
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 ...
vzn's user avatar
  • 11k
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,...
Yuval Filmus's user avatar
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.'s user avatar
  • 158k
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 ...
gnasher729's user avatar
  • 29.4k
6 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 ...
Pseudonym's user avatar
  • 22k
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,...
advocateofnone's 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 ...
Vor's user avatar
  • 12.5k
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$ ...
Yuval Filmus's 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 ...
D.W.'s user avatar
  • 158k
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 ...
Yuval Filmus's user avatar
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 (...
Luke Mathieson's user avatar
5 votes

Numerical stability of linear interpolation

According to the document "P0811R2: Well-behaved interpolation for numbers and pointers" (the link @Eric provided), it depends: a+t*(b-a) does not in general reproduce b when t==1, and can ...
Jan Heldal's user avatar
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-...
gnasher729's user avatar
  • 29.4k
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 ...
DanaJ's user avatar
  • 604
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 ...
gnasher729's user avatar
  • 29.4k
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.'s user avatar
  • 158k
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 ...
Shade's user avatar
  • 243
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 ...
John L.'s user avatar
  • 38.8k
5 votes

Efficient Algorithm to Find the n-th Odious Number

Here is an alternative answer, following greybeard's advice. For each $k$, the two integers $2k,2k+1$ contain exactly one odious number. Hence the $i$th odious number is either $2i$ or $2i+1$: it is $...
Yuval Filmus's user avatar
5 votes
Accepted

Is Determining the Number of distinct Prime Factors Polynomial?

No problem involving factorization is known to be polynomial time, and these problems (formulated as decision problems in any reasonable way) are suspected to be NP-intermediate. The only problem ...
Yuval Filmus's user avatar
4 votes
Accepted

How to find the element of the Digit Sum sequence efficiently?

Your sequence is described in oeis.org/A004207 as digits sum. There are some good points like sequence mod 9 has repeating pattern $(1, 2, 4, 8, 7, 5)^\infty$, it shares digital roots with oeis.org/...
Evil's user avatar
  • 9,445
4 votes

How to find the element of the Digit Sum sequence efficiently?

Since you asked for " a new direction or a hint " and I don't know the answer, I'll leave this here, I hope it's helpful. some ideas: It makes sense there would be a pattern mod 9, since $\forall k &...
crackpotHouseplant's user avatar
4 votes
Accepted

How to compute Jacobi symbol efficiently?

The Wikipedia article on the Jacobi symbol describes an efficient algorithm for calculating it which uses quadratic reciprocity and operates similarly to the GCD algorithm.
Yuval Filmus's user avatar
4 votes
Accepted

What is the fastest way to check if an integer is divisible by another?

Integer division The best algorithm known for integer division has running time that is slightly more than linear, i.e., a bit more than $O(n)$. In particular, it is something like $O(n \lg n 2^{\...
D.W.'s user avatar
  • 158k
4 votes
Accepted

Curious about an old algorithm which calculates modular inverse

You can replace: $$ ~~q \leftarrow \Big\lfloor\frac{a - 1}{b}\Big\rfloor $$ $$ r \leftarrow a - q ~b $$ By $q, r \leftarrow \text{divmod}(a, ~ b)$ Algorithm terminates in even number of steps ...
Aristu's user avatar
  • 1,483

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