29
\$\begingroup\$

Given a positive integer n, simplify the square root √n into the form a√b by extracting all square factors. The outputted a,b should be positive integers with n = a^2 * b with b as small as possible.

You may output a and b in either order in any reasonable format. You may not omit outputs of 1 as implicit.

The outputs for n=1..36 as (a,b):

1 (1, 1)
2 (1, 2)
3 (1, 3)
4 (2, 1)
5 (1, 5)
6 (1, 6)
7 (1, 7)
8 (2, 2)
9 (3, 1)
10 (1, 10)
11 (1, 11)
12 (2, 3)
13 (1, 13)
14 (1, 14)
15 (1, 15)
16 (4, 1)
17 (1, 17)
18 (3, 2)
19 (1, 19)
20 (2, 5)
21 (1, 21)
22 (1, 22)
23 (1, 23)
24 (2, 6)
25 (5, 1)
26 (1, 26)
27 (3, 3)
28 (2, 7)
29 (1, 29)
30 (1, 30)
31 (1, 31)
32 (4, 2)
33 (1, 33)
34 (1, 34)
35 (1, 35)
36 (6, 1)

These are OEIS A000188 and A007913.

Related: A more complex version.

var QUESTION_ID=83814,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/83814/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • \$\begingroup\$ We've had this before, and that was closed as a duplicate of the challenge linked here. \$\endgroup\$ – flawr Jun 26 '16 at 19:39

16 Answers 16

13
\$\begingroup\$

Jelly, 9 bytes

ÆE;0d2ZÆẸ

Try it online! or verify all test cases.

How it works

ÆE;0d2ZÆẸ  Main link. Argument: n

ÆE         Exponents; generate the exponents of n's prime factorization.
  ;0       Append 0 since 1ÆE returns [].
    d2     Divmod by 2.
      Z    Zip/transpose to group quotients and remainders.
       ÆẸ  Unexponent; turn the exponents of prime factorizations into integers.
\$\endgroup\$
  • 3
    \$\begingroup\$ In UTF-8, it is, but Jelly uses a custom code page. The bytes link in the header points to it. \$\endgroup\$ – Dennis Jun 27 '16 at 5:51
  • \$\begingroup\$ You post that comment a lot, so maybe you should make the bytes like clearer (for example: [bytes](link-to-byes) (not UTF-8). \$\endgroup\$ – NoOneIsHere Nov 30 '17 at 21:01
12
\$\begingroup\$

PARI/GP, 12 bytes

n->core(n,1)

core returns the squarefree part of n by default, but setting the second argument flag to 1 makes it return both parts. Output order is (b, a), e.g. (n->core(n,1))(12) -> [3, 2].

\$\endgroup\$
11
\$\begingroup\$

Python 2, 43 bytes

k=n=input()
while n%k**2:k-=1
print k,n/k/k

Test it on Ideone.

\$\endgroup\$
6
\$\begingroup\$

MATL, 12 bytes

t:U\~f0)GyU/

Try it online!

Explanation

t     % Take input n implicitly. Duplicate
:U    % Push [1 4 9 ... n^2]
\~    % True for entries that divide the input
f0)   % Get (1-based) index of the last (i.e. largest) dividing number
G     % Push input again
y     % Duplicate index of largest dividing number
U     % Square to recover largest dividing number
/     % Divide input by that. Implicitly display stack
\$\endgroup\$
4
\$\begingroup\$

Julia, 32 bytes

\(n,k=n)=n%k^2>0?n\~-k:[k,n/k^2]

Try it online!

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

Mathematica 34 bytes

#/.{a_ b_^_:>{a, b},_[b_,_]:>{1,b}}&

This says to replace all the input (#) according to the following rules: (1) a number, a, times the square root of b should be replaced by {a, b} and a function b to the power of whatever should be replaced by {1,b} . Note that the function assumes that the input will be of the form, Sqrt[n]. It will not work with other sorts of input.

This unnamed function is unusually cryptic for Mathematica. It can be clarified somewhat by showing its full form, followed by replacements of the original shorter forms.

Function[
   ReplaceAll[
      Slot[1],
      List[
         RuleDelayed[Times[Pattern[a,Blank[]],Power[Pattern[b,Blank[]],Blank[]]],List[a,b]],
         RuleDelayed[Blank[][Pattern[b,Blank[]],Blank[]],List[1,b]]]]]

which is the same as

   ReplaceAll[
      #,
      List[
         RuleDelayed[Times[Pattern[a,Blank[]],Power[Pattern[b,Blank[]],Blank[]]],List[a,b]],
         RuleDelayed[Blank[][Pattern[b,Blank[]],Blank[]],List[1,b]]]]&

and

ReplaceAll[#, 
  List[RuleDelayed[
    Times[Pattern[a, Blank[]], 
     Power[Pattern[b, Blank[]], Blank[]]], {a, b}], 
   RuleDelayed[Blank[][Pattern[b, Blank[]], Blank[]], {1, b}]]] &

and

ReplaceAll[#, 
  List[RuleDelayed[Times[a_, Power[b_, _]], {a, b}], 
   RuleDelayed[Blank[][b_, _], {1, b}]]] &

and

ReplaceAll[#, {RuleDelayed[a_*b^_, {a, b}], RuleDelayed[_[b_, _], {1, b}]}]&

and

ReplaceAll[#, {a_*b^_ :> {a, b}, _[b_, _] :> {1, b}}] &
\$\endgroup\$
1
\$\begingroup\$

Pyth, 15 bytes

/Q^
ef!%Q^T2SQ2

Test suite.

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

Matlab, 51 bytes

x=input('');y=1:x;z=y(~rem(x,y.^2));a=z(end)
x/a^2

Explanation

x=input('')       -- takes input
y=1:x             -- numbers from 1 to x
z=y(~rem(x,y.^2)) -- numbers such that their squares divide x
a=z(end)          -- biggest such number (first part of output)
x/a^2             -- remaining part
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ECMAScript 2016), 40 bytes

n=>{for(k=n;n%k**2;k--);return[k,n/k/k]}

Basically a JavaScript port of Dennis's Python 2 answer.

Try it on JSBin.

Note: it doesn't work in strict mode, because k is not initialized anywhere. To make it work in strict mode, k=n in the loop should be changed to let k=n.

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

Haskell, 43> 42 bytes

Brute force solution.

Saved 1 byte thanks to Xnor

f n=[(x,y)|y<-[1..],x<-[1..n],x*x*y==n]!!0
\$\endgroup\$
  • \$\begingroup\$ Nice solution, I like how it doesn't use mod or div. I think you can do y<-[1..] due to laziness. \$\endgroup\$ – xnor Jun 27 '16 at 11:02
  • \$\begingroup\$ Yes, you are right. It wasn't possible with my first solution last[(x,y)|x<-[1..n],y<-[1..n],x*x*y==n] but now it will work. Thanks. Do you have your own solution in Haskell? \$\endgroup\$ – Damien Jun 27 '16 at 12:06
1
\$\begingroup\$

05AB1E, 14 bytes

Lv¹ynÖi¹yn/y‚ï

Explained

Lv              # for each x in range(1,N) inclusive
  ¹ynÖi         # if N % x^2 == 0
       ¹yn/y‚ï  # create [N/x^2,x] pairs, N=12 -> [12,1] [3,2]
                # implicitly output last found pair

Try it online

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

Python, 74 Bytes

def e(k):a=filter(lambda x:k/x**2*x*x==k,range(k,0,-1))[0];return a,k/a**2

Straightforward enough.

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

Python 2.7 (ungolfed) - 181 Bytes

def e(n):   
 for x in range(1,n+1):
  r=(1,x)
  for i in range(1,x+1):
   l=i**.5
   for j in range(1,x+1): 
    if i*j==x and l%1==0 and j<r[1]:r=(int(l),j)                
  print x,r

Run as: e(number) eg. e(24)

Sample output:

>> e(24)
1 (1, 1)
2 (1, 2)
3 (1, 3)
4 (2, 1)
5 (1, 5)
6 (1, 6)
7 (1, 7)
8 (2, 2)
9 (3, 1)
10 (1, 10)
11 (1, 11)
12 (2, 3)
13 (1, 13)
14 (1, 14)
15 (1, 15)
16 (4, 1)
17 (1, 17)
18 (3, 2)
19 (1, 19)
20 (2, 5)
21 (1, 21)
22 (1, 22)
23 (1, 23)
24 (2, 6)
\$\endgroup\$
  • 1
    \$\begingroup\$ Please attempt to golf your answer as much as possible, this is a code-golf \$\endgroup\$ – caird coinheringaahing Nov 30 '17 at 18:50
0
\$\begingroup\$

APL, 25 chars

 {(⊢,⍵÷×⍨)1+⍵-0⍳⍨⌽⍵|⍨×⍨⍳⍵}

In English:

  • 0⍳⍨⌽⍵|⍨×⍨⍳⍵: index of the largest of the squares up to n that divides completely n;
  • 1+⍵-: the index is in the reversed array, so adjust the index
  • (⊢,⍵÷×⍨): produce the result: the index itself (a) and the quotient b (that is, n÷a*a)

Test:

     ↑{(⊢,⍵÷×⍨)⊃z/⍨0=⍵|⍨×⍨z←⌽⍳⍵}¨⍳36
1  1
1  2
1  3
2  1
1  5
1  6
1  7
2  2
3  1
1 10
1 11
2  3
1 13
1 14
1 15
4  1
1 17
3  2
1 19
2  5
1 21
1 22
1 23
2  6
5  1
1 26
3  3
2  7
1 29
1 30
1 31
4  2
1 33
1 34
1 35
6  1
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ECMAScript 6), 35 bytes

f=(n,k=n)=>n/k%k?f(n,--k):[k,n/k/k]

JavaScript 1+, 37 B

for(k=n=prompt();n/k%k;--k);[k,n/k/k]
\$\endgroup\$
0
\$\begingroup\$

J, 19 bytes

(0|:0 2#:])&.(_&q:)

Try it online!

Same as the Jelly solution.

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