4
$\begingroup$

Let's call $S$ the infinite string that is made by concatenating the consecutive positive integers written down in base $10$. Thus, $$S = 12345678910111213141516171819202122232425\ldots$$

Any number in $S$ occurs multiple times. The first occurrence of $3$ is in the third position of the series, the second occurrence is in the seventeenth position, and so on.

How do I find the position of the hundredth occurrence of $3$? Is there a pattern?

  • 0
    Of course there is a pattern. The question is: how complicated is the pattern?2010-10-14

3 Answers 3

2

You can solve this by thinking of some lists:

How many 3's is there in 1-10? -- 1

How many 3's is there in 11-20? -- 1

How many 3's is there in 21-30? -- 2

How many 3's is there in 31-40? -- 10

How many 3's is there in 41-50? -- 1

...

How many 3's is there in 91-100? -- 1

Now, how many 3's is there in 1-100?

How many 3's is there in 101-200?

How many 3's is there in 201-300?

How many 3's is there in 301-400? (obviously sufficient)

Then, when you know the what number comes at the 100:th place you just need count the place - for example by "counting lists" again.

  • 0
    @Hans Lundmark: Absolutely :D2010-10-14
1

You could try some careful counting. If mine is careful enough, I make the 100th occurence of 3 to be in the 889th position.

It's the first digit of 333.

I counted like this:

In 1 to 99 there are 10 threes in the unit's digit and 10 in the ten's digit, so that's makes 20, and hence there are $3 \times 20=60$ in 1 to 299.

Now in 300 to 329 there are 30 in the hundred's digit and 3 in the unit's digit, so that's another 33, making 93 so far. Now just look at 330331332333 and you will see that the 100th three is the first digit of 333 which, by some straightforward calculations, is in the 889th position.

1

Brute force:

[mariano@godot ~]$ ghci GHCi, version 6.12.1: http://www.haskell.org/ghc/  :? for help   Prelude> [i | (d,i) <- concat (map show [1..]) `zip` [1..], d == '3'] !! 100 - 1 889 Prelude> 
  • 0
    But how long will it take for the $1594323^{rd}$ appearance of the string 1594323? Their point is to force you to understand the problem and find more efficient ways to solve it. Derek's and AD's answers give some good ideas in that direction. I have solved many of them, but not that one.2010-10-15