Whole-number powers

Question

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>

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

Pyth, 11 10 12 bytes

fsmqQ^dTSQSQ

Checks all possible combinations of powers. Very slow.

Answer 6

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 2⁶³ - 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.

Answer 7

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)

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

05AB1E, 3 bytes

Ó¿Ñ

Try it online!

Port of Unrelated String’s Jelly answer.

Ó       # exponents in the prime factorization
 ¿      # gcd
  Ñ     # divisors

Answer 12

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.

Answer 13

CJam, 20 bytes

ri_,1df+\1$fmL9fmO&p

For input n, this computes log_b 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.

Answer 14

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.

Answer 15

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.

Answer 16

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)

Answer 17

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!

Answer 18

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!

Answer 19

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