cp's OEIS Frontend

A342468 Number of multiples of n up to n^2 containing the substring n in base 10.

%I A342468 #45 May 09 2021 10:12:53
%S A342468 1,1,1,1,3,2,1,2,1,2,2,2,2,2,2,2,2,2,2,5,2,2,2,2,8,2,2,3,2,4,2,3,2,2,
%T A342468 3,3,2,2,2,10,2,3,2,3,4,2,2,4,2,28,2,4,3,3,4,5,2,3,4,14,2,3,3,5,5,3,3,
%U A342468 4,4,8,2,5,2,3,21,5,7,3,3,19,2,4,2,6,6,3
%N A342468 Number of multiples of n up to n^2 containing the substring n in base 10.
%C A342468 Since the definition includes n, a(n) >= 1.
%C A342468 Called "Self-Replicating Numbers": "An n-order self-replicating number appears as a substring in exactly n multiples of itself up to its square, including itself" (Zaelin Goodman's Code Golf post).
%C A342468 There are exactly six 1st-order numbers (1, 2, 3, 4, 7, and 9).
%C A342468 Any number n always has an order a(n) >= log_10(n) (when n < 10, floor(log_10(n))=0). This is because there will always be at least one multiple where n is a substring (n itself), as well as any multiples of 10*n (n followed by any number of zeros).
%C A342468 Due to the above, for all integers x >= 1, the series of x-order self-replicating numbers is finite; a(n)=x for the last time at n=10^x-1.
%C A342468 For example, consider a(9)=1. It is the last possible order 1 because the only multiples where 9 is a substring are multiples of 10 (90, 900, ...), which are all > 9^2.
%H A342468 Yi-Hsuan Hsu, <a href="/A342468/b342468.txt">Table of n, a(n) for n = 1..1000</a>
%H A342468 Zaelin Goodman, <a href="https://codegolf.stackexchange.com/questions/220611/self-replicating-numbers">Self-Replicating Numbers</a>
%e A342468 a(5) = 3 because (5, 15, 25) contain 5 as a substring.
%e A342468 a(20) = 5 because (20, 120, 200, 220, 320) contain 20 as a substring.
%t A342468 Table[Function[{d}, Count[n Range[n], _?(SequenceCount[IntegerDigits[#], d] > 0 &)]]@ IntegerDigits[n], {n, 86}] (* _Michael De Vlieger_, Mar 13 2021 *)
%o A342468 (Python)
%o A342468 def a(n):
%o A342468     k = 0
%o A342468     for i in range(1,n+1):
%o A342468         if str(n) in str(i*n):
%o A342468             k += 1
%o A342468     return k
%o A342468 (PARI) a(n) = sum(k=1, n, #strsplit(Str(k*n), Str(n))>1); \\ _Michel Marcus_, Mar 14 2021
%Y A342468 Cf. A018834.
%K A342468 nonn,base
%O A342468 1,5
%A A342468 _Yi-Hsuan Hsu_, Mar 13 2021