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

Offset: 1

Author

Yi-Hsuan Hsu, Mar 13 2021

Keywords

• nonn
• base

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.

Examples

			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.
		

Links

• Yi-Hsuan Hsu, Table of n, a(n) for n = 1..1000
• Zaelin Goodman, Self-Replicating Numbers

Crossrefs

Cf. A018834.

Programs

Mathematica

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

PARI

a(n) = sum(k=1, n, #strsplit(Str(k*n), Str(n))>1); \\ Michel Marcus, Mar 14 2021

Python

def a(n):
    k = 0
    for i in range(1,n+1):
        if str(n) in str(i*n):
            k += 1
    return k