A392989 - OEIS

%I #12 Feb 01 2026 21:46:51

%S 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,

%T 55,58,61,54,19,40,63,4,70,73,76,79,82,75,21,42,63,87,5,94,97,100,103,

%U 96,23,44,65,86,111,6,118,121,124,117,25,46,67,88,109,135,7

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

%C 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).

%H Sean A. Irvine, <a href="/A392989/b392989.txt">Table of n, a(n) for n = 1..1000</a>

%e In the following examples x:y means compare pattern character x with text character y.

%e a(1)=1 because 1:1 (success).

%e a(2)=2 because 2:1 (fail), then 2:2 (success).

%e a(10)=12 because 1:1 (match), 0:2 (fail), then 1:2 (fail), ..., 1:9 (fail), then 1:1 (match), 1:0 (success).

%e a(12)=2 because 1:1 (match) and 2:2 (success).

%o (Python)

%o from itertools import count

%o def champ(): yield from (d for i in count(1) for d in str(i))

%o def a(n):

%o     target, matches, match_idx, cstr, c = str(n), 0, 0, "", 0

%o     for d in champ():

%o         cstr, c  =  cstr + d, c + 1

%o         if target[matches] == cstr[match_idx]:

%o             matches, match_idx = matches + 1, match_idx + 1

%o         else:

%o             matches, match_idx = 0, match_idx - matches + 1

%o         if matches == len(target): return c

%o print([a(n) for n in range(1, 68)]) # _Michael S. Branicky_, Jan 30 2026

%Y Cf. A031297, A390503, A393101.

%K nonn,base

%O 1,2

%A _Sean A. Irvine_, Jan 29 2026