23
\$\begingroup\$

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 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
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Brownie points for beating my 6 byte Jelly answer which doesn't use the builtin \$\endgroup\$ – caird coinheringaahing Mar 6 at 1:32

27 Answers 27

13
\$\begingroup\$

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!

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

J, 13 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.

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

Wolfram Language (Mathematica), 28 bytes

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

Try it online!

\$\endgroup\$
7
\$\begingroup\$

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.
\$\endgroup\$
7
+50
\$\begingroup\$

Factor + math.primes, 43 bytes

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

-3 from Leo

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ product is a long word, this can be shorter with 2each: Try it online! \$\endgroup\$ – Leo Mar 10 at 1:43
  • 1
    \$\begingroup\$ @Leo thanks, that's great! \$\endgroup\$ – rak1507 Mar 10 at 1:47
6
\$\begingroup\$

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Π)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is a reallly neat flag. \$\endgroup\$ – Razetime Mar 6 at 7:16
6
\$\begingroup\$

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!

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

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.
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ @KirillL. - That is a super tip! Thanks! The {} was very unsatisfying... \$\endgroup\$ – Dominic van Essen Mar 6 at 15:22
  • \$\begingroup\$ Here's a couple more \$\endgroup\$ – Kirill L. Mar 6 at 16:40
  • \$\begingroup\$ @KirillL. - Thanks again! I don't know what I was thinking with that terrible loop... I've made a slight adjustment to yours (for -> sapply) to make it more R-like, although this didn't save any bytes... \$\endgroup\$ – Dominic van Essen Mar 6 at 21:10
  • 1
    \$\begingroup\$ 78 bytes by changing the condition in the while (the same change applies to the other approach) \$\endgroup\$ – Robin Ryder Mar 6 at 21:39
  • \$\begingroup\$ @RobinRyder - belated thanks! \$\endgroup\$ – Dominic van Essen Mar 7 at 10:36
4
\$\begingroup\$

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?

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

Japt, 11 bytes

í!pÈj}jUl¹×

Try it

\$\endgroup\$
4
\$\begingroup\$

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 
}
\$\endgroup\$
6
  • 1
    \$\begingroup\$ r*=p.every(x=>i%x)?i**a.shift(p.push(i)):1; saves a couple of bytes. \$\endgroup\$ – Neil Mar 6 at 11:39
  • \$\begingroup\$ I am learning JavaScript and I enjoyed getting rid of the return, just to do some practice. The result isn't shorter, but anyway I leave it here in case someone knowledgeable is able to make it shorter. (The link is too long, I leave it below) \$\endgroup\$ – Sheik Yerbouti Mar 6 at 14:00
  • \$\begingroup\$ Try it online! \$\endgroup\$ – Sheik Yerbouti Mar 6 at 14:01
  • \$\begingroup\$ @Neil That's clever. Thanks! \$\endgroup\$ – iota Mar 6 at 15:40
  • \$\begingroup\$ @SheikYerbouti 84 bytes \$\endgroup\$ – iota Mar 6 at 15:46
4
\$\begingroup\$

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 
\$\endgroup\$
4
  • 2
    \$\begingroup\$ A few golfs, $ saves 1 bytes by removing (), semicolon not needed, and put s[2..] directly inside f Try it online! \$\endgroup\$ – AZTECCO Mar 6 at 18:14
  • 2
    \$\begingroup\$ Golfed a bit more: product, pointfree f. Try it online! \$\endgroup\$ – Unrelated String Mar 6 at 20:13
  • 2
    \$\begingroup\$ @AZTECCO it seems so obvious now that you said those! I guess I spent so long trying to get it to work that I let a lot slip by me (I'm really new to Haskell). Thanks a lot! :) \$\endgroup\$ – M. Salman Khan Mar 6 at 21:13
  • 1
    \$\begingroup\$ @UnrelatedString I just had to count characters to check that product had less than foldl1! I didn't account for the brackets haha. Also didn't think of function composition to remove the need for the variable in the function that's genius :) Thank you! \$\endgroup\$ – M. Salman Khan Mar 6 at 21:20
4
\$\begingroup\$

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
}                                             //   
\$\endgroup\$
4
  • \$\begingroup\$ -5 Bytes using p^0==1 \$\endgroup\$ – xibu Mar 6 at 23:05
  • \$\begingroup\$ @xibu Nice one - thanks! :D \$\endgroup\$ – Noodle9 Mar 6 at 23:17
  • \$\begingroup\$ I just noticed, that the last expression d=r; is not necessary because the assignment to r is already the last operation in the loop. \$\endgroup\$ – xibu Mar 7 at 0:42
  • \$\begingroup\$ @xibu Well spotted - thanks again! :D \$\endgroup\$ – Noodle9 Mar 7 at 11:58
3
\$\begingroup\$

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

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

05AB1E, 6 2 bytes

Try it online!

.Ó  # full program
.Ó  # push the number with a prime factorization with exponents in...
    # implicit input
    # implicit output
\$\endgroup\$
3
\$\begingroup\$

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.

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

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.
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Extended), 12 11 bytes

-1 thanks to Adám

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

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ is scalar; no need for ¨ \$\endgroup\$ – Adám Mar 6 at 22:14
  • \$\begingroup\$ of course, oops \$\endgroup\$ – rak1507 Mar 6 at 22:18
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 29 bytes

≔¹ζFA«≦⊕ζW﹪⊕Π…¹ζζ≦⊕ζ⊞υXζι»IΠυ

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

≔¹ζ

Start finding prime numbers.

FA«

Loop over the input list.

≦⊕ζW﹪⊕Π…¹ζζ≦⊕ζ

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

⊞υXζι

Take the appropriate prime power.

»IΠυ

Print the product of the resulting prime powers.

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

05AB1E, 6 bytes

ā<ØsmP

Try it online!

In other words:

P         sm        Ø                 ā                   <
product(exponate(nth_prime_number(range(1, len(input())) - 1), input()))
\$\endgroup\$
2
\$\begingroup\$

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.

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

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

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

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think seq(!l) is shorter than 1:sum(1^l). You could also try something like seq(a=l<-scan()) instead to get rid of the leading l=scan(), though I'm not sure that would be shorter or if it would even work. \$\endgroup\$ – Giuseppe Mar 6 at 15:16
  • \$\begingroup\$ @Giuseppe: thank you for the suggestions, both work. \$\endgroup\$ – Xi'an Mar 6 at 20:08
2
\$\begingroup\$

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!

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

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.

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