A342468 - OEIS

A342468

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

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 "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).

There are exactly six 1st-order 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 x-order self-replicating numbers is finite; a(n)=x for the last time at n=10^x-1.

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

Yi-Hsuan Hsu, Table of n, a(n) for n = 1..1000

Zaelin Goodman, Self-Replicating 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: A175191 A328928 A370560 * A324534 A248505 A254629