The multiples are missing

Question

Given a number \$n\$, you are to compute the sequence of positive numbers where for each number \$a\$, the \$n\$-times multiple \$n\cdot a\$ is missing.

Example

We always start with the sequence of all positive numbers: $$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15, \dots$$

For \$n=2\$, going left-to-right, we first encounter \$1\$ and remove its double, \$2\$: $$\require{cancel}\underline{1},\!\cancel{2}\!,3,4,5,6,7,8,9,10,11,12,13,14,15, \dots$$

Next is in line is thus number \$3\$, so we remove \$6\$: $$1,\!\cancel{2}\!,\underline{3},4,5,\!\cancel{6}\!,7,8,9,10,11,12,13,14,15, \dots$$ Continuing, we remove the \$8\$ because of the \$4\$, then the \$10\$ because of the \$5\$, but not the \$12\$ (because the \$6\$ has already been removed), then the \$14\$ and so on: $$1,\!\cancel{2}\!,3,4,5,\!\cancel{6}\!,\underline{7},\!\cancel{8}\!,9,\!\cancel{10}\!,11,12,13,\!\cancel{14}\!,15, \dots$$

Likewise, for \$n=3\$, we get the following sequence by removing the triple of each number we encounter: $$1,2,\!\cancel{3}\!,4,5,\!\cancel{6}\!,7,8,9,10,11,\!\cancel{12}\!,13,14,\!\cancel{15}\!, \dots$$

Task

Given a number \$n>1\$ as input, compute the respective sequence as described above. The default rules for sequence challenges apply, meaning you can either choose to

• take no further input and output the sequence indefinitely, or
• take an index \$i\$ as additional input and output (zero or one indexed)
  • the element at this index, or
  • all elements of the sequence up to this index.

This is code-golf, so the shortest answer in bytes in each language wins.

Testcases

n=2:  [1,3,4,5,7,9,11,12,13,15,16,17,19,20,21,23,25,27,28,29,31,33,35,36,37,39,41,43,44,45,47,48,49,51,52,53,55,57,59,60,61,63,64,65,67,68,69,71,73,75,76,77,79,80,81,83,84,85,87,89,91,92,93,95,97,99,100,101,103,105,107,108,109,111,112,113,115,116,117,119,121,123,124,125,127,129,131,132,133,135,137,139,140,141,143,144,145,147,148,149]
n=3:  [1,2,4,5,7,8,9,10,11,13,14,16,17,18,19,20,22,23,25,26,28,29,31,32,34,35,36,37,38,40,41,43,44,45,46,47,49,50,52,53,55,56,58,59,61,62,63,64,65,67,68,70,71,72,73,74,76,77,79,80,81,82,83,85,86,88,89,90,91,92,94,95,97,98,99,100,101,103,104,106,107,109,110,112,113,115,116,117,118,119,121,122,124,125,126,127,128,130,131,133]
n=4:  [1,2,3,5,6,7,9,10,11,13,14,15,16,17,18,19,21,22,23,25,26,27,29,30,31,32,33,34,35,37,38,39,41,42,43,45,46,47,48,49,50,51,53,54,55,57,58,59,61,62,63,65,66,67,69,70,71,73,74,75,77,78,79,80,81,82,83,85,86,87,89,90,91,93,94,95,96,97,98,99,101,102,103,105,106,107,109,110,111,112,113,114,115,117,118,119,121,122,123,125]
n=5:  [1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,25,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49,50,51,52,53,54,56,57,58,59,61,62,63,64,66,67,68,69,71,72,73,74,75,76,77,78,79,81,82,83,84,86,87,88,89,91,92,93,94,96,97,98,99,100,101,102,103,104,106,107,108,109,111,112,113,114,116,117,118,119]
n=6:  [1,2,3,4,5,7,8,9,10,11,13,14,15,16,17,19,20,21,22,23,25,26,27,28,29,31,32,33,34,35,36,37,38,39,40,41,43,44,45,46,47,49,50,51,52,53,55,56,57,58,59,61,62,63,64,65,67,68,69,70,71,72,73,74,75,76,77,79,80,81,82,83,85,86,87,88,89,91,92,93,94,95,97,98,99,100,101,103,104,105,106,107,108,109,110,111,112,113,115,116]
n=17: [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,103,104,105,106]

---

^{For n=2, the sequence is A003159, for n=3 A007417, and A171948 for n=4 when dropping the zero.}

Answer 1

Haskell, 49 48 bytes

n%a=not$mod a n<1&&n%div a n
f n=filter(n%)[1..]

Try it online!

n%a checks if there's an even amount of base-n zeros at the end of a. Laikoni saved a byte.

Answer 2

Jelly, 7 6 bytes

1ọḂ¬ɗ#

Try it online!

A full program that takes two arguments: n is the first and the second is the number of terms to return, starting from the first.

Thanks to @JonathanAllan for saving a byte!

Explanation

1ọḂ¬ɗ#
1   ɗ# | Starting with 1, find the number of valid sequence members indicated by the second argument by testing each positive integer in turn with the following:
 ọ     | - Find out how many times the integer can be divided by the first argument
  Ḃ    | - Mod 2
   ¬   | - Not

Answer 3

JavaScript (V8), 41 bytes

Outputs the sequence indefinitely.

n=>{for(k=o=[];;)o[++k]||print(o[k*n]=k)}

Try it online!

Commented

n => {           // n = input
  for(           // infinite loop:
    k =          //   k = counter, initially zero'ish
    o = [];;     //   o[] = array to store excluded integers
  )              //
    o[++k]       //   increment k and test o[k]
    ||           //   do nothing if o[k] is truthy, otherwise:
      print(     //
        o[k * n] //     set o[k * n] to something truthy
        = k      //     and print k
      )          //
}                //

Answer 4

Haskell, 35 34 bytes

f[1..]
f(x:r)n=x:f[y|y<-r,y/=n*x]n

Attempt This Online!

Call with, e.g., f[1..] 17 for \$n=17\$. Contructs the sequence as infinite list by a recursive approach. We start with the infite list [1..] = [1,2,3,4,5,...]. In every recursive call, we take the first element x from the list, add it to our output list and remove the number n*x from the remaining list r with a list comprehension before the next recursive call.

Thanks to xnor for -1 byte

Answer 5

05AB1E, 10 9 bytes

∞ʒIвγθ0¢È

-1 byte thanks to @CommandMaster.

Outputs the infinite sequence.

Try it online or verify the first 100 values of all test cases.

Explanation:"

The numbers that get removed are the ones with an odd amount of trailing 0s in their base-\$n\$ representation. For \$n=2\$ this is A036554 and for \$n=3\$ this is A145204.

∞         # Push an infinite positive list: [1,2,3,...]
 ʒ        # Filter it by:
  Iв      #  Convert the current number to base-input as list
    γ     #  Group equal adjacent values together
     θ    #  Pop and keep the last group
      0¢  #  Pop and count the amount of 0s in this last group
        È #  Check if this count is even (so the odd ones are removed after the filter)

Answer 6

><> (Fish), 29 24 bytes

^{Hover over any symbol to see what it does}

Try it If the above doesn't display correctly:

i}l2g?!v>
l::oanl/\p2*-2

><> (Fish), 22 bytes

Works on every integer except 7 so not technically valid

^{Hover over any symbol to see what it does}

Try it

Answer 7

Ruby, 39 bytes

->n,*r{1.step{|x|r&[x]==[]&&r<<p(x)*n}}

Try it online!

Answer 8

Vyxal, 5 bytes

⁰Ǒ₂)ȯ

Try it Online!

Ports jelly. Tbh I don't know why this works.

Answer 9

R, 46 bytes

\(n)while(F<-F+1)if(all(T-F/n))T=c(T,print(F))

Attempt This Online!

Prints the infinite sequence of missing-multiples-of-encountered-n.

Answer 10

Nibbles, 8.5 bytes

|,~%,/`=`@@*@$$@~

Attempt This Online!

|,~%,/`=`@@*@$$@~
|                 filter
 ,~                each k from 1 to ∞
           *@$      k * n
        `@@         convert to base n
      `=      $     group into chunks of equal digits
     /         @    last group
    ,               length
   %            ~   modulo 2

Somehow still better than 05AB1E…

Answer 11

Haskell, 52 bytes

f m i n|i`elem`m=f m(i+1)n|1>0=i:f(n*i:m)(i+1)n
f[]1

Attempt This Online!

Explanation

A somewhat "ugly" solution using the definition of the sequence rather than observations about multiplicity of factors.

f m i n

Helper function f takes: m, a list of multiples to be excluded; i, the current number under consideration; and n, the multiplier.

|i`elem`m=

If i is in the list m:

f m(i+1)n

Recursively call f, incrementing i and leaving m the same. (Don't add i to the returned list.)

|1>0=

Otherwise:

i:f(n*i:m)(i+1)n

Prepend i to a recursive call in which n*i is prepended to m (and i is incremented, as before).

f[]1

Our submission function starts with m empty and i equal to 1, and takes n as an argument.

Answer 12

Fortran (GFortran), 115 bytes

program x
real::r(999)=1
n=2
i=100
do j=1,999
if(r(j)/=0)then
print*,j
r(j*n)=0
i=i-1
if(i<1)stop
end if
end do
end

Try it online!

n is the input number, i is the number of result values to be created.

How it works: create an array r of floating point numbers (because the word real is shorter than the word integer) of an adequate size (2 * i is enough) and set all numbers to 1. Iterate the array with the loop variable j. Because of its name, j is implicitly an integer in Fortran, while an a as in the challenge description would be a floating point number, which would not be allowed as a loop variable. If the value at the index j of r is not 0, the value is printed, the value at j*n is set to 0, and the count of pending numbers is decreased by one. If the count of pending numbers is 0, the program ends.

Answer 13

Charcoal, 26 bytes

ＮθＮηＷ‹Ｌυη⊞υ⁺⊕↨υ⁰№×υθ⊕↨υ⁰Ｉυ

Try it online! Link is to verbose version of code. Outputs the first i values. Explanation:

ＮθＮη

Input n and i.

Ｗ‹Ｌυη

Repeat until i values have been found.

⊞υ⁺⊕↨υ⁰№×υθ⊕↨υ⁰

Push the next integer, but add 2 if the next integer appears in n vectorised multiplied by the list.

Ｉυ

Output the found values.

Would be 18 bytes to output the members of the sequence between 1 and i inclusive:

ＮθＦＮＦ¬№×υθ⊕ι⊞υ⊕ιＩυ

Try it online!

Alternative 18-byte version that outputs the members of the sequence between 1 and i inclusive in constant memory:

ＮθＩΦ⊕Ｎ¬﹪⌕⮌Ｘ⁰↨ιθ⁰¦²

Try it online! Link is to verbose version of code. Would be 17 bytes to output the members of the sequence less than i (remove the ⊕).

Answer 14

Perl 5.10 -n, 31 bytes

1while$d{++$k}||say$d{$k*$_}=$k

Try it online!

Translate of @Arnaulds Javascript method above.