Powers of 11 in Pascal's Triangle

So one of the first things you might recognize are the first few rows... The numbers "feel" familiar...

That could be because they are actually powers of 11...
11⁰ = 1
11¹ = 11
11² = 121
11³ = 1331
11⁴ = 14641

But what is 11⁵? Whoa - hold up. Let's recap just a little...

Let's re-examine 11²....
What we are really seeing is:

102	101	100
1	2	1
Which is really...
1 * 102	2 * 101	1 * 100
100	20	1
or... 100+20+1 = 121 = 112

The same is true for 11³...

103	102	101	100
1	3	3	1
Which is really...
1 * 103	3 * 102	3 * 101	1 * 100
1000	300	30	1
or... 1000+300+30+1 = 1331 = 113

Now, 11⁵ is a bit more tricky... The math is the exact same, but it is not as visually obvious...

105	104	103	102	101	100
1	5	10	10	5	1
Which is really...
1 * 105	5 * 104	10 * 103	10 * 102	5 * 101	1 * 100
100000	50000	10000	1000	50	1
or... 100000+50000+10000+1000+50+1 = 161051 = 115

Ian's discovery to get any number in Pascal's Triangle

I always found this interesting... A 12-year old student, when presented with an incomplete Pascal Triangle and told to complete it; found a different way of completing it (because they weren't told how, they were expected to figure it out)...

Instead of adding the two parents from above, they took the row as an entity in an of itself, without relation to previous rows... This was done using fractions....

Here's a brief example (click the title above for the full document) :















Note: The previous links/images became invalid. I found another copy of it online and have changed the links.

Pascal's Triangle and Prime Numbers

We start off using a basic Pascal Triangle....

If you aren't familiar with how it is constructed, the rules are quite simple... A) anywhere that is blue here is considered "0". B) Start with a "1" at the top. C) For each spot, simply add the two spots above it.

Now that we have the numbers, the next step is to mod them. If you are unfamiliar with "mod", think of it as "the remainder after division"... Thus, 10 mod 3 is 1 (10/3 = 3r1) and 10 mod 2 is 0 (10/2=5r0).

To simplify matters, all we care about is when the remainder is 0. For example, in this version of our Pascal's Triangle, we color coded in a darker blue anything that has a remainder other than 0. Anotherwords, the ones NOT colored in are MULTIPLES of 2.

One thing you will notice is that it is a fractal (known as Sierpinski's Gasket)... Basically, we have a 2x2 (2 high, 2 wide at base) triangle colored in... Then we repeat by adding 2 of those triangles to the bottom. So, in this example, the original triangle has 1 on row#0 and 1,1 on row#1. The two repeats are row#2 and row#3, and incidentally both contain the numbers 1 on row#2 and 1,3 (or 3,1) on row#3. The second copy is a mirror of the first.

Then, grab everything (original and two copies) and copy them as a group [thus the fractal] two more times.

The mod3 version (colored in red for NON-multiples of 3) shown here is similar with a slight difference. In this case, the original is 3x3.

But the real tricky part is the copying/cloning... While the first two clones (1/ 1,4 / 1,6,10) must seem like the exact same pattern as before, notice that we now make 3 more copies in the next couple rows BEFORE we group and clone.

This can be easily understood. Look back at the original triangle in mod2. Notice one entry in first row, and two entries in the second? When we clone it, we clone the one at the top twice beneath it.

Now look at the original triangle in mod3. The original has one in the top row, two in the second, and three in the third. We copy the original top one twice into our second set of rows, and three times in the third set of rows... THEN we group and repeat.

Let's take a look at another aspect... Notice the upside down "empty" triangles in the middle? For example, on mod2, row#8 through row#14? Well, what you will actually see is that at 2¹, 2² and 2³ that only the edge "1"s are colored in... That is because those rows are POWERS of 2. Similarly you see the same on 3¹ and 3² ( further isn't shown in this image )... This will actually become very important soon.


Now, let's consider what happens when we overlay them... I like to think of this like transparencies in elementary school (actually, I even bought some transparencies for this very purpose)...

The first thing you will likely notice is that some of those show blue, some show red, some show a purplish mix.

The blue ones are NOT multiples of 3 (cuz they show blue) but ARE multiples of 2 (because it would have been clear/empty on the mod2 chart).

The red ones would be multiples of 2 but NOT multiples of 3, for the same reason.
The purple ones are not multiples of 2 OR 3.
The clear/empty ones are therefore both multiples of 2 AND 3.

Let's look at some of those numbers... In the first 9 rows (0-8) the only clear/empty ones are the number 6, which is incidentally the 2*3. Then we also see 36, 12, 120.... You get the picture...

So why is this important? Well, for a couple reasons...

First, it shows that all composite numbers are actually transparent overlays of their prime factors...

Second, and this one is important, is because it also shows us what those factors are :)

How? Well, let's take a PQ value of 6 for example. Sure, off the top of our head, we know it is 2*3, but let's LOOK at it. Specifically, let's look at the row#6...

COLUMN
0	1	2	3	4	5	6
1	6	15	20	15	6	1
Now, what are those entries mod (2*3) [ie: mod6]?
1	0	3	2	3	0	1

Ok, you see what we got here? Col#2 has a value of 3. Col #3 has a value of 2. The only other non-zero entries are the mirror of these, and the 1s at the end. That is going to be true for ALL PQ where P and Q are prime.


I'll do more on this later.

Shor's Algorithm

1. Pick a random number a < N
2. Compute gcd(a, N). This may be done using the Euclidean algorithm.
3. If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.
4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:

   ,

   i.e. the smallest integer r for which f(x + r) = f(x).
5. If r is odd, go back to step 1.
6. If a ^r/2 ≡ -1 (mod N), go back to step 1.
7. The factors of N are gcd(a^r/2 ± 1, N). We are done.

Origin of Quake3's Fast InvSqrt()

Welcome

Over the last year or two, I have found myself doing a lot of math research in an effort to understand things like Pascal's Triangle, try to solve the RSA challenge, work on AI for games, etc...

So, here's a place to start keeping track of these ideas, notes, and finds.