Simplify a square root

29

2

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>

xnor

Posted 2016-06-26T00:00:55.153

Reputation: 115 687

We've had this before, and that was closed as a duplicate of the challenge linked here.

– flawr – 2016-06-26T19:39:19.837

Answers

13

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.

Dennis

Posted 2016-06-26T00:00:55.153

Reputation: 196 637

3In UTF-8, it is, but Jelly uses a custom code page. The bytes link in the header points to it. – Dennis – 2016-06-27T05:51:33.703

You post that comment a lot, so maybe you should make the bytes like clearer (for example: [bytes](link-to-byes) (not UTF-8). – NoOneIsHere – 2017-11-30T21:01:49.757

12

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].

Sp3000

Posted 2016-06-26T00:00:55.153

Reputation: 58 729

11

Python 2, 43 bytes

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

Test it on Ideone.

Dennis

Posted 2016-06-26T00:00:55.153

Reputation: 196 637

6

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

Luis Mendo

Posted 2016-06-26T00:00:55.153

Reputation: 87 464

4

Julia, 32 bytes

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

Try it online!

Dennis

Posted 2016-06-26T00:00:55.153

Reputation: 196 637

2

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}}] &

DavidC

Posted 2016-06-26T00:00:55.153

Reputation: 24 524

1

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.

Backerupper

Posted 2016-06-26T00:00:55.153

Reputation: 41

1

Pyth, 15 bytes

/Q^
ef!%Q^T2SQ2

Test suite.

Leaky Nun

Posted 2016-06-26T00:00:55.153

Reputation: 45 011

1

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

pajonk

Posted 2016-06-26T00:00:55.153

Reputation: 2 480

1

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.

Michał Perłakowski

Posted 2016-06-26T00:00:55.153

Reputation: 520

1

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

Damien

Posted 2016-06-26T00:00:55.153

Reputation: 2 407

Nice solution, I like how it doesn't use mod or div. I think you can do y<-[1..] due to laziness. – xnor – 2016-06-27T11:02:32.307

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? – Damien – 2016-06-27T12:06:02.303

1

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

Emigna

Posted 2016-06-26T00:00:55.153

Reputation: 50 798

0

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]

l4m2

Posted 2016-06-26T00:00:55.153

Reputation: 5 985

0

J, 19 bytes

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

Try it online!

Same as the Jelly solution.

FrownyFrog

Posted 2016-06-26T00:00:55.153

Reputation: 3 112

0

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)

Swadhikar C

Posted 2016-06-26T00:00:55.153

Reputation: 141

1

Please attempt to golf your answer as much as possible, this is a code-golf

– caird coinheringaahing – 2017-11-30T18:50:20.347

0

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

lstefano

Posted 2016-06-26T00:00:55.153

Reputation: 850

Asked: 2016-06-26T00:00:55.153

Viewed: 2 427 times

Active: 2017-12-01T03:41:20.607