Fun with primes

A 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.

Read moreFun with primes

I know I shouldn't be … but I am …

[update] a bug in my reasoning (thanks Peter!)
a Perl Golf addict. Not a recovering addict, but one that is active.
What is Perl Golf? Well, as in real golf, you try to provide the minimal number of steps to a solution. In this case, you are to solve the specific puzzle.
Detractors of Perl often make snarky comments about Perl’s equivalency to random line noise and other such nonesense. Sure … if it makes you feel good to say that … I am a fan of terse languages, I wrote programs (if you could call them that) in APL … a while ago. Its a strange sensation when you realize, looking at your code, that you can parse it … and run it … in your head. But I digress.
I ran across this one today.
The problem is:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

Most folks would start off with elegant looking loops, with well spaced and well named code and variables.
This is the antithesis of what you should do in golf and in Perl golf. Try this in the language of your choice.
Here’s my 5 minute version (call it s.pl):
map$s+=(!($_%3)+!($_%5))*$_,1..1E3;print$s
map$s+=(!($_%3)||!($_%5))*$_,1..1E3;print$s

[update] The “+” should be a logical or, otherwise we would double count numbers which are multiples of 15.
To run it
landman@lightning:~$ perl -l s.pl
267333
234168
In octave (Matlab work-alike) …
octave:12> 3*sum(1:333)+5*sum(1:200) 3*sum(1:333)+5*sum(1:200)-15*sum(1:1000/15)
ans = 267333

234168
Thats pretty cool.
Some of my other neat solutions was to solve the LED problem.
You run it like this:
./led.pl SOME_NUMBER
and it generates what looks like an ascii art version of the number. Like this:

landman@crunch-r:~$ ./led.pl 12345987
  # ### ### # # ### ### ### ###
  #   #   # # # #   # # # #   #
  # ### ### ### ### ### ###   #
  # #     #   #   #   # # #   #
  # ### ###   # ### ### ###   #
landman@crunch-r:~$ ./led.pl 21435687
###   # # # ### ### ### ### ###
  #   # # #   # #   #   # #   #
###   # ### ### ### ### ###   #
#     #   #   #   # # # # #   #
###   #   # ### ### ### ###   #

Neat … huh?
So how hard was this? Here’s the code that does it, and it can be improved upon, significantly.

Read moreI know I shouldn't be … but I am …