

A163500


a(n) is the smallest number x > 1 such that 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 the times the digit 1 appears in the decimal representations of the numbers from 0 to x. So, for example, f(11) is 4. For what number > 1 does f(x) = x? The answer to that question is 199981, the first term of this sequence. The sequence is the natural extension of this property. a(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 a(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 numbers 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



PROG

(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



KEYWORD

more,nonn,base


AUTHOR



EXTENSIONS



STATUS

approved



