{"id":538,"date":"2018-01-11T08:47:44","date_gmt":"2018-01-11T08:47:44","guid":{"rendered":"http:\/\/perfectionatic.org\/?p=538"},"modified":"2018-01-11T10:59:05","modified_gmt":"2018-01-11T10:59:05","slug":"factorizations-to-get-a-very-special-number","status":"publish","type":"post","link":"https:\/\/perfectionatic.org\/?p=538","title":{"rendered":"Factorizations to get a very special number"},"content":{"rendered":"<p>Mathematical recreation is fun. I came across a nice Mind your Decisions video and thought it would be cool to use <code>Julia<\/code> to find that special number. Have a look at the video here before we continue<br \/>\n<iframe loading=\"lazy\" title=\"Why Mathematicians Love 69,720,375,229,712,477,164,533,808,935,312,303,556,800\" width=\"740\" height=\"416\" src=\"https:\/\/www.youtube.com\/embed\/RTaQ3FH2W_A?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<pre lang=\"julia\"  line=\"1\">\nusing Primes\n\nfunction getBigestFactors{T}(a::T,b::T)\n    c=T()\n    for k in keys(a)\n        c[k]=max(a[k],b[k]) \n    end\n    for k in keys(b)\n        c[k]=max(a[k],b[k]) \n    end\n    c\nend\n\nsuperfactors=reduce(getBigestFactors,map(factor,BigInt.(1:100))) \n\nn=prodfactors(superfactors)\n\n<\/pre>\n<p><code>Julia<\/code> can be amazingly expressive. In line 14 are getting all the prime factors of all the numbers from 1 to 100 using the <code>map<\/code> function. We are using the type <code>BigInt<\/code> since will be generating pretty large numbers. The standard <code>Int<\/code> will simply overflow. We then use <code>reduce<\/code> to get all the common factors for the numbers from 1 to 100.<\/p>\n<p>If your are slight confused lets take a bit slower. First we generate a one dimensional array of <code>BigInt<\/code>s from 1 to 100.<\/p>\n<pre lang=\"julia\">\nBigInt.(1:100)\n<\/pre>\n<p>This makes use of <code>Julia<\/code>&#8216;s very <a href=\"https:\/\/julialang.org\/blog\/2017\/01\/moredots\">powerful dot factorization syntax<\/a>. We then <code>map<\/code> that array into another array of <code>Primes.Factorization{BigInt}<\/code> through the <code>factor<\/code> function in the <code>Primes<\/code> package. The <code>Primes.Factorization<\/code> type is subtype of <code>Associative<\/code>. I learned that from reading the <a href=\"https:\/\/github.com\/JuliaMath\/Primes.jl\/blob\/master\/src\/factorization.jl\">implementation<\/a>.<\/p>\n<p>The cool thing about <code>Associative<\/code> types that the can be very conveniently accessed. Lets have a closer look.<\/p>\n<pre lang=\"julia\">\na=factor(24)\nprintln(a)\n<\/pre>\n<p>yields<\/p>\n<pre lang=\"julia\">\nPrimes.Factorization(2=>3,3=>1)\n<\/pre>\n<p>That is \\(2^3 3\\)<\/p>\n<p>You can then do the following<\/p>\n<pre lang=\"julia\">\nprint(a[2]) \n<\/pre>\n<p>yielding<\/p>\n<pre lang=\"julia\">\n3\n<\/pre>\n<p>This means that the number 24 has a 2 raised to the third power as a factor.<\/p>\n<p>Or, be more adventurous and try<\/p>\n<pre lang=\"julia\">\nprint(a[5]) \n<\/pre>\n<p>which will print a<\/p>\n<pre lang=\"julia\">\n0\n<\/pre>\n<p>This makes perfect sense as \\(5^0=1\\) and <code>1<\/code>  is always a factor of any number. We will always get 0 exponent for any number that is not a prime factor of a given number.  The <code>Primes.jl<\/code> package authors have done great use of <code>Julia<\/code>&#8216;s very powerful type system.<\/p>\n<p>To solve this problem we need to look at all the prime factors for all the numbers from 1 to 100 find the highest exponent of the of each of those prime factors. To do that we implement the <code>getBigestFactor<\/code> function when does that for any two prime factorizations. We plug that into <code>reduce<\/code> and <em>et voil\u00e0<\/em>!<\/p>\n<p>The superfactors in line 14 are<\/p>\n<pre lang=\"julia\">\n2^6 \u22c5 3^4 \u22c5 5^2 \u22c5 7^2 \u22c5 11 \u22c5 13 \u22c5 17 \u22c5 19 \u22c5 23 \u22c5 29 \u22c5 31 \u22c5 37 \u22c5 41 \u22c5 43 \u22c5 47 \u22c5 53 \u22c5 59 \u22c5 61 \u22c5 67 \u22c5 71 \u22c5 73 \u22c5 79 \u22c5 83 \u22c5 89 \u22c5 97\n<\/pre>\n<p>Finally we multiply them to get our special number at line 16<\/p>\n<pre lang=\"julia\">\nn=69720375229712477164533808935312303556800\n<\/pre>\n<p>Are we done yet?<\/p>\n<p>As the saying goes &#8220;there is more than one way to skin a cat&#8221;. Some are more elegant than others.<br \/>\nHere is a more elegant and computationally more efficient way.<\/p>\n<pre lang=\"julia\" line=\"1\">\nUsing Primes\nfunction getAllFactors{T}(n::T)\n    p_factors=filter(isprime,T.(1:n))\n    exponents=[floor(T,log(p,n)) for p in p_factors]\n    zip(p_factors,exponents) |> Dict |> Primes.Factorization\nend\n<\/pre>\n<p>Here we just get the prime numbers in the range from 1 to <code>n<\/code> (line 3). Using those primes we then get the highest exponents that will not yield a number outside the range (line 4). Finally, we package everything as a <code>Primes.Factorization<\/code> (line 5).<\/p>\n<p>In <code>Julia<\/code> REPL we get<\/p>\n<pre lang=\"julia\">\njulia> getAllFactors(big\"100\")\n2^6 \u22c5 3^4 \u22c5 5^2 \u22c5 7^2 \u22c5 11 \u22c5 13 \u22c5 17 \u22c5 19 \u22c5 23 \u22c5 29 \u22c5 31 \u22c5 37 \u22c5 41 \u22c5 43 \u22c5 47 \u22c5 53 \u22c5 59 \u22c5 61 \u22c5 67 \u22c5 71 \u22c5 73 \u22c5 79 \u22c5 83 \u22c5 89 \u22c5 97\n\njulia> prodfactors(ans)\n69720375229712477164533808935312303556800\n<\/pre>\n<p>At that point, you might ask, why stop at a 100. <code>Julia<\/code> is lightening fast and powerful. Just for fun we can do the same for numbers from 1 to 1000.<\/p>\n<pre lang=\"julia\">\njulia> getAllFactors(big\"1000\")\n2^9 \u22c5 3^6 \u22c5 5^4 \u22c5 7^3 \u22c5 11^2 \u22c5 13^2 \u22c5 17^2 \u22c5 19^2 \u22c5 23^2 \u22c5 29^2 \u22c5 31^2 \u22c5 37 \u22c5 41 \u22c5 43 \u22c5 47 \u22c5 53 \u22c5 59 \u22c5 61 \u22c5 67 \u22c5 71 \u22c5 73 \u22c5 79 \u22c5 83 \u22c5 89 \u22c5 97 \u22c5 101 \u22c5 103 \u22c5 107 \u22c5 109 \u22c5 113 \u22c5 127 \u22c5 131 \u22c5 137 \u22c5 139 \u22c5 149 \u22c5 151 \u22c5 157 \u22c5 163 \u22c5 167 \u22c5 173 \u22c5 179 \u22c5 181 \u22c5 191 \u22c5 193 \u22c5 197 \u22c5 199 \u22c5 211 \u22c5 223 \u22c5 227 \u22c5 229 \u22c5 233 \u22c5 239 \u22c5 241 \u22c5 251 \u22c5 257 \u22c5 263 \u22c5 269 \u22c5 271 \u22c5 277 \u22c5 281 \u22c5 283 \u22c5 293 \u22c5 307 \u22c5 311 \u22c5 313 \u22c5 317 \u22c5 331 \u22c5 337 \u22c5 347 \u22c5 349 \u22c5 353 \u22c5 359 \u22c5 367 \u22c5 373 \u22c5 379 \u22c5 383 \u22c5 389 \u22c5 397 \u22c5 401 \u22c5 409 \u22c5 419 \u22c5 421 \u22c5 431 \u22c5 433 \u22c5 439 \u22c5 443 \u22c5 449 \u22c5 457 \u22c5 461 \u22c5 463 \u22c5 467 \u22c5 479 \u22c5 487 \u22c5 491 \u22c5 499 \u22c5 503 \u22c5 509 \u22c5 521 \u22c5 523 \u22c5 541 \u22c5 547 \u22c5 557 \u22c5 563 \u22c5 569 \u22c5 571 \u22c5 577 \u22c5 587 \u22c5 593 \u22c5 599 \u22c5 601 \u22c5 607 \u22c5 613 \u22c5 617 \u22c5 619 \u22c5 631 \u22c5 641 \u22c5 643 \u22c5 647 \u22c5 653 \u22c5 659 \u22c5 661 \u22c5 673 \u22c5 677 \u22c5 683 \u22c5 691 \u22c5 701 \u22c5 709 \u22c5 719 \u22c5 727 \u22c5 733 \u22c5 739 \u22c5 743 \u22c5 751 \u22c5 757 \u22c5 761 \u22c5 769 \u22c5 773 \u22c5 787 \u22c5 797 \u22c5 809 \u22c5 811 \u22c5 821 \u22c5 823 \u22c5 827 \u22c5 829 \u22c5 839 \u22c5 853 \u22c5 857 \u22c5 859 \u22c5 863 \u22c5 877 \u22c5 881 \u22c5 883 \u22c5 887 \u22c5 907 \u22c5 911 \u22c5 919 \u22c5 929 \u22c5 937 \u22c5 941 \u22c5 947 \u22c5 953 \u22c5 967 \u22c5 971 \u22c5 977 \u22c5 983 \u22c5 991 \u22c5 997\n\njulia> prodfactors(ans)\n7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000\n<\/pre>\n<p>Now we get super special number that is 443 digits long. Lets finish by a <code>Julia<\/code> one liner to get the number of digits<\/p>\n<pre lang=\"julia\">\njulia> getAllFactors(big\"1000\") |> prodfactors|> digits |>length\n433\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Mathematical recreation is fun. I came across a nice Mind your Decisions video and thought it would be cool to use Julia to find that special number. Have a look at the video here before we continue using Primes function getBigestFactors{T}(a::T,b::T) c=T() for k in keys(a) c[k]=max(a[k],b[k]) end for k in keys(b) c[k]=max(a[k],b[k]) end c [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[98],"class_list":["post-538","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-primes-jl"],"_links":{"self":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts\/538","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=538"}],"version-history":[{"count":18,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts\/538\/revisions"}],"predecessor-version":[{"id":561,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=\/wp\/v2\/posts\/538\/revisions\/561"}],"wp:attachment":[{"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=538"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=538"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/perfectionatic.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=538"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}