Целочисленные логарифмы

12

По заданным целым числам N , P > 1найдите наибольшее целое число Mтакое, что P ^ M ≤ N.

I / O:

Ввод дан как 2 целых числа Nи P. На выходе будет целое число M.

Примеры:

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

Примечания:

Ввод всегда будет действительным, то есть он всегда будет целым числом больше 1.

Кредиты:

Кредит на имя идет к @cairdcoinheringaahing. Последние 3 примера предоставлены @Nitrodon, и заслуга в улучшении описания принадлежит @Giuseppe.

code-golf math number arithmetic Мухаммед Салман
источник
3
Я знаю, что мы (сообщество PPCG) можем показаться слишком придирчивыми к мелочам, но такие комментарии, как мои, действительно предназначены для того, чтобы сделать задачу лучше! Теперь, когда это решено, я с удовольствием проголосовал и удалил свои предыдущие комментарии.
Джузеппе
9
Это еще одна причина, по которой мы рекомендуем сначала публиковать задания в «Песочнице» , чтобы вы могли получить полезную обратную связь, опубликовать большое задание и получить много качественных ответов с гораздо меньшим количеством суеты (например, голосов «за» и «против»). :)
Джузеппе
2
Вы всегда можете публиковать сообщения в общем чате PPCG с просьбой оставить отзыв о ваших проблемах с песочницей, чтобы привлечь к ним немного больше внимания.
Джузеппе
12
Почти все текущие ответы, основанные на математике с плавающей точкой, дают неправильные результаты даже для простых случаев, таких как (1000, 10), из-за ошибки округления, поэтому я добавил еще один тестовый пример.
nwellnhof
3
@MPW все ответы были удалены, а сделанные мной предложения были отредактированы в сообщении, поэтому они больше не актуальны.
Джузеппе

Ответы:

8

Brain-Flak , 74 байта

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

Попробуйте онлайн!

Это использует ту же концепцию, что и стандартный алгоритм положительного целочисленного деления Брейна-Флака.

# 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
[()])
Nitrodon
источник
6

Excel, 18 байт

=TRUNC(LOG(A1,A2))

Принимает ввод "n" в A1 и ввод "p" в A2.

qoou
источник
Я думаю, что вы можете использовать INTфункцию вместо того, TRUNCчтобы сохранить 2 байта.
pajonk
4

Желе , 3 байта

bḊL

Здесь не используется арифметика с плавающей точкой, поэтому нет проблем с точностью.

Попробуйте онлайн!

Как это устроено

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.
Деннис
источник
3

Сетчатка 0.8.2 , 35 байт

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

Попробуйте онлайн! Объяснение:

.+
$*

Преобразуйте аргументы в одинарные.

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

Если второй аргумент делит первый, замените первый аргумент #целочисленным плюсом, отбрасывая оставшуюся часть. Повторяйте это, пока первый аргумент не станет меньше второго.

#

Посчитайте, сколько раз цикл побежал.

Нил
источник
3

Japt, 8 байт

@<Vp°X}a

Попытайся

мохнатый
источник
Это действительно здорово, я еще не видел хорошего использования методов функций в Japt, это хороший пример.
Нить
@Nit, мне тоже потребовалось много времени, чтобы разобраться с ними - только недавно начали выяснять способы использования F.g()- но они невероятно полезны.
лохматый
3

Perl 6 , 13 байт

&floor∘&log

Попробуйте онлайн!

Конкатенация, составляющая log и floor, неявно имеет 2 аргумента, потому что первая функция log ожидает 2. Результатом является функция.

Фил Х
источник
3
Для аргументов 1000, 10это возвращает 2.
Шон
@Sean: Да, интересная проблема точности там
Фил Х
3

Haskell , 16 байт

(floor.).logBase

Попробуйте онлайн!

Haskell был разработан математиками, поэтому в Prelude есть хороший набор математических функций.

totallyhuman
источник
6
Не работает для (1000, 10) из-за ошибки округления.
nwellnhof
3

R , 25 байт

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

Попробуйте онлайн!

Возьмите журнал Pбазы Nи выполните целочисленное деление 1, так как оно корочеfloor() . Это немного страдает от числовой точности, поэтому я представлю также ответ ниже, который не должен, кроме возможного целочисленного переполнения.

R , 31 байт

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

Попробуйте онлайн!

Giuseppe
источник
1
Я не знаю, насколько строгая задача требует от нас ошибки округления, но, например, f (243,3) равно 4, когда, вероятно, должно быть 5.
JDL
@JDL это справедливо; Я считаю, что совершенно точный ответ будет ~ 31 байт.
Джузеппе
1
Я думаю , вы можете заменить pна p+.1в 25 байтах ответа , и вы по- прежнему будете в порядке, в течение 28 байт
JDL
Еще одно 28-байтовое решение без проблем с числовой точностью.
Робин Райдер
2

Рубин , 31 байт

Итак, все эти основанные на журнале подходы склонны к ошибкам округления, так что вот еще один метод, который работает с целыми числами и свободен от этих проблем:

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

Попробуйте онлайн!

Но вернемся к логарифмам, хотя неясно, с какой точностью мы должны поддерживать входные данные, но я думаю, что этот маленький трюк решил бы проблему округления для всех более или менее «реалистичных» чисел:

Рубин , 29 байт

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

Попробуйте онлайн!

Кирилл Л.
источник
2

C (gcc) + -lm, 24 байта

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

Попробуйте онлайн!

betseg
источник
Я знаю, long longно что это bytes bytes? : P
полностью человек
Также флаги больше не добавляют к вашему счету байтов, поэтому я отредактировал это, чтобы отразить это.
полностью человек
5
Не работает для (1000, 10) из-за ошибки округления.
nwellnhof
f(n,m){n=(float)log(n)/log(m);}кажется, работает @ 31 байт
GPS
2

APL (Dyalog Unicode) , 2 байта

⌊⍟

Попробуйте онлайн!

Довольно просто.

⍟ Журнал

⌊ пол

Ж. Салле
источник
Сделайте ⌊⍟
двоичный код
Мне немного стыдно, что ты на самом деле должен был сказать мне, что>.> Спасибо, хотя!
J. Sallé
2

05AB1E , 6 байтов

Lm¹›_O

Попробуйте онлайн!

Emigna
источник
это просто кажется несправедливым для всех остальных
Флорис
1
@Floris Соревнования проходят между представлениями на каждом языке, а не между языками, верно?
user202729
@ user202729 да и нет. На мой взгляд, в конце концов, «самый короткий код выигрывает». Но я заметил, что дальше было 2-байтовое решение ... Эти языки гольфа поражают меня.
Флорис
1
@Floris «Не позволяйте языкам, использующим код-гольф, отговаривать вас от публикации ответов на языках, не относящихся к код-гольфу. Постарайтесь найти как можно более короткий ответ для« любого »языка программирования».
user202729
1
@Floris Также ... даже Excel может сделать это в 2 встроенных . Языки игры в гольф могут делать это в 2 встроенных тоже, только встроенные имена короче. Ничего удивлять.
user202729
2

JavaScript , 40 33 байта

-3 байта благодаря DanielIndie

Принимает ввод в синтаксисе карри.

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

Попробуйте онлайн!

Оливер
источник
29 байт
DanielIndie
1
28 байтов и, может быть, если вы хотите метод карри
DanielIndie
@nwellnhof tio.run/##y0osSyxOLsosKNHNy09J/Z9m@z/R1i7J1k7Dx9Y3sSRDLyc/...
NoOneIsHere
Не работает для (999, 10) (должен выводить 2)
Герман Л
4
toStringРешение работает только для баз до 36.
nwellnhof
2

Пари / ГП, 6 байт

logint

(встроенное добавлено в версии 2.7, март 2014 г. Принимает два аргумента, с необязательной третьей ссылкой, которая, если имеется, устанавливается на основание, возведенное в результат)

DanaJ
источник
@StewieGriffin logint (x, y) из Pari / GP и Perl / ntheory дают правильные результаты для 7 приведенных примеров, включая «3» для 1000,10.
DanaJ
+1, но я бы посчитал это 6 байтами.
Чарльз
2
Вы не можете использовать жестко запрограммированные входы, поэтому это должна быть функция (например, лямбда или определение). Однако вы можете просто использовать, logintкоторый действителен и насчитывает 5 байтов меньше.
ბიმო
2

Python 2, 3, 46 байтов

-1 спасибо Джонатану

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

Python 1, 47 байт

def A(a,b,i=1):
 while b**i<=a:i=i+1
 return~-i
Ведант Кандой
источник
n~-iна один байт короче n i-1.
Джонатан Фрех,
Также, пожалуйста, укажите версию вашего Python.
Джонатан Фрех,
Будет ли работать в любой версии, не так ли?
Ведант Кандой
Это не будет работать в Python 1.
Джонатан Фрех,
2

JavaScript (Node.js) , 22 байта

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

Попробуйте онлайн!

Карри рекурсивная функция. Используйте как g(P)(N). Менее подвержен ошибкам с плавающей запятой, чем при использованииMath.log , и (я полагаю) код дает правильные значения, если оба входа являются безопасными целыми числами (ниже 2**52).

фонтанчик для питья
источник
1

Wolfram Language (Mathematica) 15 10 байт

Floor@*Log

(требуется обратный порядок на входе)

Оригинальная подача

⌊#2~Log~#⌋&
Келли Лоудер
источник
⌊Log@##⌋&на один байт короче
Лукас Ланг
@ Mathe172, это на один символ короче, но на это я рассчитываю 13 байтов. Левый и правый этажи считаются по 3 байта в UTF-8.
Келли Лоудер
@StewieGriffin% [10,1000] дает 3. Входные данные обрабатываются как целые числа, а не номера машин, если после них не ставится десятичный знак.
Келли Лоудер
1

Forth (gforth) , 35 байтов

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

Попробуйте онлайн!

Можно было бы сэкономить 5 байтов путем замены ожидаемых входных параметров, но вопрос указывает, что N должно быть первым (можно привести аргумент, что в постфиксном языке «First» означает «top-of-stack», но я буду придерживаться буквы правил для сейчас)

объяснение

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
reffu
источник
1

Pyth, 6 4 байта

s.lF

Сохранено 2 байта благодаря Mmenomic
Попробуйте онлайн

Как это устроено

.lэто журнал B (A)
Если честно, я понятия не имею, как Fработает. Но если это работает, это работает.
sусекает число с плавающей точкой до целого, чтобы дать нам наибольшее целое число для M.

fortraan
источник
2
1000,10 в качестве входных данных дает 2 в качестве выходных
Стьюи Гриффин
Другое похожее решение/FlM
РК.
1

Чудо , 9 байт

|_.sS log

Пример использования:

(|_.sS log)[1000 10]

объяснение

Подробная версия:

floor . sS log

Это написано бессмысленно. sSпередает элементы списка в качестве аргументов функции (в данном случае, log).

Mama Fun Roll
источник
1

Gforth , 31 байт

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

использование

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

Попробуйте онлайн!

объяснение

К сожалению, FORTH использует выделенный стек с плавающей точкой. Для этого мне нужно SWAP(обменять) входные значения, чтобы они попадали в стек с плавающей запятой в правильном порядке. Я также должен переместить значения в этот стек с помощью S>F. При перемещении результата с плавающей запятой обратно в integer ( F>S) у меня есть преимущество, чтобы получить усечение бесплатно.

Более короткая версия

Растягивая требования и предоставляя входные данные в формате float и в правильном порядке, существует более короткая версия с 24 байтами.

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

Попробуйте онлайн!

Китано
источник
Как правило, для ответов CodeGolf фрагменты запрещены (если в задании не указано иное). Этот ответ должен быть либо заключен в функцию (Word in Forth), : f .... ;либо преобразован в программу, которая принимает ввод с помощью KEYилиACCEPT
reffu
@reffu Что такое фрагмент? На мой взгляд, небольшая часть кода, чтобы показать что-то, что, однако, не делает ничего значащего для себя. С другой стороны, предоставленный мною код работает без изменений в разделе «Попробуйте онлайн!». Должны ли мы пойти мета?
Китана
В этом конкретном случае код, который вы разместили, на самом деле вызовет переполнение стека, если вы не разместите параметры перед ним. Ответы Code Golf, как правило, должны быть автономной программой или функцией, которая выдает ожидаемый результат, если вызывается позже. Если вы перейдете по ссылке на мета-пост в моем предыдущем комментарии, это прямо скажет, что стандартом для ответов является программа или функция, а ваша - нет. Чтобы исправить это, потребуется всего лишь 4 байта
reffu