MasteringPhysics Error Fail

What the heck is a nit? Is it like a null? or a nat? Thank you masteringPhysics… your feedback is so helpful (nit ended up being a theta unit vector).

Simplicity of Complex Systems

When I was younger, I was always amazed at computers. I wanted to understand them in greater detail and know how they worked. At the time I was sure that they were immensely complex machines which would take me years of study to understand, and that the inner workings surely involved a certain component of mysterious black magic.

Now when I look at a computer, after working my way from learning Java to C, all the way down to assembly, memory management, pipelined processor design, and logic gates, there is little to no magic left. They are, in fact, incredibly simple. It’s almost disappointing to think back and realize such a mysterious thing was really so simple, yet on the other hand quite gratifying to have the understanding now.

Computers are composed of nothing more than logic gates stretched out to the horizon in a vast numerical irrigation system. — Stan Augarten

And the logic gates are nothing more than switches. Given enough time and enough spare parts I could probably come up with a basic microprocessor. Systems of great complexity can be build just from a few simple components. Perhaps that should not come as a surprise, since we ourselves are such a system, composed of cells, running off of sugars and proteins, which can be broken down into basic rules from physics and chemistry. Almost anything, perhaps even the universe itself, can be broken down it to simple rules and components.

Now, as I progress in my learning of linear algebra, calculus, and discrete mathematics I ponder if someday I’ll look back with an understanding of math like I did with computers. Right now, so much if it seems confusing, with a hint of magic and trust in the fact formulas work. Am I one by one peeling away the layers of complexity in search for some simple and discrete unit of mathematics? Does the answer really just lay in the integers?

Will I one day reach a point in some number theory class, while writing away at a proof, where I look back at my days frustratingly calculating things and think to myself, “it’s all so simple! Once you understand the basics”?

Project Euler Problem #15

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

First off, let me say I’ve never taken a combinatorics course, and before this problem had never seen the words “n choose k”. If you’ve taken a combinatorics course, you’ll probably figure out this problem in about 3 seconds, realizing it’s simply 40 choose 20 (which Google calculator will gladly output). Due to my lack of combinatorics, I was forced to take a very long route to get to the answer, but challenged myself a lot more in the process.

First off, I thought to myself, there must be some function f(n) for an n x n grid that will give me the result, and I just need to find it. In order to simplify things, I changed the grid to a set of equally spaced points in a plane. For a 2×2 grid, there would be 9 points (2+1)(2+1). Then I traced through the grid again, looking for some simple pattern. I quickly noticed that once you hit the bottom or right edge, you must go straight to the end point using a single path (along the edge). Otherwise, you have two choices (down or right). In my diagram below, I drew arrows on the points that I had a choice, and simply put a line through the points on the edges that had no choice. I also took note that for an n x n grid, there would be n movements in the right direction, n movements in the down direction, and 2n movements total.

I was also on the bus at the time, so no access to a computer, which explains the badly scribbled diagrams.

The only pattern I could deduce from this, is that because there is 2n number of moves, all of which n must be down and n must be right, I could do something like this.

Down = 0

Right = 1

Paths to end in my 2×2 grid (from left to right, top to bottom in the diagram): 1100, 1001, 1010, 0011, 0101, 0110.

Nifty, but how do I make an algorithm to actually create these numbers? I could simply check using a brute force method, generating all the binary numbers from 0 to 15, and then checking if they meet the requirements. To solve the problem though, I would need to generate all the numbers from 0 to 2^(40). That’s a lot of numbers to check. 1,099,511,627,776 of them to be exact. I found the result of the 3×3 grid by hand, through painful searching. There’s 20 of them, so I don’t bother to show the result. If anyone finds an easy algorithm to use this method, I’d be interested in seeing it.

As things were, I hadn’t gotten far, and decided to take another approach. After staring at 1’s and 0’s for so long, I was ready to stare at something more graphical, and decided to represent the 3×3 grid paths as a binary tree, in the back of my mind thinking I could use a linked list in C to actually make such a structure and maybe get somewhere. First off, I put all the points into an array (in my head anyway) so I could easily keep track of them. P11, P12, P13, P21, etc for labels. Then, for a down branch, go left on the tree, and for a right branch, go right.

Then I spent quite some time trying to make out patterns. First off, I began noting the paths from a point down to the bottom, which you can see in the small numbers on the lines and under the points. Then I noticed the tree diagrams for a 1×1 (red) and 2×2 (blue) grid were actually inside the 3×3 (green) grid. Nifty! Closer I thought I was, to finding a simple recursive function to find the answer I seek. Unfortunately, I couldn’t devise a simple function to generate the number of paths from the next tree diagram. Then, it came to me, looking at the path lengths.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

20

Eureka! It’s Pascal’s  triangle up-side-down! The result I seek for a n x n grid is the middle number of the 2*n’th row of pascal’s triangle. Not only that, but this is also the sum of the terms squared of the n’th row (one of many odd patterns in the triangle). Finally all I had to do was write a program to calculate the first 20 lines of Pascal’s triangle, and then square the terms of that last row and add them together.

to calculate the triangle,

#include 

#define ROWS 21
#define COLS 21

int main() {
        int triangle[ROWS][COLS];
        int i, j;

        for (i = 0; i < ROWS; i++) {
                for (j = 0; j <= i; j++) {
                        triangle[i][j] = 0;
                        if (i == j || j == 0) {
                                triangle[i][j] = 1;
                        } else {
                                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
                        }
                        printf("%d ", triangle[i][j]);
                }
                printf("\n");
        }
}

Resulting in,

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1
1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1
1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1
1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1

Taking all the elements of the last row, squaring them, and adding them,

1^2 + 20^2 + 190^2…. = 137,846,528,820 paths to the end in a 20×20 grid. That’s a lot of paths, I’m glad I didn’t have to resort to a pure brute force approach, it would have taken quite a long time.

Project Euler

I’ve recently come across a nifty page known as Project Euler. It’s filled with over 230 math related programming problems to solve. Don’t worry if your math is rusty, most of the problems can be brute forced easily enough, but knowing some math can certainly help make your programs faster. Trying to find all the divisors of a number for example, will crawl to a halt when you get to large numbers, but there’s a shortcut to find the result of the divisor function just by the prime factorization of a number. This will help solve one of the problems in about .8 seconds instead of about 20 minutes of computation.

Most of my solutions are very hacked together and brute force, but they work well enough. I’ve been focusing more on solving each problem quickly and correctly, rather than coming up with the best code, resulting in a lot of code that falls into the burn after compiling catagory. I’ve been doing most of them in C, but some I’ve resorted to Java and other languages to make things easier, or to reuse code (there’s one challenge to write a program to solve Su Doku puzzles, something I wrote in Java and mentioned here).

If I come up with a particularly ingenious solution to one of them I might post it here. I’m current finishing up the 14th problem (doing them mostly in order).

A Programmer’s Quest for Primes: Part 4 – Special Primes

Continuing my playing with primes, I’m now up to having 1 billion of them sitting on my hard drive. That’s 11GB in a text file. It’s actually spread out between 10 files in 100 million prime blocks to load in an out of RAM easier. They were generated in only 30 minutes using the Sieve of Eratosthenes and a modified version of the prime program found here, http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm.

In this post I went through my files finding some statistics on special primes. The graphs below have groups of 1 million primes on the x-axis, and the number of special primes found within that 1 million on the y-axis.

Twin primes: prime numbers that differ by two. For example, 17 and 19. There are theories that there are an infinite number of twin primes, but looking at it as a limit as the function approaches infinity, it certainly looks like it goes to 0, if very slowly. In the first 1 billion primes, there are 58,047,180 twin primes (according to my program’s results at least), or about 5.8% of the total.

Cousin primes: prime numbers that differ by four. Interestingly, according to some number theory equations called the Hardy–Littlewood conjecture, they are supposed to have about the same distribution as twin primes. My results show it’s quite close, 58,040,262 of them in the first billion primes. The graph is about the same.

Sexy primes: no, I didn’t come up with the name, the Latin word for 6 is sex, and the math people love to name things in Latin and use Greek symbols. Primes that differ by 6. There are 105,002,853 of them in the first billion, quite a bit more than twin or cousin primes.

Answer primes: pairs of primes that differ by 42. Okay, I did make this one up. Any scifi fans out there will see the reference. There are 22,729,810 of them in the first billion primes. The graph is at least more interesting than the others due to the fact it’s a larger number. The distance between primes increases as the primes gets bigger.

Some random facts of interest (to weird people like me anyway).

The longest distance between two primes out of the first billion (consecutive composite integers): 394. There are no prime numbers between 22367084959 and 22367085353. If you split the 1 billion primes into blocks of 1 hundred million, and then find the longest runs of composite integers in each block,

292 between 1453168141 and 1453168433
336 between 3842610773 and 3842611109
354 between 4302407359 and 4302407713
340 between 8605261447 and 8605261787
382 between 10726904659 and 10726905041
354 between 11705477863 and 11705478217
346 between 14066075347 and 14066075693
376 between 16161669787 and 16161670163
372 between 20404137779 and 20404138151
394 between 22367084959 and 22367085353

Since the distance on average between primes increases as you get bigger, you’d think the max distance would increase more clearly. Such is one of the mysteries of the primes.

A Programmer’s Quest for Primes: Part 3 – Prime Distribution

While playing around with primes and C some more, I put together some plots with Mathematica dealing with the distance between primes. The prime numbers are plotted, with the n’th prime on the x-axis and the difference between it and the last prime on the y-axis. After all, I’ve got gigabytes of primes sitting around.. got to figure out something to do with them other than test my RAM while generating them.

The first 1,000 primes,

Of course, primes can’t be odd numbers apart, because that would make them even. That explains the pattern a bit. Still, for something that has baffled mathematicians for centuries, it certainly does seem like there’s a pattern to it. If you draw lines between the points,

Certainly not as pretty.

The first 10,000 primes,

The scale makes this one a bit less interesting. Too much overlap, but Mathematica really doesn’t like big listplots like this. I even crashed it a few times when I tried to do a listplot of 100,000 data plots. 10,000 was pushing it.

A random sampling of 1,000 primes (between the 90 millionth and 90 million 1 thousandth prime),

More interesting patterns in primes, the Ulam spiral. Starting at 1 and spiraling outwords from the orgin, you create a graph like so (http://en.wikipedia.org/wiki/Ulam_spiral),

And then remove all but the primes (http://en.wikipedia.org/wiki/File:Ulam-Spirale2.png),

And you find an intersting pattern, that the prime numbers tend to lay along some diagnols more oftan than others. Expanding this to 150,000 primes,

A Programmer’s Quest for Primes: Part 2 – Sieve of Eratosthenes

This is part 2 of my quest to calculate prime numbers using small and efficient programs written in C. In the first part I wrote a program to brute force find primes by testing sequential numbers to see if they were divisible by any other prime numbers found before, and making the process a bit faster by only checking odd numbers and stopping when I reach a prime greater than the square root of the number in question.

For my second prime calculating program I make use of an algorithm developed 2,200 years ago by the Greek mathematician Eratosthenes. A friend once told me all the great computer science ideas were developed 20 years ago. I often tend to think it was further back than that. Division and modulus commands are very costly in terms of CPU cycles. Multiplication and addition are much faster. Rather than checking to see if a number is prime by dividing it by all prime numbers found before it, it’s much faster to multiply the prime numbers to find all the composites, and then mark anything remaining as prime.

A bit array would be the ideal data structure for this algorithm, but because C doesn’t have a bit array structure built in. The only other option is use the bool datatype (C99) or an unsigned char (ANSI), but either way you’re wasting 7 bits of memory for each element (you only need one bit). While searching for bit arrays in C I found another programmer’s quest for calculating prime numbers here, http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm.

Rather than reinventing the wheel I just finished up my much simpler version using char arrays to find the first 100 million primes. The code can be found here, http://pherricoxide.jumbofx.com/code/eratosthenesprimecalc.c. After this point it starts running out of RAM though, so to find more primes you’ll have to use a paging or cluster method as coded in the last link.

Using the brute force program it took over 2 hours to compute the first 100 million primes.

Using this method, it took less than 7 minutes. Quite a difference to say the least. The only downside is that this algorithm uses much more RAM.

A Programmer’s Quest for Primes: Part 1 – Brute Force

While trying to come up with something to program, I looked to prime numbers in my discrete math class and decided to make a simpler prime number calculator. The deeper I delve into the world of prime numbers the more interested I become. The building blocks of all numbers with plentiful applications in cryptography have captured my spare time recently. This is part 1 of my quest for calculating prime numbers. I have no real goal in this quest, other than to expand my knowledge of mathematics and sharpen my skills of programming; it’s the journey that matters, not the destination.

First off some math. What is a prime number?

Prime Number: A positive integer p greater than 1 is called prime if the only positive factors of p are 1 and p. A positive integer that is not prime is called composite.

For example, 42 is not prime, it can be written as the product of the factors 2 and 28. 28 isn’t prime either, it can be written as 2*14. 14 can be written as 2*7. What can 7 be written as? or 2? Nothing, these are primes. Now a useful theorem.

Fundamental Theorem of Arithmetic: every positive integer greater than 1 can be written uniquely as a prime or as a product of two or more primes.

That means 42 can be written as 2*2*2*7, all of which are prime numbers. 105 can be written as 3*5*7, all prime.

Now, how can you tell of a number is prime? Well, if the number is composite, that means it can be divided by some prime number. You can keep a list of prime numbers and then try and divide that number by them all. If it doesn’t divide by any prime numbers, it’s prime itself. For example, we find a list of prime numbers: 2, 3, 5, 7, 11. Now suppose we want to see if the number 13 is prime. We’d do the following,

13 % 2 == 0? If so prime.

13 % 3 == 0? If so prime.

13 % 5 == 0? If so prime.

13 % 7 == 0? If so prime.

13 % 11 == 0? If so prime.

None of these numbers can divide 13, so 13 is prime. When we get into prime numbers like 576,194,557 though, this process will be doing millions of checks on the prime numbers found before, which will be horribly slow.

A quick way to make a huge speed difference is use another handy theorem.

Theorem: If n is a positive composite integer, then n has a prime divisor less than or equal to sqrt(n).

So rather than checking if 576,194,557 is divisible by each prime found before it, we can just check if it’s divisible by any of the primes less than or equal to 24,004.

Before getting down to the programming, one more quick way to make it more efficient is to count by 2’s, since we know all prime numbers are odd. In fact, prime numbers always end in either 1, 3, 7, or 9. Increasing the number you’re checking for primeness by 2 every time can eliminate checking anything that ends with 0, 2, 4, 6, or 8.

Therefore,  a simple brute force method for finding primes: create an array (in the heap, because the stack will overflow), and store all the primes you find in it. Increase your candidate number by 2, try to divide it by all the primes in the list, and break out of the loop if you find a number that divides it or if you reach a prime larger than sqrt(candidate). The latter means it’s composite and the former means it’s prime. Keep doing this until you find as many primes as you like. My source code for such a program written in ANSI C can be found here, http://pherricoxide.jumbofx.com/code/simpleprimecalc.c. It’s well commented and should compile with any ANSI C compiler. This is the first of hopefully several prime calculators I’m going to write.

Using this program on a 1.4ghz Intel Core 2 Duo with 2GB RAM, the first 100 million primes are found in about 137 minutes.

The problem is, as the numbers get bigger, this program runs slower and slower. The graph below shows time plotted on the horizontal axis and number of primes found plotted on the vertical. You rapidly find primes in the beginning, but after a while it will inevitably take you long minutes just to find a few primes. Using this method, we hardly have to worry about running out of RAM, because by the time we get 2GB of data (around 200 million primes), the process will be going so slowly it will hardly be worth continuing the search, at least using this brute force method.

Stay tuned for faster prime calculations with better code, better algorithms, and someday perhaps even some cluster computing, as I continue my quest for primes. Until then, here are some prime numbers to spot check your own prime calculating programs with.

1 millionth prime: 15,485,863 (found in 7 seconds)

5 millionth prime: 86,028,121 (found in 112 seconds)

10 millionth prime: 179424673 (found in 5 minutes)

20 millionth prime: 373,587,883 (found in 12 minutes)

30 millionth prime: 573,259,391

40 millionth prime: 776,531,401

50 millionth prime: 982,451,653 (found in 50 minutes)

60 millionth prime: 1,190,494,759

70 millionth prime: 1,400,305,337

80 millionth prime: 1,611,623,773

90 millionth prime: 1,824,261,409

100 millionth prime: 2,038,074,743 (found in 137 minutes)

Most Annoying Webwork Problem…

If you’ve ever had to use Webwork, you know how much of a pain it can be. For those who haven’t, it’s an online math homework program ASU likes to make use of (especially lately to save on the cost of paying graders).

On one hand, they usually let you have an unlimited number of attempts to do the problem, so you have no excuse not to get a 100% on the homework. On the other hand, it can sometimes be quite annoying. The most annoying webwork problem I’ve done today,

The temperature at a point (x,y,z) is given by , where is measured in degrees celcius and x,y, and z in meters. What is the maximum rate of increase of at (-1, 1, 2)?

This isn’t a hard to do problem, but the answer is.. well.. I’ll just show it to you.

(400e^(-61/36))^2 / sqrt((400e^(-61/36))^2 + (100e^(-61/36))^2 +(200*4/9*e^(-61/36))^2) + (-100e^(-61/36))^2 / sqrt((400e^(-61/36))^2 + (100e^(-61/36))^2 +(200*4/9*e^(-61/36))^2) + ( -4/9*200e^(-61/36))^2 / sqrt((400e^(-61/36))^2 + (100e^(-61/36))^2 +(200*4/9*e^(-61/36))^2)

Or in prettier form,

I had to submit it 3 times just to get it to stop telling me I had mismatching parenthesis… And this was only one part of a 5 part problem, all with similarly long and ugly answers.

Pondering on the Teaching of Mathematics

As I sit here working on calc III homework, I come to the realization once again that I really have no idea what I’m doing.

On one hand, I know exactly what I’m doing. I’m taking double integrals, finding Lagrange multipliers, and finding partial directional derivatives. I can tell you what these terms mean, which make any non-engineering or math major cringe, easily enough. They’re volumes under surfaces, a handy way to find max/mins, and lines tangent to surfaces in a direction. They’re actually not even hard to do, it’s just all the stuff you learned (or learned and forgot often in my case) in calc I and calc II applied to R^3 space.

On the other hand, I have no idea what I’m doing. How would I ever use this in the real world? Just trying to figure out an application is difficult. Don’t start attacking me saying there’s applications for this kind of math all over the place, because I’m trying to believe you, I really am. I just haven’t been taught any of them. Say I have a function f(x, y), and then I want to see how the function changes with respect to x only. Okay, sure, just take a partial derivative. Why would I want to find how the function changes at an angle of 42 degrees from a point though? For that matter, where do these functions come from? How do I model real world applications into the form f(x, y) so I can easily do my calc on them? If you look at the Wikipedia article for a hyperbolic paraboloid, there’s 4 sections of it’s properties and how to do stuff with it, and a footnote at the bottom saying “applications: directional antennas and receivers, such as satellite dishes, telescope mirrors, and directional microphones are paraboloids.” Nifty, why don’t they ever give me cool application problems dealing with directional antennas?

If I get a job in engineering or math, I don’t think my boss is going to come up to me and say, “hey, go find the first and second order derivatives of .” First off, I can plug that into Mathematica and get the answer in a few dozen clock cycles, faster than I can even write the first derivative with respect to x. For that matter, faster than I can write the letter ‘x’.

The really sad part is, I’m in “applied” linear algebra and calculus “for engineers”. That means somewhere at ASU there’s a bunch of math majors even more clueless about the applications of what they’re doing, even if they can prove by contradiction that their numbers are at least logically derived.

If I ever became a math professor, this is what I’d do. First off, instead of spending the first class introducing myself and the syllabus, I’d spend it introducing the subject. I’m 4 weeks into discrete math right now and I still have no idea what discrete math really is. It seems like a hodgepodge of topics and mainly a class to teach proofs in, which seems a bit pointless since the teacher said a good 50% of the material overlaps with the class I’m taking next semester on proofs. Don’t go into details about how to do anything, just talk about the general idea of the stuff. If teaching calc I, explain what derivatives and integrals are from a geometric viewpoint. Explain a few basic uses of them as well. Don’t just jump into the limit definition.

Then, when you get into the material, first play around with some problems and applications before you dive into a proof of some formula that takes half the class. This would at least show the students where you’re going during your proof. More often than not I watch my teachers manipulate expressions for 5 minutes, coming up with an obscure formula, then explaining what the formula actually does. If I’m really lucky, they’ll even explain what it means after that.

Finally, once you know the formula, where it came from, and what it does, do real world problems. If almost all the problems are related to physics, maybe physics and math should be combined into one class. It seems like physics classes just apply formulas to problems, and math classes just make up formulas without showing any problems. It’s hard to deny that a large part, maybe even the majority of uses for calculous involve physics. Of course the classes would move slower, but what’s wrong with spending more semesters if you’re combining two classes?