# The multiples are missing

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$$

Given a number $$\n>1\$$ as input, compute the respective sequence as described above. The default rules for 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 , 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.

• Can I output all numbers of to $n$ (instead of up to the n-th number)? Commented Oct 5, 2023 at 9:43
• @CommandMaster I'd rather stick to the default sequence rules, so no, this would not be allowed. Commented Oct 5, 2023 at 10:45
• Is additional white space allowed in answers or just a single whitespace character between each sequence member? Commented Oct 5, 2023 at 12:06
• @NickKennedy I'd say consistent white space is allowed, though something like 1 3 4 5 7 9 ... not. Commented Oct 5, 2023 at 12:56
• I added an n=6 test case, after having almost posted a wrong solution that fails for numbers with more than one distinct prime factor.
– xnor
Commented Oct 5, 2023 at 18:20

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. • 35 bytes by recursive filtering: f[1..];f(x:r)n=x:f(filter(/=n*x)r)n Commented Oct 5, 2023 at 13:04 • @Laikoni That's a completely different answer and I think you should post it. – lynn Commented Oct 5, 2023 at 17:57 • I wanted to rewrite n%a=(mod a n>0)>=n%div a n, but logical >= doesn't short-circuit like &&, so it just hangs. – xnor Commented Oct 5, 2023 at 18:29 # 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  • @JonathanAllan thanks, I’d forgotten how the arguments were handled for # when using a dyadic link or chain Commented Oct 6, 2023 at 15:32 # 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 ) // } //  • Clever putting that assignment in the print call. Commented Oct 5, 2023 at 11:27 # 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 • 34 bytes – xnor Commented Oct 6, 2023 at 20:19 # 05AB1E, 10 9 bytes ∞ʒIвγθ0¢È  -1 byte thanks to @CommandMaster. Outputs the infinite sequence. 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)  • Can't Ãg be ¢ for -1? There's also ∞ʒ>LmyÖOÈ, but I can't find an 8-byte solution Commented Oct 5, 2023 at 9:45 • @CommandMaster Yep, it indeed can.. Not sure why I didn't think of that, thanks. Commented Oct 5, 2023 at 9:49 # ><> (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 # Ruby, 39 bytes ->n,*r{1.step{|x|r&[x]==[]&&r<<p(x)*n}}  Try it online! • r-[x]==r saves a byte. Commented Oct 5, 2023 at 21:13 # Vyxal, 5 bytes ⁰Ǒ₂)ȯ  Try it Online! Ports jelly. Tbh I don't know why this works. • I've roll-backed your latest edit on my answer. The numbers that get removed are odd, so my answer filters and keeps those that are even. :) Commented Oct 5, 2023 at 9:52 • @KevinCruijssen I seem to have bamboozled myself with the meanings of words there. Clearly I shouldn't be golfing when I'm somewhat tired :p Commented Oct 5, 2023 at 9:54 • The only way the sequential process of building the sequence affects itself is by removing some n-multiples, and that only affects it by not removing the n-multiples of those n-multiples, so you're excluding the n-multiples of excluded n-multiples from being excluded. Hence, the largest power of n that divides a number being even is necessary and sufficient for being in the sequence. Commented Oct 5, 2023 at 17:32 # 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. # 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… # Haskell, 52 bytes f m i n|ielemm=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. |ielemm=  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. # 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. • Welcome to Code Golf Stack Exchange, and nice first answer! Commented Oct 8, 2023 at 0:37 • Thank you very much! Commented Oct 8, 2023 at 1:25 • If you’re interested, we also have a chatroom on this site called The Nineteenth Byte which you can join when your account hits 20 reputation points. Its activity varies but there are usually people who can help you learn about the site or just talk to about programming. Commented Oct 8, 2023 at 1:54 # 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 ⊕). # Perl 5.10 -n, 31 bytes 1while$d{++$k}||say$d{$k*$_}=\$k