

A342468


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


1



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, 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, 4, 4, 8, 2, 5, 2, 3, 21, 5, 7, 3, 3, 19, 2, 4, 2, 6, 6, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

Since the definition includes n, a(n) >= 1.
Called "SelfReplicating Numbers": "An norder selfreplicating number appears as a substring in exactly n multiples of itself up to its square, including itself" (Zaelin Goodman's Code Golf post).
There are exactly six 1storder numbers (1, 2, 3, 4, 7, and 9).
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).
Due to the above, for all integers x >= 1, the series of xorder selfreplicating numbers is finite; a(n)=x for the last time at n=10^x1.
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.


LINKS

YiHsuan Hsu, Table of n, a(n) for n = 1..1000
Zaelin Goodman, SelfReplicating Numbers


EXAMPLE

a(5) = 3 because (5, 15, 25) contain 5 as a substring.
a(20) = 5 because (20, 120, 200, 220, 320) contain 20 as a substring.


MATHEMATICA

Table[Function[{d}, Count[n Range[n], _?(SequenceCount[IntegerDigits[#], d] > 0 &)]]@ IntegerDigits[n], {n, 86}] (* Michael De Vlieger, Mar 13 2021 *)


PROG

(Python)
def a(n):
k = 0
for i in range(1, n+1):
if str(n) in str(i*n):
k += 1
return k
(PARI) a(n) = sum(k=1, n, #strsplit(Str(k*n), Str(n))>1); \\ Michel Marcus, Mar 14 2021


CROSSREFS

Cf. A018834.
Sequence in context: A156352 A175191 A328928 * A324534 A248505 A254629
Adjacent sequences: A342465 A342466 A342467 * A342469 A342470 A342471


KEYWORD

nonn,base


AUTHOR

YiHsuan Hsu, Mar 13 2021


STATUS

approved



