1,1

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.

(Other) ; ; this is in mzscheme (define (count-matches re str start-pos) (let ((m (regexp-match-positions re str start-pos))) (if m (+ 1 (count-matches re str (+ (caar m) 1))) 0))) (define (matches-n-in-zero-to-k fn n) (do ((sum-so-far 1) (k (+ n 1)) (re (regexp (format "~a" n)))) ((fn sum-so-far k) k) (when (equal? 0 (modulo k 1000000)) ; ; this is just a progress indicator (display (format "~a ~a ~a\n" n k sum-so-far))) (set! k (+ k 1)) (set! sum-so-far (+ sum-so-far (count-matches re (format "~a" k) 0))))) (define (s f n) (display (matches-n-in-zero-to-k 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.

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: A126558 A014778 A094799 this_sequence A164321 A106777 A094800

Adjacent sequences: A163497 A163498 A163499 this_sequence A163501 A163502 A163503

more,nonn,uned

Gregory Marton (gremio(AT)acm.org), Jul 29 2009, Aug 12 2009

Added terms 5--9 Gregory Marton (gremio(AT)acm.org), Aug 12 2009