7
\$\begingroup\$

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

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!

\$\endgroup\$
1

14 Answers 14

21
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Have you tested it for big numbers? Because I tried 10^7 (not on the TIO, on the PC), which isn't even that big and the execution took like 2-3 minutes. Does it still work for 10^100 mentioned under other of answers? \$\endgroup\$
    – elementiro
    May 24 at 15:50
  • 10
    \$\begingroup\$ @elementiro This is code golf, so as long as it works in theory the answer is valid. If it fails because of timing out or out-of-memory errors, that's perfectly fine. \$\endgroup\$
    – Jonah
    May 24 at 15:57
5
\$\begingroup\$

Vyxal, 4 bytes

ebL‹

Try it Online!

Translation of @ManishKundu's Python answer.

Jelly, 5 bytes

*`BL’

Try it online!

Ditto.

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

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!

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

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)

\$\endgroup\$
6
  • \$\begingroup\$ The output is wrong for BigInt(10)^100. \$\endgroup\$ May 24 at 14:42
  • \$\begingroup\$ what is the right answer ? \$\endgroup\$
    – MarcMush
    May 24 at 14:46
  • \$\begingroup\$ 3321928094887362347870319429489390175864831393024580612054756395815934776608625215850139743359370155099 \$\endgroup\$ May 24 at 14:51
  • \$\begingroup\$ It will work by increasing the precision, but you can always find a bigger number that won't work Try it online! \$\endgroup\$
    – MarcMush
    May 24 at 15:07
  • \$\begingroup\$ is it ok if I restrict the ouput to Int64 like this ? Try it online! \$\endgroup\$
    – MarcMush
    May 24 at 15:09
1
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ Crashes on 10000 :( \$\endgroup\$
    – user7467
    May 24 at 18:33
  • 2
    \$\begingroup\$ n=>(n**n).toString(2).length-1 seems to work for 10000 for the same byte count. \$\endgroup\$
    – Neil
    May 24 at 18:47
  • 1
    \$\begingroup\$ g(n/2n) <- Another wtf js behavior here \$\endgroup\$
    – tsh
    May 25 at 1:49
1
\$\begingroup\$

Perl 5 -Mbignum -p, 24 bytes

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

Try it online!

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

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.

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

Charcoal, 10 8 bytes

I⊖L↨Xθθ²

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.

\$\endgroup\$
3
  • \$\begingroup\$ Since unary output is allowed by default, can't it be 9 bytes? \$\endgroup\$ May 25 at 4:25
  • \$\begingroup\$ ⊖L↨Xθθ² seems to work for 7 bytes? \$\endgroup\$ May 25 at 4:35
  • \$\begingroup\$ @CommandMaster Huh, I didn't realise that Power casts its arguments to number first, thanks. I don't think unary output is reasonable though (even for Retina I prefer to use decimal I/O when I can). \$\endgroup\$
    – Neil
    May 25 at 8:54
0
\$\begingroup\$

05AB1E (legacy), 4 bytes

mbg<

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Why is this legacy? \$\endgroup\$
    – Makonede
    May 24 at 15:58
  • 1
    \$\begingroup\$ @Makonede It's an old version of the language \$\endgroup\$
    – Luis Mendo
    May 24 at 16:16
  • 1
    \$\begingroup\$ @LuisMendo I know. That's not my question. My question is why use legacy when you can use the rewrite? \$\endgroup\$
    – Makonede
    May 24 at 16:25
  • 1
    \$\begingroup\$ @makonede it doesn't quite matter \$\endgroup\$
    – wasif
    May 24 at 16:25
0
\$\begingroup\$

Pyth, 5 bytes

tl.B^

Test suite

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

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

Java, 36 bytes

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

Accepts a BigInteger as input.

Try it online!

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

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

⌊#*Log2@#⌋&

-2 thanks to ZaMoC!

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ How can you be sure this won't FPE eventually? \$\endgroup\$
    – Makonede
    May 24 at 18:04
  • 1
    \$\begingroup\$ In Mathematica these calculations are exact, no floating-point approximations involved and therefore no overflows and limitations. Just try f[10^10^6] for fun! \$\endgroup\$
    – Roman
    May 24 at 18:08
  • 1
    \$\begingroup\$ 15 bytes \$\endgroup\$
    – ZaMoC
    May 24 at 20:53
0
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ f(n){n=logb(pow(n,n));} \$\endgroup\$
    – tsh
    May 25 at 5:26
  • \$\begingroup\$ @tsh Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    May 25 at 11:49
  • \$\begingroup\$ Isn't pow a floating-point function? \$\endgroup\$ May 26 at 3:37
  • 1
    \$\begingroup\$ @CommandMaster IEEE754 floating point number have more bits for fraction than exponent. And it use binary as its representation. So it always yield correct result as long as pow(n,n) not exceed the limit of the floating point type (not yield +inf). And the same algorithm may be extend to larger IEEE754 floating types such as binary256 (if the compiler support it). The question disallow floating point errors, but not floating point functions. \$\endgroup\$
    – tsh
    May 26 at 7:27
0
\$\begingroup\$

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 101 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 10300 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?

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