Tag Info

New answers tagged algorithms

0

Let $\mathcal{I}_k(n)$ be defined as in the OP. Define $\prec_{n,k}\subset \mathcal{I}_k(n)\times\mathcal{I}_k(n)$ as the restriction of the lexicographical ordering on $k$-tuples. Notice that since the lexicographical ordering is linear total and the set $\mathcal{I}_k(n)$ is finite, $\prec_{k,n}$ is a well ordering and thus defines a canonical bijection ...

0

You rotate the radial vector of length $R$ on positive x-axis through $\lambda$ towards East in equator plane and next through $\phi$ from radial direction towards North Pole by $\phi.$ $$\begin{pmatrix} x\\y\\z \end{pmatrix} = R* \begin{pmatrix} \cos \lambda \sin \phi \\ \cos \lambda \cos \phi \\ \sin \lambda \end{pmatrix}$$ To get back to ...

-1

N1, N2 – primes, N2-N1=2; N1 always belongs to the sequence S1(p)=6p+5; p = 0, 1, 2, … N2 always belongs to the sequence S2(q)=6q+7; q = 0, 1, 2, … When p=q; N1, N2 — are twin primes. Twin primes condition: Odd positive integers N1 =6p+5 and N2=6p+7 are twin primes if and only if no one of four diophantine equations has solution: 6x^2-1 + (6x -1)y=p 6x^2-1 ...

1

You're looking for what's usually called a system of distinct representatives or SDR. A theorem of M. Hall states that the sets $\{S_i\mid 1\le i\le n\}$ have an SDR iff rhe union of any subcollection $S_{i_1},\ldots,S_{i_k}$ has size at least $k$. However, this condition is not always easy to apply directly; here's an efficient way to find an SDR. Build a ...

0

Note that $a_n-a_{n-1}=2n-1$ implies $a_n-a_0=\sum_{k=1}^n(a_k-a_{k-1})=\sum_{k=1}^n(2k-1)=n^2.$

1

Hint: $$a_{n}-a_{n-1}=2n+1$$ Take the sum of both sides from $n=1$ to $n=x$, looks to me like a telescoping series on the left. If you go through the telescoping sum process you will see: $$\sum_{n=1}^{x} (a_{n}-a_{n-1})= a_x-a_0=a_x-1$$ Now can you take the right hand sum, and equate your two results?

0

I'm not exactly sure what it is you're looking for, but you might proceed, in pseudocode, as follows: k = ceil(sqrt(A)) Sk = k^2 while (Sk <= B) { output Sk Sk = Sk+2k+1 k = k+1 }

0

Hint: If I well understand you have the directrix of the parabola $d$ with equation: $$mx-y+(y_1-mx_1)=0 \qquad m=\dfrac{y_1-y_2}{x_1-x_2}$$ and the focus $F=(F_x,F_y)$ so the parabola is, by definition, the locus of points $P= (x,y)$ such that: $$\overline{Pd}=\overline{PF}$$ and, using: $$\overline{Pd}= \dfrac{|mx-y+(y_1-mx_1)|}{\sqrt{m^2+1}}$$ ... 2 The algorithm cannot become wrong if you omit that check. After all its only outputs are "definitely composite" or "possibly prime" and neither of these outputs is wrong for a (necessarily composite) perfect power. Also, the general credibility of the test is based on the fact that repeated tests with independently random initial values a are performed ... 1 It is true that the when a matrix has a Jordan normal form, the the size of the largest block for an eigenvalue~\lambda equals the multiplicity of~\lambda as root of the minimal polynomial. This is easy to see by computing powers of J-\lambda I for a general Jordan normal form matrix~J (in the k-th power the blocks for~\lambda with size at ... 0 I doubt that this is the intended solution, but you can find min-cost paths in the presence of negative cycles using minimum-weight perfect matching. For the given graph G construct a graph G' such that \begin{align} V(G') &= \Big\{w_{\{u^3,v^0\}}, w_{\{u^2,v^1\}}, w_{\{u^1,v^2\}}, w_{\{u^0,v^3\}}\ \Big|\ \{u,v\} \in E(G)\Big\}, \\ E(G') &= ... -1 A formula for calculate logaritma of\frac{(-6.23032921698349x^{5/512}+27.50588264989884x^{3/512}+88.3015617077568x^{1/256}-109.5771151406722)}{(x^{1/512}+0.02523106318562039)}.$$Error of the present formulă is about 2.7e^{-6} (for x smaller than 10). For x<10000, error is about 0.0000967. 0 Using Master's Method case 2 is applicable since n^{\log_b a}=n^{\log_2 1}=1 which is equal to \theta(1). Thus from Master's method T(n)=\theta(n^{\log_2 1}\log n) = \theta(\log n) 0 A "short" intro:$$n=9k \Rightarrow T(n)=T(9k)=T(6k) + T(2k) + 9kn=9k + 1 \Rightarrow T(n)=T(9k+1)=T(6k) + T(2k) + 9k +1n=9k + 2 \Rightarrow T(n)=T(9k+2)=T(6k+1) + T(2k) + 9k +2n=9k + 3 \Rightarrow T(n)=T(9k+3)=T(6k+2) + T(2k) + 9k +3n=9k + 4 \Rightarrow T(n)=T(9k+4)=T(6k+2) + T(2k) + 9k +4n=9k + 5 \Rightarrow T(n)=T(9k+5)=T(6k+3) + ...

0

First transform your coordinates to $$\begin{pmatrix} x\\y\\z \end{pmatrix} = \begin{pmatrix} -r \cos(lat) \sin(lon) \\ r \cos(lat)\cos(lon) \\ r \sin(lat) \end{pmatrix}$$ Your unit direction towards the center comes from the unit vector pointing from $(x,y,z)$ towards $(0,0,0)$ $$\hat{n} = -\begin{pmatrix} - \cos(lat) \sin(lon) \\ \cos(lat)\cos(lon) ... 0 Assuming inside of third loop takes constant time c then running the whole algorithm takes:$$T(n) = \sum_{i = 1} ^ {n} \sum_{j = i} ^ {2 i} \sum_ {k = j} ^ {2 j} c$$Summation limits are exactly same as in the loops. We can then calculate T(n) :$$ \begin{aligned} T(n) &= c\sum_{i = 1} ^ {n} \sum_{j = i} ^ {2 i} (2j - j + 1) \\ \\ & \vdots ...

0

For $n=k$ you could use the following theorem: $lcm(\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}) = \frac{lcm(1,2,\ldots,n+1)}{n+1}$ A proof of this theorem can be found here: http://arxiv.org/pdf/0906.2295v2.pdf

0

For $\theta(n)$ of the time of the first loop, $i$ is $\theta(n)$. (Think about the second half of this loop when $i>\frac{n}{2}$.) In this time, for $\theta(i)=\theta(n)$ of the time of the second loop, $j$ is $\theta(i)=\theta(n)$. In this time, for $\theta(j)=\theta(i)=\theta(n)$ of the time of the second loop, $k$ is $\theta(j)=\theta(i)=\theta(n)$. ...

0

You could write a function in your favourite language to perform $a^b \text{ mod } c$. An example in Python is given here: http://aditya.vaidya.info/blog/2014/06/27/modular-exponentiation-python/

0

As mentioned by Bill, total number of expressions is 6561 which is far too much to be checked manually, but relatively quickly can be managed e.g. in Excel using brute force: Set first 17 columns for the numbers and operands: Formula in odd columns for numbers: =ROUND(COLUMN()/2,0) Formula in even columns for operands ...

3

Write out the string "123456789". Between each number you can either (1) do nothing, (2) put a "+", or (3) put a "*". So we have 3 choices between each number. This leaves $3^{9-1} = 3^8 = 6561$ possible strings to evaluate. Of course, some strings can be eliminated (for example, you can't have two "do nothings" in a row -- the smallest number such a ...

0

It appears that the random integer is not used, so that step uses constant time. For the following for loop we don't care what value $x$ starts at, so we are asking whether the for loop takes longer than $\Theta((n \log n)^3)$

0

Because of the "random integer" part, no definite bound can be given. However, if you assume a distribution for these random integers, you probably could get a distribution of the run times.

1

Actually, this is true if $T(n) =an + \sum_{j=1}^m T(\lfloor b_j n \rfloor)$ where $a, b_j > 0$ and $\sum_{i=1}^m b_j < 1$. The proof is almost identical to the following proof for the coefficients in the original problem. Suppose $T(k) \le ck$ for $\lfloor 7n/16 \rfloor \le k < n$. Then $T(n) =T(n/2)+T(7n/16)+n \le c(n/2+7n/16)+n = ... 1 The answer is {11,13,17,19,23,25,27,28,29} with a sum of 192 The following greedy algorithm is NOT correct, though it's highly tempting to think it is: Arrange the numbers in descending order. This is "the list". Start with an empty set that will be the eventual answer. This is "the set". For each item on the list: If it has a common factor with any ... 1 I think this might be correct- {30, 29, 23, 19, 17, 13, 11, 7}. I started from 30 and excluded all even numbers. I included primes, if any factor of the prime did not appear beforehand. For example, 29, 23 etc are included but primes like 5(because 30 is included), 3(because 30 is included) are excluded. -------------EDIT------------ This is a better ... 2 This is known as a nonsymmetric algebraic ricatti equation (NARE). You may google this term to find out the latest development. 0 The angle in$z$is just the negative of the latitude. Your$x$coordinate has$+x$in the direction of LON=$180^\circ$because of the minus sign. Is that what you want? Your$+y$is in the direction of$+90^\circ$. That means your coordinate system is left handed. Adding$180^\circ$for the angles in$x$and$y$should work fine. Please post some ... 2 You seem to be describing a batch scheduler: It receives the (potentially infinite) list of job instances at time zero and then instantaneously assigns the schedule of the instances. But your table does not agree. It appears that job instances arrive at undefined times in undefined numbers and that the scheduler cannot schedule an instance until it ... 0 $$\log_2(n!)=\log_2[n\cdot (n-1)\cdots 1]=\log_2 n+\log_2(n-1)+\cdots+\log_2 1$$ There are$n$terms, and most of the terms are close to$\log_2 n$in magnitude. Therefore$\log_2(n!)=\Theta(n\log n)$. (To prove this more formally, use Stirling's approximation.) 0 Look at Stirling's approximation https://en.wikipedia.org/wiki/Stirling%27s_approximation 1 You should get something like n Fib_{2n-1} Fib_{2n} a_n b_n c_n 3 3 5 4 3 5 4 8 13 12 5 13 5 21 34 30 16 34 6 55 89 80 39 89 7 144 233 208 105 233 8 377 610 546 272 610 etc. 0 One glance at your C snippet and I have no hope it is worth analysing, but don't take this as criticism. If I were good at C I would give you a routine that does the job, but I am not. So, I have a couple of pages in a .pdf file, page one shows Euclid Extended for a=3587, b=1819, and shows how gcd(3587,1819)=17 is computed, and how in one and the same run ... 0 No. Every digit that you calculate is the last digit of a partial sum. So you will never obtain the limit from a given string of digits, unless only zeros are known to follow (this being an extra information). It is important to distinguish between an infinite string of digits which does never represent the limit (unless only zeros are known to follow) and ... 0 You can compute$x = \frac{1}{y}$for given$y$as follows. We write$x$as the solution of the nonlinear equation: $$y - \frac{1}{x} = 0$$ The Newton-Raphson method then yields the successive approximations: $$x_{n+1} = 2 x_n - y x_n^2$$ In each step the number of correct digits is doubled. 0 Your question isn't very clear on what you are looking for. If you don't allow any representation of numbers, how do you store numbers in the first place, not to say compute anything with them? So you've to specify what operations you allow on numbers (basic operations). Say you want to find$x \div y$for positive integers$x,y$. If you allow only ... 0 I'm aware of Chaco which is an open-source graph partitioning package written in C language. Chaco can do KL as well as many other partitioning heuristics. You can download it from http://www3.cs.stonybrook.edu/~algorith/implement/chaco/implement.shtml And user's guide is here https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/guide.pdf 0 Based on what Euler and bof says, I think the idea is basically that removing 1 is same as an "empty move" that can be performed at most once. For the sake of contradiction, suppose the second player$B$has a winning strategy. Suppose the first player is$A$. Suppose$B$'s winning strategy is the set of rules R = {For state$S$, if$A$removes$x$, then ... 1 Note that you've essentially taken as your random input$(N-1)^N$equally likely values - you've picked from$1$to$N-1$,$N$times. But the total number of shuffles is$N!$. And for each shuffle to be equally likely, you'd need$N!$to be a divisor of$(N-1)^N$. This is not possible, because$N,$a divisor of$N!$is relatively prime to$(N-1)$, and hence ... 1 With this shuffle, you will always have the first element out of place. i.e. that probability of the first element staying in place is$0$, and is not$1/N$as the uniform distribution requires. 3 I feel the need to take this to a more mathematical realm. So here's a commentary to long for comments. Set-Up We have a system of recurrence relations defined by, $$(1) \quad \vec v_{n+1}={{|\vec v_n|} \over {||\vec v_n||^2}}-\vec A$$ $$(2) \quad a_{n+1}=a_n+| \ ||\vec v_n||-b_n|$$ $$(3) \quad b_{n+1}=||\vec v_n||$$ First let's reduce this to a system ... 1 Remember, you only have to find one example where$d(n) - e(n)$is not$O(f(n) - g(n))$. One way to do this is to try to prove that$d(n) - e(n)$always will be$O(f(n) - g(n))$, and find out where the proof does not work. For example, if$d(n) \in O(n^2)$and$e(n) \in O(n)$, (that is,$f(n) = n^2$and$g(n) = n$), then$d(n) - e(n)$will act like$d(n)$... 0 Let$d(n)=n^2+n$,$e(n)=n^2$. Then$d(n)=O(n^2)$,$e(n) O(n^2)$, but$d(n)-e(n)=O(n) \notin O(n^2-n^2)=O(0)$. 1 Put$f(n) = 2n$and$g(n) = n$You have$f(n) = O(n)$and$g(n) = O(n)$but$f(n) - g(n) = n$for all$n$. 0 Puzzles like this have been studied extensively in AI. See, for example, this treatment of the 8-puzzle. In the case of the problem you present, breadth-first search will assure us that the solution, if it exists, will be optimal as you define it. You'll define whole matrices as the states in your search, and your "+" operation as the sole operation from ... 1 If a function f is polynomially bounded,it means there exist a polynomial g and h such that for all x, g(x)<=f(x)<=h(x). 1 So first out some theoretical pondering When comes to theoretical investigation, since we have considered 2d vectors so far, I will make the simplification to move to$z = r+wi \in \mathbb{C}^1$where , the operation$|{\bf v}|$takes$z = r + wi$to$|r| + |w|i$, i.e. Moves complex number to the first quadrant by a series of reflections in the real and ... 0 Where x represents 3^x: 1 1 1 7 1 4 2 7 3 3 2 6 5 5 4 6 Move right: 2 7 1 4 2 7 3 3 2 6 5 5 4 6 Down: 7 1 4 7 3 3 3 6 5 5 4 6 Right: 7 1 4 7 4 6 5 5 4 6 Down: 7 7 1 6 5 5 5 6 Right: 7 7 1 6 6 6 Up: 1 7 6 7 6 6 Left: 1 7 6 7 6 6 Up: 1 7 7 7 Phew. Done. And ... 1 I guess the easiest option would be to apply Lyapunov theory: https://en.wikipedia.org/wiki/Lyapunov_function https://en.wikipedia.org/wiki/Lyapunov_stability As a short summary: take$f(x)$as a candidate Ljapunov function, which puts some reasonable restrictions on the shape of your optimization landscape (i.e. locally positive-definite function). All ... 0 The "rank" vectors$\sigma$and$\pi$are the inverses of the permutations a and b respectively. So it's faster to compute$\sigma$with a single pass over a, compute$\pi$with a pass over b, then computing the footrule is a linear pass over$\sigma$and$\pi\$, so this is linear time and space overall.

Top 50 recent answers are included