Hitung Super-Logaritma

29

Ini harus menjadi tantangan sederhana.

Dengan diberi nomor n >= 0, keluarkan logaritma super-log (atau log *, log-star, atau logaritma iterated , yang setara karena ntidak pernah negatif untuk tantangan ini.) Dari n.

log * (n): = {0 jika n <= 1;  1 + log * (log (n)) jika n> 1}

Ini adalah salah satu dari dua fungsi terbalik untuk tetrasi . Yang lainnya adalah super-root , yang ada dalam pertanyaan terkait .

Contohnya

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

Aturan

  • Anda tidak perlu mendukung desimal, meskipun Anda bisa.
  • Setidaknya Anda perlu mendukung input 3814280 = ceiling(e^e^e).
  • Anda mungkin tidak memberikan kode seperti pada nilai 3814280. (Program Anda secara teoritis harus mendukung angka yang lebih tinggi.) Saya ingin algoritma diterapkan.
  • Kode terpendek menang.

OEIS terkait

mbomb007
sumber
Terkait
Oliver Ni

Jawaban:

14

Jelly , 8 byte

ÆlÐĿĊḊi1

Cobalah online! atau verifikasi semua kasus uji .

Latar Belakang

Kami mulai dengan mengambil logaritma natural dari input dan hasil selanjutnya hingga hasilnya tidak lagi berubah. Ini berfungsi karena ekstensi logaritma natural ke bidang kompleks memiliki titik tetap ; jika z = e -W (-1) ≈ 0.318 + 1.337i - di mana W menunjukkan fungsi Lambert W - kita memiliki log (z) = z .

Untuk input n , setelah menghitung [n, log (n), log (log (n)), ..., z] , pertama-tama kita menerapkan fungsi plafon untuk setiap hasil. Implementasi Jelly ( Ċ) sebenarnya menghitung bagian imajiner dari bilangan kompleks , tetapi kami tetap tidak tertarik dengan ini.

Setelah k th penerapan log menghasilkan nilai kurang dari atau sama dengan 1 , Ċakan kembali 1 untuk pertama kalinya. Indeks berbasis 0 dari yang pertama 1 adalah hasil yang diinginkan.

Implementasi langsung (menghitung indeks berbasis 1, penurunan) gagal karena tepi kasus 0 , yang tidak memiliki 1 dalam daftar logaritma. Bahkan, untuk input 0 , urutan logaritma adalah

[0, None]

Ini karena logaritma Jelly ( Æl) kelebihan beban; pertama kali mencoba math.log(logaritma nyata), kemudian cmath.log(logaritma kompleks), dan akhirnya "menyerah" dan kembali None. Untungnya, Ċkelebihannya juga sama dan hanya mengembalikan argumen jika tidak dapat mengambil atau mengambil bagian imajiner.

Demikian juga, input 1 kembali

[1, 0, None]

yang dapat menciptakan masalah dalam pendekatan lain yang melibatkan atau tidak melibatkan Ċ.

Salah satu cara untuk memperbaiki masalah ini adalah menerapkan (dequeue; menghapus elemen pertama) ke array logaritma. Peta ini

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

jadi daftar tidak memiliki 1 sekarang. Dengan cara ini, menemukan indeks dari 1 pertama akan mengembalikan 0 (tidak ditemukan), yang merupakan output yang diinginkan untuk input 0 dan 1 .

Bagaimana itu bekerja

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

Ini adalah satu dari hanya tiga atom dalam Jelly yang kelebihan muatan secara tidak jelas.

Dennis
sumber
11

Jelly , 9 byte

Æl>1$пL’

Cobalah online!

Suite uji. (Sedikit dimodifikasi.)

Penjelasan

Æ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.
Biarawati Bocor
sumber
7

Javascript, 45 27 26 byte

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

Berikut ini adalah test suite (putaran ke-3)

Terima kasih @LeakyNun untuk menyimpan 1 byte dengan kondisional dan kemudian mengkonversi fungsi ke lambda, dan @Nil untuk menunjukkan false adalah nilai pengembalian ok untuk <= 1 (tes yang diubah menjadi == alih-alih ===)

CShark
sumber
Saya melakukannya tanpa es6, tapi ya itu akan menjadi 1 byte lebih pendek, terima kasih.
CShark
Mengapa Anda tidak menggunakan lambda?
Leaky Nun
tidak ada alasan yang baik, saya hanya belum menggunakannya sebanyak itu, jadi itu bukan insting pertama saya
CShark
Tampaknya kami diizinkan untuk kembali, falsebukan 0 (karena konversi otomatis ke 0 dalam ekspresi integer) dalam hal ini Anda dapat menghapus |0.
Neil
Itu akan menghemat 1 byte, tetapi apa yang Anda maksud dengan "itu secara otomatis mengkonversi ke 0"? Apa itu"?
CShark
6

Mathematica, 21 byte

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

Fungsi anonim rekursif. Mengambil integer sebagai input dan mengembalikan super-logaritma sebagai output. Cukup gunakan definisi yang diberikan.

LegionMammal978
sumber
3
Saya benar-benar melihat ke depan untuk melihat apakah ada built-in. Saya terkejut ketika tidak ada. : D
mbomb007
5

Dyalog APL , 13 byte

Terjemahan langsung OP:

{⍵≤1:0⋄1+∇⍟⍵}

TryAPL online!

Adm
sumber
5

Pyth, 10 byte

L&>b1hy.lb

Suite uji.

Ini mendefinisikan suatu fungsi.

Biarawati Bocor
sumber
Saya tidak melihat output apa pun di ruang tes Anda. Hanya sekelompok garis kosong di output.
mbomb007
@ mbomb007 Diperbaiki.
Leaky Nun
Cara yang lebih dingin: tl.u?>N1.l;-)
Jakube
@ Jakube Anda bisa memposting itu!
Leaky Nun
5

Haskell, 23 byte

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

Contoh penggunaan: l 3814280-> 4.

nimi
sumber
4

Python 3, 45 byte

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

Sebab x <= 1, ini mengembalikan False(yang == 0dalam Python).

Lynn
sumber
Ya, Falsebisa digunakan untuk 0.
mbomb007
Juga, Anda mengalahkan implementasi naif saya (dengan menggunakan anddaripada if else). Terima kasih.
mbomb007
4

05AB1E, 16 13 byte

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

Penjelasan

              # 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

Cobalah online

Emigna
sumber
3

MATL , 15 12 byte

0`ZetG>~}x@q

Cobalah online! Atau verifikasi semua kasus uji (versi yang sedikit dimodifikasi untuk menangani beberapa input).

Bagaimana itu bekerja

Mulai dengan 0, terapkan iterasi eksponensial hingga melebihi input. Outputnya adalah jumlah iterasi minus 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
Luis Mendo
sumber
3

J , 21 19 18 16 byte

Disimpan 2 byte ke Leaky Nun, 1 byte ke Galen Ivanov, dan 2 byte ke FrownyFrog!

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

Cobalah online!

Uji kasus

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
Conor O'Brien
sumber
Inilah solusi 18 byte saya: 2#@}.^.^:(0<])^:a:(Saya mulai menemukan apa yang ternyata merupakan dup dari masalah ini.)
Galen Ivanov
2#@}.(0>.^.)^:a:sepertinya berhasil.
FrownyFrog
Tidak yakin apakah itu setara.
FrownyFrog
2

MATLAB / Oktaf, 44 byte

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

Mencoba melakukan semuanya sebagai satu fungsi anonim, tapi saya lupa bahwa MATLAB / Oktaf terus mengevaluasi ekspresi bahkan jika mereka dikalikan dengan nilai false (nol) boolean:

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

costrom
sumber
Ya, alangkah baiknya memiliki produk hubungan arus pendek :-)
Luis Mendo
2

R, 38 37 byte

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

Terima kasih @ user5957401 untuk byte ekstra!

Kasus uji:

> 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
sumber
Saya pikir Anda dapat menyimpan byte dengan menggunakan pernyataan literal if, else. yaitu if(x>1)1+f(log(x))else 0satu byte lebih pendek.
user5957401
2

R , 34 byte

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

Cobalah online!

Pendekatan non-rekursif dimungkinkan: 36 byte dan mengambil input dari stdin.

n=scan()
while((n=log(n))>0)F=F+1
+F
rturnbull
sumber
2

Java 7, 47 byte

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

Cobalah online.

Metode Java 7 style rekursif di atas adalah 2 byte lebih pendek dari iterasi Java 8 style lambda:

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

Cobalah online.

Penjelasan:

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
Kevin Cruijssen
sumber
Anda mungkin membuatnya lebih pendek dengan lambda Java 8.
mbomb007
@ mbomb007 merespons tiga tahun kemudian, haha ​​.. (pada waktu itu saya hanya bermain golf di Java 7), tetapi untuk tetap menjawab pertanyaan Anda: tidak, sayangnya lambda Java 8 lebih panjang 2 byte daripada metode rekursif. Saya telah menambahkannya ke jawaban saya, dan saya juga menambahkan penjelasan.
Kevin Cruijssen
Jadi Anda tidak bisa melakukan lambda rekursif?
mbomb007
@ mbomb007 Tidak, di Jawa sayangnya tidak. Dalam Python, JavaScript, dan saya pikir C #. NET juga, lambda rekursif dimungkinkan, tetapi di Jawa bukan karena alasan tertentu ..
Kevin Cruijssen
1

Emacs Lisp, 38 byte

(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)
Tuan Yuuma
sumber
1

Jelly , 8 byte

-Ælß$Ị?‘

Implementasi langsung dari definisi. Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

-Æ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.
Dennis
sumber
1

Perl 5, 35 byte

Sangat sederhana, membutuhkan -M5.016(yang gratis) untuk mengaktifkan __SUB__kata kunci untuk rekursi anonim.

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

Alternatif lain adalah

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

yaitu 34 byte, dan memberikan output yang sama untuk semua input> 1, tetapi mengembalikan nilai false khusus untuk input <= 1. False secara numerik sama dengan nol, tetapi dicetak sebagai "" (string kosong), jadi mungkin tidak t memenuhi syarat.

hobbs
sumber
Jawaban yang bagus Anda bisa menang 1 byte dengan melakukan sub{($_=pop)>1?1+__SUB__->(log):0}olah
Dada
1

CJam (16 byte)

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

Demo online

Simpel sambil loop dengan pra-kondisi. (Yang benar-benar saya inginkan di sini adalah operasi buka Golfscript-style, tetapi CJam tidak memilikinya, dan floating point dalam GolfScript berantakan dan sama sekali tidak golfy).

Peter Taylor
sumber
Selain itu, ini adalah jawaban ke 80 saya dalam matematika dan memberi saya lencana tag kedua saya hari ini.
Peter Taylor
1

PARI / GP , 24 byte

Hanya rekursi langsung.

f(n)=if(n>1,1+f(log(n)))
Charles
sumber
1

Racket, 61 byte

(λ(x)(letrec([a(λ(b)(if(> b 1)(+ 1 (a(log b)))0))])(a x)))
Steven H.
sumber
1

Maple, 32,30 29 byte

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

Kasus uji:

> f(0.);
  0
> f(1.);
  0
> f(2.);
  1
> f(3.);
  2
> f(4.);
  2
> f(3814279.);
  3
> f(3814280.);
  4
DSkoog
sumber
1

R, 36 byte

Pendekatan yang sedikit berbeda dari Plannapus

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

Menggunakan hak untuk menjalankan kode - jadi nomor yang diinginkan harus mendahuluinya. yaitu

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

Mathematica, 29 byte

Sederhana sekali, dan bekerja untuk input yang besar dan juga negatif:

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

masukkan deskripsi gambar di sini

Landak
sumber
0

Ruby, 29 byte

l=->n{n<=1?0:1+l[Math.log n]}
Seims
sumber
-1 byte dengan menulis ulang n<=1?a:bsebagai n>1?b:adan -1 byte lebih dengan fungsi lambda anonim .
Simply Beautiful Art
0

Perl 6 , 21 byte

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

Cobalah online!

Ekspresi kurung adalah urutan. $_, argumen ke fungsi, adalah elemen pertama. *.logmenghasilkan setiap elemen berturut-turut dengan mengambil log dari elemen sebelumnya. Urutan berlanjut hingga kondisi akhir,, 1 >= *benar: 1 lebih besar dari atau sama dengan elemen saat ini. Mengurangkan 1 dari urutan memaksa ke nomor: panjangnya.

Sean
sumber