Рассчитать супер-логарифм

29

Это должно быть простой задачей.

Учитывая число n >= 0, выведите супер-логарифм (или log *, log-star или повторный логарифм , которые эквивалентны, поскольку nникогда не отрицательны для этой задачи.) Of n.

log * (n): = {0, если n <= 1;  1 + log * (log (n)), если n> 1}

Это одна из двух обратных функций к тетрации . Другой - супер-корень , который находится в связанном вопросе .

Примеры

Input       Output
0           0
1           0
2           1
3           2
4           2
...
15          2
16          3
...
3814279     3
3814280     4

правила

  • Вам не нужно поддерживать десятичные дроби, хотя вы можете.
  • Вы должны поддержать ввод по крайней мере 3814280 = ceiling(e^e^e).
  • Вы не можете жестко кодировать значения, как 3814280. (Ваша программа должна теоретически поддерживать более высокие числа.) Я хочу, чтобы алгоритм был реализован.
  • Самый короткий код выигрывает.

Родственный OEIS

mbomb007
источник
Связанный.
Оливер Ни

Ответы:

14

Желе , 8 байт

ÆlÐĿĊḊi1

Попробуйте онлайн! или проверьте все контрольные примеры .

Задний план

Мы начинаем с последовательного получения натуральных логарифмов входных данных и последующих результатов, пока результат не перестанет меняться. Это работает, потому что расширение натурального логарифма на комплексную плоскость имеет фиксированную точку ; если z = e -W (-1) ≈ 0.318 + 1.337i - где W обозначает функцию W Ламберта - мы имеем log (z) = z .

Для ввода n , после вычисления [n, log (n), log (log (n)),…, z] , мы сначала применяем функцию потолка к каждому из результатов. Реализация Jelly ( Ċ) на самом деле вместо этого вычисляет мнимую часть комплексного числа , но мы все равно не заинтересованы в этом.

Как только k- е приложение log выдаст значение, меньшее или равное 1 , Ċвернет 1 в первый раз. Основанный на 0 индекс этого первого 1 является желаемым результатом.

Простая реализация (вычисление на основе индекса 1, декремент) завершается неудачей из-за граничного случая 0 , который не имеет 1 в своем списке логарифмов. На самом деле, для входа 0 последовательность логарифмов

[0, None]

Это потому, что логарифм Jelly ( Æl) перегружен; сначала он пытается math.log(реальный логарифм), затем cmath.log(сложный логарифм) и, наконец, «сдается» и возвращается None. К счастью, Ċаналогичным образом перегружается и просто возвращает аргумент, если не может округлить или принять мнимую часть.

Аналогично, ввод 1 возвращает

[1, 0, None]

которые могут создавать проблемы в других подходах, которые включают или не включают Ċ.

Один из способов решения этой проблемы - применить (удалить из очереди; удаляет первый элемент) к массиву логарифмов. Это карты

0ÆlÐĿ -> [0, None]    -> [None]
1ÆlÐĿ -> [1, 0, None] -> [0, None]

так что ни один список не имеет 1 сейчас. Таким образом, поиск индекса первого 1 вернет 0 (не найдено), что является желаемым выходом для входов 0 и 1 .

Как это работает

ÆlÐĿĊḊi1  Main link. Argument: n (non-negative integer)

  ÐĿ      Apply the following link until the results are no longer unique.
Æl          Natural logarithm.
          Return the array of all unique results.
    Ċ     Round all resulting real numbers up to the nearest integer. This takes
          the imaginary part of complex numbers and does nothing for non-numbers.
     Ḋ    Dequeue; remove the first item (n) of the array of results.
      i1  Find the first index of 1 (0 if not found).

Это один из трех атомов в желе, которые перегружены неочевидным образом.

Деннис
источник
11

Желе , 9 байт

Æl>1$пL’

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

Тестирование. (Слегка изменено.)

объяснение

Æl>1$пL’
     п    while loop, collect all intermediate results.
  >1$      condition: z>1
Æl         body: natural logarithm.
       L   length of the array containing all intermediate results,
           meaning number of iterations
        ’  minus one.
Дрянная Монахиня
источник
7

Javascript, 45 27 26 байт

l=a=>a>1&&1+l(Math.log(a))

Вот тестовый набор (3-я версия)

Спасибо @LeakyNun за сохранение 1 байта с условной и последующей конвертацией функции в лямбду, и @Neil за указание на ложь - это нормально, возвращаемое значение для <= 1 (измененный тест на == вместо ===)

CShark
источник
Я делал это без es6, но да, это было бы на 1 байт короче, спасибо.
CShark
Почему бы вам не использовать лямбду?
Дрянная Монахиня
нет веской причины, я просто не использовал это так много, так что это не мой первый инстинкт
CShark
По-видимому, нам разрешено возвращать falseвместо 0 (так как он автоматически преобразуется в 0 в целочисленном выражении), и в этом случае вы можете удалить |0.
Нил
Это позволило бы сэкономить 1 байт, но что вы подразумеваете под «он автоматически преобразует в 0»? Что это такое"?
CShark
6

Mathematica, 21 байт

If[#>1,1+#0@Log@#,0]&

Рекурсивная анонимная функция. Принимает целое число в качестве входных данных и возвращает его супер-логарифм в качестве выходных данных. Просто использует данное определение.

LegionMammal978
источник
3
Я на самом деле посмотрел заранее, чтобы увидеть, есть ли встроенный. Я был удивлен, когда не было. : D
mbomb007
5

Pyth, 10 байт

L&>b1hy.lb

Тестирование.

Это определяет функцию.

Дрянная Монахиня
источник
Я не вижу результатов в вашем наборе тестов. Просто куча пустых строк на выходе.
mbomb007
@ mbomb007 Исправлено.
Дрянная Монахиня
Путь круче: tl.u?>N1.l;-)
Якуб
@Jakube Вы можете опубликовать это!
Утренняя монахиня
5

Haskell, 23 байта

l x|x>1=1+l(log x)|1<2=0

Пример использования: l 3814280-> 4.

Ними
источник
4

Python 3, 45 байт

import math
s=lambda x:x>1and-~s(math.log(x))

Ибо x <= 1, это возвращает False(который находится == 0в Python).

Линн
источник
Да, Falseможно использовать для 0.
mbomb007
Кроме того, вы победили мою наивную реализацию (используя, andа не if else). Грац.
mbomb007
4

05AB1E, 16 13 байт

[Dî2‹#¼žr.n]¾

объяснение

              # implicit input n
[          ]  # infinite loop
 Dî2‹#        # break if n rounded up is less than 2
      ¼       # else, increase counter
       žr.n   # set next n = log(n)
            ¾ # push counter and implicitly print

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

Emigna
источник
3

MATL , 15 12 байт

0`ZetG>~}x@q

Попробуйте онлайн! Или проверьте все контрольные примеры (слегка измененная версия для обработки нескольких входов).

Как это работает

Начиная с 0, применять повторное возведение в степень до превышения входного значения. На выходе получается количество итераций минус 1.

0       % Push 0
`       % Do...while loop
  Ze    %   Exponential
  t     %   Duplicate
  G     %   Push input
  >~    %   Is current value less than or equal to the input? If so: next iteration
}       % Finally (code executed at the end of the last iteration)
  x     %   Delete
  @q    %   Iteration index minus 1
        % Implicitly end loop
        % Implicitly display stack
Луис Мендо
источник
3

J , 21 19 18 16 байт

Сохранено 2 байта для «Нечистой монахини», 1 байт для Галена Иванова и 2 байта для «FrownyFrog»!

2#@}.(0>.^.)^:a:

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

Контрольные примеры

ls =: >:@$:@^.`0:@.(<:&1)
   ls 0
0
   ls 1
0
   ls 2
1
   ls 3
2
   ls 4
2
   ls 15
2
   ls 16
3
   ls 3814280
4
Конор О'Брайен
источник
Вот мое 18-байтовое решение: 2#@}.^.^:(0<])^:a:(Я начал совать то, что оказалось дублированием этой проблемы.)
Гален Иванов
2#@}.(0>.^.)^:a:похоже на работу.
FrownyFrog
Не уверен, что это эквивалентно.
FrownyFrog
2

MATLAB / Octave, 44 байта

function a=g(n);a=0;if n>1;a=1+g(log(n));end

Пытался сделать все это как одну анонимную функцию, но я забыл, что MATLAB / Octave продолжает оценивать выражения, даже если они умножаются на логическое значение false (ноль):

f=@(n)(n>1)*(1+f(log(n)))

costrom
источник
Да, было бы неплохо иметь короткозамкнутый продукт :-)
Луис Мендо
2

R, 38 37 байт

f=function(x)if(x>1)1+f(log(x))else 0

Спасибо @ user5957401 за дополнительный байт!

Тестовые случаи:

> f(0)
[1] 0
> f(1)
[1] 0
> f(2)
[1] 1
> f(3)
[1] 2
> f(4)
[1] 2
> f(3814279)
[1] 3
> f(3814280)
[1] 4
plannapus
источник
Я думаю, что вы можете сохранить байт, используя буквальное выражение if, else. т.е. if(x>1)1+f(log(x))else 0на один байт короче.
user5957401
2

R , 34 байта

f=pryr::f(`if`(n>1,1+f(log(n)),0))

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

Возможен нерекурсивный подход: 36 байтов и он принимает входные данные от стандартного ввода.

n=scan()
while((n=log(n))>0)F=F+1
+F
rturnbull
источник
2

Java 7, 47 байт

int c(double n){return n>1?1+c(Math.log(n)):0;}

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

Вышеуказанный рекурсивный метод стиля Java 7 на 2 байта короче, чем итеративный лямбда-стиль Java 8:

n->{int c=0;for(;n>1;c++)n=Math.log(n);return c;}

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

Объяснение:

int c(double n){      // Method with double parameter and integer return-type
  return n>1?         //  If the input is larger than 1:
    1+                //   Return 1 +
      c(Math.log(n))  //   A recursive call with log(input)
   :                  //  Else:
    0;                //   Return 0 instead

n->{                  // Method with double parameter and integer return-type
  int c=0;            //  Create a counter, starting at 0
  for(;n>1;           //  Loop as long as the input is still larger than 1:
    c++)              //   Increase the counter by 1
    n=Math.log(n);    //   And update the input to log(input)
  return c;}          //  After the loop: return the counter as result
Кевин Круйссен
источник
Вы можете получить его короче с лямбда Java 8.
mbomb007
@ mbomb007 ответил три года спустя, ха-ха .. (в то время я занимался только программированием в Java 7), но все же отвечу на твой вопрос: нет, к сожалению, лямбда-версия Java 8 на 2 байта длиннее рекурсивного метода. Я добавил это в свой ответ, и я также добавил объяснение.
Кевин Круйссен
Так ты не можешь делать рекурсивные лямбды?
mbomb007
@ mbomb007 Нет, на Java, к сожалению, нет. В Python, JavaScript и, как мне кажется, в C # .NET рекурсивные лямбды возможны, но в Java по какой-то причине нет.
Кевин Круйссен,
1

Emacs Lisp, 38 байт

(defun l(n)(if(> n 1)(1+(l(log n)))0))

Testcases:

(mapcar 'l '(0 1 2 3 4 15 16 3814279 3814280))
;; (0 0 1 2 2 2 3 3 4)
Лорд юума
источник
1

Желе , 8 байт

-Ælß$Ị?‘

Простая реализация определения. Попробуйте онлайн! или проверьте все контрольные примеры .

Как это работает

-Ælß$Ị?‘  Main link. Argument: x

     Ị    Insignificant; test if |x| ≤ 1.
      ?   If the result is 1:
-           Return -1.
          Else:
   $        Execute the monadic chain formed by the two links to the left.
Æl            Apply natural logarithm to x.
  ß           Recursively call the main link.
       ‘  Increment the result.
Деннис
источник
1

Perl 5, 35 байт

Очень просто, требует -M5.016(что бесплатно) включить __SUB__ключевое слово для анонимной рекурсии.

sub{$_[0]>1?1+__SUB__->(log pop):0}

Другая альтернатива

sub{$_[0]>1?1+__SUB__->(log pop):0}

который составляет 34 байта и дает одинаковые выходные данные для всех входов> 1, но возвращает специальное ложное значение для входов <= 1. False численно равно нулю, но печатает как «» (пустая строка), поэтому, вероятно, не не имеет права

Hobbs
источник
Отличный ответ. Вы можете выиграть 1 байт, sub{($_=pop)>1?1+__SUB__->(log):0}хотя
Дада
1

CJam (16 байт)

rd{_1>}{_ml}w],(

Онлайн демо

Простой цикл с предварительным условием. (То, что я действительно хочу здесь, это операция развертывания в стиле Golfscript, но у CJam ее нет, а плавающая точка в GolfScript грязная и совсем не похожая на гольф).

Питер Тейлор
источник
Кроме того, это мой 80-й ответ по математике и принес мне мой второй значок метки сегодня.
Питер Тейлор
1

PARI / GP , 24 байта

Просто прямая рекурсия.

f(n)=if(n>1,1+f(log(n)))
Чарльз
источник
1

Ракетка, 61 байт

(λ(x)(letrec([a(λ(b)(if(> b 1)(+ 1 (a(log b)))0))])(a x)))
Стивен Х.
источник
1

Клен, 32,30 29 байт

f:=x->`if`(x>1,1+f(log(x)),0)

Тестовые случаи:

> f(0.);
  0
> f(1.);
  0
> f(2.);
  1
> f(3.);
  2
> f(4.);
  2
> f(3814279.);
  3
> f(3814280.);
  4
DSkoog
источник
1

R, 36 байт

Немного другой подход от Plannapus

->n;a=0;while(n>1){a=a+1;n=log(n)};a

Использует правильное назначение для запуска кода - поэтому желаемое число должно предшествовать ему. т.е.

10->n;a=0;while(n>1){a=a+1;n=log(n)};a
user5957401
источник
0

Mathematica, 29 байт

Простой, как весь ад, и работает для комично больших и отрицательных входов:

f[x_]:=If[x>1,1+f[Log[x]],0]

введите описание изображения здесь

Landak
источник
0

Perl 6 , 21 байт

{($_,*.log...1>=*)-1}

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

Заключенное в скобки выражение является последовательностью. $_, аргумент функции, является первым элементом. *.logгенерирует каждый последующий элемент, беря журнал предыдущего элемента. Последовательность продолжается до тех пор, пока конечное условие не 1 >= *станет истинным: 1 больше или равно текущему элементу. Вычитание 1 из последовательности приводит его к числу: его длина.

Шон
источник