Penyebut seri harmonik

16

Sebelumnya, kami melakukan pseudofactorial angka, yang merupakan LCM angka dari 1ke n.

Ini akan berguna dalam menambahkan pecahan bersama.

Namun, kami menemukan bahwa penyebut 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6adalah 20bukan pseudofactorial dari 6, yang 60.

Tugas Anda adalah menemukan penyebut 1/1 + 1/2 + ... + 1/nbilangan bulat positif yang diberikan n.

testcases

 n result
 1 1
 2 2
 3 6
 4 12
 5 60
 6 20
 7 140
 8 280
 9 2520
10 2520
11 27720
12 27720
13 360360
14 360360
15 360360
16 720720
17 12252240
18 4084080
19 77597520
20 15519504
21 5173168
22 5173168
23 118982864
24 356948592
25 8923714800
26 8923714800
27 80313433200
28 80313433200
29 2329089562800
30 2329089562800

Referensi

Papan peringkat

Tampilkan cuplikan kode

code-golf sequence bocor Nun
sumber
Seberapa besar input yang harus digunakan?
Brad Gilbert b2gills
@ BradGilbertb2gills Sebesar wajar.
Leaky Nun

Jawaban:

8

M , 9 6 byte

Terima kasih kepada FryAmTheEggman karena telah menghemat 3 byte! Kode:

RİSg¹İ

M memiliki keuntungan besar di sini, karena ia bekerja dengan pecahan daripada mengapung. Penjelasan:

R       # Get the list [1 ... n].
 İ      # Inverse each, resulting into [1/1, 1/2, 1/3, ..., 1/n].
  S     # Sum it up. (86021/27720 for n=12)
   g¹   # Compute the greatest common denominator with n. (1/27720 for n=12)
     İ  # Calculate the inverse again. (27720 for n=12)

Menggunakan pengodean Jelly . Cobalah online! .

Juga, ada solusi 4-byte , yang kadang-kadang menghasilkan nol terkemuka (misalnya 280 -> 0280). Saya tidak yakin apakah ini diizinkan atau tidak:

RİSV

Cobalah online! .

Adnan
sumber
1
1. Penjelasan kode 6-byte tidak sepenuhnya benar. g¹menghitung pembagi umum fraksi dan n . Menggunakan g1mungkin akan lebih jelas. 2. Vmelemparkan fraksi ke string dan mengevolasinya secara niladis. <num>/adalah (non-kumulatif) dikurangi oleh operator niladik. Ini omong kosong, tetapi karena hanya ada satu angka (argumen implisit 0 ), itu tidak melakukan apa-apa. Tautan berikutnya, penyebutnya, adalah niladic, sehingga nilai pengembalian sebelumnya dicetak secara implisit dan diganti dengan nilad itu.
Dennis
@Dennis Terima kasih! Memperbaiki penjelasannya.
Adnan
@ Adnan Apakah ada dokumentasi untuk M?
Buah Esolanging
@ Challenger5 Bukan yang saya tahu. Ini sebenarnya adalah varian dari Jelly, tetapi dengan fraksi presisi yang sewenang-wenang. Dokumentasi Jelly dapat digunakan, tetapi perlu diingat bahwa banyak fitur yang diimplementasikan dalam Jelly tidak diimplementasikan pada M.
Adnan
5

Julia, 22 byte

Fungsi anonim.

n->1.//(1:n)|>sum|>den
Lynn
sumber
Panjang yang sama:n->sum(inv,1//1:n).den
Alex A.
4

Mathematica, 27 byte

Fungsi anonim.

Denominator@*HarmonicNumber

Sebagai contoh:

 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520
Lynn
sumber
Anda bisa menemukan solusi 26-byte jika Anda menggali ke dalam obrolan :)
Leaky Nun
Oh! Saya harus membiarkan Martin memposting yang itu, jika dia suka. Yang satu ini sangat harafiah, jadi saya akan menyimpannya.
Lynn
Apakah Anda mencontohkan bagaimana kode digunakan?
DavidC
3

Python 2, 69 67 byte

a=b=k=r=1
exec'a=a*k+b;b*=k;k+=1;'*input()
while r*a%b:r+=1
print r

Uji di Ideone .

Bagaimana itu bekerja

Misalkan H (n) adalah jumlah dari inversi multiplikatif dari bilangan bulat n positif pertama . Setiap saat, kita memiliki bahwa a / b = 1 + H (k - 1) . Faktanya, a , b , dan k semuanya diinisialisasi ke 1 , dan 1/1 = 1 = 1 + H (0) .

Kami ulangi cuplikan kode

a=a*k+b;b*=k;k+=1;

(sebagai string) n (input) kali dan jalankan hasilnya. Di setiap langkah, kami memperbarui a , b , dan k menggunakan identitas a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk .

Setelah semua salinan dieksekusi, a / b = 1 + H (n) , yang memiliki penyebut yang sama dengan H (n) .

Bentuk a / b yang tereduksi sepenuhnya adalah (a cd gcd (a, b)) / (b ÷ gcd (a, b)) . Alih-alih menghitung pembagi umum terbesar, kita menginisialisasi r sebagai 1 dan terus bertambah r sampai ra adalah kelipatan b .

Jelas, ini membuat ra kelipatan a dan b paling tidak umum . Karena gcd (a, b) · lcm (a, b) = ab , kita memiliki b ÷ gcd (a, b) = lcm (a, b) ÷ a = ra ÷ a = r , membuat r output yang diinginkan.

Dennis
sumber
3

Haskell, 52

Import Data.Ratio
f n=denominator$sum[1%k|k<-[1..n]]

Jika file dimuat ke GHCI, f dapat digunakan sebagai fungsi.

Vaelus
sumber
1
Mungkin maksud Anda importhuruf kecil? Menghemat satu byte untuk menggunakan mapalih - alih pemahaman:sum$map(1%)[1..n]
xnor
2

Jelly, 9 byte

!©÷RSg®®÷

Coba di sini.

             Argument: n
! ÷R         Compute [n!÷1, n!÷2, … n!÷n].
 ©             (And store n! in the register.)
    S        Find the sum of this list.
     g®      GCD with n!.
       ®÷    Divide n! by this GCD.
Lynn
sumber
Saya percaya adalah mungkin untuk mencapai bytecount yang sama tanpa mendaftar itu.
Leaky Nun
2

MATL , 14 13 byte

:p:G:!/s1\&X<

Cobalah online!

Penjelasan

Untuk input N , output dibatasi oleh N ! (faktorial N ). Kode menghitung n / k untuk n = 1, ..., N ! dan untuk k = 1, ..., N . Kemudian jumlah dari k , yang memberikan bilangan harmonik dikalikan dengan masing-masing n . Hasil yang diinginkan adalah indeks n dari nilai-nilai pertama yang merupakan bilangan bulat.

Luis Mendo
sumber
2

Ruby, 57 47 byte

->n{(1..n).reduce{|a,i|a+1.to_r/i}.denominator}

Terima kasih kepada Kevin Lau untuk mempersingkat ini dengan sepuluh byte.

Peter Kagey
sumber
Tetapkan variabel 1.to_ragar Anda tidak perlu melakukan injeksi string dan konversi. Juga, karena default Ruby reduceadalah untuk menggunakan elemen pertama sebagai inisial, dan 1/1=1, Anda tidak perlu menetapkan secara spesifik 0sebagai nilai awal.
Value Ink
2

Mathematica, 26 byte

Denominator@Tr[1/Range@#]&

Fungsi tanpa nama mengambil nsebagai input dan mengembalikan penyebut. Menggunakan trik standar penyalahgunaan Tr(trace) untuk menjumlahkan daftar timbal balik.

Martin Ender
sumber
1

JavaScript (ES6), 88 byte

m=>{for(d=1,i=0;i<m;d*=++i);for(n=i=0;i<m;n+=d/++i);for(g=d;g;[g,n]=[n%g,g]);return d/n}

Hanya bekerja hingga m = 20 karena batas ketepatan numerik JavaScript.

Neil
sumber
1

05AB1E , 8 byte

Kode:

!йL/O¿/

Penjelasan:

!         # Take the factorial of the input.
 Ð        # Triplicate this.
  ¹L      # Get the list [1 ... input].
    /O    # Divide and sum up.
      ¿   # Get the GCD of the sum and the factorial.
       /  # Divide the factorial by this.

Mungkin ada beberapa masalah akurasi untuk n> 19 karena divisi Python ... Menggunakan pengkodean CP-1252 .

Cobalah online! .

Adnan
sumber
0

J, 20 byte

(!%!+.[:+/!%1+i.)@x:

Berdasarkan pendekatan yang digunakan oleh solusi @ Lynn .

Jika presisi tidak diperlukan untuk nilai n yang besar atau jika kita dapat mengasumsikan n akan diteruskan sebagai bilangan bulat yang diperluas, diakhiri dengan x, solusi yang lebih pendek dapat digunakan untuk 15 byte .

!%!+.[:+/!%1+i.

Pemakaian

   f =: (!%!+.[:+/!%1+i.)@x:
   f 30
2329089562800
   (,:f"0) >: i. 15
1 2 3  4  5  6   7   8    9   10    11    12     13     14     15
1 2 6 12 60 20 140 280 2520 2520 27720 27720 360360 360360 360360

Penjelasan

(!%!+.[:+/!%1+i.)@x:  Input: n
                  x:  Convert n into an extended integer
              i.      Creates the range [0, 1, ..., n-1]
            1+        Add one to each, range is now [1, 2, ..., n]
          !           Get factorial of n
           %          Divide n! by each value in the range [1, 2, ..., n]
      [:+/            Sum those values
   !                  Get n!
    +.                Get gcd between n! and the sum
 !                    Get n!
  %                   Divide n! by the gcd and return
mil
sumber
0

Perl 6 ,  36  32 byte

{([+] 1.FatRat X/1..$_).denominator}
{([+] 1.FatRat X/1..$_).nude[1]}

Penjelasan:

{
  (
    [+]        # reduce with &infix:<+>

      # the following produces a Seq of Rational numbers
      # 1/1, 1/2, 1/3 ... 1/n

      1.FatRat # FatRat.new: 1,1
      X/       # crossed using &infix:</>
      1 .. $_  # Range from 1 to the input inclusive

  ) # resulting in a FatRat

  .nude # (nu)merator (de)nominator
  .[1]  # grab the denominator
}

Uji:

my &hd = {([+] 1.FatRat X/1..$_).nude[1]}

say (1..10)».&hd; # (1 2 6 12 60 20 140 280 2520 2520)

say hd 100; # 2788815009188499086581352357412492142272
say chars hd 1000; # 433
say chars hd 10000; # 4345
Brad Gilbert b2gills
sumber
0

Hoon , 95 byte

|=
@
=+
n=(gulf 1 +<)
=+
f=(roll n mul)
(div f d:(egcd f (roll (turn n |=(@ (div f +<))) add)))

Buat daftar [1...n], lipat dengan ++muluntuk faktorial, buat daftar [n!/1, n!/2, ... n!/n]dan jumlah, temukan GCD darin! dan daftar, dan bagi faktorial dengan angka itu.

Mungkin ada cara yang jauh lebih mudah untuk menghitung penyebutnya, tapi saya tidak bisa mengetahuinya: /

Pengaturan rendering
sumber
Oh Hoon, mengapa tokenizer Anda membutuhkan begitu banyak ruang putih yang berlebihan?
Leaky Nun
Semua entri Hoon saya terlihat jelek karena baris baru :( Kode Hoon normal menggunakan dua spasi di antara token, tetapi satu baris baru lebih pendek
RenderSettings
0

Python 3, 153 150 146 142 byte

Saya yakin ini bisa bermain golf lebih lanjut. Tapi saya baru di sini

f=lambda x:0**x or x*f(x-1)
z=int(input());i=f(z)
r=sum(i/y for y in range(1,z+1))  
p=lambda a,b:a if b<1else not a%b+b or p(b,a%b)
print(i/p(r,i))
George
sumber
Selamat datang di PPCG!
Leaky Nun
0

Aksioma, 34 byte

f(x)==denominator(sum(1/n,n=1..x))

uji 

(24) -> [[i,f(i)] for i in 1..30]
   (24)
   [[1,1], [2,2], [3,6], [4,12], [5,60], [6,20], [7,140], [8,280], [9,2520],
    [10,2520], [11,27720], [12,27720], [13,360360], [14,360360], [15,360360],
    [16,720720], [17,12252240], [18,4084080], [19,77597520], [20,15519504],
    [21,5173168], [22,5173168], [23,118982864], [24,356948592],
    [25,8923714800], [26,8923714800], [27,80313433200], [28,80313433200],
    [29,2329089562800], [30,2329089562800]]
                                       Type: List List Expression Integer
RosLuP
sumber
0

PHP, 81 Bytes

for($p=1;$z++<$argn;$n=$n*$z+$p/$z)$p*=$z;for($t=1+$n;$p%--$t||$n%$t;);echo$p/$t;

Cobalah online!

Jörg Hülsermann
sumber