# Integer logarithms

Given integers N , P > 1 , find the largest integer M such that P ^ M ≤ N.

### I/O:

Input is given as 2 integers N and P. The output will be the integer M.

### Examples:

4, 5 -> 0
33, 5 -> 2
40, 20 -> 1
242, 3 -> 4
243, 3 -> 5
400, 2 -> 8
1000, 10 -> 3


### Notes:

The input will always be valid, i.e. it will always be integers greater than 1.

### Credits:

Credit for the name goes to @cairdcoinheringaahing. The last 3 examples are by @Nitrodon and credit for improving the description goes to @Giuseppe.

• I know we (the PPCG community) can seem to be overly nit-picky about really small stuff, but comments like mine are really intended, in good faith, to make the challenge better! Now that that's been resolved, I have happily up-voted, and deleted my previous comments. Apr 18, 2018 at 16:26
• That's another reason why we suggest posting challenges into The Sandbox first, so that you can receive helpful feedback, post a great challenge, and get lots of high-quality answers, with much less fuss (like close- and down- votes). :) Apr 18, 2018 at 16:27
• You can always post into the general PPCG Chatroom asking for feedback on your sandbox challenges to get them a bit more attention. Apr 18, 2018 at 16:30
• Almost all of the current answers based on floating-point math produce wrong results even for simple cases like (1000, 10) because of rounding error, so I added another test case. Apr 18, 2018 at 18:23
• @MPW all the responses were deleted, and the suggestions I made were edited into the post, so they were no longer relevant. Apr 19, 2018 at 20:23

# Brain-Flak, 74 bytes

(({}<>)[()])({()<(({})<({([{}]()({}))([{}]({}))}{})>){<>({}[()])}{}>}[()])


Try it online!

This uses the same concept as the standard Brain-Flak positive integer division algorithm.

# Push P and P-1 on other stack
(({}<>)[()])

# Count iterations until N reaches zero:
({()<

# While keeping the current value (P-1)*(P^M) on the stack:
(({})<

# Multiply it by P for the next iteration
({([{}]()({}))([{}]({}))}{})

>)

# Subtract 1 from N and this (P-1)*(P^M) until one of these is zero
{<>({}[()])}{}

# If (P-1)*(P^M) became zero, there is a nonzero value below it on the stack
>}

# Subtract 1 from number of iterations
[()])


# JavaScript (ES6), 22 bytes

Saved 8 bytes thanks to @Neil

Takes input in currying syntax (p)(n).

p=>g=n=>p<=n&&1+g(n/p)


Try it online!

# Excel, 18 bytes

=TRUNC(LOG(A1,A2))


Takes input "n" at A1, and input "p" at A2.

• I think you can use INT function instead of TRUNC to save 2 bytes. Apr 19, 2018 at 7:26

# Jelly, 3 bytes

bḊL


This doesn't use floating-point arithmetic, so there are no precision issues.

Try it online!

### How it works

bḊL  Main link. Left argument: n. Right argument: p

b    Convert n to base p.
Ḋ   Dequeue; remove the first base-p digit.
L  Take the length.


# Retina 0.8.2, 35 bytes

.+
$* +r1*(\2)+¶(1+)$
#$#1$*1¶$2 #  Try it online! Explanation: .+$*


Convert the arguments to unary.

+r1*(\2)+¶(1+)$#$#1$*1¶$2


If the second argument divides the first, replace the first argument with a # plus the integer result, discarding the remainder. Repeat this until the first argument is less than the second.

#


Count the number of times the loop ran.

# Japt, 8 bytes

@<Vp°X}a


Try it

• This is really neat, I haven't really seen a good use for the function methods in Japt yet, this is a good example. Apr 18, 2018 at 18:03
• @Nit, it took me a good while to get to grips with them, too - only recently started figuring out uses for F.g() - but they're incredibly useful. Apr 18, 2018 at 19:12

n!p=until((>n).(p^).(1+))(1+)0


Try it online!

• Either until((>n).(p^))(1+)0-1 or until(\x->p^x*p>n)(1+)0 gets you down to 27 bytes.
– Lynn
Apr 21, 2018 at 5:56

# Perl 6, 13 bytes

&floor∘&log


Try it online!

Concatenation composing log and floor, implicitly has 2 arguments because first function log expects 2. Result is a function.

• For arguments 1000, 10 this returns 2.
– Sean
Apr 18, 2018 at 22:25
• @Sean: Huh, interesting precision issue there Apr 19, 2018 at 20:34

(floor.).logBase


Try it online!

Haskell was designed by mathematicians so it has a nice set of math-related functions in Prelude.

• Doesn't work for (1000, 10) because of rounding error. Apr 18, 2018 at 18:17

# R, 25 bytes

function(p,n)log(p,n)%/%1


Try it online!

Take the log of P base N and do integer division with 1, as it's shorter than floor(). This suffers a bit from numerical precision, so I present the below answer as well, which should not, apart from possibly integer overflow.

# R, 31 bytes

function(p,n)(x=p:0)[n^x<=p][1]


Try it online!

• I don't know how strict the challenge requires us to be on rounding error but for example, f(243,3) is equal to 4 when it probably is required to be 5.
– JDL
Apr 19, 2018 at 8:22
• @JDL that's a fair point; I believe a perfectly precise answer would be ~31 bytes. Apr 19, 2018 at 13:35
• I think you can replace p by p+.1 in the 25 byte answer and you will still be okay, for 28 bytes
– JDL
Apr 19, 2018 at 15:02
• Another 28 byte solution without numerical precision issues. Nov 22, 2019 at 13:24

# Python 2, 39 bytes

lambda a,b:math.log(a,b)//1
import math


Try it online!

• 1000,10 as inputs gives 2 as output. Apr 19, 2018 at 2:12

# Ruby, 31 bytes

OK, so all those log-based approaches are prone to rounding errors, so here is another method that works with integers and is free of those issues:

->n,p{(0..n).find{|i|p**i>n}-1}


Try it online!

But going back to logarithms, although it is unclear up to what precision we must support the input, but I think this little trick would solve the rounding problem for all more or less "realistic" numbers:

# Ruby, 29 bytes

->n,p{Math.log(n+0.1,p).to_i}


Try it online!

# C (gcc) + -lm, 24 bytes

f(n,m){n=log(n)/log(m);}


Try it online!

• I know about long long but what is bytes bytes? :P Apr 18, 2018 at 17:59
• Also flags don't add to your byte count anymore, so I edited to reflect this. Apr 18, 2018 at 18:00
• Doesn't work for (1000, 10) because of rounding error. Apr 18, 2018 at 18:05
• f(n,m){n=(float)log(n)/log(m);} seems to work @31 bytes
– GPS
Sep 26, 2018 at 11:51

# Japt, 5 bytes

ìV ÊÉ


Try it online!

## 8 bytes

N£MlXÃäz


Try it online!

• Was about to post the same thing using ì instead of s as s will fail if V>36. Apr 18, 2018 at 22:16
• @Shaggy Good call on V>36. Apr 18, 2018 at 22:35

# Emojicode, 49 48 bytes

🍇i🚂j🚂➡️🚂🍎➖🐔🔡i j 1🍉


Try it online!

# APL (Dyalog Unicode), 2 bytes

⌊⍟


Try it online!

Pretty straightforward.

⍟ Log

⌊ floor

• Make dyadic to save a byte: ⌊⍟
Apr 18, 2018 at 20:32
• I'm slightly ashamed you actually had to tell me that >.> thanks, though! Apr 19, 2018 at 13:04

# 05AB1E, 6 bytes

Lm¹›_O


Try it online!

• this just seems unfair to everyone else Apr 19, 2018 at 0:46
• @Floris Competitions are between submissions in each language not between languages right? Apr 19, 2018 at 1:40
• @user202729 yes and no. In my mind, in the end, "shortest code wins". But I noticed there was a 2-byte solution further down... These golf languages blow my mind. Apr 19, 2018 at 1:42
• @Floris "Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language." Apr 19, 2018 at 1:43
• @Floris Also... even Excel can do it in 2 builtins. Golfing languages can do this in 2 built-in too, just the builtin names are shorter. Nothing to surprise. Apr 19, 2018 at 1:45

# JavaScript, 40 33 bytes

-3 bytes thanks to DanielIndie

Takes input in currying syntax.

a=>b=>(L=Math.log)(a)/L(b)+.001|0


Try it online!

• 29 bytes Apr 18, 2018 at 17:12
• 28 bytes and maybe if you want curry method Apr 18, 2018 at 17:14
• Apr 18, 2018 at 19:00
• Doesn't work for (999, 10) (should output 2) Apr 18, 2018 at 19:43
• The toString solution only works for bases up to 36. Apr 18, 2018 at 21:12

# Pari/GP, 6 bytes

logint


(built-in added in version 2.7, Mar 2014. Takes two arguments, with an optional third reference which, if present, is set to the base raised to the result)

• @StewieGriffin logint(x,y) from both Pari/GP and Perl/ntheory give the correct results for the 7 examples currently shown, including '3' for 1000,10. Apr 19, 2018 at 18:19
• +1, but I would count this as 6 bytes. Apr 19, 2018 at 20:58
• You're not allowed to use hardcoded inputs, so this must be a function (eg. as a lambda or definition). However you can just use logint which is valid and counts 5 bytes less. Apr 20, 2018 at 12:43

# Python 2, 3, 46 bytes

-1 thanks to jonathan

def A(a,b,i=1):
while b**i<=a:i+=1
return~-i


## Python 1, 47 bytes

def A(a,b,i=1):
while b**i<=a:i=i+1
return~-i

• n~-i is one byte shorter than n i-1. Sep 25, 2018 at 10:26
• Also, please state your Python's version. Sep 25, 2018 at 10:26
• Will work in any version, won't it? Sep 25, 2018 at 10:27
• It will not work in Python 1. Sep 25, 2018 at 10:28

# JavaScript (Node.js), 22 bytes

m=>f=n=>n<m?0:f(n/m)+1


Try it online!

Curried recursive function. Use as g(P)(N). Less prone to floating-point errors than using Math.log, and (I believe) the code gives correct values as long as both inputs are safe integers (under 2**52).

n!p=last.fst\$span((<=n).(p^))[0..]


Thanks @Laikoni for saving 1 byte

Try it online!

# J, 5 bytes

<.@^.


Try it online!

## Wolfram Language (Mathematica) 15 10 Bytes

Floor@*Log


(requires reversed order on input)

Original submission

⌊#2~Log~#⌋&

• ⌊Log@##⌋& is one byte shorter Apr 19, 2018 at 7:55
• @Mathe172, that's one character shorter, but I count 13 bytes on that. The left floor and right floor count as 3 bytes each in UTF-8. Apr 19, 2018 at 17:36
• @StewieGriffin %[10,1000] gives 3. The inputs are treated as integers rather than machine numbers unless you put a decimal place after them. Apr 19, 2018 at 18:21

# Forth (gforth), 35 bytes

: f swap s>f flog s>f flog f/ f>s ;


Try it online!

Could save 5 bytes by swapping expected input parameters, but question specifies N must be first (an argument could be made that in a postfix language "First" means top-of-stack, but I'll stick to the letter of the rules for now)

## Explanation

swap       \ swap the parameters to put N on top of the stack
s>f flog   \ move N to the floating-point stack and take the log(10) of N
s>f flog   \ move P to the floating-point stack and take the log(10) of P
f/         \ divide log10(N) by log10(P)
f>s        \ move the result back to the main (integer) stack, truncating in the process


# Pyth, 6 4 bytes

s.lF


Saved 2 bytes thanks to Mmenomic
Try it online

## How it works

.l is logB(A)
To be honest, I have no idea how F works. But if it works, it works.
s truncates a float to an int to give us the highest integer for M.

• 1000,10 as inputs gives 2 as output Apr 19, 2018 at 18:14
• Another similar solution is /FlM
– RK.
Apr 25, 2018 at 12:45

# Wonder, 9 bytes

|_.sS log


Example usage:

(|_.sS log)[1000 10]


# Explanation

Verbose version:

floor . sS log


This is written pointfree style. sS passes list items as arguments to a function (in this case, log).

# Gforth, 31 Bytes

SWAP S>F FLOG S>F FLOG F/ F>S .


## Usage

242 3 SWAP S>F FLOG S>F FLOG F/ F>S . 4 OK


Try it online!

## Explanation

Unfortunately FORTH uses a dedicated floating-point-stack. For that i have to SWAP (exchange) the input values so they get to the floating point stack in the right order. I also have to move the values to that stack with S>F. When moving the floating-point result back to integer (F>S) I have the benefit to get the truncation for free.

## Shorter version

Stretching the requirements and provide the input in float-format and the right order, there is a shorter version with 24 bytes.

FLOG FSWAP FLOG F/ F>S .
3e0 242e0 FLOG FSWAP FLOG F/ F>S . 4 OK


Try it online!

• Generally for CodeGolf answers, snippets are disallowed (unless otherwise indicated in the challenge). This answer should either be wrapped with a function (Word in Forth) : f .... ; or a converted to a program that takes input using KEY or ACCEPT Apr 18, 2018 at 19:48
• @reffu What is a snippet? In my opinion a smal code part to show something, which, however, does nothing meaningful for itself. On the other hand, the code that I've provided does work without changes on "Try it online!". Should we go meta? Apr 18, 2018 at 20:23
• In this particular case the code you posted will in fact throw a stack underflow unless you place the parameters before it. Code golf answers should generally be a self-contained program or function that produces the expected result if called later. If you follow the link to the meta post in my previous comment it explicitly mentions that the standard is for answers to be a program or a function, of which yours is neither. To fix it would only require another 4 bytes Apr 19, 2018 at 12:18

# Husk, 87 4 bytes

LtB


Try it online!

# C (gcc), 61 bytes

i(n,t,l,o,g){for(l=g=0;!g++;g=g>n)for(o=++l;o--;g*=t);g=--l;}
`

Try it online!