Wikipedia:Reference desk/Archives/Mathematics/2014 March 20

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 20

Sequences

Define a Poseidon Sequence s with s[0] = A, s[1] = B, and s[i] = abs(s[i-2] - s[i-1]) for i >= 2. Find the smallest i such that s[i] = 0.

For example, if I gave you 5 and 18, i = 13 and the sequence would look like 5, 18, 13, 5, 8, 3, 5, 2, 3, 1, 2, 1, 1, 0.

I've noticed a few patterns in the sequence. Given 3 and 44, you get 3, 44, 41, 3, 38, 35, 3, 32, 29, 3, 26, 23, 3, 20, 17, 3, 14, 11, 3, 8, 5, 3, 2, 1, 1, 0. So we observe that:

• The sequence has a certain number (bolded; in this case, 3) that will appear every 2 numbers.
• The sequence always ends with a form of 2, 1, 1, 0 (eg 444 and 333 results in 444, 333, 111, 222, 111, 111, 0).

Compare this with 37, 4: 37, 4, 33, 29, 4, 25, 21, 4, 17, 13, 4, 9, 5, 4, 1, 3, 2, 1, 1, 0.

Or 22, 19: 22, 19, 3, 16, 13, 3, 10, 7, 3, 4, 1, 3, 2, 1, 1, 0.

However, consider 8348 and 2223: 8348, 2223, 6125, 3902, 2223, 1679, 544, 1135, 591, 544, 47, 497, 450, 47, 403, 356, 47, 309, 262, 47, 215, 168, 47, 121, 74, 47, 27, 20, 7, 13, 6, 7, 1, 6, 5, 1, 4, 3, 1, 2, 1, 1, 0. Which number appears every 2 numbers? It appears that this sequence has more than one of these. I am not sure of the ramifications this has.

Those who are more computer-literate can compile the following program to list the full sequence:

This discussion has been closed. Please do not modify it.
The following discussion has been closed. Please do not modify it.
#include <iostream> #include <vector> #include <cstdio> #include <cmath> using namespace std; typedef long long LL; int main() { LL a, b; cin >> a >> b; printf("%d, %d, ", a, b); LL counter = 2; while (true) { LL tmpa; tmpa = abs(a - b); printf("%d", tmpa); if (tmpa == 0) { printf("\ni = %d\n", counter); return 0; } else { printf(", "); } a = b; b = tmpa; counter++; } }

The question is, is there a way to determine the smallest i such that s[i] = 0 without actually going through the entire sequence? →Σσς. (Sigma) 01:36, 20 March 2014 (UTC)

'( Not convinced that the do not modify tag is intentional - I suspect a side effect of the show code block.)' The 3rd example appears to be 41 & 3 not 44 & 3. You say a certain number appears every 2 numbers. Please expand - I don't follow this. -- SGBailey (talk) 07:05, 20 March 2014 (UTC)

Thank you. You are correct in that the "do not modify" is not intentional. It is just the default title for the {{hat}} template. I have updated my original post and tried to elaborate on what this certain number, this common difference, is referring to. →Σσς. (Sigma) 07:38, 20 March 2014 (UTC)

The sequence appears to be a similar to the Euclidean algorithm, so the number of terms before you reach zero is probably a function of the continued fraction expansion of A/B. Note that the sequence eventually reaches the cycle (g, g, 0) where g is the GCD of A and B. In fact the experiments I've done suggest that when all the entries in the continued fraction are odd then the number of terms before you reach zero is s+l where s us the sum of the entries and l is the length of the continued fraction expansion. If there are even entries then it increases the number of terms needed, by how much seems to be rather complicated but I'd say a good estimate is one half the number of even terms. For a variation on this question, note that the value A/B=r can be reconstructed from the sequence of signs of s[i]-s[i-1]. This produces a "notation" for r which terminates if r is rational and continues infinitely otherwise. For example the notation for 2.25 is (1, -1, 1, -1, 1, 1, -1, 1) and for the golden ratio it would be (1, 1, 1, ... ). Not all sequences are possible, for example you can't get two consecutive -1's. Is there a simple characterization of the possible sequences and a formula for the number of possible sequences of a given length? The first few are 1=(), 2=(1), .5 = (-1, 1), 1.5 = (1, 1), ... --RDBury (talk) 11:11, 20 March 2014 (UTC)

That's an interesting thought. However, there are a few cases where the continued fraction contains 0 even entries and your solution gives the wrong answer. For example, 3, 10 or 18, 11 to name two. I will look further into this and continued fractions, but I just thought it would be useful to let you know. →Σσς. (Sigma) 07:44, 24 March 2014 (UTC)

The repetition you mention exists because you are doing the following: Start with a small value A. Now, introduce a larger value B. So, in your longer sequence, you have A, B. The next value will be B-A, we will call C. So, you have A, B, C. The next item will be B-C (because we know that A is positive and C=B-A, we know that B>C). However, C=B-A, so this new value is actual B-(B-A), which is just A. You have A, B, C, A. Now, you start over with a new B. If it is larger than A, you get A, B, C, A all over again. — Preceding unsigned comment added by 209.149.115.96 (talk) 16:23, 24 March 2014 (UTC)

Inequality about plane motions.

Suppose we have a curve $f:\mathbb {R} \to \mathbb {R} ^{2}$ with $\|f'(t)\|=1$, and $\|f''(t)\|\leq 1$ for all $t$. I wish to deduce that $\|f(\pi )-f(0)\|\geq 2$, and that the optimal curve is in fact a circle $f(t)=(\cos(t),\sin(t))$ of radius 1 . Do you have a proof? Thanks!! 95.223.99.151 (talk) 10:33, 20 March 2014 (UTC)

The function $f(t)=(t,0)$ satisfies your two constraints, so no proof. --Mark viking (talk) 20:08, 20 March 2014 (UTC)

Actually in that case f(π)-f(0)=π>2 so the statement holds.

I have a partial solution and since no one has come forward with a complete answer I'll post what I have. In the notation of Tangential angle#Polar tangential angle, and since in this case t=s=arc length

$r'(s)=\cos \psi ,\,r\theta '(s)=\sin \psi$.

Here (r, θ) are the polar coordinates, ψ is the polar tangential angle, and φ = θ + ψ is the tangential angle. Since the curve is parameterized by arc length it's easy to show |φ′|=|f′′| so |φ′|≤1. Assume the curve starts at the origin and the initial direction is toward the x-axis, so φ(0) = θ(0) = ψ(0) = r(0) = 0. Let K be the smallest number so that ψ(K)≥π/2. First I claim that θ′≤1/2 for 0≤s≤K. Let

$I=r^{2}(1-2\theta ')=r^{2}-2r\sin \psi .$

Then

$I'=2rr'-2r'\sin \psi -2r\cos \psi \psi '$

$=2r\cos \psi -2\cos \psi \sin \psi -2r\cos \psi \psi '$

$=2\cos \psi (r-\sin \psi -r\phi '+r\theta ')$

$=2\cos \psi (r-r\phi ')$

$=2r\cos \psi (1-\phi ')\geq 0\ {\text{for}}\ 0\leq s\leq K$.

I(0) is 0 and I is non-decreasing so I≥0 and therefor θ′≤1/2 for s between 0 and K. Similarly θ′≥-1/2 so |θ′|≤1/2

From the equation for arc length in polar coordinates

$r'^{2}+(r\theta ')^{2}=1$

and combining this with the previous result

$r'\geq {\sqrt {1-{\frac {r^{2}}{4}}}}$

${\frac {r'}{\sqrt {1-{\frac {r^{2}}{4}}}}}\geq 1$

and integrating both sides

$2\arcsin {r \over 2}\geq s$

$r\geq 2\sin {s \over 2}$

for s between 0 and K. If K=π, which seems likely but I'm stuck on that point, then r(π)≥2 and we are done, but all I have at the moment is K>0. Interesting problem. --RDBury (talk) 00:11, 21 March 2014 (UTC)

Limit of sum of matrices

Dear all,

I want to evaluate $S=\sum _{n=1}^{\infty }A^{n}\times B$, where $A=\left({\begin{matrix}1-a&1-a\\-ab&1-ab\end{matrix}}\right)$ and $B=\left({\begin{matrix}a\\ab\end{matrix}}\right)$, where $a$ and $b$ anywhere between 0 and 1.

I have tried to solve it analytically, but I did not saw it converge any time soon. So, I solved it numerically (with Matlabfor a whole range of $a$ and $b$ between 0 and 1) and it turned out that this sum perfectly equals $S=\left({\begin{matrix}1-a\\-ab\end{matrix}}\right)$.

Although this result is very nice, I still cannot figure out why this is the case. Probably I am unaware of (or I have forgotten) some property. Is there anyone around, who can help me in the right direction of showing that this nice numerical result actually holds analytically? Any help would be appreciated. Greetings from the Netherlands, Rubietje88 (nl) 15:21, 20 March 2014 (UTC)

By diagonalizing, you can compute an explicit expression for Aⁿ. Wolfram alpha can do this, input [[1-a,1-a],[-ab,1-ab]]^n. Then multiply by B to get an expression for AⁿB and you should be able to compute the sum in each entry without much trouble. Staecker (talk) 15:38, 20 March 2014 (UTC)

Forget $\scriptstyle {\mathbf {B} }$, $\scriptstyle {a}$ and $\scriptstyle {b}$ to start with and try to prove that the sum of the geometric series is

${\begin{aligned}\sum _{n=1}^{\infty }\mathbf {A} ^{n}&=(\mathbf {A} ^{-1}-1)^{-1}\\&=(1-\mathbf {A} )^{-1}-1\end{aligned}}$

for any $\scriptstyle {\mathbf {A} }$ for which the sum converges. Use this to get your final answer. Note that the series on the geometric series page starts from 0 rather than 1, so that the sums differ by $\scriptstyle {\mathbf {A} ^{0}=1}$. No diagonalization or software is necessary. --catslash (talk) 16:24, 20 March 2014 (UTC)

Thanks a lot Catslash, that made perfect sense! Greetings from the Netherlands, Rubietje88 (nl) 09:23, 21 March 2014 (UTC) PS: (I figured out that you meant the Identity matrix where you wrote a one ;))