Primes, area under the curve


One of the things that strikes me as being odd about prime and non-prime numbers is the concept of factors. That is, “a number is prime if it can only be evenly divided by itself and by 1”. Conversely, “a number is not prime if it can be evenly divided by any number other than 1 and itself”. So, if we take a non-prime number like six, it can be evenly divided by 1, 2, 3 and 6. The factors for “n=6”, not including 1 and 6 itself, are 2 and 3. Pretty elementary stuff, I know. But what does “2” and “3” represent here?

Y = 2 x 3

This is a rectangle that is 2 units tall by 3 units wide; or, 3 units tall by 2 units wide. In other words, “6” is the area under the curve for the equation y = 2, for x from 0 to 3; or y = 3, for x from 0 to 2.

If we took the integral of f(x) = 2, we’d get ∫f(x)dx = 2x.  If we solve for 2x = 6, then x = 3.

Again, mind-numbingly obvious. But, if ∫f(x)dx = 7, then x = 3.5. Since we only want solutions that give integer values, this equation gets rejected as having no solution.

For a slightly larger set of solutions, we could “solve” for ∫f(x)dx = 18.

If y = 2, then ∫f(x)dx = 2x. 18 = 2x gives us x = 9
y = 3, ∫f(x)dx = 3x, x = 6
y = 4, no solution
y = 5, no solution
y = 6, ∫f(x)dx = 6x, x = 3
y = 7, no solution
y = 8, no solution
y = 9, ∫f(x)dx = 9x, x = 2


y = 2, ∫f(x)dx -> x = 9

y = 3, ∫f(x)dx -> x = 6

y = 6, ∫f(x)dx -> x = 3

y = 9, ∫f(x)dx -> x = 2

This gives us 4 cases where we get integer values for a rectangle that has an area of 18.

y = 1, ∫f(x)dx -> x = 7

But, if we solve for ∫f(x)dx = 7, we just end up with unit rectangles. Either the rectangle is 7 x 1, or 1 x 7

y = 7, ∫f(x)dx -> x = 1

What’s funny is that if you look closer at the above cases for 18, you have one prime number (2 or 3) with multiple layers. It’s obvious visually that any rectangle that has a height other than 1 or that specific number is just some multiple of some other prime. Thus, what’s happening when you apply a sieve algorithm to some range of numbers is that you’re just adding another layer to the rectangle (3 x 1, 3 x 2, 3 x 3, 3 x 4, etc., for a rectangle with a width of 3).

I wish I knew where to take this. In a way, it’s the same as for the sinewave approach. If you sum the solutions for sines where sin(2*PI*i/N) = 0, for i = 2 to int(sqrt(N)), primes will have one solution and non-primes will have 2 or more. With the area approach, you’re summing the solutions for i * j = N, where i = 2 to N/2, and j = N / i (i and j are both positive integers). If there are no solutions, then N is prime. If there is at least 1 solution, then you have a non-unit rectangle of area N (same rectangle rotated 90 degrees) and the number is non-prime.

Primes only have unit rectangle solutions.

Same definition, different world.

Advertisements

Mind like a Sieve


Yes, ok, I like prime numbers. I admit it. So what?

One of the key features of prime numbers is their apparent randomness. Just because you know that one number ‘n’ is prime, doesn’t mean that you can predict that n+2 will also be prime, etc. And, given a 100-digit odd number, it’s going to take you a while to determine if it is prime or not. On the flip side though, non-prime numbers do follow specific patterns. That is, if you start out with n=2, every second number after that (4, 6, 8…) will be non-prime. And, starting with n=3, every third number will also be non-prime.

So, if you take a number at random, you can eventually determine if it is prime or not simply by dividing it by every value from 2 to n/2. Very straight-forward. Time-consuming, but straight-forward.

Now, if you want to speed things up, the patterns fall apart.

Say n=101. Sure, you could divide by 2 and see if there’s no remainder, then go to 3, 4, 5, 6, 7, 8, all the way up to 100. That wouldn’t make much sense, but you could. Instead, if you remove all the redundant numbers from the check list (4, 6, 8, 9, 10, 12, 14, 15, etc.), what does that leave you? Answer: With only the PRIME NUMBERS. Therefore, to find out if the non-primes have a pattern, we’re stuck with using apparently random values in the check list (2, 3, 5, 7, 11, etc.) On the other hand, with one more simplification, we can speed the test up.

101 / 2 = 50.5
101 / 3 = 33.67
101 / 5 = 20.2
101 / 7 = 14.4
101 / 11 = 9.2

Yup – we only need to use the prime numbers up to the one just before the square root of n. In this case, 2, 3, 5 and 7. (sqrt(101) = 10.05, and the largest prime less than 10 is 7.) If we were writing a program to do this for us, we could do something like: Look at ‘n’ and take its square root (‘sqr’). Find the first prime number smaller than sqr (pn0), and the next larger prime number (pn1). Square pn1 (pn1^2). And then say that for every number between n and pn1^2, use a prime number check list from 2 to pn0. When n equals pn1^2, pn0 = pn1, and pn1 is the next larger prime number.

Now, yes, I know that in normal cryptography and math applications there are much more elegant algorithms, and my approach isn’t practical, but I want ‘artsy’, not ‘craft’.

Anyway, a fun little pattern is to apply a sieve to all the numbers between 1 and 2 * 3 * 5. I hope it’ll become obvious why in a second.

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

(I like visualizing primes as sinewaves that have a half-period zero-crossing at that specific point on the x-axis. Any integer points that don’t already have one or more existing sinewaves crossing there will be prime and therefore will spawn a new sinewave. Here, we have sines for 2, 3 and 5.)

Assuming that in this loop 2, 3 and 5 have already been identified as prime and added to our check list manually, what we now have is a symmetrical string that we can pre-load into an array and say “any location that is crossed-out is non-prime and therefore we don’t have to test it. Substituting the above values with ‘T’ and ‘F’, we get (T=test for prime; F=Number is known to be non-prime):

TFFFFFTFFFTFTFFFTFTFFFTFFFFFTF

We could try making an array 2x3x5x7 elements long, but that’s 210 elements, and adding 7 as a factor only eliminates 7×7, 7×11, 7×13, 7×17, 7×19, 7×23, and 7×29, or 7 extra array element positions of the 210 from the calculations. Depending on how important speed is to the algorithm, this may or may not be worth the work.


(2, 3, 5 and 7, but only for n=0 to 30. Note the sudden lack of symmetry.)

In other words, if we use the above 30-element test loop, set n>5, and pre-load our prime number check list with 2, 3 and 5, we only need to test a number if the test loop position is “true” for that value, and keep repeating the loop as n increments. And we only test with the prime numbers between 2 and whichever one is smaller than the square root of n. Further, if we start with an odd value of n, and increment by 2, then we can remove 2 from our prime number checks. That is, to find all primes between 1 and 100, we only need to test the odd numbers between 7 and 99, using a check list of 3, 5 and 7 (7 gets added to our primes list because it’s prime, and to our check list once n exceeds 5×5 = 25.)

Yes, yes, very boring. So what?

Well, this finally brings me to my art application. I wanted to know which check list prime numbers are the most common lowest prime common denominators for the non-primes.

Example:

n = 2: prime
n = 3: prime
n = 4: lowest prime factor = 2
n = 5: prime
n = 6: lowest prime factor = 2
n = 7: prime
n = 8: lowest prime factor = 2
n = 9: lowest prime factor = 3
n = 10: lowest prime factor = 2
n = 11: prime
n = 12: lowest prime factor = 2
n = 13: prime
n = 14: lowest prime factor = 2
n = 15: lowest prime factor = 3

For the numbers between 1 and 15, 2 shows up as the lowest factor in the non-primes 6 times, and 3 shows up twice. The next higher prime is 5 and it doesn’t show up in the list in this example.

The question then became “what happens between 1 and 100,000?” How long is the check list, and how nonlinear is the distribution?

I surprised myself. The check list only consists of the first 65 prime numbers (from 2 to 313), and the log of the distribution is an ugly “s” shape. Nothing really earthshattering, but it did keep me off the streets for the couple of hours it took to write the code and make the graph in excel.

As a comment, the point behind using the lowest prime factor of n is to remove redundancies from the sieve algorithm. If you write out the numbers from 1 to 100, and then ‘x’ out every second number, you’re identifying 100/2 – 1 = 49 numbers as non-prime. When you ‘x’ out every third number, half of those have already been eliminated when x=2. Sure, 100/3 – 1 = 32 of the numbers are divisible by 3 and therefore are non-prime, but 6, 12, 18, 24, etc. were already identified as non-prime. Who cares if n=3 catches them again? It’s really only useful if x=3 catches 9, 15, 21, 27, etc., because these are the non-primes that x=2 missed. So, if x=2 catches 49 non-primes, x=3 catches (100/3 – 1)/2 = 16 more. x=5 only locates 6 more non-primes, and x=7 gets the last 3. That’s 74 total non-primes, leaving 25 primes (1 doesn’t count), and all 74 non-primes were caught by only 4 prime numbers (2, 3, 5 and 7).

I’m seriously considering writing a Java applet to animate the ‘s’ curve for n=1 to 100,000, but at 100,000 frames, that would be 55 minutes long. That might require a bit of editing…

==============

Shh… Don’t anybody tell me, but I went behind my back and returned to the sieves program to bump the test range from 100,000 to 1,000,000. To keep things simple, I’d written the original program in vsbasic (because it’s easy to use, fast to program in, and free) and did the tests by brute force rather than by using my above algorithm. With the first 100,000 numbers, the program run time was maybe 1-2 minutes, so optimization was unnecessary. But at 1,000,000 numbers, I cancelled out after unsuccessfully waiting several hours. Figuring that the algorithm was now justified, I spent about an hour implementing it. (I’m kind of rusty, and debug took most of my time.) It was worth the work, though, since I got the program run time down to under 20 seconds. For n = 1 to 1,000,000, the non-primes have the first 168 primes (largest is 997) as lowest prime factors. The graph shows the s-curve looking like a nice, clean “s”, too.

It’s still a silly waste of time, but it is a nice looking s.

 

Sieve of Eratosthenes Project


I like geometric art projects. I especially like playing with projects revolving around prime numbers. One of my favorites is the Sieve of Eratosthenes, which is a simple algorithm for finding prime numbers by crossing out every nth number. Proposed by Eratosthenes of Cyrene approx. 2200 years ago, the idea is that you write out the numbers that you’re interested in, from 1 to whatever (say, 100). First, pick n=2. put your pencil on the number 2, and start counting, crossing out every 2nd number (4, 6, 8, etc.) When you’re done, go back to 3, and cross out every 3rd number (6, 9, 12, 15, etc.) Keep doing this until you get to 11. Each number left uncrossed will be prime (2, 3, 5, 7, 11, etc.). You could speed the process up by only using n=prime numbers (2, 3, 5 and 7).


(Normal Sieve, for primes between 1 and 100, from left to right, top to bottom.)

Normally, people will lay the numbers out in a grid, generally a square, and number the grid points from left to right, top to bottom (as in the example in the wiki article). But, if you’re looking for patterns, this isn’t the best approach, because you can’t resize the grid to add more numbers without renumbering everything. And, the dimensions of your grid (10×50, or 14×35) impose an artificial factoring element that impacts the patterns you get (numbers not divisible by 5, or not divisible by 7). If you’re not sure what I mean, try making two Sieves, one 10×50 and one 14×35, in both number the grid points from 1 to whatever left to right, top to bottom, and compare the patterns for the prime number locations in each.


(Newton article spiral approach.)

Interestingly, the Japanese science magazine Newton had a feature article some months ago on the Riemann Hypothesis, and prime numbers in general, and one of their illustrations was a Sieve, created using the Matlab software, where the numbers were in a continuous spiral from the origin on an x-y graph. There were still no useful patterns, but the display space was now infinitely expandable – just add more graph paper. I decided I’d try something similar, but snaking back and forth only in the positive x-y quadrant.


(My approach.)

My project this time consisted of making a grid on a piece of matte board 36×36 squares, numbering the squares, and then applying the sieve algorithm with little pieces of colored construction paper. It took 3 days, several large sheets of paper and a full tube of wood glue to finish. Each pass of the sieve (n=2, 3, 5, 7, 11, etc.) is a different color paper, up to n= 19 or so, where it was easier to just repeat the colors. One pattern I was hoping would emerge is that certain numbers would get these big stacks of paper because they have so many factors in common with each other. But, even the heights of the stacks failed to produce interesting textures. Oh well.

Anyway, I stitched the photos of the matte board together in Movie Maker and added a sound track using the Rockit 8-bit synth. In part, one of the reasons for posting the project as a youtube video was to show off what you can do with the Rockit.

Youtube Video

USB Camera Webpage Updated


Finally, Gakken has updated the Otona no Kagaku site to include the files mentioned in the mook.


(Roppongi Hills miniature, from the Otona no Kagaku page. Image used here for review purposes only.)

The camera support page is here. It includes 4 youtube videos made by the guest artists highlighted in the magazine.  There’s a second page for downloading the texture maps for the Roppongi Hills miniature set.

Review: USB FX Camera


(Images from the Gakken website used for review purposes only.)

USB Special Effects Camera, 3,6750 yen ($37 USD).
Ok, this is a standard webcam that connects to your computer through the USB port. The only two things that are different about it are the close-up lens, and a short hand-held stick. One end of the stick has a tiltable camera mount, and the handle is threaded to screw onto standard-size camera tripod bolts. So, if you want to, you can attach the stick to your existing tripod for stability. Otherwise, all the real work of recording video, editing and adding effects will be done by whatever computer software you have. If you’re running Windows on a PC, you can download Movie Maker from Microsoft as a service pack, if you don’t already have a copy.

The kit consists of the camera premounted to the circuit board and pre-wired to the USB cable, the case shell halves, the handle, a couple washers and the mounting hardware. Suggested assembly time is 15 minutes and it took me about that long. I spent 5 minutes trying to bend and route the wires within the shell around the circuit board, and then constantly picking up the lens cap from the floor. The cap falls off too easily. The only tricky parts are in figuring out which screws to use. There’s one black narrow-head screw that attaches the handle to the shell case back. There are 3 silver screws for mounting the circuit board within the case, and 4 more black screws for attaching the shell case front to the shell back. The narrow head screw is the same length and thread as the other 4 black screws, so it’s easy to mix them up and use them interchangeably, it’s just that when you look at the finished camera from the front, one screw will be a different shape from the others. All the black screws are cheap metal and the heads strip if you’re not careful.


(With the camera mounted on a tripod, aimed at a set made up of images cut from the covers of the kit box.)

When you have the camera built, you can either download the AR software from Gakken (in which case you’ll also need something like lhaplus to uncompress it), or use Movie Maker or something. The Mook gives instructions for selecting the camera under 8 different applications, including Movie Maker, Photobooth, Quicktime Player, FaceTime and iMovie. The computer will automatically detect the camera and download and install the proper drivers. After that, just be sure you select the correct camera (it may either be “PC camera” or “webcam”)  from your devices list within your application. I tried using the Gakken AR software, but it keeps auto-selecting my laptop’s built-in camera and I can’t find any way to override that. Gakken doesn’t provide documentation for this app.


(The set seen from roughly the correct angle.)

The camera over-responds to changes in lighting conditions, and indoor fluorescent lighting turns everything blue-green. So, you’ll either want to use lens filters, incandescent lighting, or software editing tools. The lens is threaded. Screwing it inward changes it to pan focus; screwing the lens outward sets it to macro mode. Focusing is left up to you, based on the video you see displayed on your computer. The only caveat is to not fully remove the lens, which will expose the CCD to dust that will show up very easily in your movie.


(The figures, buildings and vehicles are glued to a long sheet of matte board. The backdrop is just a sheet of yellow construction paper cut in half and taped together. I didn’t have time to print up anything more interesting.)

The Otona no Kagaku site seems incomplete at the moment. The mook mentions several downloads, including texture maps of the buildings in the Roppongi Hills district in Tokyo, and some short movies made by the guest artists, none of which are available online yet, except for the main youtube ad). For the texture maps, you print them out on regular paper, cut the maps out and then paste them to styrofoam blocks cut to the right sizes. If you don’t want to go through that much work to make up a movie set, the front and back sides of the kit box are printed with flat 2D people and building facades you can cut out and prop up on a table. It took me about 4 hours to cut out all the images (buses, trucks, people, buildings) using a cutter knife, and I ended up using maybe only half of them on one sheet of matte board.


(One of the toys I picked up a couple years ago is a steam train engine that snaps onto a can coffee can. I needed a spacer to get the camera to stand level on the side of the coffee can, so I just used several folds of the cardboard packing that came with the kit, held together with electrical tape.)

The mook this time is pretty much 100% special effects photography. The lead article is an interview with Shinji Higuchi, who has worked on Gamera, Lorelei and a number of other movies. This is followed by a brief overview of FX history, including looks at Georges Melies, King Kong and the works of Godzilla and Ultraman master Eiji Tsuburaya. Cameraman Keiichi Sakurai demonstrates a few effects tricks with the kit camera, and several pages are dedicated to explaining the tricks further. There’s 6 pages on the making of an amateur flying turtle movie, 2 pages on making sound and exploding dirt effects, 2 pages on storyboarding, and 2 pages on different kinds of lenses that can be strapped in front of the camera with a special holder attachment. The next 10 pages are on videos made by the guest artists, a trip to an immense miniature electric train exhibit, and a guy that mounted a webcam into a plastic eyeball at the top of a tall hat (kind of a walking google maps camera thing.) The rest of the mook has instructions for making the kit, setting it up for different software apps, and finally the 12-page Science Manga strip by Yoshitoo Asari. The manga describes the camera tricks used in the Godzilla and Ultraman movies.


(It’s not literally a camera “truck”, but the principal is the same.)

The pictures in this mook are great if you’re looking for suggestions on how to make your own rubber suit movie, but because just about everything depends on the computer and software you have, the camera and holder stick are kind of redundant. You can get the same effect by buying a cheap webcam with a 6′ cable, cracking the case and mounting the camera on a wooden dowel. (In fact, the Gakken editors suggest using the kit camera as a webcam.) I do like a couple suggestions in the mook – 1) Put the camera in a clear waterproof ball (or toy submarine) and submerge it in your aquarium; 2) tape the camera onto the back of a miniature train flatbed car and run it up and down the train tracks for the kinds of camera shots you get at the Olympics. If you’re in Japan, this kit is worth getting if you really plan on making your own movies. Outside Japan, I’d say the import markups would make it overpriced for what you get. I’m really hoping the Otona no Kagaku site gets updated soon with the other video and texture map downloads.


(I still have almost half of the smaller images left over that didn’t seem needed within the above set.)

Youtube video

(For some reason, Windows Movie Maker only recorded in 320×200 pixel resolution, while the camera claims to be 2 megapixel.)

Next up, an auto-writing doll mechanism. No suggested price. Expected out sometime in January, 2014

Review: Manga Guide to Elementary Particle Physics


(All rights belong to their owners. Images used here for review purposes only.)

Let’s get the boring personal details out of the way quickly. I graduated from the University of Minnesota in 1983, with a BS in electrical engineering. I like physics, but it was one of the worst subjects for me in the entire 4-year program (astrophysics was completely over my head). I started out professionally as a quality engineer at an electronics manufacturer, but the company was dissolved as part of an M&A and I found better work as a software programmer. Most of my recent experience in electronics has been through the Gakken Otona no Kagaku line, and now the Fatman and Rockit kits. So, I’ve been feeling kind of nostalgic, as well as out of the loop, regarding anything involving integrals or differentials. I tried reading up on superstring theory on the net, but as long as it remains an unsupported theory, I don’t see the point in going into any detail on it. This kind of leaves me stuck, since I’m in a technological backwater in Kyushu and all the books I can find on most subjects are in Japanese. I’d love to get into American-style community college courses of some kind, but they don’t have those here.

Enter the recent announcement from Gakken, in email magazine #156 stating that they were publishing a new book, entitled The Manga Guide to Elementary Particle Physics, by Takuya Uruno. Yes, it’s in Japanese, but I figured that if there were lots of pictures, I’d have less kanji to wade through and whatever Japanese there was would be easier to understand. I picked up a copy for 1,155 yen ($12 USD) at the local bookstore, but the character designs of the adults and kids created to hang a story on to the science didn’t look all that good to me. The artist bio on the back page talked about Uruno being an established artist but didn’t list specific past titles. Doing a net search brought up a page on the Symmetry Magazine website, in English, with sample pages from Kasoku Kids, in English. Turns out that the communications director of the KEK accelerator approached Uruno to develop a manga series (Kasoku Kids) to teach particle physics to children, and those pages are what have been collected in the new book from Gakken. The article on the Symmetry Magazine website came out back in August, 2009, and the book covers the KEK website manga from 2008 to 2010, plus a special chapter on the Higgs Boson.


(The first few pages in the book are color photos of KEK. Here, we have an aerial view of the labs in Ibaraki Prefecture. This is followed by an overlay with the KEK accelerator, and several pictures of sections of the accelerator itself.)

I can’t find any additional hits on Kasoku Kids in English, beyond the Symmetry Magazine article, so I’m thinking that maybe only a few of the pages were translated specifically for that article. If you can prove me wrong, please send me a link so I can include it here.

The manga is essentially set up as an adventure series, with 4 school kids – Jin, Mega, Poni and Tama – visiting the KEK labs with two teachers – Takahashi and Fujimoto. Jin in particular is played for laughs, as the over-the-top gung-ho boy that understands nothing that the teachers tell him. Mega (short for Megane, or “eyeglasses”) likes SF, and can at least follow some of the explanations. Tama and Poni are along to flesh the group out. Maybe half of the book is just set-up for each new chapter, with the characters sitting around in a classroom arguing, setting out for the swimming pool, or joking with each other. Even so, that leaves about 100 pages for actual physics.

Here we have a sample page with the group at the pool, being told about gluons. There’s a lot of explanation, and none of the kanji has furigana (Japanese letters used to show how to pronounce the kanji). It’s pretty dense stuff for elementary school students, and may be targeted more toward a junior or senior high level audience. So, yeah, it’s harder for me to get through than I wanted. I’ve got to pretty much go through each sentence word by word to decipher the kanji before tackling the content of the sentences themselves. Meaning that I can’t give a full review of the science-side of the manga right now. Let’s just say that if you can find an English version of Kasoku Kids on the internet, I’d love to know about it.

But, the general pattern of each chapter is: The kids start out in some funny situation and start arguing with each other over a specific point that leads into that chapter’s topic. One of them (usually Jin) says something that triggers Prof. Fujimoto into giving a really dense explanation of the topic using technical terms which is all over the kids’ heads. Then, Prof. Takahashi steps in and rescues them by explaining each point in easier terms, with examples. So far, the only math is for the proof that E=mc^2. Everything else is just theory.