13
\$\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.

\$\endgroup\$
  • 9
    \$\begingroup\$ Could you add a few more test cases? (Preferably of reasonable size.) \$\endgroup\$ – Arnauld May 2 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 May 2 at 15:00
  • \$\begingroup\$ @Arnauld No I am careful to make it code-golf and no one is judged for that. It would just be cool if the code could run for the input ranges specfied. \$\endgroup\$ – Anush May 2 at 15:01
  • 5
    \$\begingroup\$ Quoting xnor: If it's not mandatory, answers won't do it. \$\endgroup\$ – Arnauld May 2 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 May 8 at 1:30

13 Answers 13

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}

\$\endgroup\$
  • \$\begingroup\$ Crashes with 1099511627776 \$\endgroup\$ – Anush May 2 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\$ – J42161217 May 2 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\$ – Anush May 2 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\$ – J42161217 May 2 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\$ – J42161217 May 2 at 22:36
4
\$\begingroup\$

Wolfram Language (Mathematica), 38 bytes

(c=n=#;If[i∣n,n/=i,--c]~Do~{i,n};c)&

Try it online!

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

\$\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
\$\endgroup\$
  • \$\begingroup\$ Your TIO code seems to output 3 instead of 9. \$\endgroup\$ – Anush May 2 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 May 2 at 14:01
  • \$\begingroup\$ €gZ is a bit more efficient than éθg for the same bytecount. \$\endgroup\$ – Grimmy May 3 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 May 3 at 11:20
2
\$\begingroup\$

Perl 6, 38 bytes

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

Try it online!

Takes the greedy approach to selecting divisors.

\$\endgroup\$
  • \$\begingroup\$ Doesn't terminate with 1099511627776 \$\endgroup\$ – Anush May 2 at 14:42
  • 6
    \$\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 May 2 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.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 9 bytes

ŒPP=³ƊƇẈṀ

Try it online!

-1 byte thanks to someone

-2 bytes thanks to ErikTheOutgolfer

\$\endgroup\$
  • \$\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\$ – someone May 2 at 14:17
  • \$\begingroup\$ It doesn't seem to terminate with 1099511627776 \$\endgroup\$ – Anush May 2 at 14:43
  • \$\begingroup\$ @someone doesn't work for 36 but thanks \$\endgroup\$ – HyperNeutrino May 2 at 14:46
  • \$\begingroup\$ @Anush yeah, it's really slow because i code-golfed it, not optimized for efficiency \$\endgroup\$ – HyperNeutrino May 2 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 May 2 at 15:29
2
\$\begingroup\$

Japt -h, 13 bytes

â à f_׶UÃmÊn

Try it

\$\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.
\$\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!

\$\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)
\$\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
\$\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!

\$\endgroup\$
  • \$\begingroup\$ Assuming I implemented your logic correctly, a 53-byte solution (that I couldn't rid of the "return" keyword): Try it online! \$\endgroup\$ – someone May 3 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\$ – Embodiment of Ignorance May 3 at 2:37
0
\$\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!

\$\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.