The Millionth digit.

[mfgoode]

If you write the sequence of numbers one after the other in their natural order without separating them, as though one were writing a single number:
123456789101112131415...

Find what digit occupies a given position, say the millionth ?

I would prefer a non computer solution.

Mally

[VolMike]

A part of problem 40 at http://projecteuler.net/index.php. There are 9*10^(x-1) of x-digital numbers (x>=1).First find n for which sum of length of all numbers f(n) consists of no more then n digits, less and closest to 10^6. f(n)=sum(9*x*10^(x-1),i=1..n)=1/9*(1-10^n+9*n*10^n). For n=5, f(n)=488889 -the closest value less then 10^6. Then find the ammount of 6-digits numbers, which sum of length less and closest to 10^6-f(5)=511111,The number is [511111/6]=85185. Thus, we have that all digits of all numbers in range (1..185184 (cause the 100000 is the first 6-digits number)) are included in our sequence (no more then 10^6 digits). Number of digits of 185185 which lie in sequence is equal 511111-85185*6=1. Thus, the millionth digit of sequence is the first digit of 185185- which equals 1.

[VolMike]

This problem can be solved in common case, but I suppose that symbolic result would be quite huge to be evaluated and posted there.

[bsquared]

Here's a kinda neat way to get the solution using a similar type of sequence:

The millionth digit is given by the
(1000000 - (9 * 54321))%6 th digit of the
(1000000 - (9 * 54321))/6 th 6 digit number (which has already been pointed out to be 185185) or 1.

The trillionth digit is given by the
(1000000000000 - (9 * 10987654321))%11 th digit of the
(1000000000000 - (9 * 10987654321))/11 11 digit number (which is 81919191919) or 1.

In general, the Nth digit of the seqence is given by
this digit: (N - (9 * S(d-1)))%d
of the (N - (9 * S(d-1)))/d 'th d digit number.
Where S(n) is the reverse of the original sequence (i.e. S(5) = 54321), and d is the biggest number such that (9 * S(d-1)) < N.

[bsquared]

Hmmm. I just tried this for N = 1e18 and it didn't work, and I know why. Apparently by "in general" I meant "in general for N < ~1e10"

my reverse sequence is built from the fact that you can count the number of digits in the original sequence like this:
for N = 1e6 there are:
9 numbers with 1 digit
90 numbers with 2 digits
900 with 3, etc

total digits = 9*1 + 90*2 + 900*3 ...
= 9 * (1 + 10*2 + 100*3 ...)
= 9 * (...321)

but after 9 digit numbers this isn't true anymore.

sorry for the confusion.

[VolMike]

One way to get a better algorithm is simplifying 1/9*(1-10^n+9*n*10^n),or find a simpler formula for biggest positive integer n,satisfies 1/9*(1-10^n+9*n*10^n) < = t (t- position number of unknown digit). May be it is possible to calculate short formula for some special values of t=10^s (as in problem 40 at http://projecteuler.net/index.php.).

[mfgoode]

Originally Posted by VolMike

A part of problem 40 at http://projecteuler.net/index.php.

Thus, we have that all digits of all numbers in range (1..185184 (cause the 100000 is the first 6-digits number)) are included in our sequence (no more then 10^6 digits). Number of digits of 185185 which lie in sequence is equal 511111-85185*6=1. Thus, the millionth digit of sequence is the first digit of 185185- which equals 1.

You have it right Volmike.

To make it clearer, dividing by 6 we get the quotient 85,185 and the remainder 1, so the desired digit occupies the first place in the 85,186th. 6- digit number. Since the first 6- digit number is 100,000 the 85,186th is 185,185 whose first digit is 1.

Thanks for the website. The next time I submit a problem I will check it and give something that is not included there!

Mally

[VolMike]

Originally Posted by mfgoode

You have it right Volmike.

To make it clearer, dividing by 6 we get the quotient 85,185 and the remainder 1, so the desired digit occupies the first place in the 85,186th. 6- digit number. Since the first 6- digit number is 100,000 the 85,186th is 185,185 whose first digit is 1.

Thanks for the website. The next time I submit a problem I will check it and give something that is not included there!

Mally

Hm.. It seems that you (and others) post problems not only because you really need the answer, but to "shake up" the forum and make some kind of competition? If so, I start like this forum more and more :)

[mfgoode]

Originally Posted by VolMike

Hm.. It seems that you (and others) post problems not only because you really need the answer, but to "shake up" the forum and make some kind of competition? If so, I start like this forum more and more :)

You are dead right Vol. Speaking for myself yes I do. The aim is to test your knowledge and skill on important parts of Number theory and other topics
by putting it in the form of a puzzle.

You may be interested to know that in presenting a problem for the forum I came across an original theorem. I developed it as no one seemed to have solved it and have presented a paper for publication. I have also claimed that by it I have solved the Beal's conjecture. My paper awaits evaluation as it involves an enormous cash prize.

So much for puzzles. And I may add that many if not all of the great math'cians delighted in puzzles and challenged one another with tantalising ones. Well thats how Number theory developed!

Mally

[VolMike]

Originally Posted by mfgoode

You are dead right Vol. Speaking for myself yes I do. The aim is to test your knowledge and skill on important parts of Number theory and other topics
by putting it in the form of a puzzle.

You may be interested to know that in presenting a problem for the forum I came across an original theorem. I developed it as no one seemed to have solved it and have presented a paper for publication. I have also claimed that by it I have solved the Beal's conjecture. My paper awaits evaluation as it involves an enormous cash prize.

So much for puzzles. And I may add that many if not all of the great math'cians delighted in puzzles and challenged one another with tantalising ones. Well thats how Number theory developed!

Mally

That's great! I hope we'll see your paper in Interrnet.

[mfgoode]

Originally Posted by VolMike

That's great! I hope we'll see your paper in Interrnet.

Thank you VolMike. I will be releasing it on the forum as soon as I have officially recorded it. It is very simple like the Pythagas theorem but true for all real and complex numbers. (I hope!)

Mally