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

Improve this question
\$\endgroup\$
13
  • 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, 2018 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, 2018 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, 2018 at 16:30
  • 13
    \$\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, 2018 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, 2018 at 20:23

57 Answers 57

Reset to default
1
2
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
[()])
Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
0
6
\$\begingroup\$

Excel, 18 bytes

=TRUNC(LOG(A1,A2))

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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I think you can use INT function instead of TRUNC to save 2 bytes. \$\endgroup\$
    – pajonk
    Apr 19, 2018 at 7:26
5
\$\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.
Improve this answer
\$\endgroup\$
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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Japt, 8 bytes

@<Vp°X}a

Try it

Improve this answer
\$\endgroup\$
2
  • \$\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\$
    – Etheryte
    Apr 18, 2018 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, 2018 at 19:12
3
\$\begingroup\$

Haskell, 30 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • 2
    \$\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, 2018 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.

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

C (gcc) + -lm, 24 bytes

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

Try it online!

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

Improve this answer
\$\endgroup\$
1
  • 6
    \$\begingroup\$ Doesn't work for (1000, 10) because of rounding error. \$\endgroup\$
    – nwellnhof
    Apr 18, 2018 at 18:17
3
\$\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!

Improve this answer
\$\endgroup\$
4
  • 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, 2018 at 8:22
  • \$\begingroup\$ @JDL that's a fair point; I believe a perfectly precise answer would be ~31 bytes. \$\endgroup\$
    – Giuseppe
    Apr 19, 2018 at 13:35
  • 1
    \$\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, 2018 at 15:02
  • \$\begingroup\$ Another 28 byte solution without numerical precision issues. \$\endgroup\$
    – Robin Ryder
    Nov 22, 2019 at 13:24
2
\$\begingroup\$

Python 2, 39 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • 3
    \$\begingroup\$ 1000,10 as inputs gives 2 as output. \$\endgroup\$
    – Floris
    Apr 19, 2018 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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Japt, 5 bytes

ìV ÊÉ

Try it online!

8 bytes

N£MlXÃäz

Try it online!

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

Emojicode, 49 48 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 2 bytes

⌊⍟

Try it online!

Pretty straightforward.

⍟ Log

⌊ floor

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

05AB1E, 6 bytes

Lm¹›_O

Try it online!

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ this just seems unfair to everyone else \$\endgroup\$
    – Floris
    Apr 19, 2018 at 0:46
  • 1
    \$\begingroup\$ @Floris Competitions are between submissions in each language not between languages right? \$\endgroup\$
    – DELETE_ME
    Apr 19, 2018 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, 2018 at 1:42
  • 2
    \$\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\$
    – DELETE_ME
    Apr 19, 2018 at 1:43
  • 2
    \$\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\$
    – DELETE_ME
    Apr 19, 2018 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!

Improve this answer
\$\endgroup\$
7
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)

Improve this answer
\$\endgroup\$
3
  • \$\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, 2018 at 18:19
  • \$\begingroup\$ +1, but I would count this as 6 bytes. \$\endgroup\$
    – Charles
    Apr 19, 2018 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, 2018 at 12:43
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ n~-i is one byte shorter than n i-1. \$\endgroup\$
    – Jonathan Frech
    Sep 25, 2018 at 10:26
  • \$\begingroup\$ Also, please state your Python's version. \$\endgroup\$
    – Jonathan Frech
    Sep 25, 2018 at 10:26
  • \$\begingroup\$ Will work in any version, won't it? \$\endgroup\$
    – Vedant Kandoi
    Sep 25, 2018 at 10:27
  • \$\begingroup\$ It will not work in Python 1. \$\endgroup\$
    – Jonathan Frech
    Sep 25, 2018 at 10:28
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 35 34 bytes

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

Thanks @Laikoni for saving 1 byte

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

J, 5 bytes

<.@^.

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica) 15 10 Bytes

Floor@*Log

(requires reversed order on input)

Original submission

⌊#2~Log~#⌋&
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ ⌊Log@##⌋& is one byte shorter \$\endgroup\$
    – Lukas Lang
    Apr 19, 2018 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, 2018 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, 2018 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
Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ 1000,10 as inputs gives 2 as output \$\endgroup\$
    – Stewie Griffin
    Apr 19, 2018 at 18:14
  • \$\begingroup\$ Another similar solution is /FlM \$\endgroup\$
    – RK.
    Apr 25, 2018 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).

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
3
  • \$\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, 2018 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, 2018 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, 2018 at 12:18
1
\$\begingroup\$

Husk, 8 7 4 bytes

Lt`B

Try it online!

Improve this answer
\$\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!

Improve this answer
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.