Obtenir un chiffre spécifique à partir d'une extension de ratio dans n'importe quelle base (nième chiffre de x / y)

https://stackoverflow.com/questions/804934

03-07-2019
|

Question

Existe-t-il un algorithme permettant de calculer les chiffres d’un rapport répétitif / décimal sans commencer au début?

Je recherche une solution qui n’utilise pas d’entiers de taille arbitraire, car cela devrait fonctionner dans les cas où le développement décimal peut être arbitrairement long.

Par exemple, 33/59 se développe en une décimale répétée à 58 chiffres. Si je voulais vérifier cela, comment pourrais-je calculer les chiffres à partir de la 58e place?

Édité - avec le ratio 2124679/2147483647, comment obtenir les cent chiffres des 2147484600 à 2147484700e places.

La solution

OK, la 3ème tentative est un charme:)

Je ne peux pas croire que j'ai oublié l'exponentiation modulaire.

Donc, pour voler / résumer de ma 2ème réponse, le nième chiffre de x / y est le 1er chiffre de (10 ^n-1 x mod y) / y = étage (10 * (10 ^n-1 x mod y) / y) mod 10.

La partie qui prend tout le temps est la mod 10 ^n-1, mais nous pouvons le faire avec une exponentiation modulaire rapide (O (log n)). Avec cela en place, il ne vaut pas la peine d'essayer d'utiliser l'algorithme de recherche de cycle.

Cependant, vous devez avoir la possibilité de faire (a * b mod y) où a et b sont des nombres pouvant être aussi grands que y. (Si y nécessite 32 bits, vous devez alors multiplier 32x32 puis modulus% 32 bits à 64 bits, ou vous avez besoin d’un algorithme qui contourne cette limitation. Consultez la liste ci-dessous, car j’ai eu cette limitation avec Javascript. )

Alors, voici une nouvelle 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;
}

(Vous remarquerez que les structures de abmody() et de l’exponentiation modulaire sont identiques; elles reposent toutes les deux sur Multiplication de paysans russes .) Et résultats:

js>digits2(2124679,214748367,214748300,214748400)
20513882650385881630475914166090026658968726872786883636698387559799232373208220950057329190307649696
js>digits2(122222,990000,100,110)
65656565656
js>digits2(1,7,1,7)
1428571
js>digits2(1,7,601,607)
1428571
js>digits2(2124679,2147483647,2147484600,2147484700)
04837181235122113132440537741612893408915444001981729642479554583541841517920532039329657349423345806

Autres conseils

modifier: (Je pars pour la postérité. Mais s'il vous plait , ne passez plus au vote suivant: cela peut être utile en théorie, mais ce n'est pas vraiment pratique. ont posté une autre réponse qui est beaucoup plus utile d’un point de vue pratique, ne nécessite aucun affacturage et ne nécessite pas l’utilisation de bignums.)

@ Daniel Bruckner a la bonne approche, je pense. (avec quelques torsions supplémentaires requises)

Il existe peut-être une méthode plus simple, mais ce qui suit fonctionnera toujours:

Utilisons les exemples q = x / y = 33/57820 et 44/65 en plus de 33/59, pour des raisons qui risquent de devenir claires sous peu.

Étape 1: factorisez le dénominateur (en particulier les 2 et 5)

Ecrire q = x / y = x / (2 ^{a ₂} 5 ^{a ₅} z). Les facteurs 2 et 5 du dénominateur ne causent pas de décimales répétées. Donc, le facteur z restant est égal à 10. En fait, l'étape suivante nécessite la factorisation de z, vous pouvez donc aussi factoriser le tout.

Calculez un ₁₀ = max (un ₂, un ₅) qui est le plus petit exposant de 10 qui soit un multiple des facteurs de 2 et 5 en y.

Dans notre exemple 57820 = 2 * 2 * 5 * 7 * 7 * 59, donc un ₂ = 2, un ₅ = 1, un ₁₀ = 2, z = 7 * 7 * 59 = 2891.

Dans notre exemple 33/59, 59 est un nombre premier et ne contient aucun facteur de 2 ou 5, donc un ₂ = un ₅ = un ₁₀ = 0.

Dans notre exemple 44/65, 65 = 5 * 13 et un ₂ = 0, un ₅ = a ₁₀ = 1 .

Juste pour référence, j'ai trouvé un bon calculateur d'affacturage en ligne ici . (même les totients, ce qui est important pour la prochaine étape)

Étape 2: utilisez le théorème d'Euler ou Théorème de Carmichael .

Ce que nous voulons, c'est un nombre n tel que 10 ⁿ - 1 soit divisible par z ou, en d'autres termes, 10 ⁿ & # 8801; 1 mod z. La fonction d'Euler & # 966; (z) et la fonction de Carmichael & # 955; (z) vous donneront toutes les deux des valeurs valides pour n, avec & # 955; (z) vous donnant le plus petit nombre et # 966; (z) peut-être un peu plus facile à calculer. Ce n’est pas trop difficile, cela signifie simplement de factoriser z et de faire un peu de calcul.

& # 966; (2891) = 7 * 6 * 58 = 2436

& # 955; (2891) = lcm (7 * 6, 58) = 1218

Cela signifie que 10 ²⁴³⁶ & # 8801; 10 ¹²¹⁸ & # 8801; 1 (mod 2891).

Pour la fraction plus simple 33/59, & # 966; (59) = & # 955; (59) = 58, donc 10 ⁵⁸ & # 8801; 1 (mod 59).

Pour 44/65 = 44 / (5 * 13), & # 966; (13) = & # 955; (13) = 12.

Et alors? La période de la décimale répétée doit diviser à la fois & # 966; (z) et & # 955; (z). bornes sur la période du nombre décimal répété.

Étape 3: davantage de calculs

Utilisons n = & # 955; (z). Si nous soustrayons Q '= 10 ^{a ₁₀} x / y de Q' '= 10 ^{(a ₁₀ + n)} x / y, on obtient:

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

qui est un entier car 10 ^{a ₁₀} est un multiple des facteurs de 2 et 5 de y et 10 ⁿ -1 est un multiple des facteurs restants de y.

Ce que nous avons fait ici est de déplacer le nombre d'origine q de gauche de ₁₀ places pour obtenir Q ', et de déplacer q de gauche d'un ₁₀ + n places pour obtenir Q '', qui sont des nombres décimaux répétés, mais la différence entre eux est un entier que nous pouvons calculer.

Ensuite, nous pouvons réécrire x / y sous la forme m / 10 ^{a ₁₀} / (10 ⁿ - 1).

Prenons l'exemple q = 44/65 = 44 / (5 * 13)

a ₁₀ = 1 et & # 955; (13) = 12, donc Q '= 10 ¹ q et Q' '= 10 ^{12 + 1} q.

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

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

Les autres fractions 33/57820 et 33/59 donnent des fractions plus grandes.

Étape 4: recherchez les parties décimales non répétées et répétées.

Notez que pour k compris entre 1 et 9, k / 9 = 0.kkkkkkkkkkkkkk ...

Notez de même qu'un nombre à deux chiffres kl compris entre 1 et 99, k / 99 = 0.klklklklklkl ...

Ceci généralise: pour les modèles à k chiffres abc ... ij, ce nombre abc ... ij / (10 ^k -1) = 0.abc ... ijabc ... ijabc ... ij ...

Si vous suivez le modèle, vous verrez que ce que nous devons faire est de prendre cet entier (potentiellement) énorme que nous avons obtenu à l'étape précédente, et de l'écrire sous la forme m = s * (10 ⁿ -1) + r, où 1 & # 8804; r < 10 ⁿ -1.

Ceci mène à la réponse finale:

s est la partie non répétitive
r est la partie qui se répète (complétée par un zéro à gauche si nécessaire pour s'assurer qu'il s'agit de n chiffres)
avec un ₁₀ = 0, le point décimal est entre le partie non répétée et répétée; si un ₁₀ > 0 alors il se trouve un ₁₀ endroits à gauche de la jonction entre s et r.

Pour 44/65, nous obtenons 6769230769224 = 6 * (10 ¹² -1) + 769230769230

s = 6, r = 769230769230 et 44/65 = 0.6769230769230 où le soulignement désigne ici la partie répétée.

Vous pouvez réduire les nombres en recherchant la plus petite valeur de n à l'étape 2, en commençant par la fonction de Carmichael & # 955; (z) et en recherchant si l'un de ses facteurs conduit à une valeur de n telle que 10 ⁿ & # 8801; 1 (mod z).

mise à jour: pour les plus curieux, l’interpètre Python semble être le moyen le plus simple de calculer avec bignums. (pow (x, y) calcule x ^y, et // et% correspondent respectivement à la division entière et au reste.) Voici un exemple:

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

avec l'opérateur de chaîne Python % surchargé, utilisable pour le remplissage à zéro, pour voir l'ensemble des chiffres répétés:

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

En règle générale, les fractions rationnelles ont une partie non répétitive suivie d'une partie répétée, comme ceci:

nnn.xxxxxxxxrrrrrr

xxxxxxxx est la partie non répétée et rrrrrr la partie répétée.

Déterminez la longueur de la pièce non répétée.
Si le chiffre en question se trouve dans la partie non répétée, calculez-le directement à l'aide de la division.
Si le chiffre en question se trouve dans la partie répétée, calculez sa position dans la séquence répétée (vous connaissez maintenant la longueur de tout) et choisissez le bon chiffre.

Ce qui précède est un schéma approximatif et il faudrait plus de précision pour l'implémenter dans un algorithme réel, mais cela devrait vous aider à démarrer.

AHA! caffiend: votre commentaire à mon autre réponse (plus longue) (plus précisément & "; restes en double &";) me conduit à une solution très simple, qui est O (n) où n = la somme des longueurs de la non répétition + répétition de parties, et ne nécessite que des mathématiques entières avec des nombres compris entre 0 et 10 * y où y est le dénominateur.

Voici une fonction Javascript pour obtenir le nième chiffre à droite du séparateur décimal du nombre rationnel x / y:

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

Il est récursif plutôt qu'itératif et n'est pas assez intelligent pour détecter les cycles (le 10000ème chiffre de 1/3 est évidemment 3, mais il continue jusqu'à ce qu'il atteigne la 10000e itération), mais il fonctionne au moins jusqu'à la pile. manque de mémoire.

En gros, cela fonctionne à cause de deux faits:

le nième chiffre de x / y est le (n-1) ème chiffre de 10x / y (exemple: le 6ème chiffre de 1/7 est le 5ème chiffre de 10/7 est le 4ème chiffre de 100/7 etc. .)
le nième chiffre de x / y est le nième chiffre de (x% y) / y (exemple: le cinquième chiffre de 10/7 est également le cinquième chiffre de 3/7)

Nous pouvons en faire une routine itérative et la combiner avec cycle de Floyd algorithme de repérage (que j’ai appris en tant que méthode & "; rho &" à partir d’une colonne de Martin Gardner) pour obtenir quelque chose qui raccourcit cette approche.

Voici une fonction javascript qui calcule une solution avec cette approche:

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;
}

Et un exemple d'exécution du nième chiffre de 1/700:

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

Même chose pour 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

Et 122222/990000 (partie longue non répétée):

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

Voici une autre fonction qui trouve une longueur de chiffres:

// 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;
}

J'ai inclus les résultats de votre réponse (en supposant que le code Javascript n'a pas été dépassé):

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, je n'ai aucune bonne idée. Peut-être que les fractions continues peuvent aider. Je vais y réfléchir un peu ...

MISE À JOUR

~~Du le petit théorème de Fermat et parce que 39 est primordial, tient comme suit. (= indique la congruence)~~

10^39 = 10 (39)

Parce que 10 est coprime à 39.

10^(39 - 1) = 1 (39) 10^38 - 1 = 0 (39) [to be continued tomorow]

Je devais reconnaître que 39 n’est pas primordial ... ^^ Je vais mettre à jour la réponse dans les prochains jours et présenter l’idée. Merci de noter que 39 n'est pas premier.

La réponse courte pour a/b avec a < b et une longueur de période supposée p ...

calculez k = (10^p - 1) / b et vérifiez qu'il s'agit d'un entier, sinon c = k * a n'a pas de période c
calculer <=>
convertit <=> en sa représentation décimale et le remplit à gauche avec des zéros d’une longueur totale de <=>
le i-ème chiffre après le point décimal est le (i mod p) -ième chiffre de la représentation décimale complétée (i = 0 est le premier chiffre après le point décimal - nous sommes des développeurs)

Exemple

a = 3
b = 7
p = 6

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

c = 142,857 * 3
  = 428,571

Le rembourrage n’est pas obligatoire et nous concluons.

3     ______
- = 0.428571
7

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow