Self-Replicating Numbers

Question

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 code-golf, 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

Answer 1

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)

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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!

Answer 8

Python 2, 72 bytes

def f(n,i=1):
 if sum(`i`in`i*~k`for 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

Answer 9

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.

Answer 10

PowerShell, 77 bytes

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

Try it online!

Answer 11

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.

Try it online or verify for the first n=[0,20] inputs all output-values below 1000.

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)

Answer 12

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)

Answer 13

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

Answer 14

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

Answer 15

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[0])
  i+=1
 return l

Try it online!

Answer 16

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