36
$\begingroup$

The decimal representation of $3^{100000}$ has $47713$ digits. What is the $23857^{th}$ digit - i.e. the one in the $10^{23856}$'s place?

There are lots of questions on this site asking for the last digit of various large exponents, which are well handled by modular arithmetic. The last digit of $3^{100000}$ is $1$ by such methods. There are some fewer number of questions asking for the first digit of a number, which can be handled by considering the fractional part of the base ten logarithm of the number. The first digit of the number is $1$.

Either method can be modified to give the first few or last few digits, but they don't generalize well beyond that, and there's no obvious way to combine the methods.

Is there a method to find arbitrary digits of small integers raised to large ones? Is there any reason to suspect that computing a digit in the middle is, in terms of computational complexity, a more difficult problem than computing digits on the edge?

$\endgroup$
  • 1
    $\begingroup$ In a multiplication, leading digits of the result come only from leading digits of operands, and trailing digits come only from trailing digits, whereas middle digits come from all digits. That's why it's much more difficult. $\endgroup$ – Xoff Feb 14 '15 at 6:03
  • $\begingroup$ In fact, even leading digits can be a little bit hard to compute, due to carry ! For example, computing leading digits of $3^{91021769653165636733949}$ and $3^{576864203935018747860310233639537915841216535}$ is much more complex than computing trailing digits... $\endgroup$ – Xoff Feb 14 '15 at 6:30
  • 12
    $\begingroup$ It's a $2$, obviously. $\endgroup$ – Lucian Feb 14 '15 at 6:31
  • $\begingroup$ @Xoff - it's not difficult at all (the leading digits one). For your really big one, you're going to calculate $576864203935018747860310233639537915841216535\log_{10} 3$, find the fractional part, and compare it with $\log_{10} n$ for $n=1$ through $9$. $\endgroup$ – Glen O Feb 16 '15 at 7:06
  • 2
    $\begingroup$ I've posted a question inspired by yours here. You need to compute the middle digit of $9^{50000}$. For powers of $9$, the first digit has a period of $2$ as the exponent grows. The second digit has a period of $10$, the third - $50$, the fourth - $250$, and in general - the $m$th digit has a period of $2\cdot5^m$ as the exponent grows. This makes it quite hard to predict the middle digit of such large number, unless you find an efficient way to calculate the values within the period of that digit. $\endgroup$ – barak manos Feb 17 '15 at 17:27
5
+50
$\begingroup$

In contrast with other programming languages from its time, Pascal (the programming language) also supports a set type, implemented as a bit pattern. The bit patterns associated with the Pascal set type are $256$ bits wide, but this limitation is not essential and can been replaced with other (larger) values eventually. See Wikipedia for a reference. A rather detailed description of the set type implementation can be found as well . So we have the following practice:

  • a bit pattern in a computer is a set type
We also know that

  • a bit pattern in a computer is a natural number type
Indeed, everybody knows that a natural number can be represented as a binary i.e. a bit pattern. The word "type" has been employed here in order to avoid confusion with other (i.e the standard mathematical) "set" and "number" definitions.
More precisely: the hereditarily finite sets are in one-to-one correspondence with the natural numbers. And the latter fact is independent of computers.
Examples. $$ \begin{array}{l} 0 = 000 = \{\} \\ 1 = 001 = \{0\} = \{\{\}\} \\ 2 = 010 = \{1\} = \{\{\{\}\}\} \\ 3 = 011 = \{0\; 1\} = \{\{\}\{\{\}\}\} \\ 4 = 100 = \{2\} = \{\{\{\{\}\}\}\} \\ 5 = 101 = \{0\; 2\} = \{\{\}\{\{\{\}\}\}\} \\ 6 = 110 = \{1\; 2\} = \{\{\{\}\}\{\{\{\}\}\}\} \\ 7 = 111 = \{0\; 1\; 2\} = \{\{\}\{\{\}\}\{\{\{\}\}\}\} \\ \cdots \end{array} $$ The above is related to the following reference, by Alexander Abian and Samuel LaMacchia:

If the curly brackets $\{\}$ are replaced by square brackets $\left[\,\right]$ then another important fact is observed:

  • a set type is is a natural number type is a sorted natural numbers array type
If now we devise an equivalent of the elementary number operations with sorted arrays, then we have virtual unlimited precision at our disposal. That this approach indeed works, shall be demonstrated at hand of the OP's question. Here is a link to the complete (Delphi Pascal) program that does the job:

And here is a link to the number $3^{100000}$ itself, which is too large to fit into MSE's margins:

The screen output of the program is the number of digits, the first, the middle and the last digit:
47713
1 2 1
So, indeed, as Lucian says in a comment: it's "obvious" that the digit in the middle is a $\large\, 2$ .

Note.  A power like $\,3^{100000}\,$ sounds quite impressive, but with a smart algorithm, the number of operations is only $\,\ln_2(100000)\approx17$ . For real numbers $\,x\,$ and a natural $\,n\,$ it goes as follows:

function power(x : double; n : integer) : double;
var
  m : integer;
  p, y : double;
begin
  m := n; y := x; p := 1;
  while m > 0 do begin
    if (m and 1) > 0 then p := p * y;
    m := m shr 1; { m := m / 2 }
    y := y * y;
  end;
  power := p;
end;
Wikipedia reference: Efficient computation with integer exponents .

BONUS. In view of the above, the following answer is interesting:

Reference is made to a paper by Kaye and Wong, where on page 499 we read:

It was observed in 1937 by Ackermann [1] that $\mathbb{N}$ with the membership relation defined by

    $n \in m$ iff the $n$th digit in the binary representation of $m$ is $1$
satisfies ZF$-$inf. This interpretation, formalized in ZF with $\omega$ in place of $\mathbb{N}$ yields a bijection between $\omega$ and the collection $V_\omega$ of hereditarily finite sets.

$\endgroup$
  • $\begingroup$ I awarded the bounty to this answer because, though it is not what I was looking for (- alas, with all these fast computers around, I should've chosen a larger exponent!), it is very interesting in and of itself (and quite unexpected). $\endgroup$ – Milo Brandt Feb 23 '15 at 23:19
  • $\begingroup$ @Meelo: Uhm, well, I didn't tell anybody that my implementation with "set-arrays" is terribly slow (: when compared with MAPLE, for example). So I would have lost the contest with your larger exponent, that's for sure :-( $\endgroup$ – Han de Bruijn Feb 24 '15 at 15:10
2
$\begingroup$

I wondered how Lucian could come to the correct result within one hour after the question appeared. So I gave Mathematica a chance. Here is the output:

enter image description here

$\endgroup$
  • $\begingroup$ Right. So it's sufficient (again) to find the right button in a Computer Algebra System. Now I wonder where that button is in MAPLE .. $\endgroup$ – Han de Bruijn Feb 17 '15 at 15:36
  • 7
    $\begingroup$ @HandeBruijn: It's the third button from the left, on the second upper row of the keyboard. ;-$)$ $\endgroup$ – Lucian Feb 19 '15 at 10:39
  • $\begingroup$ @Lucian: Yeah, uhm, any help appreciated ;-) $\endgroup$ – Han de Bruijn Feb 19 '15 at 10:56
  • 2
    $\begingroup$ substring(convert(3^100000, string), 23857); $\endgroup$ – Sary Feb 19 '15 at 17:56
  • $\begingroup$ @Sary: Yes, that works. I'm converted now :-) $\endgroup$ – Han de Bruijn Feb 21 '15 at 16:00
1
$\begingroup$

Aside from special cases where 'tricks' might aid in solving a specific answer, I suspect finding an arbitrary digit or slice of digits roughly reduces to the time complexity of base conversion. For example, if you want to know the middle (and only middle!) digit of a number with an odd number of digits, there may in fact be a special trick through modular arithmetic to get the answer quickly. I don't know of one, maybe Lucian does.

However, if you want to know an arbitrary digit of $N=b^k$, I believe the answer to your question is similar to knowing the complexity of base conversion from base b to base 10.

Rough argument

Storage of $N=b^k$ in base 10 will require $ \lceil \log_{10}(N)\rceil=\lceil k*\log_{10}(b)\rceil$ digits.

Computing N by repeated squaring will require $\lceil \log_2(k) \rceil$ multiplication operations each of which involves updating the $\lceil k*\log_{10}(b) \rceil$ elements of the representation.

Therefore, it appears you're bounded by $ O(k*log_2(k))$ operations as $k$ increases.

This differs by a factor of $k$ from modular arithmetic tricks which will generally get you the last digits in $O(log_2(k))$ time (i.e., if you use the same repeated squaring approach).

So where is the difference?
The 'trick' with first/last digits is to restrict the representation to a fixed constant. Although $k$ may become larger in $b^k$, the representation of your answer does not have to grow, so first/last digits can be computed efficiently.

So I think the real underlying question is:

Can arbitrary digits of $N=b^k$ be determined using a representation of fixed width (fixed number of bits)?

$\endgroup$
-1
$\begingroup$

Using a computer program (that just calculates the whole number and extract the required digit), I found that the answer is 7.

This is the program (which is in Haskell):

digits :: Integer -> [Int]
digits = map (read . (:[])) . show

main = print ((digits (3^100000)) !! 23857)
$\endgroup$
  • $\begingroup$ Yes, because Haskell seems to use array base zero instead of one. So what you have found actually is digit number $23858$ (array base $1$) which is indeed a $7$. $\endgroup$ – Han de Bruijn Feb 23 '15 at 15:06

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.