The 2024 Developer Survey results are live! See the results

Tag Info

Hot answers tagged number-theory

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,483

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,276

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 ...

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 ...
• 11.1k

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,096
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,...
• 278k

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 ...
• 31.2k
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 ...
• 22.6k
Accepted

• 1,483

Subset Sum problem with many divisibility conditions

This problem can be solved in polynomial time using linear programming, and this is actually true for any partial order $(S,\le)$. By the way, we can prove by induction that for any finite partial ...
• 366
Accepted

• 31.2k

Which is the fastest method for calculating exact square root of a integer of 200-500 digit number?

It seems a bit surprising that you did not find the Wikipedia article on integer square root where the Newton's algorithm is described in detail. Here is the implementation in Python: ...
• 30.9k

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