|
%I #45 May 09 2021 10:12:53
%S 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 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 4,4,8,2,5,2,3,21,5,7,3,3,19,2,4,2,6,6,3
%N Number of multiples of n up to n^2 containing the substring n in base 10.
%C Since the definition includes n, a(n) >= 1.
%C 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 There are exactly six 1st-order numbers (1, 2, 3, 4, 7, and 9).
%C 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 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 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 Yi-Hsuan Hsu, <a href="/A342468/b342468.txt">Table of n, a(n) for n = 1..1000</a>
%H Zaelin Goodman, <a href="https://codegolf.stackexchange.com/questions/220611/self-replicating-numbers">Self-Replicating Numbers</a>
%e a(5) = 3 because (5, 15, 25) contain 5 as a substring.
%e a(20) = 5 because (20, 120, 200, 220, 320) contain 20 as a substring.
%t Table[Function[{d}, Count[n Range[n], _?(SequenceCount[IntegerDigits[#], d] > 0 &)]]@ IntegerDigits[n], {n, 86}] (* _Michael De Vlieger_, Mar 13 2021 *)
%o (Python)
%o def a(n):
%o k = 0
%o for i in range(1,n+1):
%o if str(n) in str(i*n):
%o k += 1
%o return k
%o (PARI) a(n) = sum(k=1, n, #strsplit(Str(k*n), Str(n))>1); \\ _Michel Marcus_, Mar 14 2021
%Y Cf. A018834.
%K nonn,base
%O 1,5
%A _Yi-Hsuan Hsu_, Mar 13 2021
|
