Continued Fractions

I was working on some continued fractions, and came across the fundamental recurrence formula above. It worked pretty well for some simple continued fractions (like √2) but seemed to be a bit unfriendly towards calculating π.

I'm using this definition of π:


Now, using that definition with the above equation, it was always completely wrong...

So I tried changing the equation...

So you'll notice a few specific changes... 1) A₁ has been redefined in terms of previous results. 2) A₁ reduced the index on a₁ to a₀. 3) A_n+1 changed the index on a_n+1 to a_n. 4) B_n+1 changed the index on b_n+1 to b_n.

This may seem like a lot of changes, but really #1 didn't change the outcome at all and the rest were all about reducing the index of a/b.

Net result? All the previous stuff (√2, golden mean, etc) give the same results as before... but now π works.

Intuitive Approach to Wilson's Theorem

The other day I stumbled across something, only later to realize that it was Wilson's Theorem. Since the approach used to find it in the first place was more of a 'common-sense' approach than what you usually encounter for it, I thought I would go ahead and present it.

Let's look at two examples.... For both, what we are looking for is:
(n-1)! % n ≡ (n-1) mod n; iff n is prime

Example 1: Composite Numbers
Let's try to determine whether '10' is prime (which we know it isn't but that just makes the example easier to follow)...
(n-1)! is 1*2*3*4*5*6*7*8*9
when we mod it by 10, what we are really saying is to "find missing factors of 10"
since both 2 and 5 are in the list, the end result will be 0*
ie: (10-1)! % 10 ≡ 0 mod 10

Example 2: Prime Numbers
Let's try to determine whether '11' is prime
(n-1)! is 1*2*3*4*5*6*7*8*9*10
when we mod by 11, what we are really saying is to "find missing factors of 11"
since 11 is not in the list, the number is prime and the end result is 10 (or -1)
ie: (11-1)! % 11 ≡ 10 mod 11
or: (11-1)! % 11 ≡ -1 mod 11

* It appears that the only composite number to NOT result into congruency with 0 is '4'
(4-1)! % 4 ≡ 2 mod 4
I believe this is because it is 2-squared and it 2-away from it... thus since we get further away as we go on, it won't happen again.


Unfortunately, this didn't end up being nearly as clear as my first draft did, but let's try to make the useful bit clear here... directly from Wilson's theorem:

(n-1)! % n ≡ -1 mod n; iff n is prime
or
(n-1)! % n = (n-1) mod n; iff n is prime

or... to put it into Windows Calculator speak:
[type in some number][M+][-][1][=][n!][mod][MR][=]
if the result is equal to [MR]-1 then it is prime
otherwise the result will be 0 (or '2' for n=4) and the number is composite/non-prime

An Intuitive Guide To Exponential Functions & E

Fairly simple explanation of what 'e' is and how it works.

Wikipedia: Mental Arithmetic

I stumbled upon this today, and thought I would share. Some interesting stuff in there.

We really should start teaching kids mental arithmetic at an early age rather than the "show your work or get an F"

Coprime, aka. Relatively Prime

Two numbers are coprime (relatively prime) if they have no factors in common.
I thought this image from Wikipedia was a good visual way of seeing it:

Figure 1. The numbers 4 and 9 are coprime because the diagonal does not intersect any other lattice points

Subfactorial

I thought this was a good way of explaining it:
In practical terms, subfactorial is the number of ways of putting n letters into n envelopes (one in each envelope) with none in its correct envelope.

Pi

This is probably the simplest explanation of Pi that I have ever seen:

Mock Theta Functions

Sum of Series

sum of odd integers < 2n = n²

sum of all integers = n(n+1)/2

Pascals' Cototients

Similar to yesterdays' post, this one is based off the totients of the values in Pascal's triangle.. but this time, we are displaying the Cototients (n - totient(n))...

Pascal's Totients

I was trying to figure out new ways to look at Pascals' Triangle today, and decided to look not at the actual binomial coefficients, but at the Euler Totients of them. Take a gander.

Pascal and Binomial Coefficients

I realized that I never really showed how Pascal's Triangle is related to the Binomial Coefficients... So here we go:

(x+1)0 = 
1

(x+1)1 =
1x + 1 =
1 1

(x+1)2 =
(x+1)(x+1) = 
x*x + x*1 + 1*x + 1*1 = 
1x2 + 2x + 1 = 
1 2 1

(x+1)3 =
(x+1)(x+1)(x+1) = 
((x+1)(x+1))(x+1) = 
(1x2 + 2x + 1)(x+1) = 
(1x2*x + 1x2)+(2x*x + 2x*1)+(1*x + 1*1)= 
1x3 + 1x2 + 2x2 + 2x + x + 1 = 
1x3 + 3x2 + 3x + 1 =
1 3 3 1


(x+1)4 =
(x+1)(x+1)(x+1)(x+1) =
((x+1)(x+1)(x+1))(x+1) = 
(1x3 + 3x2 + 3x + 1)(x+1) =
(1x3*x + 1x3*1)+(3x2*x + 3x2*1)+(3x*x + 3x*1)+(1*x + 1*1) =
1x4 + 1x3 + 3x3 + 3x2 + 3x2 + 3x + 1x + 1 =
1x4 + 4x3 + 6x2 + 4x + 1 = 
1 4 6 4 1

A Modded Pacal Triangle

As you generate very large Pascal Triangles, the numbers quickly get out of control. If you are planning on modding the values after obtaining them, why not mod them first?

Here you see an example of doing a mod5 before writing the number down... So, for example, the middle element on Row#4 is 1 because (3+3)%5 = 6%5 = 1... Now, you can use the number 1 for further rows instead of the original number 6.