

A163500


Let s(n) be the smallest number x such that the decimal representation of n appears as a substring of the decimal representations of the numbers [0...x] exactly x times.


2




OFFSET

1,1


COMMENTS

This is an extension of a puzzle that a student posed as: Let f(x) be a function that counts how many times the digit 1 appears in the decimal representations of the numbers from 0 to x. So f(11) is 4. For what number > 1 does f(x) = x. The answer to that question is 199981, the first element of this sequence. The sequence is the natural extension of this property. Trivially s(0) doesn't exist, because for any x, [0...x] (inclusive) contains zero, meaning there is at least one matching substring, and this is a monotonically increasing function. It is not clear that s(n) is defined for all n>0, though the related sequence which uses f(x)>x rather than f(x)=x has at least less of a feeling of caprice about it. Multidigit n are clearly at a disadvantage, but I have tried to phrase it, "appears as a substring" so that, for example, 11 appears in 1111 thrice rather than twice.


LINKS

Table of n, a(n) for n=1..9.


PROG

(Other) ;; this is in mzscheme (define (countmatches re str startpos) (let ((m (regexpmatchpositions re str startpos))) (if m (+ 1 (countmatches re str (+ (caar m) 1))) 0))) (define (matchesninzerotok fn n) (do ((sumsofar 1) (k (+ n 1)) (re (regexp (format "~a" n)))) ((fn sumsofar k) k) (when (equal? 0 (modulo k 1000000)) ;; this is just a progress indicator (display (format "~a ~a ~a\n" n k sumsofar))) (set! k (+ k 1)) (set! sumsofar (+ sumsofar (countmatches re (format "~a" k) 0))))) (define (s f n) (display (matchesninzerotok f n))) ;; where f should be one of = or > depending on which sequence you care about. ;; this could be made much more efficient, of course. In particular, the ;; initial sequences up to the first x of m digits have serious regularity.


CROSSREFS

See also A164321 which uses > instead of =. The first nine terms are contained in the sequences 1: A014778, 2: A101639, 3: A101640, 4:A101641, 5: A130427, 6: A130428, 7: A130429, 8: A130430, 9: A130431.
Sequence in context: A216400 A014778 A094799 * A164321 A230019 A106777
Adjacent sequences: A163497 A163498 A163499 * A163501 A163502 A163503


KEYWORD

more,nonn,base


AUTHOR

Gregory Marton, Jul 29 2009, Aug 12 2009


EXTENSIONS

a(5)  a(9) added by Gregory Marton, Aug 12 2009
Donovan Johnson pointed out the 6th term was incorrect, Nov 01 2010


STATUS

approved



