Mianownik szeregów harmonicznych

16

Wcześniej robiliśmy pseudofactorial z liczby, która jest LCM liczb od 1do n.

Przydałoby się dodać razem ułamki.

Okazuje się jednak, że mianownik 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6jest 20zamiast pseudo czynnikowego 6, który jest 60.

Twoim zadaniem jest znalezienie mianownika 1/1 + 1/2 + ... + 1/npodanej dodatniej liczby całkowitej n.

Przypadki testowe

 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

Bibliografia

Tabela liderów

Pokaż fragment kodu

code-golf sequence Leaky Nun
źródło
Jak duży wkład musi działać?
Brad Gilbert b2gills 13.06.16
@ BradGilbertb2gills Tak duży, jak to rozsądne.
Leaky Nun

Odpowiedzi:

8

M , 9 6 bajtów

Dzięki FryAmTheEggman za oszczędność 3 bajtów! Kod:

RİSg¹İ

M ma tutaj ogromną przewagę, ponieważ działa raczej z ułamkami niż pływakami. Wyjaśnienie:

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)

Wykorzystuje kodowanie Jelly . Wypróbuj online! .

Istnieje również rozwiązanie 4-bajtowe , które czasami wyświetla wiodące zero (np 280 -> 0280.). Nie jestem pewien, czy jest to dozwolone, czy nie:

RİSV

Wypróbuj online! .

Adnan
źródło
1
1. Wyjaśnienie 6-bajtowego kodu nie jest całkiem poprawne. g¹oblicza gratest wspólny dzielnik frakcji i n . Korzystanie g1byłoby prawdopodobnie bardziej zrozumiałe. 2. Vrzuca frakcję na sznurek i ewaluuje ją niladycznie. <num>/jest (niekumulatywne) redukowane przez operator niladyczny. To nonsens, ale ponieważ jest tylko jedna liczba (domyślny argument 0 ), po prostu nic nie robi. Kolejne łącze, mianownik, jest zerowe, więc poprzednia zwracana wartość jest drukowana niejawnie i zastępowana tym niladem.
Dennis
@Dennis Thanks! Naprawiono wyjaśnienie.
Adnan
@Adnan Czy jest jakaś dokumentacja dla M?
Esolanging Fruit
@ Challenger5 Nie wiem o tym. W rzeczywistości jest to wariant galaretki, ale z dowolnymi ułamkami precyzji. Można używać dokumentacji Jelly, ale miej na uwadze, że wiele funkcji zaimplementowanych w Jelly nie jest zaimplementowanych w M.
Adnan
5

Julia, 22 bajty

Anonimowa funkcja.

n->1.//(1:n)|>sum|>den
Lynn
źródło
Ta sama długość:n->sum(inv,1//1:n).den
Alex A.
4

Mathematica, 27 bajtów

Anonimowa funkcja.

Denominator@*HarmonicNumber

Na przykład:

 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520
Lynn
źródło
Możesz znaleźć 26-bajtowe rozwiązanie, jeśli zagłębisz się w czat :)
Leaky Nun
O! Powinienem pozwolić Martinowi opublikować ten, jeśli mu się podoba. Ten jest dosłownie dosłownie, więc go zatrzymam.
Lynn
Czy zilustrowałbyś przykład użycia kodu?
DavidC
3

Python 2, 69 67 bajtów

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

Przetestuj na Ideone .

Jak to działa

Niech H (n) będzie sumą odwrotności multiplikatywnej pierwszych n dodatnich liczb całkowitych. Przez cały czas mamy a / b = 1 + H (k - 1) . W rzeczywistości wszystkie a , b i k są inicjowane na 1 , a 1/1 = 1 = 1 + H (0) .

Powtarzamy fragment kodu

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

(jako ciąg) n (dane wejściowe) razy i wykonaj wynik. Na każdym etapie aktualizujemy a , b i k przy użyciu tożsamości a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk .

Po wykonaniu wszystkich kopii a / b = 1 + H (n) , który ma ten sam mianownik co H (n) .

Całkowicie zredukowana postać a / b to (a ÷ gcd (a, b)) / (b ÷ gcd (a, b)) . Zamiast obliczać największy wspólny dzielnik, inicjalizujemy r jako 1 i zwiększamy r, aż ra będzie wielokrotnością b .

Oczywiście sprawia to, że ra jest najmniejszą wspólną wielokrotnością a i b . Ponieważ gcd (a, b) · lcm (a, b) = ab , mamy to, że b ÷ gcd (a, b) = lcm (a, b) ÷ a = ra ÷ a = r , co daje r pożądaną moc wyjściową.

Dennis
źródło
3

Haskell, 52

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

Jeśli plik jest załadowany do GHCI, f może być użyte jako funkcja.

Vaelus
źródło
1
Prawdopodobnie masz na myśli importmałe litery? Oszczędza bajt, aby użyć mapzamiast zrozumienia:sum$map(1%)[1..n]
xnor
2

Galaretka, 9 bajtów

!©÷RSg®®÷

Wypróbuj tutaj.

             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
źródło
Wierzę, że możliwe jest osiągnięcie tego samego bajtu bez tego rejestru.
Leaky Nun
2

MATL , 14 13 bajtów

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

Wypróbuj online!

Wyjaśnienie

W przypadku wejścia N dane wyjściowe są ograniczone przez N ! (silnia N ). Kod oblicza n / k dla n = 1, ..., N ! i dla k = 1, ..., N . Następnie sumuje się nad k , co daje liczbę harmoniczną pomnożoną przez każdy n . Pożądanym wynikiem jest indeks n pierwszej z tych wartości, która jest liczbą całkowitą.

Luis Mendo
źródło
2

Ruby, 57 47 bajtów

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

Dzięki Kevinowi Lau za skrócenie tego o dziesięć bajtów.

Peter Kagey
źródło
Przypisz zmienną, aby 1.to_rnie trzeba było wstrzykiwać i konwertować łańcucha. Ponadto, ponieważ domyślną wartością Ruby reducejest użycie pierwszego elementu jako wartości początkowej i 1/1=1nie trzeba specjalnie ustawiać 0jako wartości początkowej.
Wartość tuszu
2

Mathematica, 26 bajtów

Denominator@Tr[1/Range@#]&

Funkcja bez nazwy, która przyjmuje ndane wejściowe i zwraca mianownik. Wykorzystuje standardową sztuczkę polegającą na nadużywaniu Tr(śledzenie), aby zsumować listę wzajemności.

Martin Ender
źródło
1

JavaScript (ES6), 88 bajtów

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}

Działa tylko do m = 20 z powodu ograniczeń precyzji liczbowej JavaScript.

Neil
źródło
1

05AB1E , 8 bajtów

Kod:

!йL/O¿/

Wyjaśnienie:

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

Mogą wystąpić pewne problemy z dokładnością dla n> 19 z powodu podziału Pythona ... Używa kodowania CP-1252 .

Wypróbuj online! .

Adnan
źródło
0

J, 20 bajtów

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

W oparciu o podejście zastosowane w rozwiązaniu @ Lynn .

Jeśli precyzja nie jest konieczna dla dużych wartości n lub jeśli możemy założyć, że n zostanie przekazana jako rozszerzona liczba całkowita, z przyrostkiem x, można zastosować krótsze rozwiązanie dla 15 bajtów .

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

Stosowanie

   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

Wyjaśnienie

(!%!+.[:+/!%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
mile
źródło
0

Perl 6 ,  36  32 bajtów

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

Wyjaśnienie:

{
  (
    [+]        # 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
}

Test:

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
źródło
0

Hoon , 95 bajtów

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

Utwórz listę [1...n], złóż ją ++mulza pomocą silni, stwórz listę [n!/1, n!/2, ... n!/n]i zsumuj, znajdź GCD zn! i listę i podziel silnię przez tę liczbę.

Prawdopodobnie istnieje o wiele łatwiejszy sposób obliczenia mianownika, ale nie mogę tego rozgryźć: /

RenderSettings
źródło
Oh Hoon, dlaczego twój tokenizer potrzebuje tak wielu zbędnych białych znaków?
Leaky Nun
Wszystkie moje wpisy Hoon wyglądają brzydko z powodu nowych linii :( Normalny kod Hoon używa dwóch spacji między tokenami, ale jedna nowa linia jest krótsza
RenderSettings
0

Python 3, 153 150 146 142 bajtów

Jestem pewien, że można pograć w golfa dalej. Ale jestem tu nowy

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))
Jerzy
źródło
Witamy w PPCG!
Leaky Nun
0

Aksjomat, 34 bajty

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

test 

(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
źródło
0

PHP, 81 bajtów

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

Wypróbuj online!

Jörg Hülsermann
źródło