User:Darcourse/sandbox: Difference between revisions

This is the user sandbox of Darcourse. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

Let the triple ${\displaystyle (\theta _{i},d_{i},w_{i})}$ be the angle, distance and weight of a particle from the centre of the disc.

Let P be some particles on a unit disk such that a given diameter axis ${\displaystyle d_{1}}$ means that the sum of perpendiculars from P to ${\displaystyle d_{1}}$ is zero. Let ${\displaystyle d_{2}}$ be a distinct other axis with the same property.

Prove that all ${\displaystyle d}$ have this property.

Consider two axis orthogonal to each other and a set of weights with the above property (which can be achieved by calculating the position of the ${\displaystyle n^{th}}$ weight after the first ${\displaystyle n-1}$ weights have been placed).

Note that the perpendiculars to a new rotated orthogonal pair of axes from a given weight all lie on the circumference of the circle centred halfway between the origin and the weight, radius half the full distance from O to W.

This applies to each weight, and so there are a set of circles each with a common point on the circumference of the origin and the new axes intersect with these circles at the new distances.

From trigonometric identities, we have:

${\displaystyle {\begin{aligned}\sin(\alpha +\beta )&=\sin \alpha \cos \beta +\cos \alpha \sin \beta \\\cos(\alpha +\beta )&=\cos \alpha \cos \beta -\sin \alpha \sin \beta \end{aligned}}}$

We know:

${\displaystyle {\begin{aligned}\sum w_{i}\sin \alpha _{i}&=0\\\sum w_{i}\cos \alpha _{i}&=0\end{aligned}}}$

If ${\displaystyle \alpha _{i}}$ is the original angle, and ${\displaystyle \beta }$ is the rotated amount, then we have:

${\displaystyle {\begin{aligned}w_{i}\sin(\alpha _{i}+\beta )&=w_{i}\sin \alpha _{i}\cos \beta +w_{i}\cos \alpha _{i}\sin \beta \\w_{i}\cos(\alpha _{i}+\beta )&=w_{i}\cos \alpha _{i}\cos \beta -w_{i}\sin \alpha _{i}\sin \beta \end{aligned}}}$

and summing:

${\displaystyle {\begin{aligned}\sum w_{i}\sin(\alpha _{i}+\beta )&=\sum w_{i}\sin \alpha _{i}\cos \beta +\sum w_{i}\cos \alpha _{i}\sin \beta \\\sum w_{i}\cos(\alpha _{i}+\beta )&=\sum w_{i}\cos \alpha _{i}\cos \beta -\sum w_{i}\sin \alpha _{i}\sin \beta \end{aligned}}}$

${\displaystyle {\begin{aligned}\sum w_{i}\sin(\alpha _{i}+\beta )&=\cos \beta \sum w_{i}\sin \alpha _{i}+\sin \beta \sum w_{i}\cos \alpha _{i}=0+0=0\\\sum w_{i}\cos(\alpha _{i}+\beta )&=\cos \beta \sum w_{i}\cos \alpha _{i}-\sin \beta \sum w_{i}\sin \alpha _{i}=0-0=0\end{aligned}}}$

The resultant weighted vector at the origin is therefore zero, and this is invariant over axis rotation.

Or, the lines midway between two are balanced, and this process continues ad infinitum.

Consider ${\displaystyle f(x)=x^{2}}$, ${\displaystyle x\leq y,0\leq t\leq 1}$. Then:

${\displaystyle f(tx+(1-t)y)-tf(x)-(1-t)f(y)}$

${\displaystyle =t^{2}x^{2}+2t(1-t)xy+(1-t)^{2}y^{2}-tx^{2}-(1-t)y^{2}}$

${\displaystyle =t(t-1)x^{2}+2t(1-t)xy+(1-t)(-t)y^{2}}$

${\displaystyle =-t(1-t)\left(x^{2}-2xy+y^{2}\right)}$

${\displaystyle =-t(1-t)(x-y)^{2}}$

${\displaystyle \leq 0}$

---

Consider ${\displaystyle f(x)=\log(x)}$, ${\displaystyle 0<x\leq y,0\leq t\leq 1}$. Then:

${\displaystyle f(tx+(1-t)y)-tf(x)-(1-t)f(y)}$

${\displaystyle =\log(tx+(1-t)y)-(t\log(x)+(1-t)\log(y))}$

${\displaystyle =\log(tx+(1-t)y)-\log(x^{t}y^{1-t})}$

${\displaystyle =\log({\frac {tx+(1-t)y}{x^{t}y^{1-t}}})}$

So need to prove:

${\displaystyle {\frac {tx+(1-t)y}{x^{t}y^{1-t}}}\geq 1}$

or

${\displaystyle tx+(1-t)y\geq x^{t}y^{1-t}}$

or, dividing by ${\displaystyle y}$:

${\displaystyle t\left({\frac {x}{y}}-1\right)+1\geq \left({\frac {x}{y}}\right)^{t}}$

So:

${\displaystyle t\left({\frac {x}{y}}-1\right)+1-\left({\frac {x}{y}}\right)^{t}}$

${\displaystyle =\left({\frac {x}{y}}-1\right)\left(t-{\frac {\left({\frac {x}{y}}\right)^{t}-1}{{\frac {x}{y}}-1}}\right)}$

${\displaystyle =\left({\frac {x}{y}}-1\right)\left(t-(1+{\frac {x}{y}}+\dots +\left({\frac {x}{y}}\right)^{t-1})\right)}$

${\displaystyle \geq 0}$

The Catalan q-polynomials ${\displaystyle C_{k}(q)}$ count the number of blocks present in the diagram under the diagonal height k, and start

• ${\displaystyle C_{0}(q)=1}$
• ${\displaystyle C_{1}(q)=1}$
• ${\displaystyle C_{2}(q)=1+q}$
• ${\displaystyle C_{3}(q)=1+q+2q^{2}+q^{3}}$
• ${\displaystyle C_{4}(q)=1+q+2q^{2}+3q^{3}+3q^{4}+3q^{5}+q^{6}}$

The sum of the coefficients of ${\displaystyle C_{k}(q)}$ give ${\displaystyle C_{k}}$.

To generate the next level, we add a horizontal and vertical step. The horizontal step is always placed at the origin, and the vertical step can be placed anywhere off the bounding diagonal, and is the first time the path touches the diagonal.

The first path from the convolution is inserted along the (k-1)-th diagonal created by the two endpoints of the new steps, and the second is placed along the k-th diagonal.

With Dyck words, where the new template is ${\displaystyle X(k)Y(n-k)}$, where ${\displaystyle (k)}$ is a Dyck word of length k. The X step is always first, and the Y step comes after a k-length Dyck word.

The new polynomial is therefore the heights of the previous polynomials, plus the rectangle created by the insertion.

${\displaystyle C_{n}(q)=\sum _{i=0}^{n-1}q^{i(n-i)}C_{i}(q)C_{n-i}(q)}$

For example, ${\displaystyle C_{4}(q)=q^{0}(1)(1+q+2q^{2}+q^{3})+q^{3}(1)(1+q)+q^{4}(q+1)(1)+q^{3}(1+q+2q^{2}+q^{3})(1)}$.

Let

${\displaystyle f(x)=x^{3}+cx+d}$

The local minima and maxima are given by the zeroes of the differential of ${\displaystyle f(x)}$.

${\displaystyle f'(x)=3x^{2}+c}$

If ${\displaystyle x={\sqrt {\frac {-c}{3}}}}$ then (c is negative)

${\displaystyle f(x)={\sqrt {\frac {c}{3}}}^{3}-c{\sqrt {\frac {-c}{3}}}+d}$

and ${\displaystyle f(x)>0}$ means

${\displaystyle {\sqrt {\frac {c}{3}}}^{3}\left({\frac {1}{3}}-1\right)>d}$

${\displaystyle {\sqrt {\frac {-c}{3}}}^{3}\left({\frac {2}{3}}\right)>d}$

${\displaystyle -4c^{3}>27d^{2}}$

• 12 34 56
• 13 26 45
• 14 25 36
• 15 23 46
• 16 24 35

• 12 34 58 67
• 13 24 57 68
• 14 25 36 78
• 15 26 37 48
• 16 27 38 45
• 17 28 35 46
• 18 23 47 56

${\displaystyle {\frac {1+4x+x^{2}}{(1-x)^{4}}}=1+8x+27x^{2}+64x^{3}+125x^{4}+\dots }$

https://www.wolframalpha.com/input?i=%281%2B4x%2Bx%5E2%29%2F%281-x%29%5E4

The general relation is given by the Eulerian numbers.

Prove

${\displaystyle {\binom {m}{j}}{\binom {n}{k}}\leq {\binom {m+n}{j+k}}}$

${\displaystyle ={\frac {m!n!}{j!k!(m-j)!(n-k)!}}\leq {\frac {(m+n)!}{(j+k)!(m+n-j-k)!}}}$

Consider

${\displaystyle {\frac {(m+n)!}{m!n!}}{\frac {j!k!}{(j+k)!}}{\frac {(m-j)!(n-k)!}{(m+n-j-k)!}}}$

where

${\displaystyle {\frac {(a+b)!}{a!b!}}={\binom {a+b}{a}}={\frac {(a+1)\cdots (a+b)}{b!}}=\prod _{i=1}^{b}\left(1+{\frac {a}{i}}\right)}$

so

${\displaystyle {\frac {\prod _{i=1}^{m}\left(1+{\frac {n}{i}}\right)}{\prod _{i=1}^{j}\left(1+{\frac {k}{i}}\right)\prod _{i=1}^{m-j}\left(1+{\frac {n-k}{i}}\right)}}}$

and

${\displaystyle {\frac {\binom {m+n}{m}}{{\binom {j+k}{j}}{\binom {m+n-j-k}{m-j}}}}}$

TRUTH

0000 (0) FALSE

0110 (6) XOR

1001 (9) NXOR

1111 (F) TRUE

IDEMPOTENT

0001 (1) AND

0011 (3) A

0101 (5) B

0111 (7) OR

INJECTIVE

0100 (4) LT

1100 (C) NB

1101 (D) LTE

1110 (E) NAND

SURJECTIVE

0010 (2) GT

1000 (8) NOR

1011 (B) GTE

1010 (A) NA

${\displaystyle \sum _{i=0}^{k}{\binom {n-k-1+i}{i}}2^{n-k-i}}$

${\displaystyle n=6,k=3:1+6+15+20=42}$

${\displaystyle {\binom {2}{0}}2^{3}+{\binom {3}{1}}2^{2}+{\binom {4}{2}}2+{\binom {5}{3}}=8+12+12+10=4}$2.

Catalan number

Start with the GF for the central binomial coefficient.

${\displaystyle {\frac {1}{\sqrt {1-4x}}}=\sum _{k=0}^{\infty }{\binom {2k}{k}}x^{k}}$

Integrating and setting the constant to ${\displaystyle {\frac {1}{2}}}$ from the case ${\displaystyle x=0}$ yields

${\displaystyle {\frac {1-{\sqrt {1-4x}}}{2}}=\sum _{k=0}^{\infty }{\frac {1}{k+1}}{\binom {2k}{k}}x^{k+1}}$

Divide by x to get

${\displaystyle {\frac {1-{\sqrt {1-4x}}}{2x}}=\sum _{k=0}^{\infty }C_{k}x^{k}}$

Primitive root modulo n

The order of an element is the smallest k where ${\displaystyle a^{k}\equiv 1{\pmod {n}}}$.

k divides ${\displaystyle \phi (n)}$. Testing a candidate against each possible k returns negative if and only if the candidate is a primitive root.

a/k	1	2	3	4	5	6
1	1	1	1	1	1	1
2	2	4	1	2	4	1
3	3	2	6	4	5	1
4	4	2	1	4	2	1
5	5	4	6	2	3	1
6	6	1	6	1	6	1

Fermat's theorem on sums of two squares

(5) can be proved by Euler's criterion. It also tells us that if ${\displaystyle p=4k+1}$,

${\displaystyle p|\prod _{i=1}^{4k}\left(i^{2k}+(i-1)^{2k}\right)}$

which is the sum of two squares by (1). (2), (3) and (4) can then be used to find it.

For each prime p of p-1, remove k^p from 1,..,p-1 as k runs over the same range. Only primitive roots remain.

${\displaystyle a^{k}\equiv 1{\pmod {p}}}$ if and only if ${\displaystyle k|p-1}$

For example, ${\displaystyle x^{7}-1}$ is never divisible by 13, 17, etc..., but is by 29.

Say ${\displaystyle x\equiv a{\pmod {p}}}$, and also ${\displaystyle x\equiv b{\pmod {q}}}$ with p,q primes, and a,b least residues.

Note that ${\displaystyle p^{q-1}}$ is ${\displaystyle 0{\pmod {p}}}$ and ${\displaystyle 1{\pmod {q}}}$. Similarly ${\displaystyle q^{p-1}}$ is ${\displaystyle 1{\pmod {p}}}$ and ${\displaystyle 0{\pmod {q}}}$.

Therefore ${\displaystyle aq^{p-1}+bp^{q-1}\equiv a{\pmod {p}}}$ and ${\displaystyle aq^{p-1}+bp^{q-1}\equiv b{\pmod {q}}}$, and so ${\displaystyle x\equiv aq^{p-1}+bp^{q-1}{\pmod {pq}}}$

Plane partition

The GF is

${\displaystyle \prod _{i=1}^{\infty }{\frac {1}{(1-x^{i})^{i}}}}$

Consider instead the much simpler GF of

${\displaystyle {\frac {1}{1-x}}\prod _{i=2}^{\infty }{\frac {1}{(1-x^{i})^{2}}}}$

The n-th term is the number of partitions of n into at least 0 parts + partitions of n-1 into at least 1 part + partitions of n-2 into at least 2 parts + etc...

The GF for at least k parts is

${\displaystyle LP_{k}=x^{k}\prod _{i=1}^{k}{\frac {1}{(1-x^{i})}}\prod _{i=1}^{\infty }{\frac {1}{(1-x^{i})}}}$

and

${\displaystyle \sum _{k=0}^{\infty }LP_{k}=\prod _{i=1}^{\infty }{\frac {1}{(1-x^{i})^{2}}}}$

and we have counted the single x twice.

Let ${\displaystyle \triangle ABC}$ be coordinates ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3})}$. Then the midpoints of AB and AC are

${\displaystyle \left({\frac {x_{1}+x_{2}}{2}},{\frac {y_{1}+y_{2}}{2}}\right)}$

${\displaystyle \left({\frac {x_{1}+x_{3}}{2}},{\frac {y_{1}+y_{3}}{2}}\right)}$

The perpendiculars are

${\displaystyle {\binom {y_{2}-y_{1}}{x_{1}-x_{2}}}}$

${\displaystyle {\binom {y_{3}-y_{1}}{x_{1}-x_{3}}}}$

and the equations of the perpendiculars through the midpoints are

${\displaystyle {\binom {x}{y}}={\binom {\frac {x_{1}+x_{2}}{2}}{\frac {y_{1}+y_{2}}{2}}}+s{\binom {y_{2}-y_{1}}{x_{1}-x_{2}}}}$

${\displaystyle {\binom {x}{y}}={\binom {\frac {x_{1}+x_{3}}{2}}{\frac {y_{1}+y_{3}}{2}}}+t{\binom {y_{3}-y_{1}}{x_{1}-x_{3}}}}$

with equality when

${\displaystyle {\frac {x_{1}+x_{2}}{2}}+s(y_{2}-y_{1})={\frac {x_{1}+x_{3}}{2}}+t(y_{3}-y_{1})}$

${\displaystyle {\frac {y_{1}+y_{2}}{2}}+s(x_{1}-x_{2})={\frac {y_{1}+y_{3}}{2}}+t(x_{1}-x_{3})}$

so

${\displaystyle (x_{2}-x_{3})+2s(y_{2}-y_{1})=2t(y_{3}-y_{1})}$

${\displaystyle (y_{2}-y_{3})+2s(x_{1}-x_{2})=2t(x_{1}-x_{3})}$

and then

${\displaystyle (x_{2}-x_{3})(x_{1}-x_{2})+2s(x_{1}-x_{2})(y_{2}-y_{1})=2t(x_{1}-x_{2})(y_{3}-y_{1})}$

${\displaystyle (y_{2}-y_{3})(y_{2}-y_{1})+2s(x_{1}-x_{2})(y_{2}-y_{1})=2t(x_{1}-x_{3})(y_{2}-y_{1})}$

so

${\displaystyle (x_{2}-x_{3})(x_{1}-x_{2})-(y_{2}-y_{3})(y_{2}-y_{1})=2t(x_{1}y_{3}-x_{2}y_{3}+x_{2}y_{1}-x_{1}y_{2}+x_{3}y_{2}-x_{3}y_{1})}$

Hamiltonian cycles

Generate the permutations of all vertices. Remove all those with non-adjacent vertices.

Two cuts are adjacent if the corresponding partitions differ by only 1 vertex.

An integer in base b can be written as

${\displaystyle n=\sum _{i=0}^{N}a_{i}b^{i}}$

and the same integer in base d is

${\displaystyle n=\sum _{i=0}^{M}c_{i}d^{i}}$

If ${\displaystyle d+e=b}$, then the first equation becomes

${\displaystyle n=\sum _{i=0}^{N}a_{i}(d+e)^{i}}$

Expand this using the binomial formula to get

${\displaystyle n=\sum _{i=0}^{N}a_{i}\sum _{k=0}^{i}{\binom {i}{k}}e^{k}d^{i-k}}$

and collect by like terms in d to get the second equation.

We want to add two bytes A and B. We use auxiliary bytes C and D to store the carries and answer, and a carry flag for the final bits.

Let C be initially zero, and a,b,c,d be aligned bits.

Then ${\displaystyle d=a\otimes b\otimes c}$ and ${\displaystyle c'=(a\land b)\lor (a\land c)\lor (b\land c)}$

where ${\displaystyle \otimes }$ is XOR and c' is the next carry bit.

The Jordan curve theorem states that any line crosses a closed loop on a plane an even number of times, with tangencies counting twice.

Using the fundamental polygon, a similar result can be established for the torus and other surfaces.

This leads to the observation that a if a loop on a surface disconnects it, then it creates an inside and an outside. A loop that doesn't disconnect the surface doesn't.

If f and g are continuous functions on ${\displaystyle [a,b]}$, let ${\displaystyle h(x,\lambda )=\lambda f(x)+(1-\lambda )g(x)}$.

If x is fixed,

${\displaystyle h(x,\lambda +d\lambda )-h(x,\lambda )=d\lambda (f(x)+g(x))}$

which is continuous as ${\displaystyle f(x)+g(x)}$ is constant.

If ${\displaystyle \lambda }$ is fixed,

${\displaystyle h(x+dx,\lambda )-h(x,\lambda )=\lambda (f(x+dx)-f(x))+(1-\lambda )(g(x+dx)-g(x))}$

which is continuous because ${\displaystyle f(x),g(x)}$ are.

The Client-Vendor-Bank model (CVB) involves the oAuth model.

Only the Authentication and Authorization layers are used, along with vendorId and vendorSecret. These are registered with the Bank.

The steps involved are:

1. C sends V transaction request

2. V asks C for Authentication with vendorId and transaction details from B

3. B replies to V with the AuthCode for the transaction

4. V posts AuthCode, vendorId and vendorSecret to B

5. B commits the transaction and sends receipt to V

6. V sends receipt to C

This model has minimal external interference, and is secure as B has two potentially conflicting items for the same transaction.

• Bell numbers
• Catalan numbers

The 15 Bell numbers for n = 4 with the Catalan equivalent:

• 1234 - (((())))
• 1 234 - ()((()))
• 2 134 - (()(()))
• 3 124 - ((()()))
• 4 123 - ((()))()
• 12 34 - (())(())
• 13 24 - crossed
• 14 23 = ((())())
• 12 3 4 - (())()()
• 13 2 4 - (()())()
• 14 2 3 - (()()())
• 23 1 4 - ()(())()
• 24 1 3 - ()(()())
• 34 1 2 - ()()(())
• 1 2 3 4 - ()()()()

The congruent number problem asks which square numbers are in an arithmetic progression of 3.

Are there higher powers such that 3 lie in an AP?

That is

${\displaystyle a^{n}+x=b^{n}}$

${\displaystyle b^{n}+x=c^{n}}$

or

${\displaystyle a^{n}-b^{n}=b^{n}-c^{n}}$

so

${\displaystyle a^{n}+c^{n}=2b^{n}}$

A random walk on a 2d grid arrives at coordinate ${\displaystyle (x,y)}$ after z steps, where

${\displaystyle R(x,y,z)=R(x-1,y,z-1)+R(x+1,y,z-1)+R(x,y-1,z-1)+R(x,y+1,z-1)}$

This leads to the definition

${\displaystyle R(x,y,z)=\sum _{k=0}^{z-x-y}{\frac {z!}{(x+k)!k!(y+z-x-y-k)!(z-x-y-k)!}}}$