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.
a(10) <= 10^92 + 10^91 - 190. - Giovanni Resta, Aug 13 2019
PROG
(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.
CROSSREFS
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