12
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Giuseppe Apr 18 '18 at 16:26
  • 9
    \$\begingroup\$ 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). :) \$\endgroup\$ – Giuseppe Apr 18 '18 at 16:27
  • 2
    \$\begingroup\$ You can always post into the general PPCG Chatroom asking for feedback on your sandbox challenges to get them a bit more attention. \$\endgroup\$ – Giuseppe Apr 18 '18 at 16:30
  • 12
    \$\begingroup\$ 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. \$\endgroup\$ – nwellnhof Apr 18 '18 at 18:23
  • 3
    \$\begingroup\$ @MPW all the responses were deleted, and the suggestions I made were edited into the post, so they were no longer relevant. \$\endgroup\$ – Giuseppe Apr 19 '18 at 20:23

50 Answers 50

8
\$\begingroup\$

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
[()])
\$\endgroup\$
7
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

Excel, 18 bytes

=TRUNC(LOG(A1,A2))

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

\$\endgroup\$
  • \$\begingroup\$ I think you can use INT function instead of TRUNC to save 2 bytes. \$\endgroup\$ – pajonk Apr 19 '18 at 7:26
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Japt, 8 bytes

@<Vp°X}a

Try it

\$\endgroup\$
  • \$\begingroup\$ This is really neat, I haven't really seen a good use for the function methods in Japt yet, this is a good example. \$\endgroup\$ – Nit Apr 18 '18 at 18:03
  • \$\begingroup\$ @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. \$\endgroup\$ – Shaggy Apr 18 '18 at 19:12
3
\$\begingroup\$

Haskell, 30 bytes

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

Try it online!

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

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ For arguments 1000, 10 this returns 2. \$\endgroup\$ – Sean Apr 18 '18 at 22:25
  • \$\begingroup\$ @Sean: Huh, interesting precision issue there \$\endgroup\$ – Phil H Apr 19 '18 at 20:34
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 6
    \$\begingroup\$ Doesn't work for (1000, 10) because of rounding error. \$\endgroup\$ – nwellnhof Apr 18 '18 at 18:17
2
\$\begingroup\$

Python 2, 39 bytes

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

Try it online!

\$\endgroup\$
  • 3
    \$\begingroup\$ 1000,10 as inputs gives 2 as output. \$\endgroup\$ – Floris Apr 19 '18 at 2:12
2
\$\begingroup\$

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!

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

C (gcc) + -lm, 24 bytes

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

Try it online!

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

Emojicode, 49 48 bytes

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

Try it online!

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – JDL Apr 19 '18 at 8:22
  • \$\begingroup\$ @JDL that's a fair point; I believe a perfectly precise answer would be ~31 bytes. \$\endgroup\$ – Giuseppe Apr 19 '18 at 13:35
  • \$\begingroup\$ I think you can replace p by p+.1 in the 25 byte answer and you will still be okay, for 28 bytes \$\endgroup\$ – JDL Apr 19 '18 at 15:02
2
\$\begingroup\$

05AB1E, 6 bytes

Lm¹›_O

Try it online!

\$\endgroup\$
  • \$\begingroup\$ this just seems unfair to everyone else \$\endgroup\$ – Floris Apr 19 '18 at 0:46
  • \$\begingroup\$ @Floris Competitions are between submissions in each language not between languages right? \$\endgroup\$ – user202729 Apr 19 '18 at 1:40
  • \$\begingroup\$ @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. \$\endgroup\$ – Floris Apr 19 '18 at 1:42
  • \$\begingroup\$ @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." \$\endgroup\$ – user202729 Apr 19 '18 at 1:43
  • \$\begingroup\$ @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. \$\endgroup\$ – user202729 Apr 19 '18 at 1:45
2
\$\begingroup\$

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!

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

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)

\$\endgroup\$
  • \$\begingroup\$ @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. \$\endgroup\$ – DanaJ Apr 19 '18 at 18:19
  • \$\begingroup\$ +1, but I would count this as 6 bytes. \$\endgroup\$ – Charles Apr 19 '18 at 20:58
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – ბიმო Apr 20 '18 at 12:43
1
\$\begingroup\$

Haskell, 35 34 bytes

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

Thanks @Laikoni for saving 1 byte

Try it online!

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

J, 5 bytes

<.@^.

Try it online!

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

Wolfram Language (Mathematica) 15 10 Bytes

Floor@*Log 

(requires reversed order on input)

Original submission

⌊#2~Log~#⌋&
\$\endgroup\$
  • \$\begingroup\$ ⌊Log@##⌋& is one byte shorter \$\endgroup\$ – Lukas Lang Apr 19 '18 at 7:55
  • \$\begingroup\$ @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. \$\endgroup\$ – Kelly Lowder Apr 19 '18 at 17:36
  • \$\begingroup\$ @StewieGriffin %[10,1000] gives 3. The inputs are treated as integers rather than machine numbers unless you put a decimal place after them. \$\endgroup\$ – Kelly Lowder Apr 19 '18 at 18:21
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 1000,10 as inputs gives 2 as output \$\endgroup\$ – Stewie Griffin Apr 19 '18 at 18:14
  • \$\begingroup\$ Another similar solution is /FlM \$\endgroup\$ – RK. Apr 25 '18 at 12:45
1
\$\begingroup\$

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

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

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!

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – reffu Apr 18 '18 at 19:48
  • \$\begingroup\$ @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? \$\endgroup\$ – Kitana Apr 18 '18 at 20:23
  • \$\begingroup\$ 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 \$\endgroup\$ – reffu Apr 19 '18 at 12:18
1
\$\begingroup\$

Husk, 8 7 4 bytes

Lt`B

Try it online!

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

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!

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

Japt, 5 bytes

ìV ÊÉ

Try it online!


8 bytes

N£MlXÃäz

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Was about to post the same thing using ì instead of s as s will fail if V>36. \$\endgroup\$ – Shaggy Apr 18 '18 at 22:16
  • \$\begingroup\$ @Shaggy Good call on V>36. \$\endgroup\$ – Oliver Apr 18 '18 at 22:35
1
\$\begingroup\$

MATL, 5 bytes

:YAnq

Try it online!

Simple arbitrary base conversion to avoid using floating point math.

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

APL (Dyalog Unicode), 2 bytes

⌊⍟

Try it online!

Pretty straightforward.

Log

floor

\$\endgroup\$
  • \$\begingroup\$ Make dyadic to save a byte: ⌊⍟ \$\endgroup\$ – Adám Apr 18 '18 at 20:32
  • \$\begingroup\$ I'm slightly ashamed you actually had to tell me that >.> thanks, though! \$\endgroup\$ – J. Sallé Apr 19 '18 at 13:04
1
\$\begingroup\$

Ruby, 29 bytes

->p,n{r=0;r+=1while 0<p/=n;r}

Try it online!

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