Post by OmnipotentEntity

Posted: 6/5/2017 5:17 PM

Quote

thatguy

Editor

Joined: 11/3/2013
Posts: 506

Here's a more interesting twin prime problem: prove that the only Fibonacci numbers that are also twin primes are 3, 5 and 13. (I can remember the result, and I have been shown a proof, but I can't remember the details and Google isn't helping. But I think it relies pretty heavily on recurrence formulas for the Fibonacci numbers, and for F_n+-2, that enable you to factorise them.)

Posted: 6/6/2017 7:16 AM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

thatguy wrote:

Here's a more interesting twin prime problem: prove that the only Fibonacci numbers that are also twin primes are 3, 5 and 13.

I think you mean numbers that are one of the members of a twin prime pair? Btw, in a related note, is it hard to prove how many Fibonacci numbers are prime (as in, are there infinitely many of them)?

Posted: 6/6/2017 5:41 PM

Quote

thatguy

Editor

Joined: 11/3/2013
Posts: 506

One fact about Fibonacci numbers is they have the Mersenne-like property that F_mn is a multiple of F_m and F_n. Hence all Fibonacci numbers with composite indices are composite, except F₄, which is an exception because F₂ is 1. Another way in which the Fibonacci numbers resemble the Mersenne numbers is their exponential growth rate. It seems the problems are similar to each other, and probably equally difficult.

Posted: 6/9/2017 5:23 PM
(Edited: 7/7/2017 8:33 PM)

Quote

OmnipotentEntity

He/Him

Player (36)

Joined: 9/11/2004
Posts: 2630

I thought it might be interesting to examine what other divisors F_mn have if we remove all of the divisors from F_m and F_n

3 : {"2": 1}
4 : {"3": 1}
5 : {"5": 1}
6 : {"2": 2}
7 : {"13": 1}
8 : {"7": 1}
9 : {"17": 1}
10 : {"11": 1}
11 : {"89": 1}
12 : {"2": 1, "3": 1}
13 : {"233": 1}
14 : {"29": 1}
15 : {"61": 1}
16 : {"47": 1}
17 : {"1597": 1}
18 : {"19": 1}
19 : {"37": 1, "113": 1}
20 : {"41": 1}
21 : {"421": 1}
22 : {"199": 1}
23 : {"28657": 1}
24 : {"2": 1, "23": 1}
25 : {"5": 1, "3001": 1}
26 : {"521": 1}
27 : {"53": 1, "109": 1}
28 : {"281": 1}
29 : {"514229": 1}
30 : {"31": 1}
31 : {"557": 1, "2417": 1}
32 : {"2207": 1}
33 : {"19801": 1}
34 : {"3571": 1}
35 : {"141961": 1}
36 : {"3": 1, "107": 1}
37 : {"73": 1, "149": 1, "2221": 1}
38 : {"9349": 1}
39 : {"135721": 1}
40 : {"2161": 1}
41 : {"2789": 1, "59369": 1}
42 : {"211": 1}
43 : {"433494437": 1}
44 : {"43": 1, "307": 1}
45 : {"109441": 1}
46 : {"139": 1, "461": 1}
47 : {"2971215073": 1}
48 : {"2": 1, "1103": 1}
49 : {"97": 1, "6168709": 1}
50 : {"101": 1, "151": 1}
51 : {"6376021": 1}
52 : {"90481": 1}
53 : {"953": 1, "55945741": 1}
54 : {"5779": 1}
55 : {"661": 1, "474541": 1}
56 : {"7": 1, "14503": 1}
57 : {"797": 1, "54833": 1}
58 : {"59": 1, "19489": 1}
59 : {"353": 1, "2710260697": 1}
60 : {"2521": 1}
61 : {"4513": 1, "555003497": 1}
62 : {"3010349": 1}
63 : {"35239681": 1}
64 : {"1087": 1, "4481": 1}
65 : {"14736206161": 1}
66 : {"9901": 1}
67 : {"269": 1, "116849": 1, "1429913": 1}
68 : {"67": 1, "63443": 1}
69 : {"137": 1, "829": 1, "18077": 1}
70 : {"71": 1, "911": 1}
71 : {"6673": 1, "46165371073": 1}
72 : {"103681": 1}
73 : {"9375829": 1, "86020717": 1}
74 : {"54018521": 1}
75 : {"230686501": 1}
76 : {"29134601": 1}
77 : {"988681": 1, "4832521": 1}
78 : {"79": 1, "859": 1}
79 : {"157": 1, "92180471494753": 1}
80 : {"1601": 1, "3041": 1}
81 : {"2269": 1, "4373": 1, "19441": 1}
82 : {"370248451": 1}
83 : {"99194853094755497": 1}
84 : {"83": 1, "1427": 1}
85 : {"9521": 1, "3415914041": 1}
86 : {"6709": 1, "144481": 1}
87 : {"173": 1, "3821263937": 1}
88 : {"263": 1, "881": 1, "967": 1}
89 : {"1069": 1, "1665088321800481": 1}
90 : {"181": 1, "541": 1}
91 : {"13": 1, "741469": 1, "159607993": 1}
92 : {"4969": 1, "275449": 1}
93 : {"4531100550901": 1}
94 : {"6643838879": 1}
95 : {"761": 1, "29641": 1, "67735001": 1}
96 : {"2": 1, "769": 1, "3167": 1}
97 : {"193": 1, "389": 1, "3084989": 1, "361040209": 1}
98 : {"599786069": 1}
99 : {"197": 1, "18546805133": 1}
100 : {"401": 1, "570601": 1}
101 : {"743519377": 1, "770857978613": 1}
102 : {"919": 1, "3469": 1}
103 : {"519121": 1, "5644193": 1, "512119709": 1}
104 : {"103": 1, "102193207": 1}
105 : {"8288823481": 1}
106 : {"119218851371": 1}
107 : {"1247833": 1, "8242065050061761": 1}
108 : {"3": 1, "11128427": 1}
109 : {"827728777": 1, "32529675488417": 1}
110 : {"11": 1, "331": 1, "39161": 1}
111 : {"1459000305513721": 1}
112 : {"10745088481": 1}
113 : {"677": 1, "272602401466814027129": 1}
114 : {"229": 1, "95419": 1}
115 : {"1381": 1, "2441738887963981": 1}
116 : {"347": 1, "1270083883": 1}
117 : {"29717": 1, "39589685693": 1}
118 : {"709": 1, "8969": 1, "336419": 1}
119 : {"159512939815855788121": 1}
120 : {"241": 1, "20641": 1}
121 : {"97415813466381445596089": 1}
122 : {"5600748293801": 1}
123 : {"68541957733949701": 1}
124 : {"3020733700601": 1}
125 : {"5": 1, "158414167964045700001": 1}
126 : {"1009": 1, "31249": 1}
127 : {"27941": 1, "5568053048227732210073": 1}
128 : {"127": 1, "186812208641": 1}
129 : {"257": 1, "5417": 1, "8513": 1, "39639893": 1}
130 : {"131": 1, "2081": 1, "24571": 1}
131 : {"1066340417491710595814572169": 1}
132 : {"261399601": 1}
133 : {"3457": 1, "42293": 1, "351301301942501": 1}
134 : {"4021": 1, "24994118449": 1}
135 : {"1114769954367361": 1}
136 : {"23230657239121": 1}
137 : {"19134702400093278081449423917": 1}
138 : {"691": 1, "1485571": 1}
139 : {"277": 1, "2114537501": 1, "85526722937689093": 1}
140 : {"12317523121": 1}
141 : {"108289": 1, "1435097": 1, "142017737": 1}
142 : {"688846502588399": 1}
143 : {"8581": 1, "1929584153756850496621": 1}
144 : {"10749957121": 1}
145 : {"349619996930737079890201": 1}
146 : {"151549": 1, "11899937029": 1}
147 : {"293": 1, "3529": 1, "347502052673": 1}
148 : {"11987": 1, "81143477963": 1}
149 : {"110557": 1, "162709": 1, "4000949": 1, "85607646594577": 1}
150 : {"12301": 1, "18451": 1}
151 : {"5737": 1, "2811666624525811646469915877": 1}
152 : {"1091346396980401": 1}
153 : {"17": 1, "7175323114950564593": 1}
154 : {"229769": 1, "9321929": 1}
155 : {"21701": 1, "12370533881": 1, "61182778621": 1}
156 : {"12280217041": 1}
157 : {"313": 1, "11617": 1, "7636481": 1, "10424204306491346737": 1}
158 : {"32361122672259149": 1}
159 : {"317": 1, "97639037": 1, "229602768949": 1}
160 : {"23725145626561": 1}
161 : {"8693": 1, "612606107755058997065597": 1}
162 : {"3079": 1, "62650261": 1}
163 : {"977": 1, "4892609": 1, "33365519393": 1, "32566223208133": 1}
164 : {"163": 1, "800483": 1, "350207569": 1}
165 : {"86461": 1, "518101": 1, "900241": 1}
166 : {"35761381": 1, "6202401259": 1}
167 : {"18104700793": 1, "1966344318693345608565721": 1}
168 : {"167": 1, "65740583": 1}
169 : {"337": 1, "89909": 1, "104600155609": 1, "126213229732669": 1}
170 : {"1158551": 1, "12760031": 1}
171 : {"6841": 1, "5741461760879844361": 1}
172 : {"313195711516578281": 1}
173 : {"1639343785721": 1, "389678749007629271532733": 1}
174 : {"349": 1, "947104099": 1}
175 : {"701": 1, "17231203730201189308301": 1}
176 : {"93058241": 1, "562418561": 1}
177 : {"2191261": 1, "805134061": 1, "1297027681": 1}
178 : {"179": 1, "22235502640988369": 1}
179 : {"21481": 1, "156089": 1, "3418816640903898929534613769": 1}
180 : {"10783342081": 1}
181 : {"8689": 1, "422453": 1, "8175789237238547574551461093": 1}
182 : {"689667151970161": 1}
183 : {"1097": 1, "14297347971975757800833": 1}
184 : {"253367": 1, "9506372193863": 1}
185 : {"1702945513191305556907097618161": 1}
186 : {"63799": 1, "35510749": 1}
187 : {"373": 1, "10157807305963434099105034917037": 1}
188 : {"563": 1, "5641": 1, "4632894751907": 1}
189 : {"38933": 1, "955921950316735037": 1}
190 : {"191": 1, "41611": 1, "87382901": 1}
191 : {"4870723671313": 1, "757810806256989128439975793": 1}
192 : {"2": 1, "11862575248703": 1}
193 : {"9465278929": 1, "1020930432032326933976826008497": 1}
194 : {"3299": 1, "56678557502141579": 1}
195 : {"88999250837499877681": 1}
196 : {"5881": 1, "61025309469041": 1}
197 : {"15761": 1, "25795969": 1, "227150265697": 1, "717185107125886549": 1}
198 : {"991": 1, "2179": 1, "1513909": 1}
199 : {"397": 1, "436782169201002048261171378550055269633": 1}
200 : {"9125201": 1, "5738108801": 1}
201 : {"5050260704396247169315999021": 1}
202 : {"809": 1, "7879": 1, "201062946718741": 1}
203 : {"1217": 1, "56470541": 1, "2586982700656733994659533": 1}
204 : {"409": 1, "66265118449": 1}
205 : {"821": 1, "125598581": 1, "36448117857891321536401": 1}
206 : {"619": 1, "1031": 1, "5257480026438961": 1}
207 : {"4072353155773627601222196481": 1}
208 : {"3329": 1, "106513889": 1, "325759201": 1}
209 : {"57314120955051297736679165379998262001": 1}
210 : {"21211": 1, "767131": 1}
211 : {"22504837": 1, "38490197": 1, "800972881": 1, "80475423858449593021": 1}
212 : {"1483": 1, "2969": 1, "1076012367720403": 1}
213 : {"1277": 1, "185790722054921374395775013": 1}
214 : {"47927441": 1, "479836483312919": 1}
215 : {"2607553541": 1, "67712817361580804952011621": 1}
216 : {"6263": 1, "177962167367": 1}
217 : {"433": 1, "44269": 1, "217221773": 1, "2191174861": 1, "6274653314021": 1}
218 : {"128621": 1, "788071": 1, "593985111211": 1}
219 : {"123953": 1, "4139537": 1, "3169251245945843761": 1}
220 : {"59996854928656801": 1}
221 : {"203572412497": 1, "90657498718024645326392940193": 1}
222 : {"4441": 1, "146521": 1, "1121101": 1}
223 : {"4013": 1, "108377": 1, "251534189": 1, "164344610046410138896156070813": 1}
224 : {"223": 1, "449": 1, "1154149773784223": 1}
225 : {"11981661982050957053616001": 1}
226 : {"412670427844921037470771": 1}
227 : {"23609": 1, "5219534137983025159078847113619467285727377": 1}
228 : {"227": 1, "26449": 1, "212067587": 1}
229 : {"457": 1, "2749": 1, "40487201": 1, "132605449901": 1, "47831560297620361798553": 1}
230 : {"1151": 1, "5981": 1, "324301": 1, "686551": 1}
231 : {"9164259601748159235188401": 1}
232 : {"299281": 1, "834428410879506721": 1}

I dunno. There do seem to be more very large primes than I expected. Something I found surprising while writing this program. F_m² is divisible by F_m but not necessarily by F_m². The first counter example is F₉.

Build a man a fire, warm him for a day, Set a man on fire, warm him for the rest of his life.

Posted: 6/10/2017 7:57 AM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

I was wondering why the Mandelbrot set is symmetric on the y-axis but not on the x-axis. (If you calculate for a value a+bi whether it belongs to the set, or how many steps it takes to bail out, you get the exact same value as with a-bi. However, the same is not true for -a+bi.) It's not obvious directly from the formula z_n+1 = z_n²+c why it would be symmetric on one axis but not the other.

Posted: 6/10/2017 12:16 PM

Quote

rhebus

Joined: 2/19/2010
Posts: 248

Let z^*_n denote the nth iteration of the sequence using c^* instead of c. Then we can see that z^*_n = z_n^* (proven below). In words, we can calculate the nth member of the sequence for c^* just by computing the nth iteration for c and taking its conjugate. Membership of the Mandelbrot set is based on the magnitude of z_n going to infinity. Given that z and z^* have the same magnitude, z^*_n goes to infinity if and only if z_n goes to infinity, and so c is a member of the Mandelbrot set if and only if c^* is, which gives exactly the symmetry you describe. Proof sketch: z_n^* = z^*_n holds because complex conjugate commutes with addition and multiplication, and the sequence z_n is based only on addition and multiplication. Proof by induction: Base case: z₀^* = 0 = z^*₀ Induction step: If z_n^* = z^*_n, then: z_n+1^* = (z_n² + c)^* [by definition] = z_n^2* + c^* [conjugation distributes over addition] = z_n^*2 + c^* [conjugation commutes with squaring] = z^*_n² + c^* [using induction hypothesis] = z^*_n+1 [by definition] EDIT: The key reason why this argument doesn't work on the other axis is that the corresponding operation (negation or "unary minus") doesn't commute with multiplication/squaring: (-x)(-y) ≠ -(xy) in general, while x^*y^* = (xy)^*.

Posted: 6/10/2017 4:44 PM

Quote

HHS

Active player (286)

Joined: 10/8/2006
Posts: 356

Can you construct an algorithm that, given a set A, an integer N, and a set B of subsets of A with cardinality less than or equal to N, produces a set C of subsets of A of cardinality less than or equal to N, such that each element in B is a subset of an element in C, and C has the lowest possible cardinality?

Posted: 6/10/2017 5:37 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

rhebus wrote:

z_n+1^* = (z_n² + c)^* [by definition] = z_n^2* + c^* [conjugation distributes over addition] = z_n^*2 + c^* [conjugation commutes with squaring] = z^*_n² + c^* [using induction hypothesis]

I don't know what "induction hypothesis" means here.

= z^*_n+1 [by definition]

This seems to show why it's symmetric on the imaginary axis, but it does not show why it's not symmetric on the real axis.

EDIT: The key reason why this argument doesn't work on the other axis is that the corresponding operation (negation or "unary minus") doesn't commute with multiplication/squaring: (-x)(-y) ≠ -(xy) in general, while x^*y^* = (xy)^*.

I'm not sure I understand that. As an additional question: The z_n+1=z_n³+c fractal is (or, more precisely, appears to be) symmetric on both the imaginary and the real axes. Why is that the case? z_n+1=z_n⁴+c once again is not (even though it has a more complicated three-axis symmetry, where each axis is separated by 120 degrees.) In general, with even powers there is no real-axis symmetry, while with odd powers there is. Can this be shown to be true?

Posted: 6/10/2017 6:36 PM
(Edited: 6/11/2017 3:08 AM)

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

OmnipotentEntity wrote:

thatguy wrote:
Here's a more interesting twin prime problem: prove that the only Fibonacci numbers that are also twin primes are 3, 5 and 13. (I can remember the result, and I have been shown a proof, but I can't remember the details and Google isn't helping. But I think it relies pretty heavily on recurrence formulas for the Fibonacci numbers, and for F_n+-2, that enable you to factorise them.)
The solution is behind a paywall. http://i.imgur.com/t1ULGO6.gif

While looking for other ways to prove this, I found a nice formula involving the Fibonacci and Lucas numbers. Recall that Fibonacci numbers are defined as F₀=0, F₁=1, F_n+2=F_n+1+F_n. The first few numbers are 0,1,1,2,3,5,8,13,21,34,... , and it can even be extended backward to negative indices: ...,-8,5,-3,2,-1,1,0,1. Note that F_-n = (-1)ⁿ⁺¹F_n. Lucas numbers are related similarly, and are defined as L₀=2, L₁=1, L_n+2=L_n+1+L_n. The first few numbers are 2,1,3,4,7,11,18,29,47,... , and it can be extended backward: ...,18,-11,7,-4,3,-1,2,1. Note that L_-n = (-1)ⁿL_n. Then the entire problem above can be solved just with the following identity, which applies for all integers m,n. F_mL_n + F_nL_m = 2F_m+n. (*) Proof is by induction, which I will omit. Replacing n in (*) with -n gives: F_mL_n - F_nL_m = (-1)ⁿ2F_m-n, (**) because of F_-n = (-1)ⁿ⁺¹F_n and L_-n = (-1)ⁿL_n. Taking (*)+(**) and (*)-(**) and dividing by 2 give: F_mL_n = F_m+n + (-1)ⁿF_m-n, (***) F_nL_m = F_m+n - (-1)ⁿF_m-n. (****) @ Setting m=n in (***) gives F_2n = F_nL_n. So F_2n is prime only for n=2, which gives the twin primes 3,5. @ Setting m=n+3 in (***) gives F_2n+3 + (-1)ⁿF₃ = F_2n+3 + (-1)ⁿ2 = F_n+3L_n. So F_2n+3 + (-1)ⁿ2 is prime only for n=1, which gives the twin primes 3,5 again. @ Setting m=n+3 in (****) gives F_2n+3 - (-1)ⁿF₃ = F_2n+3 - (-1)ⁿ2 = F_nL_n+3. So F_2n+3 - (-1)ⁿ2 is prime only for n=1 and 2, which give two pairs of twin primes, 5,7 and 11,13. So the only Fibonacci primes that are part of a pair of twin primes are 3,5, and 13. Note that you can also prove that, for example, the only primes that are one away from a Fibonacci number are 2,3, and 7. (Hint: set m=n+1 and m=n+2 in both (***) and (****).)

Posted: 6/10/2017 8:25 PM

Quote

rhebus

Joined: 2/19/2010
Posts: 248

Warp wrote:

I don't know what "induction hypothesis" means here.

It's a proof by induction: it works by assuming that z_n^* = z^*_n and using this assumption to show that z_n+1^* = z^*_n+1. The step labelled "using induction hypothesis" is the part where I rely on the assumption that z_n^* = z^*_n.

EDIT: The key reason why this argument doesn't work on the other axis is that the corresponding operation (negation or "unary minus") doesn't commute with multiplication/squaring: (-x)(-y) ≠ -(xy) in general, while x^*y^* = (xy)^*.
I'm not sure I understand that.

What I'm saying is: if you try to do my proof by induction, but using negation instead of complex conjugation, the step labelled "[conjugation commutes with squaring]" won't work any more, because negation doesn't commute with squaring: (-x)² ≠ -x². Admittedly saying this proof doesn't work isn't the same as saying that there definitely isn't horizontal symmetry. I'm pretty sure this is only one or two steps away from proving that though.

As an additional question: The z_n+1=z_n³+c fractal is (or, more precisely, appears to be) symmetric on both the imaginary and the real axes. Why is that the case?

If you understood what I wrote above, you'll see this is directly related to the following series of identities: (-x)² = x² (-x)³ = -x³ (-x)⁴ = x⁴ (-x)⁵ = -x⁵ ... For any odd natural number n, negation commutes with raising to the nth power, and so you can use the above proof by induction to show that there is horizontal symmetry. For every even number, negation does not commute with raising to the nth power, so the proof fails.

Posted: 6/11/2017 3:08 AM

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

Actually, horizontal flip doesn't correspond to negation, but negation of complex conjugation. (Negation is 180-degree rotation.) Your point still stands though. In the general case z_n+1=z_n^k+c, there is actually rotational symmetry (by multiples of 2π/(k-1)) combined with vertical reflection symmetry (complex conjugation).

rhebus wrote:

Admittedly saying this proof doesn't work isn't the same as saying that there definitely isn't horizontal symmetry. I'm pretty sure this is only one or two steps away from proving that though.

For z_n+1=z_n²+c, let c=1. Then the sequence is 0,1,2,5,26,... so 1 is not in the Mandelbrot set. On the other hand, for c=-1, the sequence is 0,-1,0,-1,... and so -1 is in the set. Same kind of argument for even powers greater than 2.

Posted: 6/11/2017 7:27 PM

Quote

rhebus

Joined: 2/19/2010
Posts: 248

FractalFusion wrote:

Actually, horizontal flip doesn't correspond to negation, but negation of complex conjugation. (Negation is 180-degree rotation.)

Oh, of course! Nice catch.

Posted: 6/17/2017 11:56 AM

Quote

r57shell

Player (98)

Joined: 12/12/2013
Posts: 378
Location: Russia

Idk would it be interesting for you or not, but atm I'm trying to beat following question: What is setup of Sonic 3 Special Stage with blue spheres. By setup I mean: position, radius of sphere, position, target, fov of camera.

Posted: 6/21/2017 6:54 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

In many situations, especially when it concerns animating things, it's useful to have easing functions that take a linearly-changing parameter t, which gets values from 0.0 to 1.0, and return a curve (that likewise starts from 0.0 and ends in 1.0, but does something else than increase linearly). One useful such easing function is one that starts slow and accelerates up to t=0.5, and then decelerates and ends slow in t=1.0. (This is useful eg. when animating an object on screen, to have it perform that kind of smooth accelerating/decelerating motion instead of moving at constant speed.) One way of creating such a function is to make it polynomial, like this:

double easeInOut(double t, double exponent)
{
    if(t < 0.5) return pow(2 * t, exponent) * 0.5;
    else return 1 - pow(2 * (1 - t), exponent) * 0.5;
}

What this does is that when t < 0.5, it's scaled to the range 0-1, the exponent is applied to it, and then scaled back to the range 0-0.5. And when t >= 0.5, the same is done, but mirroring t about 0.5 (thus getting a mirrored curve). This allows choosing the speed at which the acceleration/deceleration changes, so that with exponent values that are close to 1.0 the acceleration is not very pronounced, and with larger values it gets more pronounced. For example with an exponent of 2 we get this nice easing curve:

With an exponent of 4 the curve is more pronounced:

The important thing is that the curve is smooth over the entire range. Now, what if we wanted the starting acceleration to be less pronounced than the ending deceleration? In other words, what if we wanted to use two exponents rather than one: The first exponent for the first half, and the second exponent for the second half. We can't simply plug the two exponents in the above code because the resulting curve is not smooth:

There's a visible jump in slope at t=0.5 (and this jump becomes very obvious if eg. used in an animation). So my question is: How to get a smooth curve like this, where the starting half uses one exponent and the ending half uses another? One possibility would be to change those 0.5 factors in the formula, so that the joint point at t=0.5 goes up or down (in this example it would have to go up). But by how much, exactly?

Posted: 6/21/2017 7:34 PM

Quote

rhebus

Joined: 2/19/2010
Posts: 248

It depends what you mean by "smooth", but you probably want Cⁿ continuity for n=1 or n=2. (See wiki on smoothness for more on this.) I'd probably use a B-spline which, as the article states, is a curve which "has minimal support with respect to a given degree, smoothness, and domain partition". In this sense it is the optimal solution to your problem (to the extent that your problem is well-defined at all).

Posted: 6/21/2017 9:20 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

rhebus wrote:

I'd probably use a B-spline

But in the context of this thread I was posing the challenge of how to calculate that factor in the formula (which is now 0.5) in order to make the curve smooth. Why wouldn't that problem be well-defined?

Posted: 6/21/2017 10:52 PM

Quote

Tub

Joined: 6/25/2005
Posts: 1377

You still haven't told us what you mean by "smooth". You can make it C¹-continuous by deriving both functions, comparing their value at x=0.5 and scaling until they match. That's easy. If you require C²-continuous or more, moving the center point won't be enough. Css transitions use cubic bezier curves for easing. IIRC they're perfectly smooth, and the parametrization used in css guarantees that the curve is monotoneous in time and doesn't self-intersect. For any real application, I'd use those.

m00

Posted: 6/22/2017 5:52 AM

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

I'm pretty sure Warp is referring to C¹-continuity (continuous and once differentiable) as "smooth"; the functions defined above in Warp's post, even for the same exponent, are not C²-continuous (continuous and twice differentiable). I'm assuming that what Warp means is that the function defined on [0,0.5] must be a scaling (horizontal and/or vertical) of y=xⁿ, and that it is not allowed to be transformed in any other way. And similarly the function defined on [0.5,1] is defined as above, but rotated 180 degrees around the point (0.5,0.5). Warp's question is: for given exponents, what is the y value of the point where these two segments meet (when x=0.5), so that the resulting curve is continuous and once differentiable? Note that scaling y=xⁿ horizontally and vertically gives y=C(Dx)ⁿ, which we can rewrite as y=(CDⁿ)xⁿ. So we can assume that the function f is defined as y=Ax^m on [0,0.5], y=1-B(1-x)ⁿ on [0.5,1]. Then f must be continuous and differentiable at 0.5. That gives the two equations: A(0.5)^m = 1-B(0.5)ⁿ Am(0.5)^m-1 = Bn(0.5)^n-1 Solving this (I leave this to the reader) gives B=m2ⁿ/(m+n), A=n2ⁿ(m+n). So at x=0.5, y=n2^n-m/(m+n). By the way, my first thought of an "easing function" was the sine curve 0.5+0.5sin(π(x-0.5)).

Posted: 6/22/2017 9:07 AM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

I suppose that my use of the word "smooth" was not what it means in mathematics, as there it means "infinitely differentiable", rather than just "once differentiable". A hint that I referred to the latter might have been given by me saying in my post "there's a visible jump in slope at t=0.5", which refers to the first derivative (and that only).

FractalFusion wrote:

So we can assume that the function f is defined as y=Ax^m on [0,0.5], y=1-B(1-x)ⁿ on [0.5,1]. ... So at x=0.5, y=n2^n-m/(m+n).

That doesn't seem correct. Rather obviously (at least for values of m and n greater than 1) y ought to be between 0 and 1. In other words, somewhere in between the starting point (which is at y=0) and the ending point (at y=1). But, for example, if m=2 (the first half is quadratic) and n=4 (the second half is quartic), that formula gives 4*2^4-2/(2+4) = 16/6, which is > 1. Edit: By the way, your functions are not correct. They should be: y = A(2x)^m, x=[0, 0.5] y = 1 - B(2(1-x))ⁿ, x=[0.5, 1] I don't know if the error stems from this.

Posted: 6/22/2017 9:47 AM

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

Found the mistake. I put A=n2ⁿ(m+n) when it should have been A=n2^m(m+n). (Apologies, that was a really dumb error on my part.) That gives y=n/(m+n) at x=0.5. So now y is clearly between 0 and 1.

Warp wrote:

Edit: By the way, your functions are not correct. They should be: y = A(2x)^m, x=[0, 0.5] y = 1 - B(2(1-x))ⁿ, x=[0.5, 1]

It doesn't really matter; y = A(2x)^m can be rewritten as y = Cx^m where C = A2^m. Similarly y = 1 - B(2(1-x))ⁿ can be rewritten as y = 1 - D(1-x)ⁿ where D = B2ⁿ. Edit: But now I see that it would probably have been better to solve it that way.

Posted: 6/22/2017 10:27 AM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

FractalFusion wrote:

That gives y=n/(m+n) at x=0.5.

That seems to indeed give a proper result. For example, if m=2 and n=4, plugging in 4/6 and 1-4/6 as the factors in the equation gives us the nice smooth curve:

Posted: 6/24/2017 9:29 AM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

I was wondering if it would be reasonable to generalize the challenge: What if I wanted for the transition from the first curve to the second one to happen somewhere else than at x=0.5? Could the formula be generalized so that transition happens at any given x within the range (0, 1) (non-inclusive)? I suppose that if I expressed the question as code, it would be like:

double easeInOut(double t, double exp1, double exp2, double threshold)
{
    double thresholdY = ...;
    if(t < threshold) return pow(t / threshold, exp1) * thresholdY;
    else return 1 - pow((1 - t) / (1 - threshold), exp2) * (1 - thresholdY);
}

In my original question threshold was 0.5, and thresholdY = exp2/(exp1+exp2). But what would a more generalized formula be, for any value of threshold between 0.0 and 1.0 (non-inclusive)?

Posted: 6/24/2017 6:32 PM

Quote

FractalFusion

Editor, Expert player (2073)

Joined: 6/15/2005
Posts: 3282

Let's suppose that, instead of meeting at x=0.5, the segments meet at x=d where d is in (0,1). Then we write the segments as: y=A(x/d)^m, x in [0,d] y=1-B((1-x)/(1-d))ⁿ, x in (d,1] The function must be continuous and differentiable at d. This gives: A = 1-B Am/d = Bn/(1-d) Solving the equations for A and B gives A=dn/(dn+(1-d)m) and B=(1-d)m/(dn+(1-d)m). The segments meet at x=d, y=dn/(dn+(1-d)m).

Posted: 6/24/2017 10:17 PM

Quote

Warp

Banned User

Joined: 3/10/2004
Posts: 7698
Location: Finland

That seems to work. In this example, exp1=2, and exp2=4. On the left the threshold is 0.3, and on the right it's 0.7.

Forum Off topic some math challenges.

Forum

Off topic

some math challenges.