# Abbreviating Huge and Minuscule Numbers with Math and JavaScript

## The Problem

Let’s say we want to write an algorithm for formatting very large and very small numbers using the standard SI decimal prefixes (because we really, really do!). We want something that will take numbers and create the abbreviated output, as below:

1. 123784692876928714 → ‘123.78P’
2. 1237846924 → ‘1.24G’
3. 0.0000000000000002342 → ‘23.42f’
4. 0.0000000002342 → ‘23.42n’
5. 0.00000002342 → ‘234.22µ’
6. 0.000012345 → ‘123.45m’
7. 1234 → ‘1.23k’

I’m sure there are quite a few ways to do this. What if we could write something with only two non-repeated conditionals using a few math concepts in eight lines of code? Would you be more interested in learning about the math behind it? Let get started. First, let take a look at this algorithm and the lookup table it uses:

##### The Proposed Solution

// This is the list of standard SI unit prefixes
var symbols =  {
'-8': 'y',
'-7': 'z',
'-6': 'a',
'-5': 'f',
'-4': 'p',
'-3': 'n',
'-2': 'µ',
'-1': 'm',
'0':  '',
'1': 'k',
'2': 'M',
'3': 'G',
'4': 'T',
'5': 'P',
'6': 'E',
'7': 'Z',
'8': 'Y',
'9': 'H'  // Though not official, 'hella' is hella big → 10^(9*3) or 10^27
};

function formatNumber(val, decimalPlaces) {
var exponent = Math.log(val) / Math.log(10);
var magnitudeExp = Math.floor(exponent);
var hasIntegerComponent = magnitudeExp >= 0;
var sign = (hasIntegerComponent) ? -1 : 1;
var adjustment = sign * (magnitudeExp % 3);
var significand = val / Math.pow(10, magnitudeExp + adjustment);
var index = (hasIntegerComponent) ? Math.floor(magnitudeExp / 3) : Math.ceil(magnitudeExp / 3);
return significand.toFixed(decimalPlaces) + symbols[''+index];
}


That’s it! That’s all there is to the algorithm! It will handle numbers having up to 29 digits and small numbers having a significant decimal place with 24 zeros in front of it. If that’s not good enough, an index and symbol for it should be added in the lookup table.

If math like this is foreign, a little head scratching might be in order. The math is actually pretty simple. There’s some interesting things about number bases and logarithms here.

## Number Bases

Number bases? As a programmer, one might be familiar with a few number bases — like decimal, hexadecimal, binary, and, perhaps, octal. A number base signifies how many symbols can be used to represent one digit. For instance, in decimal — or base 10 — there are 10 symbols that can represent a digit. These digits are 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. In binary, two symbols are used — 0 and 1. In Hexadecimal, 16 symbols are used — 0-9 and A-F. In octal, the digits 0-7 are used — though, octal is rare these days.

Each digit in a number in a certain base has a certain value, which is related to the number base. Each number position, starting with the ones place in the 0th position (the rightmost side) and continuing to the last or nth position, has a value which is a multiple of the base. Here are examples in a few number bases.

##### Decimal

1,234,567

 Position: $6$ $5$ $4$ $3$ $2$ $1$ $0$ Digit value: $1$ $2$ $3$ $4$ $5$ $6$ $7$ Place value: $10^6$ $10^5$ $10^4$ $10^3$ $10^2$ $10^1$ $10^0$ Position value: $1,000,000$ $200,000$ $30,000$ $4,000$ $500$ $60$ $7$

To get the value of the number in decimal, simply add the values up:

$\displaystyle 1,000,000 + 200,000 + 30,000 + 4,000 + 500 + 60 + 7 = 1,234,567$

So each position has a value of the place times the value of the digit. In decimal, there is the ones place, the tens place, the hundreds place, the thousands place, the ten thousands place, and so on. Each digit happens to have the value that we normally give it, because the this is what we normally use and are used to.

What about other systems? Let us take a look.

##### 10101010
 Position: $7$ $6$ $5$ $4$ $3$ $2$ $1$ $0$ Digit value: $1$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ Place value: $2^7$ $2^6$ $2^5$ $2^4$ $2^3$ $2^2$ $2^1$ $2^0$ Position value: $128$ $0$ $32$ $0$ $8$ $0$ $2$ $0$

To get the value of 10101010 in decimal, simply add the values up:

$\displaystyle 128 + 0 + 32 + 0 + 8 + 0 + 2 + 0 = 170$

Again, the value of the position if the value of the digit times the place value. It only has two digits and they still have the same values as the decimal versions of those digits. What about a system with more symbols than ours?

“Wait, what!? That doesn’t even look like a number!”

In hexadecimal, it’s a perfectly valid number. The digits A-F are used in addition to digits 0-9. In fact, the digit A comes right after 9 and it has a value of 10. The digits B-F have the values 11-15, respectively.

 Position: $3$ $2$ $1$ $0$ Digit value: $D = 13$ $E = 14$ $A = 10$ $D = 13$ Place value: $16^3$ $16^2$ $16^1$ $16^0$ Position value: $13 \times 4,096$ $14 \times 256$ $10 \times 16$ $13 \times 1$

To get the value of the number in decimal, simply add the values up:

$\displaystyle 53,248 + 3,584 + 160 + 13 = 57,005$

##### Summary

Whew! What a whirlwind tour of number systems! This is all of the basic knowledge needed to understand what comes next. This covered the basics of number systems:

• Each number system in base $b$ uses $b$ digits.
• Each digit is in a position. Starting from the rightmost digit at $0$ and increasing with each digit moving leftward.
• Each digit in a number system has a value from $0$ to $b - 1$.
• Each position, $p$, has a place value, or weight, which is $b^{p}$.
• A digit with value, $v$, in a position, $p$, has a position value of $v \times b^{p}$
• Number has a value of the sum of the digit values times their weights.

This also means that every number is actually a polynomial in disguise:

$\displaystyle number = \sum^{places}_{i=0}{digit_{i} \times b^{i}}$

The number of digits or places in a number indicates the order of the polynomial.

## Logarithms

What is a logarithm? A logarithm is a special mathematical function that gives us a special number. Normally, it is written $\log$ or $\ln$ — the second means the base is $\mathrm{e}$ (Euler’s constant). It is a special function that looks like this when graphed:

This graph conveys a few useful facts about the logarithm: The logarithm of a value is always less than the value. If an identity line of $y = x$ was drawn on the above graph of $y = \ln x$, the two graphs would actually never intersect. $\ln x$ is only zero at $x = 1$. It could also be argued that $\ln x$ doesn’t have a value at $x = 0$. The heart of a logarithm lies in the mathematics defining it.

The base $b$ logarithm gives the value of $x$ in the equation:

$\displaystyle b^x = n$

The logarithm in base $b$ of a number $n$ is written:

$\displaystyle x = \log_{b} n$

In the case of JavaScript’s Math.log(), it is a natural logarithm. It will solve for $x$ in this equation:

$\displaystyle \mathrm{e}^x = n$

The base 10 logarithm, $\log_{10}$, can be found by taking $\ln n / \ln 10$. Generally, the base $b$ logarithm can be found by $\log_{b} n = \frac{\log n}{\log b}$, where $\log$ is a logarithm in any base available for you to use. Most likely it will be $\ln$, since it is so useful in math.

Now why is a logarithm useful?

Logarithms are useful for numerous reasons:

• They can turn multiplication into addition. For instance, $a^{x} \times a^{y} = a^{x+y}$. Anyone can take the shortcut and mentally add up the numbers, but a computer can’t. However it can be programmed to use the properties a logarithms to change simplify parts of calculations without having to compute full values of repeated exponentiation until the final step. This also makes sure the numbers are smaller until the last step.
• If one wants to encode a certain number of states as digits in a system, one would like to know how many digits that many states would take up:
• In base 2, $\log_{2} 2 = 1$. We can use 1 bit to represent two states. We can use 3 bits to represent 8 states (000, 001, 010, 011, 100, 101, 110, 111), $\log_{2} 8 = 3$.
• In base 10, $\log_{10} 10 = 1$. This means we can use one decimal digit to represent 10 states — the range 0-9 encompasses ten digits. We can represent 1000 states with 3 digits (0-999), $log_{10} 1000 = 3$.
• Generally, $digitsForNStates_{b} = \log_{b} N$ where $N$ is the number of states to represent in base $b$.
• In general, $1 + \log_{b} n$ gives us the length of digits used to represent a number $n$ in the base $b$ number system. For example $1 + \log_{2} 256 = 9$, which makes sense since we can represent 256 values from 0 through 255 with 8 bits. We cannot represent 256 with 8 bits, but we can with 9.
• In physics and information theory, a logarithm is related to a value called the entropy of the system.

The primary reason why a logarithm is useful in this case is because it yields an exponent that encodes a lot about a number. Here’s a an example with a number in decimal:

$\displaystyle 1,234 = 1 \times 10^{3} + 2 \times 10^{2} + 3 \times 10^{1} + 4 \times 10^{0}$

This could also be written as:

$\displaystyle 1.234 \times 10^{3}$

In this case, $1.234$ is the significand and $10^{3}$ is the magnitude.

Taking the base 10 log of 1,234 yields an interesting number. This number will be between 3 and 4. Why is it between 3 and 4? Well, $\log_{10} 1,000 = 3$ and $\log_{10} 10,000 = 4$ and this is somewhere between those two numbers. For instance, $\log_{10} 1,000,000,000 = 9$ for any number n between 1,000,000,000 and 10,000,000,000 (not including 10,000,000,000), the $log_{10} n$ will be between 9 and 10 (not including 10).

This is also a valid relationship:

$\displaystyle 1,234 = 10^{(3 + fraction)}$

Now why is it 3 and a fraction? Taking the integer part of $\log_{10}1,234$ gives three. Taking $10^{fraction}$ gives 1.234. This means $10^{3} \times 10^{fraction} = 1,234$. So taking this and turning it into a bunch of math gives us everything anyone would ever want to know about the number and the different logarithms. It also means this information can be used to derive the magnitude of the number and get it’s most significant digits for any number.

Here is every identity and step used to formally derive these quantities:

1. $value = significand \times magnitude$
2. $significand = 10^{significandExp}$
3. $magnitude = 10^{magnitudeExp}$
4. $value = 10^{significandExp} \times 10^{magnitudeExp}$
5. $\log_{10} value = \log_{10} 10^{magnitudeExp} \times \log_{10} 10^{significandExp}$
6. $\begin{array}[b]{l} \log_{10} 10^{magnitudeExp} \times \log_{10} 10^{significandExp}\\ =\log_{10} 10^{(magnitudeExp + significandExp)} \end{array}$
7. $\log_{10} value = \log_{10} 10^{(magnitudeExp + significandExp)}$
8. $exponent = \log_{10} value$
9. $exponent = \log_{10} 10^{(magnitudeExp + significandExp)}$
10. $exponent = magnitudeExp + significandExp$
11. $value = 10^{exponent}$
12. $value = 10^{magnitudeExp + significandExp}$

By definition, $magnitudeExp$ is an integer. The floor operation on the $\log_{10}$ yields $magnitudeExp$. Also by definition, $significandExp$ must be less than one or greater or equal to zero. But why must it be greater than or equal to zero and less than one? A decimal significand is going to be between 1 and 9. If the significand was zero, the whole number would be zero. If the significand was less than 1, then the magnitude was wrong. If the significand is greater than 9, the magnitude was wrong. These numbers map to values of $10^{x}$, where $0 \leq x < 1$.

And of course, there’s the most straight forward way to get the significand:

1. $value = significand \times magnitude$
2. $magnitude = 10^{magnitudeExp}$
3. $value = significand \times 10^{magnitudeExp}$
4. $significand = \frac{value}{10^{magnitudeExp}}$

This method, just using exponentiation and division, is probably more accurate than using the $significandExp$ in most cases, since finding the exponent using the Math.log function is just an approximation. Using it to extrapolate the significant digits can lead to errors, especially with very large or small numbers.

## Back to the algorithm

The first few lines should be pretty obvious, given the explanation above:


var exponent = Math.log(val) / Math.log(10);
var magnitudeExp = Math.floor(exponent);


This figures out a few things:


var hasIntegerComponent = magnitudeExp >= 0;
var sign = (hasIntegerComponent) ? -1 : 1;
var adjustment = sign * (magnitudeExp % 3);

• If the number has just a fractional component (magnitudeExp is less than zero) or if it has a whole number part, too (magnitudeExp is greater than zero).
• The sign of the adjustment. If the number has a whole number part, the sign is negative and the adjustment is subtracted. If the the number is a fraction, the sign is positive and the adjustment is added.
• The adjustment itself. This is how many digits away from a grouping of 3 digits the number would be given the magnitudeExp.

If scientific notation was all that was required, the $significand$ and $magnitudeExp$ would satisfy the problem. This algorithm is not actually converting to scientific notation. The algorithm should not show only one leading digit and a few decimal places. It should group digits into a maximum of three leading digits. Numbers between 000 – 999 will always be displayed before the suffix. It should be the equivalent of dividing the number by 1000, 1000000 and so forth (these numbers have counts of zeros which are multiples of three). This will group numbers into groups of 3 digits at most before the decimal place — this is where subtracting magnitudeExp % 3, (“magnitudeExp modulo 3”, the remainder of dividing by 3) comes from. That makes sure the abbreviations are only for place holders for the thousands, millions, billions, and so forth and never a placeholder for, say, ten thousand or a hundred million.

This code takes the adjustment into account when figuring out the significand to make sure that there is a group of at most 3 digits in the significand:


var significand = val / Math.pow(10, magnitudeExp + adjustment);


This code makes sure the suffix appended to the number matches up with the grouping of three most significant digits:


var index = (hasIntegerComponent) ? Math.floor(magnitudeExp / 3) : Math.ceil(magnitudeExp / 3);
return significand.toFixed(decimalPlaces) + symbols[''+index];


Depending on the logarithm of the number being positive or negative, we either take the floor or ceiling of magnitudeExp / 3, respectively. This makes sure we get the right integer for the index in the suffix lookup table.

That integer part of $\frac{magnitude}{3}$ is actually the 1000, 1000000, 1000000000, and so forth in disguise. In fact Math.pow(10, Math.floor(magnitude / 3)) gives those values. This compresses the table of symbols so we don’t have something like the following, but rather the look-up table in the topmost code listing:


{
...
-1: 'm', -2: 'm', -3: 'm',
0:  '',  1:  '',  2:  '',
3: 'k',  4: 'k',  5: 'k',
...
}


I suppose that the algorithm embodies a lot of knowledge about number systems, bases, and logarithms; but it’s very elegant. 😀 I haven’t tested how efficient it is compared to other methods, but, given the flexibility it has from the way it’s derived, it’s probably a decent trade-off.

# Interesting Fibonacci Goodness

Last year I was working on deriving a matrix based method for translating and rotating various polygons around pentagons. In the process of this I got sidetracked and started to look into the golden mean. People swoon over how it defines the most beautiful rectangles! It crops up inside pentagons and various 3-D polyhedra. It’s glorious. It’s just like how a circle has the ratio pi, and it has a name too: phi. I’ll be writing it down in Greek from here on out (it’s originally from there anyway). So learn this shape: $\varphi$ Sometimes people write it out like this: $\phi$ Either way it’s just a variable name. Sometimes it refers to something other than the golden mean, but here it’s the golden mean. As I found powers of $\varphi$, I kept noticing certain values popping up in sequence. It turns out that one can find powers of $\varphi$ through the following formula:

$\displaystyle\frac{\sqrt{5}F_n + L_n}{2} = \varphi^n$

Where $F_n$ and $L_n$ are the nth Fibonacci and Lucas numbers, respsectively.

What are these numbers? Well, you probably know about the Fibonacci numbers, but I’ll go over them here. They follow a certain sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144… and so on. Typically, one starts counting with one, but they really start with zero. Start with a zero and a one. The next number is 0 + 1 = 1. The next number is 1 + 1 = 2. After that, 1 + 2 = 3. One keeps adding the current number to the previous number to get the next number. These numbers crop up in pine cones, sunflowers, and a myriad of other places.

The other not so well known sequence, the Lucas numbers, are defined the same exact way, but with different starting numbers: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521… forever and ever, amen. Start with 2 and 1. 2 + 1 = 3. 1 + 3 = 4. 3 + 4 = 7. If you’ve read Godel, Escher, Bach: An Eternal Golden Braid you may have run across this sequence. They grow the same way the Fibonacci numbers do. If one takes the ratio of the Lucas numbers to the Fibonacci numbers as they grow, one will find it approximates the square root of five.

I wasn’t certain that I was writing things out properly, so I started writing out everything again. Then, I decided to take my knowledge of the binomial theorem and apply it to this question. The binomial theorem is really awesome. It’s related to Pascal’s triangle. If you think that’s cool you’re in luck. If you haven’t hadn’t heard of it yet. Fearest not, I shall walk thee through it. Pascal’s triangle looks like this:

$\displaystyle 1$

$\displaystyle 1 \qquad 1$

$\displaystyle 1 \qquad 2 \qquad 1$

$\displaystyle 1 \qquad 3 \qquad 3 \qquad 1$

$\displaystyle 1 \qquad 4 \qquad 6 \qquad 4 \qquad 1$

If you add two adjacent numbers in a row together you get the number that goes in between the two numbers on the next row down. It can be expressed in terms of a nifty little operation known as the factorial. The factorial takes a number and multiplies that number by every counting number less than it. So, if I take the factorial of 3, written 3!, I get 1 x 1 x 2 x 3 = 6. If I want to find the kth number of the nth row, of Pascal’s triangle I use the choose function. It is written out like this:

$\displaystyle{n \choose k} = \frac{n!}{k!(n-k)!}$

This tells me how many ways I can choose k items out of n total items. It also tells me what the kth coefficient is for a binomial raised to the nth power. If I have the binomial $x + y$ and I square it, I end up with $x^2 + 2xy + y^2$. Let me make something more obvious, $(1)x^2 + (2)xy + (1)y^2$. Notice a pattern yet? Try this one, $(1)x^3 + (3)x^2y + (3)xy^2 + (1)y^3$. See the rows in the triangle appearing? Let me arrange those starting with raising the binomial the the power of 0:

$\displaystyle (1)$

$\displaystyle (1)x + (1) y$

$\displaystyle (1)x^2 + (2)xy + (1)y^2$

$\displaystyle (1)x^3 + (3)x^2y + (3)xy^2 + (1)y^3$

$\displaystyle (1)x^4 + (4)x^3y +(6)x^2y^2 + (4)xy^3 + (1)y^4$

Okay, okay, I’ll stop. It should be entirely too obvious by now. Hold onto this because I’ll come back to it in a moment.

First let’s talk about a number I mentioned before. The golden mean is defined mathematically as the ratio:

$\displaystyle \varphi = \frac{1+\sqrt{5}}{2}$

This, my friends, is a binomial. It’s a really special binomial, it is easy to work with and has some cool properties when the binomial theorem is applied to it. Now, let me introduce you to another formula called the Binet formula. It gives one the nth number of the Fibonacci sequence.

$\displaystyle F_n = \frac{\varphi^n - (1-\varphi)^n}{\sqrt{5}}$

It’s a nice little gem of a formula, but let’s write it out in terms of the binomials it contains:

$\displaystyle F_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n\sqrt{5}}$

It may look more frightening, but trust me, it’s simpler this way. There is some “magic” we can do with the binomials on the top. Let me show you, but first I’ll need to introduce you to the summation sign. He’s a simple fellow who might look scary. All he does is add things together. Lets watch him add all the numbers from 1 to 5.

$\displaystyle 1 + 2+ 3 +4 + 5 = \sum_{i=1}^5{i}$

That’s all there is to it, just start with the number 1 in the variable i, evaluate the expression, increment i, evaluate the expression, add it to the previous result, rinse, repeat as needed.

Now, I’ll continue. The term $(1 + \sqrt{5})^n$ can be written as a series sum $\sum_{i=0}^n{{n \choose i}\sqrt{5}^i}$ and the term $(1 - \sqrt{5})^n$ can be written as $\sum_{i=0}^n{{n \choose i}(-\sqrt{5})^i}$. Put these together and several things happen because of the minus sign. It actually sorts out the odd powered terms, getting rid of the even terms (because the even terms are subtracted from each other, while the odd terms are added to each other). That leaves:

$\displaystyle F_n = \frac{1}{2^n\sqrt{5}}\sum_{i \nmid 2}^n{{n \choose i}2\sqrt{5}^i}$,

which reduces to,

$\displaystyle F_n = \frac{1}{2^{n-1}}\sum_{i \nmid 2}^n {{n \choose i}5^{\frac{i-1}{2}}}$

,
and the notation $\displaystyle i\nmid2$ means all i not divisible by 2 or all i mod 2 = 1. It’s the notation used by Ireland and Rosen, not to be confused with other notation meaning the first number divides the second number.

Now you look at me and ask, “How did that get any simpler”? It didn’t really, but this has the property of proving that all numbers in the sequence will be integers, otherwise known as nice round whole numbers! How? Notice that we are summing over all odd numbers less than n starting with 1, if one subtracts 1 from an odd number one gets an even number back. An even number is divisible by two, so that fraction in 5’s exponent reduces to an integer.

Oh, I guess I still need to prove that 2 raised to n-1 evenly divides the sum. In the case of n = 0, the sum equals zero and 0 times 2 = 0. For n = 1, we have 1 times 1 = 1. Now, for every other case there is a 1 plus an odd number multiplied by a coefficient that grows faster than 2 raised to n-1. I give up for now. 🙂 I just know that there are enough twos being multiplied and added together that 2 raised to n-1 divides out evenly.

The corresponding formulas for the Lucas series are:

$\displaystyle L_n = \frac{(1+\sqrt{5})^n+(1-\sqrt{5})^n}{2^n}$

and

$\displaystyle L_n = \frac{1}{2^{n-1}}\sum_{i \mid 2}^n {{n \choose i}5^{\frac{i}{2}}}$

where the summation is over all even integers less than n divisible by two starting with zero, or where the condition i mod 2 = 0 holds.

The next exploration I have in mind for this is to derive something called a q-analog of these series. Also, (and I’m stoked about this!) I want to look at what the Fibonacci and Lucas sequences look like when extended into the complex plane.

#### Updated code:

Here is some Ruby code for calculating the Fibonacci and Lucas numbers using my derived methods. I took advantage of the functional aspects of Ruby to simply writing out the computation and sorting the odd and even terms before applying the rest of the computations. Another optimization I made was to create a factorial lookup table. Instead of computing the factorial every time, it calculates all factorials in an array and looks up the number (resulting in quite a speed increase, but the ). Also, note that this version uses my fully simplified identities and will obviously only return integers. The past version suffered from rounding errors, and the result had to be cast back into an integer. Just copy and past the following into fibonacci.rb, and type ruby fibonacci.rb 100 to get the first one hundred numbers in each sequence.

 base = 5 num = ARGV[0].to_i

 def is_even(n)   n % 2 == 0 end def is_odd(n)   n % 2 == 1 end def sum (set)   set.inject(0) { |total, i| total + i } end def setup_factorial(n)   f = Array(0..n)   f.map! { |i| if i == 0 then 1 else i*f[i-1] end } end def choose(n, k, f)   f[n] / ( f[k] * f[n-k] ) end def lucas(base, range, f)   lucas = Array(range)   range.each do |n|     lucas[n] = Array(0..n)     #compute lucas terms     lucas[n] = lucas[n].select { |i| is_even(i) }     lucas[n].map! { |i| choose(n, i, f) * base **(i/2) }     lucas[n] = sum(lucas[n]) / (2**(n-1))   end   lucas end def fibonacci (base, range, f)   fibonacci = Array(range)   range.each do |n|     fibonacci[n] = Array(0..n)     #compute fibonacci terms     fibonacci[n] = fibonacci[n].select { |i| is_odd(i) }     fibonacci[n].map! { |i| choose(n, i, f) * base **((i-1)/2) }     fibonacci[n] = sum(fibonacci[n]) / (2**(n-1))   end   fibonacci end 

puts "Setting up factorial lookup table..." factorial = setup_factorial(num) puts "Done." puts "Calculating series..." fibonacci(base, 0..num, factorial).each { |i| print i, ", " } puts 

#### Old Code

Here is some ruby code for calculating the Fibonacci and Lucas numbers using my derived methods. Please note that it inefficiently sums over both even and odd numbers in both series, but multiplies the unneeded results with a zero. It also cheats the rounding errors by casting the floats back into an integer (which might actually cause some numbers to be wrong).

 def is_odd(n)   n%2 end

 def is_even(n)   (n+1)%2 end def sum (range)   range.inject(0) { |total, i| total + yield(i) } end def factorial(n)   if n == 0     1   else     n * factorial(n-1)   end end def choose(n, k)   factorial(n) / ( factorial(k) * factorial(n-k) ) end def fibonacci(n)   ( sum(0..n) { |j| is_odd(j) * choose(n, j) * (Math.sqrt(5)**(j-1)) / 2**(n - 1) } ).to_i end def lucas(n)   ( sum(0..n) { |j| is_even(j) * choose(n, j) * (Math.sqrt(5)**j) / 2**(n - 1) } ).to_i end 

(0..100).each { |j| print fibonacci(j), ", " } puts (0..100).each { |j| print lucas(j), ", " } puts 

# Today is really Square Day!

——– Original Message ——–
Subject: Happy Square Day!
Date: Thu, 05 Mar 2009 17:24:39 -0600
From: Roger Hill
Reply-To: Handheld Computing Conference discussion list
Organization: Southern Illinois University at Edwardsville
To: hhc@lists.brouhaha.com, ****@deepthought.com

Hi all,

Recently there was something in the news about “Square Root Day”,
03/03/09, and Richard Nelson circulated an E-mail about it. I was
you would get if you just ran the day, month, and 4-digit year
together as MMDDYYYY and looked for perfect squares. For example,
today in American-style notation is 3/05/2009 which runs together as
the number 3052009.

So I checked on that, and was rather startled to discover that the
nearest “square day” is actually TODAY! Happy Square Day!!

Naturally I had to turn a computer loose on the problem, so using
Excel I found that today is only the 6th square day since 1900 (which
is as far back as Excel deals with dates). The last one was
9/01/2004. But the next one is only a few weeks away, 4/01/2009 (no
fooling!). After that, you’ll have to wait till 2/26/2016.

If (like me) you favor the YYYY/MM/DD notation, today is not a square
day but the next one will be 2015/11/21. I have not yet tried to
figure it out for the European-style (DDMMYYYY) format.

— Roger

(P.S. I’m sending this to both the HHC and the CHIP lists; sorry if
you get it twice as a result.)

_______________________________________________
HHC mailing list
HHC@lists.brouhaha.com
http://lists.brouhaha.com/mailman/listinfo/hhc

# Happy 3.14159265358979323846… Day!

Today is PI Day, the unofficial holiday of geeks all around.

Have a good (PI) day.

If you missed it — it’ll happen again next year.