23
\$\begingroup\$

A collection of positive integers d_1 d_2 ... d_k is a factorisation of a positive integer n if

d_1 * d_2 * ... * d_k = n

Each positive integer has a unique prime factorisation, but in general they also have factorisations in which some of the terms are composite. E.g.

12 = 6 * 2 = 4 * 3 = 3 * 2 * 2

Write a program, function, verb, or similar which takes as input a single positive integer and returns or prints a complete list of its distinct factorisations. The factorisations may be produced in any order, and their terms may be in any order, but no two should be permutations of each other. Factorisations may not include 1 with two exceptions: for input n you may give the factorisation n*1 instead of n; and for input 1 you may give the factorisation 1 instead of the empty list.

You may assume that the input will be in the range of a signed 32-bit integer. If the output is as a string, there should be a clear distinction between the delimitation of numbers within a factorisation and the delimitation of the factorisations, but it is not necessary (for example) for the factors to be joined with an *.

Your code should be capable of handling any valid input within 10 minutes on a reasonable desktop machine.

Examples

1                  [[]]
                or [[1]]
                or [[1 1]]

7                  [[7]]
                or [[7 1]]
                or [[1 7]]

12                 [[12] [6 2] [4 3] [2 3 2]]
                or variants

16                 [[2 2 2 2] [2 2 4] [2 8] [4 4] [16]]
                or variants

901800900          a list of 198091 factorisations

1338557220         a list of 246218 factorisations
\$\endgroup\$
  • \$\begingroup\$ Can you post the list of factorisations of 901800900 and 1338557220 somewhere where we can check them? My code is giving me 2048 and 1024 factorizations for those numbers, respectively, and I'm not sure why. \$\endgroup\$ – Sherlock9 Jul 29 '16 at 9:28
  • \$\begingroup\$ @Sherlock9, will do that when I get home. What I can do with an online generator is to give you a valid output for 5336100. \$\endgroup\$ – Peter Taylor Jul 29 '16 at 10:22
  • 3
    \$\begingroup\$ This reminds me of a ProjectEuler challenge (unfortunately I don't remember which). But there you had to count the number of factorizations instead of listing them. \$\endgroup\$ – flawr Jul 29 '16 at 13:43
  • \$\begingroup\$ Related OEIS: A001055 \$\endgroup\$ – Sherlock9 Jul 29 '16 at 20:07
12
\$\begingroup\$

Haskell, 56 bytes

_!1=[[]]
i!n=[j:f|j<-[i..n],mod n j<1,f<-j!div n j]
(2!)

(2!)(1338557220::Int) prints in five minutes on my laptop, when compiled with ghc -O3.

Haskell, 62 bytes, but much faster

i!n|i*i>n=[[n]]|0<1=[i:f|mod n i<1,f<-i!div n i]++(i+1)!n
(2!)

(2!)(1338557220::Int) prints in a quarter of a second on my laptop, when compiled with ghc -O3.

\$\endgroup\$
  • \$\begingroup\$ How do I test this? ghc gives me Parse error: naked expression at top level and ghci gives me parse error on input `=' \$\endgroup\$ – Peter Taylor Jul 29 '16 at 14:55
  • \$\begingroup\$ @PeterTaylor Replace the function (2!) with the program main = print ((2!) (1338557220::Int)), compile with ghc -O3 factor.hs, and run with ./factor. \$\endgroup\$ – Anders Kaseorg Jul 29 '16 at 20:10
7
\$\begingroup\$

Pyth, 29 bytes

Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2

M                                def g(G, H):
                   @H2             square root of H
                  S                1-indexed range up to floor
                 >    tG           all but first G − 1 elements
            f                      filter for elements T such that:
              %HT                    H mod T
             !                       is false (0)
   m                               map for elements d:
       gd/Hd                         g(d, H/d)
    +Ld                              prepend d to each element
  a                     ]]H        append [[H]]
 s                                 concatenate
                           g2Q   print g(2, input)

Try it online

Runs in twenty seconds for 1338557220 on my laptop.

\$\endgroup\$
  • \$\begingroup\$ @PeterTaylor The usual way: pyth factor.pyth (or pyth -c 'Msam+Ldgd/Hdf!%HT>S@H2tG]]Hg2'), providing 16 on stdin. Make sure you are using a current version of Pyth; implicit Q was added in March. I can’t imagine how you might be getting division by zero, though. \$\endgroup\$ – Anders Kaseorg Jul 29 '16 at 20:06
  • \$\begingroup\$ Arrrrgh. I was using " instead of ', and bash was expanding the !% to something else. \$\endgroup\$ – Peter Taylor Jul 29 '16 at 21:24
6
\$\begingroup\$

Python, 252 313 312 311 145 141 137 135 103 84 83 bytes

This is largely based on Anders Kaseorg's Pyth answer. Any golfing suggestions welcome. Try it online!

Edit: 19 bytes golfed thanks to Dennis. Fixed a typo in the code and added a TIO link.

g=lambda n,m=2:[[n]]+[j+[d]for d in range(m,int(n**.5)+1)if n%d<1for j in g(n/d,d)]

Ungolfed:

def g(n, m=2):
    a = [[n]]
    s = int(n**.5) + 1
    for d in range(m, s):
        if n%d == 0:
            for j in g(n/d, d):
                a.append([d]+j)
    return a
\$\endgroup\$
  • 1
    \$\begingroup\$ **.5 gets rid of the import. \$\endgroup\$ – Dennis Jul 30 '16 at 0:57
4
\$\begingroup\$

JavaScript (ES6), 83 bytes

f=(n,a=[],m=2,i=m)=>{for(;i*i<=n;i++)n%i<1&&f(n/i,[...a,i],i);console.log(...a,n)}

Only borrowed @AndersKaseorg's square root trick because it ended up saving me bytes overall. Prints 1 for an input of 1, otherwise doesn't print 1s.

\$\endgroup\$
1
\$\begingroup\$

Ruby 1.9+, 87 89 87 bytes

This answer is based on Anders Kaseorg's Pyth answer. This code only works for versions after Ruby 1.9, as stabby lambdas -> were only introduced in 1.9. Any golfing suggestions are welcome.

g=->n,m=2{(m..Math.sqrt(n)).select{|i|n%i<1}.flat_map{|d|g[n/d,d].map{|j|[d]+j}}+[[n]]}

Ungolfed:

def g(n, m=2)
  a = [[n]]
  s = (m..Math.sqrt(n))
  t = s.select{|i|n%i<1}
  t.each do |d|
    g[n/d,d].each do |j|
      a.push([d]+j)
    end
  end
  return a
end
\$\endgroup\$
  • \$\begingroup\$ Does this require a particular version of Ruby? With 1.8.7 I get a complaint about g[n/d,d]: wrong number of arguments (0 for 1) \$\endgroup\$ – Peter Taylor Jul 30 '16 at 6:16
  • \$\begingroup\$ Apparently stabby lambdas -> were introduced in Ruby 1.9. I'll edit the answer to show the version number required. \$\endgroup\$ – Sherlock9 Jul 30 '16 at 8:48
  • \$\begingroup\$ Ok, thanks. I'm still curious about g[n/d,d]. g(n/d,d) is more backwards-compatible. \$\endgroup\$ – Peter Taylor Jul 30 '16 at 10:38
  • 1
    \$\begingroup\$ Ah, the f[n] is required to call stabby lambdas and Ruby lambdas in general. f(n) and f n calls require def and end. More info here and here \$\endgroup\$ – Sherlock9 Jul 30 '16 at 10:51
1
\$\begingroup\$

J, 52 bytes

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:

Not as efficient as it could be since some factorizations may be repeated and a final pass has to be done after sorting each factorization and then de-duplicating.

Try it online! (But try to keep the input values small).

On my desktop, the timings are

   f =: [:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:
   timex 'r =: f 1338557220'
3.14172
   # r
246218
   timex 'r =: f 901800900'
16.3849
   # r
198091

Explanation

This method relies on generating all set partitions for the prime factors of the input integer n. The performance is best when n is square-free, otherwise duplicate factorizations will be created.

[:~.q:<@/:~@(*//.)"$~#@q:_&(;@]<@(,~"{~0,#\@~.)"1)}:  Input: integer n
                                                  }:  Curtail, forms an empty array
                       q:                             Prime factorization
                     #@                               Length, C = count prime factors
                         _&(                     )    Repeat that many times on x = []
                                 (            )"1       For each row
                                            ~.            Unique
                                         #\@              Enumerate starting at 1
                                       0,                 Prepend 0
                                  ,~"{~                   Append each of those to a
                                                          copy of the row
                               <@                         Box it
                            ;&]                         Set x as the raze of those boxes
                                                      These are now the restricted growth
                                                      strings of order C
    q:                                                Prime factorization
            (    )"$~                                 For each RGS
               /.                                       Partition it
             */                                         Get the product of each block
        /:~@                                            Sort it
      <@                                                Box it
[:~.                                                  Deduplicate
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.