Solution to Saturday’s puzzle:

Define ƒ:

ƒ(n) is the element that has atomic number corresponding to the n-th prime number, expressed in Chinese.

For simplicity of analysis, ƒ can be thought of as a composite function
ƒ(n) = g(h(n))
ƒ(n) = gh(n)

g(n) = the (Chinese) name the element with atomic number n, and
h(n) = the n-th prime number

Example:

Let n = 25,
ƒ(n) = g(h(25))

h(25) = 97 (the 25th prime number is 97)
g(97) = 锫 (Berkelium has atomic number of 97)

ƒ(25) =锫

Estimate the domain of ƒ:

Elements in with atomic numbers greater than 111 have not been named yet, placeholders are used to refer to these elements. It is analogous to calling a carburettor a ‘thingy’ when one does not know the name.

The greatest prime less than or equal to 111 is 109, which is the 29th prime number. As such, the domain of ƒ lies in [1, 29].


To be more rigorous, let’s break ƒ into its constituent functions g and h.
g(n) is the name of the element with atomic number n.
h(n) is the n-th prime number.

g is defined for all values of n between 1 and 111. Since n is a count of protons in an atom, it cannot take negative values. If there is no proton (n = 0), the particle does not qualify as an atom. If the atomic number is 112 or greater, the element is unnamed, and g is not defined.

h is defined for all values of n greater than zero, since there is no such thing as the zero-th prime number. Since the list of prime numbers is sorted by magnitude, h is a monotonously increasing function: h(n+1) > h(n) ∀n ≥ 1.

For g(h(n)) to be defined, h(n) must not be greater than 111.

It is known that h(1) = 2, h(29) = 109 and h(30) = 113. Since h is a monotonously increasing function, it can be deduced that the maximum possible n that will result in ƒ being defined is 29, and all values of n between 1 and 29 will not result in h(n) exceeding 109.

The smallest value of n possible is 1, and the largest is 29. The domain of ƒ is [1, 29].


Further reading:

元素周期表


Mathematics & Applied Sciences

Here’s a little puzzle:

There exists a function ƒ(n) which takes a natural number n as an argument and returns a character.

It can be said with certainty that natural numbers smaller than 20 are in ƒ’s domain.

ƒ(n) for the first 15 values of n is exhibited in the image below, in the following order:

ƒ(1) ƒ(2) ƒ(3) ƒ(4) ƒ(5)
ƒ(6) ƒ(7) ƒ(8) ƒ(9) ƒ(10)
ƒ(11) ƒ(12) ƒ(13) ƒ(14) ƒ(15)



Click here for large size image


Define ƒ.
Estimate the domain of ƒ.



Hint:

Here is a dictionary.


Interesting reads

Mathematics & Applied Sciences

So, what is this Skewe’s number?

Godfrey Harold Hardy (1877-1947) remarked that Skewe’s number is ‘the largest number that has ever served any definite purpose in mathematics’. [1]


The story starts when we consider the prime numbers- numbers that do not divide wholly with any number except for one and itself. The first few prime numbers are

2, 3, 5, 7, 11, 13, 17, 19...

In 300BC, Euclid of Alexandria proved that there are infinitely many prime numbers. [2]

The prime counting function π(N) now comes into play. π(N) simply counts the number of prime numbers equal or less than N.

For N = 11, π(11) = 5. There are 5 prime numbers equal or less than N: 2, 3, 5, 7 & 11.

π(0) = 0
π(1) = 0
π(2) = 1
π(3) = 2
π(4) = 2
π(5) = 3
π(6) = 3

π(100,000,000) = 5761455 [2]

Because the exact distribution of primes is not predictable, number theorists have had to make do with functions that would approximate π(N).

Over the years, various proposals have been made to estimate π(N) at large values of N, each conjecture more accurate than the last.



The twiddle sign (~) indicates that the approximation gets increasingly accurate for larger values of N.

Bernhard Reimann’s landmark 1859 doctorate paper refines the prime counting function’s estimate to a very precise but unproven estimate [2]



Where li(N) is the (natural) log integral from 0 to N.


From here, we will go on to explain how Skewe’s number came about.

Riemann’s log integral was a a good approximation of the prime counting function π(N). However, li(N) seemed to consistently overestimating the actual value of π(N).

For example, at large values of t, 0 can be closely approximated by the following exponential function:



In this particular example, the exponential function is always positive (for positive t), hence consistently overestimating the value of zero. However, the function approaches 0 for increasing t.

The appeared to be the case with Riemann’s log integral- it was consistently larger than π(N), but the error shrinks with larger values of N. For all N within our grasp, li(N) was greater than π(N). In fact, Gauss (1777-1855) was thought to believe that li(N) would always overestimate π(N). [2]

In 1914, John Edensor Littlewood proved that on the contrary, li(N) can overestimate and underestimate π(N), and switches back and forth infinitely many times. This result created quite a sensation, and the next question was obviously, at what value of N is the first ‘Littlewood violation’ (where li(N) turns from overestimation to underestimation)?

In 1933, one of Littlewood’s students Samuel Skewes showed that assuming the truth of the Riemann Hypothesis, the first Littlewood violation would be definitely less than the following number, now known as (the first) Skewe’s number [2] [3]:



GH Hardy calculated that if one were to play chess using every particle in the universe (10^84 particles), where one step is the exchange of two particles, then the number of possible games is roughly equal to Skewe’s number. [1]

In 2000, the upper bound of the first Littlewood violation was estimated to be near the vicinity of 1.39822 x 10^316, a mere 316 digit number. Another paper shows that there is a small possibility of the first violation occurring around 10^176. [2]

However, this is not the end of the story. Samuel Skewes also showed that assuming the Riemann Hypothesis is false (as opposed to the previous true assumption), the first Littlewood violation would occur below another even more monstrous number, known as the second Skewe’s number: [3]




References:
[1] Simon Singh, ‘Fermat’s Last Theorem’, Fourth Estate, London 1997.
[2] John Derbyshire, ‘Prime Obsession – Bernhard Riemann and the greatest unsolved problem in mathematics’, Joseph Henry Press, Washington DC, 2003.
[3] Eric W. Weisstein, ‘Skewes Number’, MathWorld


Mathematics

The JFE 8555 problem revisited- digital roots

Note: Familiarity of the concept of congruence is expected. Failing that, a concise introduction can be found here.

A rethink of the original problem has prompted a much neater (although not necessarily any easier to read) and a more general solution.

We will attempt to add the digits together in any arbitrary manner, repeating till we reach one digit.

35897
-> 3 + 5 + 8 + 9 + 7 = 32
-> 3 + 2 = 5

(35) + (897) = 932
-> 9 + 3 + 2 = 14
-> 1 + 4 = 5

(3+5) + (8 + 9) + 7 = (8) + (17) + 7
-> 8 + (1+7) + 7 = 8 + 8 + 7
-> 8 + 8 + 7 = 23
-> 2 + 3 = 5

3 + 58 + 97 = 158
-> 15 + 8 = 23
-> 2 + 3 = 5

The flabbergasted reader might want to try a few other addition combinations for amazement’s sake, and to show that the result is always 5.

To generalise the situation, the number involved will be written as abcd with each letter representing one digit. This number abcd can be in any base n. For sake of simplicity this number is represented with only 4 digits, but can be extended to as many digits as desired.

Separating the digits of abcd:


Equations (1)

Remember that the notation is generalised for any base-n, hence the powers of n are used instead of thousands, hundreds and tens as used in base-10.


Equations (2)

Equations 2 are valid statements. To illustrate, we will use n=10 with B:


Equations (3)

Now, on to a bit on the properties of congruence:


Equations (4)

Applying these rules to the number abcd:


Equations (5)

Now, suppose we cluster the digits into groups of two and summing the elements in each group. This is illustrated using abcd= 1534, base-10.

5734
5+7; 3+4
12; 7
1+2;7
3;7
3+7
10
1+0
1

The digital root of 5734 is 1.

Returning to the general case,


Equations (6)

The last step taken is exactly the same those presented in equations (5). Continuing on, the sum of the digits in each bracket is only one digit (for all cases of n greater than 2, the trivial case). This is because both digits are smaller than n, and the sum of two digits, both smaller than n, result in number than when its digits are added, result only in one digit.

Illustrating using base-10, the sum of 2 digits: 9 and 9:
9+9 = 18
1 + 8 = 9

At the limit, n (in this case, n=10) digits may be added and the result remains as one digit:
9+9+…+9=90
9+0=9

To continue from equations (6), the sums of the bracketed numbers result only in one digit each:


Equations (7)

In equations 7, the digits are further added and finally reduced to the resultant digital root a''''.


Now, to show that the grouping order of the addition operations do not matter, the grouping of ab and cd will now be reordered to abc and d.


Equations (8)

Which gives the same result as the grouping of ab and cd.


In conclusion, the digital root of a number in base-n is congruent to the number, mod n-1. The digital root is independent on the summation order of digits.



End note: Now, the interesting question is, who would read this? Yuan Harng, most probably. Michelle Chong, maybe. Everyone else just hits the big red x on the top right of the window.

So why did I do this? Because I needed a mental workout.


Mathematics

The convergence and divergence of a series

The family of series in consideration today is of the following form:



For s = 1, the series is the harmonic series, which is a (slowly) divergent series.



For s = 2, it is the Basel Problem, named after the Swiss city where Jakob Bernoulli published the problem. Interestingly enough, the Basel problem was originally raised by Professor Pietro Mengoli at the University of Bologna. Regardless, it is referred to as the Basel Problem and not as the “Bologna Problem”. In particular, the Basel Problem is a convergent series, but to exactly what number it converges to, no one knew. 46 years after it was raised, Leonhard Euler found the closed form to the Basel Problem, as well as an algorithm for the closed form for all even numbers of s. Up to now, there is no known closed form for odd numbers of s.



In his investigations of prime numbers, Bernhard Riemann used the above family of series, and called it the Zeta function in his 1859 paper.



The convergence or divergence of the Zeta function can be easily proven using the power of calculus. In particular, the series for a particular s can be compared to the integral of a suitably chosen function.

Consider the Basel Problem. To show that it is a convergent series, the elements of the series are compared to a continuous function f(x).



The comparison itself will consider the area bounded by the series, and area bounded by the function f. The area of the function f is simply its integral, while the area of the series is the sum of rectangles of width 1, and of the same height as the series elements.

To show that the series in the Basel Problem is convergent, we first show that f(x) is convergent, then fit the series to be always under the function f(x), such that the series is always less than or equal to the function f(x). Thus if f(x) converges, the series converges.

Firstly, show that the integral of f(x) to infinity converges.



Then, fit the series below the function f(x) such that it is always less than or equal to f(x).
Integrate from 1 to ∞, and the integral turns out to be one, a finite number.

Note that the integration was not taken from 0 to ∞ because f(x) is singular at 0, and we already know that the first term of the series is one, a finite value.

The sum of all terms after the first is strictly less than the integral of f(x), since the series is always less than or equal to f(x). The integral to infinity is one, and the first term is one. The series should converge to a number less than 1 + 1 = 2. As Euler discovered, it converges to 1.64493…


click here for larger image

Similarly, to show that the Zeta of s = 0.5 is divergent, all that needs to be done is to compare it to a suitably chosen function g(x), and show that the integral of g(x) to infinity is divergent. Fit the series so that it is always greater than or equal to g(x), so that if the integral of g(x) diverges, the series diverges.




click here for larger image

The problem is of determining the convergence of the series simply becomes an exercise in integration. For what values of s does the series converge?

Define a general function to represent the continuous function:



Integrating the h(x) from a finite value to infinity, at what values of s does the integral diverge?


The inverted A symbol represents "for all"
The rounded E symbol represents "is an element of"
The symbol R represents the field of all real numbers


To determine convergence or divergence, the most important criteria is the power of b (which is the variable that approaches infinity). If b is raised to a positive power, and then inversed, the value approaches zero and all is well. However, if b is raised to a negative power and inversed, the value approaches infinity and the series diverges.

Now we know that the series diverges for all s less than one, and converges for all s greater than one. And for s exactly equal to one, the harmonic series:



The harmonic series (and the natural logarithm) diverges so amazingly slowly that this phenomenon itself deserves an article.




Mathematics

The number of elementary operations to calculate the determinant of a real, k-by-k matrix

The pleasure of (self) discovery is great.

This post is a hedonistic repetition of something I played with on Thursday night. There are no jokes in today’s entry.

Contents:

Introduction- the matrix determinant
Counting the number of elementary operations needed to find the determinant
Expressing the number of elementary operations as a non-recursive function
Proof by induction that the two expressions are equivalent
Cite this article
End note

Introduction- the matrix determinant

The determinant of a matrix A can be expressed as the following:



Where Cij is the cofactor of aij, and Mij is the minor of A formed by removing row i and column j.

The number of elementary operations required to calculate the determinant of a k-by-k matrix will be denoted by f(k).


Counting the number of elementary operations needed to find the determinant
As the definition shows, |A| is a sum of k terms. Each term consists of a multiplication of an element with its cofactor. To count the operations required: summing k terms would require (k-1) addition operations; there are k multiplication steps, and there are k different cofactors to determine. Each cofactor is the determinant of a (k-1) by (k-1) matrix. Note that the step (-1)^(i+j) in the cofactor has been neglected because it is a computationally simple operation of sign flipping.

Thus f(k) = (k-1) + k + k*f(k-1)
f(k) = k[2+f(k-1)] -1.

The trivial case for this recursive equation starts at f(1)=0. Knowing this, all other values of f(k) can be determined by recursion.




Expressing the number of elementary operations as a non-recursive function

Calculating f(k) algebraically for several cases of k, it appears to take the following non-recursive form:



Proof by induction that the two expressions are equivalent

To show that g(k) is an alternative representation of f(k), g(k) = f(k) will be proven by induction. The first case g(1) = f(1) will be proven. Then, assuming that g(k)=f(k) is true, g(k+1) = f(k+1) will be proven. By showing that g(1)=f(1), the second argument can be applied to show that since g(1) = f(1), then g(2) = f(2). Applying the second argument again, it can be shown that since g(2) = f(2), then g(3) = f(3)…

First, show that g(1) = f(1).


*Note that 0! is defined to be 1.

Now prove that if g(k)=f(k), then g(k+1)=f(k+1).



*Pay attention to the factorial signs. They are sometimes not quite visible.


Thus the number of elementary operations required to calculate the determinant of a k-by-k matrix is shown to be



Cite this article

Tan Yee Wei(2005), "The number of elementary operations to calculate the determinant of a real, k-by-k matrix", from "Snippets of This and That"
http://tanyeewei.blogspot.com/2005/10/number-of-elementary-operations-to.html


End note:

A mathematician, a physicist, and an engineer were trying to show that all odd numbers greater than 1 are prime numbers. The mathematician says, “3 is a prime, 5 is a prime, 7 is a prime. By mathematical induction, it follows that all odd numbers greater than 1 are prime.”
The physicist gives his explanation, “3 is a prime, 5 is a prime, 7 is a prime, 9 is an experimental error, 11 is a prime.”
The engineer then says, “3 is a prime, 5 is a prime, 7 is a prime, 9 is a prime, 11 is a prime, 13 is a prime, 15 is a prime.”





Mathematics

The infinite geometric series and inflation

Assumed knowledge: elementary manipulation of equations (lower secondary mathematics)
Difficulty: 3/5
Tedium: 3.5/5
Insight: 3/5


Table of contents:
Amendments
An infinite amount of money
The infinite geometric series
Inflation and the present value of future cash
Connecting the two ideas
Which prize to choose?
Cite this article
Appendix: geometric proof of S(2)=2



Amendments
__earth has pointed out a flaw in my economics:

actually, inflation and present/future value are two different but related idea.

What you've explained is present/future value of money. The rate is not inflation but instead, it's nominal interest rate.

In fact, in economics, when real rate is r and nominal rate's i with inflation's pi, the equation is approximately,

r = i - pi.

But then, you could assume real interest rate is zero and hence nominal insterest rate is equal to inflation.

JFE 8555 has highlighted an assumption that was not declared:

[I'll take] 25 bucks now, coz i may not see tomorrow.

The assumption is that $1 in your great-great-grandchild's wallet has the same value as the present value of that same dollar now, in your hand.



An infinite amount of money
Suppose you have been awarded a prize for being the tidiest person in your school/institute/company. For your prize, you can pick one of the following choices:
$25 now
$1 annually, indefinitely.

By now, alarm bells should be ringing in your head. Infinity?!
We’ll have try to make some sense of this mess.



The infinite geometric series
Consider the following series:



Each subsequent term in S(2) is half of the previous term. We can have S(3), and that would give us a series that has each subsequent term as one third of the previous term.

To calculate S(2), it would entail adding an infinite number of terms, and hope that it does not blow up in our faces. Observe:



I’ve written that S(2) is equal to S(2), which makes perfect sense. Subsequently, I have separated the first term from the others by the use of a bracket.

I then multiplied each term in the bracket by 2, and divided them all by 2. Nothing has changed- its only multiplication by one.

This is the elegant bit: the infinite geometric is now expressed as 1 + half of itself.



Repeating the same exercise for a general S(x):





Inflation and the present value of future cash

In the economy we are currently stuck in, there is a trend of increasing prices. Often, $1 will not buy you the same amount of goods $1 did back in ‘those days’. Suppose we are in a very messed up economy which sees an inflation rate of 100%- every year, prices increase by 100%. A bar of chocolate which costs $10 today will cost $20 next year. In other words, today, $10 will buy one bar of chocolate. Next year, $10 will only buy you half a bar. Another year later, the chocolate price will have doubled yet again to $40 a bar. $10 can only get you a quarter bar.

This brings us to the problem of concept of net present value. Suppose you know that you will obtain $10 in 2 years time. You would be able to buy a quarter bar of a chocolate.

Today, the same quarter bar of chocolate will cost you $2.5. Thus, the value of $10 in 2 years time is $2.5 now, for a case of 100% inflation.

With a more sedentary case of 5% inflation would mean prices go up by 5% per year. What used to cost $10 would cost $10.50 the next year, and $11.025 the subsequent year.

In 2 years time, when the price of a bar of chocolate is $11.025, $10 can only buy you 0.907 of a bar. Currently, 0.907 of a bar would cost 0.907 x $10 = $9.07. Thus, the value of $10 in 2 years time is $9.07 now, for a case of 5% inflation.



Connecting the two ideas

Having seen the infinite geometric series and the present value of future cash, we can connect the ideas to the concept of indefinite payments (as presented as an option in the prize).

Suppose you are in a horrible economy where the inflation rate is 100%. Every year, the price of goods double; every year, the value of money halves.

In other words, $1 next year is can only buy you as much as $0.50 now. $1 two years later is only equivalent to $0.25 now. $1 three years later is only $(1/8) now.

Now, we get paid $1 every year, indefinitely. Taking the net present value, we calculate how much each $1 in the future would be worth now. It turns out to be the infinite geometric series S(2):



Note that because we are having an inflation of 100%, prices double every year. This doubling is reflected in the 2 found in S(2).

In an economy with 5% inflation, every year, prices are 105% that of last year. In this case, the net present value of the indefinite $1 annually is S(1.05).



In general, the net present value of an indefinite annual payment of $1 (starting this year), in an economy with inflation of i, can be expressed as S(1+i).



Which prize to choose?

The choice offered is either $25 now, or $1 annually.

Here, we make a drastic simplification: the economy’s inflation stays constant indefinitely.

At what inflation rate does the choice become irrelavent- the net present value of the payments ($1 annually) equal to the current payment ($25)?



When the inflation rate is at 4.1666%, there is no monetary gain by choosing one over the other. If the inflation is greater than 4.16667%, then it would make sense to choose the $25 now rather than $1 every year. Just to highlight the point, 100% inflation will give a net present value of only $2, definitely less than $25.

If, on the other hand, inflation is less than 4.16667%, it would make sense to choose the annual payments. For example, if there was no inflation, the present value of every $1 in the future stays at $1, and the indefinite sum would explode into an infinite amount of money.

The choice is thus dependent on the constant predicted inflation rate for the economy.



Cite this article

Tan Yee Wei(2005), "The infinite geometric series and inflation", from "Snippets of This and That"
http://tanyeewei.blogspot.com/2005/08/infinite-geometric-series-and.html



Appendix: geometric proof that S(2)=2
Proof given by Lee Yuan Harng

This is a geometric proof of the following:



We first draw a square of size 1, as represented by the red square.
To add 1/2, we add the yellow rectangle, which is actually half a square.
To add 1/4, we add the grey square, which is actually a quarter of the red square, or half of the yellow rectangle.
To add 1/8, we add the green rectangle, which is half of the grey square.



This addition goes on indefinitely, and each subsequent shape is exactly half of the previous shape.

The first few terms in the infinite geometric series S(2) correspond to the red, yellow, grey, green, blue, fuchsia, black, silver elements.

All subsequent terms are small enough to be shoved into the white unfilled area at the top right corner. In earlier additions, each new term only occupied half of the existing unfilled area. When we only had the red square, the right side portion was unfilled. Adding the yellow rectangle only filled that space up by a half. The next addition, the grey square, only filled up the remaining space by a half, and so did the subsequent addition.

From another point of view, the unfilled space decays by a half for every new term added. At the limit, the space decays to an infinitesimal area of about zero. The filled space thus occupies 2 units.







Mathematics

The JFE 8555 problem explained

Continuing from the previous entry:

We will attempt to add the digits together in any arbitrary manner, repeating till we reach one digit.

35897
-> 3 + 5 + 8 + 9 + 7 = 32
-> 3 + 2 = 5

(35) + (897) = 932
-> 9 + 3 + 2 = 14
-> 1 + 4 = 5

(3+5) + (8 + 9) + 7 = (8) + (17) + 7
-> 8 + (1+7) + 7 = 8 + 8 + 7
-> 8 + 8 + 7 = 23
-> 2 + 3 = 5

3 + 58 + 97 = 158
-> 15 + 8 = 23
-> 2 + 3 = 5

The flabbergasted reader might want to try a few other combinations for amazement’s sake, and to show that the result is always 5.

The key to unravelling this problem lies in the number 9. What is so special about this number?

We’ll first consider the numbers 10, 100 and 1000.
10 = 9 +1
100 = 99 + 1
1000 = 999 + 1

Divide the numbers by 9:



The interesting point about this division operation is that there is a remaining fraction 1/9.

The following example (using 35897) should make it obvious that this division by 9 is analogous to digit extraction where we extract digits out of a multi-digit number.



And out of this mess comes 5 as the numerator in the fraction.

So the above case was an illustration of
35897
3 + 5 + 8 + 9 + 7 = 32
-> 3 + 2 = 5


Can we do it for the following?
35897
3 + 58 + 97 = 158
-> 15 + 8 = 23
-> 2 + 3 = 5

This time, the digits have been arbitrarily condensed into groups.



Again, 5 appears at the end of the digit summation operation. 5 always appears, because the digit summation operation is simply showing part of the divide by 9 process. And, 35897 divide by 9 will always give 3988 + 5/9 no matter how you express the individual components.




Mathematics

The JFE 8555 problem

The Sum of Digits:


On the 28th of July, blogger JFE 8555 highlighted an interesting phenomenon to do with the digits of numbers.

See this for the original version by the author himself itself.

Below is an example done using a 5-digit number, 35997.

We will attempt to add the digits together in any arbitrary manner, repeating till we reach one digit.

35897
-> 3 + 5 + 8 + 9 + 7 = 32
-> 3 + 2 = 5

(35) + (897) = 932
-> 9 + 3 + 2 = 14
-> 1 + 4 = 5

(3+5) + (8 + 9) + 7 = (8) + (17) + 7
-> 8 + (1+7) + 7 = 8 + 8 + 7
-> 8 + 8 + 7 = 23
-> 2 + 3 = 5

3 + 58 + 97 = 158
-> 15 + 8 = 23
-> 2 + 3 = 5

The flabbergasted reader might want to try a few other combinations for amazement’s sake.

Tomorrow, the explanation!




Mathematics