Tuesday, July 31, 2012

GJSieve v1.7.0

With the release of MuPuPriNT v0.2a, GJSieve was updated to a sleeker and more streamlined (albeit still alpha) version.

It looks better and has fewer unnecessary things like buttons that do nothing. At the same time, it has more features.

It's worth noting, though, that there are still some issues, mainly with the output file not being formatted properly sometimes and still not printing the entire generated number when it has a lot of digits.

For a full TODO, see our wiki.

Here's what it looks like:

You can find it here.

--
JB

Monday, July 30, 2012

Spoiler alert!



I have officially finished an early draft of NCSpiral. As I mentioned earlier, find it here or read about it here.

If you want to see what the program can and will do, take a look at the screenshot below. The left is actually my desktop background (nerdy, no?) on one monitor, while I look at the resulting file from NCSpiral at 450 x 450 on the second (bigger) monitor.

Pretty happy with how this turned out, for only a day's work.



NCSpiral - alpha

6 hours later, I have written a program that will generate Ulam's Spiral.

I am still testing it, since after all I wrote it today, but you can find the source here. Also, you'll need the headers for includes and stepping functions.

Or I mean I guess just download the executable. Using this will always produce the exact same thing, since currently the only way to change anything is by editing the code.

-

I feel like that merits some explanation. Well, two things.

1. maxlength is defined as whatever you want, but eventually used to set the values of Rows and Columns, both of which are declared as type const int. This means that once they are initialized, they are set. No, this would not work:

unsigned long int n;
cout >> "enter maxlength";
cin << n;
#define maxlength n

Well, actually, I guess it would. Except for the fact that to initialize an array, you need a constant value. Otherwise you'd have to dynamically allocate, clear, and re-allocate memory blocks and blah, who wants to do that when you can just use a vector?

So neither this:

unsigned long int SpiralArray[n][n];

nor this:

unsigned long int SpiralArray[maxlength][maxlength];

would work. Both will simply give you compiler errors.

2. Formatting! It's a pain!

Consider this snippet, which is actually just a comment from my code...

/*

For formatting below, bear this in mind: Each number should have 6 "spaces" allocated to it. This is to keep things even. So, a number with one digit is printed "____n_" which means that 2 next to each other gives us "____n_____n_" - notice the even amount of space between them (5). Therefore, a number with 2 digits should  have one fewer space in front of it, and so on. ALL NUMBERS must have ONE space AFTER them. So:

1 digit:  ____n_ = 4 spaces, n, space
2 digits: ___nn_ = 3 spaces, n, space
3 digits: __nnn_ = 2 spaces, n, space
4 digits: _nnnn_ = 1 space , n, space
5 digits: nnnnn_ = no space, n, space

For numbers with more than 6 digits, you would need to edit the code so that numbers take up 7 spaces, and
add a new space before each n (so a 1 digit number has 5 instead of 4, etc).

This is scalable, it just needs editing. The whole idea of the spiral is for each number to take up the
exact same amount of space, or else there is no pattern to observe!!

*/

The last part is the most important. Think about it - why did the Excel spreadsheet work? Because it's a really powerful program that's somehow innately good for graphing? Nope. Although it is, I'll admit...

No, the reason Excel was good for the spiral is because each cell is the same size no matter what it contains. A cell where you put 1 is the exact same size as a cell where you put 1,000,000. You can even put numbers in that are too big for the cell, and they won't change size.

So, imagine that this arbitrary "6 spaces" (or 7, or however many you choose to expand it to include) is our working definition of a "cell," only instead of an XLSX, it's a TXT.

The height is luckily pre-determined by the operating system's default plain-text font and character encoding, so we just need to set the width.

I chose 6 because I wanted a space after each number - at least one. Obviously some have much more. It's Ulam's Spiral, after all. There are supposed to be huge blank spaces!

A 1-digit number needs 4 spaces in front of it because the last two characters in its "cell" must be itself and the ending space. A 2-digit number gets 3 spaces because it takes up one more space...and so on, and so forth.

So to expand to a format where we'd be able to represent bigger numbers, we increase the amount of space in a "cell." For instance, to allow 8 digit numbers to be represented cleanly, we need 9 spaces per "cell." So let's do this:

1 digit:   _______n_ = 7 spaces, n, space
2 digits: ______nn_ = 6 spaces, n, space
3 digits: _____nnn_ = 5 spaces, n, space
4 digits: ____nnnn_ = 4 spaces, n, space
5 digits: ___nnnnn_ = 3 spaces, n, space
6 digits: __nnnnnn_ = 2 spaces, n, space
7 digits: _nnnnnnn_ = 1 space , n, space
8 digits: nnnnnnnn_ = no space, n, space

Easy enough. The hard part is writing it in properly!

As always, keeping you updated.

JB

NCSpiral? - Initial notes

I wrote this in some spare time yesterday (i.e most of yesterday). As reference, consider an Excel spreadsheet that looks like this:



Also bear in mind that much of the code in these notes is actually wrong and/or won't do the right thing.

--

Ulam's Spiral is better looked at as a bunch of concentric squares for mathematical purposes.

Imagine that the origin point, 1, is at (x,y) where both x and y are (initially) 0. Each concentric square greater than 0 begins at (x+1, y) and ends at (x

+1, y-1). Additionally, x and y are re-initialized at the end of a square. Thus, if square 1 begins at (1, 0), then it will end at 1, -1).

Based on the representation in Excel, the squares should (and indeed do) begin and end thus:

x = 0, y = 0
Begin = (x+1, y)
End = (x+1, y-1)
s(n) = square name
for n++ : End (s(n-1)) = (x,y)

Format: square name = (Begin) (End)

s1 = (1,0) (1,-1)
s2 = (2,-1) (2, -2)
s3 = (3, -2) (3, -3)
s4 = (4, -3) (4, -4)
s5 = (5, -4) (5, -5)
s6 = (6, -5) (6, -6)

As you go out from the origin at 1, each square has progressively more slots. Let's number each concentric square starting with square 1, which contains only

the number 1. Square 2 contains up to 9. And so on like this:

square name (up to x) = amount of numbers

s1 (up to 9) = 8
s2 (up to 25) = 16
s3 (up to 49) = 24
s4 (up to 81) = 32
s5 (up to 121) = 40
s6 (up to 170) = 48

And so on.

This shows that each concentric square increases in "capacity" by 8 as you move outwards from the origin.

Indeed, using Excel to represent this makes sense, as you have a clear visual image that:

s1 = 3x3
s2 = 5x5
s3 = 7x7
s4 = 9x9
s5 = 11x11
s6 = 13x13

The area of each square is as follows:

s1 = 9
s2 = 25
s3 = 49
s4 = 81
s5 = 121
s6 = 169

But the numbers are around the "perimeter." However, note that the perimeter of a square is 2L+2W (or simply s*4 where s = side) which in each instance here

gives a higher value than the amount of numbers actually present. This is because the "corners" are occupied. Notice it is a difference of 4 for each:

square name (perimeter) = actual amount of numbers in each

s1 (12) = 8
s2 (20) = 16
s3 (28) = 24
s4 (36) = 32
s5 (44) = 40
s6 (52) = 48

This also shows how, incidentally, the perimeter of each square also increases by 8 each time. Thus, we have to imagine that square 0 (which contains only

the number 1) has a perimeter of 4, meaning each side has length 1. Never mind that this implies it holds 0 numbers. 

So, the formula we have thus far is:

s(x) = length of one side of square x
p(x) = perimeter of square x
n(x) = amount of numbers in square x

s0 = 1
s1 = 3
s2 = 5
s3 = 7
s4 = 9
s5 = 11
s6 = 13

p(x) = s(x) * 4
n(x) = p(x) - 4

>> n(x) = (s(x) * 4) - 4

The amount of numbers in one square of the spiral is equal to the value of 4 times the length of each side of the square minus 4.

--

Consider the Excel spreadsheet once again.

For our purposes here, it is best to imagine the  origin (1) to be cell BP100.  According to the formula,  this means that each new square should start at B

(+letter)(+1). See above - I explain that each square begins at (x+1, y) and ends at (x+1, y-1) where for each new square, the "End" values of x and y become

the new initial values for x and y.

In Excel terms, do we really need an ending value? If you start drawing a square with a line thickness of one cell, there's only one possible way to do it if

you want to increase in thickness by one cell each time - you increment the STARTING value.

See, imagine you are physically drawing a square. Your start point is wherever you put your pencil down. You are finished drawing the square once your pencil

returns to that point, aren't you? And wouldn't it be more efficient to start drawing a new, slightly bigger square around the first one starting from a

point, say, diagonal from the corner of the square? (hint - of course it is, especially for computers).

square name = (start)

s1 = (BQ100)
s2 = (BR101)
s3 = (BS102)
s4 = (BT103)
s5 = (BU104)
S6 = (BV105)
s7 = (BW106)

and so on and so forth...

Now then. The question here is one of how best to represent this programatically...and, indeed, using what language. VB? C? C++? VC?

Since I am more familiar with C/C++, let's try to represent it with that. By "it," I mean the function that would be best implemented to put numbers into the

boxes.

C and C++ do not have any way to represent shapes - at least, not as "shapes" on a "plane." What they do have, though, is the ability to create a

multidimensional array. This is essentially no different from a matrix. It is represented textually as a grid of numbers, and you can pick x and y co-

ordinates of each number in the array very simply.

To create a multidimensional array, we simply initialize it thus:

int SpiralArray [7][7];

This creates exactly what it looks like - an array called SpiralArray with 7 rows and 7 columns. In terms of our prime spiral, this will go up to the number

49.

There is one thing conceptually different about a multidimensional array when compared to a series of concentric squares, however - a multidimensional array

is a bunch of rows and columns (which in any other program might as well be called a table) whilst a series of concentric squares is, well, a bunch of

squares containing and being contained by each other.

Conceptually, it's a bit less meta to think of rows and columns...

So! Once the array is initialized, we can call it with any number of operators and do a bunch of stuff with whatever is in the array. Problem is, there is

nothing in the array yet.

There are two options to fill SpiralArray. One is manually, which will take a while. The other is programatically, which will take a while to WRITE, but is

MUCH more highly scalable.

Let's do it manually first, because it's actually really simple.

int SpiralArray [7][7] =
{
    {37, 36, 35, 34, 33, 32, 31},    //row 0
    {38, 17, 16, 15, 14, 13, 30 },    //row 1
    {39, 18, 5, 4, 3, 12, 29},    //row 2
    {40, 19, 6, 1, 2, 11, 28},    //row 3
    {41, 20, 7, 8, 9, 10, 27},    //row 4
    {42, 21, 22, 23, 24, 25, 26},    //row 5
    {43, 44, 45, 46, 47, 48, 49}    //row 6
};

Look at that very closely...it's the prime spiral, isn't it? Well, start at 1 in the middle, and spiral out. Looks like it to me!

Okay, so that was easy. It took a few minutes of typing, but now we have the array. We can do stuff with it, like print it or find out what's in a certain

location within it, or whatever people do with arrays.

But this is neither scalable nor efficient. Actually, it's borderline ridiculous. Having 49 numbers is one thing. That's up to s3 in our example above. (Note

that s1, s2, and s3 combined actually hold 48, but remember we decided s0 was the square with 1, so s0 through s3 = 49 numbers.)

Using this array we typed out, however, we can determine relationships between the numbers, since of course there ARE relationships and it IS predictable.

We should start with the number 1 to determine the numbers' relationships programatically. 1 is at the fourth spot in the third row, or in C++ terms:

int middle = SpiralArray[3][4];
cout >> middle;

That should print the number 1 to the console window.

Notice the straightforward syntax - NameOfArray[row][column] - which will get the value in the specified location (but only AFTER the array is set up!)

Now to figure out a relationship...

First, let's represent row and column as x and y, respectively. To best represent this, I'll have to re-write the way we initialize the array.

const int Rows = 7;
const int Columns = 7;

int SpiralArray [Rows][Columns]=
{
    {37, 36, 35, 34, 33, 32, 31},    //row 0
    {38, 17, 16, 15, 14, 13, 30 },    //row 1
    {39, 18, 5, 4, 3, 12, 29},    //row 2
    {40, 19, 6, 1, 2, 11, 28},    //row 3
    {41, 20, 7, 8, 9, 10, 27},    //row 4
    {42, 21, 22, 23, 24, 25, 26},    //row 5
    {43, 44, 45, 46, 47, 48, 49}    //row 6
};


for (int x= 0; x< Rows; x++)
    for (int y= 0; y< Columns; y++)
        cout << SpiralArray[x][y];

But wait, all that does is print the array. I thought we wanted to try filling it programatically.

So, let's try this instead. Remember that x is the row and y is the column.


const int Rows = 7;
const int Columns = 7;
int x = 3;
int y = 4;
int n = 1;

int SpiralArray [Rows][Columns];

    do {

SpiralArray[x][y] = n; // 1

y++;
n++;

SpiralArray[x][y] = n; // 2

x--;
n++;

SpiralArray[x][y] = n; // 3

y--;
n++;

SpiralArray[x][y] = n; // 4

y--;
n++;

SpiralArray[x][y] = n; // 5

x++;
n++;

SpiralArray[x][y] = n; // 6

x++;
n++;

SpiralArray[x][y] = n; // 7

y++;
n++;

SpiralArray[x][y] = n; // 8

y++;
n++;

SpiralArray[x][y] = n; // 9

       }

while (x < Rows, y < Columns);


for (x = 3; x< Rows; x++) {
    for (y = 4; y< Columns; y++){
        cout << SpiralArray[x][y];
}
}

There we go! We just made...well, one square of the spiral, anyway. Make this code snippet into a full (albeit tiny) program, and if should give us this:

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 5 4 3 0 0
0 0 6 1 2 0 0
0 0 7 8 9 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Looks promising, doesn't it? Well here's the thing. We can't simply implement that same function for each square, because each square contains progressively

more and more numbers.
That is, we're going to need to step forward, back, up, or down for more than just one row or column each time. In fact, the amount by which the steps would

need to increase is predictable.

This code snippet makes s0 and s1, which contain 1 and 8 numbers respectively. This is the only case in which the quantity of numbers differs by a number

other than 8.

The best way to go about this, actually, is to define helper functions for each step (a "step" is wherever we insert numbers into the array).

Also, we're going to switch rows and columns to y and x, respectively. If you think about a co-ordinate plane, this makes more sense.

We'll start with the transition from 1 to 2, which is a left-to-right movement, so we'll call it "StepRight".

void StepRight (int& column, int& value)
{
    column++;
    value++;
}

And to actually implement this, we'll have to call it thus:

StepForward(x,n);
SpiralArray[y][x] = n;

But we'll also be needing some other functions. For now, that's four in total:

StepRight= for left-to-right movement (x++)
StepLeft= for right-to-left movement (x--)
StepUp = for down-to-up movement (y++)
StepDown = for up-to-down movement (y--)

Because after all, a spiral of squares essentially moves in four increments of 90 degrees each.

Of course, the spiral WILL still come back to itself...we'll get to that.

So now, we can write the code like this:

const int Rows = 7;
const int Columns = 7;
int x = 4;
int y = 3;
int n = 1;

int SpiralArray [Rows][Columns];

    while (SpiralArray[y][x] != 0)
{

SpiralArray[y][x] = n; // 1

StepRight(x,n);
SpiralArray[y][x] = n; // 2

StepUp(y,n);
SpiralArray[y][x] = n; // 3

StepLeft(x,n);
SpiralArray[y][x] = n; // 4

StepLeft(x,n);
SpiralArray[y][x] = n; // 5

StepDown(y,n);
SpiralArray[y][x] = n; // 6

StepDown(y,n);
SpiralArray[y][x] = n; // 7

StepRight(x,n);
SpiralArray[y][x] = n; // 8

StepRight(x,n);
SpiralArray[y][x] = n; // 9

}

This should return the exact same thing we got before.

But that's still just s1. How do we fill s2, which has 16 numbers in it?

It doesn't make much sense to just keep writing Step* functions out. So, we use recursivity.

Making each square involves a certain amount of right, up, left, down, and right movement IN THAT ORDER. Looking back at the Excel spreadsheet, you notice

that each new square begins exactly one step to the right of where the previous one ended. This is a helpful consistency for sure.

s1 = Right 1, Up 2, Left 2, Down 2, Right 2

Because a square has corners, and we don't want to over-step them, the most it will ever step on a side is the length of the side minus one.

s2 = Right 1, Up 3, Left 4, Down 4, Right 4

Or in relative terms:

s(x) = Right 1, Up (side length - 2), Left (side length - 1), Down (side length - 1), Right (side length - 1)

Does that work? Let's just see.

s3 = Right 1, Up 5, Left 6, Down 6, Right 6

Hey! Yeah, it does work. Look back at the array we generated. The one with the 0s in it? Yeah - count around in a spiral and you'll see this formula does

indeed work.

But, how do we implement recursion like that?

One way is using "for" loops like this below. Let's pretend we are starting at 1, so the first StepRight() gets us to where 2 should be. Assume everything

else is already initialized as it is above.

int length = 3;
int pos = 0;
int GoUp = length - 2;
int GoLeft = length - 1;
int GoDown = length -1;
int GoRight = length -1;

for (length = 3; length < 14; length+=2)
        {

StepRight(x,n);

for (pos=0; pos < GoUp; pos++) // going up
    {

StepUp(y,n);
SpiralArray[y][x] = n;

    }

for (pos=0; pos < GoLeft; pos++) // going left
    {

StepLeft(x,n);
SpiralArray[y][x] = n;

    }

for (pos=0; pos < GoDown; pos++) // going down
    {

StepDown(y,n);
SpiralArray[y][x] = n;

    }

for (pos=0; pos < GoRight; pos++) // going right
    {

StepRight(x,n);
SpiralArray[y][x] = n;

    }
        }

This sure does look like it ought to draw a spiral...

But wait. Where does 1 go?

1 is strange. It's not really a square. If we are imagining this as a coordinate plane, 1 is more like a dot (or more accurately, a point).

When we decided that our biggest square would have a length of 7, we used (4,4) as our value of (y, x) - that is, row 4, column 4.

Notice anything about that? The numbers, specifically. That's right - 4 and 4 add up to 8, which is 7+1.

In more literal terms, the x and y (column and row) coordinates of 1 are always equal, and their values are half of the even number one greater than the

maxiumum side length.

This is no coincidence. It also happens to be the amount of numbers in the first square after 1, which is a coincidence and irrelevant to this program.

The length of each square is an odd number, and odd numbers have "middles." The "middle" is a number where there are an equal amount of numbers on each side.

Determining the middle of a number is simple. Also, it just so happens that the middle of the length of a side of a square here will be the column (or x

value) in which we will place 1.

We can do this thus:

int Rows, Columns, y, x, maxlength;
int n = 1;

cout << "Enter the maximum length of the biggest square..."
cin >> maxlength;

x = (maxlength + 1) / 2;
y = x;

Rows = maxlength;
Columns = maxlength;

int SpiralArray [Rows][Columns];

Let's say that instead of 7, you want to go up to s6, which is 13 numbers long. Where do we put 1? Well, at (7,7), right? So you put in 13 and it calculates

x to be (13+1) / 2, which is 7. Then, it sets y to the same thing. So when we start off the program, we do

SpiralArray[y][x] = n;

which puts n (1) at (7,7), or in row 7 column 7.

Consider this:

Max side length : 1 is at (y, x)

3 : (2,2)
5 : (3,3)
7 : (4,4)
9 : (5,5)
11 : (6,6)
13 : (7,7)
15 : (8,8)
17 : (9,9)
19 : (10,10)

The maximum side length, if you hadn't noticed, also dictates the dimensions of the array. It makes more sense to demonstrate with a smaller array/spiral, so

let's say you want the max square length to be only 3:

5 4 3
6 1 2
7 8 9

Oh, look, there's 1 at row 2 column 2. Extrapolate to a max side length of 5:

17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 24 25

Okay, the formatting is off, but you can easily tell that 1 is indeed at row 3 column 3.

It might not make logical sense, at first, to think that 10 is the "middle" of 19. Well, yes, it is:

1 2 3 4 5 6 7 8 9 >>10<< 11 12 13 14 15 16 17 18 19

Count the numbers on each side of 10. There are 9. 9 on each side. No, we do not start at 0. When do you ever start counting at 0? No one does that. You

don't start with nothing and suddenly have something. If you're trying to get somewhere quantifiable, you need to start somewhere quantifiable, or you're

basing your pursuit on nothing, which is going to get us nowhere.

Plus, if you start at 0, then even numbers have middles, and that would throw this whole program off, so don't do it.

We need to slow down for a moment here. What do we even HAVE thus far?

- a bunch of prerequisites and definitions
- an understanding of how multi-dimensional arrays work
- a way to create an array with as many rows and columns as you need (or want)
- a fairly good way to loop the spiraling function
- oh, and we also have functions to step up, left, down, and right as needed based on the length of the side

Numbers work in interesting ways. The fact that there is a relationship at all between the length of the side of the square and the amount we need to step in

any direction is remarkable.

We are well on our way to generating Ulam's Spiral in a C++ program!

Sunday, July 29, 2012

Ulam's Spiral Revisited

In a previous post, I compared Ulam's Spiral (below) to something I erroneously called the "fundamental theory of the universe."


I apologize for this. There is no such thing as the "fundamental theory of the universe." Besides, even if there was, it would more likely apply to physics than astronomy (think fundamental interaction i.e of particles).

No, indeed, it makes much more sense to compare the theory behind the Spiral to, perhaps, the second law of thermodynamics.

That, of course, states that an organized system tends to move towards disorder - or, in a word, entropy.

Let us entertain the idea that we can expand upon this long-established law of physical science with terminology used by Newton himself:

"An organized system tends to move towards disorder unless acted upon by an outside force."

But naturally, this does not apply to the Universe! The Universe is moving towards disorder not in spite of the forces acting upon it, but because of them!

This is where defining the intersection between number theory and astronomy becomes a bit tricky. Number theory, you see, is an invented science focusing on the study of numbers and how they behave.

It is rather strange, if you give it some thought, for "numbers" and "math" are simply things we humans invented and then imposed upon the natural world - seemingly, without a full understanding of how they really work. And yet, in the same breath, it can be argued that everything in science is simply a label to help us categorize and understand things about the natural world.

If we decided to start calling physics "scisyhp," nothing about the concepts that field studies or explains would change in the slightest. Similarly, if I said there are 1A trees in my backyard, that does not change how many trees are actually there (twenty-six).

With that said, let's return to Ulam's Spiral, a fascinating example of "strongly nonrandom behavior."

When Ulam drew his spiral, he noticed the diagonal lines that appeared almost entirely predictably. This is one of the things people cite to back up theories that the amount of prime numbers is infinite. In my previous post, however, I seemed to imply through comparison to the Milky Way that the distribution of stars in the Galaxy is "strongly nonrandom." and that, by extension of the Spiral theory, there are an infinite amount of stars.

For one, the amount of stars in the Galaxy is finite. Granted, there are billions upon billions, but it is still a measurable number. At the rate old stars die and new stars are born, it might be difficult to obtain an exact number, but it is certainly possible.

Additionally, the distribution of stars in the Galaxy is, in fact, strongly random. Herein lies another disconnect between Ulam's Spiral and the Galaxy - the Galaxy is a three-dimensional space, whilst the Spiral is not (although yes, technically both are indeed spirals). The positioning of a star s on an (x,y,z) co-ordinate space is random but influenced by a variety of things such as gravity and mass (which in turn affect each other). Star s affects the position of star t because of its mass, whilst both are affected by the black hole most educated people believe is the center of the Galaxy.

This means that you cannot expect to find a star at a certain location (x,y,z) relative to another location (x,y,z). In Ulam's Spiral, however, it is entirely possible provided you can figure out a trend line for one (or several) of the diagonal lines and, from there, predict a certain location (x,y) where a prime number p will fall with 95% confidence.

However...

Remember that "theory" I referenced? It is, in fact, a real theory, one which is widely accepted amongst scientists and educators. I will call it, for lack of a better name (or locatable Wikipedia article), the "No Special Place" theory. To refresh your memory, this is the belief that there is no "unique" or "special" place in space; that it's all pretty much about the same in terms of the "stuff" any given part of space contains. The only reason we see more in one part of the sky than another is because of things blocking our view in the atmosphere (particulates, humidity, light pollution) or far beyond us entirely (interstellar dust).

Why does this happen?

Assuming that it does happen, the reason there is "no unique place in space" is in fact due to entropy. Reason: nature is lazy. There is a reason trees grow straight up. When you blow a bubble, there is a reason it is always spherical. On that note, it's the same reason stars are always spherical. Things expand to fill a space evenly until some outside force prevents them from doing so - in this case, stars only stop growing because the energy they produce only allows them to expand to a certain point before they can no longer hold themselves together.

Thus, stars in a galaxy are distributed both randomly and non-randomly. Their initial positioning is decidedly non-random, since each influences another and all are influenced by something more powerful (i.e black holes). Within a certain region of space, however, a star's position given in terms of (x,y,z) is random, but predictable to a certain degree.

That is, in a cubic AU of space (if space was ever measured in cubic AUs), there should be x stars. This just makes sense considering the scientifically accepted theory that no place in space looks or is composed incredibly differently than any other place in space.

Humans did not invent stars, but we did invent numbers. Since this is by design a predictable system superimposed on the natural order of things, it does not innately abide by the laws of entropy - rather, it affirms them.

As one moves further and further from zero, there is less and less likelihood that a number n will be prime. However, consider the design of Ulam's Spiral - comparing it to the Universe, or at least the Galaxy, is still entirely feasible in this context. As it moves further from zero (the origin), there should be fewer primes as numbers increase in size, right? Yes and no. There is less likelihood that n will be prime as n increases in size, but this is compensated for (though not negated, given the patterns that form in the Spiral) by the fact that each 360-degree path past the origin contains progressively more and more numbers.

Basic probability states that with more values of n, the likelihood of n being prime remains about the same. Compare this to the theory that with 21 people in a room, it is likely two will have the same birthday,

Ulam's Spiral confirms the first statement - in fact, it seems to provide visual confirmation that n is nearly always prime at a certain point in the spiral!

Consider the picture below, on which I've imposed red lines (click to see the full resolution with the lines more visible).

Lines can be drawn practically anywhere, but the most pronounced are diagonal, vertical, and horizontal perpendicular lines, as well as diagonal parallel lines. Notice also the existence of tangential (and sometimes chordal) lines for each diagonal line.

There is too much of a pattern to be ignored. Numbers, although we made them up, do in fact represent real and quantifiable things.

Why would we invent a system to keep track of things, to maintain order in our world in a way we can understand, if that system was not predictable?

Granted, we do not fully understand the way "numbers" (especially prime numbers) work. This is why I write little prime-testing programs and why we have large-scale distributed-computing projects to find ones with millions and millions of digits.

Ulam's Spiral can theoretically be extrapolated to infinity. I don't know when that will happen, but I can guarantee you it will look like the picture above.

In the meantime, the great mathematical and analytical thinkers of our day are likely close to a breakthrough in prime number theory as more and more are discovered - each of which, as demonstrated above in two different formats, maintains the integrity of Ulam's Spiral and seems to point to a single ultimate conclusion - there are infinite primes...

Saturday, July 28, 2012

MuPuPriNT v0.2a

I suppose one could call these "nightly builds," since I wake up early and work on the program practically all day with breaks for meals.

28 hours ago, I uploaded v0.1a. Changes since then are surprisingly numerous, and range from bugfixes to long-planned features to spur-of-the-moment additions.

You can find the latest version here.

Changes include:
  • IsItPrime? and the Pythagorean tester no longer overflow, as they take a string (of up to 30,000 digits) as input instead of an unsigned long integer
  • Addition of a manifest file allowing implementation of Win7 visual styles
  • Tooltips in the main window (mainly for prototyping)
  • Added four useful buttons to the main window
  • Progress bars in every application within MuPuPriNT
  • Instructions dialog boxes now display the correct instructions!
  • The "Web" window now displays and works properly
  • Closing the "Web" window no longer quits the program, while pressing "Quit" actually does
  • Removal of unused and/or unnecessary buttons
  • Removal of a great deal of vestigial and/or redundant code*
  • Resizing of some windows to just generally look better.


It should be noted that the graphical goodies (better known as "Common Controls") are largely and for the most part simply for prototyping. This includes the links in the "Web" window, the progress bars, and the tooltips. The application and all of its components would function (and were functioning) perfectly fine without them.

I just decided to add them for several reasons. For one, I wanted to. Everyone likes progress, and everyone likes bars. For two, they actually do indicate progress - they will tick forward after each integer operation and each trial division.

However, since most of the computation time is calculating the big number itself, the progress bars won't really tell you anything about how well that's coming along. That's just because there's no way to call the SendMessage() function to tell the progress bar to STEPIT (no really, that's the message handle) while the program is computing, say, a Proth number. There is nowhere in the code to put that.

On a related note, I am still looking for ways to make the output files either write faster or write better (or both).

In my troubleshooting, I noticed that the files seem to get truncated only with small values of n (or, where applicable, k). Why is this? I can't figure it out! There is no good reason for that to happen, similar to the strange case where it inputs highwords (which we see as blank spaces) into the wide-character string (which is fine) and then prints them to the file (which is not fine). Working on it.

More on issue tracking to come. For now, enjoy the product of about 6 days' work!

Common Controls and Shell Functions


To elaborate further on my previous progress report, I'll go into detail about some of the problems I was facing and how I ultimately solved them. 

Now, perhaps you are wondering why I was so stressed about INITCOMMONCONTROLSEX not working. First off, I was a bit misleading. The all-caps version is a typedef. The function is InitCommonControlsEx - the capitalization here also makes it a lot harder to, uh, mis-read the last couple words...

Additionally, I was calling it twice - once with InitCommonControlsEx(&InitCtrlEx); and again with if (!InitCommonControlsEx(&InitCtrlEx)) { make an error message box} , the latter of which is actually unnecessary if you've already called the function.

It's the same as registering a window class. You don't need to call RegisterClassEx() if you have a conditional that simply tells the program what to do if a function doesn't work. With that in place, the program will say "Oh, well I can register the class, so why not? Saves me from throwing an error message. Moving right along..."

So, the step-by-step process to ensuring you can use common controls in your pure Win32 API VC application:
  • Locate ComCtl32.lib in C:\Program Files (x86)\Microsoft SDKs\Windows\v7.0A\Lib
  • Link to it. If you have made your own dependency directory, copy it to the lib folder and link to it in that directory.
  • Put #include <commctrl.h> in your main header or wherever your #includes are.
  • Right-click your Resource File and click Add Item... then New Item... and select XML file (it's towards the bottom)
  • Overwrite the contents of the new blank XML with this:  
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <assembly xmlns="urn:schemas-microsoft-com:asm.v1" manifestVersion="1.0">
  <assemblyIdentity
      version="1.0.0.0"
      processorArchitecture="*"
      name="CompanyName.ProductName.YourApplication"
      type="win32"
/>
  <description>Your application description here.</description>
  <dependency>
    <dependentAssembly>
      <assemblyIdentity
          type="win32"
          name="Microsoft.Windows.Common-Controls"
          version="6.0.0.0"
          processorArchitecture="*"
          publicKeyToken="6595b64144ccf1df"
          language="*"
        />
    </dependentAssembly>
  </dependency>
</assembly> 
  • Now, save that XML as YourApplicationName.exe.manifest. For instance, mine is called MuPuPriNT_1.exe.manifest.
  • Almost done. Put this in your main header (e.g stdafx.h):
#pragma comment(linker,"/manifestdependency:\"type='win32' name='Microsoft.Windows.Common-Controls' "\   
"version='6.0.0.0' processorArchitecture='*' publicKeyToken='6595b64144ccf1df' language='*'\"") 
  • Finally, we need to enable visual styles on a resource level. Close your resource file(s) if it is / they are open, then right-click on the .rc and click View Code. 
  • Put this at the beginning after #include resource.h:
CREATEPROCESS_MANIFEST_RESOURCE_ID RT_MANIFEST "the name of the manifest file you just created"


If this is all successful, you should find that your program now has correct Windows 7 visual styles. That means things like shiny buttons that glow when your cursor is over them, smooth lime-green progress bars, boxes etched more naturally, etc. Basically, the program will no longer look like it's running on Windows 2000.


I cannot take credit for this fix - I found it on MSDN, of all places - but I can at least try to explain it in a somewhat more easily understood fashion.


-



I also found something out about ShellExecute(). Besides that it is an incredibly useful and powerful function, I learned that calling it is a real pain in the brain unless (provided you are using Visual Studio 2010 like I am) you do exactly this:
  • Be sure that shell32.lib is included in your linker. There is no good reason why it shouldn't, as I'm fairly sure it is linked by default, but check anyway. 
  • If for whatever reason it's not, you'll find it in the same place we found ComCtl32.lib above.
Here's the tricky part I found out. Although ShellExecute() will only work with UNICODE programs, that wasn't an issue for me - the header it uses defines the function as ShellExecuteW(), whilst what the user implements has no W because the normal ShellExecute()function is defined as the wide-character version. Okay, cool. Why is that so tricky? It's not. All you need to gather from this is that if you are using ANSI encoding, you have to use ShellExecuteEx()

So, I mentioned a header, but didn't name it. The header you want is called shellapi.h, and it is worth noting that VC is not case-sensitive with the names of include files - for instance, in the Windows 7 SDK, it's called ShellAPI.h, but contains exactly the same stuff. 

The trick is that even if you #include it in your main header, even if you #include it after Windows.h, even if you #include it dead last...you will still get a C3061 compiler error - "ShellExecute is undefined."

WTF?! I linked the library, I included it in my header with all the other stuff, it's after Windows.h, it's spelled correctly...what do you want from me?!

Not that. Turns out, header files containing things like very specific function definitions are better off #included separately. At least, this is how I see it, since the program worked perfectly after I took ShellAPI.h out of stdafx.h and #included it at the beginning of my main cpp source file - so in this case, declarations in your big main cpp file ought to look like this:

#include "stdafx.h"
#include "resource.h"
#include "ShellAPI.h" 

I forgot the final bullet point, I guess.
  • #include the shellapi.h in the declarations at the beginning of your cpp source file, not in a precompiled header.

That was a frustrating start to the morning for sure...

Progress Report: Saturday 1445

I have made significant progress today.

Remember this to-do list from earlier this morning? Well, I re-formatted it!

 To do today:

  • Remove the remaining "useless" controls - that is, buttons that do nothing, edit boxes that display nothing, menu items with no pointers, etc
  • As a direct result, the GJSieve standalone will be updated to version 1.5.6
  • Determine why initializing common controls in MuPuPriNT fails
Specifically, I want to / am trying to:
  • create SysLink controls in a separate window that pops up when a certain menu item is selected
  • create a progress bar control that at least sort of tells you how much work is done
  • and none of this can be done without figuring out why INITCOMMONCONTROLSEX won't work

GJSieve will be updated shortly. The only thing holding me back is the lack of progress bar...

Back to work. But I'll just leave this screenshot here...looks a bit different, huh? Prettier, even.

Progress Report: Saturday, 0816

In the last two hours, I've accomplished:
  • created progress bar for Proth tester (implementation of GJSieve in MuPuPriNT)
  • corrected minor problems with filename inconsistencies
  • trimmed some useless code
  • fixed comments to actually reflect the code they're next to
Including last night, the following has been accomplished:
  • IsItPrime? is no longer limited by unsigned longs and instead takes its input as a string converted to an mpz_t variable,  thus allowing input of very large values of n
  • Same thing for the Pythagorean tester - also, n can be extremely large here because there is no power function called
  • Removed some useless buttons and re-sized the windows so they don't look awkward
  • Deleted about 500 lines of code used for debugging the window procedure about two weeks ago
 To do today:
  • Remove the remaining "useless" controls - that is, buttons that do nothing, edit boxes that display nothing, menu items with no pointers, etc
  • As a direct result, the GJSieve standalone will be updated to version 1.5.6
  • Determine why initializing common controls in MuPuPriNT fails
Specifically, I want to / am trying to:
  • create SysLink controls in a separate window that pops up when a certain menu item is selected
  • create a progress bar control that at least sort of tells you how much work is done
  • and none of this can be done without figuring out why INITCOMMONCONTROLSEX won't work
Stay tuned.

Friday, July 27, 2012

The Nature of the Unnatural

In mathematics, we have things called "natural" and "unnatural" numbers, "rational" and "irrational," "real" and "imaginary."

Number theorists, however, recognize one universal truth about all numbers - they are made up.

Numbers are just a system humans made up and imposed on the natural world. They are just something we use to label, categorize, and hopefully understand the natural order of things.

A long conversation several days ago led me to realize how lucky we are that mathematics and number theory is no Tower of Babel. The example I used went something like this:

-

The year is roughly 500 BCE, and in some bizarrely unprecedented historical event, people from all over the world are coming together to share their knowledge and collectively better the human race. A Greek mathematician, a Chinese scholar, and a Native American wise man find themselves standing next to each other observing the same landscape. The Greek says there are "tría" trees. The Chinese man shakes his head and says there are "san." The Native American looks a bit confused, and says something in a somewhat gutteral tone that no one understands.

These three people, of course, cannot understand each other. The Greek, being used to unintelligible foreigners, decides to demonstrate how he reached that conclusion. He points to each tree in turn, and as he points, verbally labels them: "Éna. Dýo. Tría." The Chinese scholar catches on, and does the same thing, saying instead "Yi, er, san." The Native American begins to understand that these strange, pale, and somewhat hairy people have developed systems identical to his own culture's method of keeping track of quantities of things. He grabs a stick and draws a pictogram in the dirt. The Chinese person smiles at this overly-complicated procedure, and draws three stacked parallel horizontal lines. The Greek's eyes light up when he sees this, and he in turn draws three tick marks (vertical), excitedly gesturing that his system is similar to the Chinese one.

An Egyptian comes and joins the three, noticing the Native American's pictogram. He takes the stick and draws a hieroglyphic character indicating the quantity of trees before them. The Greek is a bit confused as to why people would use art to represent such mundane things. The Chinese man thinks it overly complicated, but recalls that his culture once used pictographic characters (and remembers their writing system is in fact based on them). Gradually, all four begin to understand that whatever they wrote or said means the same thing.

Then an Arabic guy comes over, rolls his eyes, and writes "3."

-

At any rate, this "verbal labelling" is of course what we call "counting." Each of these hypothetical people come from completely different cultures that never interacted as they were developing, leading to their very different forms of communication. Some Native American cultures, for instance, did not exactly have a writing system, whilst their contemporaries in some parts of China felt they had too many. But at some point, they all realized they needed a way to keep records and indicate quantities, or else trade and record-keeping would be hopeless.

-

The Greek thought to himself: after all, despite being from different parts of the world, we all have only ten fingers. What if that dark-skinned man with long flowing hair wants eleven of something? Does he indicate that in a manner similar to the fellow with the narrow eyes?

The Chinese scholar sees a man who looks similar to himself, and rushes over, thinking that perhaps he would finally be able to talk to someone. But as he approaches, he instantly knows the man is Japanese - clearly, he had spent a good deal of time on a fishing boat, not a terraced farm. But the scholar remembers something he learned about Japan once, and instead of talking to the Japanese man, he deftly scratches some characters in the dirt.

The Japanese man thinks for a moment, then smiles and writes a few characters as well, though he is restricted by his language's limited use of Chinese characters. He asks the Chinese scholar how many trees are in that spot, and the Chinese man says "san." The Japanese man looks confused, and writes a character identical to the one the Chinese man had written, saying "mi."*

It dawns on the Chinese man that this is a bit odd, having a different way of saying the exact same thing. We even write it the same way! Curious, he writes a sequence of characters, saying them as he goes along. "Yi, er, san, si, wu, liu, qi, ba, jiu, shi." The Japanese man looks puzzled. Why does he say it like that? He picks up a stick and points to each of the Chinese characters, saying "hita, huto, mi, yo, itu, mu, nana, ya, kokono, towo."* 

The Arabic man was observing all of this smugly. Someday, these backwards Easterners will realize my people's system is far superior.

-

If a situation like this had actually arisen, there likely would have been a lot more frustration. The East Asians would all hang out with each other anyway, since with only a few exceptions, they can all recognize enough classical Chinese (or more accurately, Han) characters to communicate reasonably well. The Native Americans would be cautious of these strange pale people who seemed to claim "possession" of "their" strange systems of drawing series of lines and whatnot to represent quantities. The Greeks, however, would be fascinated by these different cultures and the ways in which they applied order to the world around them. The Romans would eavesdrop on the Greeks so they didn't have to come up with anything brand-new. The Egyptian wouldn't understand why these cultures were so proud of their "number" systems, since his culture used theirs to build monuments none of the others could dream of.

And if the Arabic guy was just sitting there laughing at the way these various people were writing numbers - come on, lines? pictures? - well, who could blame him?

-

The Martian watching these Earth-dwellers realized that despite not being able to understand each other, they at least recognized they were trying to express the same exact idea. He grabbed his holo-tablet and jotted some quick notes, writing a quick description of each Earth being (so vastly different depending on where they came from!), and then did his best to replicate each of the characters or pictograms they had written or drawn. What was it they were trying to say? Oh, right, the amount of trees! He counted them up and, at the top of the holo-page, wrote his version of what Earth beings hundreds, maybe thousands of years later would call "three." Well, that's more trees than we've got, at any rate.

--

* That's Old Japanese. Remember, I said this was around 500 BCE! The "ichi, ni, san..." system didn't come around til later. It's still different from Chinese, but they do use the exact same characters for numbers.

MuPuPriNT v0.1a

As promised, I have created a source package for MuPuPriNT and uploaded it here.

It's simply an archive of my VS2010 solution directory with all its dependencies.



I recommend checking out the ReadMe file included in this archive, but for information's sake, I will touch on some important points here as well.

Known issues:
  • IsItPrime? has essentially not been updated since March. It is still incapable of testing numbers larger than 2^32-1 due to signedness restrictions. I am looking into ways to get around this.
  • Results files in any program will still sometimes print text l i k e t h i s and/or cut off at a certain point (usually around the "formula" section. I do not know why beyond that it has something to do with character encoding (which is, by default, Unicode).
  • The "Save" button in GJSieve is deprecated. It still works, but will be phased out soon. It makes more sense to save as the formula.
  • There are some inconsistencies across programs. These are mainly cosmetic in nature and will be dealt with. They ought not affect normal usage.
Not issues, but rather not yet implemented:
  • Most menu items (still) do nothing. This includes everything on the View menu.
  • The NullCoding menu's only option will, upon being clicked, simply create a blank window. This window is meant to contain hyperlinks but I have not yet gotten that to work. 
  • More often than not, you get huge outputs that obviously do not fit in the boxes provided. These will be made scrollable in the future.
  • Progress indicators are forthcoming, but currently nonexistant
  • The buttons are really boring. For reasons I can't understand, they will not display the icons I am telling them to!
Not issues, but not ideal either:
  • If you actually look closely at the code, you will notice that edit controls are basically recycled throughout the program  - that is, they are defined once in the resource header and then used in pretty much the same way (or else only slightly differently) in each program instance. 
  • The only reason this could get confusing is because of naming - for instance, IDC_PROTH is the name of every formula display box, and IDC_CPU is (for some reason) the name of one of the status bars. 
  • Additionally, most handles, besides being (problematically?) consistent across programs, are left over from several weeks ago when development got off to a pretty slow and bumpy start. This is why some are called things like hEdit, hEdit2, hDlg, and hWndButton while others are called things like ndesc, bignum, and factors. Perhaps in the future these will be updated to reflect their true purposes, but for now it is not really a problem unless you are utterly unfamiliar with the code.
Another problem is that I do not fully know how to use the SysLink function. Remember, I use pure Win32 API with VC++, without MFC or ATL. This means MFC Link Controls are out of the question.

MSDN's documentation is, as usual, sparse and generally unhelpful. Their instructions for calling the InitCommonControlsEx function are also unhelpful, seeing as when I call it, I am told that I am, in fact, redefining it, as it is already called in CommCtrl.h and I assume that CommCtrl32.lib is automatically included. Am I wrong in thinking that?

Since everything else, including every single other control in the program, works perfectly,  I am blaming myself for making an amateur mistake somewhere along the lines. Then again, that's partially why I made this blog - so I can look back in the future and laugh at my relative lack of experience.

I have currently been teaching myself C/C++ for three weeks and the Win32 API for two weeks. How time flies!

MuPuPriNT

Expect an alpha version of the multi-tester application later this afternoon!

Thursday, July 26, 2012

Is GJSieve "efficient?"

While it is true that this application is being developed primarily as a means of teaching C/C++ and demonstrating the usefulness of the MPIR fork of the GMP library, it also serves as a valuable insight into various practices of number theory.

In a previous post, it was suggested that perhaps trial division with an array of prime numbers alone was not the best way to find factors of an integer. To expand on that, allow me to posit that trial division is itself an inefficient means of factorizing numbers, at least in the way in which it is currently implemented in programs like GJSieve.

Currently, a number N is trial-divided using:

std::vector ta<99999>;

In this vector, each value is set to the previous value + 1, starting at 2. Thus, the vector progresses:


2, 3, 4, 5, 6, 7, 8, 9, 10, <...> 100001, 100002

The program divides the number N by ta[u]= trial where u=1; u++ in a "for" conditional. This increases while the number from the vector, styled trial, is less than 100002. 


Therefore, rather than using an array of primes only, we simply use an array of whole numbers.


But doesn't this seem like overkill? What if a number such as 3 or 5 turns out to be a factor? Why test every other number after that? 

In order to prevent this unnecessary arithmetic, we implement the trial division function such that it stores the remainder in a variable and then immediately follow with checks to see if the remainder is exactly zero or not.

If the remainder is zero, then trial is a factor. There is also a check to see if the trial number is equal to N - for instance, when testing 13, the first factor it finds is 13.

This was an issue in version 1.5.0, wherein practically every number was "composite" because it was a factor of itself and the program did not differentiate as it should have. But if we implement something like 

if (trial == N && remainder == 0)

{

gmp_printf ("%Zd %s", N, "could be prime!);

}

then every number less than 100002 will be "prime!"

The solution is this:
  1. after a trial division, check to see if the remainder is zero
  2. if it is not, then move on to the next trial number
  3. if the remainder IS zero, check to see if it is equivalent to N
  4. if it is equivalent to N, go to step 8
  5. if it is not equivalent to N, display that it is a factor
  6. divide N by that number to determine the other factor
  7. display both factors provided they are both whole numbers that divide N. Break.
  8. if the trial number is equivalent to N, this means no other trial numbers were factors and N is likely to be prime. Break.
The break statement is key. This prevents unnecessary trial divisions. Namely, it prevents the program from trying to divide smaller numbers by larger numbers - for instance, you don't want to be dividing 791 by 1551. Even though 791 is prime, the program will calculate a remainder of 791 every time unless it stops at either the first factor found or the point where the trial number equals N.

There IS, however, a problem here. What if N is greater than 100002? 


In most cases, it is - sometimes, exponentially. This is where trial division becomes viewed as inefficient. It would be impractical (and, indeed, impossible) to have a dynamic vector that would test every number up to N, especially if N has several hundred thousand digits! That, and no number is ever factored by a number one or a few less than it - with a select couple exceptions (ie 2 factors 4).


As was also mentioned in the previous post, it is more efficient to divide up to the point where the trial number = sqrt(N). 

A feature like this is slated for implementation into GJSieve,  but will likely not appear for quite some time. There are numerous things to take into account, such as the fact that square roots are rarely whole numbers (and when they are, the number is very likely to be composite). Also, how does one dynamically grow an array or vector? Making a new one for each new N seems to make sense, but would probably end up using a lot of memory. 

This is all part of the deterministic process, though. We'll keep you updated!

JB

Tuesday, July 24, 2012

To trial divide, or not...? Ask the spiral!

Fundamentals of discrete mathematics state that any positive integer can be represented canonically, or in what's called "standard form," as the product of many small primes.

From this, we can easily draw the conclusion that almost all "large" numbers (with, shall we say, 5 or more digits) that are composite have an extremely high likelihood of having any of the following numbers as factors:

2, 3, 5, 7, 11, 13, 17, 19, 23

The array of primes above can be extrapolated ad infinitum, provided you subscribe to the Euclidean belief that there is not a finite amount of primes. However, as the leading edge gets higher, the likelihood of it being a factor decreases.

This is not because 47 is innately less likely to factor a number than is 23. Rather, it is because when using an array of known prime numbers to (attempt to) factor some integer n, the leading edge of that array increases until it approaches (or exceeds) the boundary sqrt(n).

Of course, the square root of some integer n is not always a whole number. In such cases, ought one round up or down? Let's say that we round down when the decimal digits are  >= .49 and up when they are =<.50.

Back to the premise of trial division - that the use of primes alone to factor n becomes less and less effective as one approaches sqrt(n).

Primes do not necessarily become "sparser" as numbers increase in size. Consider Ulam's Spiral.



Now, imagine that the "center" of the spiral is Earth, and each white dot is a star. From this perspective (at the origin, on the z axis, arbitrarily perpendicular to a 2D space), it would appear that all the "stars" are roughly evenly spaced, albeit sometimes clustered. Close inspection seems to suggest some kind of pattern, and despite being unable to describe the pattern, it is clear the positioning of these dots is not random.

Now, imagine that you are on "Earth" in the center of this spiral. Also, imagine there is no light pollution and the night sky is clear. What would you observe?

The answer varies, but one thing is for sure - you would not necessarily observe a pattern. In fact, you would see the night sky blanketed in stars such that no area of the sky looks discernably different from any other.

This is, in fact, the fundamental theory of the Universe - that there is no "unique" or "special" place in space, and all areas look about the same.

Does the space between stars actually get bigger as you move away from some arbitrary origin point? Of course not*. They just get harder to see - mainly because of interstellar dust, actually, not because they are "fainter."

How on earth does this relate to number theory?

Ulam's Spiral shows us that there is a predictable amount of primes in a given range of numbers. While there is no formula to determine this - yet - it is safe to say that if we were to expand this picture, subsequently added areas would contribute to the overall appearance of a spiral.

However - are there actually fewer primes in ranges of larger numbers? Will the spaces between white dots grow? Why do they seem "clustered" around the middle?

I can at least answer the last rhetorical there: There are fewer numbers around the middle! Remember how we said there is a predictable amount of primes in a given range of numbers? Well, in the spiral, a "range" of numbers is represented by a full 360-degree path around the middle. This path becomes longer and longer as you move away from the origin! Thus, the space between primes should grow...shouldn't it?

No, not necessarily! The amount of primes in a given range of numbers in the spiral actually seems to increase! Why? Because there are more numbers in that 360-degree path? Yes, that sounds logical. But is it provable fact?

No! Of course not. That's why number theory exists as a field of study! Number theorists strive to find rhyme and reason to prime numbers. We can only observe and speculate whilst they do so.

More on trial division to come!

-

JB 24 Jul 2012


*not to be confused with galaxies or galactic clusters, which are in fact speeding away from each other from what seems to be a roughly central point.

Future goals

GJSieve and GJSieveC/W
  • trial division array through sqrt(n)
  • more accurate progress indicators (ie "Working..." or a progress bar)
  • scrollable output boxes
  • working menu options!
IsItPrime
  • ability to input > (2^32)-1
  • working menu options!
MuPuPriNT
  • working menu options!
  • more interesting buttons
  • perhaps a new name

New blog!

Welcome to the NCPrime blog!

This is primarily here to keep track of progress and issues related to GJSieve and other NullCoding projects.

If you are here, I recommend you check out our project website, a central location where everything is posted.

However, typically only finished projects are posted there. Anything in-progress or not very stable will likely be posted or at least described here.

Thank you for your interest!