19
$\begingroup$

I want to find the 5566th digit after the decimal point of 7/101. I input the following code into Mathematica 11:

Mod[IntegerPart[7/101*10^5566], 10]

The output is 6, which is the correct answer. Is there a better way to find the answer? Thank you very much in advance.

$\endgroup$
  • 8
    $\begingroup$ The best way to find this digit is in my opinion to calculate it. Since 7/101 ist periodic and so every digit in position n for which mod(n,4)=2 is 6. And mod(5566,4)=2. $\endgroup$ – mgamer Aug 29 '16 at 4:34
  • 1
    $\begingroup$ @mgamer great point. Intelligence wins over brute force. $\endgroup$ – Mr.Wizard Aug 29 '16 at 4:37
  • 2
    $\begingroup$ @Mr.Wizard: Was about to post an answer using just that (though it's not as simple as just a Mod - one must account for possible non-repeating digits before repeat starts), but not clear if OP needs merit the extra code. It will be orders of magnitude faster when going out millions+ digits, but for less, probably no real advantage over your answer... $\endgroup$ – ciao Aug 29 '16 at 4:48
24
$\begingroup$

Fast algorithm

n = 5566
IntegerPart[10 Mod[7 PowerMod[10, n - 1, 101], 101]/101]

A brute force approach (see also these posts on stackoverflow :) ) may be fine for the current problem, but what if n is a huge number? The only possibility apart from guessing the periodic sequence of numbers as mgamer suggested would be to use modular arithmetics. Let me explain my answer. In contrast to the original post we put the number of interest not in the last digit of the integer part, but in the first digit of the fractional part. Conveniently, the fractional part can be computed as a reminder, or for higher efficiency by PowerMod.

Let us compare the timing of the two methods:

n = 556612345;
Mod[IntegerPart[7 10^n/101], 10] // Timing
(*{10.447660, 3}*)
IntegerPart[10 Mod[7 PowerMod[10, n - 1, 101], 101]/101] // Timing
(*{0.000016, 3}*)

The time difference is obvious!

Explanation

Let us consider another example, we compute the n=6 digit of the 7/121 fraction.

n = 6
N[7/121, 30]

0.0578512396694214876033057851240.

In the original post the sought digit is the last digit of the integer part:

N[7 10^n/121, 20]

57851.239669421487603

whereas in my solution it is the first digit in the fractional part

N[Mod[7*10^(n - 1), 121]/121, 20]

0.12396694214876033058 .

It is further used that Mod[a 10^b,c]=Mod[a PowerMod[10,b,c],c].

Reusable function

As requested in the comments, a reusable function can be provided:

Clear[nthDigitFraction];
nthDigitFraction[numerator_Integer, denominator_Integer, n_Integer, 
   base_Integer: 10] /; n > 0 && base > 0 && denominator != 0 := 
 Module[{a = Abs[numerator], b = Abs[denominator]}, 
  IntegerPart[base Mod[a PowerMod[base, n - 1, b], b]/b]]
$\endgroup$
  • 2
    $\begingroup$ That's the way to do it. +1 $\endgroup$ – ciao Aug 29 '16 at 8:03
  • 2
    $\begingroup$ @Mr.Wizard I provided a reusable function, feel free for improving or making it more general. $\endgroup$ – yarchik Aug 29 '16 at 9:09
  • 1
    $\begingroup$ @yarchik if you looked at my code and read its introduction I DO NOT use brute force. In this case the recurring cycle is length 4 so determining digit is almost trivial. I applaud your method. Please note my function is general but not tweeted and used modular arithmetic. $\endgroup$ – ubpdqn Aug 29 '16 at 9:46
  • 1
    $\begingroup$ @ubpdqn Thank you, I modified my post accordingly. However, if you try your method on larger numbers the computational time grows rather fast. For instance I could not have computed dec[7, 101345, 5566]with your method. $\endgroup$ – yarchik Aug 29 '16 at 10:17
  • 2
    $\begingroup$ @yarchik yes and that is why I voted for your answer. It is very efficient and clean and was a nice lesson for me. The achilles heal of my approach was the need (not to process all the digits) but determing the cylce. :) $\endgroup$ – ubpdqn Aug 29 '16 at 10:19
10
$\begingroup$

An alternative formulation of RealDigits that I prefer:

RealDigits[7/101, 10, 1, -5566][[1, 1]]

(* 6 *)

This yields better performance which becomes important when looking for deeper digits:

d = 6245268;

RealDigits[7/101, 10, 1, -d][[1, 1]]  // AbsoluteTiming
RealDigits[7/101, 10, d - 1][[1, -1]] // AbsoluteTiming
{0.0501477, 3}

{1.06702, 3}

Recommended reading:


For comparison to other methods now posted RealDigits can compute the repeating decimal itself:

RealDigits[7/101]
{{{6, 9, 3, 0}}, -1}

How to programmatically work with this output was the subject of a different Question, though I cannot find it at the moment. The possible combinations of repeating and nonrepeating digits as well as the offset makes a truly elegant yet robust solution difficult (at least to me) but in the easiest case, which this happens to be:

d = 5566;

RealDigits[7/101] /.
  {{c_List}, o_} :>
    c[[ Mod[d + o, Length @ c, 1] ]]

(* 6 *)

This is of course quite fast:

d = 556612345;

RealDigits[7/101] /.
  {{c_List}, o_} :> c[[ Mod[d + o, Length@c, 1] ]] // RepeatedTiming
{0.00001243, 0}
$\endgroup$
9
$\begingroup$

Use RealDigits

RealDigits[7/101, 10, 5566][[1]][[5565]]
$\endgroup$
  • 1
    $\begingroup$ FWIW this could also be written RealDigits[7/101, 10, 5566 - 1][[1, -1]]. +1 of course, but see the performance caveat in my answer. $\endgroup$ – Mr.Wizard Aug 29 '16 at 4:08
5
$\begingroup$

Correction

I thank yarchik for his answer and his test of my code identified an error (as well as my code being extremely inefficient for long cycle length):

For this particular example, the recurring patter is of length 4.

So,

fun[n_, d_] := 
 Module[{lst = 
    NestWhileList[QuotientRemainder[10 #[[2]], d] &, 
     QuotientRemainder[n, d], UnsameQ, All], p}, 
  p = Position[lst, lst[[-1]]][[1, 1]];
  {lst[[1 ;; p - 1, 1]], lst[[p ;; -2, 1]]}]
dec[n_, d_, p_] := Module[{a, b},
  {a, b} = fun[n, d];
  b[[Mod[p-Length@a+1, Length@b, 1]]]]

where

  • fun just separates cycling and non-cycling.
  • dec determines value of at position p by working out where in cycle p is

So,

dec[7, 101, 5566]
dec[7, 101, 6245268]

yields 6 and 3 respectively.

As a reality check (not proof):

{#, RealDigits[7/101, 10, 1, -#][[1, 1]], dec[7, 101, #]} & /@ 
  RandomInteger[{10000, 1000000}, 20] // TableForm

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.