Shor, I’ll do it

I ran into this article by Scott Aaronson today and thought I would share it.  To wet your taste, here's the first sentence of the second paragraph:

Alright, so let’s say you want to break the RSA cryptosystem, in order to rob some banks, read your ex’s email, whatever. 

Overall, I found it to be a pretty good writeup for the layman.  It's a little esoteric when it comes to explaining the QFT, but still - he did a good job.

Stern–Brocot tree and Continuous Fractions

This post continues the previous entries on Continuous Fractions.  This time, we expand the concept to encompass the Stern-Brocot tree.

The Stern-Brocot tree is a binary search tree where the two legs represent "less than" and "more than" (or Low,High or Left,Right, etc).

As you can see from the image, it starts with 1 (or 1/1) at the top. The left side is less than 1 and the right side is more than 1.  Once you choose a side; its' children are then less/more than that node.

Ok, that looks cool -- but what can we do with it?

We can use it to make a simple continued fraction for any positive number (decimal, fraction or whole number).  We could probably expand it to handle negative numbers by starting at 0 instead of 1, but then we'd have to revisit the division-by-zero post.

The simple continued fraction is simply the continued fraction that has a '1' for all the partial numerators.  Let's look at a simple example of how we can convert a decimal number into a continued fraction through use of the Stern-Brocot tree.

For this example, let's start with a simple decimal... Let's say, 1.25.
To convert the decimal to the SB tree, we'll walk down the tree and record our chosen path with 'L' for left and 'R' for right.

We start with the 1/1. Since 1.25 > 1/1, we choose the Right side of the tree.
Next choice: Since 1.25 < 2/1, we choose the Left path.
Next, 1.25 < 3/2, so again we choose the Left path.
Next, we chose Left for 1.25 < 4/3.
Last, we choose Left for 1.25 = 5/4 and we are done.
So, in order, we chose RLLLL.
We could also write that we chose R¹L⁴.

But how do we translate that to a continued fraction?  We just use the exponents!

R¹L⁴ becomes [1;4].
Note: If we were using a number lower than 1 as our target, we'd put a '0' in front of that (like [0;1,4] which is actually the inverse; or 4/5).



The process is easily reversible as well.  Let's say we started with that Continued Fraction of [1;4].
First, we need to know whether to start with Left or Right.  If the first digit is 0, choose Left; otherwise choose Right.  So, for [1;4] we choose Right.
We remember that the number are the exponents; and that it will always alternate.  So [1;4] becomes R¹L⁴ .
The exponents represent a count of how many of that letter to choose; so that becomes [R][LLLL] or RLLLL.
Walking down the SB tree, we choose in order: 1/1, 2/1, 3/2, 4/3, 5/4.

Ok, that is all well and good... but that tree only shows a few rows; what do we do when it runs out?

The process for generating the next row isn't so bad when you see it paired with the continued fractions.
Below 5/4 for example:

5/4 = [1;4]
assuming that is in the form [a0;a1,a2,...,ak] the two children are:
[a0;a1,a2,...,ak+1] on the left and [a0;a1,a2,....,ak-1,2] on the right
Or in our particular case:
[1;4+1] = [1;5] = 6/5 = 1.2 on the left
[1;4-1,2] = [1;3,2] = 9/7 = 1.2857142857142858 on the right
and it is easy to verify that 1.2 < 1.25 < 1.2857...
or that 6/5 < 5/4 < 9/7


One more simple example in honor of 1:59 tomorrow....:
RRRLLLLLLLRRRRRRRRRRRRRRRLRRRRRRRRRRRRRRRRRRRRRRRRRLRRRRRRRLLLL
[3;7,15,1,25,1,7,4]
314159/100000 = 3.14159

Slashdot: 47th Mersenne Prime Confirmed

The new prime, 2^42,643,801 - 1, is actually smaller than the one discovered previously.

Primality of 1

When I was in school, I remember them teaching that a prime number was any number divisible by only 1 and itself. Thus, in school, they taught that 1 was prime. Since then, I have noticed that everyone insists that 1 is not prime. Since many of the patterns I find work better with 1 being prime, I decided to try to figure out why the discrepancy...

From Wikipedia:

Until the 19th century, most mathematicians considered the number 1 a prime, with the definition being just that a prime is divisible only by 1 and itself but not requiring a specific number of distinct divisors. There is still a large body of mathematical work that is valid despite labelling 1 a prime, such as the work of Stern and Zeisel. Derrick Norman Lehmer's list of primes up to 10,006,721, reprinted as late as 1956,^[2] started with 1 as its first prime.^[3] Henri Lebesgue is said to be the last professional mathematician to call 1 prime.^{[citation needed]} The change in label occurred so that the fundamental theorem of arithmetic, as stated, is valid, i.e., “each number has a unique factorization into primes.”^[4][5]

So there you have it. They decided in the last 43 years that 1 could no longer be prime so that one of their theorems could be correct. Why does that remind me of someone fudging statistics?

I know, I know... soapbox, right? First the divide-by-zero post, then this... How about this, as soon as we can explain all our math in simple fractals without saying things like "except 0 or 1" or "with n>1", then I'll change my position on it.

Thus Theorem 1 of Hardy & Wright (1979) takes the form, “Every positive integer, except 1, is a product of primes”

bah humbug ;)

Prime digits

A coworker made a comment to me Friday about the distribution of digits in prime numbers. He was referring to a recent Slashdot article talking about the first digit in the prime number...

but I have never liked thinking of the 1st digit as the far left... I'd prefer to think of the far right digit as digit 0. Can't help it - it's the whole positional notation thing (10^3 10^2 10^1 10^0 . 10^-1 10^-2 etc)...

So I started looking at the distribution of the primes on the right side.

The last digit (digit 0, far right digit) is directly related to the number of primes...
Now 2 and 5 are both used once (for themselves).
0,4,6 and 8 are never used.
1,3,7,9 all follow this pattern:

Assume {x} = {1,3,7,9}
Assume {y} = {all primes < 10^n}
let z = ({y} ≡ x (mod 10^n))
z is also the number of times that x was the last digit in {y}

So let's look at a simple example...
{y} = {all primes < 10000}

0 was never the last digit
1 was the last digit 307 times (if you count 1 as prime, 306 otherwise)
2 was the last digit once ('2')
3 was the last digit 310 times
4 was never the last digit
5 was the last digit once ('5')
6 was never the last digit
7 was the last digit 308 times
8 was never the last digit
9 was the last digit 303 times

similarly...
there were 307 primes ≡ 1 (mod 10000) [assuming 1 counts as prime]
there was 310 primes ≡ 3 (mod 10000)
there was 308 primes ≡ 7 (mod 10000)
there was 303 primes ≡ 9 (mod 10000)

For {y} < 100000, we have
0 2388 1 2402 0 1 0 2411 0 2390

For {y} < 1000000, we have
0 19618 1 19665 0 1 0 19621 0 19593

etc

Checking OEIS, I found those sequences listed here:
A073505 for 1 (if 1 is *NOT* prime)
A073506 for 3
A073507 for 7
A073509 for 9

A006880 seems to be the SUM of each line
Example: 0+307+1+310+0+1+0+308+0+303=1230 [-1 for the sequence due to 1 being prime or not] < 10^4

So it doesn't really get us much... but it does tell us that the number of primes ending in X is equal to the number of primes congruent to X mod 10^n.

Division by Zero

I've been on this kick lately where I have started question some of the basic assumptions I learned in math... things like "you can't easily define pi" or the concept of an "irrational number". Today's philosophical debate is on the idea of division by zero.

This came up because I was creating a ContinuedFraction interface for integers... The number 3, for instance, is 3 + 0/0 + 0/0 .... etc... instead of zeros I had to replace them with nulls in order to prevent the app from trying to compute the 0/0 bit... That got me thinking... maybe it should be allowed...

Let's take a simple concept. Let's say there are 10 pennies on the table, and it is decided that the pennies will be split evenly amongst everyone at the table. [Yes, pennies - I don't want anyone getting the bright idea to make change].

Now, if there are 5 people, everyone gets 2 pennies. Simple.

If there are 3 people, everyone gets 3 pennies and 1 is left on the table.

If there are no people, then there is still 10 pennies on the table.

What's so difficult about that?

So, in essence:
10/5 = 2r0
10/3 = 3r1
10/0 = 0r10
Seems like Occams Razor would say that the whole concept has been arbitrarily inflated to give us errors, exceptions and NaN.

What about the other way around?

If there are 0 pennies...
0/5 = no pennies for anyone
0/3 = same
0/0 = same

Seems like we really don't have an issue there.

Of course, this would mean that things such as limits get screwed up -- but so what. If we think we have irrational numbers, why not stir the pot a bit? Maybe they were not correctly defined in the first place.

Besides, that will open up the ContinuedFractions to more interesting options... like

SeriesCF

While working on my ContinuedFractions library today, it occured to me that our current representation of pi could be simplified by just specifying the numerators and denominators as series...


I went ahead and changed the implementation to use a new SeriesCF class instead of the default ContinuedFraction class and I think the new approach is much cleaner.

PresenTeX

While writing this package today, I came across the PresenTeX website. Very nice...


from
cf = d_0 + \cfrac{n_0}{d_1 + \cfrac{n_1}{d_2 + \cfrac{n_2}{d_3 + \cfrac{n_3}{\ddots\,}}}}
I got:

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