## 27 July 2007

### Intuitive Approach to Wilson's Theorem

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

## 20 July 2007

### An Intuitive Guide To Exponential Functions & E

## 15 July 2007

### Wikipedia: Mental Arithmetic

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

## 06 May 2007

### Coprime, aka. Relatively Prime

## 13 April 2007

### Subfactorial

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.

## 05 April 2007

## 01 March 2007

## 26 February 2007

## 16 February 2007

### Pascals' Cototients

## 15 February 2007

### Pascal's Totients

## 12 February 2007

### Pascal and Binomial Coefficients

(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 =

1x^{2} + 2x + 1 =

*1 2 1*

(x+1)^{3} =

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

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

(1x^{2} + 2x + 1)(x+1) =

(1x^{2}*x + 1x^{2})+(2x*x + 2x*1)+(1*x + 1*1)=

1x^{3} + 1x^{2} + 2x^{2} + 2x + x + 1 =

1x^{3} + 3x^{2} + 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) =

(1x^{3} + 3x^{2} + 3x + 1)(x+1) =

(1x^{3}*x + 1x^{3}*1)+(3x^{2}*x + 3x^{2}*1)+(3x*x + 3x*1)+(1*x + 1*1) =

1x^{4} + 1x^{3} + 3x^{3} + 3x^{2} + 3x^{2} + 3x + 1x + 1 =

1x^{4} + 4x^{3} + 6x^{2} + 4x + 1 =

*1 4 6 4 1*

## 07 February 2007

### 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.

## 06 February 2007

### Binary Representation of Pascal's Triangle

To look like this, one thing you might do is work out all the values of the previous lines and then mod them to determine whether they should be highlighted or not.

Yet another way might be to just keep track of whether the values above are 1 or 0, and realize that the next one down is only 0 if both the parent hexes are 1.

But, how about a way to do it without any regard to previous rows? This method is quite simple...

Let's say you want to examine nCr (n=row, r=col)... say, 5C2 (10 if you look at the image)...

How do we do it? First, write down the binary value of n and r.

Now, if ANY digit in r is larger than the corresponding digit in n, it is even. Otherwise, it is odd.

Looking at our example, we compare:

bits | |||
---|---|---|---|

2 | 1 | 0 | |

n | 1 | 0 | 1 |

r | 0 | 1 | 0 |

r[1] is higher than n[1] so it is even |

So, to determine if any point in Pascals' Triangle is odd/even, you just have to compare the binary representation of the row and column. :)

## 26 January 2007

### Twin Primes

While it is not visually obvious which numbers are multiples of two, we do know that all multiples of 3 end in 0. Since no prime (except 3) can be a multiple of 3, that means that all primes are going to end in ī or 1. Well, since we know all primes are odd, that also means that the specific number with a 0 ending would have also been a multiple of 2. IE: The number ending in 0 would have been a multiple of 6.

Where am I going with this? Well, let's look at the first few multiples of 2*3

6 - 5 and 7 are twin primes

12 - 11 and 13 are twin primes

18 - 17 and 19 are twin primes

24 - 23 and 25... nope, not that one (23 is prime though, other is 5

^{2})

30 - 29 and 31 are twin primes

36 - 35 and 37... nope, not that one (37 is prime though, other is 5*7)

42 - 41 and 43 are twin primes

48 - 47 and 49... nope, not that one (47 is prime though, 49 is 7

^{2})

54 - 53 and 55... nope, not that one (53 is prime though, other is 5*11)

60 - 59 and 61 are twin primes

66 - 65 and 67... nope, not that one (67 is prime though, other is 5*13)

72 - 71 and 73 are twin primes

80 - 79 and 81... nope, not that one (79 is prime though, 81 is 9

^{2})

well obviously that wasn't the "correct solution"...

let's start with a simple question - did we miss any twin primes?

well we miss (3,5) - but that could just be because we were specifically looking for multiples of 6.

other than that, we did not skip any twin primes

what about those 'extra' entries?

well some are when we have squares (5

^{2}, 7

^{2}, 9

^{2})

the others are 5*{7,11,13}

could be a pattern there... partial one anyways...

let's look at it from another aspect... what primes did we miss?

obviously anything below 6 since we started with multiples of 6

other than that, we got all primes...

and 6 extra values below 82... so about 7% too many

it has to become less usable as we get higher, doesn't it?

600 - 599 and 601 are twin primes

606 - 607 is prime

612 - 613 is prime

618 - 617 and 619 are twin primes

624 - (neither 623 or 625 are prime)

630 - 631 is prime

636 - (neither 635 or 637 are prime)

642 - 641 and 643 are twin primes

648 - 647 is prime

652 - 653 is prime

660 - 659 and 661 are twin primes

and no primes are missing (though a couple extras)

## 18 January 2007

### Prime Numbers, Assumptions and Thoughts

First, it is commonly believed that there is no pattern to prime numbers. Research studied under this belief might very well be simply falling prey to self-fullfilling prophecy. We know that prime numbers do indeed have a pattern. How? Because color-coding a Pascal Triangle to look like a Sierpinski Gasket shows that prime numbers form perfect fractals, while composite numbers show overlapping fractcals. I discussed this a little while ago. Using this method, with just a couple sentences of explanation, ANYONE can look at a picture (mod some number) and tell you if it is a prime number or not (primes look clean, composites look cluttered). The pattern is visually obvious.

Second, let's tackle the concept that '1' is not a prime number... Some people will tell you that '1' isn't prime because it doesn't fit the rules. Others because it isn't convenient. Still others say it was due to the Greeks thinking number games weren't as challenging with it. Hell, you are probably wondering why we even care... Simple: If '1' IS a prime number, then all the equations that don't

*quite*work change... the math changes... We get rid of "except 1" or ">=2" type of exceptions... but most importantly, because it would force us to look at things differently -- which is what we desperately need if we are going to 'solve' primes.

So, what about the argument that it doesn't fit the rules? What is the definition of a prime number? Generally, people assume it is "any number greater than 1 that has only 1 and itself as factors".. So 1*3 is prime because no other number is a factor. 1*4 is not prime because 2 is a factor. 1*1 has no other factors, therefore it should be considered prime. But, you also see why people have a problem with it. Because it is also a square ;) They always say "1 and itself"... Well, under that definition '1' should be prime. The only reason they say it isn't is because they add the clause "greater than 1" or "except 1" to the rule. Occam's razor fans should be well aware of the problem here. You don't add a single exception (for a number that would otherwise work) just because you don't like or understand it.

You are probably still wondering why we care... Let's say you are writing an equation... f(n)=nth prime. Well, if '1' is prime, then all the current attempts are actually doing f(n)=(n+1)st prime... thus patterns may be easier to see if we quit assuming 1 can't be prime.

What other assumptions do we have? Primes get further and further apart... Not true... No matter how high you go, there will be twin primes. This tells us that twin primes are not a special case or exception -- but are in fact part of the pattern. And don't forget what we said earlier -- it is a fractal -- so it repeats forever.

In fact, the whole concept that there are 'types of primes' is simply a misnomer. Each type of prime is simply a subset of the fractal.

## 17 January 2007

### Slashdot | Largest Twin Prime Yet Discovered

The Twin Internet Prime Search and PrimeGrid have recently discovered the largest known twin prime. A twin prime is a pair of prime numbers separated by the integer two. The pair discovered on January 15th was 2003663613 * 2195,000 ± 1. The two primes are 58,711 digits long. The discoverer was Eric Vautier, from France.