15
\$\begingroup\$

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

\$\endgroup\$
5
  • \$\begingroup\$ Can I output all numbers of to \$n\$ (instead of up to the n-th number)? \$\endgroup\$ Oct 5, 2023 at 9:43
  • 1
    \$\begingroup\$ @CommandMaster I'd rather stick to the default sequence rules, so no, this would not be allowed. \$\endgroup\$
    – Laikoni
    Oct 5, 2023 at 10:45
  • \$\begingroup\$ Is additional white space allowed in answers or just a single whitespace character between each sequence member? \$\endgroup\$ Oct 5, 2023 at 12:06
  • 1
    \$\begingroup\$ @NickKennedy I'd say consistent white space is allowed, though something like 1 3 4 5 7 9 ... not. \$\endgroup\$
    – Laikoni
    Oct 5, 2023 at 12:56
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Oct 5, 2023 at 18:20

14 Answers 14

6
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 35 bytes by recursive filtering: f[1..];f(x:r)n=x:f(filter(/=n*x)r)n \$\endgroup\$
    – Laikoni
    Oct 5, 2023 at 13:04
  • 2
    \$\begingroup\$ @Laikoni That's a completely different answer and I think you should post it. \$\endgroup\$
    – Lynn
    Oct 5, 2023 at 17:57
  • \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Oct 5, 2023 at 18:29
6
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ @JonathanAllan thanks, I’d forgotten how the arguments were handled for # when using a dyadic link or chain \$\endgroup\$ Oct 6, 2023 at 15:32
5
\$\begingroup\$

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
      )          //
}                //
\$\endgroup\$
1
  • \$\begingroup\$ Clever putting that assignment in the print call. \$\endgroup\$
    – noodle man
    Oct 5, 2023 at 11:27
5
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 34 bytes \$\endgroup\$
    – xnor
    Oct 6, 2023 at 20:19
3
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can't Ãg be ¢ for -1? There's also ∞ʒ>LmyÖOÈ, but I can't find an 8-byte solution \$\endgroup\$ Oct 5, 2023 at 9:45
  • \$\begingroup\$ @CommandMaster Yep, it indeed can.. Not sure why I didn't think of that, thanks. \$\endgroup\$ Oct 5, 2023 at 9:49
3
\$\begingroup\$

><> (Fish), 29 24 bytes

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

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

enter image description here

><> (Fish), 22 bytes

Works on every integer except 7 so not technically valid

irl3g?!\
:l2-*3p\lnao:

Hover over any symbol to see what it does

Try it

\$\endgroup\$
3
\$\begingroup\$

Ruby, 39 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ r-[x]==r saves a byte. \$\endgroup\$
    – Dingus
    Oct 5, 2023 at 21:13
3
\$\begingroup\$

Vyxal, 5 bytes

⁰Ǒ₂)ȯ

Try it Online!

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

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. :) \$\endgroup\$ Oct 5, 2023 at 9:52
  • \$\begingroup\$ @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 \$\endgroup\$
    – lyxal
    Oct 5, 2023 at 9:54
  • \$\begingroup\$ 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. \$\endgroup\$ Oct 5, 2023 at 17:32
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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…

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

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.

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

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.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Welcome to Code Golf Stack Exchange, and nice first answer! \$\endgroup\$
    – noodle man
    Oct 8, 2023 at 0:37
  • \$\begingroup\$ Thank you very much! \$\endgroup\$
    – hbhbnr
    Oct 8, 2023 at 1:25
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – noodle man
    Oct 8, 2023 at 1:54
1
\$\begingroup\$

Charcoal, 26 bytes

NθNηW‹Lυη⊞υ⁺⊕↨υ⁰№×υθ⊕↨υ⁰Iυ

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

NθNη

Input n and i.

W‹Lυη

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.

Iυ

Output the found values.

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

NθFNF¬№×υθ⊕ι⊞υ⊕ιIυ

Try it online!

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

NθIΦ⊕N¬﹪⌕⮌X⁰↨ιθ⁰¦²

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 ).

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

Perl 5.10 -n, 31 bytes

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

Try it online!

Translate of @Arnaulds Javascript method above.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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