22
$\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.

Improve this question
$\endgroup$
3
  • 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$ Commented Aug 29, 2016 at 4:34
  • 1
    $\begingroup$ @mgamer great point. Intelligence wins over brute force. $\endgroup$ Commented Aug 29, 2016 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$ Commented Aug 29, 2016 at 4:48

4 Answers 4

Reset to default
26
$\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]]
Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ That's the way to do it. +1 $\endgroup$ Commented Aug 29, 2016 at 8:03
  • 2
    $\begingroup$ @Mr.Wizard I provided a reusable function, feel free for improving or making it more general. $\endgroup$ Commented Aug 29, 2016 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$ Commented Aug 29, 2016 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$ Commented Aug 29, 2016 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$ Commented Aug 29, 2016 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}
Improve this answer
$\endgroup$
0
9
$\begingroup$

Use RealDigits

RealDigits[7/101, 10, 5566][[1]][[5565]]
Improve this answer
$\endgroup$
1
  • 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$ Commented Aug 29, 2016 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

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.