Reconstruct an integer from its prime exponents

Question

All integers \$n > 0\$ can be expressed in the form

$$n = \prod_{\text{prime } p} p^e = 2^{e_2} 3^{e_3} 5^{e_5} 7^{e_7} \cdots$$

This form is also known as it's prime factorisation or prime decomposition, and each integer has a unique prime factorisation.

As the bases are fixed, it is possible to reconstruct an integer when just given a list of the exponents of it's prime factorisation. For example, given \$E = [0,3,2,1,0,2]\$ we can reconstruct \$n\$ as

$$ \begin{align} n & = 2^0 3^3 5^2 7^1 11^0 13^2 \\ & = 1 \cdot 27 \cdot 25 \cdot 7 \cdot 1 \cdot 169 \\ & = 798525 \end{align} $$

Therefore, \$[0,3,2,1,0,2] \to 798525\$, and is the only such list (ignoring trailing zeros) that does so.

You are to take an input consisting of non-negative integers representing the exponents of the prime factorisation of some integer and output the integer with that prime factorisation.

Both the integer and the elements of the input will be within the bounds of your language, and you can take input in any convenient method. You may have an arbitrary (from 0 to infinite) number of trailing zeros in the input. The array will never be empty, but may be [0]

This is code-golf so the shortest code in bytes wins

Test cases

[0] -> 1
[1] -> 2
[3, 2] -> 72
[0, 1, 2] -> 75
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] -> 347
[6, 2] -> 576
[1, 7] -> 4374
[5, 7] -> 69984
[10, 5] -> 248832
[1, 0, 0, 8, 4] -> 168804902882
[3, 8, 10] -> 512578125000
[7, 9, 0, 8] -> 14523977994624
[4, 4, 7, 0, 0, 5, 5] -> 53377275216476250000
[1, 8, 1, 7, 8, 1] -> 150570936449966222190
[10, 0, 2, 8, 9] -> 347983339699826969600
[4, 8, 2, 3, 7, 9] -> 186021488852335961308083600
[7, 6, 6, 8, 6, 8, 4] -> 1014472920935186644572261278658000000
[9, 6, 7, 5, 1, 8, 10] -> 8865565384329431006794755470280000000

Answer 1

Python 2, 61 bytes

Wilson's theroem FTW!

f=lambda p,a=1,b=1:p==[]or b**(a%b*p[0])*f(p[a%b:],a*b*b,b+1)

Try it online!

Python 2, 62 bytes

f=lambda p,a=1,b=1:p==[]or(a%b<1or b**p.pop(0))*f(p,a*b*b,b+1)

Try it online!

Answer 2

J, ¹³ 7 bytes

_&q:inv

Try it online!

As described here, the verb _ q: n returns the prime exponents of n. So the inverse inv of that verb is exactly what we want.

Answer 3

Wolfram Language (Mathematica), 28 bytes

1##&@@(i=0;Prime@++i^#&/@#)&

Try it online!

Answer 4

Jelly, 2 bytes

ÆẸ

Try it online!

Just the builtin.

Jelly, 6 bytes

JÆN*µP

Try it online!

If those brownie points are attainable, it's going to be hard!

 ÆN       n-th prime
J         for each n in 1 .. len(input).
   *      Raise each prime to the corresponding exponent,
    µ     then
     P    output the product.

Answer 5

Factor + math.primes, 43 bytes

[| x | 1 x length nprimes x [ ^ * ] 2each ]

-3 from Leo

Try it online!

Answer 6

Factor + math.primes math.unicode, 38 33 bytes

[ dup length nprimes swap v^ Π ]

Try it online! Explanation:

• dup duplicate the input (e.g.) { 0 1 2 3 } { 0 1 2 3 }
• length find the length of a sequence { 0 1 2 3 } 4
• nprimes generate primes given the number on top of the data stack { 0 1 2 3 } { 2 3 5 7 }
• swap swap the top two objects on the data stack { 2 3 5 7 } { 0 1 2 3 }
• v^ vector exponentiation (component-wise) { 1 3 25 343 }
• Π find the product of a sequence 25725

Factor + math.primes math.unicode, 38 33 bytes

[ [ length nprimes ] keep v^ Π ]

An equivalent answer using the data flow combinator keep instead of stack shufflers. Data flow combinators generally keep the data stack more static and easier to reason about than stack shufflers.

Try it online!

Answer 7

Vyxal r, 4 bytes

ẏǎeΠ

Try it Online!

ẏǎeΠ
ẏ     # range(0, len(input))
 ǎ    # nth_prime(^) // vectorises
  e   # ^ ** input // vectorises element-wise
   Π  # product(^)

The r flag tells Vyxal to pass arguments to built-ins in reverse order. It's been around before this challenge, so I didn't add it to cheat this one time. Without it, this would be 5 bytes (ẏǎ$eΠ)

Answer 8

Husk, 6 bytes

Πz`^İp

Try it online!

Explanation

Πz`^İp implicit input
 z     zip the input
    İp with the infinite list of primes, removing extras
   ^   using the power function,
  `    with flipped arguments.
Π      take its product.

Answer 9

R, 83 82 79 78 68 bytes

Edit: -4 bytes thanks to Kirill L. and -1 byte thanks to Robin Ryder.

function(l,p=1){for(i in l){while(sum(!(T=T+1)%%2:T)-1)1;p=p*T^i};p}

Try it online!

Loops over the list l of prime exponents, each time using while(sum(!(T=T+1)%%2:T)-1)1 to update T to the next prime, and multiplying the cumulative product p (initialized to 1) by T to the power of the current exponent. Finally, returns p.

Answer 10

Brachylog, 13 bytes

wᵐ<₁ṗᵐ≜;?z^ᵐ×

Try it online!

Function submission which dumps some garbage to STDOUT since it saves a byte over l~l<₁ṗᵐ≜;?z^ᵐ× or ∧ċ<₁ṗᵐ;?z₂≜^ᵐ×.

wᵐ               Create a list of unbound variables with the same length as the input.
                 (This also prints each element, but that's besides the point.)
  <₁             This list is strictly increasing,
    ṗᵐ           and each of its elements is prime.
      ≜          Assign a value to each element.
       ;?z^ᵐ     Raise each prime to the power of the corresponding element of the input,
            ×    and output the product of the powers.

Without the ≜, it completely breaks given exponents of zero--I suppose because they are mathematically eliminated from the final product?

Answer 11

Japt, 11 bytes

í!pÈj}jUl¹×

Try it

Answer 12

JavaScript, 91 86 84 bytes

a=>{p=[],r=1;for(i=2;0 in a;i++)r*=p.every(x=>i%x)?i**a.shift(p.push(i)):1;return r}

Try it online!

Saved 2 bytes thanks to Neil

Explanation

a=>{
  p=[],//array of primes
  r=1;//product/result
  for(i=2;
     0 in a;
    //if 0 exists as a key in the array, then the first element exists 
    //and it is not empty
    i++)
    r*=
       p.every(x=>i%x)?
      //check if there is a remainder after division with each previous prime
      //if so, then i is prime
         i**a.shift(
            p.push(i)//add to prime array, (shift ignores all arguments)
         ) 
         //multiply result by i to the power of the first 
         //input array element (and remove it)
    :1; //multiply by 1 if i is not prime
    return r 
}

Answer 13

Haskell, 83 69 57 bytes

Thanks to thanks to @AZTECCO and @Unrelated String for bringing it down to 57 bytes :)

f=product.zipWith(^)(s[2..])
s(x:t)=x:s[y|y<-t,y`mod`x>0]

Try it Online!

Edit: Realised that newlines are also one byte so putting multiple lines on a single line with semicolons doesn't change the size.

Edit #2: Realised that I don't need to take (length x) to my list of primes, zipWith only takes how many it needs to.

Edit #3: Reduced to 57 bytes, thanks to thanks to @AZTECCO and @Unrelated String (See Comments)

Explanation:

(My solution wasn't very difficult to understand but I'm a beginner with Haskell so writing this out helps me xD)

A more readable version would be:

sieve (x:xs) = x:sieve [y | y<-xs, y `mod` x > 0]
primes = sieve [2..]
applyExponents x = zipWith (^) primes x
reconstruct = product . applyExponents 

Recursive function used to generate a list of primes---use list comprehension to remove multiples of the last prime inserted into the list.

sieve (x:xs) = x:sieve [y | y<-xs, y `mod` x > 0]

Apply recursive sieve function to an infinite list of natural numbers from 2 onwards to get an infinite list of primes.

primes = sieve [2..]

Use take (length x) to evaluate the list of primes and get the right number of prime numbers for the length of list x. Use zipWith to apply the correct exponent to each prime number.

applyExponents x = zipWith (^) p x

Then use product to multiply the list resulting from the previous step together.

reconstruct = product . applyExponents 

Answer 14

C (gcc), ^{110 \$\cdots\$ 79} 75 bytes

Saved 5 9 bytes thanks to xibu!!!

d;p;r;f(a,l)int*a;{for(r=p=1;l;r*=pow(p,d<2?l--,*a++:0))for(d=++p;p%--d;);}

Try it online!

Inputs an array of prime exponents and its length \$l\$ (because C arrays have undefined length) and returns the product of the first \$l\$ primes to those exponents.

Explanation (before some golfs)

d;p;r;f(a,l)int*a;{                           // function taking an array of  
                                              // ints and its length l
  for(r=p=1;l--;                              // loop over the array elements  
                                              // setting the product r and  
                                              // the previous prime to 1  
                r*=pow(p,*a++)                // once we've found the next  
                                              // prime multiply r by it  
                                              // to the power of the current  
                                              // value in a    
    for(d=2;d>1;)                             // loop until we find the next  
                                              // prime, d==1 will flag this  
      for(d=++p;                              // set d to p bumped  
                p%--d;)                       // bump d down and loop  
                                              // until we find the highest                      
                                              // divisor of p    
  d=r;                                        // return r
}                                             //   

Answer 15

PowerShell, 106 bytes

$s=1;while($n-lt$a.length){if(('1'*(++$i))-notmatch'^1?$|^(11+?)\1+$'){$s*=[math]::pow($i,$a[($n++)])}};$s

Try it online!

Uses a regex to match prime numbers, more about it here

Answer 16

05AB1E, 6 2 bytes

.Ó

Try it online!

.Ó  # full program
.Ó  # push the number with a prime factorization with exponents in...
    # implicit input
    # implicit output

Answer 17

Raku, 31 bytes

{[*] grep(&is-prime,^∞)Z**$_}

Try it online!

grep(&is-prime, ^∞) is an infinite, lazy sequence of primes. Z** zips that sequence with $_, the list argument to the function, using exponentiation. Then [*] computes the product of that sequence.

Answer 18

Haskell, 61 56 bytes

f=product.zipWith(^)[x|x<-[2..],all((>0).rem x)[2..x-1]]

Try it online!

• saved 5 by stealing @Unrelated String advice to @M. Salman Khan answer.

Answer 19

APL (Dyalog Extended), 12 11 bytes

-1 thanks to Adám

⊢×.*⍨¯2⍭⍳∘≢

⊢×.*⍨¯2⍭⍳∘≢
     ¯2⍭⍳∘≢  ⍝ the first n primes
⊢×.*⍨        ⍝ powers and product

Try it online!

Answer 20

JavaScript (ES7),  64  58 bytes

a=>(g=d=>a+a?n%--d?g(d):(d>1||n**a.shift())*g(++n):1)(n=2)

Try it online!

With BigInts, 61 bytes

A version that supports large integers. Expects a list of BigInts.

a=>(g=d=>a+a?n%--d?g(d):(d<2?d:n**a.shift())*g(++n):1n)(n=2n)

Try it online!

Commented

a => (                 // a[] = input array
  g = d =>             // g is a recursive function taking a divisor d
  a + a ?              // if a[] is not empty:
    n % --d ?          //   decrement d; if it's not a divisor of n:
      g(d)             //     do recursive calls until it is
    :                  //   else:
      (                //     multiply the final result by:
        d > 1 ||       //     - 1 if d is greater than 1 (n is composite)
        n ** a.shift() //     - the prime n raised to the power of the next
      )                //       exponent extracted from a[] otherwise
      * g(++n)         //     and multiply by the result of a recursive call
                       //     with n + 1
  :                    // else:
    1                  //   stop the recursion and return 1
)(n = 2)               // initial call to g with d = n = 2

Answer 21

Charcoal, 29 bytes

≔¹ζＦＡ«≦⊕ζＷ﹪⊕Π…¹ζζ≦⊕ζ⊞υＸζι»ＩΠυ

Try it online! Link is to verbose version of code. Explanation:

≔¹ζ

Start finding prime numbers.

ＦＡ«

Loop over the input list.

≦⊕ζＷ﹪⊕Π…¹ζζ≦⊕ζ

Increment the integer it until it's prime via Wilson's theorem.

⊞υＸζι

Take the appropriate prime power.

»ＩΠυ

Print the product of the resulting prime powers.

Answer 22

05AB1E, 6 bytes

ā<ØsmP

Try it online!

In other words:

P         sm        Ø                 ā                   <
product(exponate(nth_prime_number(range(1, len(input())) - 1), input()))

Answer 23

Japt, 11 bytes

£Èj}iY pXÃ×
£           // Map the input array with X as items and Y as indexes to
 È }iY      // Y-th positive number
  j         // that is prime
       pX   // to the power of X,
         Ã× // then reduce with multiplication.

Try it out here.

Answer 24

Retina, 83 bytes

$
,__
m)+`,(_+)$(?<=\1¶.+)|,(__+)\2+$
$&_
~["L$`^¶$.("|""]'_L$`(.+),(_+)
$1*$($.2$*

Try it online! Takes a newline-separated list. Explanation:

$
,__

Pair each element of the input array with 2 in unary.

+`,(_+)$(?<=\1¶.+)|,(__+)\2+$
$&_

Increment each unary part until it is a prime greater than the previous one.

m)`

Turn on per-line $ for all of the stages up to and including the above.

["L$`^¶$.("|""]'_L$`(.+),(_+)
$1*$($.2$*

Transform each pair into a repeated multiplication, so that for example 3,__ becomes three copies of 2* i.e. 2*2*2* while 2,___ becomes two copies of 3* i.e. 3*3*. Append a _ to handle the case of zero input, and prepend L$`^ and $.( to create a Retina program that replaces the current value with the total product.

~`

Evaluate that Retina program. For example, in the case of an input of 3 2, the resulting program is as follows:

L$`^
$.(2*2*2*3*3*_

3*_ is $(___) and so on, with $.( taking the final length in decimal (Retina actually optimises this and simply multiplies the values together).

Answer 25

R+primes, 46 43 bytes

Exploiting the primes library

prod(primes::nth_prime(seq(a=l<-scan()))^l)

Don't try it online! (as primes is not recognised by tio.run, apparently) Here is the output on rrdr.io:

prod(primes::nth_prime(seq(a=l<-scan()))^l)
0 0 0 0 1
Read 5 items
[1] 11

prod(primes::nth_prime(seq(a=l<-scan()))^l)
2 3 1 0 0 1
Read 6 items
[1] 7020

prod(primes::nth_prime(seq(a=l<-scan()))^l)
9 0 0 1 0 0 2
Read 7 items
[1] 1035776

Answer 26

Ruby -rprime, 54 37 bytes

A whopping 17 bytes off by Sisyphus.

->x{c=1;x.zip(Prime){|a,b|c*=b**a};c}

Try it online!

Answer 27

Wolfram Language (Mathematica), 29 bytes

(i=s=1;s*=Prime@i++^#&/@#;s)&

Try it online!

One character longer than @att's solution but maybe it has potential for golfing down.