Factorization diagrams in Haskell

http://mathlesstraveled.com/2012/10/05/factorization-diagrams/

by Peteris • 14 years ago

103 19 14 years ago

ysc• 14 years ago

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." :)

cocoflunchy4• 14 years ago

Exactly!

walrus2• 14 years ago

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

walrus2• 14 years ago

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.

jrockway• 14 years ago

I like how you have to pretend you're sharing music when you just want to show the Internet the output of your mathematical computations. What a world.

Bakkot• 14 years ago

> 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• 14 years ago

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• 14 years ago

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• 14 years ago

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.

jonp• 14 years ago

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/

cocoflunchy4• 14 years ago

Arg! You beat me to it.

Almaviva2• 14 years ago

> var PI = 355 / 113;

You know about Math.PI?

smcl• 14 years ago

I'm curious about this line, too. I wonder if it's maybe just a wee joke

gwillen• 14 years ago

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.

cocoflunchy4• 14 years ago

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

tikhonj• 14 years ago

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

cocoflunchy4• 14 years ago

Thanks! I didn't know that.

the_cat_kittles• 14 years ago

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

Factorization diagrams in Haskell

Related Stories