Desmos, 20 bytes

f(P,N)=floor(log_PN)

This formula can be deduced by the following:

P^M ≤ N
M ≤ log_P(N)
if M must be an integer, we can just round down to get:
M = floor(log_P(N))

Try in on Desmos!

APL(NARS), 4 chars

⌊⎕⍟⎕

test:

  ⌊⎕⍟⎕
⎕:
  10
⎕:
  10000
4
  ⌊⎕⍟⎕
⎕:
  10
⎕:
  1000
3

Python 2, 31 bytes

f=lambda x,y:x>=y and-~f(x/y,y)

Try it online!

GNU roff (groff), 88 bytes

.de F
\\R't 1
\\R'M 0'
.while \\nt<=\\$1 \\{.nr t \\nt*\\$2
\\R'M +1\\}
\\R'M -1
\\nM
..

Attempt This Online!

Explained

.de F        \" define macro F
\\R't 1      \" set register t to 1
\\R'M 0'     \" set register M to 0
.while \\nt<=\\$1 \\{  \" while register t is not greater than first argument
.nr t \\nt*\\$2  \" set register t to register t times second argument
\\R'M +1\\}      \" increment register R. End of loop
\\R'M -1    \" decrement register R
\\nM        \" print out numeric value of register M
..          \" end of macro definition 

nroff, 95 bytes

It's stupid that I had to increment one more than expected, then decrement the value. I tried replacing initial value .nr M -1 and deleting decrementing part but the result went something very crazy (e.g. .F 4 5 returned -3 and .F 1000 10 returned 1526194161). How does nroff really represent numerical value!?

.de F
.nr t 1
.nr M 0
.while \\nt<=\\$1 \\{.nr t \\nt*\\$2
.nr M \\nM+1\\}
.nr M \\nM-1
\\nM
..

Attempt This Online!

Thunno 2 L, 2 bytes

Bḣ

Attempt This Online!

Convert the second input to Base-first input, then remove the ḣead (first item). The L flag takes the length.

Pyt, 7 bytes

Đ←⇹ř^≥Ʃ

Try it online!

Couldn't use built-in log function because of floating-point inaccuracies. Takes N, then P.

Đ              implicit input; Đuplicate
 ←             get input
  ⇹            swap top two on stack
   ř           řangify
    ^          raise to power element-wise
     ≥         is N greater than or equal to each element?
      Ʃ        Ʃum; implicit print

Vyxal, 3 bytes

$•⌊

Try it Online!

$•⌊
$   # swap input
 •  # log
  ⌊ # floor

Ruby, 29 26 bytes

f=->n,p{n<p ?0:1+f[n/p,p]}

Try it online!

Keg, -hr, 19 bytes

¿&¿0{:^:'$Ë&:&≤|⑨};

Try it online!

Uses the same technique as the Pyth answer

Explained

Wren, 32 bytes

Log, log, floor.

Fn.new{|a,b|(a.log/b.log).floor}

Try it online!

x86(16/32 bit) opcode, 13 bytes

83 CB FF  31 DB  F7 F1  43  09 C0  75 F7  C3

Input EAX, ECX, output EBX

OR  EBX, -1
XOR EDX, EDX
DIV ECX
INC EBX
OR  EAX, EAX
JNZ $-7
RET

Runic Enchantments, 13 bytes

i'LAi'LA,'fA@

Try it online!

Nothing fancy here. Reads an input and calls Log on it, repeats for the second input, divides, and floors. Runic is very permissive with typing, using implicit conversions where it makes sense to do so, with only a couple of explicit conversion operators (to-number, to-char, and dictionary-lookup).

Equivalent to (int)Math.Floor((double)Math.Log(a) / Math.Log(b))

Python 3 with mpmath, 52 bytes

import mpmath
def f(N,P):return int(mpmath.log(N,P))

Test it:

for N, P in zip([4, 33, 40, 242, 243, 400, 1000], [5, 5, 20, 3, 3, 2, 10]):
    print(f(N,P))

How I would really do it. The mpmath (included with SymPy) logarithm seems more accurate, even at default. I always love some arbitrary precision floating-point. I was really surprised that the standard methods led to such inaccuracies.

Java 8, 36 34 bytes (with floating point errors on one test case)

a->b->b+=Math.log(a)/Math.log(b)-b

-2 bytes thanks to @OlivierGrégoire.

Try it online.

Explanation:

Java only has Math.log(double val) as builtin, which is basically log₁₀. For log_n(val) you'll have to use Math.log(val)/Math.log(n).
So this is what the Math.log(a)/Math.log(b) does. The b+=...-b is used to cast the doubles of the Math.log to an integer, which is shorter than a->b->(int)(Math.log(a)/Math.log(b)) (thanks @OlivierGrégoire).

Java 10, 245 240 239 231 bytes

a->b->(int)(l(a)/l(b));double l(java.math.BigInteger v){int n=v.bitLength(),i=0,j=0;long t=1L<<52,M=t,m=0;for(;++i<54&&(j=n-i)>=0;M>>=1)m|=v.testBit(j)?M:0;return(n-1+Math.log((j>0&&v.testBit(j-1)?m+1:m)*1f/t)*1.4426950408889634);}

-5 bytes thanks to @ceilingcat.

Try it online.

Explanation:

To fix the floating point errors we'll have to use a BigInteger log. a->b->(int)(l(a)/l(b)) is basically the same as before (note that a and b are now java.math.BigInteger inputs instead of int, so the same b+=...-b won't work here.

The separated log-method for better precision I got from this Stackoverflow answer.

double l(java.math.BigInteger v){
  // Get the minimum number of bits necessary to hold this value
  int n=v.bitLength(),
  // Index integers
      i=0,j=0;
  // Calculate the double-precision fraction of this numbers; as if the
  // binary point was left of the most significant '1' bit.
  // (Get the most significant 53 bits and divide by 2^53)
  // mantissa is 53 bits (including hidden bit)
  long t=1L<<52,M=t,m=0;
  for(;++i<54&&(j=n-i)>=0;M>>=1)m|=v.testBit(j)?M:0;
  // Round up if next bit is 1.
  // Add the logarithm to the number of bits, and subtract 1 because the
  // number of bits is always higher than necessary for a number
  // (i.e. log2(v)<n for every `v`)
  return(n-1+Math.log((j>0&&v.testBit(j-1)?m+1:m)*1f/t)*1.4426950408889634);}
  // Magic number converts from base e to base 2 before adding. For other
  // bases, correct the result, NOT this number!

Gol><>, 7 bytes

IISLS(h

Can take the inputs seperated by a comma. (ex. [4,5], [6,8])

I'm pretty sure that this is the absolute smallest it can get..

Intel 8087 FPU assembly, 38 bytes

Uses only the Intel 8087 math co-processor.

d9e8 df06 3c01 d9f1 d9e8 df06 3e01 d9f1 def9 9bd9
3e3e 0181 0e3e 0100 0c9b d92e 3e01 df1e 3c01

Unassembled:

; Integer logarithm
; input: integers N, P > 1 (mem16,mem16)
; output: N (mem16) largest integer such that P ^ M ≤ N
INTLOG  MACRO N,P
        FLD1        ; ST(1) = 1
        FILD N      ; ST = N
        FYL2X       ; ST = 1 * LOG2(N)
        FLD1        ; ST(1) = 1
        FILD P      ; ST = P
        FYL2X       ; ST = 1 * LOG2(P)
        FDIV        ; ST = LOG2(N) / LOG2(P)
        FWAIT       ; sync CPU/FPU
        FSTCW P     ; get the current CW register
        OR P, 0C00H ; set RC for floor rounding mode
        FWAIT       ; sync CPU/FPU
        FLDCW P     ; set the modified CW register
        FISTP N     ; N = FLOOR(ST)
        ENDM

Example IBM PC DOS test program:

    FINIT           ; reset 8087
    CALL INDEC      ; generic decimal input routine
    MOV  N, AX      ; first input into N
    CALL INDEC      ; generic decimal input routine
    MOV  P, AX      ; second input into P
    INTLOG N,P      ; calculate
    MOV  AX, N      ; result in N into AX for display
    CALL OUTDEC     ; generic decimal output routine

Tests:

A>INTDEC.COM
: 4
: 5
0
A>INTDEC.COM
: 33
: 5
2
A>INTDEC.COM
: 40
: 20
1
A>INTDEC.COM
: 242
: 3
4
A>INTDEC.COM
: 243
: 3
5
A>INTDEC.COM
: 400
: 2
8
A>INTDEC.COM
: 1000
: 10
3

Note: 16 bytes of this code are just for putting the FPU into floor rounding mode.

Tcl, 39 bytes

proc L n\ p {expr int(log($n)/log($p))}

Try it online!

Gives 4 for (243,3) as it is the integer truncation of 4.99999999999999...! The same happens when I tried other answers!

q, 42 bytes

{r::x;{$[r>=y xexp x;x;.z.s[x-1;y]]}[x;y]}

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).

Haskell, 30 bytes

f n p=head[x|x<-[0..],p^x>n]-1

Should be no round-off errors

PowerShell 3, 44 38 Bytes

param($n,$p)for(;($n/=$p)-ge1){$z++}$z

Truncating to an int is too dang long in this language. However, looting the formula others are using bypasses this. Crossed-out 44 is still 44

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

C (gcc), 41 31 bytes

Thanks to Kevin for his suggestion, which is reproduced below:

f(n,p,m){for(;n/=p;m++);n=m-2;}

Try it online!

Previous submission:

f(n,p){int m;for(m=0;n/=p;m++);return m;}

Try it online!

No library functions required.

Pyth, 8 bytes

tf<Q^vzT

Test suite.

Explanation

tf<Q^vzT – Full program.
 f       – First positive integer T that satsfies:
   Q       – The first input
  <        – Is less than
     vz    – The second input
    ^  T   – Raised to the T-th power.
t        – Decrement the integer and output implicitly.

PHP, 43 Bytes

Try it online!

Code

function f($p,$n){echo intval(log($p,$n));}

intval() truncates a float number, as for log($p,$n) the integer part of the result will always be the maximum positive integer that satisfies the inequation.

34 Bytes

If passing arguments to the script

Try it online

Code

<?=intval(log($argv[0],$argv[1]));

dc, 30 bytes

sp0sm[dlplm1+dsm^!>M]dsMxlm1-p

Try it online!

No logs in dc means no FP errors... Also means doing the thing repeatedly and testing to see when we go over, which... is not very golfy.

Straightforward, but here's the gist: sp stores our p value in p; 0sm stores a zero in what will ultimately be our m value, m. Macro M duplicates what's left on the stack (n), loads p, loads m, spends a lot of bytes incrementing m (lm1+dsm), does the exponentiation ^ and tests if the result is less than or equal to n (left on stack). Keeps going so long as this is true, then loads m, subtracts 1, and prints it.

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)

Python 3, 40 39 bytes

-1 @Jonathan

g=lambda n,p,a=1:a*p<=n and-~g(n,p,a*p)

Try it online!

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!

05AB1E, 6 bytes

Lm¹›_O

Try it online!

Perl 6, 22 bytes

{(1,*×$^p...*>$^n)-2}

Try it online!

1, * × $^p ... * > $^n is a sequence that starts with 1, where each succeeding element is generated from the previous by multiplying by $^p (the second argument to the function), and continues up to the element * such that * is greater than $^n (the first argument to the function). Subtracting two from this sequence coerces it to a number, specifically its length. Two less than the length is the desired integer logarithm.

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!

APL (Dyalog Unicode), 2 bytes

⌊⍟

Try it online!

Pretty straightforward.

⍟ Log

⌊ floor

MATL, 5 bytes

:YAnq

Try it online!

Simple arbitrary base conversion to avoid using floating point math.

Emojicode, 49 48 bytes

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

Try it online!

Haskell, 16 bytes

(floor.).logBase

Try it online!

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

Japt, 5 bytes

ìV ÊÉ

Try it online!

8 bytes

N£MlXÃäz

Try it online!

PHP, 28 bytes

<?=log($argv[1],$argv[2])|0;

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!

Husk, 8 7 4 bytes

Lt`B

Try it online!

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.

C (gcc) + -lm, 24 bytes

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

Try it online!

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!

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).

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.

Pyth, 6 4 bytes

s.lF

Saved 2 bytes thanks to Mmenomic
Try it online

How it works

.l is log_B(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.

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!

Haskell, 30 bytes

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

Try it online!

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

Japt, 8 bytes

@<Vp°X}a

Try it

Lua, 47 37 bytes

(N,P)return math.floor(math.log(N,P))

Try it online!

Thanks to @user9549915 for saving 10 bytes

Wolfram Language (Mathematica) 15 10 Bytes

Floor@*Log 

(requires reversed order on input)

Original submission

⌊#2~Log~#⌋&

Ruby, 31 bytes

->n,p,d=0{n<p**(d+=1)?d-1:redo}

Try it online!

Curse you, floating point errors

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!

Retina 0.8.2, 35 bytes

.+
$*
+r`1*(\2)+¶(1+)$
#$#1$*1¶$2
#

Try it online! Explanation:

.+
$*

Convert the arguments to unary.

+r`1*(\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.

J, 5 bytes

<.@^.

Try it online!

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
[()])

Haskell, 35 34 bytes

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

Thanks @Laikoni for saving 1 byte

Try it online!

Python 2, 39 bytes

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

Try it online!

Excel, 18 bytes

=TRUNC(LOG(A1,A2))

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