New answers tagged algorithms
0
If you’re talking about rates of growth, $\sum_{i=1}^{100}\frac12=50$ is $\Theta(1)$, as is $100\left(4+\frac1n\right)$. Assuming that $\lg$ is the binary log, $n\le\sum_{i=1}^{\lg n}2^i\le 2n$ for $n\ge 1$, so $\sum_{i=1}^{\lg n}2^i$ is $\Theta(n)$, as is $\frac{n^2+\lg n}n=n+\frac{\lg n}n$. And $\frac{n^2}2+n\lg n$ is $\Theta(n^2)$, as is $5n(4+2^{\lg ...
3
For readability I'll write $[a_1,a_2,\ldots,a_n]$ for the tower $a_1^{a_2^{a_3^\cdots}}$.
Let all of the $a_i,b_i$ be in the interval $[2,N]$ where $N=2^K$ (if any $a_i$ or $b_i$ is 1 we can truncate the tower at the previous level, and the inputs must be bounded to talk about complexity).
Then consider two towers of the same height
$$
T=[N,N,\ldots,N,x] ...
1
Hint: for what $s$ will the loop terminate the next time through? You need $s=0$ at the end of the loop. How about trying it for $n=1$ through $8$?
3
I see no reason to assume that the number of elements is divisible by $3$; so I'll work with $m$ elements, where $m$ is your $3n$. This answer has gone through a lot of edits; I now have a complete answer for all $m$.
For $m \equiv 1$ or $3 \bmod 6$, the answer is $(m^2-m)/6$. For $m \equiv 5 \bmod 6$, the answer is $(m^2-m-8)/6$. For $m$ even, the answer ...
6
My approach is similarly numeric to Leonid's, but more precise and perhaps easier to analyse. It supports real exponents > 0.
The idea is to represent power towers as a single floating point number with $n$ exponentiations: $(x\mid n) := exp^n(x)$. Normalizing $x\in[0,1)$, this format allows easy comparison between numbers.
What remains is a way to ...
0
Are these two problems related at all?
The answer is yes, and it is at many levels. The general number field sieve, which is generally thought of as a factoring algorithm, is also very useful for solving discrete logs.
Theoretically:
Solving the discrete log with a composite modulus is exactly as hard as factoring [3]. However, it is not known if ...
0
if there are only number of vertices and their corresponding degree known, can we check if the graph contains at least a cycle?
Do you mean a complete cycle (Hamiltonian) or any cycle at all? Vertex degrees fail in some strong ways for the problem of a complete cycle, because degree-based tests are too fast to be able to solve NP-complete problems. To ...
0
Suppose $U$ is an exponentially distributed random variable and $\Pr(U>u)=e^{-au}$ for $u>0$ (and $\Pr(U>u)=1$ for $u\le 0$). Then
$$
\Pr(e^U > x) = \Pr(U > \log_e x) = e^{-a\log_e x} = x^{-a} \text{ for }x>1,
$$
so $e^U$ is a Pareto-distributed random variable. If you want the cutoff to be a positive number other than $1$, then just ...
1
Here is a very simple proposal :) Note that this can totally converge to a local minimum, so if you want to be confident that you're as close as possible to the best solution, you should run the whole procedure several times, and select the one with the smallest energy... Not great, but it's not an easy problem :/
To answer your last comment, this has ...
1
In this case, I'm afraid you just have to go ahead and calculate $2^{1000}$. There are various clever ways to do this, but for numbers this small a simple algorithm is fast enough.
The very simplest is to work in base 10 from the start. Faster is to work in binary, and convert to base 10 at the end, but this conversion is not completely trivial. A ...
3
The smallest denominator $q$ is $q=44$ corresponding to $$\frac pq=\frac{35}{44}=0.795\overline{45}$$
To see this, note that
$$ \frac ab=\frac{31}{39}=0.79487\ldots$$
is too small and
$$\frac cd=\frac{4}{5}=0.8$$
is too big.
For any fraction with $\frac ab<\frac pq<\frac cd$, we have
$$\frac pq-\frac ab=\frac{bp-aq}{bq}>0\qquad\frac cd-\frac ...
3
This is solved with continued fractions. Your specific example $0.795$ is the continued fraction $[0;1,3,1,7,5]$. It has convergents (best approximations) $0,1,\frac{3}{4},\frac{4}{5},\frac{31}{39},\frac{159}{200}$.
$\frac{4}{5}=0.8$ is pretty good, and $\frac{31}{39}=0.7948718\ldots$ is even better.
1
If you have an $n$-vertex graph with $n$ or more edges, there must be a cycle. You can calculate the number of edges from the degree sequence using the Handshaking Lemma.
If the $n$-vertex graph has $n-1$ or fewer edges, provided there are two vertices of degree $2$ or more, it may contain a cycle (or it may not). For example, these two graphs have the ...
0
If we are given that a graph $G$ has 9 vertices with degrees $(2,2,2,1,1,1,1,1,1)$, then we cannot determine if $G$ has a cycle or not, since there exist two graphs $G_1,G_2$ with the given properties where the first has a cycle and the second does not. The graph $G_1$ consists of the union of a triangle and three path graphs of two vertices, while the graph ...
0
Thinking out aloud ;)
If you arranged the numbers in all possible ways noting you must have at least 2 numbers and incriminating to the maximum selected.
Then reproduce each number set with the = in each valid location. This would be your starting point.
Where you can then place the selected modifiers in each valid place.
First one at a time.
Then ...
1
Note that $$\sum_z P[z|X,\theta_n] \ln P[X,z|\theta] \\=\sum_\color{red}z\bigg(\ln P[X,z|\theta]\bigg)\color{red}{P[z|X,\theta_n]} \\=E_{Z|X,\theta_n}\bigg(\ln P[X,z|\theta]\bigg)$$ Here probability distribution is $P[z|X,\theta_n]$ and summing over $z$. So, by the definition of expectation we get the desired result.
1
Let $x_i$ be the number of times you push button $i$. You'll only ever push it $0$ times or $1$ time, so be can take $x_i$ to be modulo $2$.
You would like light 1 to go from OFF to ON. When we examine the chart in the link in your comments, we can only affect light 1 by switching buttons 25 or 36. This yields an equation: $$x_{25}+x_{36}\equiv1$$ so that ...
0
Take any pair of input vectors which are not identical. Their difference is the direction of the line, and either of these two is a start point.
For all other points, subtract the start point and check whether the result is an exact multiple of the direction vector.
1
You are interested in the asymptotic behaviour; you can show that any $T$ satisfying the second relation is monotone (increasing), and then you can use the "sandwiching" theorem to relate solutions to the second to solutions to the first —up to some term which will, in hindsight (once you have the solution to the first relation) prove to be negligible.
1
This is a particularly simple variant of what is known as the coin problem. Here's a dynamic programming solution that runs in time linear in $t$. We use an array $m[0\dots t]$ of booleans, which I'll refer to as either T or F. The value of $m[i]$ will represent whether or not $i$ can be represented as the sum of zero or more copies of $a, b, c$. We will ...
0
You can easily sovle this problem with dynprog, if it is nessesary. It is $O(t)$. There are for sure much better algorithms, but your question has a tag "dynamic-programming"...
http://pastebin.com/QN2BJL17
8
Recently I asked a very similar question at Mathematica.SE.
I assume you know it, because you participated in the discussion.
Leonid Shifrin suggested an algorithm that solves this problem for the majority of cases, although there were cases when it gave an incorrect answer. But his approach seems correct and it looks like it is possible to fix those ...
0
Do you something about the nature of your differential equation? One that involves exponential forms may be very efficiently approximated using exponentials in a way similar to Taylor series...
Utilizing logarithms, xlog(x)... And mixtures of different elementary functions may ask prove useful too... Constructing the method isn't significantly difficult you ...
0
It is possible to do this using Alpertron. If you input
x=17;x=n(x);i-50;x.
into its Batch factorization tool, it will output
17 is prime
19 is prime
[...snipped the list...]
257 is prime
263 is prime
To make it more interesting, we could try
x=n(10^100);x=n(x);i-50;x.
which finds the first 50 primes after $10^{100}$. It takes a few seconds on ...
0
Looking at this from a computer science like perspective, I would use the following algorithm to generate my list of primes.
input = (17,50)
if 17 is prime:
counter = 1
from_seed = seed
while counter <= 50
if from_seed is prime
print from_seed
counter+1
from_seed+1
else
from_seed+1
...
1
Here you go - give any random number as an input, and it will give you the next prime after it. You can feed its output into itself to make a list. It basically uses Fermat's Little Theorem to heuristically check if each number is a prime, and keeps checking successive odd numbers until you get to something that works.
It has a very small chance of failure ...
3
$r$ and $s$ are regular expressions, which represent regular sets. If $r$ and $s$ are regular expressions that represent sets $R$ and $S$, then the regular expression $r+s$ denotes the set $R\cup S$.
If $r$ is a regular expression denoting the set $R$, then $$r^*$$ is a shorthand for $$\epsilon + r + rr + rrr + \cdots .$$
4
Let $R$ be the set of words described by the regular expression $r$, and let $S$ be the set of words described by the regular expression $s$. Then the regular expression $(r+s)^*$ describes the words in the set $(R\cup S)^*$, and $r^*+s^*$ describes the words in the set $R^*\cup S^*$. Thus, the question boils down to asking whether it’s necessarily true that ...
0
Start with $A=n$, $B=0$, $C=1$, $D=0$. (Or, if by definition all but $A$ are empty, preceed the code with a +C).
We want to keep $B=F_{n-A}$, $C=F_{n+1-A}$, $D=0$.
1 while -A {
2 while -B {
3 +D
} // that is: D:=B, B:=0
4 while -C {
5 +B
6 +D
} // that is: D:=D+C, B:=C, C:=0
7 while -D {
8 +C
...
0
The number looks small enough to be brute-forced on a computer. Just try every possible factor, starting with 2, 3, 4, ... and keep dividing them out as long as the division comes out even. Then continue looking for factors of the quotient. You don't even need to explicitly restrict to primes, because any composite number you try simply won't divide the ...
3
The thing with Project Euler is that there is usually an obvious brute-force method to do the problem, which will take just about forever. As the questions become more difficult, you will need to implement clever solutions.
One way you can solve this problem is to use a loop that always finds the smallest (positive integer) factor of a number. When the ...
0
Project Euler problems (at least the ones that I have done) tend to deal with a lot of number theory topics. So, reading an introductory number theory book could be helpful.
With regards to your particular situation, I suggest finding primes first, then testing the primes for divisibility. That is, to find prime factors of $25$, don't test $1, 2, 3, 4, 5, ...
2
I’m afraid that no theorems or formulas can help you much in the developing of the algorithm, and therefore you should concentrate on the algorithm itself. I wrote a simple Pascal program to illustrate one of the simplest of such algorithms.
program SurNum;
const
m=7;
n=7;
var
IFi,OFi:Text;
tC:Char;
i,j,k:Byte;
a:array[1..m,1..n]of ...
2
You’re starting with the function $f(x)=2x-3$. I’ll write $f^n(x)$ for the result of applying $f$ repeatedly $n$ times. Thus, you’re looking for $f^{12}(5)$ and more generally $f^n(x)$.
One elementary approach is to calculate $f^n(x)$ for some small values of $n$ and look for a pattern:
$$\begin{align*}
f(x)&=2x-3\\
f^2(x)&=2f(x)-3\\
...
5
For the particular function you have, we can figure out $f^{(n)}(x)$.
$f^{(1)}(x)=2x-3$
$f^{(2)}(x)=2(2x-3)-3=2^2-(2+1)3$
$f^{(3)}(x)=2(2^2x-(2+1)3)-3 = 2^3x-(4+2+1)3$
$f^{(4)}(x)=2(2^3x-(4+2+1)3)-3 = 2^4x - (8+4+2+1)3$
The pattern is $f^{(n)}(x)=2^nx-(2^n-1)3$, which can be rearranged as $2^n(x-3)+3$. To prove this I would use induction.
0
As mentioned in the comments, this document under point (2) described a solution algorithm for the problem posed.
0
I had a misunderstanding. I thought 308 is the no of combinations for making all rolls as given in data and one of the 308 combination is the optimal answer given there, but now I have understood that 308 is the no of combinations for making use of the first 5600 width roll. Example
1380
1380+1380
1380+1380+1380
1380+1380+1380+1380
1380+1380+1520
.
..
and ...
1
Correct me if I am wrong, but I am assuming you want something like S XOR T: $S \oplus T$.
This is equivalent to $T \lor S \land \lnot (T \land S)$:
To get this in CNF:
$$T \lor S \land \lnot (T \land S) \equiv (T \lor S) \land (\lnot T \lor \lnot S)\tag{1}$$
Now, if we want to express this using your assignments of $T = (A \lor C) \land (B \lor C)$ and ...
1
You are looking for a Tree Spanner. In general it is NP-Hard to find such a tree for weighted and unweighted graphs, but it can be found in polynomial time in few special cases. You can find more information about it and more related results in this paper:
L. Cai and D.G. Corneil. Tree spanners. SIAM J. Discrete Math., 8(3):359–387, 1995.
1
Two relevant papers:
Titus, C. J. Characterizations of the restriction of a holomorphic function to the boundary of a disk. J. Analyse Math. 18 (1967) 351–358.
Farias, Antonio O. Orientation-preserving mappings, a semigroup of geometric transformations, and a class of integral operators. Trans. Amer. Math. Soc. 167 (1972), 279–289.
(The author of 2 was ...
0
Let $p(n)$ be your number. You can write it recursively as:
$p(n) = n^{n-2} - \sum_{k=1}^{(n/2)} {n/2 \choose k} \times p(n - 2k)$ where $p(0)=0$
What this formula states is that the total number of such trees is equal to total number of trees minus the number of times in which only one of your constraints is violated minus the total number of times in ...
2
You computed $d \equiv 17$ and $e \equiv 17^{1/121} \equiv 240$, while the result should be $e \equiv 17^{1/121} \equiv 15$. What goes wrong here is that you computed $1/121$ modulo $p$, instead of $1/121$ modulo $p - 1$.
Modulo $p = 257$ we have $$1/121 \equiv 17 \mod{257}$$ and thus you get a wrong answer: $$17^{1/121} \stackrel{?}{\equiv} 17^{17} ...
0
Part 1
If I understand your problem, you're given a collection of sets $\mathcal{S}=\{S_{1},\ldots, S_{n}\}$ and you want to pick $S_{i} \in \mathcal{S}$ such that $S_{i} \cap S_{j} \neq \emptyset$ for all $j\in [1,n]$ and $|S_{i}|$ is minimized.
If so, the problem is solvable in polynomial time. We can test whether each set in $\mathcal{S}$ intersects all ...
1
Consider this answer as temporary. The solution is kind of specific for Mathematica, from which this question was moved, so maybe using loops or something would have made it easier to see a Ruby solution. Anyway, this is what I typed. Mods can delete if they want.
----mathematica answer ----
Quickly, before it gets moved! (too late :( )
Note that this is ...
2
It's a little bit unclear what you want, so I'm going to present several possible answers that you can choose from.
The simplest possibility is that you simply want to divide the range into three equal parts. Assuming that the lowest number is $L$ and the highest is $H$, you can calculate the ranges as:
from $L$ to $L + \frac{H-L}3$,
from $L + ...
2
When the data is reconstructed from the quantized coefficients, the resulting coefficients will be
240 100 60 120
180 60 40 210
60 120 140 200
40 70 100 0
Thus the (signed) quantization errors are
-3 2 -3 -3
-7 -5 8 32
-8 -1 9 2
-14 -23 38 -81
3
In addition to Raymond's neat formula, I found the following less neat version.
It is based on the observation that after around $\sqrt n$ terms, we start seeing a lot of repeated values. By looking at how many solutions there are to $\lfloor\frac{n}{k}\rfloor=a$ we can get an expression like:
$$\underbrace{\sum_{k=1}^{\lfloor\frac{n}{\lfloor\sqrt ...
5
For the initial sum see sequence A006218 from OEIS and the Wikipedia page about the 'Divisor summatory function'.
Richard Sladkey's paper 'A Successive Approximation Algorithm for Computing the Divisor Summatory Function' proposes evolutions of the classical :
$$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor=2\sum_{k=1}^{\lfloor\sqrt{n}\rfloor} ...
0
This is a proof by contradiction. It assumes that there is a stable matching $S$ in which $A$ has a worse partner than in the stable matching $S^*$ produced by the Gale–Shapley algorithm, and derives a contradiction.
"$Z$ is not the worst valid partner for $A$": That such a pair exists follows from the assumption that $S^*$ is not "woman-pessimal" (never ...
1
IF $P$ divides $b,$ the remainder will be $0$
Else $(b,P)=1$
$$((b^{M_1})^{M_2})^{M_3}\cdots)^{M_n}=b^{M_1\cdot M_2\cdot M_3\cdots M_n}$$
As $P$ is prime, $a^{P-1}\equiv\pmod P$ if $(a,P)=1$ using Fermat's Little Theorem.
So, we need to find $M_1\cdot M_2\cdot M_3\cdots M_n\pmod {(P-1)}$
Then use repeated exponentiation.
Top 50 recent answers are included
