# Self-Replicating Numbers

## Background

For the purpose of this challenge, all numbers and their string representations are assumed to be in decimal (base 10). I tried to find proper terminology for this challenge, but I do not think there is any, so I made it up.

A self-replicating number is a number that appears as a substring in any of its multiples up to and including its square, excluding itself. An $$\n\$$-order self-replicating number appears as a substring in exactly $$\n\$$ multiples of itself up to its square, including itself. All numbers are at least 1st-order self-replicating numbers, because they appear as a substring in their first multiple (1 times the number).

For example: 5 is a 3rd-order self-replicating number, because it appears 3 times in the multiples of itself up to its square: 5, 10, 15, 20, 25. On the other hand, 4 is a 1st-order self-replicating number, because it appears only once: 4, 8, 12, 16.

There are only 6 1st-order replicators, because numbers will always have a self-replicator order $$\\geq\lfloor\log_{10}(x)\rfloor+1\$$, where $$\x\$$ is the number, as multiples of the number and any power of ten are guaranteed to have the number as a substring. Because of this property of self-replicating numbers, the series of $$\n\$$-order self-replicating numbers cannot ever be an infinite series. The last possible $$\n\$$-order self-replicating number is $$\10^n-1\$$.

## The Challenge

Your task is to write a program which takes two integers, $$\m\$$ and $$\n\$$, and does one of the following:

• return the first $$\m\$$ $$\n\$$-order self-replicating numbers $$\or\$$
• return the $$\m^{th}\$$ $$\n\$$-order self-replicating number (0 or 1-indexed, your choice) $$\or\$$
• output the series of numbers that are either $$\m\$$-order or $$\n\$$-order self-replicating numbers. You may treat this series as if it were infinite; in other words, your code is not required to halt - it'd be very cool if it did, though. $$\or\$$
• By popular demand, and because the previous option was a source of valid misinterpretation, you may now instead take a single integer, $$\n\$$, and output the series of $$\n\$$-order self-replicating numbers. As with the last option, you may treat the series as if it were infinite.

## Rules

• You are allowed undefined behavior for values of $$\m\leq0\$$ or $$\n\leq0\$$.
• Your code is not required to halt if the next number in the sequence does not exist. For example: if you chose either of the first two output options and your code receives $$\m=7, n=1\$$ as input, a 7th 1st-order self-replicating number will never be found because no 1st-order self-replicating numbers higher than 9 exist.
• Standard loopholes forbidden.
• This is , shortest program in bytes for each language wins.

## Test Cases

$$\m\$$ $$\n\$$ Output
5 0 undefined
6 1 1,2,3,4,7,9
7 1 1,2,3,4,7,9 $$\or\$$ undefined
20 2 6,8,10,11,12,13,14,15,16,17,18,19,21,22,23,24,26,27,29,31
30 4 30,45,48,52,55,59,68,69,82,94,110,115,122,128,130,136,137,139,144,145,152,168,170,171,176,177,184,187,190,192
10 38 650,3520,3680,3920,6050,6350,6840,7640,7880,7960
3 101 7125,8900,9920
1 2778 5000
• The 3rd output option is rather unusual. Can't we just take $n$ and print the corresponding terms forever? Mar 12, 2021 at 15:51
• Fwiw, I think the standard option that Arnauld suggested makes much more sense. Mar 12, 2021 at 17:30
• @Arnauld your comment along with some answers misinterpreting the third point swayed my opinion. Thanks for helping to improve the challenge for all! Mar 12, 2021 at 20:10
• @Wasif Sorry, poor choice of wording. It should have read "I think it'd be cool if.." Mar 13, 2021 at 14:24
• oeis.org/A342468 Nov 10, 2021 at 18:29

# Jelly, 11 bytes

1ẇⱮ×R$SƊ=¥#  Try it online! Takes $$\n\$$ then $$\m\$$ on the command line and outputs the first $$\m\$$ $$\n\$$-order self-replicating numbers ## How it works 1ẇⱮ×R$SƊ=¥# - Main link. Takes n on the left
¥  - Group the previous 2 links into a dyad f(k, n):
Ɗ    -   Group the previous 3 links into a monad on k:
$- Group the previous 2 links into a monad on k: R - Yield the range [1, 2, ..., k] × - Multiply each element by k Ɱ - For each element i in [k, 2k, ..., k²]: ẇ - Is k a substring of i? S - Sum; Count the 1s = - Does this equal n? 1 # - Count up k = 1, 2, 3, ... until m such k return true under f(k, n)  • Nice! I really feared I'd made a challenge that these golfing languages would have a 2-byter for - to get 11 whole bytes out of Jelly, I'm overjoyed. Mar 12, 2021 at 14:58 • @ZaelinGoodman Just wait, I'm sure Jonathan Allan or Kevin Cruijssen will produce a magic 7 or 8 byte version in Jelly or 05AB1E :P Mar 12, 2021 at 14:59 • It just wouldn't be CodeGolf if they didn't put us all to shame on a regular basis :) Mar 12, 2021 at 15:00 • @ChartZBelatedly I think you're overestimating my golfing abilities, haha. I did outgolf you by a single byte with my 05AB1E answer, though. ;) Mar 30, 2021 at 15:05 # JavaScript (V8), 76 67 66 bytes Saved 1 byte thanks to @user81655 A function expecting $$\n\$$ and printing the $$\n\$$-order self-replicating numbers forever. n=>{for(m=0;k=++m;s||print(m))for(s=n;k;)s-=!!(k--*m+'').match(m)}  Try it online! ### Commented n => { // n = input for( // infinite outer loop: m = 0; // start with m = 0 k = ++m; // before each iteration, increment m and copy it in k // (always truthy, so we never exit the loop) s || print(m) // after each iteration, print m if s = 0 ) // for( // inner loop: s = n; // start with s = n k; // stop when k = 0 ) // s -= // decrement s if ... !!(k-- * m + '') // ... k * m coerced to a string .match(m) // contains m (decrement k afterwards) } // end  # R, 58 55 bytes -3 bytes thanks to Dominic van Essen n=scan();repeat if(sum(grepl(F,(F=F+1)*1:F))==n)show(F)  Try it online! Prints all the $$\n\$$-order self-replicating numbers. • 55 bytes... I think... Mar 12, 2021 at 21:04 • @DominicvanEssen Thanks! Mar 12, 2021 at 23:01 # J, 47 bytes (>:@][echo@]^:(e.~1#.1*@#.]E.&":"0]+]*i.))^:_&1  Try it online! Third option for output. TIO has +2 since I changed infinity _ to 651 to make it clear that it works. # Brachylog, 17 bytes Generates the sequence for a given $$\n\$$. ≤≜.{≥.;?×s?∧≜}ᶜ?∧  Try it online! ≤≜.{≥.;?×s?∧≜}ᶜ?∧ ≤≜ a number k greater-equal than n . is the output { }ᶜ count the outputs of the predicate, ? unify with n ∧ return the output ≥ a number less-equal than k . is the output ;?× multiplied by k s? has k as substring ∧≜ return the output  • Brachylog seems very well-suited for sequence questions like this. Mar 12, 2021 at 18:41 • @Jonah Indeed, practically every predicate is a generator. Sometimes with just one output value. :-) – xash Mar 12, 2021 at 18:45 • Doesn't seem like that second ≜ should be necessary, or even necessarily do anything--so it's really weird how it breaks if you remove it Mar 13, 2021 at 7:27 # Charcoal, 19 bytes ＩΦＸχ⌈θ№θＬΦι№Ｉ×ι⊕λＩι  Try it online! Link is to verbose version of code. Takes a pair (actually any list) of integers [n, m] as input and outputs all self-replicating numbers of those order(s), but somewhat slow so avoid using it at all really. Explanation:  χ Predefined variable 10 Ｘ Raised to power θ Input integers ⌈ Maximum Φ Filter implicit range where θ Input integers № Contains Ｌ Length of ι Current value Φ Filter implicit range where ι Outer value × Multiplied by λ Inner index ⊕ Incremented Ｉ Cast to string № Contains ι Outer value Ｉ Cast to string Ｉ Cast to string Implicitly print  # Wolfram Language (Mathematica), 81 bytes outputs the series of n-order self-replicating numbers forever Do[Tr@Boole@StringContainsQ[(T=ToString)/@Array[m#&,m],T@m]==#&&Print@m,{m,∞}]&  Try it online! # Python 2, 72 bytes def f(n,i=1): if sum(iini*~kfor k in range(i))==n:print i f(n,i+1)  Try it online! Trivial answer that loops through the numbers in order and checks if they are self-replicating. -8 bytes thanks to dingledooper • @Arnauld cool, updated. Mar 12, 2021 at 20:25 • 75 bytes Mar 12, 2021 at 23:33 • And it's 72 bytes in Python 2. Mar 12, 2021 at 23:57 • I think this works for 67 bytes. It counts how many times the number appears as a string in the list representation, which in theory could allow a multiple to contain the number twice and be double counted, but I think this can't happen without going above the square of the number. – xnor Mar 13, 2021 at 11:46 # PowerShell, 99 bytes param($n)for($x=1;;++$x){$o=0;for($i=$x;$i-le($x*$x);$i+=$x){$o+=("$i"-match"$x")};if($o-eq$n){$x}}


Try it online!

A script expecting $$\n\$$ and printing the first $$\n\$$-order self-replicating numbers forever.

# PowerShell, 77 bytes

param($m,$n)for(;$n*($m-=$z)){,++$i*($z=(1..$i|?{$i*$_-match$i}).Count-eq$n)}


Try it online!

# 05AB1E, 10 bytes

∞ʒL¤*¬δåOQ


Uses the last option: given an integer $$\n\$$, outputs the infinite (non-halting) sequence of $$\n\$$-order self-replicating numbers.

Explanation:

∞           # Push an infinite list of positive integers: [1,2,3,...]
ʒ          # Filter each integer y by:
L         #  Push a list in the range [1,y]
y*       #  Multiply each by y
δ     #  Map over each value in this list:
y å    #   Check if it contains y as substring
O   #  Sum this list together to get the amount of truthy values
Q  #  And check if this is equal to the (implicit) input-integer n
# (after which the filtered infinite list is output implicitly as result)


# Scala, 67 bytes

n=>Stream.from(1)filter(x=>x.to(x*x,x).count(_+""contains ""+x)==n)


Try it in Scastie! (ignore the deprecation warnings)

# Japt, 18 bytes

Èõ*X è_s øXÃ¥V}jU1


Try it

• we could save a byte by returning nth term 0 indexed just by using iU instead of jU1 but this way is more easy to validate output.
    È ...}jU1 - first n terms
õ*X       - multiples to X^2
è .. ¥V   - number of multiples returning true to _ 'function (Z)'== second input?
_s øXÃ    - convert to string and check if contains X


# APL(Dyalog Unicode), 27 bytes SBCS

{⍸⍵=(1⊥⊢(1∊⍷⍥⍕)¨⊢×⍳)¨⍳10*⍵}


Try it on APLgolf!

A dfn submission which takes $$\n\$$ and prints all self-replicating numbers of order $$\n\$$ and terminates.

Commented:

{⍸⍵=(...)¨⍳10*⍵}   ⍝ dfn which takes n as a right argument and returns all nth-order self-replicating numbers
⍳10*⍵    ⍝ the indices from 1 to 10^n
(...)¨         ⍝ for each number, calculate the order of self-replication
⍵=               ⍝ is this order equal to n?
⍸                 ⍝ the indices of all 1's

(1⊥⊢(1∊⍷⍥⍕)¨⊢×⍳)   ⍝ train that takes a number k as a right argument and returns the order
⊢×⍳    ⍝ k × (1 2 ... k) = (k×1 k×2 ... k×k)
⊢( ... )¨       ⍝ for each value as a right argument and k as a left argument:
1∊⍷           ⍝ is the left argument is a substring of the right after ...
⍥⍕         ⍝ ... both are formatted as a string
1⊥                ⍝ sum all results


# Python 3, 160 154 bytes

def am(m,n):
k=lambda n:[i*n for i in range(1,n+1)if str(n)in str(i*n)];l=[];i=1
while len(l)<m:
q=k(i)
if len(q)==n:l.append(q)
i+=1
return l


Try it online!

• You have a lot of extra whitespace and newlines that can be removed by putting things on the same line using ;, or in the case of the if, just getting rid of the space altogether. Mar 17, 2021 at 13:33
• Also am could be one character shorter. Mar 18, 2021 at 2:28

# Kotlin, 96 bytes

fun f(n:Int)=generateSequence(1){it+1}.filter{x->(x..x*x step x).count{"$it".contains("$x")}==n}


Try it online!

Returns the sequence of all $$\n\$$-order self-replicating numbers