Tag Info

New answers tagged

1

Such an $n$ exists iff $p=1 \mod 4$. And also $p=1 \mod 4$ iff $p=x^2+y^2$ for integers $x, y$. Then the solution is $n=\frac{x}{y} \mod p$. This could be faster using $1\le x\le \sqrt{p}$.


0

I think you could measure the curvature of that curve $\gamma(t)$ with $t\in[0,1]$. First you have to build the derivate (or gradient), by computing: $$ \gamma'(t) = \left(\frac{\partial \gamma_1}{\partial t},\frac{\partial \gamma_2}{\partial t}\right)\approx\frac{\gamma(t+h)-\gamma(t)}{h}$$ Where you try to choose $h$ as small as possible. Now you build ...


0

This histogram will approximate distribution of $f(X)$ where $X\sim U(0,1)$ and $f(x)$ is bounded to $[0,1]$. You are correct that in the limit of infinite samples and bins, the the approximation will be exact. As for how it related to $f$, think of it this way. If $f(x)=c$ where $c$ is constant, then your histogram will just be a spike at $c$ If ...


0

You have a recurrence relation $$a_n - a_{n-1} - a_{n-2} = 0\ \ \ \ \ \ (1)$$ with initial conditions $a_1 = a$, $a_2 = b$. The initial relation is the same as for the normal fibonacci sequence, and has (positive) solution (which you can check) $$a_n = \lambda\phi^n + \mu\phi^{-n}$$ $\lambda$ and $\mu$ can then be calculated using the initial conditions, ...


2

Hint. Start with $a := 1$ and $b := n$. Now look at $s := S[a] + S[b]$, if $s > x$, decrease $b$ by $1$, if $s < x$, increase $a$ by $1$. You either find a pair or end up with $b < a$, in which case there is no such pair.


1

Let $i=1$, $j=n$. If $i>j$, terminate: No solution exists. (If the elements are required to be distinct, test for $i\ge j$ instead). If $a_i+a_j=x$, terminate: Solution found If $a_i+a_j<x$, let $i\leftarrow i+1$ and go back to 2. Let $j\leftarrow j-1$ and go back to 2. Each time step 2 is reached, the differenec $j-i$ decreases by one, starting ...


1

Calculating the $Q_n$ for $n=0\ldots 11$ gives, $n!Q_n = A_n$ with $\{A_n\}_{n\in\mathbb N_0} = \{1,1,2,4,10,26,76,232,764,2620,9496,35696,\ldots\}$ at least the comments on http://www.oeis.org should give you some hints for the respective matching sequences.


1

g'(x) = 1 + 2x + (1+x)g(x) I am not giving the derivation in case this is a homework question, but it should be easy to work out. Once you get this, you can solve this integral using standard techniques. Try wolfram: http://www.wolframalpha.com/input/?i=g%27%28x%29+%3D+1+%2B+2x+%2B+%281%2Bx%29g%28x%29 Now to get $Q_n$ compare coefficients of x.


0

Yes, there is an algorithm: DePano, A., Yan Ke, and J. O’Rourke. "Finding largest inscribed equilateral triangles and squares." Proc. 25th Allerton Conf. Commun. Control Comput. 1987. Unfortunately, I do not have easy access to my own article. :-/       (Image from this link.)


0

My initial assumption is wrong, and an 80-80-20 triangle provides the coutnerexample. If the triangle is maximal then all 3 vertices have to be on edges of the polygon. So I'm thinking that it makes sense to approach the problem by iterating over all tuples of 3 edges (filtering out tuples where all 3 edges are the same), assuming one vertex is somewhere ...


0

I created a rule for divisibility by seven, eleven and thirteen whose algorithm for divisibility by seven is this: N = a,bcd; a' ≣ ( − cd mod 7 + a ) mod 7; cd is eliminated and if 7|a'b then 7|N. The procedure is applied from right to left repetitively till the leftmost pair of digits is reached. If the leftmost pair is incomplete consider a = 0. Example: N ...


0

We can rewrite it as $-( f(n-1)) =\{k_1f(n-3)+k_1f(n-3)n+k_1f(n-3)n^2+k_1f(n-3)n^3+..+\infty\}+\{k_0f(n-2)+k_0f(n-2)n+k_0f(n-2)n^2+k_0f(n-2)n^3+..+\infty\}\tag1$ from $-f(n-1)=\frac{1}{1-n}(k_0f(n-2)+k_1f(n-3))\tag 2$.Taking summation up to infinity in n from both ends we get the terms involving $\sum_{n=0}^{\infty} f(n)$ on both sides. But some ...


0

I see a finite structure in Tree and node coloring.. What is your take if we go with graph theory method to get an expression for general case n and later add all as series up to infinity?If we can find a sequence some thing like GP. We may end up in a finite expression


0

Let we set $a_n=f(n)$, and $$ g(x) = \sum_{n=0}^{+\infty} a_n x^n.$$ Since: $$ x\cdot g'(x) = \sum_{n=1}^{+\infty} n\, a_n x^{n},$$ $$ x\cdot g(x) = \sum_{n=1}^{+\infty} a_{n-1} x^{n},$$ $$ x^2\cdot g(x) = \sum_{n=2}^{+\infty} a_{n-2} x^{n},$$ the recursion gives that $g(z)$ is a solution of the differential equation: $$ x\cdot g'(x)-5x = k_0(x\cdot ...


1

Check out Kung's algorithm. Given $n$ vectors in $\mathbb{R}^d$, it computes the non-dominated front for $d=2,3$ in $O(n \log n)$ time and for $d > 3$ in $O\left ( n (\log n)^{d-2}\right)$. I believe it has been implemented in the paretoset function on FEX.


0

Assuming lists as your container types, merging two sorted lists in-place of sizes $n_1,n_2$ takes $O(n_1+n_2)$ steps (if yo use arrays, the complexity is the same, but you'd use a separate "output" array). Hence you can essentially half the number of lists by merging them in pairs in $O(n_1+n_2+\ldots+n_k)=O(n)$ steps. If $k\le 2^r$, we can reach a single ...


0

What you want to do is to keep k pointers, one for each list. Now maintain a min-heap with the elements here. The min-heap will always have k elements. When the min comes to be from list i, increment the ith pointer by 1 and add the new element from list i into the min-heap. As element addition and min extraction for min heap of size k can be done in O(log ...


2

If f1 is in F2 then take f2 = f1. EDIT as Casteels pointed out, this is ruled out by the wording of the question. Else, T1 - f1 has two connected components say C1 and C2. T2 must have at least one edge from C1 to C2. Take that as f2.


2

Take some large n, $$ \begin{align} f(n) &= \frac{f(n-1) f(n-2)}{n} \\ &= {f(n-2)^2 f(n-3) \over n (n-1)} \\ &= {f(n-3)^3 f(n-4)^2 \over n (n-1) (n-2)^2} \\ &= \frac{f(n-4)^5 f(n-5)^3}{n (n-1) (n-2)^2 (n-3)^3} \\ &= \dots \\ &=\frac{f\left(n - (n-2) \right)^{F_{n-1}} f\left(n - (n-1) \right)^{F_{n-2}}}{\prod^{n-3}_{i=0} ...


1

As @Winther commented, letting $a_n=\log f(n)$ one has $$a_n-a_{n-1}-a_{n-2}=-\log n.$$ We only need a particular solution. Let $F_n$ be the Fibonacci sequence $F_0=F_1=1, F_i=F_{i-1}+F_{i-2}$. And consider $$b_n= \sum^n_{i=0}F_i\log (n-i).$$ It is easy to show that $$b_n=b_{n-1}+b_{n-2}+\log n.$$


2

I believe the formula is, for $n\geq 3$, $$f(n) = 2^{F_{n-1}}\prod_{k=3}^{n}k^{-F_{n-k+1}}$$ where $F_1,F_2,F_3,\ldots$ is the standard Fibonacci sequence whose first two terms are $1$. You can see this by just writing out the first several terms. For example, $$f(9) =\dfrac{2^{21}}{3^{13}4^8 5^5 6^3 7^2 8^1 9^1} $$ Addendum (Inductive Proof): The base ...


0

To prove the correctness you can use an invariant. This is a statement that holds true throughout the execution of the algorithm. In your case, the invariant expresses that the partial sum $S$ that you form never exceeds $T$. (When you try to increase some $x_i$, either the sum reaches $T$ and you stop, or $x_i$ reaches its upper bound $b_i$ before.) So ...


1

It is not that $h(S_1)=h(S_2)$ is true; in fact $h(S_1)=a$ and $h(S_2)=c$, as explained in the example at pag. 80, where $h$ is the minhash function associated to the permutation $\{abcde\}\mapsto \{beadc\}$ and $S_1$ resp. $S_2$ are given in figure 3.3. What is true is that the probability of having $h(S_1)=h(S_2)$, for generic $S_1$ and $S_2$ obtained by ...


0

Since Hagen was faster in mentioning the intermediate value theorem, let me prove that your algorithm works. Let $B_k:=\sum_{i=1}^k b_i + \sum_{i=k+1}^na_i$ for $k=0,\dots,n-1$. For example, $B_0 = \sum_{i=1}^na_i\leq T$ - that's your first try. You know that $B_k$ is a non-decreasing sequence and that $T\leq B_{n-1}$. Either $T= B_{n-1}$ which is simple, or ...


0

The set $[a_1,b_1]\times \ldots\times [a_n,b_n]$ is connected (as a product of connected sets) and hence the image under the continuous map $[a_1,b_1]\times \ldots \times [a_n,b_n]\to \mathbb R$, $(x_1,\ldots,x_n)\mapsto x_1+\ldots +x_n$ is connnected, so with $a_1+\ldots +a_n$ and $b_1+\ldots +b_n$ it attains also all intermediate points.


0

the given problem is best fit on master theorem


2

Your textbooks gives you a proof by induction for this sentence. Initial control gives you a first value $j$ for which the claim holds. Preservation control uses the induction hypothesis (claim holds for $j-1$) to perform the induction step (claim holds for $j$). The idea of proof by induction is the following: You show the claim for one specific value ...


3

Log time is clearly not possible in an unsorted array, but here is an O(n k) time algo where k is number of bits the numbers can have: Assume integers are given in binary representation. Set 'prefix' to empty. for i from 1 to k: { Count = number of integers in the list which start with prefix followed by 1. If count is at least 2 then append 1 to ...


1

Let $x_7$ be the remainder when $B$ is divided by $A$. Let $B_1 = (B-x_7)/A$. Let $x_6$ be the remainder when $B_1$ is divided by $A$. Let $B_2 = (B_1-x_6)/A$. Let $x_5$ be the remainder when $B_2$ is divided by $A$. Let $B_3 = (B_2-x_5)/A$. ... Let $x_2$ be the remainder when $B_5$ is divided by $A$. Let $B_6 = (B_5-x_2)/A$. Finally, let $x_1 = ...


0

By way of enrichment we solve another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 4 T(\lfloor n/2 \rfloor) + n^2.$$ Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Then we can unroll the recurrence to ...


0

It looks like you are storing times as $a$ full seconds and $b$ nanoseconds. Then $x=a+b10^{-9}$ and $y=a'+b'10^{-9}$ and are asking how to represent $x-y,\quad x-y=(a-a')+(b-b')10^{-9}$ which works fine as long as $b-b'$ doesn't borrow. In that case $x-y,\quad x-y=(a-a'-1)+(b-b'+10^9)10^{-9}$


1

This is amenable to analysis by the Akra-Bazzi method. The calculations go like this, using the notation of the Wikipedia article: \begin{eqnarray*} k & = & 1 \\ a_1 & = & a \\ b_1 & = & 1/a \\ g(x) & = & x \log x \\ h(x) & = & 0 \\ p & = & 1 \Leftarrow a_1 b_1=1 \\ T(x) & = & \Theta \left ( x \left ( ...


2

Since this question is asked frequently I will try to work out a solution for generic positive integers $a$ where $a\ge 2$. Suppose we have $T(0)=0$ and $$T(1)=T(2)=\ldots =T(a-1)=1$$ and for $n\ge a$ $$T(n) = a T(\lfloor n/a \rfloor) + n \lfloor \log_a n \rfloor.$$ Furthermore let the base $a$ representation of $n$ be $$n = ...


0

Since there are $\binom{N}{2} = \Omega(N^2)$ different intervals to possibly flip over, and computing the sum after flipping a given interval involves summing $N$ numbers, the naive algorithm you propose takes either $\Omega(N^3)$ time. With some cleverness, you can improve this to $\Omega(N^2)$ by reusing certain computations. Here is an algorithm that ...


0

Suppose you are making change amount $Z$ and you can't do it with only one coin. Then $Z = X + Y$, and you've already calculated the optimum amount for $X$ and $Y$. So just check all possible $X$ and $Y$ pairs.


0

By way of enrichment here is a solution in Perl that checks its arguments very carefully and otherwise tries to keep it simple. Here is a sample run for a common choice of denominations: $ ./change.pl 100 1 2 5 10 20 50 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, ...


0

I'm late to the party. But, 2-adic Newton is pretty fast. Here's a 64-bit version: /* If x is square, return +sqrt(x). * Otherwise, return -1. */ long long isqrt(unsigned long long x) { /* Precondition: make x odd if possible. */ int sh = __builtin_ctzll(x); x >>= (sh&~1); /* Early escape. */ if (x&6) return -1; ...


0

There will be groups of cards with only positive values ($x_i > 0$) in between groups of cards with only non-positive values ($x_i \leq 0$). You can use this to limit the number of trials you consider. The motivation is that there is no benefit to including positive cards on the ends of the group of cards you're going to flip. They only hurt. ...


0

Each tile moves independently. For Type 1 moves, Bob has to move each tile that doesn't start out in the right place once. At a maximum he will make $N^2-1$ moves. For Type 2 moves, each tile has to move the Manhattan distance that it starts from its final spot number of times. Each tile moves from $0$ to $2N-2$ times. To get the average, note we can ...


1

The algorithm that joriki linked to is described in more detail in Martínez, Conrado, Alois Panholzer, and Helmut Prodinger. "Generating Random Derangements." ANALCO. 2008. http://epubs.siam.org/doi/pdf/10.1137/1.9781611972986.7 It's NOT a rejection-based algorithm (I'm not sure why Mythio thinks it is). The permutation is generated one element at a time, ...


1

This should work: Let $A'$ be all vertices with in-degree 0, and let $A''$ be their neighbors Add vertices in $A'$ to $A$ Add vertices in $A''$ to $V \setminus A$ Remove $A' \cup A''$ from $G$ and repeat steps 1-3 until the graph is empty Correctness: Since there are no edges between vertices with in-degree 0, property (i) holds for $A'$. As all ...


1

As $26^7/2^{32} \approx 1.87$, there will be only one set of $a,b,c,d,e,f,g$ for about$13\%$ of the values and two sets for all the rest. They will be related by $abcdefg_{26}=a'b'c'd'e'f'g'_{26} + 2^{32}=a'b'c'd'e'f'g'_{26}+13:23:12:17:11:23:22_{26}$ It corresponds to putting a leading $1$ in front of the base $2$ representation of the primed values. ...


0

$$(26*(26*(26*(26*(26*(26*25+25)+25)+25)+25)+25)+25)=8031810175$$ $$2*(2^{32}-1)=8589934590>\mbox{the above}$$ Hence if the number recorded is $(26(26(26(26(26(26a + b) + c) + d) + e) + f) + g)=M$ mod $2^{32}-1$, and really $(26(26(26(26(26(26a + b) + c) + d) + e) + f) + g)=N$, the possibilities are: $$N=M \mbox{ or } N=M+2^{32}-1$$ Then I guess you ...


2

Algorithms are to be understood as Turing Machines, in the majority of contexts. But you are right: from a Turing Machine, one can always modify the transition table so that the Turing Machine we obtain is different, yet it essentially does the same thing. In this context, we say that the two Turing Machines have the same language: on any input, if one ...


0

As commenters said, there is nothing incorrect with having values on the horizontal axis increasing right to left. A well-known example of such inversion of the horizontal axis is the Hertzsprung–Russell diagram of star luminosities versus their effective temperatures. The temperature increases right to left. "Hertzsprung-Russel StarData" by ESO - ...


0

The only difference between the two routines is that the second has some extra steps. The second could be written as ... [1] for i in range(len(L)): [2] for j in range(1, i): [3] if L[j] < L[i]: [4] #swap [5] for j in range(i+1, len(l)): [6] if L[j] < L[i]: [7] #swap So the second version differs from the first by the ...


0

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 2 T(\lfloor n/2 \rfloor) + n^3.$$ Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 2^k.$$ Then we can unroll the recurrence to obtain the ...


1

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=T(3)=T(4)=1$ and for $n\ge 5$ $$T(n) = 3 T(\lfloor n/5 \rfloor) + \lfloor \log_5 n \rfloor^2.$$ Then we can unroll the recurrence to obtain the following exact formula for $n\ge 5$ $$T(n) = 3^{\lfloor \log_5 n \rfloor} + ...


0

You can get a bound by looking at the smallest gap between your numbers. For your example, $0.456-0.444=0.012$ If you use $n$ bits such that $2^{-n} \lt 0.012$ you are guaranteed that the representations will be different after rounding. In this case, we find $n=7, 2^{-n}=0.0078125$ and in fact $0.456 \approx 0.0111010_2, 0.444 \approx 0.0111001_2$, so ...


0

First check if $n=2^b$, then basically look for prime powers, i.e. check if $n=a^b$ with $b$ prime up to $b = \lfloor \log n / \log 3 \rfloor\;$ (this is just 37 for $n=10^{18}).\;$ There are fast checks for $b=2$ and you can use tables mod m for small primes e.g. check $a^3 \equiv n \pmod {61}$ etc. For larger primes compute the $b'$th root with Newton. ...



Top 50 recent answers are included