Abrufen eine bestimmte Stelle von einem Expansionsverhältnis in jeder Basis (n-te Ziffer der x / y)

Question

Gibt es einen Algorithmus, der die Ziffern ein Wiederholungs-Dezimal-Verhältnis ohne Start zu Beginn berechnen kann?

Ich bin auf der Suche nach einer Lösung, die nicht willkürlich Größe ganze Zahlen nicht verwendet, da dies für die Fälle funktionieren soll, wo die Dezimalentwicklung beliebig lang sein kann.

Zum Beispiel erweitert 33/59 auf eine sich wiederholende dezimal mit 58 Ziffern. Wenn ich das überprüfen wollte, wie konnte ich die Ziffern berechnen auf der 58. Startplatz?

Herausgegeben - mit dem Verhältnis 2124679/2147483647, wie die hundert Stellen im 2147484600. durch 2147484700. Orte.

Answer 1

OK, 3. Versuch ist ein Charme:)

Ich kann nicht glauben, dass ich über modulare Potenzierung vergessen haben.

So zu stehlen / zusammenfassen aus meiner zweiten Antwort, die n-te Ziffer von x / y ist die erste Ziffer (10 ^n-1 x mod y) / y = Boden (10 * (10 ^n-1 x mod y) / y) mod 10.

Der Teil, der die ganze Zeit in Anspruch nimmt die 10 ^n-1 y mod, aber wir können mit schneller (O (log n)) modulare Exponentiation tun. In diesem Ort ist es nicht einen Versuch wert, den Zyklus-Findungs-Algorithmus zu tun.

Allerdings haben Sie die Möglichkeit, tun müssen, um (a * b mod y) wobei a und b sind Zahlen, die als y so groß sein können. (Wenn y 32 Bits erfordert, dann müssen Sie 32x32 mehrfach tun und dann 64-Bit-% 32-Bit-Modul, oder Sie benötigen einen Algorithmus, der diese Beschränkung umgeht. Siehe meine Liste, die folgt, da ich in diese Einschränkung mit Javascript lief. )

Hier ist also eine neue Version.

function abmody(a,b,y)
{
  var x = 0;
  // binary fun here
  while (a > 0)
  {
    if (a & 1)
      x = (x + b) % y;
    b = (2 * b) % y;
    a >>>= 1;
  }
  return x;
}

function digits2(x,y,n1,n2)
{
  // the nth digit of x/y = floor(10 * (10^(n-1)*x mod y) / y) mod 10.
  var m = n1-1;
  var A = 1, B = 10;
  while (m > 0)
  {
    // loop invariant: 10^(n1-1) = A*(B^m) mod y

    if (m & 1)
    {
      // A = (A * B) % y    but javascript doesn't have enough sig. digits
      A = abmody(A,B,y);
    }
    // B = (B * B) % y    but javascript doesn't have enough sig. digits
    B = abmody(B,B,y);
    m >>>= 1;
  }

  x = x %  y;
  // A = (A * x) % y;
  A = abmody(A,x,y);

  var answer = "";
  for (var i = n1; i <= n2; ++i)
  {
    var digit = Math.floor(10*A/y)%10;
    answer += digit;
    A = (A * 10) % y;
  }
  return answer;
}

(Sie werden bemerken, dass die Strukturen der abmody() und der modularen Potenzierung sind die gleichen, beide sind basierend auf

Answer 2

Bearbeiten (Ich gehe Post hier für die Nachwelt aber bitte Sie upvote es nicht mehr.. Es theoretisch nützlich sein kann, aber es ist nicht wirklich praktisch I Beiträge geschrieben haben eine andere Antwort, die viel nützlicher aus praktischer Sicht ist, erfordert keinen Factoring, und erfordert nicht die Verwendung von bignums.)

---

@ Daniel Bruckner hat den richtigen Ansatz, glaube ich. (Mit ein paar zusätzliche Drehungen erforderlich)

Vielleicht gibt es eine einfachere Methode, aber die folgenden wird immer funktionieren:

Lassen Sie sich die Beispiele q verwenden = x / y = 33/57820 und 44/65 zusätzlich zu 33/59, aus Gründen, die klar in Kürze werden können.

Schritt 1: Faktor der Nenner (speziell ausklammern 2 ist und 5s)

Write q = x / y = x / (2 ^{a ₂} 5 ^{a ₅} z). Faktoren von 2 und 5 im Nenner führen nicht wiederholt Dezimalstellen. So ist der verbleibende Faktor z coprime bis 10. In der Tat ist, erfordert der nächste Schritt z Factoring, so dass Sie könnte genauso gut die ganze Sache Faktor.

Berechnen einer ₁₀ = max (a ₂ a ₅ ), der die kleinste Exponent von 10 ist, die ein Vielfaches der Faktoren ist, von 2 und 5 in y.

In unserem Beispiel 57820 = 2 * 2 * 5 * 7 * 7 * 59, so a ₂ = 2, a ₅ = 1, a ₁₀ = 2, z = 7 * 7 * 59 = 2891.

In unserem Beispiel 33/59, ist 59 eine Primzahl und enthält keine Faktoren von 2 oder 5, so einem ₂ = a ₅ = a ₁₀ = 0

In unserem Beispiel 44/65, 65 = 5 * 13 und ein ₂ = 0, a ₅ = a ₁₀ = 1 .

Gerade als Referenz fand ich einen guten Online-Factoring-Rechner hier . (Auch tut totients, die für den nächsten Schritt wichtig ist)

Schritt 2: Verwenden Sie Eulers Theorem oder Carmichael Theorem .

Was wollen wir eine Zahl n, so dass 10 ⁿ - 1 teilbar durch z, oder in anderen Worten, 10 ⁿ ≡ 1 mod z. Eulersche Funktion φ (z) und Carmichael-Funktion λ (z) werden beide geben Sie gültige Werte für n, mit λ (z) gibt Ihnen die kleinere Anzahl und φ (z) ist vielleicht ein wenig leichter zu berechnen. Dies ist nicht zu hart, es bedeutet nur, z Factoring und eine wenig Mathematik zu tun.

φ (2891) = 7 * 6 * 58 = 2436

λ (2891) = LCM (7 * 6, 58) = 1218

Das bedeutet, dass 10 ²⁴³⁶ ≡ 10 ¹²¹⁸ ≡ 1 (mod 2891).

Für die einfachere Fraktion 33/59, φ (59) = λ (59) = 58, so 10 ⁵⁸ ≡ 1 (mod 59).

44/65 = 44 / (5 * 13), φ (13) = λ (13) = 12.

Was? Nun muss die Periode des sich wiederholenden dezimal beide φ teilen (z) und λ (z), so dass sie Sie effektiv obere Schranken für die Periode des sich wiederholenden dezimal geben.

Schritt 3: Mehr Zahlknirschens

Lassen Sie uns verwenden n = λ (z). Wenn wir Q subtrahieren‘= 10 ^{a ₁₀} x / y von Q '' = 10 ^{(a ₁₀ + n)} x / y, erhalten wir:

m = 10 ^{a ₁₀} (10 ⁿ - 1) x / y

, die eine ganze Zahl ist weil 10 ^{a ₁₀} ist ein Vielfaches der Faktoren von 2 und 5 von Y, und 10 ⁿ -1 ist ein Vielfaches der übrigen Faktoren von y.

Was wir hier getan ist zu verschieben, um die ursprüngliche Anzahl q von einem ₁₀ Plätze frei Q erhalten‘, und links q Verschiebung durch ein ₁₀ + n Orte zu bekommen Q ‚‘, die Dezimalstellen wiederholen, aber der Unterschied zwischen ihnen ist eine ganze Zahl wir berechnen können.

Dann können wir umschreiben x / y als M / 10 ^{a ₁₀} / (10 ⁿ - 1).

Nehmen wir das Beispiel q = 44/65 = 44 / (5 * 13)

a ₁₀ = 1 ist, und λ (13) = 12, so Q‘= 10 ¹ q und Q '' = 10 ^{12 + 1} q.

m = Q '' - Q‘= (10 ¹² - 1) * 10 ¹ * (44/65) =153846153846 * 44 = 6769230769224

q = 6769230769224/10 / (10 ¹² - 1).

Die anderen Fraktionen 33/57820 und 33/59 führen zu größeren Fraktionen.

Schritt 4:. Finden Sie das nicht wiederholt und Dezimal-Teile zu wiederholen

Beachten Sie, dass für k zwischen 1 und 9, k / 9 = 0.kkkkkkkkkkkkk ...

Ebenso beachten Sie, dass eine 2-stellige Zahl kl zwischen 1 und 99, k / 99 = 0.klklklklklkl ...

Dieses verallgemeinert: für k-stellige Muster abc ... ij, diese Zahl abc ... ij / (10 ^k -1) = 0.abc ... ijabc ... ijabc ... ij ...

Wenn Sie das Muster folgen, werden Sie sehen, dass das, was wir tun müssen, ist diese (möglicherweise) große Zahl m nehmen wir im vorherigen Schritt erhalten, und schreiben Sie es als m = s * (10 ⁿ -1) + r, wobei 1 ≤ r <10 ⁿ -1.

Dies führt zur endgültigen Antwort:

• s ist der Nicht-Wiederholungsteil
• r ist die Wiederholungsteil (mit Nullen aufgefüllt auf der linken Seite, wenn notwendig, um sicherzustellen, dass es n Ziffern)
• mit einem ₁₀ = 0, wird der Dezimalpunkt zwischen der nichtwiederholendes und ein Teil zu wiederholen; wenn a ₁₀ > 0, dann wird es sich a ₁₀ Stellen nach links von die Verbindung zwischen s und r.

Für 44/65, erhalten wir 6769230769224 = 6 * (10 ¹² -1) + 769230769230

s = 6, r = 769230769230 und 44/65 = ,6769230769230, wo die unterstrichenen hier den wiederholten Teil bezeichnet.

Sie können die Zahlen kleiner machen, indem den kleinsten Wert von n in Schritt 2 zu finden, indem sie mit der Carmichael-Funktion λ (z) beginnen und zu sehen, wenn einer ihrer Faktoren auf Werte von n führen, so dass 10 ⁿ ≡ 1 (mod z).

Update: Für die Neugierigen, scheinen der Python interpeter der einfachste Weg, um mit bignums zu berechnen. (Pow (x, y) berechnet x ^y und //% und ist ganzzahlige Teilung und Rest, respectively.) Hier ist ein Beispiel:

>>> N = pow(10,12)-1
>>> m = N*pow(10,1)*44//65
>>> m
6769230769224
>>> r=m%N
>>> r
769230769230
>>> s=m//N
>>> s
6
>>> 44/65
0.67692307692307696

>>> N = pow(10,58)-1
>>> m=N*33//59
>>> m
5593220338983050847457627118644067796610169491525423728813
>>> r=m%N
>>> r
5593220338983050847457627118644067796610169491525423728813
>>> s=m//N
>>> s
0
>>> 33/59
0.55932203389830504

>>> N = pow(10,1218)-1
>>> m = N*pow(10,2)*33//57820
>>> m
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> r=m%N
>>> r
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> s=m//N
>>> s
0
>>> 33/57820
0.00057073676928398479

mit dem überladenen Python % String-Operator verwendbar für Zero-Padding, den vollen Satz von wiederholten Ziffern zu sehen:

>>> "%01218d" % r
'0570736769283984780352819093739190591490833621584226911103424420615703908682116
91456243514354894500172950536146662054652369422345209270148737461086129367001037
70321687997232791421653407125562089242476651677620200622621930127983396748529920
44275337253545485991006572120373573158076790038049117952265652023521272915946039
43272224143894846074022829470771359391214112763749567623659633344863369076444136
97682462815634728467658249740574195780006918021445866482186094776893808370805949
49844344517468004150812867519889311656866136285022483569699066067104808024904877
20511933586994119681771013490141819439640262884814942926323071601521964718090626
08094085091663784157730888965755793842960913178830854375648564510549982704946385
33379453476305776547907298512625389138706329989622967831200276720857834659287443
79107575233483223797993773780698720166032514700795572466274645451400899342787962
64268419232099619508820477343479764787270840539605672777585610515392597717052922
86406087858872362504323763403666551366309235558630231753718436527153234175025942
58042199930819785541335178139052231061916291940505015565548253199584918713248011
06883431338637149775164303009339328951919750951227948806641300588031822898650985
8180560359737115185'

Als allgemeine Technik, rationale Fraktionen haben eine nicht-Wiederholung durch einen Wiederholungsteil gefolgt Teil, wie folgt aus:

nnn.xxxxxxxxrrrrrr

xxxxxxxx ist das nicht wiederholte Teil und rrrrrr ist der Wiederholungsteil.

1. Bestimmen Sie die Länge des nicht wiederholten Teils.
2. Wenn die Ziffer in dem betreffenden Teil nicht wiederholt, dann berechnet sie Division direkt verwenden.
3. Wenn die Ziffer in Frage im Wiederholungsteil ist, berechnen ihre Position innerhalb der Wiederholungsfolge (Sie kennen nun die Längen von allem), und die richtige Ziffer auswählen.

Das obige ist eine grobe Skizze und würde mehr Präzision müssen in einem tatsächlichen Algorithmus implementieren, aber es sollte Ihnen den Einstieg.

AHA! Caffiend: Kommentar zu meiner anderen (längeren) Antwort (speziell „doppelte Reste“) führt mich zu einer sehr einfachen Lösung, die O (n), wobei n = die Summe der Längen der nicht wiederholten + Wiederholung Teile ist, und erfordern nur Integer Mathematik mit Zahlen zwischen 0 und 10 * y wobei y der Nenner ist.

Hier ist eine Javascript-Funktion, die n-te Stelle rechts vom Komma für die rationale Zahl x / y zu erhalten:

function digit(x,y,n) 
{ 
   if (n == 0) 
      return Math.floor(x/y)%10; 
   return digit(10*(x%y),y,n-1);
}

Es ist ziemlich rekursiv als iterative, und ist nicht intelligent genug Zyklen zu erkennen (die 10000. Ziffer von 1/3 ist offensichtlich 3, aber das geht immer weiter, bis es die 10000. Iteration erreicht), aber es funktioniert zumindest bis der Stapel der Speicher ausgeht.

Im Grunde ist dies funktioniert, weil von zwei Tatsachen:

• die n-te Ziffer der x / y der (n-1) -ten Ziffer von 10x / y (Beispiel: der 6. Stelle von 1/7 der 5. Stelle von 10/7 ist die 4. Ziffer von 100/7 etc ist ).
• die n-te Ziffer von x / y ist die n-te Ziffer (x% y) / y (Beispiel: der 5. Stelle von 7.10 ist auch die 5. Stelle von 3/7)

Wir können zwicken dies eine iterative Routine zu sein, und kombinieren es mit Floyds Zyklus -finding Algorithmus (die ich als „rho“ -Methode von einer Martin Gardner Säule gelernt), etwas zu bekommen, das diesen Ansatz Verknüpfungen.

Hier ist eine JavaScript-Funktion, die eine Lösung mit diesem Ansatz berechnet:

function digit(x,y,n,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  while (n > 0)
  {
    n--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      n = n % period;
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }
  }
  var answer=Math.floor(x1/y);
  if (returnstruct)
    return {period: period, digit: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digit='+this.digit;
      }};
  else
    return answer;
}

Und ein Beispiel für die n-te Stelle der 1/700 ausgeführt wird:

js>1/700
0.0014285714285714286
js>n=10000000
10000000
js>rs=digit(1,700,n,true)
period=6,digit=4
js>n%6
4
js>rs=digit(1,700,4,true)
period=0,digit=4

Das Gleiche gilt für 33/59:

js>33/59
0.559322033898305
js>rs=digit(33,59,3,true)
period=0,digit=9
js>rs=digit(33,59,61,true)
period=58,digit=9
js>rs=digit(33,59,61+58,true)
period=58,digit=9

Und 122222/990000 (lange nicht wiederholender Teil):

js>122222/990000
0.12345656565656565
js>digit(122222,990000,5,true)
period=0,digit=5
js>digit(122222,990000,7,true)
period=6,digit=5
js>digit(122222,990000,9,true)
period=2,digit=5
js>digit(122222,990000,9999,true)
period=2,digit=5
js>digit(122222,990000,10000,true)
period=2,digit=6

Hier ist eine weitere Funktion, die eine Strecke von Ziffern findet:

// find digits n1 through n2 of x/y
function digits(x,y,n1,n2,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  var answer='';
  while (n2 >= 0)
  {
    // time to print out digits?
    if (n1 <= 0) 
      answer = answer + Math.floor(x1/y);

    n1--,n2--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      if (n1 > period)
      {
        var jumpahead = n1 - (n1 % period);
        n1 -= jumpahead, n2 -= jumpahead;
      }
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }    
  }
  if (returnstruct)
    return {period: period, digits: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digits='+this.digits;
      }};
  else
    return answer;
}

ich die Ergebnisse für Ihre Antwort enthalten haben (vorausgesetzt, dass # 's Javascript tat nicht Überlauf):

js>digit(1,7,1,7,true)
period=6,digits=1428571
js>digit(1,7,601,607,true)
period=6,digits=1428571
js>1/7
0.14285714285714285
js>digit(2124679,214748367,214748300,214748400,true)
period=1759780,digits=20513882650385881630475914166090026658968726872786883636698387559799232373208220950057329190307649696
js>digit(122222,990000,100,110,true)
period=2,digits=65656565656

Ad-hoc-Ich habe keine gute Idee. Vielleicht fortgesetzt Fraktionen helfen können. Ich werde ein wenig darüber nachdenken ...

UPDATE

Aus Fermats kleinen Satz und weil 39 ist prim folgendes gilt. (= zeigt Kongruenz)

10^39 = 10 (39)

Da 10 coprime bis 39.

10^(39 - 1) = 1 (39)

10^38 - 1 = 0 (39)

[to be continued tomorow]

Ich war gestaffelten zu erkennen, dass 39 keine Primzahl ist ... ^^ Ich werde aktualisieren und die Antwort in den nächsten Tagen und präsentieren die ganze Idee. Vielen Dank für die Feststellung, dass 39 keine Primzahl ist.

Die kurze Antwort für a/b mit a < b und einer Periodenlänge p angenommen ...

• berechnen k = (10^p - 1) / b und stellen Sie sicher, dass es eine ganze Zahl, sonst a/b hat nicht einen Zeitraum von p
• berechnen c = k * a
• konvertiert c seinen dezimal represenation und linken Pad mit Nullen auf eine Gesamtlänge von p
• die i-te Stelle nach dem Komma ist das (i mod p) -ten Stelle der paded Dezimaldarstellung (i = 0 die erste Stelle nach dem Komma ist - wir sind Entwickler)

Beispiel

a = 3
b = 7
p = 6

k = (10^6 - 1) / 7
  = 142,857

c = 142,857 * 3
  = 428,571

Padding nicht erforderlich ist, und wir schließen.

3     ______
- = 0.428571
7

Answer 3

Bearbeiten (Ich gehe Post hier für die Nachwelt aber bitte Sie upvote es nicht mehr.. Es theoretisch nützlich sein kann, aber es ist nicht wirklich praktisch I Beiträge geschrieben haben eine andere Antwort, die viel nützlicher aus praktischer Sicht ist, erfordert keinen Factoring, und erfordert nicht die Verwendung von bignums.)

---

@ Daniel Bruckner hat den richtigen Ansatz, glaube ich. (Mit ein paar zusätzliche Drehungen erforderlich)

Vielleicht gibt es eine einfachere Methode, aber die folgenden wird immer funktionieren:

Lassen Sie sich die Beispiele q verwenden = x / y = 33/57820 und 44/65 zusätzlich zu 33/59, aus Gründen, die klar in Kürze werden können.

Schritt 1: Faktor der Nenner (speziell ausklammern 2 ist und 5s)

Write q = x / y = x / (2 ^{a ₂} 5 ^{a ₅} z). Faktoren von 2 und 5 im Nenner führen nicht wiederholt Dezimalstellen. So ist der verbleibende Faktor z coprime bis 10. In der Tat ist, erfordert der nächste Schritt z Factoring, so dass Sie könnte genauso gut die ganze Sache Faktor.

Berechnen einer ₁₀ = max (a ₂ a ₅ ), der die kleinste Exponent von 10 ist, die ein Vielfaches der Faktoren ist, von 2 und 5 in y.

In unserem Beispiel 57820 = 2 * 2 * 5 * 7 * 7 * 59, so a ₂ = 2, a ₅ = 1, a ₁₀ = 2, z = 7 * 7 * 59 = 2891.

In unserem Beispiel 33/59, ist 59 eine Primzahl und enthält keine Faktoren von 2 oder 5, so einem ₂ = a ₅ = a ₁₀ = 0

In unserem Beispiel 44/65, 65 = 5 * 13 und ein ₂ = 0, a ₅ = a ₁₀ = 1 .

Gerade als Referenz fand ich einen guten Online-Factoring-Rechner hier . (Auch tut totients, die für den nächsten Schritt wichtig ist)

Schritt 2: Verwenden Sie Eulers Theorem oder Carmichael Theorem .

Was wollen wir eine Zahl n, so dass 10 ⁿ - 1 teilbar durch z, oder in anderen Worten, 10 ⁿ ≡ 1 mod z. Eulersche Funktion φ (z) und Carmichael-Funktion λ (z) werden beide geben Sie gültige Werte für n, mit λ (z) gibt Ihnen die kleinere Anzahl und φ (z) ist vielleicht ein wenig leichter zu berechnen. Dies ist nicht zu hart, es bedeutet nur, z Factoring und eine wenig Mathematik zu tun.

φ (2891) = 7 * 6 * 58 = 2436

λ (2891) = LCM (7 * 6, 58) = 1218

Das bedeutet, dass 10 ²⁴³⁶ ≡ 10 ¹²¹⁸ ≡ 1 (mod 2891).

Für die einfachere Fraktion 33/59, φ (59) = λ (59) = 58, so 10 ⁵⁸ ≡ 1 (mod 59).

44/65 = 44 / (5 * 13), φ (13) = λ (13) = 12.

Was? Nun muss die Periode des sich wiederholenden dezimal beide φ teilen (z) und λ (z), so dass sie Sie effektiv obere Schranken für die Periode des sich wiederholenden dezimal geben.

Schritt 3: Mehr Zahlknirschens

Lassen Sie uns verwenden n = λ (z). Wenn wir Q subtrahieren‘= 10 ^{a ₁₀} x / y von Q '' = 10 ^{(a ₁₀ + n)} x / y, erhalten wir:

m = 10 ^{a ₁₀} (10 ⁿ - 1) x / y

, die eine ganze Zahl ist weil 10 ^{a ₁₀} ist ein Vielfaches der Faktoren von 2 und 5 von Y, und 10 ⁿ -1 ist ein Vielfaches der übrigen Faktoren von y.

Was wir hier getan ist zu verschieben, um die ursprüngliche Anzahl q von einem ₁₀ Plätze frei Q erhalten‘, und links q Verschiebung durch ein ₁₀ + n Orte zu bekommen Q ‚‘, die Dezimalstellen wiederholen, aber der Unterschied zwischen ihnen ist eine ganze Zahl wir berechnen können.

Dann können wir umschreiben x / y als M / 10 ^{a ₁₀} / (10 ⁿ - 1).

Nehmen wir das Beispiel q = 44/65 = 44 / (5 * 13)

a ₁₀ = 1 ist, und λ (13) = 12, so Q‘= 10 ¹ q und Q '' = 10 ^{12 + 1} q.

m = Q '' - Q‘= (10 ¹² - 1) * 10 ¹ * (44/65) =153846153846 * 44 = 6769230769224

q = 6769230769224/10 / (10 ¹² - 1).

Die anderen Fraktionen 33/57820 und 33/59 führen zu größeren Fraktionen.

Schritt 4:. Finden Sie das nicht wiederholt und Dezimal-Teile zu wiederholen

Beachten Sie, dass für k zwischen 1 und 9, k / 9 = 0.kkkkkkkkkkkkk ...

Ebenso beachten Sie, dass eine 2-stellige Zahl kl zwischen 1 und 99, k / 99 = 0.klklklklklkl ...

Dieses verallgemeinert: für k-stellige Muster abc ... ij, diese Zahl abc ... ij / (10 ^k -1) = 0.abc ... ijabc ... ijabc ... ij ...

Wenn Sie das Muster folgen, werden Sie sehen, dass das, was wir tun müssen, ist diese (möglicherweise) große Zahl m nehmen wir im vorherigen Schritt erhalten, und schreiben Sie es als m = s * (10 ⁿ -1) + r, wobei 1 ≤ r <10 ⁿ -1.

Dies führt zur endgültigen Antwort:

• s ist der Nicht-Wiederholungsteil
• r ist die Wiederholungsteil (mit Nullen aufgefüllt auf der linken Seite, wenn notwendig, um sicherzustellen, dass es n Ziffern)
• mit einem ₁₀ = 0, wird der Dezimalpunkt zwischen der nichtwiederholendes und ein Teil zu wiederholen; wenn a ₁₀ > 0, dann wird es sich a ₁₀ Stellen nach links von die Verbindung zwischen s und r.

Für 44/65, erhalten wir 6769230769224 = 6 * (10 ¹² -1) + 769230769230

s = 6, r = 769230769230 und 44/65 = ,6769230769230, wo die unterstrichenen hier den wiederholten Teil bezeichnet.

Sie können die Zahlen kleiner machen, indem den kleinsten Wert von n in Schritt 2 zu finden, indem sie mit der Carmichael-Funktion λ (z) beginnen und zu sehen, wenn einer ihrer Faktoren auf Werte von n führen, so dass 10 ⁿ ≡ 1 (mod z).

Update: Für die Neugierigen, scheinen der Python interpeter der einfachste Weg, um mit bignums zu berechnen. (Pow (x, y) berechnet x ^y und //% und ist ganzzahlige Teilung und Rest, respectively.) Hier ist ein Beispiel:

>>> N = pow(10,12)-1
>>> m = N*pow(10,1)*44//65
>>> m
6769230769224
>>> r=m%N
>>> r
769230769230
>>> s=m//N
>>> s
6
>>> 44/65
0.67692307692307696

>>> N = pow(10,58)-1
>>> m=N*33//59
>>> m
5593220338983050847457627118644067796610169491525423728813
>>> r=m%N
>>> r
5593220338983050847457627118644067796610169491525423728813
>>> s=m//N
>>> s
0
>>> 33/59
0.55932203389830504

>>> N = pow(10,1218)-1
>>> m = N*pow(10,2)*33//57820
>>> m
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> r=m%N
>>> r
57073676928398478035281909373919059149083362158422691110342442061570390868211691
45624351435489450017295053614666205465236942234520927014873746108612936700103770
32168799723279142165340712556208924247665167762020062262193012798339674852992044
27533725354548599100657212037357315807679003804911795226565202352127291594603943
27222414389484607402282947077135939121411276374956762365963334486336907644413697
68246281563472846765824974057419578000691802144586648218609477689380837080594949
84434451746800415081286751988931165686613628502248356969906606710480802490487720
51193358699411968177101349014181943964026288481494292632307160152196471809062608
09408509166378415773088896575579384296091317883085437564856451054998270494638533
37945347630577654790729851262538913870632998962296783120027672085783465928744379
10757523348322379799377378069872016603251470079557246627464545140089934278796264
26841923209961950882047734347976478727084053960567277758561051539259771705292286
40608785887236250432376340366655136630923555863023175371843652715323417502594258
04219993081978554133517813905223106191629194050501556554825319958491871324801106
88343133863714977516430300933932895191975095122794880664130058803182289865098581
80560359737115185
>>> s=m//N
>>> s
0
>>> 33/57820
0.00057073676928398479

mit dem überladenen Python % String-Operator verwendbar für Zero-Padding, den vollen Satz von wiederholten Ziffern zu sehen:

>>> "%01218d" % r
'0570736769283984780352819093739190591490833621584226911103424420615703908682116
91456243514354894500172950536146662054652369422345209270148737461086129367001037
70321687997232791421653407125562089242476651677620200622621930127983396748529920
44275337253545485991006572120373573158076790038049117952265652023521272915946039
43272224143894846074022829470771359391214112763749567623659633344863369076444136
97682462815634728467658249740574195780006918021445866482186094776893808370805949
49844344517468004150812867519889311656866136285022483569699066067104808024904877
20511933586994119681771013490141819439640262884814942926323071601521964718090626
08094085091663784157730888965755793842960913178830854375648564510549982704946385
33379453476305776547907298512625389138706329989622967831200276720857834659287443
79107575233483223797993773780698720166032514700795572466274645451400899342787962
64268419232099619508820477343479764787270840539605672777585610515392597717052922
86406087858872362504323763403666551366309235558630231753718436527153234175025942
58042199930819785541335178139052231061916291940505015565548253199584918713248011
06883431338637149775164303009339328951919750951227948806641300588031822898650985
8180560359737115185'

Answer 4

Als allgemeine Technik, rationale Fraktionen haben eine nicht-Wiederholung durch einen Wiederholungsteil gefolgt Teil, wie folgt aus:

nnn.xxxxxxxxrrrrrr

xxxxxxxx ist das nicht wiederholte Teil und rrrrrr ist der Wiederholungsteil.

1. Bestimmen Sie die Länge des nicht wiederholten Teils.
2. Wenn die Ziffer in dem betreffenden Teil nicht wiederholt, dann berechnet sie Division direkt verwenden.
3. Wenn die Ziffer in Frage im Wiederholungsteil ist, berechnen ihre Position innerhalb der Wiederholungsfolge (Sie kennen nun die Längen von allem), und die richtige Ziffer auswählen.

Das obige ist eine grobe Skizze und würde mehr Präzision müssen in einem tatsächlichen Algorithmus implementieren, aber es sollte Ihnen den Einstieg.

Answer 5

AHA! Caffiend: Kommentar zu meiner anderen (längeren) Antwort (speziell „doppelte Reste“) führt mich zu einer sehr einfachen Lösung, die O (n), wobei n = die Summe der Längen der nicht wiederholten + Wiederholung Teile ist, und erfordern nur Integer Mathematik mit Zahlen zwischen 0 und 10 * y wobei y der Nenner ist.

Hier ist eine Javascript-Funktion, die n-te Stelle rechts vom Komma für die rationale Zahl x / y zu erhalten:

function digit(x,y,n) 
{ 
   if (n == 0) 
      return Math.floor(x/y)%10; 
   return digit(10*(x%y),y,n-1);
}

Es ist ziemlich rekursiv als iterative, und ist nicht intelligent genug Zyklen zu erkennen (die 10000. Ziffer von 1/3 ist offensichtlich 3, aber das geht immer weiter, bis es die 10000. Iteration erreicht), aber es funktioniert zumindest bis der Stapel der Speicher ausgeht.

Im Grunde ist dies funktioniert, weil von zwei Tatsachen:

• die n-te Ziffer der x / y der (n-1) -ten Ziffer von 10x / y (Beispiel: der 6. Stelle von 1/7 der 5. Stelle von 10/7 ist die 4. Ziffer von 100/7 etc ist ).
• die n-te Ziffer von x / y ist die n-te Ziffer (x% y) / y (Beispiel: der 5. Stelle von 7.10 ist auch die 5. Stelle von 3/7)

Wir können zwicken dies eine iterative Routine zu sein, und kombinieren es mit Floyds Zyklus -finding Algorithmus (die ich als „rho“ -Methode von einer Martin Gardner Säule gelernt), etwas zu bekommen, das diesen Ansatz Verknüpfungen.

Hier ist eine JavaScript-Funktion, die eine Lösung mit diesem Ansatz berechnet:

function digit(x,y,n,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  while (n > 0)
  {
    n--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      n = n % period;
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }
  }
  var answer=Math.floor(x1/y);
  if (returnstruct)
    return {period: period, digit: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digit='+this.digit;
      }};
  else
    return answer;
}

Und ein Beispiel für die n-te Stelle der 1/700 ausgeführt wird:

js>1/700
0.0014285714285714286
js>n=10000000
10000000
js>rs=digit(1,700,n,true)
period=6,digit=4
js>n%6
4
js>rs=digit(1,700,4,true)
period=0,digit=4

Das Gleiche gilt für 33/59:

js>33/59
0.559322033898305
js>rs=digit(33,59,3,true)
period=0,digit=9
js>rs=digit(33,59,61,true)
period=58,digit=9
js>rs=digit(33,59,61+58,true)
period=58,digit=9

Und 122222/990000 (lange nicht wiederholender Teil):

js>122222/990000
0.12345656565656565
js>digit(122222,990000,5,true)
period=0,digit=5
js>digit(122222,990000,7,true)
period=6,digit=5
js>digit(122222,990000,9,true)
period=2,digit=5
js>digit(122222,990000,9999,true)
period=2,digit=5
js>digit(122222,990000,10000,true)
period=2,digit=6

Hier ist eine weitere Funktion, die eine Strecke von Ziffern findet:

// find digits n1 through n2 of x/y
function digits(x,y,n1,n2,returnstruct)
{
  function kernel(x,y) { return 10*(x%y); }

  var period = 0;
  var x1 = x;
  var x2 = x;
  var i = 0;
  var answer='';
  while (n2 >= 0)
  {
    // time to print out digits?
    if (n1 <= 0) 
      answer = answer + Math.floor(x1/y);

    n1--,n2--;
    i++;
    x1 = kernel(x1,y); // iterate once
    x2 = kernel(x2,y);
    x2 = kernel(x2,y); // iterate twice  

    // have both 1x and 2x iterations reached the same state?
    if (x1 == x2)
    {
      period = i;
      if (n1 > period)
      {
        var jumpahead = n1 - (n1 % period);
        n1 -= jumpahead, n2 -= jumpahead;
      }
      i = 0; 
      // start again in case the nonrepeating part gave us a
      // multiple of the period rather than the period itself
    }    
  }
  if (returnstruct)
    return {period: period, digits: answer, 
      toString: function() 
      { 
        return 'period='+this.period+',digits='+this.digits;
      }};
  else
    return answer;
}

ich die Ergebnisse für Ihre Antwort enthalten haben (vorausgesetzt, dass # 's Javascript tat nicht Überlauf):

js>digit(1,7,1,7,true)
period=6,digits=1428571
js>digit(1,7,601,607,true)
period=6,digits=1428571
js>1/7
0.14285714285714285
js>digit(2124679,214748367,214748300,214748400,true)
period=1759780,digits=20513882650385881630475914166090026658968726872786883636698387559799232373208220950057329190307649696
js>digit(122222,990000,100,110,true)
period=2,digits=65656565656

Answer 6

Ad-hoc-Ich habe keine gute Idee. Vielleicht fortgesetzt Fraktionen helfen können. Ich werde ein wenig darüber nachdenken ...

UPDATE

Aus Fermats kleinen Satz und weil 39 ist prim folgendes gilt. (= zeigt Kongruenz)

10^39 = 10 (39)

Da 10 coprime bis 39.

10^(39 - 1) = 1 (39)

10^38 - 1 = 0 (39)

[to be continued tomorow]

Ich war gestaffelten zu erkennen, dass 39 keine Primzahl ist ... ^^ Ich werde aktualisieren und die Antwort in den nächsten Tagen und präsentieren die ganze Idee. Vielen Dank für die Feststellung, dass 39 keine Primzahl ist.

Die kurze Antwort für a/b mit a < b und einer Periodenlänge p angenommen ...

• berechnen k = (10^p - 1) / b und stellen Sie sicher, dass es eine ganze Zahl, sonst a/b hat nicht einen Zeitraum von p
• berechnen c = k * a
• konvertiert c seinen dezimal represenation und linken Pad mit Nullen auf eine Gesamtlänge von p
• die i-te Stelle nach dem Komma ist das (i mod p) -ten Stelle der paded Dezimaldarstellung (i = 0 die erste Stelle nach dem Komma ist - wir sind Entwickler)

Beispiel

a = 3
b = 7
p = 6

k = (10^6 - 1) / 7
  = 142,857

c = 142,857 * 3
  = 428,571

Padding nicht erforderlich ist, und wir schließen.

3     ______
- = 0.428571
7