Wednesday, July 20, 2016
My teenage son wants to go grocery shopping with us
The other day I was going to the grocery store to do some shopping and my son said to me: "I want to go with you to the grocery store." This has never happened before. He is also spending more time outside. I believe it is all due to this life changing program that my son has downloaded on his phone. It is a proven system (proven within the last week or so) that has gotten many people exercising more and spending more time outside. The basic premise is simple; the goal is to catch small monsters (so called pocket monsters) while wandering around the neighborhood. All I can say is Bravo to the creators of this app!
Monday, June 20, 2016
Meta recurrences
In my freshman year at college, my roommate Joe introduced me to the book "Gödel, Escher, Bach: an Eternal Golden Braid" by Douglas Hofstadter that I really enjoyed reading. In this book, Hofstadter considers sequences whose recurrence relation is such that the arguments themselves depend on the terms of the sequence. For instance, the classical Fibonacci sequence is defined by f(n) = f(n-1) + f(n-2), with f(1) = f(2) = 1. Hofstadter considered a meta Fibonacci sequence defined by q(1) = q(2) = 1, and q(n) = q(n-q(n-1)) + q(n-q(n-2)). Not much is known about this sequence, except that it behaves wildly. It is not even known whether the sequence is well defined!
Several variants of meta Fibonacci sequences have been analyzed in Refs. [1-4].
For some simpler meta recurrences, much more can be said about them. For instance Golomb showed that sequences satisfying the recursion a(n) = a(n - a(n-1)) is eventually periodic when it is well-defined. He also showed several meta recurrences with explicit solutions, such as a(n) = a(a(n)).
In particular, he showed that the recursion a(n) = a(n-a(n-1)) + 1 with a(1) = 1 has a simple solution described by the sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ....
Next we show that this last recursion can be generalized as follows. For an integer k, define the meta recurrence a(n) = a(n-a(n-k))+k with initial conditions a(i) = i for i = 1,...,k. This recurrence has a simple solution and it can be constructed starting with km copies of k(m+1), followed by km+1, km+2, ..., k(m+1), as m varies from 0, 1, 2, ... It is straightforward to verify that this construction satisfies the recurrence relation. Thus for each k the sequence corresponding to the meta recurrence is well defined, every positive integer is in the sequence, and every integer not a proper multiple of k appears once. If t is a multiple of k, then t appears t-k+1 times.
The cases of k=2 and k=3 are shown in OEIS sequences A193358 and A274213 respectively.
For k = 4, the sequence is: 1, 2, 3, 4, 8, 8, 8, 8, 5, 6, 7, 8, 12, 12, 12, 12, 12, 12, 12, 12, 9, 10, 11, 12, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 13, 14, 15, 16, ....
References
[1] S.M Tanny "A well-behaved cousin of the Hofstadter sequence," Discrete Math., 105 (1992), pp. 227–239.
[2] Callaghan, Joseph, John J. Chew III, and Stephen M. Tanny. "On the behavior of a family of meta-Fibonacci sequences." SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824.
[3] B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
[4] C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12.
Several variants of meta Fibonacci sequences have been analyzed in Refs. [1-4].
For some simpler meta recurrences, much more can be said about them. For instance Golomb showed that sequences satisfying the recursion a(n) = a(n - a(n-1)) is eventually periodic when it is well-defined. He also showed several meta recurrences with explicit solutions, such as a(n) = a(a(n)).
In particular, he showed that the recursion a(n) = a(n-a(n-1)) + 1 with a(1) = 1 has a simple solution described by the sequence 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ....
Next we show that this last recursion can be generalized as follows. For an integer k, define the meta recurrence a(n) = a(n-a(n-k))+k with initial conditions a(i) = i for i = 1,...,k. This recurrence has a simple solution and it can be constructed starting with km copies of k(m+1), followed by km+1, km+2, ..., k(m+1), as m varies from 0, 1, 2, ... It is straightforward to verify that this construction satisfies the recurrence relation. Thus for each k the sequence corresponding to the meta recurrence is well defined, every positive integer is in the sequence, and every integer not a proper multiple of k appears once. If t is a multiple of k, then t appears t-k+1 times.
The cases of k=2 and k=3 are shown in OEIS sequences A193358 and A274213 respectively.
For k = 4, the sequence is: 1, 2, 3, 4, 8, 8, 8, 8, 5, 6, 7, 8, 12, 12, 12, 12, 12, 12, 12, 12, 9, 10, 11, 12, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 13, 14, 15, 16, ....
References
[1] S.M Tanny "A well-behaved cousin of the Hofstadter sequence," Discrete Math., 105 (1992), pp. 227–239.
[2] Callaghan, Joseph, John J. Chew III, and Stephen M. Tanny. "On the behavior of a family of meta-Fibonacci sequences." SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824.
[3] B. Balamohan, A. Kuznetsov and S. Tanny, On the behavior of a variant of Hofstadter's Q-sequence, J. Integer Sequences, Vol. 10 (2007), #07.7.1.
[4] C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12.
Continued fraction expansion of the square root of n
Results from Galois imply that the continued fraction expansion of $\sqrt{n}$ is of the form $[a_0; \overline{a_1,a_2,\cdots, a_2, a_1, 2a_0}]$ (see also Ref.[1], page 469).
In OEIS sequences A031710, A031712, A031713, A031749 and several other sequences, the least number among the periodic part of the continued fraction expansion is considered, i.e what is $\delta(n) \triangleq \min (a_1,a_2,\cdots, a_2, a_1, 2a_0)$?
If $t$ is an integer that divides $2k$, then it is straightforward to verify that the continued fraction expansion of $\sqrt{(km)^2+tm}$ for $m \geq 1$ is equal to $[km; \overline{\frac{2k}{t}, 2km}]$. This implies the following result:
If $r$ is even, then $\delta((\frac{rm}{2})^2+m) = r$ for all $m\geq 1$.
If $r$ is odd, then $\delta((rm)^2+2m) = r$ for all $m\geq 1$.
References:
[1] Charles Smith, A Treatise on Algebra, Fifth Edition, Macmillan and Co., 1896.
In OEIS sequences A031710, A031712, A031713, A031749 and several other sequences, the least number among the periodic part of the continued fraction expansion is considered, i.e what is $\delta(n) \triangleq \min (a_1,a_2,\cdots, a_2, a_1, 2a_0)$?
If $t$ is an integer that divides $2k$, then it is straightforward to verify that the continued fraction expansion of $\sqrt{(km)^2+tm}$ for $m \geq 1$ is equal to $[km; \overline{\frac{2k}{t}, 2km}]$. This implies the following result:
If $r$ is even, then $\delta((\frac{rm}{2})^2+m) = r$ for all $m\geq 1$.
If $r$ is odd, then $\delta((rm)^2+2m) = r$ for all $m\geq 1$.
References:
[1] Charles Smith, A Treatise on Algebra, Fifth Edition, Macmillan and Co., 1896.
Saturday, May 28, 2016
Generating functions of sequences
The generating function of a sequence
$\{a(n)\}_{n=0}^\infty = \{a_0, a_1, a_2, \cdots\}$ for integers $n\geq 0$ is defined as $f(x) = a_0 + a_1x + a_1x^2 + \cdots$.
For a sequence that satisfies the linear recurrence relation
$a(n) = c_0a(n-1) + c_1a(n-2) + \cdots + c_{m}a(n-m-1)$
with initial terms $a(0) = a_0, a(1) = a_1, \cdots , a(m) = a_m$,
the general form of the generating function is given by:
$$ f(x) = \frac{a_mx^m + \sum_{i=0}^{i< m}\left(a_ix^i- c_ix\sum_{j=0}^{j < m-i}a_jx^{i+j}\right)}{
1-x\sum_{i=0}^{i \leq m}c_ix^{i}}
$$
The sequence $a(n) = bc^n+d$ satisfies the recurrence relation $a(n) = (c+1)a(n-1)-ca(n-2)$ with
generating function:
$$ (b(1-x) + d(1- cx ))/((1-x )(1-cx)) $$.
$\{a(n)\}_{n=0}^\infty = \{a_0, a_1, a_2, \cdots\}$ for integers $n\geq 0$ is defined as $f(x) = a_0 + a_1x + a_1x^2 + \cdots$.
For a sequence that satisfies the linear recurrence relation
$a(n) = c_0a(n-1) + c_1a(n-2) + \cdots + c_{m}a(n-m-1)$
with initial terms $a(0) = a_0, a(1) = a_1, \cdots , a(m) = a_m$,
the general form of the generating function is given by:
$$ f(x) = \frac{a_mx^m + \sum_{i=0}^{i< m}\left(a_ix^i- c_ix\sum_{j=0}^{j < m-i}a_jx^{i+j}\right)}{
1-x\sum_{i=0}^{i \leq m}c_ix^{i}}
$$
The sequence $a(n) = bc^n+d$ satisfies the recurrence relation $a(n) = (c+1)a(n-1)-ca(n-2)$ with
generating function:
$$ (b(1-x) + d(1- cx ))/((1-x )(1-cx)) $$.
How to lose weight without working out
Today, my son said: "Since we are spinning along with the earth, shouldn't the centrifugal force make us feel lighter?" The answer is yes, since the centrifugal force cancels out a little bit of the gravitational pull of the Earth. In fact, that is exactly what a satellite does. It spins so fast around the earth that the centrifugal force cancels out the gravitational pull so it is "floating" in space. The centrifugal force is a virtual or fictitious force denoting the opposite of the force (the centripetal force) needed to achieve the circular motion and this centripetal force is supplied by the force of gravity. There is another interpretation where the satellite is forever falling towards earth, but the motion also has a velocity component that is perpendicular to the force of gravity and its direction changes (due to the gravitational acceleration), but the magnitude doesn't.
How much lighter do you weight on the equator, where you are spinning the fastest, versus on the poles where you are not spinning at all. There are 2 reasons why you weight is different on the poles versus the equator. The first reason is the centrifugal force described above.
This force is given by Newton's second law: $F = ma$ along with $a = \omega^2r$. $\omega$ is the angular velocity of the earth rotation, i.e. $\frac{2\pi}{T}$, where $T$ is about 24 hours = $86400s$. The radius at the equator is about $r$ = 6378137 m. This results in a=0.03373 which is about 0.34% of the gravitational acceleration of $g =9.8 \frac{m}{s^2}$
The second reason is that the earth is not a perfect sphere but is squashed on the poles since the centrifugal force of the spinning earth pulls the matter of the earth from the center of mass and this happens more at the equator than at the poles. Thus you are further away from the center of mass of the Earth on the surface of the equator than on the surface of the pole. This affects the value of $g = \frac{MG}{r^2}$ where $M$ is the mass of the Earth and $G$ is the universal gravitational constant. This adds another 0.67% to the difference resulting in you (and any mass) weighting about 1% less on the equator than at the poles.
How much lighter do you weight on the equator, where you are spinning the fastest, versus on the poles where you are not spinning at all. There are 2 reasons why you weight is different on the poles versus the equator. The first reason is the centrifugal force described above.
This force is given by Newton's second law: $F = ma$ along with $a = \omega^2r$. $\omega$ is the angular velocity of the earth rotation, i.e. $\frac{2\pi}{T}$, where $T$ is about 24 hours = $86400s$. The radius at the equator is about $r$ = 6378137 m. This results in a=0.03373 which is about 0.34% of the gravitational acceleration of $g =9.8 \frac{m}{s^2}$
The second reason is that the earth is not a perfect sphere but is squashed on the poles since the centrifugal force of the spinning earth pulls the matter of the earth from the center of mass and this happens more at the equator than at the poles. Thus you are further away from the center of mass of the Earth on the surface of the equator than on the surface of the pole. This affects the value of $g = \frac{MG}{r^2}$ where $M$ is the mass of the Earth and $G$ is the universal gravitational constant. This adds another 0.67% to the difference resulting in you (and any mass) weighting about 1% less on the equator than at the poles.
Sunday, May 15, 2016
Interesting number: 55
The number 55 = 5 x 11 = (10 x 11)/2 is a semiprime, a Fibonacci number, a triangular number, a square pyramidal number, a squarefree number, a palindrome in base 10, and a Stirling number of the second kind.
Tuesday, May 3, 2016
Ironic song while driving this morning
While driving to work this morning, the sky was gray and overcast and there is a light drizzle. Sometime during the commute, the song "I can see clearly now" by Johnny Nash came on the music streaming service. I got a chuckle out of it as the lyrics are in direct contradiction to what I was seeing around me.
Thursday, April 14, 2016
Interesting number: 348588115
The number 348588115 = 5 × 23 × 3031201 has some interesting properties. It is a sphenic number (i.e. it is the product of 3 distinct prime numbers). Reversing the decimal digits also results in a sphenic number: 511885843 = 7 × 953 × 76733. In addition, the decimal digits also are a concatenation of the decimal digits of 2 other sphenic numbers:
'348588115' = '34858' + '8115' and 34858 = 2 × 29 × 601, 8115 = 3 × 5 × 541.
'348588115' = '34858' + '8115' and 34858 = 2 × 29 × 601, 8115 = 3 × 5 × 541.
Tuesday, March 15, 2016
Grocery shopping and Braess' paradox
Some time ago, our local grocery store introduced self-checkout, where we can scan our grocery items ourselves. My wife and I like to use this option since there are several stations open and not many people are using it, so we can get through the checkout quicker. However, recently we noticed that the lines at the self-checkout are getting longer, while the lines at the checkout clerks are sometimes shorter than the self-checkout lines. I believe this is an example of Braess' paradox. Braess noticed that when a new road is added to a network of existing roads, the congestion can actually increase. His reasoning is that each driver follows a selfish routing algorithm and chooses the shortest route to the destination. If the new road is a shortcut, then everyone who can use this road will choose it, and this can actually increase the congestion through the network. This seems to be happening with the self-checkout lines as well. Everyone assumes it is quicker to use them and this leads to longer lines. One way to achieve optimal throughput in a road network is if there is a centralized control to route each driver, but this would require information about the speed and travel plans of all drivers and it might favor some drivers over others for the overall good. To implement this would require cars to talk to each other using technologies such as connected vehicles, vehicle-to-vehicle communications and dedicated short range communication (DSRC).
Back to our grocery shopping trips. Yesterday the self-checkout lines was quite long so we went to the checkout clerk who is much faster than us in scanning the groceries (plus there was an additional clerk to bag our groceries), and we got done much quicker than if we had used the self-checkout line. Sometimes one or more of the self-checkout stations are out of order which is similar to lane closures on a multi-lane highway. If more people realize that regular checkout is faster, we could have another Braess' paradox in the making and lead to longer lines at the regular checkout lines. In the long run, this can lead to cycles of short and long lines forming alternately at the self-checkout lanes and at the regular checkout stations! Fortunately this is unlikely to happen since the 2 types of checkout lines are in close proximity so the shopper has a good sense of the congestion of the entire system. But imagine a mega-store where for some odd reason the regular checkout lines are far away from the self-checkout lines! The shopper needs to decide which line is more optimal based on incomplete information and what other shoppers would do. On the other hand, the speed of checkout may not be the only objective. Some people prefer self checkout because they feel like they don't make mistakes and make better bagging decisions (like not having eggs at the bottom of the bag) if they do it themselves.
Back to our grocery shopping trips. Yesterday the self-checkout lines was quite long so we went to the checkout clerk who is much faster than us in scanning the groceries (plus there was an additional clerk to bag our groceries), and we got done much quicker than if we had used the self-checkout line. Sometimes one or more of the self-checkout stations are out of order which is similar to lane closures on a multi-lane highway. If more people realize that regular checkout is faster, we could have another Braess' paradox in the making and lead to longer lines at the regular checkout lines. In the long run, this can lead to cycles of short and long lines forming alternately at the self-checkout lanes and at the regular checkout stations! Fortunately this is unlikely to happen since the 2 types of checkout lines are in close proximity so the shopper has a good sense of the congestion of the entire system. But imagine a mega-store where for some odd reason the regular checkout lines are far away from the self-checkout lines! The shopper needs to decide which line is more optimal based on incomplete information and what other shoppers would do. On the other hand, the speed of checkout may not be the only objective. Some people prefer self checkout because they feel like they don't make mistakes and make better bagging decisions (like not having eggs at the bottom of the bag) if they do it themselves.
Monday, March 14, 2016
Happy Pi Day 2016!
Today, March 14, is Pi Day. As I wrote in an earlier post this year's Pi Day is specially nice since 3.14.16 is Pi rounded to 4 places after the decimal point.
Subscribe to:
Comments (Atom)