Получение определенной цифры от расширения отношения в любой основе (энная цифра x/y)

АГА! caffiend: ваш комментарий к моему другому (более длинному) ответу (в частности, «повторяющиеся остатки») приводит меня к очень простому решению, которое является O (n), где n = сумма длин неповторяющихся + повторяющихся частей, и требует только целое число математика с числами от 0 до 10 * y, где y - знаменатель.

Вот функция Javascript, позволяющая получить n-ю цифру справа от десятичной точки для рационального числа x / y:

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

Это рекурсивное, а не итеративное и не достаточно умен, чтобы обнаруживать циклы (10000-ая цифра 1/3, очевидно, равна 3, но это продолжается до тех пор, пока не достигнет 10000-й итерации), но работает, по крайней мере, до тех пор, пока стеку не хватит памяти.

В основном это работает из-за двух фактов:

• n-я цифра x / y - это (n-1) -я цифра 10x / y (пример: 6-ая цифра 1/7 - это 5-ая цифра 10/7 - это 4-ая цифра 100/7 и т. д.)
• n-ая цифра x / y - это n-ая цифра (x% y) / y (пример : 5-ая цифра 10/7 также является 5-ой цифрой 3/7)

Мы можем настроить это как итеративную процедуру и объединить ее с алгоритмом нахождения цикла Флойда (который я выучил как метод "RHO" из колонки Мартина Гарднера), чтобы получить что-то, что сокращает этот подход.

Вот функция javascript, которая вычисляет решение с помощью этого подхода:

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

И пример выполнения n-й цифры 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

То же самое для 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

И 122222/990000 (long неповторяющаяся часть):

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

Вот еще одна функция, которая находит отрезок цифр:

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

Я включил результаты для вашего ответа (предполагая, что Javascript # не переполнен):

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

As a general technique, rational fractions have a non-repeating part followed by a repeating part, like this:

nnn.xxxxxxxxrrrrrr

xxxxxxxx is the nonrepeating part and rrrrrr is the repeating part.

1. Determine the length of the nonrepeating part.
2. If the digit in question is in the nonrepeating part, then calculate it directly using division.
3. If the digit in question is in the repeating part, calculate its position within the repeating sequence (you now know the lengths of everything), and pick out the correct digit.

The above is a rough outline and would need more precision to implement in an actual algorithm, but it should get you started.

Ad hoc У меня нет хорошей идеи. Может быть, продолжение фракций может помочь. Я собираюсь немного подумать об этом ...

ОБНОВЛЕНИЕ

Из маленькой теоремы Ферма и поскольку 39 является простым, справедливо следующее. ( = указывает на конгруэнтность)

10^39 = 10 (39)

Поскольку 10 взаимно просто с 39.

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

10^38 - 1 = 0 (39)

[to be continued tomorow]

Я должен был многоуровнево признать, что 39 не простое число ... ^^ Я собираюсь обновить и ответ в следующие дни и представить всю идею. Спасибо, что отметили, что 39 не является простым.

Краткий ответ для a / b с a < b и предполагаемая длина периода p ...

• вычисляют k = (10 ^ p - 1) / b и проверяют, что это целое число, иначе a / b не имеет периода p
• вычислить c = k * a
• преобразовать c в его десятичное представление и заполнить его нулями до общей длины p
• i-я цифра после десятичной запятой является (i mod p) -ой цифрой переданного десятичного представления (i = 0 - первая цифра после запятой - мы являются разработчиками)

Пример

a = 3
b = 7
p = 6

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

c = 142,857 * 3
  = 428,571

Заполнение не требуется, и мы заключаем.

3     ______
- = 0.428571
7

редактировать: (Я оставляю пост здесь для потомков. Но , пожалуйста больше не высказывайте это: это может быть теоретически полезно, но не очень практично Я опубликовал еще один ответ, который намного более полезен с практической точки зрения, не требует какого-либо факторинга и не требует использования bignums.)

@ Даниэль Брукнер, я думаю, имеет правильный подход. (требуется несколько дополнительных поворотов)

Возможно, есть более простой метод, но всегда будет работать следующий:

Давайте использовать примеры q = x / y = 33/57820 и 44/65 в дополнение к 33/59 по причинам, которые могут стать понятны в ближайшее время.

Шаг 1: Выделить знаменатель (особенно вычесть 2 и 5)

Напишите q = x / y = x / (2 ^{a ₂} 5 ^{а ₅} г). Факторы 2 и 5 в знаменателе не приводят к повторным десятичным знакам. Таким образом, оставшийся коэффициент z взаимно прост с 10. Фактически, следующий шаг требует факторизации z, так что вы также можете все это учитывать.

Рассчитайте ₁₀ = max (a ₂ , ₅ ), который является наименьшим показателем 10, кратным коэффициентам 2 и 5 в y.

В нашем примере 57820 = 2 * 2 * 5 * 7 * 7 * 59, поэтому a ₂ = 2, a ₅ = 1, a ₁₀ = 2, z = 7 * 7 * 59 = 2891.

В нашем примере 33/59 59 является простым и не содержит множителей 2 или 5, поэтому a ₂ = a ₅ = a ₁₀ = 0

В нашем примере 44/65, 65 = 5 * 13 и a ₂ = 0, a ₅ = a ₁₀ = 1.

Просто для справки я нашел хороший онлайн-калькулятор факторинга здесь . (даже делает totients, что важно для следующего шага)

Шаг 2: Используйте теорему Эйлера или теорему Кармайкла .

Нам нужно число n такое, что 10 ⁿ - 1 делится на z или, другими словами, 10 ⁿ mod 1 mod z. Функция Эйлера φ (z) и функция Кармайкла λ (z) будут давать вам действительные значения для n, причем λ (z) даст вам меньшее число, а φ (z), возможно, будет немного легче вычислить. Это не так уж сложно, это просто означает, что нужно учесть z и немного подсчитать.

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

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

Это означает, что 10 ²⁴³⁶ [10 ¹²¹⁸ ≡ 1 (мод. 2891).

Для более простой фракции 33/59, φ (59) = λ (59 ) = 58, поэтому 10 ⁵⁸ ≡ 1 (мод 59).

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

И что? Ну, период повторяющейся десятичной дроби должен делить и φ (z), и λ (z), чтобы они эффективно давали верхние границы для периода повторяющейся десятичной дроби.

Шаг 3: Увеличение числа операций

Давайте использовать n = λ (z). Если вычесть Q '= 10 ^{a ₁₀} x / y из Q' '= 10 ^{(a ₁₀ + n)} x / y, мы получить:

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

, что является целым числом , поскольку 10 ^{a ₁₀} кратно коэффициентам 2 и 5 из y, а 10 ⁿ -1 - кратно оставшимся коэффициентам y.

Что мы здесь сделали сдвинуть влево исходное число q на _{10 мест} , чтобы получить Q ', 0, десятичная точка находится между неповторяющаяся и повторяющаяся часть; если a ₁₀ > 0, то оно находится a ₁₀ мест слева от соединение между s и r.

Для 44/65 мы получаем 6769230769224 = 6 * (10 ¹² -1) + 769230769230

s = 6, r = 769230769230 и 44/65 = 0.6769230769230, где подчеркивание здесь обозначает повторяющуюся часть.

Вы можете уменьшить числа, найдя наименьшее значение n на шаге 2, начав с функции Кармайкла λ (z) и посмотрев, приводит ли какой-либо из ее факторов к значения n такие, что 10 ⁿ ≡ 1 (mod z).

update: Для любопытных интерпретатор Python представляется наиболее простым способом вычисления с помощью bignums. (pow (x, y) вычисляет x ^y , а // и% - целочисленное деление и остаток соответственно.) Вот пример:

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

с перегруженной строкой Python % оператор используется для заполнения нулями, чтобы увидеть полный набор повторяющихся цифр:

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