Prime Numbers

x/log(x) (red) Approximates the Number of Primes under xx/9 (blue)The green line shows the difference

Playing with a little bit of algebra and trying to write a program to solve a particular problem. I need to factor a number, which means I need a list of prime numbers, so how much space do I need given a number of certain size? x/9 (blue) approximates x/log(x) well enough for my purposes for values of x under a billion.

P.S. Finished my factoring program.

Playing with Numbers

Why do prime numbers make these spirals?
This video is pretty entertaining, at least if you like numbers. The first half is pretty straightforward. The second half where he starts talking about Dirichlet's Theorem (14:48) is a little more esoteric. I know some people are fascinated by infinity, but I am not one of them. It comes in handy for imagining how things will go, but for any kind of concrete answer, it's pretty worthless.

How Many Prime Numbers in a Grid Full of Digits?

Ray Tracing - Project #8 - Kevin Wall

I started another community programming puzzle over on Codingame.com yesterday. One of the first problems I ran into was determining how much storage space I would need. Writing down my thoughts sometimes helps clarify the issue, and since the editor on the Codingame IDE doesn't have automatic word wrap, nor does the brain dead Linux text editor, I used what was handy, which was Blogger. Plus I got a blog post out of it.

The problem is straight forward enough: We are given a grid filled with numeric digits. Our job is to find out how many prime numbers we can find in this grid.

Since maximum size of the grid is 8 by 8, none of our numbers can have more than 8 digits. The standard storage space for an integer is 32-bits. Leave off one bit for the sign (positive or negative) and the largest number you can store in this space is two billion and something, which has 10 digits, so a standard integer should do fine for all of our work.

The grid has R rows and C columns, so there can be at most R x C single digit prime numbers, but less than ten, because there are only ten digits, and actually only 4, because there are only 4 single digit prime numbers: 2, 3, 5 & 7.

An R by C grid can have at most:

• ((R - 1) x C) + (R x (C - 1)) two digit prime numbers.

An 8 by 8 grid can have:

• (7 x 8) + (8 x 7)                   two digit prime numbers.
• (6 x 8) + (8 x 6), or (2 x 8 x 6) three digit prime numbers.
•                       (2 x 8 x 5)  four digit numbers

Continuing the pattern, the total comes out to (2 x 8 x 7!) or 80,640. Would is be possible to generate a grid that had that many unique prime numbers? That's another question and given that even if we only need four bytes for each number, we are going to need less than half a megabyte of RAM, so we don't need to go any further, we'll just allocate space for 80,640 integers.

It is a relatively simple programming problem, but the boss lady was on a rampage yesterday so my concentration was impaired. Also, I was a little out of practice since I hadn't done any programming for several weeks. In particular, I wasn't able to put together a simple procedure to determine if a number was prime. I figured out the solution this morning. Turns out you need to hold TWO coherent thoughts in your head in order to make it work. One thought is not sufficient.

Babylonian Trig, Part 2

A plot of the first 47 Pythagorean Triples - Jrkenti

I'm looking at the numbers from the Babylonian Cuneiform Tablet Plimpton 322 and I notice that one triangle (#11) can be scaled way down. Divide all sides of #11 by 15 and you have your basic 3, 4, 5 right triangle. Then I look at the others and I notice that one side of every triangle can be factored using only the numbers, 2, 3 and 5. Well, all except #3. All the rest are prime numbers. This leads me to Euclid's formula for generating Pythagorean Triples. Working backwards I figure out what the values are for l and m, and factored them, and what do you know? The only factors of l and m are 2, 3  and 5, well, except for #3. I don't know if this proves anything, except maybe that Oswald killed Kennedy, or maybe it proves the reverse. In any case figuring this all out kept me entertained for a couple of hours. The spreadsheet has three pages. The first is the original data, the second converts the numbers to decimal and verifies some obscure mathematical assertion that some other egghead figured out, and the third contains the triples and their factors.

Pi from Nothin'

Riemann Hypothesis - Numberphile
Stu turned me on to an obscure little math trick for determining if a number is a prime number or not. It's not generally useful as it involves factorials, which get really big really fast. But there is a computer math package that can deal with numbers of any size, as long as you have enough computer memory to accommodate them, so I thought I would take Stu's formula and the GMP math package and see if I could make them play together.
     Dealing with really long numbers is not very difficult, you just have to keep track of overflows. Any half competent programmer should be able to write a set of routines to perform the basic operations, but it's a common enough job that some people got together and wrote a complete library of functions and procedures.
    Like any bit of software there are rules for how to use it. For me the easiest way to learn these rules is find a sample piece of code and start messing with it, so I went looking and I found this: randPi.c by Mitch Richling, which to purports to make Pi out of nothing but random numbers. He uses the GMP library to deal with his really long random numbers, so it was good example to start with. Plus it was weird. Pi from nothin'? How can that be?
     It depends on the observation that between any two random numbers, there is a statistical probability that they are relatively prime, i.e. the only factor they have in common is one. 3 and 4 are relatively prime. 3 and 6 are not, they have a factor of 3 in common. 4 and 6 are not, they have the factor 2 in common. Two numbers by themselves won't tell you much, but if you have big pile of them and start counting the number of pairs that are relatively prime and those that aren't, you end up with a ratio that (if you munge it just a bit) looks just like Pi.
    I got to thinking about this and realized you don't really need random numbers. After all, random numbers are just one number out of a range of numbers. You run long enough and you will cover all numbers in the range. You should be able to get the same effect by just testing the relative primeness of all the numbers in a range. I wrote a small program to test this and it indeed works. Running a cross tabulation of all the numbers from 1 to ten thousand resulted in value of 3.141534, which is not bad considering I made it from nothin'.

    Okay, we have GMP library and we think we know how to use it. Let's test Stu's formula, so I wrote another little program, it works and so Stu's formula seems to be valid. My program only goes up to 31, but that's only because we are starting to fill up the screen with the giant numbers that come from computing factorials. 31! (31 factorial) is like a zillion digits.

P.S. I have decided I don't like github because they don't handle tabs. Google Drive / Docs has a viewer that works okay and the two programs are stored there. It doesn't support highlighting, and there may be some argument over tabs, but it's not bad, and it doesn't require any extra fooling around.

ABC @ Home

I came across this story about prime numbers on Graham Hancock's website. Seems some dude has proven some conjecture about ABC Triples, whatever they are. The proof is only 500 pages long. I'm gonna sit down and read that just as soon as I win the lottery. The story doesn't do a good job of telling what an ABC Triple is, much less why we should care, so I fed it to Google and found some interesting stuff. The least interesting was this page that does a pretty good job of explaining what an ABC Triple is, and makes a pass at explaining why we might care.

A page on slashdot has an apparently endless discussion about how math articles in Wikipedia are only good for grad students, even the Wikipedia articles on algebra are of no help to any lesser beings, like a high school student who is trying to learn algebra.

I followed a link on another page and found that there are a whole bunch of these "@ home" projects going on. The idea behind "@ home" is there are some projects that might produce some useful results, if only enough computer power was available, so someone designs a program that can be run on a whole bunch of PC's independently, and encourages PC owners to download and run these programs. The programs run in the background and only when nothing else is going on, which for most computers is most of the time. So we are putting all those idle CPU cycles to use. I had heard that SETI was using this and there is a protein folding program floating around somewhere. There was even a program that was attempting to solve the Eternity II puzzle. This guy was running over a dozen. I don't even know what most of them are.

The picture comes from the original story. I thought it was an interesting take on prime numbers. Notice how most of the prime numbers line up on diagonals, or occupy corners. I wrote a simple prime number sieve some time ago and this prompted me to go look for it, but it seems to have vanished. No big loss, the prime number business has become a quagmire. I don't know how far they have gotten, but I imagine they are up into the hundreds of digits. With numbers up to a value of a million or so, it's kind of interesting, but once you've got a thousand prime numbers it's no longer fun. It's more like work.