Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithms
Search options questions only
not deleted
user 6043
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
1
vote
3
answers
494
views
Differences of squares
Suppose I wanted to express a number $N$ as a difference of squares. For large $N$ this is in general difficult, as finding $N=a^2-b^2$ leads to the factorization $N=(a+b)(a-b)$. Even if the problem i …
- 9,114
11
votes
3
answers
2k
views
Mertens' function in time $O(\sqrt x)$
At the least, I would expect a mention that previous algorithms were slower. …
- 9,114
16
votes
4
answers
2k
views
Bounds on squarefree numbers
Let $q_1,q_2,\ldots$ denote the squarefree integers 1, 2, 3, 5, .... What effective bounds are known for $q_n$? Clearly
$$q_n\sim\zeta(2)n$$
but I need hard inequalities. Of course from the above t …
- 9,114
3
votes
2
answers
865
views
Efficiently finding the largest divisor of N less than sqrt(N)
Suppose you have a number
$$
N = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, A060775$(N)$.) How can I efficiently find this $d$?
If …
- 9,114
10
votes
2
answers
3k
views
Can a number be factored quickly, given the sum of its prime factors?
This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ha …
- 9,114
4
votes
1
answer
491
views
Can we count primes in residue classes quickly?
Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in tim …
- 9,114
5
votes
4
answers
2k
views
Determining a recurrence relation
I would like to solve the general problem of determining a linear recurrence relation that fits a given integer sequence of length $n$, or stating that none exists (with fewer than $n/2-k$ coefficient …
- 9,114
6
votes
1
answer
367
views
Speeding the quadratic sieve with an oracle
Algorithms, heuristics, and reductions to known hard problems would be welcome. You may assume that $k$ and $b$ are reasonable: there are $\gg k$ solutions. …
- 9,114
1
vote
1
answer
321
views
Number of biquadrates mod n
Is there an explicit formula for the number of fourth powers mod n?
Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for higher …
- 9,114
4
votes
0
answers
180
views
Computing the density of a set of multiples
Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ of posi …
- 9,114