7
\$\begingroup\$

Input

An integer \$n\$ greater than or equal to 1.

Output

The number of bits in the binary representation of the integer that is the product of the first \$n\$ primes.

Example

The product of the first two primes is 6. This needs 3 bits to represent it.

Given unlimited memory and time your code should always output the correct value for n <= 1000000.

\$\endgroup\$
6
  • 4
    \$\begingroup\$ That would be A045716 :-) \$\endgroup\$
    – Giuseppe
    Commented Jul 30, 2023 at 12:19
  • 1
    \$\begingroup\$ @Giuseppe Except that the first term is different (must be 2 here instead of 1). \$\endgroup\$
    – Bubbler
    Commented Jul 30, 2023 at 22:51
  • 2
    \$\begingroup\$ I'm inclined to close this as a dupe of sum of first n primes (which was the closest to "calculate first n primes" I could find) and bit length of n, since the two are the necessary building blocks and there is no way to avoid them. \$\endgroup\$
    – Bubbler
    Commented Jul 30, 2023 at 23:43
  • 1
    \$\begingroup\$ @Bubbler: The bit-length Q&A is "for any positive 32-bit integer". This question requires BigInt. It's only a duplicate if you limit this question to languages where the native integer type is a BigInt, or where one works as a drop-in replacement including for bit-scan functions. A machine-code answer to that question is trivial (4 bytes for x86, for a bsr bit-scan reverse + ret), but would take much more work for this question. (You could approximate the answer by summing bit-lengths (logs) of each prime, but low bits can make the difference between carry-out to a new bit-pos.) \$\endgroup\$ Commented Aug 1, 2023 at 17:48
  • 1
    \$\begingroup\$ @Bubbler If you look, for example, at dingledooper's answer you'll find at least one nontrivial synergy that is unique to the combined task: Using the primorial instead of the more common (squared) factorial to generate the prime numbers. \$\endgroup\$
    – loopy walt
    Commented Aug 1, 2023 at 18:34

19 Answers 19

8
\$\begingroup\$

Factor, 24 bytes

[ primorial bit-length ]

Try it online!

primorial  ! get the primorial of the input
bit-length ! how many bits does it have?
\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES12), 75 bytes

-1 byte thanks to @tsh

Expects a BigInt.

n=>eval("for(p=k=1n;p;d?0:p*=n--&&k)for(d=k++;k%d--;)p.toString(2).length")

Try it online!


JavaScript (ES12), 76 bytes

n=>eval("for(p=k=1n;n;d?0:p*=n--&&k)for(d=k++;k%d--;);p.toString(2).length")

Try it online!

Commented

This is a version without eval() for readability.

n => {                 // n = input
  for(                 // outer loop:
    p =                //   p = product
    k = 1n;            //   k = current prime candidate
    n;                 //   stop when n = 0
    d ?                //   if d is not 0:
      0                //     do nothing
    :                  //   else:
      p *= n-- && k    //     decrement n and multiply p by k
  )                    //
    for(               //   inner loop:
      d = k++;         //     start with d = k and increment k
      k % d--;         //     decrement d until it divides k
    );                 //
  return p.toString(2) // convert the final product to base 2
         .length       // and return the length
}                      //
\$\endgroup\$
5
  • \$\begingroup\$ I naively thought that you had to use bigint for big ints in JavaScript! \$\endgroup\$
    – Simd
    Commented Jul 30, 2023 at 10:55
  • 1
    \$\begingroup\$ @Simd but 1n is a bigint... \$\endgroup\$
    – Neil
    Commented Jul 30, 2023 at 13:05
  • \$\begingroup\$ @Neil Ah, thanks. \$\endgroup\$
    – Simd
    Commented Jul 30, 2023 at 13:05
  • 2
    \$\begingroup\$ n=>eval("for(p=k=1n;p;d?0:p*=n--&&k)for(d=k++;k%d--;)p.toString(2).length") with input changed to bigint. \$\endgroup\$
    – tsh
    Commented Jul 30, 2023 at 13:24
  • 1
    \$\begingroup\$ For those wondering why not to do a tagged template (mdn) (i.e. n=>eval`...`) is because "If the argument of eval() is not a string, eval() returns the argument unchanged." (mdn) and a tagged template literal passes in an Array as the first argument (not a string primitive) \$\endgroup\$ Commented Aug 1, 2023 at 14:48
6
\$\begingroup\$

Jelly, 5 bytes

Ẓ#PBL

A full program that accepts an integer from STDIN that prints the result.

Try it online!

How?

Straight forward, just saving a byte over the monadic Link ÆN€PBL

Ẓ#PBL - Main Link: no arguments
 #    - starting at {implict k=0} find the first {STDIN} k for which:
Ẓ     -   is prime?
  P   - product
   B  - to binary
    L - length
\$\endgroup\$
3
  • \$\begingroup\$ Pretty fast too! \$\endgroup\$
    – Simd
    Commented Jul 30, 2023 at 15:16
  • 2
    \$\begingroup\$ Uses sympy under the hood. Will get slower as the input increases as it is testing every single integer for primality. I don't really understand why ÆN€PBL is so much slower for small inputs, I would have thought calling lambda z: sympy.ntheory.generate.prime(z) for [1..input] would be as fast or faster than repeating lambda z: int(sympy.primetest.isprime(z)) for each number until input primes are found. Perhaps it's not using the same hardcoded lookup for small primes. \$\endgroup\$ Commented Jul 30, 2023 at 15:28
  • 2
    \$\begingroup\$ Ẓ# is a clever replacement for ÆN€, nice! \$\endgroup\$ Commented Jul 30, 2023 at 16:13
6
\$\begingroup\$

PARI/GP, 30 bytes

n->#binary(vecprod(primes(n)))

Attempt This Online!

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

Python, 70 bytes

f=lambda n,x=1,i=1:n and f(n-(b:=x**i%i>0),x*i**b,i+1)or len(bin(x))-2

Try it online!

The idea is that if x is the product of every prime number up to n, then the next prime number must not share any prime factors with x. This is done by calculating the first i greater than n such that x**i%i>0. This works because if i isn't the next prime, all of its prime factors are below n, so it will easily divide x**i. Raising x to the ith power makes sure that prime powers are also caught, since x by itself only contains each prime factor once.

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

Vyxal, 34 bitsv2, 4.25 bytes

ʁǎΠbL

Try it Online!

Very simple

Explained

ʁǎΠbL­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌­
ʁǎ     # ‎⁡A list of the first n primes
  Π    # ‎⁢Take the product of that
   bL  # ‎⁣And get the length of the binary representation
💎

Created with the help of Luminespire.

\$\endgroup\$
2
  • \$\begingroup\$ 357 is the largest input value that works on your TIO link. \$\endgroup\$
    – Simd
    Commented Jul 30, 2023 at 10:49
  • 3
    \$\begingroup\$ @Simd that's because it times out after 10 seconds (by design). You can use the T flag to up the time out to 60 seconds or use the offline interpreter for unlimited time. \$\endgroup\$
    – lyxal
    Commented Jul 30, 2023 at 11:20
4
\$\begingroup\$

Arturo, 58 bytes

$=>[0x:∏select.first:&2..∞=>prime? while->x>0[1+'x/2]]

Unfortunately, I have to count bits by counting how many halvings it takes to get to zero since both log and as.binary no longer work properly once values get into bignum territory. Perhaps there is a smarter way...?

Try it!

$=>[                ; a function where input is assigned to &
    0               ; push 0 -- we'll use this to count bits later
    x:              ; to x, assign...
    ∏               ; product of
    select.first:&  ; the first <input> number of
    2..∞=>prime?    ; prime numbers in [2..∞]
    while->x>0[     ; while x is greater than zero...
        1+          ; increment our bit count
        'x/2        ; divide x by two in place
    ]               ; end while
]                   ; end function
\$\endgroup\$
4
\$\begingroup\$

Ruby -rprime, 39 bytes

->n{'%b'%Prime.take(n).inject(:*)=~/$/}

Attempt This Online!

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

Pari/GP, 26 bytes

-3 Thanks to alephalpha:

n->#binary(lcm(primes(n)))

Try it online!

Pari/GP, 29 bytes (original)

n->logint(lcm(primes(n)),2)+1

Try it online!

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

MATLAB, 35 bytes

upd. use nthprime instead of primes(n)(get all primes up to n)

@(n)ceil(log2(prod(nthprime(1:n))))

Full code with test cases:

f=...
@(n)ceil(log2(prod(nthprime(1:n))));
disp(arrayfun(f,1:57));
\$\endgroup\$
2
  • 1
    \$\begingroup\$ What's the 300? \$\endgroup\$
    – l4m2
    Commented Aug 1, 2023 at 9:40
  • \$\begingroup\$ It needs to take arbitrary input, not just the number 300. \$\endgroup\$
    – Someone
    Commented Aug 1, 2023 at 21:51
3
\$\begingroup\$

05AB1E, 5 bytes

ÅpPbg

Try it online!

Explanation

ÅpPbg  # Implicit input
Åp     # First n primes
  P    # Product
   b   # To binary
    g  # Take the length
       # Implicit output
\$\endgroup\$
3
\$\begingroup\$

Rust + num + num-prime, 59 bytes

|n|num_prime::nt_funcs::primorial::<num::BigUint>(n).bits()
\$\endgroup\$
3
  • \$\begingroup\$ Does BigUint have a limit to how large an int it can handle? \$\endgroup\$
    – Simd
    Commented Jul 31, 2023 at 17:55
  • 1
    \$\begingroup\$ @Simd It's arbitrarily large \$\endgroup\$
    – corvus_192
    Commented Jul 31, 2023 at 18:00
  • \$\begingroup\$ How can BigUInt exist and how would it do 0-1? \$\endgroup\$
    – l4m2
    Commented Aug 2, 2023 at 3:21
3
\$\begingroup\$

Excel, 98 94 92 bytes

2 bytes saved thanks to Taylor Alex Raine

=LET(
    a,ROW(1:99),
    LEN(BASE(PRODUCT(TAKE(FILTER(a,MMULT(N(MOD(a,TOROW(a))=0),a^0)=2),A1)),2))
)

Input in cell A1.

Fails for A1>13.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ use 1:99 for -2 bytes \$\endgroup\$ Commented Aug 10, 2023 at 19:03
3
\$\begingroup\$

Thunno 2 L, 4 bytes

Æppḃ

Try it online!

Explanation

Æppḃ  # Implicit input
Æp    # First n primes
  p   # Product
   ḃ  # To binary
      # Take the length
      # Implicit output
\$\endgroup\$
2
\$\begingroup\$

J, 18 bytes

f=:3 :'##:*/p:i.y'

Try it online!

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

Charcoal, 26 bytes

Nθ→→W‹Lυθ¿⬤υ﹪ⅈκ⊞υⅈM→IL↨Πυ²

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

Nθ

Input n.

→→

Start searching for primes at 2.

W‹Lυθ

Stop when n primes have been found.

¿⬤υ﹪ⅈκ

If none of the primes found so far is a factor of the current value, then...

⊞υⅈ

... push the current value to the list of primes.

M→

Otherwise increment the current value. (Note that after a prime is pushed, the value is not immediately incremented, but if more primes are needed then it will "fail" the divisibility test and get incremented that way.)

IL↨Πυ²

Output the length of the base 2 representation of the product.

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

Python, 67 bytes

f=lambda N,P=1,p=1:len(-N*f"{P:b}")or f(N-P**p%-~p,P-P**p%~p*P,p+1)

Attempt This Online!

Disclaimer: This one has one flaw which is that it is "zero-based" which is stretching the rules, I suppose. But I'd still very much like to show it off.

Obviousy, this is heavily based on @dingledooper's answer.

How?

This leverages a bit of elementary number theory, i.e. Fermat's little theorem, to squeeze out a few bytes.

The basic strategy is the same as dingledooper's: Use the nascent primorial to identify the next prime.What we do differently is when testing the next prime number candidate \$p\$ we raise the primorial \$P\$ to one less power, \$P^{p-1}\mod p\$ instead of \$P^p \mod p\$ That way we know the value can only be \$1\$ (iff \$p\$ is indeed a prime) or \$0\$. The value can, for example, directly be used to decrement the prime number counter. The conditional update of the primorial is also streamlined.

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

JavaScript (Node.js), 74 bytes

n=>eval("for(i=s=p=1;n;s*=j?1:n--&&i)for(j=i++;s*i<2?i%j--:[++p,s/=2];)p")

Try it online!

Little RAM. Assumes n#(Product of first n primes) don't get too near to \$2^k\$ and therefore need confirm.

JavaScript (Node.js), 73 bytes basically by Arnauld

n=>eval("for(p=k=i=1n;n;d?0:p*=n--&&k)for(d=k++;k%d--;);for(;p/=2n;)++i")

Try it online!

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

Wolfram Language (Mathematica), 45 bytes

Try it online!

Length@IntegerDigits[Times@@Prime~Array~#,2]&
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.