Nenner der harmonischen Reihe

16

Früher haben wir das Pseudofaktor einer Zahl gemacht, die das LCM der Zahlen von 1bis ist n.

Es wäre nützlich, wenn Brüche addiert würden.

Allerdings finden wir , dass der Nenner 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6ist 20anstelle des pseudofactorial von 6, das ist 60.

Ihre Aufgabe ist es, den Nenner einer 1/1 + 1/2 + ... + 1/nbestimmten positiven ganzen Zahl zu finden n.

Testfälle

 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

Verweise

Bestenliste

Code-Snippet anzeigen

code-golf sequence Undichte Nonne
quelle
Wie groß muss der Input sein?
Brad Gilbert b2gills
@ BradGilbertb2gills So groß wie vernünftig ist.
Undichte Nonne

Antworten:

8

M , 9 6 Bytes

Danke an FryAmTheEggman für das Speichern von 3 Bytes! Code:

RİSg¹İ

M hat hier einen großen Vorteil, weil es eher mit Brüchen als mit Floats arbeitet. Erläuterung:

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)

Verwendet die Jelly-Codierung . Probieren Sie es online! .

Es gibt auch eine 4-Byte- Lösung, die manchmal eine führende Null ausgibt (z 280 -> 0280. B. ). Ich bin mir nicht sicher, ob das erlaubt ist oder nicht:

RİSV

Probieren Sie es online! .

Adnan
quelle
1
1. Die Erklärung des 6-Byte-Codes ist nicht ganz korrekt. g¹berechnet den größten gemeinsamen Teiler der Fraktion und n . Die Verwendung g1wäre wahrscheinlich klarer. 2. VWirft die Fraktion in eine Zeichenfolge und entfernt sie auf Null. <num>/wird durch einen niladischen Operator (nicht kumulativ) reduziert. Das ist Unsinn, aber da es nur eine Zahl gibt (das implizite Argument 0 ), tut es einfach nichts. Der nächste Link, der Nenner, ist niladisch, daher wird der vorherige Rückgabewert implizit gedruckt und durch diesen Wert ersetzt.
Dennis
@ Tennis Danke! Die Erklärung wurde korrigiert.
Adnan
@Adnan Gibt es Unterlagen für M?
Esolanging Fruit
@ Challenger5 Nicht das ich wüsste. Es ist eigentlich eine Variante von Jelly, aber mit willkürlichen Präzisionsbrüchen. Die Jelly-Dokumentation kann verwendet werden. Beachten Sie jedoch, dass viele in Jelly implementierte Funktionen in M.
Adnan,
5

Julia, 22 Bytes

Eine anonyme Funktion.

n->1.//(1:n)|>sum|>den
Lynn
quelle
Gleiche Länge:n->sum(inv,1//1:n).den
Alex A.
4

Mathematica, 27 Bytes

Eine anonyme Funktion.

Denominator@*HarmonicNumber

Beispielsweise:

 In[1] := (Denominator@*HarmonicNumber)[10]
 Out[1] = 2520
Lynn
quelle
Sie könnten eine 26-Byte-Lösung finden, wenn Sie in den Chat graben :)
Leaky Nun
Oh! Ich sollte Martin das posten lassen, wenn er möchte. Dieser ist wirklich buchstäblich, also werde ich ihn behalten.
Lynn
Würden Sie beispielhaft erläutern, wie der Code verwendet wird?
DavidC
3

Python 2, 69 67 Bytes

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

Teste es auf Ideone .

Wie es funktioniert

Sei H (n) die Summe der multiplikativen Inversen der ersten n positiven ganzen Zahlen. Wir haben immer a / b = 1 + H (k - 1) . Tatsächlich a , b und k sind alle initialisierten 1 und 1/1 = 1 = 1 + H (0) .

Wir wiederholen das Code-Snippet

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

(als String) n (Eingabe) mal und führe das Ergebnis aus. In jedem Schritt aktualisieren wir a , b und k unter Verwendung der Identität a / b + 1 / k = ak / bk + b / bk = (ak + b) / bk .

Nachdem alle Kopien ausgeführt wurden, ist a / b = 1 + H (n) , was den gleichen Nenner wie H (n) hat .

Die vollständig reduzierte Form von a / b ist (a ≤ gcd (a, b)) / (b ≤ gcd (a, b)) . Anstatt den größten gemeinsamen Divisor zu berechnen, initialisieren wir r als 1 und erhöhen r weiter, bis ra ein Vielfaches von b ist .

Klar macht das ra am wenigsten verbreiteten Vielfachen von a und b . Da gcd (a, b) · lcm (a, b) = ab ist, ist b ÷ gcd (a, b) = lcm (a, b) ÷ a = ra ÷ a = r , was r zur gewünschten Ausgabe macht.

Dennis
quelle
3

Haskell, 52

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

Wenn die Datei in GHCI geladen ist, kann f als Funktion verwendet werden.

Vaelus
quelle
1
Vermutlich meinst du importKleinbuchstaben? Es wird ein Byte mapsum$map(1%)[1..n]
gespeichert
2

Gelee, 9 Bytes

!©÷RSg®®÷

Probieren Sie es hier aus.

             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
quelle
Ich glaube, es ist möglich, dasselbe bytecount ohne dieses Register zu erreichen.
Undichte Nonne
2

MATL , 14 13 Bytes

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

Probieren Sie es online!

Erläuterung

Für den Eingang N ist der Ausgang durch N begrenzt ! (Fakultät von N ). Der Code berechnet n / k für n = 1, ..., N ! und k = 1, ..., N . Dann summiert es sich über k , was die mit jedem n multiplizierte harmonische Zahl ergibt . Das gewünschte Ergebnis ist der Index n des ersten dieser Werte, der eine ganze Zahl ist.

Luis Mendo
quelle
2

Ruby, 57 47 Bytes

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

Vielen Dank an Kevin Lau für die Verkürzung um zehn Bytes.

Peter Kagey
quelle
Weisen Sie eine Variable zu, 1.to_rdamit Sie keine Zeichenfolgen einfügen und konvertieren müssen. Da in Rubys Standardeinstellung für reducedas erste Element als Anfangsbuchstabe verwendet wird 1/1=1, müssen Sie diesen 0Wert nicht speziell festlegen .
Wert Tinte
2

Mathematica, 26 Bytes

Denominator@Tr[1/Range@#]&

Eine unbenannte Funktion, die nals Eingabe den Nenner zurückgibt. Verwendet den Standardtrick des Missbrauchs Tr(Trace), um die Liste der Reziprozitäten zu summieren.

Martin Ender
quelle
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}

Funktioniert aufgrund der Grenzen der numerischen Genauigkeit von JavaScript nur bis zu m = 20.

Neil
quelle
1

05AB1E , 8 Bytes

Code:

!йL/O¿/

Erläuterung:

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

Aufgrund der Python-Division kann es bei n> 19 zu Genauigkeitsproblemen kommen ... Verwendet den CP-1252 Codierung.

Probieren Sie es online! .

Adnan
quelle
0

J, 20 Bytes

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

Basierend auf dem Ansatz der @ Lynn- Lösung .

Wenn für große Werte von n keine Genauigkeit erforderlich ist oder wenn angenommen wird, dass n als erweiterte Ganzzahl mit dem Suffix "" übergeben wird x, kann eine kürzere Lösung für 15 Byte verwendet werden .

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

Verwendung

   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

Erläuterung

(!%!+.[:+/!%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
Meilen
quelle
0

Perl 6 ,  36  32 Bytes

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

Erläuterung:

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

Prüfung:

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
quelle
0

Hoon , 95 Bytes

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

Erstellen Sie eine Liste [1...n], falten Sie sie mit ++mulder Fakultät um, erstellen Sie eine Liste [n!/1, n!/2, ... n!/n]und addieren Sie sie, suchen Sie die GCD von n!und die Liste und dividieren Sie die Fakultät durch diese Zahl.

Es gibt wahrscheinlich einen viel einfacheren Weg, den Nenner zu berechnen, aber ich kann es nicht herausfinden: /

Rendereinstellungen
quelle
Oh Hoon, warum benötigt Ihr Tokenizer so viele redundante Leerzeichen?
Undichte Nonne
Alle meine Hoon-Einträge sehen wegen der Zeilenumbrüche hässlich aus :( Normaler Hoon-Code verwendet zwei Leerzeichen zwischen Token, aber eine Zeile ist kürzer
RenderSettings
0

Python 3, 153 150 146 142 Bytes

Ich bin sicher, das kann weiter Golf spielen. Aber ich bin neu hier

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
quelle
Willkommen bei PPCG!
Undichte Nonne
0

Axiom, 34 Bytes

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

Prüfung 

(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
quelle
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;

Probieren Sie es online!

Jörg Hülsermann
quelle