A factorization game

Question

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.

• Arnauld: Could you add a few more test cases? (Preferably of reasonable size.)
• Arnauld: 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.)
• Arnauld: Quoting xnor: If it's not mandatory, answers won't do it.
• Jeppe Stig Nielsen: 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).
• guest4308: @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)

Answer 1

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}

• user9207: Crashes with 1099511627776
• ZaMoC: @Anush It doesn't crash. Just needs memory. You didn't say anything about memory limitations. This is code golf
• user9207: Yes I realise. It just would be nice if you could actually run the code the input ranges specified in the question.
• ZaMoC: @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"
• ZaMoC: @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

Answer 2

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.

Answer 3

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.

Answer 4

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

• user9207: Your TIO code seems to output 3 instead of 9.
• Emigna: @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.
• Grimmy: €gZ is a bit more efficient than éθg for the same bytecount.
• Emigna: @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 :)

Answer 5

Perl 6, 38 bytes

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

Try it online!

Takes the greedy approach to selecting divisors.

• user9207: Doesn't terminate with 1099511627776
• Jo King: @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

Answer 6

Jelly, 9 bytes

ŒPP=3ƊƇẈṀ

Try it online!

-1 byte thanks to someone

-2 bytes thanks to ErikTheOutgolfer

• the default.: 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.
• user9207: It doesn't seem to terminate with 1099511627776
• hyperneutrino: @someone doesn't work for 36 but thanks
• hyperneutrino: @Anush yeah, it's really slow because i code-golfed it, not optimized for efficiency
• Erik the Outgolfer: 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\$).

Answer 7

Japt -h, 13 bytes

â à f_×ばつ¶UÃmÊn

Try it

Answer 8

Brachylog, 8 bytes

×ばつ⟩l

Try it online!

(The naive approach, ×ばつ≠l}f⌉, 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.

Answer 9

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!

Answer 10

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!

Answer 11

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)

Answer 12

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

Answer 13

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!

• the default.: Assuming I implemented your logic correctly, a 53-byte solution (that I couldn't rid of the "return" keyword): Try it online!
• Gymhgy: @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.

Answer 14

Husk, 10 bytes

▲さんかくmLfo=1ΠṖḊ

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