Factorization diagrams in Haskell

[jonp]

Here's a JavaScript/HTML5/Canvas version.

You can view the first 100 diagrams in a grid or view the diagram for the N of your choice. There's also an option to view an alternative diagram where the drawing starts with the smallest prime instead of the smallest.

http://jsfiddle.net/FEKX2/3/

[gwillen]

I noticed the author speculating about color, so I colorized it based on the identity of the largest prime:

http://jsfiddle.net/HEHHj/2/

It actually uses the last prime drawn, so it's only useful in 'smallest first' mode. That ought to be fixed, but I was lazy about it.

Colorizing the image based on the largest prime makes the pattern intelligible a little bit longer, before it becomes impossible to tell the big primes apart.

[Almaviva]

> var PI = 355 / 113;

You know about Math.PI?

[cocoflunchy]

Arg! You beat me to it.

[walrus]

Install dependencies:

  cabal install arithmoi
  cabal install diagrams

Copy all the code from the blog post into a file (let's call it factor.hs). At the end of that file, add:

  main = defaultMain $ factorDiagram YOUR_NUMBER

Then run:

  runhaskell factor.hs -o image.png -w 400

[walrus]

By the way, here are the first 2263 diagrams: http://jumpshare.com/v/R7nRxZ?b=27itKy. It's a renamed bzipped tar. Extract with:

  tar xjf factors.mp3

It extracts to a directory named 'factors' to about 30 mb total.

[Bakkot]

> Of course, this really only works well for numbers with prime factors drawn from the set {2, 3, 5, 7}.

So express the number as a sum of numbers with factors drawn from that set, and draw a several diagrams, one for each summand. A quick bit of Python confirms that every number under 14925 can be expressed as the sum of no more than three such numbers in the most obvious way possible (ie using a greedy algorithm).

For example, you might write 9999 as 9800 + 196 + 3, all of which have nice factorization diagrams.

[ggchappell]

Could it be that every positive integer is the sum of at most k such numbers, for some fixed k?

EDIT: No.

Proof. Fix a positive integer k. How many k-tuples of such numbers are there, whose sum is at most x? (For this to work, there would always need to be at least x of them.)

If (2^a_1 + 3^b_1 + 5^c_1 + 7^d_1) + ... + (2^a_k + 3^b_k + 5^c_k + 7^d_k) <= x, then all the exponents are at most log_2(x). So the number of all such sums is at most [log_2(x)]^(4k). And that is asymptotically less than x.

EDIT 2: But I'm sure the required k grows pretty slowly. This would be a workable technique for very large numbers indeed.

[grimboy]

I feel like expanding that set a little is really only a matter of picking a more distinctive arrangement than a circle. Like 11 would be more readable as 3 vertical lines of 4, then 3, then 4 again. Just varying the shape a little would go a long way towards making them more readable, and you could still fall back to a circle for larger primes.

[tzs]

It is not clear to me that writing 9999 as 9800 + 196 + 3 is useful, because I don't see any way to readily infer anything about the factorization of 9999 from the factorizations of 9800, 196, and 3.

[ysc]

Zero comments even though it's a nice read. I guess everyone suddenly got busy after reaching the paragraph "I wish I knew how to make a website where you could enter a number and have it show you the factorization diagram… maybe eventually." :)

[cocoflunchy]

Exactly!

[cocoflunchy]

Here's my version: http://cocoflunchy.github.com/factorviewer/ Not perfect at all... but it works.

[tikhonj]

Hey, you can change the default branch in the GitHub admin panel. There's a little drop down just under the repository name field.

[the_cat_kittles]

Wonderful. I'm glad you did this, it was entertaining to read