Tag Info

New answers tagged

0

Here's a very straightforward solution; I haven't thought about whether it's the most efficient (in terms of keeping $m$ small). Let $\mathcal{K}=\{K_1,\ldots,K_r\}$ be the "special" subsets, and let $M$ be the "direct product" of these subsets: that is, each coupon $M$ has a list of $r$ names, one person from each subset: $$M=\{ (k_1,\ldots,k_r) \mid ...


0

Complexity issues aside, here is one method. Suppose we wanted to allow any group of people access except for one specific group $J\subseteq [n]$. We can do this by having a single coupon which we give to everybody not in $J$ (that is, assign the bitstring 0 to elements of $J$ and the bitstring 1 to the other elements). Of course this rules out subsets of ...


0

Do you mean this? The reverse function of $log_ab=c$ is $b=a^c$, therefore: The reverse of $nlog_2n=62746$ would be $$n=2^{\frac{62746}{n}}$$ or $$n^n=2^{62746}$$


0

Newton's method is effective. Let's say the answer is around $a_0=1000000/\log_21000000\approx50000$. Let $M=1000000\ln2=693147$. Then $$a_1=a_0-\frac{a_0\ln a_0-M}{1+\ln a_0}=62873\\ a_2=a_1-\frac{a_1\ln a_1-M}{1+\ln a_1}=62746$$ All my logs are the natural log, to base $e$, rather than $\log_2$.


0

One simple way to compute nth roots of integers is to use Khovanskii's matrix method. A good explanation of this process can be found here.


1

Let me first treat part one, since this is the easiest part Part 1: the number of subsets of a given set $X$ is $2^{|X|}-1$, where $|X|$ is the number of elements in $X$. I had to substract the $1$ because you are not interested in the empty subset $\emptyset$. A way to see why this is the number of options is the following: consider a set of $|X|$ slots, ...


1

If you know that $x$ can be divided by $y$ without remainder (i.e. $x/y=d \in N$ because, e.g., $y$ is the result of some gcd computation of $x$ with some other number) you can do the following (for simplicity let me further restrict the answer to $x,y>0$: $y = 2^k*y_1$ with $y_1$ odd. Hence $x$ must be divisible by $2^k$ and $x_1 = x/2^k$. $x/y$ = ...


0

You cannot, as the comments point out. $(n+1)^7 = \omega(n\log n)$, i.e. $\frac{(n+1)^7}{n\log n} \xrightarrow[n\to\infty]{} \infty$. (If what you wanted to show were true, the ratio would have to be bounded). A way to see it is that $(n+1)^7$ behaves roughly like $n^7$, while $n\log_2 n$ "behaves (almost) like $n$" (ignoring the second-order factor for ...


0

Others correctly pointed out the error. What you have is $\omega( n \log (2n))$ because the function you have is less than $(2n)^7 = O(n^7)$. Hence, if you take the limit of this function over $n \log (2n)$, you'll get infinity.


0

The fastest known algorithms are based on the Bailey-Borwein-Plouffe formula. A particular variation later developed by Plouffe (see here) can be used to calculate the base-$10$ digits of $\pi$ by using the formula $$ \pi + 3 = \sum_{n=1}^{\infty} \frac{n 2^n n!^2}{(2n)!} $$ Plouffe's method calculates the $n^{\text{th}}$ digit of $\pi$ in ...


1

As Emilio Novati stated in a comment, the sieve of Eratosthenes will work. The sieve will probably be fast enough for your needs, although potentially faster approaches exist (see Lykos's answer). I didn't want to bother converting it to pseudocode, so here is a function written in C that returns the greatest prime less than or equal to $N$. #include ...


0

There are a few algorithms available. You could for example test for any number smaller than x, starting with x-1 if it is prime, that way if you use the AKS primality test you would probably get the best scaling algorithm for the problem you are describing (polynomial in log(x) ). You could also do simple trial division to assess primality for smaller ...


0

To compute the $n^{th}$ root of the integer $N$, you can use Newton's iterations for the equation $$x^n-N=0:$$ $$x_{k+1}=x_k-\frac{x_k^n-N}{nx_k^{n-1}}=(1-\frac1n)x_k+\frac{N}{nx_k^{n-1}}.$$ You will need to implement all four arithmetic operations for long numbers; powers are computed using repeated squarings. For a good starting approximation, just use ...


2

One way to do it which i like the most are continued fractions because they make you feel that you can write an irrational number in rational terms that is $\frac{p}{q}$ form but actually its not a rational form. A continued fraction is of the form :$$ a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cdots}}} $$ So a continued fraction for $\pi$ would be ...


3

how do people compute decimal digits of irrational numbers in general? In general, you can't. Almost all real numbers are incomputable, only a countable number of real numbers are computable, $\pi$ and $e$ among them as well as almost every other number you can name. An example of an incomputable number is Chaitin's Constant. Because most of the ...


0

There are 136 solutions for this: 126478359 1 2 6 4 7 8 3 5 9 66 126478539 1 2 6 4 7 8 5 3 9 66 132458796 1 3 2 4 5 8 7 9 6 66 132458976 1 3 2 4 5 8 9 7 6 66 132956478 1 3 2 9 5 6 4 7 8 66 132956748 1 3 2 9 5 6 7 4 8 66 134765298 1 ...


0

A simple divide-and-conquer recursion looks like it comes in at $O(nk)$, just like the recurrence given by @BenKuhn. Split the variables into two halves, and inductively compute $\sigma_{n/2}^j$ for $j=0,\ldots,k$ evaluated on both halves. Iterate $r$ times, where $n\approx 2^r k$; the total work required is $2^r$ evaluations of $\{\sigma_k^j\mid 0\le j\le ...


4

There is no general way to compute the decimal expansion for an arbitrary member of the set of irrational numbers, I. :( --Proof Start-- Here's a wishy washy proof (The statements that most obviously lack support are marked with a "*", so if anyone's interested, you should look into them yourself): Consider R to be the set of real numbers. I is a proper ...


0

$x_{T}^{k}$ denotes the $k$th row in $X$ The main idea is that: the authors first defined some dictionary, and then based on them, using K-SVD to denoising the image. After that, the dictionary is updated by OMP (Orthogonal Matching Pursuit). This work will be iteratively done until satisfying convergence condition. $K-SVD$ is a very original paper on ...


3

I don't know why nobody has mentioned the fast algorithms that are actually used for calculating $π$ to extremely high precision. Here are some: Borwein's algorithm Gauss-Legendre algorithm Machin-like formulae


0

Algorithm 1 : 8n^2 Algorithm 2 : 64n*ln(n) You can simply search these two equations in Wolphram Alpha or just run both these formulas for n in Microsoft Excel you will see that Algorithm 2 starts performing better after n = 26. https://www.wolframalpha.com/input/?i=8n%5E2%2C+64n*ln%28n%29


12

You generally need to use arbitrary precision arithmetic to compute large numbers of digits of typical irrational numbers. The exception is oddball things like the Champernowne constant 0.12345678910111213141516… :) There are various arbitrary precision arithmetic packages available. Internally, they use big arrays or lists to hold groups of the digits of ...


19

I applaud your genuine curiosity. There is no general method. To compute the decimal digits for any particular irrational number you start with a definition of the number. For $\pi$ there are lots of methods known. @GregoryGrant 's answer points to one of the oldest and most famous. Archimedes started with inscribed and circumscribed regular hexagons, then ...


10

For some irrational numbers, like $\pi$, there are convenient infinite series that converge to them. So for example $$\sum_{n=1}^\infty\frac{1}{n^2}=\frac{\pi^2}{6}$$ By adding up more and more terms of this series you get closer and closer to $\pi^2/6$. You can take an estimate for some value of $n$, multiply by $6$ and then take the square root. That ...


5

Continued fractions are commonly used in order to get the decimal value with enough accuracy. For example, the A001203 sequence in the Sloan's online encyclopedia represents $\pi$ in a form of continued fraction (actually, all infinite, rational numbers can be decomposed into a finite continued fraction, whereas irrational numbers cannot).


18

Here's how Archimedes did it 2,500 years ago. $\pi$ is the circumference of a circle with diameter one. What Archimedes did was to inscribe a polygon with $n$ sides inside the circle. Like this for $n=5$. He then calculated the circumference of the polygon. This gives an approximation to $\pi$ for each $n$ and as $n$ grows it gets closer and closer to ...


0

The easiest way I've found to get the equation for a bezier curve of order / degree $N$ is to use the binomial theorem and pascal's triangle. Basically, the generic formula for Bezier curves looks like $(As+Bt)^N$ where $N$ is the degree of the curve which has $N+1$ control points. You could expand this by hand. If you wanted to create a quadratic curve ...


2

Given a set $D=\{d_1,\ldots,d_m\}\subset\mathbb N$ of coin denominations, for $n\in\mathbb N_0$ let $f(n)$ denote the minimum number of coins (with repetition) in $D$ needed to obtain sum $n$ (or $f(n)=\infty$ if it is ompossible). Then clearly $f(n)\ge 0$ for all $n$ and $f(n)=0\iff n=0$. If $n>0$ and a way to obtain $n$ with $f(n)$ coins uses at least ...


3

If you allow $k_1,k_2$ to be integers, you have accounted for moves $(p,q), (-p,-q), (q,p), (-q,-p)$, but have not allowed $(p,-q),(-p,q),(q,-p),(-q,p)$ You are correct that $k_1,k_2$ should be integers but need $k_3,k_4$ for the other moves available. Then your intuition that the $k$'s should be integers is correct. The solution will not be unique as ...


2

You have the pieces you need. You will show by induction on the number of nodes that $h(c_i)=k_i$. The first step in constructing the Huffman tree $T$ will be to combine $c_{n-1}$ and $c_n$; since $p_{n-1}=p_n=2^{-k}$ the combined node has weight $2^{-(k-1)}$ -- in particular, $1$ over a power of two. So the induction hypothesis applies to the tree $T'$ ...


2

HINT: The induction is on $n$. If $n=2$, the only possibility is that $k_1=k_2=1$: no other combination gives you $p_1+p_2=1$. You can easily verify that in that case $h(c_1)=h(c_2)=1$. For the induction step, assume the result for some $n\ge 2$, and prove it for $n+1$. Note that after you combine the the two least probable characters in the first step of ...


1

An approach : A number $n$ can be representated by $xa+yb$ with integers $x,y$ (not necessarily positive!) if and only if $n$ is a multiple of $g:=gcd(a,b)$ We can assume $gcd(a,b)=1$ because if $gcd(a,b)=g$ we can set $a'=\frac{a}{g}$, $b'=\frac{b}{g}$ and $n$ can be represented by $xa'+yb'$ if and only if $ng$ can be represented by $xa+xb$. In other ...


1

From a purely algorithmic perspective, a priority-first search should work fine for the parameters given; it's logarithmic in $a$ and $b$, and roughly linear in $k$ (depending on your implementation). At stage $k$, this algorithm produces the $k$-th smallest expressible number; it also maintains a list $C$ of "candidates" as a priority queue. Initially ...


1

Your psuedocode should be nested loops, with optional indentation for clarity. $$\sum_{a=0}^{36}\sum_{b=0}^{36}\sum_{c=0}^{36}\sum_{d=0}^{36} 1 =\quad\begin{array}{|l}\textrm{Let n=0} \\ \textrm{For a = 0 to 36 step 1} \\ \quad\textrm{For b = 0 to 36 step 1} \\ \qquad\textrm{For c = 0 to 36 step 1} \\ \qquad\quad\textrm{For d = 0 to 36 step 1} \\ ...


2

There is 1 equation and 9 unknowns, the problem is we have an underdetermined system: http://en.wikipedia.org/wiki/Underdetermined_system. The only relationship we know (in the typical phrasing of the question) is that they all belong to the set [1...9] and are mutually exclusive. While all solutions can be found using brute force (with a program), I don't ...


1

On 1: Suppose a node is on depth $i$ from the root (the root is on depth $0$, its direct children is of depth $1$, etc). What is the probability of this node to still be connected to the root? It is equal to the probability that none of the $i$ edges between it and the root is removed, i.e. $$2^{-i}$$ For a node of depth $i$ from the root, define $X_i$ to ...


2

On 2) The probability that a sequence of length $k$ is monotone is $\left(k+1\right)2^{-k}$. This because there are exactly $k+1$ distinct patterns that will be labeled as monotone, and each pattern has a probability of $2^{-k}$ to occur. A sequence of length $n$ has $\binom{n}{k}$ subsequences of length $k$. Give each a number $r\in\left\{ ...


0

[This partially answer the question, because this solution doesn't use the revolving door ordering algorithm, which is stated over literature as the best (i.e., computationally efficient) algorithm to the task] I didn't understand really well the revolving door ordering algorithm so I didn't implement it, of course I could just code the algorithm without ...


0

I think for acceptance the expression is $(a\cup b)^*b(a\cup b)$. You don't need to read something before the last $b$ but one. (for example $ba$ is accepted by your machine). For the halting and reject notice that you cannot halt in $q$ nor in $v$ since you can read anything from there. Hence the only possibility to halt and reject are: be in $r$ and ...


1

Hint: You can reduce the problem to 2-CNF-SAT. Have clauses such as $B_{17}\lor R_{17}$, $\neg B_{17} \lor \neg R_{17}$, and $\neg B_{17}\lor \neg B_{42}$.


1

I ask StackOverflow for a programmatic solution, turn out having 20 answer: 2015-05-20 01:44:23.568 Math[29526:3757225] a=3 b=2 c=1 d=5 e=4 f=7 g=8 h=9 i=6 2015-05-20 01:44:23.569 Math[29526:3757225] a=3 b=2 c=1 d=5 e=4 f=7 g=9 h=8 i=6 2015-05-20 01:44:24.074 Math[29526:3757225] a=5 b=2 c=1 d=3 e=4 f=7 g=8 h=9 i=6 2015-05-20 01:44:24.075 Math[29526:3757225] ...


0

If you want to remove the "wrong" points from the linear model before fitting it, you first need to define a criterion to decide which points are wrong. Otherwise, you can use several measures of influence such as Cook's distance or studentized residuals, but first you need to fit the entire model.


0

Your proof is correct. Just in second step note that $\sum_{i \in S} (\mu - \frac{1}{p \lambda_i}) = \sum_{i =1} ^{r} (\mu - \frac{1}{p \lambda_i})$ since for any $i \notin S $, $(\mu - \frac{1}{p \lambda_i})_+ = 0$.


0

Hint: Break up the sum into each term. $$\sum_{i=1}^{r} \left[\mu-\frac{1}{\rho \lambda_i}\right]=\sum_{i=1}^{r} \mu - \sum_{i=1}^{r}\frac{1}{\rho \lambda_i}=1$$ Then you should be able to simplify the first sum, and by factoring out $\frac{1}{\rho}$ from the second sum and rearranging you will get an answer that looks like the one given.


1

1) For your specific objective function "objfun" the minimizer can be found algebrically in one step. e.g. $x^*= 0.5(1 + x_{prev})$ 2) "fminunc" is a Quasi-Newton method (default) or Trust Region method for finding local minima. It works best when you supply the gradient and hessian of your function. If you choose this route, I suggest you write ...


1

Any turn-based game like chess can be viewed as a tree, where the root node is the starting position, each possible move for the first player is an arc from the root to another node, then all arcs from nodes in the second layer to positions in the third layer are initial moves for the second player, and so on. The leaf nodes at the bottom of the tree are ...


0

With a computer program you can do the following: The program can go through all the possible moves, all possible reactions of the human, all possible counter-reactions and so on... Now each possible move can be scored by an heuristic. The program can do the move with the best expected outcome... The program can look in a database of all recorded chess ...


3

I assume that (as usual in this type of problem) the operations are executed left toright (not by arithemtic priority). Here are the solutions: [9, 4, 8, 6, 7, 3, 1, 2, 5]: $9+13=22$, $22\times 4=88$, $88:8=11$, $11+6=17$, $17+12=29$, $29\times 7=203$, $203-3=200$, $200-11=189$, $189+1=190$, $190\times 2=380$, $380:5=76$, $76-10=66$. [9, 7, 2, 8, 4, 3, 6, ...


0

First find the factors of it by factorisation second get the prime numbers involved in that say $(a,b,\ldots)$. E.g., $18=(2^1)(3^2)$. The prime factors are $2$ and $3$. Third formula: $$\text{No. of coprimes to $N$}= N(1-1/a)(1-1/b)\cdots$$



Top 50 recent answers are included