Calculate \$ \lfloor n \log_2(n) \rfloor \$, exactly

Question

Given an integer \$ n \ge 2 \$, you need to calculate \$ \lfloor n \log_2(n) \rfloor \$, assuming all integers in your language are unbounded.

However, you may not ignore floating-point errors - for example, in python lambda n:int(n*math.log2(n)) is an invalid solution, because for example for n=10**15, int(n*math.log2(n)) is 49828921423310432, while the actual answer is 49828921423310435.

Rules

• You can assume the input is an integer \$ n \ge 2 \$
• You may use any reasonable I/O method
• Standard loopholes are disallowed

Test cases

2 -> 2
3 -> 4
4 -> 8
5 -> 11
6 -> 15
7 -> 19
8 -> 24
9 -> 28
10 -> 33
100 -> 664
1000 -> 9965
10000 -> 132877

10 brownie points for beating my 4 byte 05AB1E answer.

This is code golf, so the shortest answer wins. Good luck!

Answer 1

Python 3, 25 bytes

lambda n:len(bin(n**n))-3

Try it online!

If the answer is \$x\$, then \$x+1 > n\log{n} \ge x\$ holds true, which means \$2^{x+1} > n^n \ge 2^x\$. So we can simply count the number of bits in the binary representation of \$n^n\$.

Answer 2

Vyxal, 4 bytes

ebL‹

Try it Online!

Translation of @ManishKundu's Python answer.

Jelly, 5 bytes

*`BL’

Try it online!

Ditto.

Answer 3

Jelly, 4 bytes

*ḃ2L

A monadic Link accepting an integer, \$n>1\$, that yields \$ \lfloor n \log_2(n) \rfloor \$.

Try it online!

How?

As noted by Manish Kundu the answer is one less than the number of binary digits of \$n^n\$.

This can be achieved in Jelly in five bytes in a few ways one of which is: *b2L’.

Note, however, that \$n^n=2^x-1\$ has no integer solutions except \$n=x=1\$ (see Wolfram Alpha*) and that the bijective base two representation of a number always has one less digit than the standard base two representation except when the number is of the form \$2^k-1\$ (when both representations are identical, a string of \$k\$ ones).

Since \$n=1\$ is invalid input we can, therefore, count the number of digits in the bijective base two representation of \$n^n\$.

*ḃ2L - Link: integer, n
*    - (n) exponentiate (n) -> n^n
  2  - two
 ḃ   - (n^n) in bijective base (2)
   L - length

* if someone has a proof, I'll happily put it here!

Answer 4

MATL, 7 bytes

X$tZl*k

Try it online!

X$tZl*k
X$       - sym, implicit input
  t      - duplicate top of stack and push it
   Zl    - log2
     *   - multiply
      k  - floor

This is just what elementiro did except in golfed MATLAB, and since this is my first time posting, I am not sure if this is considered a duplicate.

Answer 5

Ruby, 20 bytes

->n{/.$/=~"%b"%n**n}

Try it online!

Get the length of the binary string representation of n^n. Basically uses the same formula as Manish Kundu and everybody else after him.

Using bit_width or digits(2).size would make it longer.

Answer 6

Julia, 18 24 bytes

n->ndigits(n^n,base=2)-1

Try it online!

port of Manish Kundu's answer

previous answer:

n->floor(log2(n)n)

Try it online!

input needs to be a BigInt to avoid floating point errors.

Technically invalid because you need to augment the precision for very big numbers (with setprecision(2048) for example for 10^100)

Answer 7

JavaScript (Node.js), 30 bytes

Same approach as Manish Kundu.

Expects a BigInt.

n=>(g=n=>n?g(n/2n)+1:-1)(n**n)

Try it online!

Answer 8

Perl 5 -Mbignum -p, 24 bytes

$_=int$_*(1*$_)->blog(2)

Try it online!

Answer 9

Wolfram Language (Mathematica), 17 15 bytes (11 characters)

⌊#*Log2@#⌋&

-2 thanks to ZaMoC!

Try it online!

Answer 10

Charcoal, 10 8 bytes

Ｉ⊖Ｌ↨Ｘθθ²

Try it online! Link is to verbose version of code. Explanation: Uses the same identity \$ \lfloor n \log_2 n \rfloor = \lfloor \log_2 n^n \rfloor \$ as everyone else. (Exponentially slow for large n of course, so stick to 4 digit inputs for testing on TIO.) Edit: Saved 2 bytes thanks to @CommandMaster.

Answer 11

05AB1E (legacy), 4 bytes

mbg<

Try it online!

Answer 12

Pyth, 5 bytes

tl.B^

Test suite

A near literal translation of Manish Kundu's Python 3 answer.

Answer 13

Java, 36 bytes

n->n.pow(n.intValue()).bitLength()-1

Accepts a BigInteger as input.

Try it online!

Answer 14

C (gcc), ^{52 \$\cdots\$35} 23 bytes

Saved 8 bytes thanks to tsh!!!

f(n){n=logb(pow(n,n));}

Try it online!

Uses the formula from Manish Kundu's Python answer.

Answer 15

MATLAB/Octave, 30 bytes

@(x)floor(sym(x)*log2(sym(x)))

Try it online! Anonymous function. The result is symbolic number but can be easily cast to any other type. This solution works as long as the upper bound of int64 allows it.

---

Technically, much better solution is @(x)floor(x*log2((x))) (which is 20 bytes btw) with symbolic input. Since the question says input is integer I couldn't use it though. Because our input is unbounded it works for much much bigger numbers (I managed to calculate 10^{1 000 000} but the calculations took a while and the output in console was truncated, for too big numbers throws an error though). I encourage anyone to check the result for 10³⁰⁰ if their method is capable of working for such big inputs:

f(sym(10^300)) =
 
996578428466208704361095828846817052759449417907374183616426918744780432982587564755041923007811046529897211513075075548047229095279058066482590831899596618155585405797251670592905282757007467500082430012203570937256212532914759940262053756896742020749233906529817764982497756734670715067992925218241378

_{...did I mention unlike some of the other answers this takes only ~0.05s for MATLAB to calculate even for that big inputs?}

Answer 16

Pyt, 5 bytes

ṖɓąŁ⁻

Try it online!

ṖɓąŁ⁻
Ṗ        implicit input (n); raise n to the nth power
 ɓ       convert to binary string
  ąŁ     convert string to array of characters and get length
    ⁻    subtract one; implicit print

Port of Manish Kundu's Python answer