8 ms·
Factorization diagrams in Haskell
- ysc 14y agoZero 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 14y agoExactly!
- walrus 14y agoInstall 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 14y agoBy the way, here are the first 2263 diagrams: http://jumpshare.com/v/R7nRxZ?b=27itKy 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 14y agoI 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 14y 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 14y agoCould 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 14y agoI 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 14y agoIt 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 14y agoHere'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/ http://jsfiddle.net/FEKX2/3/
- cocoflunchy 14y agoArg! You beat me to it.
- Almaviva 14y ago> var PI = 355 / 113; You know about Math.PI?
- gwillen 14y agoI noticed the author speculating about color, so I colorized it based on the identity of the largest prime: http://jsfiddle.net/HEHHj/2/ 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.
- cocoflunchy 14y agoHere's my version: http://cocoflunchy.github.com/factorviewer/ http://cocoflunchy.github.com/factorviewer/ Not perfect at all... but it works.
- tikhonj 14y agoHey, you can change the default branch in the GitHub admin panel. There's a little drop down just under the repository name field.
- cocoflunchy 14y agoThanks! I didn't know that.
- the_cat_kittles 14y agoWonderful. I'm glad you did this, it was entertaining to read