tag:blogger.com,1999:blog-26379284728594538312021-01-03T23:55:08.081-05:00Accidental Desultory CogitationsRandom thoughts on a variety of topics, but mostly on science and technology.Unknownnoreply@blogger.comBlogger112125tag:blogger.com,1999:blog-2637928472859453831.post-31509463618476948862021-01-03T23:08:00.001-05:002021-01-03T23:55:08.040-05:00Googol, Google and Isaac Asimov<p><span style="font-family: inherit;">I have been a huge fan of Isaac Asimov's fiction since I was a youngster. I have read all his Robot series and Foundation series books and many of his short stories. I was fortunate enough to hear him speak at our university when I was an undergraduate student. In one of his (many) non-fiction books he wrote that </span></p><p><span style="font-family: inherit;">"<span style="background-color: white; color: #181818; font-size: 14px;">For instance, in a book entitled Mathematics and the Imagination (published in 1940) the authors, Edward Kasner and James Newman, introduced a number called the `googol,' which is good and large and which was promptly taken up by writers of books and articles on popular mathematics. </span><span style="background-color: white; color: #181818; font-size: 14px;">Personally, I think it is an awful name, but the young child of one of the authors invented it, and what could a proud father do? Thus, we are afflicted forever with that baby-talk number."</span></span></p><p><span style="background-color: white; color: #181818; font-size: 14px;"><span style="font-family: inherit;">Asimov passed away in 1992, 6 years before Google was founded and before the internet is woven into the fabric of our lives, ranging from communication to entertainment to commerce. As is well known, Google chose the name as a play-on-words of the word googol. I wonder what Asimov would have thought of the fact that a word derived from the "baby-talk" word is the name of one of the largest technology companies on the planet and is also used to denote the act of finding out information via the vast information source that is the World Wide Web, technological developments that I am sure he would have love to see.</span></span></p><p><span style="background-color: white; color: #181818; font-family: Merriweather, Georgia, serif; font-size: 14px;"><br /></span></p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-88010800898384575732020-12-26T17:13:00.004-05:002020-12-27T02:01:28.566-05:00Harmonic mean of integers<p>The <a href="https://en.wikipedia.org/wiki/Harmonic_mean">harmonic mean</a> of a set of $n$ numbers $x_i$ is defined as $\frac{n}{\sum_{i=1}^n x_i^{-1}}$. While investigating the number of subsets of $\{1,...,n\}$ such that the harmonic mean is an integer (OEIS sequence <a href="https://oeis.org/A339453">A339453</a>), I formulated and proved the following result, which states that for $n >1$ positive integers whose maximum is a prime power that is attained by a single element, their harmonic mean is not an integer:</p><p><b>Theorem:</b> Let $x_i$ be a finite set of positive integers such that $x_j = \max_i x_i = p^k$ for some prime $p$ and positive integer $k$ and all other numbers $x_i$ are strictly less than $p^k$, then the harmonic mean of $\{x_i\}$ is not an integer.</p><p><b>Proof:</b> Let $M$ be the least common multiple of $\{x_i\}$. Assume that $x_i$ are sorted in nondecreasing order. Thus $x_n = p^k$ and $x_i < p^k$ for all $i<n$ . Then $M = Wp^k$ where $p$ does not divide $W$. Let $Q_i = M/x_i$ and $Q = \sum_i Q_i$. This implies that $Q_n = W$ and $p$ divides $Q_i$ for $i <n$.</p><p>The harmonic mean $H$ can then be written as $nM/Q$. Since $p$ does not divide $W$, this implies that $p$ does not divide $Q$. Suppose $H$ is an integer. Then this implies that $Q$ divides $nM/p^k = nW$.</p><p>As $x_i < x_n$ for $i < n$, this implies that $Q_i > W$ for $i < n$, i.e. $Q > nW$, and this contradicts the fact that $Q$ divides $nW$ and thus $H$ is not an integer.</p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-52620737571722420992020-12-14T21:24:00.000-05:002020-12-14T21:24:01.733-05:00Visualizing chaotic attractors via 3D-printed models<p> It has been 30 years since I first studied chaotic circuits and dynamical systems. At that time, we visualize the beautiful 3-D (and higher dimensional) chaotic attractors using a Silicon Graphics workstation. I was delighted to read in the December 2020 issue of the Notices of the AMS the article "<a href="https://www.ams.org/journals/notices/202011/rnoti-p1692.pdf">Modeling Dynamical Systems for 3D Printing</a>" by Stephen K. Lucas, Evelyn Sander and Laura Taalman. The ubiquity of inexpensive 3D printers makes it much easier to create 3D models of chaotic attractors. The authors provided excellent Mathematica and Matlab programs that make it easy to create STL files that can be sent to 3D printers to print these models. With python being able to be run on platforms ranging from PC to smartphones to Raspberry Pi's, I thought it would be nice to have a Python version of these programs. I ported the Matlab program to Python and utilized Python's object oriented features to make it easy to use them for other chaotic dynamical systems. </p><p>The Python port is available here: <a href="https://github.com/postvakje/3d-printing-of-chaotic-attractor">https://github.com/postvakje/3d-printing-of-chaotic-attractor</a></p><p>The file <a href="https://github.com/postvakje/3d-printing-of-chaotic-attractor/blob/main/dynamical_systems.py">dynamical_systems.py</a> can be edited to add additional dynamical systems by providing the parameters, initial and ending simulation time, initial conditions and system equations. </p><p>The data files that are output can be used with an script on OpenSCAD to create STL files.</p><div class="separator" style="clear: both; text-align: center;"><a href="https://github.com/postvakje/3d-printing-of-chaotic-attractor/raw/main/nonautonomous_chaotic_attractor.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="528" data-original-width="800" height="264" src="https://github.com/postvakje/3d-printing-of-chaotic-attractor/raw/main/nonautonomous_chaotic_attractor.jpg" width="400" /></a></div><br /><p><br /></p><p><br /></p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-76684369834763349202020-11-24T12:06:00.000-05:002020-11-24T12:06:44.812-05:00The special place of the decimal number system<p>Modern society has been using the decimal number system for a long time, i.e. a number $n$ is expressed in base $10$ as $n = \sum_i b_i10^i$ where $0\leq b_i < 10$ are integers denoting the decimal digits of $n$.</p><p>Although there have been other cultures and civilizations who have used other number systems, most notably the <a href="https://en.wikipedia.org/wiki/Roman_numerals">Roman numerals</a> and the Mayan <a href="https://en.wikipedia.org/wiki/Maya_numerals">base-20</a> number system, it was believed the decimal system was used by many due to us having 10 fingers. From a mathematical point of view, the base of the number system is arbitrary. For digital computers, using base 2 is more appropriate as it is easier to build components representing and processing 2-valued logic, or equivalently the binary digit, or the bit. It is interesting to note that one of the first (I said one of the first as there is a dispute whether the ABC computer is the first digital computer) digital computer, ENIAC, uses a decimal system and requires 10 vacuum tubes to represent a single decimal digit, each tube representing each of the numerals 0, 1, ..., 9.</p><p>Thus it came as a surprise to me that there is something inherently special about the decimal system. In 1964 Gustav Lochs proved the following theorem.</p><p><i><b><a href="https://en.wikipedia.org/wiki/Lochs%27s_theorem">Lochs' theorem (1964)</a>:</b></i> Let $m$ be the number of terms of a continued fraction expansion needed to determine the first $n$ decimal digits of a real number $x$. Then for almost all $x$, $\lim_{n\rightarrow \infty} \frac{m}{n} = \frac{ln(10)ln(64)}{\pi^2} \approx 0.970$.</p><p>What this tells us is that each coefficient of the continued fraction expansion contain slightly more information than each decimal digit. Had we use a base-11 numbering system, it would have been the opposite, each base-11 digit would contain more information than each additional continued fraction coefficient.</p><p><br /></p><p> </p><p><br /></p>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-443847804060482422020-10-19T16:43:00.007-04:002020-10-20T12:59:50.583-04:00A 2D walk generated by primes<p>Consider starting at (0,0) on the plane and as we enumerate the primes p, except for 2 and 5, we take a step in the E, N, W, S direction depending on whether the last decimal digit of p is 1, 3, 7, 9 respectively.</p><p>The resulting 2D walk looks quite interesting. The first 200,000 steps looks like this:</p><p></p><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-ai_-qgCPpGA/X433El_gWwI/AAAAAAAAAsI/eiB6b0kP00gXCaGH4Hq4hkUggAUScowiACLcBGAsYHQ/s2048/prime2dwalk.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1624" data-original-width="2048" height="508" src="https://1.bp.blogspot.com/-ai_-qgCPpGA/X433El_gWwI/AAAAAAAAAsI/eiB6b0kP00gXCaGH4Hq4hkUggAUScowiACLcBGAsYHQ/w640-h508/prime2dwalk.png" width="640" /></a></div><br />The Python code used to generate this plot can be found <a href="https://github.com/postvakje/AccidentalDesultoryCogitations/blob/main/prime_2D_randomwalk.py">here</a>.<div>Using a different correspondence of last digit to directions, we get different, but qualitatively similar plots.</div><div>For instance (1->W, 3->E, 7->S, 9->N) gives us:</div><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-6ytn2Xj0Q6U/X439m-k-UpI/AAAAAAAAAsU/9FEEUknjD8Iwg9e7wAfTk9tOkF6A93TeACLcBGAsYHQ/s2048/prime2dwalk-v2.png" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1793" data-original-width="2048" height="560" src="https://1.bp.blogspot.com/-6ytn2Xj0Q6U/X439m-k-UpI/AAAAAAAAAsU/9FEEUknjD8Iwg9e7wAfTk9tOkF6A93TeACLcBGAsYHQ/w640-h560/prime2dwalk-v2.png" width="640" /></a></div><div>Overall, they seem more clustered and dense that a 2D random walk.</div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-32613257907024985172020-07-22T15:27:00.002-04:002020-07-22T15:27:59.949-04:00Happy casual π day!Today is also known as π approximation day. Today is July 22, which is written as 22/7 in many <a href="https://en.wikipedia.org/wiki/Date_format_by_country">countries</a>.<br /><br />22/7 is a rational number with repeating digits in decimal 3.14285714285714... and is one of the earliest approximation (besides the number 3) to π = 3.141592653589... and has been used since antiquity. 22/7 approximates π to 2 decimal digits. 22/7 is also the second <a href="https://mathworld.wolfram.com/Convergent.html">convergent</a> in the <a href="https://mathworld.wolfram.com/PiContinuedFraction.html">simple continued fraction expansion of π</a>. The convergents in this continued fraction are the best rational approximation of π, in the sense that if n/d with n and d coprime is a convergent, then no other rational number m/c with c ≤ d is closer to π. It is interesting to note some other convergents have also been used as approximation to π. For instance the fourth convergent 355/113 = 3.141592920... matches up with π to 6 decimal places and was discovered by astronomer Zu Chongzhi (祖沖之) in the fifth century A.D.<br /><br />I talked about these 2 approximations in my blog post from <a href="https://accidentaldesultorycogitations.blogspot.com/2017/03/pi-day-2017.html">Pi Day 2017</a>. For countries where the date format is YY/MM, we have to wait 2 years before we have a casual π or π approximation month during July 2022!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-52763894428947105342020-07-20T22:18:00.000-04:002020-07-20T22:18:22.897-04:0080's, 90's and todayI have been listening to a music channel called "80's, 90's and today" and it occurs to me that while there is only 1 decade between 80's and 90's, there are now 3 decades between 90's and today. When I was growing up, music from the 60's are considered oldies, perhaps the oldies today should include 80's and 90's music. Maybe the music channel should change its title, unless the implication is that "today" consists of music of the last 2+ decades (the 00's, the 10's and the start of the 20's) rather than grouped by a single decade, as was done before.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-54369266609612220402019-11-07T13:11:00.000-05:002019-11-07T13:11:20.809-05:00Prepending and appending a repunit with the same numberConsider a repunit R(n) of n digits in decimal, i,e, the number consisting of n 1's which is equal to $(10^n-1)/9$. If we append and prepend R(n) with the same number k, which we will denote as k|R(n)|k with | denoting concatenation of digits, will k|R(n)|k be prime? For instance, for k = 324 and n = 1111, $k|R(n)|k = 3241111324 = 2^2\times 11^2 \times 281\times 23831$. It turns out that if n is a power of 2, then k needs to have at least n digits for k|R(n)|k to be prime. In particular, we have the following result:<br /><br /><b>Theorem:</b> If $2^r$ is the largest power of 2 that divides n and k has at most $2^r-1$ digits, then k|R(n)|k is not prime. This is true even if some of the digits of k are leading zeros.<br /><br /><i>Proof:</i> If k has m digits, then $k|R(n)|k = k(10^{n+m}+1) + R(n)10^m$ which is a multiple of gcd$(R(n),10^{n+m}+1)$.<br /><br />Since $10^{2^r} - 1 = (10^{2^{r-1} -1})\times (10^{2^{r-1} + 1})$ and 9 does not divide $10^n+1$, by induction it is easy to show that $10^{2^w} + 1$ is a divisor of $R(2^r)$ for $1 \leq w < r$. Since $R(2^r)$ is a divisor of $R(2^r s)$, $10^{2^w} + 1$ is also a divisor of $R(2^r s)$.<br /><br />For $1 \leq m < 2^r$, let $t$ be the 2-adic valuation (or 2-adic order) of m, i.e. t is the largest integer such that $2^t$ divides $m$. This means that $0 \leq t < r$.<br /><br />Then $10^{2^r s+m}+1 = 10^{2^t q}+1 = (10^{2^t})^q + 1$ for some odd number $q$.<br /><br />Since the sum of two odd powers $a^q+b^q$ is divisible by $a+b$, this implies that $10^{2^r s+m}+1$ is divisible by $10^{2^t}+1$.<br /><br />This implies that for $n = 2^r s$ and for all $1 \leq m < 2^r$, gcd$(R(n),10^{n+m}+1) \geq 10^{2^t}+1 > 1$, i.e. $k|R(n)|k$ is not prime. QED<br /><br />For example, for n = 32, the smallest $k$ such that $k|R(n)|k$ is prime is k = 10000000000000000000000000000077, a number with 32 digits. The smallest such $k$ for different $n$'s can be found in OEIS sequence <a href="https://oeis.org/A263182">A263182</a> (see also OEIS sequence <a href="https://oeis.org/A329121">A329121</a>).<br /><br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-30177517698969322382019-11-06T20:48:00.000-05:002019-11-06T20:48:11.872-05:00Product of a number and its reversal in decimal<span style="background-color: white; font-size: 13px; text-indent: -16px;"><span style="font-family: inherit;">The number 10119126106147652568 is the smallest number such that it is the product of a number and its reversal in decimal notation in exactly 5 ways. </span></span><br /><span style="background-color: white; font-size: 13px; text-indent: -16px;"><span style="font-family: inherit;"><br /></span></span><span style="font-family: inherit;"><span style="background-color: white; font-size: 13px; text-indent: -16px;">10119126106147652568 </span><span style="background-color: white; font-size: 13px; text-indent: -16px;">= 8848263411 * 1143628488 = 8044687521 * 1257864408 = 4884561702 * 2071654884 = 4440958722 * 2278590444 = 4082378742 * 2478732804.</span></span><br /><span style="font-family: inherit;"><span style="background-color: white; font-size: 13px; text-indent: -16px;"><br /></span></span><span style="font-family: inherit;"><span style="background-color: white; font-size: 13px; text-indent: -16px;">Multiply this number by 10 and it is the smallest number </span></span><span style="background-color: white; font-size: 13px; text-indent: -16px;">such that it is the product of a number and its reversal in decimal notation in exactly 10 ways. </span><br /><span style="background-color: white; font-size: 13px; text-indent: -16px;"><br /></span><span style="background-color: white; font-size: 13px; text-indent: -16px;">101191261061476525680 = 88482634110 * 1143628488 = 80446875210 * 1257864408 = 48845617020 * 2071654884 = 44409587220 * 2278590444 = 40823787420 * 2478732804 = 24787328040 * 4082378742 = 22785904440 * 4440958722 = 20716548840 * 4884561702 = 12578644080 * 8044687521 = 11436284880 * 8848263411.</span>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-22118952490475433182019-01-11T13:04:00.000-05:002019-01-11T13:04:26.418-05:00Numbers whose binary complement is larger than the binary complement of its square.<a href="https://oeis.org/">OEIS</a> sequence <a href="https://oeis.org/A323192">A323192</a> lists numbers whose binary complement is larger than the binary complement of its square. The binary complement is defined as flipping each bit in its binary representation. For instance, 29 is 11101 in binary, so its binary complement is 2 which is 00010 in binary. Note that the binary complement function is not one-to-one, for instance the binary complement of 61 (111101 in binary) is also 2. This function is not exactly the same as <a href="https://en.wikipedia.org/wiki/Ones%27_complement">1's complement</a> in computer arithmetic, since the number of bits flipped is not fixed but is equal to the number of bits in the binary representation of the number.<br /><br />Giovanni Resta noted that the first 13 terms of sequence A323192 are of the form $\lfloor\sqrt{2^k-1}\rfloor$. It turns out this is true in general. In fact we can prove more. In particular, we can show that the terms of this sequence corresponds to numbers of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ which are larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$ with $k > 0$.<br /><br />This result follows from the following theorem:<br /><br /><b>Theorem:</b> if $n$ is a term of OEIS sequence A323192, then $n$ is of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ for some $k > 0$. In addition, $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.<br /><br /><i>Proof:</i> suppose $n$ has $k$ bits in its binary representation, i.e. $2^{k-1} \leq n < 2^k$. Then $n^2$ has either $2k-1$ or $2k$ bits.<br /><br />First we show that if $n$ is a term of the sequence, then $n^2$ has $2k-1$ bits. Suppose $n^2$ has $2k$ bits, i.e. $n^2 \geq 2^{2k-1}$. Then $2^{2k} - 1 - n^2 < 2^k - 1 - n$. This is rearranged as $n^2 - n + 2^k - 2^{2k} > 0$. Solving this quadratic inequality leads to $n > 2^k$ which contradicts the fact that $n$ has $k$ bits.<br /><br />Thus $n^2 < 2^{2k-1}$ and $2^{2k-1} - 1 - n^2 < 2^k - 1 - n$. Solving this inequality and combining it with $n < \sqrt{2^{2k-1}}$ shows that $n$ must satisfy $\sqrt{2^{2k-1}} > n > \frac{1}{2}+ \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.<br /><br />To complete the proof, we need to show that for each $k$, there is at most one integer satisfying this inequality. This is easily verified for $k = 1$. Assume that $k > 1$. Let $a = \sqrt{2^{2k-1}}$ and $b = \frac{1}{2} + \sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}$.<br /><br />Using the identity $\sqrt{x} - \sqrt{y} = (x-y)/(\sqrt{x}+\sqrt{y})$ it follows that $a-b = -\frac{1}{2} + \frac{2^k - \frac{1}{4}}{\sqrt{2^{2k-1}}+\sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}} < -\frac{1}{2} + \frac{2^k}{\sqrt{2^{2k-1}} + \sqrt{2^{2k-1}-2^k}}$.<br /><br />Since $k \geq 2$, $\sqrt{2^{2k-1}-2^k} = \sqrt{2^{2k-1}(1-2^{1-k})} \geq \sqrt{\frac{1}{2}}\ \sqrt{2^{2k-1}}$. This implies that $a-b < -\frac{1}{2} + \frac{2^k}{\frac{\sqrt{2}+1}{\sqrt{2}}\sqrt{2^{2k-1}}} = \frac{2\sqrt{2}}{\sqrt{2}+1} - \frac{1}{2} < 0.672$. Thus it follows that there is at most one integer in the range between $b$ and $a$.<br /><br />The above discussion also completely characterizes the sequence. $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if $\sqrt{2^{2k-1}}-\lfloor\sqrt{2^{2k-1)}}\rfloor < a-b$ where $a-b$ is as defined above.<br /><br />The criterion can be simplified as:<br />$\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$. This concludes the proof.$\blacksquare$<br /><br />Note that $a-b \rightarrow \frac{1}{2}$ as $k \rightarrow \infty$, i.e. for large $k$, the fractional part of $\sqrt{2^{2k-1}}$ should be less than about $\frac{1}{2}$ in order for the integer part to be a term.<br /><br />The numbers $k$ such that $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term of OEIS sequence A323192 are listed in OEIS sequence <a href="https://oeis.org/A323062">A323062</a>.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-65179562887258302052019-01-07T14:25:00.000-05:002019-01-07T14:25:31.998-05:00560106 and 601065There is a remarkable property of the sequence of numbers 560106, 5606106, 56066106, 560666106, etc. Take any number of the sequence, say 56066106, reverse the digits: 60166560, multiply these 2 numbers, multiply the result by 10 and the result is a perfect square. Thus<br />$56066106 \times 60166065 \times 10 = 33732769778928900 = 183664830^2$.<br /><br />To see this, let us denote the decimal digits reversal of a number $n$ as $R(n)$. Let $a = 56\times 10^{4+k}+106 + 6000\times (10^k-1)/9$ for $k\geq 0$. Then $R(a) = 601\times 10^{3+k}+65 + 6000\times (10^k-1)/9$. The number $10\times a\times R(a)$ can be written as $30360100\times (10^{k + 3} - 1)^2/9$ whose square root is $5510\times (10^{k + 3} - 1)/3$.<br /><br />It is clear the the digit reversals of these numbers, i.e. 601065, 6016065, 60166065, 601666065, ..., satisfy the same property.<br /><br />Other numbers with this property can be found in <a href="https://oeis.org/">OEIS</a> sequence <a href="https://oeis.org/A323061">A323061</a>.<br /><br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-42700688712940755412018-12-30T12:49:00.000-05:002018-12-30T12:49:24.733-05:00Christmas lights ring oscillatorWe set up a string of Christmas lights wrapped around a pine tree outside and plug it into an outlet with a dusk to dawn sensor so it will only turn on at dusk. After a windy day, some of the lights fell from the tree so we adjusted it in the evening. After adjustment, my son noticed that the lights turn on and off at a regular interval, which was strange since these lights are not flashing lights, but are supposed to be on all the time. It turns out one of the light bulb is too close to the light sensor on the outlet, thus tricking it to turn off since the outlet assumed it was dawn. Since it is now dark without the lights, the sensor assumes it is dusk and turns the light back on and so on and so on. Since there is a delay in the sensor, this resulted in the lights being turned on and off periodically. In essence, we have constructed a ring oscillator. A <a href="https://en.wikipedia.org/wiki/Ring_oscillator">ring oscillator</a> consists of a loop of an odd number of NOT logic gates. The number of stages and the delay in each stage of the logic gates determine the frequency of the oscillator. In our case, we have a single NOT gate represented by the dawn-to-dusk light sensor/outlet combination.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-84209372924962223022018-05-20T23:36:00.000-04:002018-05-21T00:30:56.322-04:00An equation involving radicalsWhile browsing the internet, the following brainteaser popped up on the screen: find $x$ such that<br /><br />$$\sqrt{x+15} + \sqrt{x} = 15$$<br /><br />A straight forward approach is to square both sides, move the single term with radicals to one side and square again, and reducing terms to obtain a linear equation in $x$ whose solution gives the answer.<br /><br />Here is another (somewhat simpler) way to solve this problem. First note that the left hand side is a increasing function of $x$ and at $x=0$ is equal to $\sqrt{15} < 15$, so there is a single real solution to the equation above.<br />If we set $x = y^2$ and $x+15 = (y+z)^2$, we get $15 = 2yz + z^2 = z(2y+z)$. The left hand side of the original equation then becomes:<br /><br />$y+z +y = 2y+z = 15$. Combine this with the above it follows that $z = 1$ and $y = 7$. Thus the answer is $x = 49$.<br /><br />In general, this method shows that the equation<br /><br /><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">$$\sqrt{x+a} + \sqrt{x} = b$$ where $b \geq 0$ and $b^2 \geq a$ has as the only real solution:</span><br /><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><br /></span><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">$$x = \left(\frac{b^2-a}{2b}\right)^2$$</span><br /><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><br /></span><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">For the case $a = b \geq 0$, this reduces to</span><br /><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><br /></span><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-variant: normal; letter-spacing: normal; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"></span><br /><div style="-webkit-text-stroke-width: 0px; background-color: transparent; color: black; font-family: Times New Roman; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-variant: normal; letter-spacing: normal; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">$$x = \left(\frac{a-1}{2}\right)^2$$</span></span></div><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-variant: normal; letter-spacing: normal; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><div style="-webkit-text-stroke-width: 0px; background-color: transparent; color: black; font-family: Times New Roman; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><br /></span></div><div style="-webkit-text-stroke-width: 0px; background-color: transparent; color: black; font-family: Times New Roman; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">w<span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;">hich is an integer if $a$ is odd.</span></div><div style="-webkit-text-stroke-width: 0px; background-color: transparent; color: black; font-family: Times New Roman; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; orphans: 2; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"><span style="background-color: transparent; color: black; display: inline; float: none; font-family: "times new roman"; font-size: 16px; font-style: normal; font-variant: normal; font-weight: 400; letter-spacing: normal; text-align: left; text-decoration: none; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px;"></span></div><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike></span><b></b><i></i><u></u><sub></sub><sup></sup><strike></strike>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-45716001334724447522018-04-16T17:49:00.001-04:002018-04-16T17:49:45.945-04:00What is a slide rule for?I was listening to Sam Cooke's classic song "Wonderful World" and thought of the line: "Don't know what the slide rule is for". When the song was released in 1960, the line was describing how disinterested the protagonist was about math and algebra, as the slide rule was a common tool for doing calculations. Today, that line would probably describe most young adults or younger, as the slide rule has not been used for calculations for many years with the rise of the calculator. When I was in high school, we used electronic calculators in our tests and exams, but out of curiosity my brother and I bought a slide rule anyway (they were still being sold in bookstores at the time, but disappeared soon after from the shelves). I was fascinated by how you can multiply two numbers merely by aligning the start of one ruler with the first number and reading off the result off the second number. This is due a property of logarithm: log(ab) = log(a) + log(b). Thus multiplication is reduced to addition. By printing the numbers in logarithmic scale and lining up segment end-to-end (corresponding to addition), we achieve the operation of multiplication using a slide rule. Similarly, division can be done with a slide rule as it corresponds to subtraction. And it can do a lot more, such as trigonometry and taking square and cube roots. Accuracy was a problem, and they were soon supplanted by calculators which can compute to many digits of precision. As the song is continuously being covered by many artists, I wonder if the current audience would find the lyrics strange?Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-9873457219646611592018-03-14T13:16:00.001-04:002018-03-14T13:16:55.324-04:00Primes of the form H(n,-k)-1OEIS sequence <a href="https://oeis.org/A299145">A299145</a> lists the primes of the form $Q(n,k) = \sum_{i=2}^n i^k$ for $n \geq 2$ and $k> 0$. It is clear that except for the case $k =1$ and $n=2$ resulting in the prime $2$, we must have $n\geq 3$.<br />The sum $Q(n,k)$ is equal to $H(n,-k) - 1$ where $H(n,m) = \sum_{i=1}^n \frac{1}{i^m}$ is the <a href="https://en.wikipedia.org/wiki/Harmonic_number#Generalized_harmonic_numbers">generalized harmonic number</a> of order $n$ of $m$. It is well known that $H(n,-k)$ is a polynomial of $n$ of degree $k+1$. In particular, <a href="https://en.wikipedia.org/wiki/Faulhaber%27s_formula">Faulhaber's formula</a> shows that<br />$$H(n,-k) = \frac{1}{2} n^k + \frac{1}{k+1}\sum_{j=0}^{\lfloor k/2 \rfloor} \left(\begin{array}{c} k+1\\2j\end{array}\right) B_{2j} n^{k+1-2j}$$<br />where $B_i$ is the $i$-th <a href="https://en.wikipedia.org/wiki/Bernoulli_number">Bernoulli number</a>.<br /><br />$H(n,k)$ and thus $Q(n,k)$ can be written as a degree $k+1$ polynomial of $n$ with rational coefficients. The smallest denominator of this polynomial is found in OEIS <a href="https://oeis.org/A064538">A064538</a>. In 2017, Kellner and Sondow showed that this is equal to $(k+1)\prod_{p\in S}$ where $S$ is the set of primes $p \leq \frac{k+2}{2+(k \mod 2)}$ such that the sum of the base $p$ digits of $k+1$ is $p$ or larger.<br /><br />Since $H(1,-k) = 1$, this implies that $Q(1,k) = 0$ and thus $n-1$ is a factor of $Q(n,k)$. Since $n\geq 3$, if $n-1$ does not get cancelled out by a factor of the denominator, we would have a nontrivial factor of $Q(n,k)$ and thus $Q(n,k)$ is not prime. This implies that $Q(n,k)$ is prime only if $n-1$ is a divisor of a(k) in sequence A064538. Thus for each $k$ there is only a finite number of values of $n$ to check. This provides an efficient algorithm to find terms of this sequence by looking only for primes in the numbers $Q(n,k)$ where $n-1$ is a divisor of A064538(k). There are <a href="https://oeis.org/A299145/b299145.txt">45</a> such numbers with $1000$ or less digits.<br /><br /><b>References</b><br />Bernd C. Kellner, Jonathan Sondow, <a href="https://doi.org/10.4169/amer.math.monthly.124.8.695">Power-Sum Denominators</a>, Amer. Math. Monthly 124 (2017), 695-709.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-78792324651979135892018-02-20T21:51:00.000-05:002018-02-20T21:51:27.026-05:00Chaos in musicIn an earlier <a href="http://accidentaldesultorycogitations.blogspot.com/2014/03/fractals-in-fairy-tale.html">post</a>, I talked about fractals mentioned in the lyrics of a song. Today, I heard the song "Jurassic Park" by Al Yankovic, which mentions <a href="https://en.wikipedia.org/wiki/Chaos_theory">chaos theory</a>, a related branch of mathematics that studies the unpredictable and complex behavior of dynamical systems, often manifested as <a href="https://en.wikipedia.org/wiki/Butterfly_effect">sensitive dependence on initial conditions</a>. On the other hand, musical compositions themselves can exhibit fractal and chaotic behavior [1,2].<br /><br /><b>References:</b><br /><br />[1] K J Hsü and A Hsü, "Self-similarity of the "1/f noise" called music," PNAS, vol. 88, no. 8, pp. 3507-3509, 1991.<br />[2] J. Beran, "Music - Chaos, Fractals, and Information," CHANCE, vol. 17, no. 4, pp. 7-16, 2004.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-4204552633183766862017-12-18T12:48:00.000-05:002017-12-18T12:48:52.416-05:00O, zero and eightWhen my parents bought us our first computer, a <a href="https://en.wikipedia.org/wiki/Commodore_VIC-20">Commodore VIC-20</a>, in my early teens, I learned that to distinguish capital O with the digit zero, a diagonal line is put through the digit zero (also known as a <a href="https://en.wikipedia.org/wiki/Slashed_zero">slashed zero</a>). This is due to the relatively low resolution computer fonts used in those days, where O is easily confused with 0 (but its use actually <a href="https://en.wikipedia.org/wiki/Slashed_zero">predates</a> computers). On the other hand, some Scandinavian languages has something similar to a slashed zero in their alphabet, and the slashed zero can cause more problems than it solves. The use of the slashed zero is also useful when writing computer code using pen and paper, an activity that is becoming rare. Recently, I have not seen the use of slashed zero in word processing since given the number of pixels they have at their disposal, many fonts do not use it to represent the digit 0. In some fonts such as DejaVu Sans Mono and the font used in the Windows command prompt, a dotted zero is used to represent 0. Incidentally, for the Default font used in this blog, zero (0) looks almost identical to the lowercase letter "o".<br /><br />The empty set (the set with zero elements) is denoted as {}, and is sometimes also denoted with a symbol similar to a slashed zero, but with the slash extending beyond the boundary of "0". This notation makes sense since in <a href="https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers">Zermelo-Fraenkel set theory</a> the natural numbers are defined as sets with 0 being the empty set and the number n+1 defined as $n \cup \{n\}$, i.e. n+1 is the set obtained by augmenting the set n with a single element: the set consisting of the set n. In other words, 0 = {}, 1 = {{}}, 2 = {{},{{}}}, etc.<br /><br />The use of a slashed zero is a good idea, but recently I found that it is causing problems for me. There is one place where I consistently see the use of a slashed zero and that is on credit card receipts. With advancing age and the onset of farsightedness, I have a hard time separating the slashed zero from the digit 8. When we go out to eat at a restaurant, the lighting is typically dim which exacerbates the problem and sometimes I have a hard time determining how much tip to leave and add it up correctly on the bill. I wish the receipt printer would not use the slash zero in their font (I don't think the dotted zero is much better either in this case).Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-61948037345600438392017-10-10T13:06:00.000-04:002017-10-10T13:06:11.715-04:00The triangle inequality and its converse<h2>The triangle inequality</h2>The triangle inequality is a workhorse in many branches of mathematics. It expresses the subadditivity of norms and is stated as:<br />$$ \| A+B\| \leq \|A\| + \|B\|.$$<br />The name comes from its interpretation on the plane. If $A$ and $B$ are complex numbers, then we can draw a triangle with vertices at the points $0$, $A$ and $A+B$, with the resulting sides having norms equal to $|A|$, $|B|$ and $|A+B|$. Stated in another way, if $a$, $b$ and $c$ are the lengths of the $3$ sides of a triangle, then $a \leq b+c$. This is illustrated in Fig. 1.<br />A slightly different, but clearly equivalent statement is the following: if $a \geq b \geq c \geq 0$ are the lengths of the $3$ sides of a triangle, then $a \leq b+c$. We will use this alternative formulation as it is easier to state and prove the converse and its generalization.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-UUyo-lQaCmA/Wdwj3tfX7HI/AAAAAAAAAlc/LmIaNDApXIgYwmB5VPHURYf2zGliPTdhQCLcBGAs/s1600/triangle1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="207" data-original-width="500" height="132" src="https://3.bp.blogspot.com/-UUyo-lQaCmA/Wdwj3tfX7HI/AAAAAAAAAlc/LmIaNDApXIgYwmB5VPHURYf2zGliPTdhQCLcBGAs/s320/triangle1.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 1: Illustration of the triangle inequality and its converse.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><h2>Converse of the triangle inequality on the plane</h2>The converse of the triangle inequality is also true: If $a \geq b \geq c \geq 0$ and $a \leq b+c$, then there exists a triangle whose sides have lengths $a$, $b$ and $c$ respectively. Equivalently this can be restated as: If $a \geq b \geq c \geq 0$ and $a \leq b+c$, then there exists complex numbers $A$, $B$ and $C$ with $|A|=a$, $|B| = b$, $|C| = c$ such that $A+B+C = 0$.<br /><br />The following is a simple construction of this triangle.<br />First we show that $d = \frac{b^2+c^2 - a^2}{2bc}$ satisfies $|d| \leq 1$. This follows from the fact that $d = \frac{(b+c)^2 -a^2-2bc}{2bc} = -1 + \frac{(b+c)^2 - a^2}{2bc} \geq -1$<br />and $d= \frac{(b-c)^2 -a^2+2bc}{2bc} = \frac{(b-c)^2 -a^2}{2bc} + 1\leq 1$.<br />Thus we can choose $\phi = \cos^{-1}(d)$ which satisfies $a^2 = b^2+c^2-2bc\cos (\phi)$ and the <a href="http://mathworld.wolfram.com/LawofCosines.html">law of cosines</a> shows that the triangle with sides of length $b$ and $c$ and angle $\phi$ with have the third side of length $a$. (see Fig. 1).<br /><br /><h2>The generalized triangle inequality and its converse</h2>A simple induction argument generalizes the triangle inequality to the summation of more than 2 quantities:<br />$$\left\| \sum_i^n A_i\right\| \leq \sum_i^n \|A_i\|$$<br />The geometrical interpretation is that if $r_i$ are the lengths of edges of a polygon, then $r_i \leq \sum_{j\neq i} r_j$ or equivalently, if $r_i$ are the lengths of edges of a polygon, and $r_1\geq r_i$, then $r_1\leq \sum_{i > 1}r_i$ (Fig. 2).<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Q079PAYpCCc/WdwkcDuh5-I/AAAAAAAAAlg/-sAk_pNRpiAAhEPCZ2XwX1_hfqa1u_kNgCLcBGAs/s1600/polygon1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="345" data-original-width="625" height="176" src="https://1.bp.blogspot.com/-Q079PAYpCCc/WdwkcDuh5-I/AAAAAAAAAlg/-sAk_pNRpiAAhEPCZ2XwX1_hfqa1u_kNgCLcBGAs/s320/polygon1.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 2: Illustration of the generalized triangle inequality and its converse.</div><div style="text-align: left;"><br /></div>The converse of the generalized triangle inequality is true as well. If $r_1\geq r_i \geq 0$ and $r_1\leq \sum_{i = 2}^n r_i$, then there is a $n$-polygon with $r_i$ as the lengths of its sides (Fig. 2). Having one vertex of the polygon at the origin of the complex plane this can be reformulated as:<br /><br /><b>Lemma 1: </b>(Ref. [1])<br />Let $n\geq 2$ and $r_1\geq r_2\geq \cdots r_n \geq 0$ be real sumbers such that $r_1 \leq \sum_{i=2}^n r_i$, then there exists complex numbers $c_i$ such that $|c_i| = r_i$ and $\sum_i c_i = 0$.<br /><br /><b>Proof: </b><br />As stated in [1] this is easily proved by induction. For $n=2$ this implies that $|r_1| = |r_2|$ and thus we can set $c_1 = r_1 = -c_2$. For $n=3$ this is the converse of the triangle inequality described above. Suppose the Lemma is true for $n = k \geq 3$. Let $n = k+1$, and $s_k = r_k+r_{k+1}$. If $s_k \leq r_1$, then applying the Lemma to $r_1,\cdots r_{k-1}, s_k$ and then splitting $c_k$ into $\frac{r_k}{s_k}c_k$ and $\frac{r_{k+1}}{s_k}c_k$ would prove it for $n=k+1$. If $s_k > r_1$, then $s_k \leq r_1 + r_2 \leq \sum_{i=1}^{k-1} r_k$ and again we can apply the Lemma for $n=k$.<br /><br /> <br />The degenerate case occurs when $r_1 = \sum_{i=2}^n r_i$ in which the resulting polygon must have zero area (Fig. 3). The proof of Lemma 1 also shows that the polygon can be arranged to look like a triangle, i.e. there is a partition of $\{r_i\}$ into $3$ sets $R_1$, $R_2$ and $R_3$ such that $\sum_{r_i\in R_1}r_i \geq \sum_{r_j\in R_2}r_j \geq \sum_{r_k\in R_3}r_k $ and $\sum_{r_i\in R_1}r_i \leq \sum_{r_j\in R_2\cup R_3}r_j $. This is illustrated in Fig. 4.<br /> <br /><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-jtRhPydn-L0/WdwxP_MzMqI/AAAAAAAAAl0/UAyZJeBnpYQ4Zg2g15QpRXkkYI0JqXy5QCLcBGAs/s1600/line1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="325" data-original-width="616" height="168" src="https://2.bp.blogspot.com/-jtRhPydn-L0/WdwxP_MzMqI/AAAAAAAAAl0/UAyZJeBnpYQ4Zg2g15QpRXkkYI0JqXy5QCLcBGAs/s320/line1.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 3: The degenerate polygon when $r_1 = \sum_{i=2}^n r_i$.</div><div class="separator" style="clear: both; text-align: center;"><br /></div><div style="text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://3.bp.blogspot.com/-bDq-l2LR8pA/WdwxdlM0B2I/AAAAAAAAAl4/qQqPwETiaYAUuN7Y5NC7fqNEmdLikpvUgCLcBGAs/s1600/triangle2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="293" data-original-width="603" height="155" src="https://3.bp.blogspot.com/-bDq-l2LR8pA/WdwxdlM0B2I/AAAAAAAAAl4/qQqPwETiaYAUuN7Y5NC7fqNEmdLikpvUgCLcBGAs/s320/triangle2.png" width="320" /></a></div><div style="text-align: center;">Fig. 4: The edges of the polygon can be reordered to form a triangle.</div><div style="text-align: center;"><br /></div><h4>overlapping edges</h4>We have implicitly allowed the possibility that the edges of the polygon may overlap, i.e. the angles of the vertices are allowed to be $0$ (see for example the degenerate case in Fig. 3). The next result shows that we can have up to $n-3$ angles to be either $0$ or $\pi$. <br /><br /><br /><b>Lemma 2: </b>(Ref. [2])<br />Let $r_i$ be real numbers such that $r_1\geq r_2 \geq \cdots \geq r_n \geq 0$ and $r_1 \leq \sum_{i=2}^n r_i$, then there exists $c_i$ such that $|c_i| = r_i$ and $\sum_i c_i = 0$ and either all $c_i$'s are real or $n-2$ of the $c_i$'s are real.<br /><br /><b>Proof:</b><br />We follow the proof in [2]. Select $j\geq 3$ to be the smallest number such that $\sum_{i=3}^j r_i \geq r_1-r_2$. Such an $j$ is possible since $\sum_{i=3}^n r_i \geq r_1-r_2$. Since $r_i\leq r_2$ for $i\geq 3$, this implies that $\sum_{i=3}^j r_i < r_1$ as otherwise $\sum_{i=3}^{j-1} r_i \geq r_1-r_2$. For $k = j+1,\dots n$, if $\sum_{i=3}^{k-1} r_i \leq r_1$, then set $c_k = r_k$, otherwise set $c_k = -r_k$. Ths ensures that $r_1-r_2\leq \sum_{i=3}^k c_i \leq r_1+r_2$ for each $k$ and by the converse of the triangular inequality there exists $c_1$ and $c_2$ with $|c_1| = r_1$ and $|c_2| = r_2$ such that $\sum_i c_i = 0$. Note that in the degenerate case both $c_1$ and $c_2$ are real.<br /><br /><br />The geometric interpretation of this result is that the polygon can be folded into a triangle (possibly with some overlapping edges and angles equals to $0$) as illustrated in Fig. 5 with the edges with lengths $a$ and $b$ being the 2 longest edges.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-0DsoNWluXz8/WdwyXLrI4XI/AAAAAAAAAl8/9s5QvgDWX9MCok_9802RRjyoLqkKDyPpQCLcBGAs/s1600/triangle3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="352" data-original-width="1005" height="112" src="https://1.bp.blogspot.com/-0DsoNWluXz8/WdwyXLrI4XI/AAAAAAAAAl8/9s5QvgDWX9MCok_9802RRjyoLqkKDyPpQCLcBGAs/s320/triangle3.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;">Fig. 5: The edges of the polygon can be reordered and folded to form a triangle with the edges with lengths $a$ and $b$ being the longest 2 edges. Some of the edges may be overlapping.</div><div class="separator" style="clear: both; text-align: left;"><br /></div><h2><br />Singularity of matrices</h2>The Levy-Desplanques theorem [3,4] (which is equivalent to Gershgorin's circle criterion [5]) gives a sufficient condition for a complex matrix to be nonsingular:<br /><br /><b>Theorem 1</b><br />The matrix $A = \{a_{ij}\}$ is nonsingular if $|a_{ii}| > \sum_{j\neq i}|a_{ij}|$ for all $i$.<br /><br />This is easily shown by using the generalized triangle inequality. Suppoe $A$ is singular, i.e. $Ax = 0$ for some nonzero vector $x$.<br />Let $i$ be such that $|x_i|\geq |x_j|$ for all $j$. Since $x\neq 0$, this implies that $|x_i| > 0$. Then applying the generalized triangle inequality to $|\sum_{j\neq i}a_{ij}x_j| = |a_{ii}x_i|$ results in:<br />$$ |a_{ii}||x_i| \leq \sum_{j\neq i}|a_{ij}||x_i|$$<br />Dividing both sides by $|x_i|$ shows that it violates the condition that $|a_{ii}| > \sum_{j\neq i}|a_{ij}|$ for all $i$.<br /><br />Similarly, the converse of the triangle inequality can be used to prove the following statement:<br /><br /><b>Theorem 2:</b> (Ref. [1])<br />Let $A$ be a real nonnegative matrix and let $D$ is a nonzero diagonal matrix with nonnegative diagonal elements. If $B=DA$ satisfies $b_{ij}\leq \sum_{k\neq i} b_{kj}$ for all $i$, $j$, there there exists a complex singular matrix $C = \{c_{ij}\}$ with $|c_{ij}| = a_{ij}$.<br /><br />If $d_ia_{ij}\leq \sum_{k\neq i} d_ka_{kj}$ for all $i$, $j$, then Lemma 1 implies that there are $g_{ij}$ with $|g_{ij}| = d_ia_{ij}$ such that $\sum_i{g_{ij}} = 0$.<br />By choosing $c_{ij} = \frac{g_{ij}}{d_i}$ if $d_i \neq 0$ and $c_{ij} = a_{ij}$ if $d_i = 0$, we get a matrix such that $\sum_i d_ic_{ij} = 0$ and $|c_{ij}| = a_{ij}$. Since $D$ is not the zero matrix, this implies that the rows of $\{c_{ij}\}$ are linear dependent, hence $C$ is singular.<br /><br /><br />These results were extended by the Camion-Hoffman theorem [1] which gives necessary and sufficient conditions for a real matrix $A$ such that any complex matrix whose elements have the same norm as the corresponding elements in $A$ is nonsingular. More precisely it is stated as:<br /><br /><b>Theorem 3:</b> (Camion-Hoffman)<br />Let $A = \{a_{ij}\}$ be a real matrix of nonnegative numbers. The following conditions are equivalent:<br /><br /><ol><li>If $C = \{c_{ij}\}$ is a complex matrix with $|c_{ij}| = a_{ij}$ then $C$ is nonsingular.</li><li>If $D$ is a nonzero diagonal matrix with nonnegative diagonal elements, then $B = DA$ contains an entry $b_{ij}$ such that $b_{ij} >\sum_{k\neq i} b_{kj}$.</li><li>There exists a permutation matrix $P$ and a diagonal matrix $D$ with positive diagonal elements such that $B = PAD$ is strictly row sum dominant, i.e. $b_{ii} >\sum_{i\neq j} b_{ij}$.</li></ol><br /><br />If the conditions in Theorem 3 are not satisfied, then there is a candidate matrix $C$ with $|c_{ij}| = a_{ij}$ such that $C$ is singular.<br />Lemma 2 can be used to show that this candidate can be chosen such that each row is real except for possibly two elements.<br /><br /><b>Lemma 3: </b>(Ref. [2])<br />If $B$ is a singular complex matrix, then there exists a singular complex matrix $C$ such that each row has either $0$ or $2$ complex elements and $|b_{ij}| = |c_{ij}|$.<br /><br /><b>Proof:</b><br />Suppose $Bz = 0$. As before, we select $c_{ij} = \frac{b_{ij}z_j}{|z_j|}$ if $z_j\neq 0$ and $c_{ij} = |b_{ij}|$ otherwise, i.e. $\sum_i c_i = 0$. This means that $\sum_i c_{ij}|z_j| = 0$, i.e. $C$ is singular. By Lemma 2, we can replace up to $n-2$ of $c_{ij}$ with real numbers of the same norm. <br /><br />This result is extended in [2] to show that this candidate can be chosen with at most $2$ complex elements:<br /><br /><b>Theorem 4:</b> (Ref. [2])<br />If $B$ is a singular complex matrix, then there exists a singular complex matrix $C$ with either $0$ or $2$ complex elements such that $|b_{ij}| = |c_{ij}|$.<br /><br /><b>References</b><br />[1] P. Camion and A. J. Hoffman, "<a href="https://msp.org/pjm/1966/17-2/pjm-v17-n2-p03-p.pdf">On the nonsingularity of complex matrices</a>," <i>Pacifi c Journal of Mathematics</i>, vol. 17, no. 2, pp. 211-214, 1966.<br />[2] D. Coppersmith and A. J. Hoffman, "<a href="https://doi.org/10.1016/j.laa.2004.03.029">On the singularity of matrices</a>," <i>Linear Algebra and its Applications</i>, vol. 411, pp. 277-280, 2005.<br />[3] L. Lévy, "Sur la possibilité du l'équilibre électrique," <i>C. R. Acad. Sci. Paris</i>, vol. 93, pp. 706-708, 1881.<br />[4] J. Desplanques, "Théorème d'algèbre," <i>J. de Math. Spec.</i>, vol. 9, pp. 12-13, 1887.<br />[5] S. A. Geršgorin, "Über die Abgrenzung der Eigenwerte einer Matrix," <i>Izv. Akad. Nauk SSSR Otd. Fiz.-Mat. Nauk</i>, vol. 7, pp. 749-754, 1931.<br /><br /><br /> <br /><br /> <br /><br /> <br /><br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-8521707709229286372017-09-08T23:28:00.000-04:002017-09-08T23:28:26.740-04:00Numbers such that 7 is the smallest decimal digit of their squares.9949370777987917 is the smallest number whose square has as its smallest decimal digit 7.<br />Note that $9949370777987917^2 = 98989978877879888789778997998889$. What is the next such number?Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-2637928472859453831.post-40611437103828599982017-07-23T23:02:00.001-04:002017-07-23T23:02:38.726-04:00Solar eclipse 2017On August 21, 2017, there will be a <a href="https://www.space.com/33797-total-solar-eclipse-2017-guide.html">solar eclipse</a> occurring coast to coast across the continental United States. The last time this happened was almost a century ago in 1918. This has two effects on states that generate a lot of solar energy: the solar energy generated decreases during an Eclipse and people turn on their lights as the sky darkens. Both of these events stress the utility grid. California's utilities <a href="http://www.sfgate.com/business/article/Eclipse-plea-from-regulators-Stay-in-the-dark-11307981.php">are asking people not to turn on the lights during this event</a>. I am surprised such a short event (and California is not even in the path of totality) can cause concerns for power utilities operators. I wonder if something similar happens when there is no wind in the summer and more people turn on their fans to cool off?Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-83337018620909083602017-07-17T18:41:00.001-04:002017-07-17T19:33:21.742-04:00Happy Yellow Pig Day!Today, July 17 is <a href="http://holidayinsights.com/other/pigday.htm">Yellow Pig Day</a>. This "holiday" was created by Princeton math students Michael Spivak and David C. Kelly when they were analyzing the number 17 and wanted to have a day to celebrate this number. This year (2017) is extra special since the year also ends in the digits 17.<br />Michael Spivak is the author of the wonderful differential geometry texts (published by Publish-or-Perish Press which he founded) which I fondly remember reading in graduate school. He also wrote a popular typesetting book on TeX which I did not read since Leslie Lamport's book on LaTeX makes typesetting papers using LaTeX so easy that I have skipped learning TeX and went straight to using LaTeX (which sits on top of TeX).<br />If I remember correctly, the typesetting software I used prior to LaTeX was ChiWriter, which is quite easy to use as it is WYSIWYG, so moving to a typesetting paradigm where you relinquish control on the formatting, page breaks, etc. to the software is quite unnerving, but I soon learn to appreciate it as I can focus on the content of the document, rather than spend time improving its appearance.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-70563981728433430522017-06-04T11:22:00.002-04:002017-06-04T11:40:59.505-04:00Moon and Jupiter on June 3, 2017The Moon and Jupiter are in close proximity (not physically, but as viewed from Earth) on the night of June 3, 2017.<br /><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-oLd0NjsdKtg/WTQlleG4I_I/AAAAAAAAAkg/nA3yG6rkpEwD-QdFAuEi_Qwk3FphDdvjQCLcB/s1600/Moon%2Band%2BJupiter.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="1600" data-original-width="911" height="640" src="https://1.bp.blogspot.com/-oLd0NjsdKtg/WTQlleG4I_I/AAAAAAAAAkg/nA3yG6rkpEwD-QdFAuEi_Qwk3FphDdvjQCLcB/s640/Moon%2Band%2BJupiter.JPG" width="363" /></a></div><br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-86717597040703302262017-05-21T10:28:00.002-04:002017-05-21T10:28:41.988-04:00The race of Cloud ComputingI wrote <a href="http://accidentaldesultorycogitations.blogspot.com/2016/11/bots-creating-news-digests-about-bots.html">earlier</a> about a news digest app returning supplemental information which is not directly related to the article. Today, I read on the app that the horse "Cloud Computing" has won the Preakness race. And sure enough, there is a box underneath the article with a definition of cloud computing from Wikipedia. What is ironic is that this news summary is probably enabled by leveraging cloud computing. "Cloud Computing" won over "Classic Empire" by coming in from behind and won the race by a head. Perhaps this is an indication how cloud computing will overtake the classical empire of on premise computing😊.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-61084621597873111042017-05-11T12:22:00.001-04:002017-05-11T12:22:22.014-04:00Find interesting properties of your favorite numberI created a simple web application where you can enter a positive integer < 10<sup>12 </sup>, wait a few moments and it will return a list of interesting properties about this number. Please give it a try and let me know what you think!<br /><br />To start, please visit: <a href="http://postvakje.pythonanywhere.com/">http://postvakje.pythonanywhere.com/</a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2637928472859453831.post-65153458445777302502017-05-07T17:05:00.000-04:002017-05-07T17:35:58.236-04:00Spring is here, pt. 2<div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-yuhesL5GL1U/WQ-LJi0T9xI/AAAAAAAAAkA/xuYzTjU7-rEN1IXeKEBlN6Z1ldA-HLI3wCLcB/s1600/housefinch.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="376" src="https://1.bp.blogspot.com/-yuhesL5GL1U/WQ-LJi0T9xI/AAAAAAAAAkA/xuYzTjU7-rEN1IXeKEBlN6Z1ldA-HLI3wCLcB/s400/housefinch.JPG" width="400" /></a></div><div style="text-align: center;"><br /></div><div style="text-align: center;">House Finch</div><div style="text-align: center;"><br /></div><div class="separator" style="clear: both; text-align: center;"><a href="https://2.bp.blogspot.com/-r2WMmYq3XPY/WQ-LhS9OV8I/AAAAAAAAAkE/KupeRX-htRwWnajF6mrs65y5Ik2NQNC3ACLcB/s1600/chippingsparrow.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="376" src="https://2.bp.blogspot.com/-r2WMmYq3XPY/WQ-LhS9OV8I/AAAAAAAAAkE/KupeRX-htRwWnajF6mrs65y5Ik2NQNC3ACLcB/s400/chippingsparrow.JPG" width="400" /></a></div><div style="text-align: center;"><br /></div><div style="text-align: center;">Chipping Sparrow</div><div style="text-align: center;">My wife says it reminds her of Red from Angry Birds</div>Unknownnoreply@blogger.com0