14
\$\begingroup\$

Definitions

  • Two numbers are co-prime if their only positive common divisor is 1.
  • A list of numbers is mutually co-prime if every pair of numbers within that list are co-prime with each other.
  • A factorization of number n is a list of numbers whose product is n.

Task

Given a positive number n, output the mutually co-prime factorization of n with the maximum length that does not include 1.

Example

For n=60, the answer is [3,4,5], because 3*4*5=60 and no other mutually co-prime factorization without 1 has length greater than or equal to 3, the length of the factorization.

Rules and freedoms

  • You can use any reasonable input/output format.
  • The entries in the output list do not need to be sorted.

Testcases

n   output
1   []
2   [2]
3   [3]
4   [4]
5   [5]
6   [2, 3]
7   [7]
8   [8]
9   [9]
10  [2, 5]
11  [11]
12  [3, 4]
13  [13]
14  [2, 7]
15  [3, 5]
16  [16]
17  [17]
18  [2, 9]
19  [19]
20  [4, 5]
21  [3, 7]
22  [2, 11]
23  [23]
24  [3, 8]
25  [25]
26  [2, 13]
27  [27]
28  [4, 7]
29  [29]
30  [2, 3, 5]
31  [31]
32  [32]
33  [3, 11]
34  [2, 17]
35  [5, 7]
36  [4, 9]
37  [37]
38  [2, 19]
39  [3, 13]
40  [5, 8]
41  [41]
42  [2, 3, 7]
43  [43]
44  [4, 11]
45  [5, 9]
46  [2, 23]
47  [47]
48  [3, 16]
49  [49]
50  [2, 25]
51  [3, 17]
52  [4, 13]
53  [53]
54  [2, 27]
55  [5, 11]
56  [7, 8]
57  [3, 19]
58  [2, 29]
59  [59]
60  [3, 4, 5]
61  [61]
62  [2, 31]
63  [7, 9]
64  [64]
65  [5, 13]
66  [2, 3, 11]
67  [67]
68  [4, 17]
69  [3, 23]
70  [2, 5, 7]
71  [71]
72  [8, 9]
73  [73]
74  [2, 37]
75  [3, 25]
76  [4, 19]
77  [7, 11]
78  [2, 3, 13]
79  [79]
80  [5, 16]
81  [81]
82  [2, 41]
83  [83]
84  [3, 4, 7]
85  [5, 17]
86  [2, 43]
87  [3, 29]
88  [8, 11]
89  [89]
90  [2, 5, 9]
91  [7, 13]
92  [4, 23]
93  [3, 31]
94  [2, 47]
95  [5, 19]
96  [3, 32]
97  [97]
98  [2, 49]
99  [9, 11]

Scoring

This is . Shortest answer in bytes wins.

\$\endgroup\$

15 Answers 15

10
\$\begingroup\$

Mathics, 24 bytes

#^#2&@@@FactorInteger@#&

Try it online!

\$\endgroup\$
  • 5
    \$\begingroup\$ #^#2&@@@FactorInteger@#&[1] returns {1} in Mathematica. But it works in Mathics. \$\endgroup\$ – alephalpha May 12 '17 at 10:54
  • \$\begingroup\$ @alephalpha Thanks, it wouldn't even have occurred to me to see whether Mathics implements FactorInteger differently. :) \$\endgroup\$ – Martin Ender May 12 '17 at 11:03
9
\$\begingroup\$

Brachylog, 4 bytes

ḋḅ×ᵐ

Try it online!

Explanation

       # output is the list of
  ×ᵐ   # products of each
 ḅ     # block of consecutive equal elements
ḋ      # of the prime factors
       # of the input
\$\endgroup\$
  • 2
    \$\begingroup\$ Congrats on your first Brachylog answer! ...at least I think? \$\endgroup\$ – Fatalize May 12 '17 at 16:36
  • 1
    \$\begingroup\$ @Fatalize: My 2nd I think. I had this one from before. Definitely my shortest one though :) \$\endgroup\$ – Emigna May 12 '17 at 16:46
5
\$\begingroup\$

05AB1E, 3 5 bytes

+2 bytes to fix the edge case of 1. Thanks to Riley for the patch (and for the test suite, my 05ab1e is not that strong!)

ÒγP1K

Test suite at Try it online!

How?

Ò     - prime factorisation, with duplicates
 γ    - split into chunks of consecutive equal elements
  P   - product of each list
   1  - literal one
    K - removed instances of top from previous
      - implicitly display top of stack
\$\endgroup\$
  • \$\begingroup\$ @Adnan is that the best link for "bytes" or is there a formatted code page somewhere? \$\endgroup\$ – Jonathan Allan May 12 '17 at 10:51
  • \$\begingroup\$ Yeah, there is a code-page that displays all bytes. \$\endgroup\$ – Adnan May 12 '17 at 10:53
  • 1
    \$\begingroup\$ Oh, how'd I miss it >_< Thanks ever so much :) \$\endgroup\$ – Jonathan Allan May 12 '17 at 10:53
  • \$\begingroup\$ Does not work for 1. \$\endgroup\$ – Leaky Nun May 12 '17 at 11:00
  • \$\begingroup\$ @LeakyNun fixed up with help :) \$\endgroup\$ – Jonathan Allan May 12 '17 at 14:10
3
\$\begingroup\$

CJam, 9 bytes

{mF::#1-}

Try it online!

Simply separates the input into its constituent prime powers and removes 1s (only necessary for input 1).

\$\endgroup\$
3
\$\begingroup\$

Haskell, 51 bytes

(2#) is an anonymous function taking an integer and returning a list.

Use as (2#) 99.

m#n|m>n=[]|x<-gcd(m^n)n=[x|x>1]++(m+1)#div n x
(2#)

Try it online!

Inspired by the power trick some people used in the recent squarefree number challenge.

  • m#n generates factors of n, starting with m.
  • If m>n, we stop, concluding we've already found all factors.
  • x=gcd(m^n)n is the largest factor of n whose prime factors are all in m. Note that because smaller m are tested first, this will be 1 unless m is prime.
  • We include x in the resulting list if it's not 1, and then recurse with the next m, dividing n by x. Note that x and div n x cannot have common factors.
  • (2#) takes a number and starts finding its factors from 2.
\$\endgroup\$
3
\$\begingroup\$

MATL, 7 bytes

&YF^1X-

Try it online! Or verify all test cases.

Explanation

Consider input 80 as an example.

&YF    % Implicit input. Push array of unique prime factors and array of exponents
       % STACK: [2 3 5], [4 0 1]
^      % Power, element-wise
       % STACK: [16 1 5]
1      % Push 1
       % STACK: [16 1 5], 1
X-     % Set difference, keeping order. Implicitly display
       % STACK: [16 5]

EDIT (June 9, 2017): YF with two outputs has been modified in release 20.1.0: non-factor primes and their (zero) exponents are skipped. This doesn't affect the above code, which works without requiring any changes (but 1X- could be removed).

\$\endgroup\$
  • \$\begingroup\$ I assume the change means 1X- is redundant in the new release... also, that looks like set difference rather than intersection to me. \$\endgroup\$ – Ørjan Johansen Jun 9 '17 at 23:10
  • \$\begingroup\$ @ØrjanJohansen Correct on both. Thanks! \$\endgroup\$ – Luis Mendo Jun 9 '17 at 23:26
2
\$\begingroup\$

Jelly, 5 bytes

ÆF*/€

Test suite at Try it online!

How?

ÆF*/€ - Main link: n
ÆF    - prime factors as [prime, exponent] pairs
   /€ - reduce €ach with:
  *   - exponentiation
\$\endgroup\$
  • \$\begingroup\$ An alternate 6-byte solution in an attempt to find another method that would tie with yours (unfortunately failing): ÆfŒgZP. It has the same number of tokens but too many two-byte atoms ;) \$\endgroup\$ – HyperNeutrino May 12 '17 at 12:10
  • \$\begingroup\$ ...and like my deleted 05ab1e entry it returns 1 for an input of 1 which is disallowed (the effect of performing an empty product). \$\endgroup\$ – Jonathan Allan May 12 '17 at 12:14
  • \$\begingroup\$ :( Well, whoops, overlooked that. Darn. :P \$\endgroup\$ – HyperNeutrino May 12 '17 at 12:18
2
\$\begingroup\$

Alice, 10 bytes

Ifw.n$@EOK

Try it online!

Unfortunately, this uses code points as integer I/O again. The test case in the TIO link is input 191808 which decomposes into 64, 81 and 37. Note that this solution prints the prime powers in order from largest to smallest prime, so we get the output %Q@.

For convenience, here is a 16-byte solution with decimal I/O which uses the same core algorithm:

/O/\K
\i>fw.n$@E

Try it online!

Explanation

As the other answers, this decomposes the input into prime powers.

I      Read a code point as input.
f      Compute its prime factorisation a prime/exponent pairs and push them
       to the stack in order from smallest to largest prime.
w      Remember the current IP position on the return address stack. This
       starts a loop.
  .      Duplicate the current exponent. This will be zero once all primes
         have been processed.
  n$@    Terminate the program if this was zero.
  E      Raise the prime to its corresponding power.
  O      Output the result as a character.
K      Return to the w to run the next loop iteration.
\$\endgroup\$
2
\$\begingroup\$

mathematica 46 bytes

#[[1]]^#[[2]]&/@If[#==1,#={},FactorInteger@#]&

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice answer, but it's giving slightly incorrect output for some of the test cases. Currently your code outputs {}; {2}; {3}; {2}; {5}; {2,3}; {7}; {2}; {3}; {2,5}; {11}; {2,3}; {13}; ... but it should output {}; {2}; {3}; {4}; {5}; {2,3}; {7}; {8}; {9}; {2,5}; {11}; {4,3}; {13}; ... instead. \$\endgroup\$ – Kevin Cruijssen May 12 '17 at 14:37
  • \$\begingroup\$ I think I fixed it \$\endgroup\$ – J42161217 May 12 '17 at 14:58
  • \$\begingroup\$ Seems to work in TIO indeed. +1 Oh, and welcome to PPCG, I see you're fairly new here. You've probably already seen it, but if not, Tips for golfing in Mathematica might be interesting to read through. Enjoy your stay! :) \$\endgroup\$ – Kevin Cruijssen May 12 '17 at 15:11
  • 1
    \$\begingroup\$ If you find yourself accessing the components of # more than # itself, you can save a lot of bytes by using Apply (@@@) instead of Map (/@): #^#2&@@@If... \$\endgroup\$ – Martin Ender May 12 '17 at 20:32
1
\$\begingroup\$

PHP, 62 Bytes

prints a associative array with the prime as key and how often the prime is use as value and nothing for input 1

for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!++$r[$i];print_r($r);

Try it online!

Output for 60

Array
(
    [2] => 2
    [3] => 1
    [5] => 1
)

PHP, 82 Bytes

for($i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);print_r($r);

Try it online!

prints nothing for input 1 if you wish a empty array instead and a sorted array it will be a little longer

for($r=[],$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r[$i]=$r[$i]?$r[$i]*$i:$i);sort($r);print_r($r);
\$\endgroup\$
1
\$\begingroup\$

Actually, 6 bytes

w⌠iⁿ⌡M

Try it online!

Explanation:

w⌠iⁿ⌡M
w       factor into [prime, exponent] pairs
 ⌠iⁿ⌡M  for each pair:
  i       flatten
   ⁿ      prime**exponent
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 28 bytes

n->[x[1]^x[2]|x<-factor(n)~]

Try it online!

\$\endgroup\$
0
\$\begingroup\$

miniML, 47 bytes

Challenges involving prime factorization are terribly over-represented here, so we are all sadly forced to have factorization in the standard library.

fun n->map(fun p->ipow(fst p)(snd p))(factor n)

Note that the 'mini' in miniml refers to the size of the feature set, not the size of source code written in it.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 61 bytes

require 'prime'
->n{(2..n).select{|e|n/e.to_f%1==0&&e.prime?}}

I'm really disappointed after looking 6-7 byte solutions -))

\$\endgroup\$
0
\$\begingroup\$

Mathematica, 24 bytes

Power@@@FactorInteger@#&

Too bad @@@* is not a thing. Also, I'd like /@*, @@*, and in fact, change @@@ to /@@, //@ to @@@ or whatever and add the infinite family of //@, ///@, ...

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