15
\$\begingroup\$

Input

A single integer \$1 \leq x \leq 10^{15}\$.

Output

The maximum number of distinct positive integers that have the product \$x\$.

Examples

Input: 1099511627776. Output: 9. One possible optimal list of factors is: (1, 2, 4, 8, 16, 32, 64, 128, 4096).

Input: 127381. Output 4. One possible optimal list of factors is: (1, 17, 59, 127).

Related to this old question.

Improve this question
\$\endgroup\$
8
  • 9
    \$\begingroup\$ Could you add a few more test cases? (Preferably of reasonable size.) \$\endgroup\$
    – Arnauld
    Commented May 2, 2019 at 14:31
  • 8
    \$\begingroup\$ Given your comments on most answers: if you're looking for efficient code instead, this should definitely not be tagged as code-golf. You may consider either fastest-code or fastest-algorithm for an upcoming challenge. If you really wanted all answers to work in a limited time within the specified range, it should have been explicitly mentioned. (And I would have recommended a smaller range so that it does not conflict with code-golf entirely.) \$\endgroup\$
    – Arnauld
    Commented May 2, 2019 at 15:00
  • 5
    \$\begingroup\$ Quoting xnor: If it's not mandatory, answers won't do it. \$\endgroup\$
    – Arnauld
    Commented May 2, 2019 at 15:09
  • 1
    \$\begingroup\$ For x=1, 2, ... I get f(x)=1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 3, 4, 2, 3 which I do not find in OEIS. It is clear enough that records will appear for factorial numbers x. For example the smallest x such that f(x)=13 will be 13!. I guess f depends only on the exponents of the prime factorization. So to find f(13^4*19^7*29^2) we might simplify to f(2^7*3^4*5^2). \$\endgroup\$
    – Jeppe Stig Nielsen
    Commented May 8, 2019 at 1:30
  • 1
    \$\begingroup\$ @JeppeStigNielsen the OEIS sequence is for factors greater than one, so the sequence for this question is A086435 + 1. (table for A086435 from 1 to 10000) \$\endgroup\$
    – guest4308
    Commented Sep 12 at 12:13

14 Answers 14

Reset to default
5
\$\begingroup\$

Wolfram Language (Mathematica), 52 bytes

Max[Length/@Cases[Subsets@Divisors@#,{a__}/;1a==#]]&

Try it online!

4-bytes saved thanks to @attinat

Here is also a 153 bytes version that calculates 1099511627776 and 10^15 

Max[Length/@Table[s=RandomSample@Flatten[Table@@@FactorInteger[#]];Last@Select[Times@@@TakeList[s,#]&/@IntegerPartitions@Length@s,DuplicateFreeQ],5!]]+1&

Try it online!

The result for 10^15 is 12

{1, 2, 4, 5, 10, 16, 25, 40, 50, 100, 125, 250}

Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ Crashes with 1099511627776 \$\endgroup\$
    – user9207
    Commented May 2, 2019 at 14:43
  • 7
    \$\begingroup\$ @Anush It doesn't crash. Just needs memory. You didn't say anything about memory limitations. This is code golf \$\endgroup\$
    – ZaMoC
    Commented May 2, 2019 at 14:46
  • \$\begingroup\$ Yes I realise. It just would be nice if you could actually run the code the input ranges specified in the question. \$\endgroup\$
    – user9207
    Commented May 2, 2019 at 14:49
  • 6
    \$\begingroup\$ @Anush This is code-golf. Not nice answers. Please specify your criteria. An answer is either valid or not. I think the problem here is the question... Maybe you should change it to "most sufficient algorithm" \$\endgroup\$
    – ZaMoC
    Commented May 2, 2019 at 14:54
  • 3
    \$\begingroup\$ @Anush I made an edit in my answer and added one more version which is really fast and efficient in case you want to check it \$\endgroup\$
    – ZaMoC
    Commented May 2, 2019 at 22:36
4
\$\begingroup\$

Wolfram Language (Mathematica), 38 35 31 bytes

If[i∣n,n/=i;1,0]~Sum~{i,n=#}&

Try it online!

Greedy algorithm. Times out on TIO on larger inputs such as 1099511627776.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 9 bytes

Very inefficient. Will time out on TIO for numbers with a large amount of divisors.

ÑæʒPQ}€gZ

Try it online!

Explanation

Ñ          # push a list of divisors of the input
 æ         # push the powerset of that list
  ʒPQ}     # filter, keep only the lists whose product is the input
      €g   # get the length of each
        Z  # take the maximum
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Your TIO code seems to output 3 instead of 9. \$\endgroup\$
    – user9207
    Commented May 2, 2019 at 14:00
  • \$\begingroup\$ @Anush: It is a different number than your example (since that one times out due to to many factors). I probably should use a more distinct example. \$\endgroup\$
    – Emigna
    Commented May 2, 2019 at 14:01
  • \$\begingroup\$ €gZ is a bit more efficient than éθg for the same bytecount. \$\endgroup\$
    – Grimmy
    Commented May 3, 2019 at 11:04
  • \$\begingroup\$ @Grimy: True. It won't do much difference as it's the filter that is the big bad guy here, but it doesn't hurt being a bit more efficient :) \$\endgroup\$
    – Emigna
    Commented May 3, 2019 at 11:20
2
\$\begingroup\$

Perl 6, 38 bytes

{$!=$_;+grep {$!%%$_&&($!/=$_)},1..$_}

Try it online!

Takes the greedy approach to selecting divisors.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Doesn't terminate with 1099511627776 \$\endgroup\$
    – user9207
    Commented May 2, 2019 at 14:42
  • 7
    \$\begingroup\$ @Anush Well, it terminates eventually. Generally, the answer is valid if the program's algorithm would work with any input, if it were given as much memory and time as it wanted. Since this is code-golf, I optimised it for code length, not algorithmic complexity \$\endgroup\$
    – Jo King ♦
    Commented May 2, 2019 at 14:49
2
\$\begingroup\$

Javascript (ES6), 39 bytes

f=(n,i=0)=>n%++i?n>i&&f(n,i):1+f(n/i,i)

There's probably a few bytes that can be saved here and there. Just uses the greedy algorithm for the factors.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Jelly, 9 bytes

ŒPP=³ƊƇẈṀ

Try it online!

-1 byte thanks to someone

-2 bytes thanks to ErikTheOutgolfer

Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ While preparing a input for the OEIS superseeker, I created a 11-byte likely golfable Jelly program (that uses a different approach), and am unlikely to post a Jelly answer so I'll pretend I golfed a byte from your solution: ÆE×8‘½’:2S‘ (it works with the power of the OEIS "formula" section for A003056). Disclaimer: it might be wrong, but it works on the test cases. \$\endgroup\$
    – the default.
    Commented May 2, 2019 at 14:17
  • \$\begingroup\$ It doesn't seem to terminate with 1099511627776 \$\endgroup\$
    – user9207
    Commented May 2, 2019 at 14:43
  • \$\begingroup\$ @someone doesn't work for 36 but thanks \$\endgroup\$
    – hyperneutrino ♦
    Commented May 2, 2019 at 14:46
  • \$\begingroup\$ @Anush yeah, it's really slow because i code-golfed it, not optimized for efficiency \$\endgroup\$
    – hyperneutrino ♦
    Commented May 2, 2019 at 14:46
  • 1
    \$\begingroup\$ You can remove ÆD, it's not like there are more partitions that are going to be created like this, it's just going to take a lot more time (times out for \$x\ge21\$). \$\endgroup\$
    – Erik the Outgolfer
    Commented May 2, 2019 at 15:29
2
\$\begingroup\$

Japt -h, 13 bytes

â à f_׶UÃmÊn

Try it

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 8 bytes

f;?⟨⊇×⟩l

Try it online!

(The naive approach, {~×≠l}ᶠ⌉, generates an infinite number of solutions with extra 1s before eliminating them with ≠, and thus fails to actually terminate. It's not a problem, though, since it's for the same byte count!)

Takes input through the input variable and output through the output variable. The header on TIO contains a copy of most of the code for the sake of showing you what the factor list is, but this works perfectly fine without it. Since ⊇ gives larger sublists first, this predicate essentially does the same thing as most other answers, but without explicitly generating and filtering the complete powerset of the factors, thanks to backtracking.

            The output
       l    is the length of
    ⊇       a sublist (the largest satisfying these constraints)
f           of the factors of
            the input
 ; ⟨  ⟩     which
     ×      with its elements multiplied together
  ?         is the input.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 34 bytes

Obviously times out on that massive number, but will eventually time out if given enough time on another machine.

->n{(1..n).count{|e|n%e<1?n/=e:p}}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala, 77 bytes

def f(n:Long)={var(m,c,i)=(n,1,2L);while(i<=m){if(m%i==0){m/=i;c+=1};i+=1};c}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Gaia, 10 9 bytes

Π=
dz↑⁇(l

Try it online!

Follows the same "algorithm" as seen elsewhere -- filter the divisor powerset for the longest with product equal to the number and return its length.

	| helper function
Π=	| is prod(list)==n (implicit)?
	|
	| main function; implicitly takes n
dz	| divisor powerset (in decreasing order of size)
  ↑⁇	| filter by helper function
    (l	| take the first element and take the length (implicitly output)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Clam, 15 bytes

p}_`nq#:;qQ@s~Q

TIO link coming soon (when dennis pulls)

Basically a port of @Emigna's 05AB1E solution.

Explanation

                - Implicit Q = first input
p               - Print...
 }              - The last element of...
  _             - Sorted...
   `nq          - Lengths of... (map q => q.len)
           @s   - Items in powerset of
             ~Q - Proper divisors of Q
      #         - Where... (filter)
        ;q      - Product of subset
       :        - Equals...
          Q     - Q
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

C# (Visual C# Interactive Compiler), 54 bytes

int f(int n,int i=0)=>n%++i<1?1+f(n/i,i):n>i?f(n,i):0;

Uses the same approach as @vrugtehagel's and @JoKing's answers.

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Assuming I implemented your logic correctly, a 53-byte solution (that I couldn't rid of the "return" keyword): Try it online! \$\endgroup\$
    – the default.
    Commented May 3, 2019 at 2:23
  • 1
    \$\begingroup\$ @someone Thanks, but according to meta, functions have to be reusable. Also, I'm don't know if it is acceptable to have declarations outside of the function leave out a trailing semicolon, may make a meta post on that. \$\endgroup\$
    – Gymhgy
    Commented May 3, 2019 at 2:37
0
\$\begingroup\$

Husk, 10 bytes

▲mLfo=¹ΠṖḊ

Try it online! A port of Emigna's answer.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.