A393101 - OEIS

%I #10 Feb 01 2026 21:45:57

%S 1,2,3,4,5,6,7,8,9,12,13,2,22,25,28,31,34,37,40,33,17,35,3,46,49,52,

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

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

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

%C The comparisons counted are those between the pattern and text, initial comparisons of the pattern with itself are not counted.

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

%H Michael S. Branicky, <a href="/A393101/a393101.py.txt">Python program for OEIS A393101</a>

%H Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a393/A393101.java">Java program</a> (github)

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm">Knuth-Morris-Pratt algorithm</a>

%o (Python) # see linked program

%Y Cf. A033307, A022543, A392989, A390503, A387487.

%K nonn,base

%O 1,2

%A _Sean A. Irvine_, Feb 01 2026