19
\$\begingroup\$

Some numbers like 64 can be expressed as a whole-number power in multiple ways:

64 ^ 1
 8 ^ 2
 4 ^ 3
 2 ^ 6

Output a sorted array of all possible such powers (here, [1,2,3,6]) in as few bytes as possible.


Input

A positive whole number that's greater than 1 and less than 10000.


Output

An array of whole-number powers p (including 1) for which the input can be expressed as a^p with whole-number a. The outputs may have decimals, as long as they are in order.

Any floating point issues must be handled by the program.


Examples

Input: 3
Output: [1]

Input: 9
Output: [1, 2]

Input: 81
Output: [1, 2, 4]

Input: 729
Output: [1, 2, 3, 6]

Scoreboard

For your score to appear on the board, it should be in this format:

# Language, Bytes

Strikethroughs shouldn't cause a problem.

function getURL(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:getURL(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){var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),useData(answers)}})}function getOwnerName(e){return e.owner.display_name}function useData(e){var s=[];e.forEach(function(e){var a=e.body.replace(/<s>.*<\/s>/,"").replace(/<strike>.*<\/strike>/,"");console.log(a),VALID_HEAD.test(a)&&s.push({user:getOwnerName(e),language:a.match(VALID_HEAD)[1],score:+a.match(VALID_HEAD)[2],link:e.share_link})}),s.sort(function(e,s){var a=e.score,r=s.score;return a-r}),s.forEach(function(e,s){var a=$("#score-template").html();a=a.replace("{{RANK}}",s+1+"").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SCORE}}",e.score),a=$(a),$("#scores").append(a)})}var QUESTION_ID=58047,ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],answer_ids,answers_hash,answer_page=1;getAnswers();var VALID_HEAD=/<h\d>([^\n,]*)[, ]*(\d+).*<\/h\d>/;
body{text-align:left!important}table thead{font-weight:700}table td{padding:10px 0 0 30px}#scores-cont{padding:10px;width:600px}#scores tr td:first-of-type{padding-left:0}
<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="scores-cont"><h2>Scores</h2><table class="score-table"><thead> <tr><td></td><td>User</td><td>Language</td><td>Score</td></tr></thead> <tbody id="scores"></tbody></table></div><table style="display: none"> <tbody id="score-template"><tr><td>{{RANK}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SCORE}}</td></tr></tbody></table>

\$\endgroup\$
  • 1
    \$\begingroup\$ My answer prints [1 2 3 6] for the last test case. Could it also print [6 3 2 1], [1.0 2.0 3.0 6.0] or [6.0 3.0 2.0 1.0]? \$\endgroup\$ – Dennis Sep 16 '15 at 2:35
  • 2
    \$\begingroup\$ What can we assume about input sizes and floating-point arithmetic? This affects the solution where you try to take roots of the number and see if the result is integer. \$\endgroup\$ – xnor Sep 16 '15 at 2:59
  • 4
    \$\begingroup\$ I think the references to roots were confusing everyone, so I rewrote it in terms of powers. Feel free to change things back. \$\endgroup\$ – xnor Sep 16 '15 at 3:43
  • 1
    \$\begingroup\$ I appreciate the edit! Suggestions and revisions are always welcome, provided they improve my question's quality (which I believe yours did). I've only recently started asking questions on this particular network, and find the community generally welcoming. Criticism and correction is much appreciated! @xnor \$\endgroup\$ – Zach Gates Sep 16 '15 at 3:47
  • 1
    \$\begingroup\$ Simply find the largest valid power and then list its factors! \$\endgroup\$ – SuperJedi224 Sep 16 '15 at 10:26

19 Answers 19

10
\$\begingroup\$

Pyth, 10 bytes

f}Q^RTSQSQ

Demonstration

For each power, it generates the list of all numbers up to the input taken to that power, and then checks if the input is in the list.

\$\endgroup\$
10
\$\begingroup\$

Haskell, 38

f n=[b|b<-[1..n],n`elem`map(^b)[1..n]]

Pretty straightforward. The list comprehension finds values of b for which the input n appears among [1^b, 2^b, ..., n^b]. It suffices to check b in the range [1..n].

\$\endgroup\$
9
\$\begingroup\$

Python 2, 53

lambda n:[i/n for i in range(n*n)if(i%n+1)**(i/n)==n]

Brute forces all combinations of bases in exponents in [0, n-1] and bases in [1, n].

\$\endgroup\$
8
\$\begingroup\$

Python 3, 56 bytes

lambda n:[i for i in range(1,n)if round(n**(1/i))**i==n]

This is really clumsy. Tests if each potential i-th root gives an integer by rounding it, taking it the power of i, and checking that it equals to original.

Directly checking that the root is a whole number is tricky because floating points give things like 64**(1/3) == 3.9999999999999996. Rounding it to an integer let us check if taking the power returns to the original value. Thanks to ypercube for suggesting this, saving 1 byte.

feersum has a shorter and more clever solution. You all should really upvote that.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't it be accurate if you checked round(n**(1/i),0)**i==n ? \$\endgroup\$ – ypercubeᵀᴹ Sep 16 '15 at 10:09
  • \$\begingroup\$ @ypercube Good call, together with 0 being the default accuracy for round, this saves a byte. \$\endgroup\$ – xnor Sep 16 '15 at 20:10
7
\$\begingroup\$

Pyth, 11 10 12 bytes

fsmqQ^dTSQSQ

Checks all possible combinations of powers. Very slow.

\$\endgroup\$
5
\$\begingroup\$

CJam, 23 bytes

rimF{1=:E){E\d%!},}%:&p

This works by taking the prime factorization of n and computing the intersection of the divisors of all exponents.

It is a bit longer than my other solution, but I expect it to work (and finish instantly) for all integers between 2 and 263 - 1.

Try it online in the CJam interpreter.

How it works

ri                       Read an integer from STDIN.
  mF                     Push its prime factorization.
    {             }%     For each [prime exponent]:
     1=:E                  Retrieve the exponent and save it in E.
         ){     },         Filter; for each I in [0 ... E]:
           E\d%              Compute E % Double(I).
                             (Casting to Double is required to divide by 0.)
               !             Push the logical NOT of the modulus.
                           Keep I if the result is truhty, i.e., if I divides E.
                    :&   Intersect all resulting arrays of integers.
                      p  Print the resulting array.
\$\endgroup\$
5
\$\begingroup\$

APL, 17 bytes

(X=⌊X←N*÷⍳N)/⍳N←⎕

My first APL program; golfing suggestions are appreciated.

              N←⎕  ⍝ Store input into N
             ⍳     ⍝ The list [1 2 ... N]
            /      ⍝ Select the elements A for which
      N*÷⍳N)       ⍝ N^(1/A)
(X=⌊X←             ⍝ equals its floor (that is, is an integer)
\$\endgroup\$
  • \$\begingroup\$ Please add pseudocode/explanation. But +1 (can't vote right now) for using APL ( - being terse before it was cool) :-) \$\endgroup\$ – mınxomaτ Sep 16 '15 at 3:47
  • \$\begingroup\$ Also +1, much love for APL. Ultimate golfing vehicle. \$\endgroup\$ – user44912 Sep 16 '15 at 3:52
  • \$\begingroup\$ Based on the pseudocode, this is unlikely to work (unless APL performs an approximate floating-point equality test). For example, with pow(pow(7,3),1./3)) I get 6.99999999999999 in C or Python. This is because accuracy is lost when calculating 1/A. \$\endgroup\$ – feersum Sep 16 '15 at 7:14
  • \$\begingroup\$ @feersum I don't know about offline interpreters, but all powers of 3 work correctly on tryapl.org. \$\endgroup\$ – lirtosiast Sep 16 '15 at 15:54
  • \$\begingroup\$ @ThomasKwa It seems that an approximate equality test is indeed used. dyalog.com/uploads/documents/Papers/tolerant_comparison/… \$\endgroup\$ – feersum Sep 16 '15 at 18:25
3
\$\begingroup\$

JavaScript (ES5), 73 bytes 81 bytes 79 bytes 75 bytes

for(n=+prompt(),p=Math.pow,i=0;i++<n;)p(.5+p(n,1/i)|0,i)==n&&console.log(i)

Checks to see if closest integer power of possible root equals n. ~~(.5+...) is equivalent to Math.round(...) for expressions within integer range (0 to 2^31 - 1).

Edit: Used lazy && logic instead of if to shave 2 bytes and added prompt for input since question added a clarification. Was previously assuming input was stored in n.

Edit 2: Changed ~~(.5+...) to .5+...|0 to save two bytes by avoiding grouping.

Edit 3: Removed var to save 4 bytes. In non-strict mode, this is acceptable.

\$\endgroup\$
  • \$\begingroup\$ You can shave a couple bytes by juggling expressions: for(var p=Math.pow,i=1;i++<n;p(~~(.5+p(n,1/i)),i)==n&&console.log(i)); \$\endgroup\$ – user44912 Sep 16 '15 at 3:57
  • \$\begingroup\$ @Alhadis thanks for your input, I'll make an edit in a bit \$\endgroup\$ – Patrick Roberts Sep 16 '15 at 4:02
  • \$\begingroup\$ @PatrickRoberts You could squeeze p=Math.pow into prompt saving 1 byte \$\endgroup\$ – Downgoat Sep 16 '15 at 4:12
  • \$\begingroup\$ @vihan, that would be an invalid declaration, since var is required \$\endgroup\$ – Patrick Roberts Sep 16 '15 at 4:15
  • \$\begingroup\$ Unless you meant for instead of prompt.. \$\endgroup\$ – Patrick Roberts Sep 16 '15 at 4:17
3
\$\begingroup\$

Brachylog, 8 bytes

≥^↙.?≥ℕ≜

Try it online!

Takes input through its input variable and generates each power through its output variable, in ascending order as required, unlike the old solution ≥ℕ≜^↙.?∧ which just so happens to have the exact same length.

≥           Some number which is less than or equal to
            the input,
 ^          when raised to the power of
  ↙.        the output,
    ?       is the input.
       ≜    Label
            the output
      ℕ     as a whole number
     ≥      which is less than or equal to
    ?       the input.

I don't have any rigorous justification for asserting that every exponent is no greater than the input, but in order for the program to actually terminate it needs to be bounded.

ḋḅlᵛf is a far shorter (non-generator) solution for all of the given test cases, but it fails if the input isn't a power of a product of distinct primes. (Come to think of it, since all of the test cases are powers of primes, ḋlf also works...) The best I've come up with to salvage the idea, ḋḅlᵐḋˢ⊇ᵛ×f, comes out to 10 bytes.

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

Jelly, 6 bytes

ÆEg/ÆD

Try it online!

    ÆD    The list of divisors of
ÆE        the exponents in the prime factorization of the input
   /      reduced by
  g       greatest common divisor.
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 3 bytes

Ó¿Ñ

Try it online!

Port of Unrelated String’s Jelly answer.

Ó       # exponents in the prime factorization
 ¿      # gcd
  Ñ     # divisors
\$\endgroup\$
2
\$\begingroup\$

JavaScript ES7, 66 bytes

Takes advantage of experimental array comprehensions. Only works on Firefox.

n=>[for(i of Array(n).keys(m=Math.pow))if(m(0|.5+m(n,1/i),i)==n)i]

Possible golfing. I'll probably try to squish the expressions a little shorter and hopefully find an alternative to the long Array(n).keys() syntax.

Could be shorter but JavaScript has horribly floating point accuracy.

\$\endgroup\$
  • \$\begingroup\$ Ah, learned something new... cool. \$\endgroup\$ – Patrick Roberts Sep 16 '15 at 5:24
2
\$\begingroup\$

CJam, 20 bytes

ri_,1df+\1$fmL9fmO&p

For input n, this computes logb n for all b less or equal to n and keeps the results that are integers.

This should work for all integers between 2 and 9,999. Run time is roughly O(n).

Try it online in the CJam interpreter.

How it works

ri                   e# Read an integer N from STDIN.
  _,                 e# Copy N and transform it into [0 ... N-1].
    1df+             e# Add 1.0 to each, resulting in [1.0 ... Nd].
        \1$          e# Swap the array with N and copy the array.
           fmL       e# Mapped log base N: N [1.0 ... Nd] -> [log1(N) ... logN(N)]
              9fmO   e# Round each logarithm to 9 decimals.
                  &  e# Intersect this array with [1.0 ... Nd].
                   p e# Print the result.
\$\endgroup\$
  • \$\begingroup\$ Is 15,625 the only input on which it fails or is it the only which failed that you tested? \$\endgroup\$ – Beta Decay Sep 16 '15 at 6:09
  • \$\begingroup\$ There are most definitely others. In fact, I just found out that it failed for 4913 as well, which made my previous revision invalid. \$\endgroup\$ – Dennis Sep 16 '15 at 6:17
2
\$\begingroup\$

Ruby, 50

->n{(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||p(i)}}

Prints to screen.

Ruby, 57

->n{a=[]
(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||a<<i}
a}

Returns an array.

In test program:

f=->n{(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||puts(i)}}

g=->n{a=[]
(1..n).map{|i|(n**(1.0/i)+1e-9)%1>1e-8||a<<i}
a}

f.call(4096)
puts g.call(4096)

Calculates each root and tests them modulo 1 to see if the remainder is less than 1e-8. Due to limited precision some valid integer roots are calculated to be the form 0.9999.., hence the need to add 1e-9 to them.

Up to the nth root of n is calculated, which is total overkill, but seemed the shortest way to write a non-infinite loop.

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

Stax, 6 bytes

£ÅeÉåC

Run and debug it

All divisors of the gcd of exponents in the prime factorization. It's the same as the jelly algorithm.

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

DC, 104 bytes

Input is taken from terminal, output is printed and also on the stack.

Because this uses the ? operator, you need to use dc -e "<solution>" or dc <file with solution in it>.

Nobody ever sees my answers, let alone vote on them, but I really just enjoy solving problems in DC. It's the least efficient solution in this thread so far, but I thought I'd post it anyways.

1sb?sn[lesi]ss[lble1+dse^dln=sln>c]sc[liSflq1+sq]sm[Lfplq1-dsq0<p]dsp[lb1+sb0si0selcxli0!=mlbln!=h]dshxx

starter stuff

1sb           Store 1 in register b
?sn           Store user input in register n
[lesi]ss      A macro to copy the e to the i register, stored in the s register

Macro to raise a base to all powers until the result is larger than the target or equal to the target

[lble1+dse^dln=sln>c]sc
[lb                 ]   load our base num (register b)
[  le               ]   load our exponent (register e)
[    1+dse          ]   add 1 to the exponent, copy and store in the e register
[         ^d        ]   raise the base to the exponent and copy it
[           ln=s    ]   load the user input, if that is equal to the power result run the macro in register s
[               ln>c]   load the user input, if it's greater than the power result run the macro in register c (this one)
[                   ]sc save this macro in register c

Macro to save a valid exponent value as found from the above exponent macros to another stack

[liSflq1+sq]sm
[liSf      ]     copy the i register to the top of the stack in register f
[    lq1+sq]     add 1 to the q register
[          ]sm   save this macro in the m register

Macro to run the 2x above macro (macro c) through all bases from 2 to our target number

[lb1+sb0si0selcxli0!=mlbln!=h]dsh
[lb1+sb                      ]     add 1 to the base number
[      0si0se                ]     reset the i and e registers (previously found value and exponent
[            lcx             ]     load and run the c macro
[               li0!=m       ]     load the result of the c macro and if it's not 0, run m to save it to the f stack
[                     lbln!=h]     if our base number is not equal to our target number, run macro h (this macro)
[                            ]dsh  duplicate this macro and save one copy, so that one is left on the stack to run later

Macro to print the values from the f stack

[Lfplq1-dsq0<p]dsp
[Lfp          ]      load the top value from the f register and print it
[   lq1-dsq   ]      load the q register and subtract one from it and save it
[          0<p]      if the q register is greater than 0, run macro p (this macro) again
[             ]dsp   duplicate this macro and save one copy, so that one is left on the stack to run later

xx finally run the two macros on the stack (h and then p)

\$\endgroup\$
  • 1
    \$\begingroup\$ I would guess that not many people know DC. Answering new questions (especially being one of the earliest answers) will help with getting more attention. You might also try using TIO links for your answers, as that's very popular. Here's DC on TIO. \$\endgroup\$ – mbomb007 Jun 19 at 21:09
  • \$\begingroup\$ Thanks! I'll definitely use that for answers going forwards! \$\endgroup\$ – FlexEast Jun 20 at 13:18
1
\$\begingroup\$

Ruby, 46 bytes

Brute force solution. Self-explanatory; for input \$n\$, find all numbers \$e\$ where for some \$b\$, \$b^e=n\$.

->n{(0..n).select{|e|(1..n).find{|b|b**e==n}}}

Try it online!

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

C# (Visual C# Interactive Compiler), 93 bytes

g=n=>Enumerable.Range(1,n);
f=n=>g(n).SelectMany(x=>g(n).Where(y=>(Math.Pow(x,y)==n))).Reverse()

Try it online!

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

Japt, 10 bytes

õ
f@mpX øN

Try it

õ            :Implicit input of integer U
õ            :Range [1,U]
f@mpX øN     :Reassign to U
f            :Filter
 @           :By passing each X through the following function
  m          :  Map U
   pX        :    Raise to the power of X
      ø      :  Contains
       N     :    Any element of the (singelton) array of inputs
\$\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.