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.
Thursday, April 14, 2016
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.
Saturday, February 27, 2016
Van der Pol Oscillator
The original neon-bulb oscillator circuit studied by Van der Pol and Van der Mark in their 1927 paper consists of a neon-bulb connected to a capacitor, resistor, a bias voltage source and a sinuosoidal signal voltage source. The operation of this circuit without the sinusoidal signal can be described as follows: the neon bulb is not conducting and the voltage source charges up the the capacitor until a certain point at which the neon bulb starts conducting (and glowing) and discharges the capacitor until the voltage is low enough to turn off the neon bulb and the cycle starts anew. Looking at the $v$-$i$ characteristic of the neon bulb we see that it is a function with two local extrema just like the cubic polynomial. The role of the bias voltage source is to add power to the system, since the neon bulb by itself does not supply any power. In particular, by looking at the equivalent $v$-$i$ characteristic of the neon bulb in parallel with the bias voltage, it effectively shift the characteristic so it looks more like the cubic and thus can oscillate.
Except for the external driving source, this circuit is similar to the circuits considered in a previous post. To write state equations, we model the neon-bulb as a nonlinear resistor in parallel with an small linear inductor and a small linear capacitor.
When the sinusoidal source is turned off, the oscillator oscillates freely with a frequency $\omega_1$. The addition of the sinusoidal voltage source add another frequency $\omega_2$ to the system. One can think of the Poincaré map (generated by sampling the flow at frequency $\omega_2$) as a map on the circle, the circle being the limit cycle. In fact, for certain parameters, we see behavior similar to those obtained from the circle map.
The complete state equations of the circuit is given by:
\[ \begin{array}{lcl} \frac{dv}{dt} & = &
-\frac{1}{RC}v - \frac{1}{C}i + \frac{E}{RC} \\
\frac{di}{dt} & = & \frac{1}{L}v - \frac{f(i)}{L}
- \frac{E_0 \sin(\omega t)}{L}
\end{array}
\]
By adjusting the capacitor $C$, we change the free running frequency of the oscillator, i.e. changing the ratio between the two frequency. We observe frequency locking where the oscillator oscillates at a submultiple of the driving frequency for a range of capacitor values. If we vary the driving frequency, we observe the Devil's staircase, similar to the one observed in the circle map.
References:
Van der Pol, B. and Van der Mark, J., “Frequency demultiplication”, Nature, 120, 363-364, 1927.
Kennedy, M. P. & Chua, L. O., “Van der Pol and chaos,” IEEE Trans. Circuits Syst. CAS-33, 974–980, 1986.
Kennedy, M. P., Krieg, K. R. & Chua, L. O., “The Devil’s staircase: The electrical engineer’s fractal,” IEEE Trans. Circuits Syst. CAS-36, 1133–1139, 1989.
Except for the external driving source, this circuit is similar to the circuits considered in a previous post. To write state equations, we model the neon-bulb as a nonlinear resistor in parallel with an small linear inductor and a small linear capacitor.
When the sinusoidal source is turned off, the oscillator oscillates freely with a frequency $\omega_1$. The addition of the sinusoidal voltage source add another frequency $\omega_2$ to the system. One can think of the Poincaré map (generated by sampling the flow at frequency $\omega_2$) as a map on the circle, the circle being the limit cycle. In fact, for certain parameters, we see behavior similar to those obtained from the circle map.
The complete state equations of the circuit is given by:
\[ \begin{array}{lcl} \frac{dv}{dt} & = &
-\frac{1}{RC}v - \frac{1}{C}i + \frac{E}{RC} \\
\frac{di}{dt} & = & \frac{1}{L}v - \frac{f(i)}{L}
- \frac{E_0 \sin(\omega t)}{L}
\end{array}
\]
By adjusting the capacitor $C$, we change the free running frequency of the oscillator, i.e. changing the ratio between the two frequency. We observe frequency locking where the oscillator oscillates at a submultiple of the driving frequency for a range of capacitor values. If we vary the driving frequency, we observe the Devil's staircase, similar to the one observed in the circle map.
References:
Van der Pol, B. and Van der Mark, J., “Frequency demultiplication”, Nature, 120, 363-364, 1927.
Kennedy, M. P. & Chua, L. O., “Van der Pol and chaos,” IEEE Trans. Circuits Syst. CAS-33, 974–980, 1986.
Kennedy, M. P., Krieg, K. R. & Chua, L. O., “The Devil’s staircase: The electrical engineer’s fractal,” IEEE Trans. Circuits Syst. CAS-36, 1133–1139, 1989.
Triangular numbers
A triangular number $T(n)$ is defined as $n(n+1)/2$. It is equal to the binomial coefficient $\left(\begin{array}{c}n+1\\2\end{array}\right)$ and is also equal to $0+1+2+\cdots+n$. When is an integer $m\geq 0$ equal to a triangular number $T(n)$ for some integer $n\geq 0$? We have $n(n+1) = 2m$. Using the quadratic formula to solve the quadratic equation $n^2+n-2m = 0$ for $n$, we obtain one solution for $n$:
$$ n = \frac{\sqrt{8m+1}-1}{2} $$
The other solution for $n$ is negative (or complex) so we will not use that.
If $8m+1$ is not the square of an integer, then $n$ is not an integer. If $8m+1$ is the square of an integer, then $8m+1$ is odd and thus $\sqrt{8m+1}$ is odd as well. This means that $n = \frac{\sqrt{8m+1}-1}{2}$ is an integer. Thus $m$ is a triangular number if and only if $8m+1$ is the square of an integer.
$$ n = \frac{\sqrt{8m+1}-1}{2} $$
The other solution for $n$ is negative (or complex) so we will not use that.
If $8m+1$ is not the square of an integer, then $n$ is not an integer. If $8m+1$ is the square of an integer, then $8m+1$ is odd and thus $\sqrt{8m+1}$ is odd as well. This means that $n = \frac{\sqrt{8m+1}-1}{2}$ is an integer. Thus $m$ is a triangular number if and only if $8m+1$ is the square of an integer.
Sunday, February 14, 2016
What not to listen to while driving
We were driving on the road today and listening to "In the shadow of the mountain king" from Peer Gynt by Edvard Grieg when my son remarked: "This is not a good piece of music to listen to when driving, it makes you drive faster and faster." My wife replied: "The same is true for Bolero". I tend to agree. Luckily, my driving is not affected by the tempo of the music and we reached our destination safely.
Friday, February 12, 2016
The curse and blessing of exponential growth
Exponential growth is a common phenomena occurring all around us. Sometimes it is good, other times not. Simply speaking, we talk about exponential growth if some quantity is increasing as an exponential function of another quantity, i.e. y = abx.
The Good:
The Good:
- Typically when you put your money in the bank, your banks pays you interest as a percentage of your money, i.e. if you have \$100 in the bank and the bank pays you 5% interest a year, then you will have 1.05$\times$\$100 = \$105 after one year. Assuming the interest rate is constant, if the next year, the bank only pays you 5% of the original \$100, then your gain will be \$5 year after year, i.e the money in the bank is 100+5n after n years. But because of compound interest, i.e. your interest will also earn interest, you will receive 5% of \$105 = \$5.25 in interest the second year and the money in the bank will be will be \$100*1.05n after n years, i.e. an exponential growth. If you can appreciate how fast exponential growth is, this is the best reason for anyone to save money early.
- In cryptography, making the number of possibilities that an encryption key can take on large is an important idea to make cryptographic techniques secure. This is akin to choosing a long password. The number of combinations grows exponentially with the number of digits. For instance, a n-digit decimal number has $10^n$ possible combinations.
- In the analysis of computer algorithms, many known algorithms for solving hard NP-complete problems (such as 3SAT) have time complexity exponential in the problem size. This means that the size of the problem that can be solved will be limited.
- Many models of growth assumes an exponential growth rate, but this cannot be sustained indefinitely in a finite universe. Some examples are Moore's Law or models of population growth. Models of chaotic systems such as the Lorenz system and Chua's circuit also experience exponential divergence of trajectories on a small scale, but on a larger scale the trajectories remain bounded.
Monday, February 8, 2016
Parity of binomial coefficients
Consider the binomial coefficient C(n,m) = n*(n-1)*...*(n-m+1)/(m*(m-1)*...*2*1). When is this number odd and when is it even? In this post, we use Lucas' theorem to provides a simple characterization of this. Lucas' theorem states that for integers $m$, $n$ and prime $p$, the following relationship holds:
\[ C(n,m) \equiv \prod_{i=0}^{k} C(n_i, m_i) \mod p \]
where $n_i$ and $m_i$ are the digits of $n$ and $m$ in base $p$ respectively, with $n_0$ and $m_0$ being the least significant digits.
When $p=2$, $n_i$ and $m_i$ are the bits in the binary expansion of $n$ and $m$ and $C(n_i, m_i)$ is $0$ if and only if $n_i < m_i$. This implies that $C(n,m) \equiv 0 \mod 2$ if and only if $n_i < m_i$ for some $i$.
The truth table for $n_i < m_i$ is:
\[\begin{array}{ c | c || c }
n_i & m_i & n_i < m_i \\ \hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 1 & 0 \\
\end{array}\]
i.e., it is logically equivalent to $m_i AND ( NOT n_i)$. If we think of $AND$ and $NOT$ as bitwise operations on the binary representation of numbers, then we have shown that:
$C(n,m) \equiv 0 \mod 2$ if and only if $m AND ( NOT n)$ is not zero.
A simple Python function that implements this statement is
def bincoefmod2(n,m):
# computes binomial(n,m) mod 2
return 0 if ~n & m else 1
or equivalently:
def bincoefmod2(n,m):
# computes binomial(n,m) mod 2
return int(not ~n & m)
Incidentally, for bits $n_i$ and $m_i$, $n_i < m_i$ is logically equivalent to $NOT (m_i\Rightarrow n_i)$.
Next we consider C(n,m)C(a,b) mod 2. Clearly this is equivalent (mod 2) to (C(n,m) mod 2)*(C(a,b) mod 2). Thus $C(n,m)C(a,b) \equiv 0 mod 2$ if and only if $m AND ( NOT n)$ is not zero or $b AND ( NOT a)$ is not zero. This in turns implies the following:
\[\begin{array}{l}
C(n,m)C(a,b) \equiv 0 mod 2 \Leftrightarrow \\
(m AND ( NOT n)) OR (b AND ( NOT a)) \ne 0
\end{array}\]
where OR is a bitwise operation. The corresponding Python function is:
def bincoefprodmod2(n,m,a,b):
# computes binomial(n,m)*binomial(a,b) mod 2
return 0 if (~n & m)|(~a & b) else 1
or equivalently:
def bincoefprodmod2(n,m,a,b):
# computes binomial(n,m)*binomial(a,b) mod 2
return int(not (~n & m)|(~a & b))
\[ C(n,m) \equiv \prod_{i=0}^{k} C(n_i, m_i) \mod p \]
where $n_i$ and $m_i$ are the digits of $n$ and $m$ in base $p$ respectively, with $n_0$ and $m_0$ being the least significant digits.
When $p=2$, $n_i$ and $m_i$ are the bits in the binary expansion of $n$ and $m$ and $C(n_i, m_i)$ is $0$ if and only if $n_i < m_i$. This implies that $C(n,m) \equiv 0 \mod 2$ if and only if $n_i < m_i$ for some $i$.
The truth table for $n_i < m_i$ is:
\[\begin{array}{ c | c || c }
n_i & m_i & n_i < m_i \\ \hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \\
1 & 1 & 0 \\
\end{array}\]
i.e., it is logically equivalent to $m_i AND ( NOT n_i)$. If we think of $AND$ and $NOT$ as bitwise operations on the binary representation of numbers, then we have shown that:
$C(n,m) \equiv 0 \mod 2$ if and only if $m AND ( NOT n)$ is not zero.
A simple Python function that implements this statement is
def bincoefmod2(n,m):
# computes binomial(n,m) mod 2
return 0 if ~n & m else 1
or equivalently:
def bincoefmod2(n,m):
# computes binomial(n,m) mod 2
return int(not ~n & m)
Incidentally, for bits $n_i$ and $m_i$, $n_i < m_i$ is logically equivalent to $NOT (m_i\Rightarrow n_i)$.
Next we consider C(n,m)C(a,b) mod 2. Clearly this is equivalent (mod 2) to (C(n,m) mod 2)*(C(a,b) mod 2). Thus $C(n,m)C(a,b) \equiv 0 mod 2$ if and only if $m AND ( NOT n)$ is not zero or $b AND ( NOT a)$ is not zero. This in turns implies the following:
\[\begin{array}{l}
C(n,m)C(a,b) \equiv 0 mod 2 \Leftrightarrow \\
(m AND ( NOT n)) OR (b AND ( NOT a)) \ne 0
\end{array}\]
where OR is a bitwise operation. The corresponding Python function is:
def bincoefprodmod2(n,m,a,b):
# computes binomial(n,m)*binomial(a,b) mod 2
return 0 if (~n & m)|(~a & b) else 1
or equivalently:
def bincoefprodmod2(n,m,a,b):
# computes binomial(n,m)*binomial(a,b) mod 2
return int(not (~n & m)|(~a & b))
Chinese New Year 2016
Today, February 8, 2016, is Chinese New Year. Just for fun, I looked through OEIS to see what interesting facts I can find about the leap year 2016. Here are some facts about the number 2016:
- 2016 is the sum of the divisors of both the 42th and the 47th generalized pentagonal number.
- 2016 = 3^3+...+9^3 is the sum of 7 positive cubes.
- The sum of divisors of 2016 squared is a multiple of 2016.
- The 2016th Fibonacci number is a multiple of the sum of divisors of 2016 (= 6552)
- Both 2016 and 2016^2 has 0 as smallest digit and 6 as largest digit.
- The product of the proper divisors of 2016 is a multiple of the sum of the proper divisors of 2016.
- Both the number of divisors of 2016 and the number of positive integers relatively prime to 2016 that are less than or equal to 2016 are perfect squares.
- 2016 = 63*64/2 is a triangular number, i.e, it is the sum 1+2+...+63.
- 2016 = 6!+36^2.
- 2016 (in base 10) is divisible by the sum of their digits in every base from 2 through to 16.
Monday, December 21, 2015
Another fan awakens
While rewatching Star Wars episodes 1-6, my wife remarked that Han Solo can be roughly translated into Chinese as 單身漢 (Han sounds like 漢 and solo means single which is 單身) which has the meaning of a bachelor, a suitable way to describe his character.
She also wished that she has the Jedi's mind control powers. I told her that she already has that power. For instance, when she says "You will take out the trash" and waves her hand, I take the trash outside to the garbage bin.
She also wished that she has the Jedi's mind control powers. I told her that she already has that power. For instance, when she says "You will take out the trash" and waves her hand, I take the trash outside to the garbage bin.
Subscribe to:
Posts (Atom)