Fun with primes
By joe
- 3 minutes read - 538 wordsA long time ago, in a galaxy far … far … away … I’ve been playing with primes for a while … computing them, etc. Have a neat way to represent any natural number (exluding 0) in terms of the exponents of their prime factors. Lots of reasons for playing with this. Started doing this before joining SGI … many moons ago, and used it as a way to entertain myself on airplanes when the laptop battery ran out. For some reason, I do my best coding 10km above the planetary surface. I haven’t worked on this in a while, and I just couldn’t motivate myself to do some other stuff, so I figured I’d take a break and rework this. I had coded it in … fortran (yeah, really). So I reworked it into a little C, and have it set up so I can drive this from scripts to gather the data. Ok, the notation in short (I don’t know if this is a common notation, I came up with it many years ago, and hopefully I re-invented someone elses wheel): Let φi be the ith prime. Then any natural number N (excluding 0) may be written as ∏(i=1 .. ∞)φie(i). Prime numbers will have the e(i) as zeros everywhere apart from a single e(n)=1 on the nth prime exponent. And composite numbers will have patterns of 1 or greater on the exponents. There are actually lots of cool things you can do with this notation, and I’ve got a few pages of notes and proofs somewhere in my basement of sum of 2 evens being even, sum of two odds being even, sum of even and odd being odd, and the interleaving of even and odd numbers. Yeah, I am a closet mathematician. Complete amateur at best. But having fun with it. So I just finished converting the old fortran code to C, and checking it. Using the above definition, and simply printing the exponents, here are the numbers from 1 to 10 (understanding that unprinted exponents after the last 1 or greater are zero).
- 1 -> 0
- 2 -> 1
- 3 -> 0 1
- 4 -> 2
- 5 -> 0 0 1
- 6 -> 1 1
- 7 -> 0 0 0 1
- 8 -> 3
- 9 -> 0 2
- 10 -> 1 0 1
Whats cool is you can see some very interesting patterns emerge.
landman@pegasus:~/play/factors$ ./factor.exe 1
landman@pegasus:~/play/factors$ ./factor.exe 10
1 0 1
landman@pegasus:~/play/factors$ ./factor.exe 100
2 0 2
landman@pegasus:~/play/factors$ ./factor.exe 1000
3 0 3
landman@pegasus:~/play/factors$ ./factor.exe 10000
4 0 4
landman@pegasus:~/play/factors$ ./factor.exe 100000
5 0 5
landman@pegasus:~/play/factors$ ./factor.exe 1000000
6 0 6
landman@pegasus:~/play/factors$ ./factor.exe 10000000
7 0 7
landman@pegasus:~/play/factors$ ./factor.exe 100000000
8 0 8
landman@pegasus:~/play/factors$ ./factor.exe 1000000000
9 0 9
This pattern makes perfect sense, as 100 = 1010, so your prime factors (2 * 5) are squared … 22 * 30 * 52. And 1000=1010*10 or 103 or 23 * 30 * 53. And so on. Right now, I am using ints throughout, though it is trivial to convert it to longs. And I could probably pretty easily convert it to the gmp (multiprecision) package. Anyway, its fun code for the moment, and I want to play with it some more.