A392989 Number of character comparisons needed by naive string search to identify the first occurrence of string n in the infinite Champernowne word 123456789101112... (A033307).

1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 2, 22, 25, 28, 31, 34, 37, 40, 33, 17, 39, 3, 46, 49, 52, 55, 58, 61, 54, 19, 40, 63, 4, 70, 73, 76, 79, 82, 75, 21, 42, 63, 87, 5, 94, 97, 100, 103, 96, 23, 44, 65, 86, 111, 6, 118, 121, 124, 117, 25, 46, 67, 88, 109, 135, 7

Offset

1,2

Comments

Naive string search simply tries the pattern (n here) at each position of the text (1234... here) in turn until a match is found (i.e., without taking account of any special properties of the pattern or text).

Links

Sean A. Irvine, Table of n, a(n) for n = 1..1000

Example

In the following examples x:y means compare pattern character x with text character y.
a(1)=1 because 1:1 (success).
a(2)=2 because 2:1 (fail), then 2:2 (success).
a(10)=12 because 1:1 (match), 0:2 (fail), then 1:2 (fail), ..., 1:9 (fail), then 1:1 (match), 1:0 (success).
a(12)=2 because 1:1 (match) and 2:2 (success).

Prog

(Python)
from itertools import count
def champ(): yield from (d for i in count(1) for d in str(i))
def a(n):
    target, matches, match_idx, cstr, c = str(n), 0, 0, "", 0
    for d in champ():
        cstr, c  =  cstr + d, c + 1
        if target[matches] == cstr[match_idx]:
            matches, match_idx = matches + 1, match_idx + 1
        else:
            matches, match_idx = 0, match_idx - matches + 1
        if matches == len(target): return c
print([a(n) for n in range(1, 68)]) # Michael S. Branicky, Jan 30 2026

Crossrefs

Cf. A031297, A390503, A393101.

Sequence in context: A280594 A280593 A322511 * A171827 A322002 A107743

Adjacent sequences: A392986 A392987 A392988 * A392990 A392991 A392992

Keyword

nonn,base

Author

Sean A. Irvine, Jan 29 2026

Status

approved