An integer \$n\$ greater than or equal to 1.
The number of bits in the binary representation of the integer that is the product of the first \$n\$ primes.
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.
[ primorial bit-length ]
primorial ! get the primorial of the input
bit-length ! how many bits does it have?
-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")
n=>eval("for(p=k=1n;n;d?0:p*=n--&&k)for(d=k++;k%d--;);p.toString(2).length")
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
} //
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\$
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
Ẓ#PBL
A full program that accepts an integer from STDIN that prints the result.
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
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
Ẓ# is a clever replacement for ÆN€, nice!
\$\endgroup\$
Commented
Jul 30, 2023 at 16:13
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
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.
ʁǎΠbL
Very simple
ʁǎΠ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.
T flag to up the time out to 60 seconds or use the offline interpreter for unlimited time.
\$\endgroup\$
$=>[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...?
$=>[ ; 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
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));
|n|num_prime::nt_funcs::primorial::<num::BigUint>(n).bits()
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.
Ｎθ→→Ｗ‹Ｌυθ¿⬤υ﹪ⅈκ⊞υⅈＭ→ＩＬ↨Πυ²
Try it online! Link is to verbose version of code. Explanation:
Ｎθ
Input n.
→→
Start searching for primes at 2.
Ｗ‹Ｌυθ
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.
Ｍ→
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.)
ＩＬ↨Πυ²
Output the length of the base 2 representation of the product.
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)
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.
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.
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")
Little RAM. Assumes n#(Product of first n primes) don't get too near to \$2^k\$ and therefore need confirm.
n=>eval("for(p=k=i=1n;n;d?0:p*=n--&&k)for(d=k++;k%d--;);for(;p/=2n;)++i")
Length@IntegerDigits[Times@@Prime~Array~#,2]&
bsrbit-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\$