18
\$\begingroup\$

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
\$\endgroup\$
7
  • 6
    \$\begingroup\$ The 3rd output option is rather unusual. Can't we just take \$n\$ and print the corresponding terms forever? \$\endgroup\$
    – Arnauld
    Mar 12 '21 at 15:51
  • 3
    \$\begingroup\$ Fwiw, I think the standard option that Arnauld suggested makes much more sense. \$\endgroup\$
    – Jonah
    Mar 12 '21 at 17:30
  • 1
    \$\begingroup\$ @Arnauld your comment along with some answers misinterpreting the third point swayed my opinion. Thanks for helping to improve the challenge for all! \$\endgroup\$ Mar 12 '21 at 20:10
  • 1
    \$\begingroup\$ @Wasif Sorry, poor choice of wording. It should have read "I think it'd be cool if.." \$\endgroup\$ Mar 13 '21 at 14:24
  • 1
    \$\begingroup\$ oeis.org/A342468 \$\endgroup\$
    – bigyihsuan
    Nov 10 '21 at 18:29

16 Answers 16

7
\$\begingroup\$

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Mar 12 '21 at 14:58
  • 3
    \$\begingroup\$ @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 \$\endgroup\$ Mar 12 '21 at 14:59
  • 1
    \$\begingroup\$ It just wouldn't be CodeGolf if they didn't put us all to shame on a regular basis :) \$\endgroup\$ Mar 12 '21 at 15:00
  • \$\begingroup\$ @ChartZBelatedly I think you're overestimating my golfing abilities, haha. I did outgolf you by a single byte with my 05AB1E answer, though. ;) \$\endgroup\$ Mar 30 '21 at 15:05
7
\$\begingroup\$

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
\$\endgroup\$
0
6
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 55 bytes... I think... \$\endgroup\$ Mar 12 '21 at 21:04
  • \$\begingroup\$ @DominicvanEssen Thanks! \$\endgroup\$ Mar 12 '21 at 23:01
5
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Brachylog seems very well-suited for sequence questions like this. \$\endgroup\$
    – Jonah
    Mar 12 '21 at 18:41
  • 1
    \$\begingroup\$ @Jonah Indeed, practically every predicate is a generator. Sometimes with just one output value. :-) \$\endgroup\$
    – xash
    Mar 12 '21 at 18:45
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ Mar 13 '21 at 7:27
4
\$\begingroup\$

Charcoal, 19 bytes

IΦXχ⌈θ№θLΦι№I×ι⊕λIι

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
  X                 Raised to power
     θ              Input integers
    ⌈               Maximum
 Φ                  Filter implicit range where
       θ            Input integers
      №             Contains
        L           Length of
          ι         Current value
         Φ          Filter implicit range where
              ι     Outer value
             ×      Multiplied by
                λ   Inner index
               ⊕    Incremented
            I       Cast to string
           №        Contains
                  ι Outer value
                 I  Cast to string
I                   Cast to string
                    Implicitly print
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ @Arnauld cool, updated. \$\endgroup\$ Mar 12 '21 at 20:25
  • \$\begingroup\$ 75 bytes \$\endgroup\$ Mar 12 '21 at 23:33
  • \$\begingroup\$ And it's 72 bytes in Python 2. \$\endgroup\$ Mar 12 '21 at 23:57
  • \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Mar 13 '21 at 11:46
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

PowerShell, 77 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard
    Mar 17 '21 at 13:33
  • 1
    \$\begingroup\$ Also am could be one character shorter. \$\endgroup\$ Mar 18 '21 at 2:28
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.