Tag Info

New answers tagged

1

I can give you a recursive formula which might be good enough to find big values with the aid of a computer, or maybe someone can find a closed form for it. Let $a_n$ denote the number of different ways we can represent $n$ with our coins with $a_0=1$ by definition. Consider $F(x) = \sum a_k x^k$. We can see that $$F(x) = ...


0

So following from Lab's link we have $$n=x^2+y^2+z^2\iff n\ne4^a(8b+7)$$ Therefore to test we divide by 4 as much as possible at least once. Then subtract 7 and test if it is divisible by 8. If the divisibilities are true then you have a number that can't be represented as such. Algorithm Check divisibility by 4. If it is not divisible then $n$ is such ...


0

Hint: You need one station for each suburb exactly on the circumference of the city. This is the number of ways to express $R^2$ as a sum of two squares. A little searching will find this. It depends on the factorization of $R^2$


0

Here is an $\mathcal{O}(n\log n)$ answer. For example, let be A = [2, 4, 6, -9, 12, -20]. We assume zero-based indexing. alg(A): cumulativeSums = [0] for x in A: y = the last element of cumulativeSums add y + x at the end of cumulativeSums sort cumulativeSums minDifference = infinity for i = 1, ... , length(cumulativeSums) - ...


0

You can detect $l$ greatest values (and collect them in positions $n-l+1,\ldots,n$) from the array by calling SQRTSORT with $k=0$, $k=\sqrt{n}-l$, $k=2\sqrt{n}-2l$, and so on. Therefore, $2\sqrt{n}$ calls are sufficient to find $\sqrt{n}/2$ greatest values from array. Doing this recursively, we sort the array with at most $4n$ calls of SQRTSORT. A lower ...


0

Some form of short interpretation is given by Prof. L. Vandenberghe, UCLA, here http://www.seas.ucla.edu/~vandenbe/236C/lectures/fgrad.pdf Slide 5; though not very informative, given the lack of answers, I am just going to think of it as extrapolation.


0

Notice that the table that tells you how to multiply is in fact the table of the Klein $4$-group, which is an abelian group of order 4, however all of its elements have order $2$ or $1$. now notice that since groups are associative and this particular group is associative, by the generalized associative and commutative laws all we need to know to determine ...


2

If you're doing $ \pm a \pm b \pm c \pm d$, there are $4$ signs, and each can be $+$ or $-$, so that makes $2^4$ possibilities. But for a large number of terms, trying every possibility is a very inefficient algorithm. Depending on the nature of the terms, you might do better with a Dynamic Programming algorithm. If $S_k$ is the set of all possible sums ...


0

Start by opening boxes 1, 8, 16, 23, 31. Now try showing that it is possible to restrict your search to one of the intervals [1, 16], [16, 31] - This will involve checking some simple cases. So say we are in [1, 16] and we know the content of box 8. With this information, we can even narrow down to one of the subintervals [1, 8], [8, 16] unless $B(1) < ...


0

I think we can solve the problem for 32 boxes with 9 openings: Let the boxes be numbered 1, 2, ..., 32. Let the values in the boxes be $a_1, a_2, \dots, a_{32}$. Preliminary observations: (1) We are looking for a box whose value is a local maximum (i.e., whose value is greater than or equal to each of its immediate neighbors' value). We understand that a ...


1

If I understand right the problem (it's not very clear), I think it can be done with less than 11. Hint/sketch: Lets say that a box is apt if its value is greater or equal than that of its neighbours. We want to find an apt box. This is analogous to finding a local maximum of a discrete sequence Starting from the chain $(x_{1} \cdots x_{31})$, uncover ...


0

Because $\Theta\left(n^2\right)$ is characterizing average running time across all possible inputs, - it just means that your algorithm runs extremely well on vast majority of inputs but has a small margin of pathological cases. EDIT Note that in such a case, the worst-case complexity would be $\Omega \left(n^{3n}\right)$, but that does not contradict that ...


4

This is called the maximum matching problem, and it is one of the few graph problems for which there is a non-obvious polynomial time algorithm! It's called Edmonds's blossom algorithm: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm Edit: Following Casteels's suggestion, here's an example showing that the greedy algorithm might only get you ...


2

The author of the problem once wrote an article about baby-step-giant-step algorithm (but in Chinese). The baby-step giant-step is a meet-in-the-middle algorithm computing the discrete logarithm. I think this article may help you. http://en.wikipedia.org/wiki/Baby-step_giant-step


0

You don't actually need to sort anything if you only need the top 5 points Initialize by storing an array of 5 "null" points with rank $r = 0$ and store $r_0 = 0$. For each point $P(x,y,r)$, if $P$ is inside the rectangle (i.e. $X_1 < x < X_2$ and $Y_1 < y < Y_2$) and $r > r_0$, then replace a point in the array with the lowest rank with ...


0

Dijkstra himself simplified the example problem by noting the symmetry between wolf and cabbage, see http://www.cs.utexas.edu/users/EWD/videos/EWD4.mpg.


0

From what you're asking, I think you're asking to: Given $n$ points, find all $k \le n$ points $(x,y)$ located in a given rectangle. Out of those $k$ points, find the top $r$ ranked points. Here's what I would do in this case: Sort the coordinates by $x$-coordinate. Depending on if your points are bounded or not, you can do an $O(n)$ non-comparison ...


5

In your formula you wrote $a\cdot\log_{1.c}b$. In the plots, I'm plotting the function which would go in the base of the logarithm. So the function we want is a function which is always above 1 and is decreasing towards 1 $$a\log_{1.c}b=\frac{a\log b}{\log 1.c}$$ This was what you suggested in your question, and I don't think this is what you wanted Now ...


0

DPBP is NP-complete. I give a reduction from the partition problem. Define $\text{PART}=\left\{ {x_1,x_2,\ldots,x_n\in \mathbb{N}|\exists I:\sum_{i\in I}x_i=\sum_{i\not\in I}x_i} \right \}$. Given an instance $\left \{ {x_1,\ldots ,x_n} \right \}$ of PART, we build a graph in the following way. For each $i\in \left \{{1,\ldots,n} \right \}$, we have a ...


0

Having looked up the definition of "point cloud", my comment of taking a Cayley graph and removing the edges may (theoretically) work, but you need a couple of fudges and in reality it all depends on where you are working. There is lots of literature about algorithms and Cayley graphs (they have applications in computer networking), so I thought it would be ...


1

EDIT: I put information related to this, including the method used in the computer output below, at http://math.blogoverflow.com/ I think you should work out the case $D=E=F=0$ first, it is trickier than you think. Given an indefinite form $$ f(x,y) = P x^2 + Q xy + R y^2 $$ with integers $P,Q,R$ and discriminant $$ \Delta = Q^2 - 4 P R $$ positive but ...


2

The quadratic form $A x^2 + C x y + B y^2$ is positive or negative definite (implying $|p(x,y)| \to \infty$ as $\|(x,y)\| \to \infty$ ) if $C^2 < 4 A B$ and indefinite (implying $p(x,y)$ is not bounded above or below) if $C^2 > 4 AB$. Your statement about "if the leading coefficients have the same sign" is false, e.g. $x^2 + 3 x y + y^2$ has no ...


2

These are not combinations but permutations. There are $n!$ permutations of $(1,2,\cdots,n)$, with $n!=1\cdot2\cdots n$. There is a very simple algorithm to get them, one at a time, in lexicographic order (that is, the order you use in your example). Start with a permutation $(a_1,a_2,\cdots,a_n)$, we want the next one in lexicographic order. Find the ...


1

An algorithm is given at https://www.ics.uci.edu/~eppstein/numth/ (C++ implementation of J.H.Conway's "nimber" arithmetic.). The function to actually perform the multiplication is at nimber.C:316:nim_times.


1

It is not true that all functions corresponding to the same entry in the table will be $\Theta$ of each other. In particular, $a^x = O(b^x)$ if and only if $|a| \leq |b|$. I'm not sure about the L-notation bit. It is true, however, that $f = O(g)$ if $g$ is lower down on the table.


1

is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? Yes, in the following sense. Assume that $f(n)=h(n)+r(n)$ and $g(n)=k(n)+s(n)$ with $h(n)=\Theta(k(n))$, $r(n)=o(h(n))$ and $s(n)=o(h(n))$. Then indeed $f(n)=\Theta(g(n))$.


2

I'm not sure I fully understand your question, but have a look at (b): $$ \lim_{n \to \infty} \frac{\sqrt{n}}{n^{\frac{2}{3}}} = 0 $$ This means $f(n) = o(g(n))$, i.e. we can pick $c >0$ arbitrarily small, and $\forall c>0 \ \exists \ N(c)\ s.t. \ \forall n>N(c) \ \sqrt{n} < c n^{\frac{2}{3}}$. At the same time $\nexists N(s) \ s.t. \forall ...


1

I think you might want to look into De Bruijn sequences; it sounds like you want to count the distinct non-self-intersecting paths through the De Bruijn graph.


0

If you have the functional form $f(x)=A\log (x+B)+C$ (with three parameters), and impose only the two constraints $f(0)=1$ and $f(1)=0$, then your problem is underdetermined and you should expect to have a free parameter remaining. What you've done so far is correct. $$ f(0)=A\log B + C = 1 \\ f(1)=A\log(1+B)+C=0. $$ Subtracting one equation from the other ...


0

The answer is that each choice of $A, B, C$ that satisfy the conditions you've produced will give you a transformed log function that satisfies your conditions, and there are many such choices of $A, B, C$ that do this. That doesn't mean that we can set any particular variable to any value, however; for example, since $\log$ is increasing, $\frac{1}{A} = ...


0

I suggest that you instead use $$ y=\frac{1}{(x+1)^{13}} $$ You can change the exponent $13$ so as to modify the shape. This gives the correct sort of behaviour, it is significantly faster to evaluate computationally than logarithms, and it is physically more realistic (when you push real atoms together they repel with a force $\sim r^{-13}$).


1

This usually is covered in any basic abstract algebra course. Any permutation can be decomposed into some cyclic permutations and any cyclic permutation can be decomposed into $k$ transpositions even though $k$ is not unique, its parity is always the same. So as long as $M$ is at least equal to the number of transpositions (after some simplifications and ...


1

This Dynamic Programming algorithm uses an array of length $n$. Filling in any element of this array takes constant time, since any element other than the two base cases can be computed by simply accessing the previous two elements. Thus, since each element is the array is computed at most once in constant time, it follows that computing the entire array ...


0

Maximal value of $s(x)$ is 81. It is enough to check $s(b*y^a+c)=y$, for values $0<y\leq 81$. Here is python code: s = lambda x: sum(map(int, str(x))) def solve(a,b,c, decs=9): r = [] for s_x in xrange(9*decs+1): x = b * s_x**a + c if s_x == s(x): r.append(x) return r print solve(3,2,8)


0

Necessary and Sufficient conditions in terms of rank inequalities are given in: http://arxiv.org/pdf/math/0506382v1.pdf Even though it has been a while, I hope it helps!


0

What follows uses the notation from MJDs excellent contribution. Here is an implementation in C by way of Rosetta-Stone like enrichment. This computes all possible assignments even though each of these inhabits an orbit of $24$ assignments that can be obtained from another by a rotation ($3\times 3$ rotations about an axis through the ...


5

I found this not hard to solve with a pen and a piece of paper towel, so I suspect that it's rather unconstrained and there are many solutions. Later on I may write a program to generate all possible solutions and count them, but for now here's what I did to find a single solution. (Addendum: I did eventually write the program; see the comment below.) The ...


0

Dijkstra's algorithm works just fine for undirected graphs. As others have pointed out, if you are calling a library function that expects a directed graph, then you must duplicate each edge; but if you are writing your own code to do it, you can work with the undirected graph directly.


0

Observe that whoever can produce the number 1 will win the game. If $n \equiv 1 (\mod (k+1))$, then Bob wins. Otherwise, I can claim Alice wins. Proof: Assume $n>1$ (the $n=1$ case is trivial). Suppose $n \equiv 1 (\mod (k+1))$. Then if Alice subtracts $x$, Bob will just subtract $(k+1)-x$ on the next turn. Alice can never produce a number that is ...


1

You should find plenty of resources (like this and this) by searching for "image processing" in addition to "contrast". The basic contrast and brightness adjustments are transformations of the form $$ f(x) = \alpha x + \beta $$ (with the result rounded to an integer and clamped to the range $[0,255]$.). Here $x$ is a color component value (R,G or B). The ...


1

Convolution with a mollifier, suggested by Jack D'Aurizio, works well on Euclidean spaces. Another approach, which applies to general metric spaces, is to use the upper or lower $L$-Lipschitz envelope of given function $f:X\mapsto \mathbb R$. Specifically, $$g_L (x) = \sup_{y\in X}( f(y)-L\,d(x,y)) \tag{upper envelope}$$ $$h_L (x) = \inf_{y\in X}( ...


1

Hint: Consider the sequence $a(n)=T(n)^2$. This sequence satisfies the recurrence relation $a(0)=0, a(1)=1$ and $$ a(n) = T(n)^2=\frac{T^2(n-1)+T^2(n-2)}{2}+n = \frac{1}{2}a(n-1)+\frac{1}{2}a(n-2)+n, $$ for $n\geq 2$. Can you solve it from here?


0

$T(n) = \frac{1}{3} \sqrt{3 n^2+5 n+\frac{2}{3} \left((-1)^{n+1} 2^{-n}+1\right)}$


0

For every $(i,j)$, consider $$t(i,j)=2^{-i}4^{-j}T(2^i,4^j),$$ then $t(i,0)=t(0,j)=a$ for every nonnegative $(i,j)$ and, for every positive $(i,j)$, $$t(i,j)=\tfrac12t(i-1,j)+\tfrac14t(i,j-1)+1.$$ Let $\ell\geqslant1$. If $t(i,j)\leqslant C$ for every $(i,j)$ such that $i+j=\ell-1$, then, for every $(i,j)$ such that $i+j=\ell$, ...


1

The first quote should not have been published, because the conclusion is categorically wrong. Almost all objective functions are Kolmogorov random. They have no order whatsoever that can be exploited in optimizer design. An optimizer cannot be specialized to one of them. For almost all of the theoretically possible functions on which an optimizer performs ...


1

Question 2, first. In NFL analysis, optimization (search) is decomposed into sampling of the objective function (mapping), and use of the sample to generate an output. It is tacitly assumed that all optimizers under comparison process samples identically. The NFL literature uses the terms search algorithm and optimization algorithm to refer to the sampler ...


0

Assume $(a^{(i)}_1,\cdots, a^{(i)}_n)$ is the sequence of heights in step $i$ and let $l^{(i)}$ be the number of minimums in $ (a^{(i)}_1,\cdots, a^{(i)}_n)$ where $1\leq i \leq m.$ Initially, if $l^{(1)} > mw,$ because there're more minimums than our effective choices then the desired maximum is simply the initial minimum element i.e. ...


2

Start by running $1$ step right, then $2$ steps left, then $4$ steps right and so on. Assume that you hit your room at step $1 + 2 + 4 + \dots + 2^{m-1} + k$, $2^{m-1} < k \le 2^m$. Then we have used $2^{m} - 1 + k$ steps in total, and we are at $$n = \sum_{j=0}^{m-1} (-1)^j 2^{j} + (-1)^m k = \frac{1 - (-2)^{m}}{3} + (-1)^m k.$$ Therefore $|n| \ge k - ...


0

This calls for some graph theory. Begin by visiting an arbitrary vertex; add each vertex it's connected to (all the things around a face, or along edges, that include the vertex), to your itinerary. Then visit a node in your itinerary and add its neighbors, that you haven't visited, to the itinerary. When you've run out of itinerary, you've found a ...


2

This is an illustration of using DFT to find the product of two polynomials. It is based on the fact that Fourier transform (discrete or continuous) converts convolution into multiplication. The product of two polynomials amounts to convolution of their coefficients: $$ \left(\sum_{j=0}^n a_j x^j\right)\left(\sum_{k=0}^n b_k x^k\right) = \sum_{m=0}^{2n} ...



Top 50 recent answers are included