3
$\begingroup$

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

Any number in $S$ occurs multiple times. The first occurence of 3 is in position 3 of the series, 2nd occurence is in position 17.

How do I find the position of 3 in 100th occurence? Is there a pattern?

  • 0
    The answers, *of course*, depend on the infinite sequence. Unless you provide details about it, this is not a real question.2010-10-14
  • 0
    My guess is this is motivation: http://projecteuler.net/index.php?section=problems&id=3052010-10-14
  • 0
    Moron - You are right.2010-10-14
  • 0
    @Milli Zeal: As you agreed with Moron's comment, I've edited the question to ask what I think you meant to ask. Feel free to change it back if it's not what you intended.2010-10-14
  • 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
    A little correction: There are _ten_ 3's in the interval [31,40] (because 33 contains two).2010-10-14
  • 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
    The Euler problems are scaled to make brute force not be nearly fast enough. That said, brute force for a ways is a good way to check your algorithm (which you presumably create after thinking about the other answers.2010-10-15
  • 1
    @Ross: well, they should rescale the problems! That line of code evaluates in a lot less than a second.2010-10-15
  • 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