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

53 Answers 53

1
2
1
\$\begingroup\$

MATL, 5 bytes

:YAnq

Try it online!

Simple arbitrary base conversion to avoid using floating point math.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Wren, 32 bytes

Log, log, floor.

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

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Keg, -hr, 19 bytes

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

Try it online!

Uses the same technique as the Pyth answer

Explained

With Highlighter

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Ruby, 29 26 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Ruby, 31 bytes

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

Try it online!

Curse you, floating point errors

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Lua, 47 37 bytes

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

Try it online!

Thanks to @user9549915 for saving 10 bytes

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

PHP, 28 bytes

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

Try it online

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Don't you need the g= in order for this to work? My understanding has always been that unnamed functions are OK, except in cases like this where the function is referred to by name elsewhere (as in recursive functions). So for example, (lambda n,p,a=1:a*p<=n and g(n,p,a*p)+1)(5, 5) will obviously produce an error, but instead I can do g=lambda n,p,a=1:a*p<=n and g(n,p,a*p)+1 and then call g(5,5). [Unless maybe a new consensus has emerged about this...?] \$\endgroup\$ – mathmandan Apr 18 '18 at 22:08
  • \$\begingroup\$ @mathmandan - you are correct, my bad. fixed. \$\endgroup\$ – RootTwo Apr 19 '18 at 5:27
  • \$\begingroup\$ expected 0, got False. Okay.... \$\endgroup\$ – Jonathan Frech Apr 19 '18 at 18:43
  • \$\begingroup\$ @Jonathan, in a numeric context False has the value 0. \$\endgroup\$ – RootTwo Apr 19 '18 at 23:49
  • \$\begingroup\$ @RootTwo I know, it just looked funny to call that Okay.. You could have used {r:d} in your string formatting. \$\endgroup\$ – Jonathan Frech Apr 20 '18 at 13:02
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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]));
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @FransiscoHahn : This is code-golf so you might wanna shorten your code ? \$\endgroup\$ – Muhammad Salman Apr 18 '18 at 16:32
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think setting m to a parameter saves a couple bytes. Try it online! -- truth be told, I was looking at "Tips for Golfing in C" and saw this; my C knowledge is minimal at best. \$\endgroup\$ – Giuseppe Apr 20 '18 at 18:26
  • \$\begingroup\$ First I want to ask, why do you initialize int m; and only in the for-loop do m=0? You could have done int m=0;for(;... directly. In C however you can use some nice tricks, including the one stated (but incorrectly linked in the TIO I think) by @Giuseppe, as well as dropping the return like this: m;f(n,p){for(m=0;n/=p;m++);n=m;} Try it online 32 bytes \$\endgroup\$ – Kevin Cruijssen Apr 24 '18 at 12:25
  • \$\begingroup\$ Actually, using ,m as parameter implicitly gives it the parameter-index as initial value (not sure if this is always the case, my C knowledge is limited). If it indeed is, f(n,p,m){for(;n/=p;m++);n=m-2;} can be used instead for 31 bytes. Try it online. Oh, and welcome to PPCG! :) \$\endgroup\$ – Kevin Cruijssen Apr 24 '18 at 12:26
0
\$\begingroup\$

Haskell, 30 bytes

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

Should be no round-off errors

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

q, 42 bytes

{r::x;{$[r>=y xexp x;x;.z.s[x-1;y]]}[x;y]}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Darn rounding errors >:( \$\endgroup\$ – Nissa Apr 20 '18 at 13:03
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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 log10. For logn(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!
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Suggest ++i<54&(j=n-i)>=0;M/=2 instead of ++i<54&&(j=n-i)>=0;M>>=1 \$\endgroup\$ – ceilingcat Nov 22 '19 at 10:40
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Although this is one of the shortest answers, it could do with at least some explanation (preferably a disassembly, so that mortals can see which registers are used, and which opcodes). \$\endgroup\$ – Toby Speight Apr 19 '18 at 14:24
  • \$\begingroup\$ But 32 bit division not use edx? So edx it is not initialized to 0? \$\endgroup\$ – RosLuP Nov 25 '19 at 15:31
  • \$\begingroup\$ @RosLuP Fixed.. \$\endgroup\$ – l4m2 Nov 27 '19 at 0:36
1
2

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.