Friday, 6 July 2018

Derivation of nth Term of a Lucas Sequence - Fibonacci Numbers and the Golden Ratio

Who am I?  Index of Blogs

I present a full derivation of the general term Gn of a Lucas sequence, and discuss the cases of the Fibonacci and Lucas numbers.  The Golden Ratio Φ (Greek letter Phi) enters in the discussion naturally and is an integral part of the derivation. 

The unique properties of Fibonacci Numbers and the Golden Ratio have captivated scientists, artists, architects and others over many centuries.  They are abundantly found in nature - particularly in the arrangement of petals and branches in plants.  There are many places where their properties are described but it is difficult to find a derivation of the general term without going to mathematical journals where the subject is treated formally and also much background in mathematics is assumed.  
The presentation here is suitable for someone with a knowledge of school level mathematics.      

I define the Lucas sequence as follows:   A Lucas Sequence is a series of numbers where the nth term is formed by adding the two terms immediately preceding it. 
The series starts from n = 0 and is represented by the recurrence relation:

                            Gn+1 = Gn + Gn-1    for n ≥ 1          ...  eq. 1 

The first two terms, G0 and G1, uniquely determine the rest of the elements of the series.  For example, the choice  
G0 = 0 and G1 = 1, gives the Fibonacci numbers 0,1,1,2,3,5,8,13,21, ...    while 
G0 = 2 and G1 = 1, gives the Lucas numbers 2,1,3,4,7,11,18,29, ...
In order to find the nth term, we define a generating function G(x) as a power series in x whose coefficients are the elements of the Lucas sequence.

[Click on a slide to see full page image, press Esc to return to text]

Equation 6 defines the generating function of the Lucas sequence with the first two terms equal to G0 and G1.  
The next step is to expand G(x) in a power series in x.  This is achieved in the following slides:  

Fibonacci and Lucas numbers:  These number series are formed for particular choices of the first two terms 
G0 = 0 and G1 = 1, gives the Fibonacci numbers
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,  ...

G0 = 2 and G1 = 1, gives the Lucas numbers
 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 143, 219, 362,  ...

The full expression for the nth term is given in equation 13 and with the particular choices allows us to write: 
Equations 14 and 15 are expressions for general F and L series while equation 16 gives the approximation for large values of n.
We notice the very close similarity of the Fibonacci and Lucas series and their intimate relationship with the Golden ratio.

Extensions:  The recurrence relation in eq. 1 that we had used is
           Gn+1 = Gn + Gn-1    for n ≥ 1          ...  eq. 1

Many different sequences may be constructed by modifying eq. 1.  A general form might be as follows:

           Gn+1 = P Gn - Q Gn-1    for n ≥ 1          ...  eq. 17 

It is also possible to have a term equal to the sum of, say, preceding three terms (the tribonacci series) etc. 

One of the more intriguing extensions is the Random Fibonacci Sequence where P and Q in eq.17 are allowed to take values of +1 or -1 in a  random fashion with probability 0.5. Divakar Vishwanath found that for large n, the sequence increases as (1.13198824...)n with a probability of 1.- a completely counterintutive result.  The number 1.13198824 has been named as the Vishwanath number.  

Final Word:  In this blog I have set out the background to the development of Fibonacci numbers and establish their close relationship to the golden ratio.  I feel the derivation of the general term has a great heuristic value as the method detailed here for the calculation of the generating function for a given recurrence relation may be applied to other cases as well.  I was guided by the book 'Generatingfunctionology' by Herbert S Wilf.

In my next blog, I wish to explore the wonderful worlds of Fibonacci numbers and the Golden Ratio.  These two characters prop up in completely different situations generating surprise and a delightful feeling.  
Congratulations if you are reading this sentence - well done.

Thursday, 7 June 2018

Enhanced Reactivity of Powders, Number of Surface Atoms; Inter-Atomic and -Molecular Forces.

Who am I? Index of Blogs

 'Materials in powdered form are much more reactive'.
'Inter-atomic forces are attractive and short ranged'      

Powdered materials are highly reactive because more of their atoms lie on the surface making them available to react with the atoms of the medium.  
Put it another way:

1.  The percentage of atoms on the surface increases as the particle size in the powder decreases.  And,

2.  Forces between atoms in the material and in the surrounding medium are effective over such short distances that only the number of surface atoms determine the reactivity of the powdered material.  

I shall examine these statements in detail here.
Catalysts, nano-particles, the digestive system, design of fireworks etc. are some examples that demonstrate how large surface area of small particles plays a crucial role in determining the enhanced reactivity. 

Note:  We talk about atoms of a material for convenience.  Our discussion is equally valid for molecules.

Let us look at the first point: The percentage of atoms on the surface increases as the particle size in the powder decreases.

Consider a cube weighing 1 gram of a material
 of gram atomic weight M grams (1 mole of material)
(We consider a cube as the algebra is easier to follow - the discussion is valid for other shapes too.  Also, effects due to crystal structures etc are ignored in our discussion).

Number of atoms in 1 mole of material is given by Avogadro constant NA  where 
                                     N = 6.023 x  1023                                                                     eq. 1  
Hence, Number of atoms in 1 gram of material     N = NA /M         eq. 2
Since M is a small number (M = 27 for aluminium), number of atoms in a gram of material is very large  -----   2.23 x 1022  for aluminium.
If the density of the material is d g/cm3,  
then the volume of the cube of mass 1 gram is 1/d cm3  

Notice that we can use eq.4 to calculate the average spacing between two atoms in a material.  
For aluminium, M= 27 g and density d = 2.7 g/cm3

Eq. 4 gives, for Al, the inter-atomic spacing = 2.55 x 10-8 cm or 0.255 nm  
              {1 nano-meter = 10-9 meter = 10-7 cm}       

We now use eq. 12 to calculate percentage of surface atoms for a material.  
The left hand figure shows the situation for a 1 gram cube of Al (M = 27 g, d = 2.7 g/cm3) while the right hand figures (in green) show the increase in surface area of a cube of 1 cm side on subdivision.

The straight line log-log graph shows how the percentage of surface atoms increases rapidly with the number of small cubes.  The number of surface atoms for a single cube is only 0.000021% but increase to almost 100% for 1020 cubes when a mono-layer of atoms is formed.

The combined surface area of small cubes may also be calculated from eq.6  and is
               S = 6 s2 P   = 6 (P/d2)1/3                      eq. 13 

For Al, density = 2.7 g/cmand  S = 3.094 P1/3 cm2                      eq. 14

For  P = 1018,     S = 3.094 10cm2   or 309 m2

This means that the 1 gm Al cube has now
a surface area equal to  a 17.6 m x 17.6 m field!

The case of other materials is similar as shown in the following slide:

The important conclusion from this analysis is that materials in finely powdered form have very large surface area and a large fraction of atoms reside on the surface.  These atoms can participate in reactions with atoms of surrounding medium with a corresponding enhanced reactivity.

A second interesting observation is, that atoms are very closely spaced  - approximately 0.25 nm apart.  The last line of the slide also shows that the inter-atomic separation in all materials is very similar - particularly for Al, Ag and Pt even though they have very different atomic masses. This spacing is comparable to the size of atoms and also to the typical distance over which interatomic forces operate.  We shall now look at these observations in more detail.

Force Between Two Atoms:
The force depends on the separation distance between the two atoms.  The discussion is general and the atoms do not have to be of the same type - they may come from different elements. 

An atom of atomic number Z consists of a central nucleus of positive charge equal to Ze, with negatively charged Z electrons, each of charge -e, surrounding the nucleus.  The atom is overall electrically neutral with most of its mass concentrated in the nucleus. The electrons are attracted to the protons inside the nucleus to provide stability.  

It will be useful to have a plot of  sizes of various atoms.  The size of an atom is determined by the extent of its electron cloud and the slide is a plot of atomic radii. 

Forces between atoms are Coulomb forces -- forces between charged particles.  Like charges repel and opposite charges attract each other.  Being overall neutral, at large separation distances, say greater than a few nano-meters (nm), atoms do not interact with each other.

In the following, I shall describe the origin and nature of inter-atomic forces in a simplified fashion.  The scope of this blog does not allow a more in-depth discussion which may be found in 1, 2, 3

As the two atoms get closer, their electron clouds  start to overlap.  Electrons are also in motion and their distribution changes with time.  Electrons feel attractive force due to the positively charge nuclei of the two atoms, and electron density in the overlap space increases.  This results in weak attractive forces (negative potential energy) to come in play at modest separations.  
If the atoms get very close - separation less than 0.2 nm - then the positively charged nuclei are no longer effectively shielded by negative electrons and the nuclei repel each other with sharply rising potential energy V(r). (See slide).  
The minimum of the potential energy is where the two atoms feel no force F(r) and the separation there is the equilibrium separation R. 

We can make an interesting observation from the potential energy curve in the slide above.  As the atoms are not strictly stationary (atoms are not at absolute zero temperature), they are confined at the bottom of the approximately parabolic potential well and execute vibrations with the energy determined by the temperature of the material.  At higher temperatures, the amplitude of vibration is greater and the atoms do come closer to each other with increased probability of a chemical reaction happening.  This situation is explained in the next slide:

Inter-molecular Forces:  In a molecule, two or more atoms are held together by chemical bonds.  These bonds form as a result of the sharing (co-valent or molecular bond) or exchange of electrons among atoms (ionic bond). 
Just like inter-atomic  forces, two molecules also experience attractive and repulsive forces between them. Such inter-molecular forces are much weaker than the forces (bonds) that hold the atoms of a molecule together, but have a profound affect on the way a molecule's chemical and physics properties are determined.  
Density:  Atoms and molecules feel a strong repulsive force if their separation is reduced beyond a certain value. This means that the number of molecules that may be packed in a given volume has an upper limit - saturation density.  This is true for solids and liquids (also for nuclei which experience a short range repulsive force although on a much smaller length scale of femto-meters 
or 10-15m).  For solids, atoms or molecules are fixed in space and may prefer an ordered crystalline structure which may affect their density (liquid water and ice is a case where water is more dense than ice).
In liquids, thermal motion causes molecules to overcome the attractive inter-molecular forces and molecules can wander randomly in the body of the liquid.  The liquid will have higher volume - reduced density - as temperature is increased.

If the temperature is increased more than a certain level (boiling point), then the molecules of the liquid can break completely free of the attractive forces and we have a gaseous state. In gases, the density depends on the temperature and pressure.

Macroscopic Properties of liquids and gases:   Inter-molecular forces manifest themselves as bulk properties of liquids and gases (fluids) in the form of viscosity, surface tension, capillary action etc.  Low-temperature response of gases is greatly affected by the inter-molecular forces.

In this blog, I have discussed two main topics - increase in surface area as the size of a particle is reduced and the role of inter-atomic (and molecular) forces in determining the physical and chemical properties of substances.  
By decreasing the particle size, one is providing a greater number of surface atoms/molecules that are within the range of attractive forces of the molecules of the surrounding medium and available for chemical reactions.  The result in reactivity may be and is indeed exploited in a very large number of situations in nature and design of industrial processes.  I hope to discuss some of the applications in a future publication.

I wish to reemphasize that it is the surface area of powdered materials that is important as a large surface area allows the possibility of surface atoms (or molecules) to react with reactants in the surrounding medium. A good example is of a pile of dried milk powder that will not ignite even if a roaring Bunsen flame is played on it.  However, if the powder is sprinkled onto a flame, a spectacular fireball is produced which demonstrates the increased reaction rate by increasing surface area.
Powdered materials are one way to increase surface area.  In liquids and gases, molecules are free to move about and already available for reaction with other molecules.  Liquids are on average 1000 times more dense than gases with a much larger number density of reactants available.  

Thanks for reading.

Thursday, 31 May 2018

Sum of Powers of Digits in a Number - Iterations lead to a Fixed Point or a Limit Cycle

Who am I?  Index of Blogs 

I recently came across a paper by Paul Yiu entitled 'Iterations of Sum of Powers of Digits'.  I thought that it was a delightful play on numbers and after trying it out on my 13 years old grand-daughter, I decided that everybody can enjoy the quaint results (presented in a formal way in the paper). 
I shall attempt to present the discussion in a more layman friendly jargon - enjoy!
See also the article in Wiki on Happy Numbers

Starter:  We shall try powers of 2 first - the idea is as follows:

Choose a number N,
Sum the square of digits in the number N to obtain S1
Sum the square of digits in S1 to obtain S2
Continue doing this ...
What do you get ?? 

Best to check it out - Let N = 239

Then S1 = 2^2 + 3^2 + 9^2  = 4 + 9 + 81 = 94
        S2 = 9^2 + 4^2 =  81 + 16 = 97
        S3 = 9^2 + 7^2 =  81 + 49 = 130
        S4 = 1^2 + 3^2 + 0^2 = 1 + 9 +0 = 10
        S5 = 1^2 + 0^2 = 1

Any further iterations will leave the sum at 1.
Digit one is a fixed Point.

If we start with any of following numbers, then we shall obtain the fixed point equal to 1. 

17, 10, 131923, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 97, 91, 100

These are also known as Happy Numbers. 
The happiness of a number is unaffected by rearranging the digits, and by inserting or removing any number of zeros in the number.

Numbers in red are prime numbers and are called Happy Primes.

What about the remaining numbers - the so-called sad numbers.  
Nothing better than trying it out.  Let us choose N =  83

Then          S1 = 8^2 + 3^2 = 64 + 9 = 73
                 S2 = 7^2 + 3^2 = 49 + 9 = 58
Likewise...  S3 = 89,  S4 = 145,  S5 = 42, S6 = 20, 
                 S7 = 4, S8 = 16, S9 = 37 and S10 = 58

Notice that S10 = 58 = S2.  
This simply means that further iterations will repeat the sequence from S2 to S10 - indefinitely. Sad numbers are trapped in a cycle - let us call it a limit cycle.

For the sum of squares of the digits in a number, 
the limit cycle is 58, 89, 145, 42, 20, 4, 16, 37, 58.  
Where one enters the limit cycle depends on the starting number

(Click on the slide to view full page image, press Escape to return to text)

The fixed point 1 and the limit cycle are the only final outcomes of iterations of sum of  squares of digits in any number!

Sum of Cubes:   There are five fixed points and four limit cycles in this case.   85.5% end up in fixed points and only 14.5% end in limit cycles.  They are best shown in the following slide:

 An examples:  Let us start with N = 275

Then S1 = 2^3 + 7^3 + 5^3 = 8 + 343 + 125 = 476
        S2 = 64 + 343 + 216 =623
        S3 = 216 + 8 + 27 = 351
        S4 = 27 + 125 + 1 = 153
        S5 = 1 + 125 + 27 = 153    A Fixed Point

See also where a short computer program is also provided to calculate the fixed points and limit cycles.

Sum of Fourth Powers:  There are 4 fixed points and 2 limit cycles in this case.  Vast majority of iterations ( ~ 79%) end up in a limit cycle with 7 nodes (shown in the slide below). 
The fixed point 8208 occurs with overwhelming frequency (> 90%) relative to other fixed points. 

Why do Fixed Points and Limit Cycles Happen?

I now wish to find out why we get fixed points and limit cycles. 

Let us consider the example of a number that is made of 5 digits and consider that we are iterating with sum of each digit raised to the power 3.  

The maximum possible sum of the cubes of digits in a 5 digit number (for N = 99999) is 5 x 9^3 = 3645
The smallest 5 digit number is 10,000 which is larger than 3645. 
An iteration reduces the magnitude of the number. 
This is true for any number that has 5 or more digits.

For a number with 4 digits, 
the maximum possible sum of cube of digits is 4 x 9^3 = 2916.
Some 4-digit number (1,000 to 2915) are indeed less than 2916 and the value of a 4-digit number is not necessarily reduced after an iteration.

Therefore, a sum of cubes iteration on an arbitrarily large number (of 5 or more digits) will always result in a smaller number (the final theoretical maximum value of the sum being 2916) but not for a number with four or fewer digits. 

The sum of cubes is a finite set of numbers, from 1 to 2916, and an iteration will eventually reproduce a value that is already achieved in a previous iteration - a limit cycle is formed.  
Fixed points are special cases of a limit cycle with just one element or node. 

Likewise, for sum of squares, 
the theoretical maximum value of the sum is  3 x 9^2 = 243 

It may be shown that for an n digit number N, if n > k + 1 where k is the power to which each digit is raised, N is always greater than the sum of kth power of digits.  Fixed points and limit cycles will lie in the range from 1 to  (k+1) x 9^k.

Sum of first Powers (Sum of digits)This is a special case and I have left its discussion to this last section.  
Iterations of the sum of the digits in a number result in fixed points from 1 to 9.

Fixed Points: 1, 2, 3, 4, 5, 6, 7, 8 and 9

Let us consider the case of a five digit number N = abcde
This is 

N = 10000 a + 1000 b + 100 c + 10 d + e

Sum of digits S1 is 

S1   = a + b + c + d + e

N - S1 = 9999 a + 999 b + 99 c + 9 d

We notice that N - S1 is completely divisible by 9. 
Essentially, the first iteration on N has reduced its value by an amount that is a multiple of 9.  
Depending on the initial number of digits in N, S1 will have a much smaller number of digits let us say that 

S1 = fgh or S1 = 100 f + 10 g + h

The next iteration will reduce S1 by a multiple of 9 and will, in general, leave a fixed point remainder.

Summing digits may be used to find the remainder (in the range from 1 to 8) when the number is divided by 9. 
A remainder equal to 9 means that the original number is divisible by 9

Example:   Consider a number  N   = 659824753
                  Sum of digits         S1 = 49
                  Next iteration        S2  = 13
                  Next iteration        S3  =  4
If N is divided by 9 then the remainder will be 4

Friday, 25 May 2018

Optimal Car Separation at Traffic Lights - Current Driving Habits Require a Rethink

Who am I? Index of Blogs

In fifty two years of driving, I have had five accidents.  Four of these were somebody running into the back of my car at a traffic light or at a roundabout.  My experience is supported by data that nearly 25% accidents are rear-end collisions and short separation between vehicles is the cause.  

Why do we pack closely at traffic lights? - waiting to accelerate away when the lights turn green?  Everybody does it and it is considered more time-efficient.  But is it so?

A recent study at Virginia Tech. by Ahmadi et al. conclusively shows that short separation distances at traffic lights do not save time and may serve only to increase the number of rear-end collisions.  They find that the separation that cars maintain during free flow - the 2 seconds rule - is a good guide for  separation distances (S meters) at traffic lights.  Separations up to about 8 m do not impact on travel efficiency in a 30 mph zone.  

The experimental study is described in the following three slide:
(Click on the slide to see full page image, press Escape to return to text)

We notice, for smaller separations cars in the queue take longer before start to accelerate - for example, for S = 0.38 m, the fourth car in the queue is not moving even after 6 seconds from when the first car began to accelerate (light going green).  This is because a car would start to move (accelerate) only when the car in front has moved to a safe separation appropriate to a free flow driving (remember the 2-second rule).
In contrast, when S = 7.6 m, even the fifth car is able to move within the initial 6 seconds.

Notice; independent of the bumper-to-bumper distances from 0.38 m to 7.6 m, the time for all the ten cars to cross the intersection was constant to within 1 second at 23 seconds.  Only for S = 15 m, where the separation is comparable to the minimum distance for comfortable driving, the time increased to 27 +- 3 second.  

It would seem that keeping a larger separation in stop-go driving conditions does not impact on travel time and is much safer.  Drivers should be made aware of this observation and encouraged to follow the conclusions.  I might have saved my time spent in pursuing four insurance claims which thankfully settled in my favour.

The study explains these experimental observations using a theoretical model and I encourage you to visit their publication for details.

I wish to thank Professor Jonathan Boreyko (BEAM, Virginia Tech.) for his kind permission to use some of the material from the study.

Post Script:  The 2-second rule gives the following safe spacing for driving at different speeds

70 mph  S = 62 m;  50 mph  S = 44 m;  30 mph  S = 26 m and  20 mph  S = 17 m.

Considering that the reaction time of the driver might be of the order of 1 second (she may be tired too), the 2 seconds rule over-estimates the recommended separations by a factor of may be two for 20 or 30 mph zones.  

Monday, 21 May 2018

Surface to Volume Ratio for a Spheroid, Cylinder, Cone and Rectangular Box - A Quantitative Analysis

Who Am I?  Index of Blogs.

Among all 3-D solids, for a given volume V, a sphere has the smallest surface area S.  

This statement is universally made. But for me, it has been almost impossible to find a proof of this statement. Another question I have often wondered is, how different the ratio S/V is for other 3-D shapes compared to a sphere.  In the following, I provide a full analysis for a cylinder, a cone, a rectangular box and a spheroid (of which the sphere is a special case). Let us first look at the sphere to set the baseline.
(Click on a slide to view its full page image, Press Escape to return to text)

Sphere:  For a sphere, the situation is straightforward.  The volume and the surface area of a sphere are completely determined by its radius R.  This is shown in slide 1.  

Cylinder:   The volume and surface area of a cylinder are expressed as in slide 2.


 Rectangular Box:

In the above discussion, we have obtained general expressions for a cylinder, a cone and a rectangular box.  These are very useful to obtain insight into the situation: for example, we found that minimum surface area of a cylinder happens when its height is twice its radius, or for a cone the condition is that the slant height is three times the radius of the circular base, etc.
We can, of course, use a spreadsheet (I have used EXCEL) to check the general results also and obtain a good understanding how the surface area increases with the parameter of interest.  
This is shown in the next 3 slides for a given volume of 1000 cm^3.

The minimum surface areas are significantly greater than for a sphere of volume 1000 cm^3 which has a surface area of 483.6 cm^2.

Spheroid:  I now return back to the case of a sphere which is a special member of the ellipsoid family.  An ellipsoid is a surface that may be obtained from a sphere by deforming it by means of directional scalings.  The three principal axes of an ellipsoid are of unequal lengths.      
In order to keep the discussion simple, we shall consider a simplified ellipsoid - a spheroid that has two of its axes equal in length. This is shown in the next three slides:

I have shown here that, for the solids considered, a sphere indeed has the smallest surface area for a given volume.  
It might be interesting for you to find examples where this fact is manifested in nature and design.

Final Word:  You might have noticed that for cylinders, cones and boxes, when the length parameter goes to zero or to very large values, the surface area tends to infinity.  This is simply because the 3-D surface tends to approximate a 2-D plane of large dimensions.