text:
(RGS 1/5) Binary multiples
A binary multiple of a positive integer k is a positive integer n such that n is written only with 0s and 1s in base 10 and n is a multiple of k. For example, 111111 is a binary multiple of 3.
It is easy to show that a positive integer has infinitely many binary multiples. See here for a construction proof of one binary multiple for each k. Multiplying by powers of 10 you get infinitely many more.
Your task
Given a positive integer k, return the smallest binary multiple of k.
Input
A positive integer k.
Output
A positive integer n, the smallest binary multiple of k.
Test cases
2 -> 10
3 -> 111
4 -> 100
5 -> 10
6 -> 1110
7 -> 1001
8 -> 1000
9 -> 111111111
10 -> 10
11 -> 11
12 -> 11100
13 -> 1001
14 -> 10010
15 -> 1110
16 -> 10000
17 -> 11101
18 -> 1111111110
19 -> 11001
20 -> 100
100 -> 100

This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

This is the first challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is 450 reputation in prizes! (See 6 of the rules)
Otherwise, this is still a regular code-golf challenge, so enjoy!

Related: One-zero dividend. I think this isn't a duplicate though because in that challenge all the 1's had to come before all the 0's and you didn't have to output the smallest instance.

@xnor thanks! Looking forward for your submission

This is OEIS A004290.

So which answer surprised you the most?

@a'_' ahaha incredible. Are you going to post an answer in Roj?

Related

05AB1E, 6 bytes
∞b.ΔIÖ

Try it online! or verify all test cases (courtesy of @KevinCruijssen)

Explanation
∞b           - Infinite binary list
  .Δ         - Find the first value such that..
    IÖ       - It's divisible by the input

Short answer, good job! Do you think you can add the TIO link with all the test cases?

@RGS Here ya go. ;)

Thanks @KevinCruijssen was going to have to go work out how to do that ;)

@ExpiredData Ah, shall I delete it so it'll be a learning curve for you? ;)

@KevinCruijssen nah I would have just gone and stolen it from another one of your answers

Python 2, 42 bytes
f=lambda k,n=0:n*(max(`n`)<'2')or f(k,n+k)

Try it online!

Full program, same length:
a=b=input()
while'1'<max(`b`):b+=a
print b

Try it online!

Nice Python submission! If the full program is the same length and doesn't exceed the Recursion Depth, why don't you use it as the "main" submission? :)

MATL, 10 bytes
`@YBUG\}HM

Try it online! Or verify all test cases.
Explanation
`      % Do...while
  @    %   Push iteration index (1-based)
  YB   %   Convert to binary string (1 gvies '1', 2 gives '10,  etc).
  U    %   Convert string to number ('10' gives 10). This is the current
       %   solution candidate
  G    %   Push input
  \    %   Modulo. Gives 0 if the current candidate is a multiple of the
       %   input, which will cause the loop to exit
}      % Finally: execute on loop exit
  H    %   Push 2
  M    %   Push input to the second-last normal function (`U`); that is,
       %   the candidate that caused the loop to exit, in string form
       % End (implicit). If top of the stack is 0: the loop exits.
       % Otherwise: a new iteration is run
       % Display (implicit)

"Ah, why is there a bug in my program? Hm..."

I removed the bug but I don't think I fixed it :( +1!

JavaScript (ES6), 37 bytes
Looks for the smallest \$n\$ such that the decimal representation of \$p=n\times k\$ is made exclusively of \$0\$'s and \$1\$'s.
f=(k,p=k)=>/[2-9]/.test(p)?f(k,p+k):p

Try it online! (some test cases removed because of recursion overflow)

JavaScript (ES6), 41 bytes
Looks for the smallest \$n\$ such that \$k\$ divides the binary representation of \$n\$ parsed in base \$10\$.
k=>(g=n=>(s=n.toString(2))%k?g(n+1):s)(1)

Try it online! (all test cases)

R, 50 38 bytes
-4 bytes thanks to Giuseppe.
grep("^[01]+$",(k=scan())*1:10^k)[1]*k

Try it online!
It follows from this blog post (linked in the question) that the smallest binary multiple of \$k\$ is smaller than \$2\cdot10^{k-1}\$; this answer uses the larger bound \$k\cdot10^k\$ instead.
Creates a vector of all multiples of \$k\$ between \$k\$ and \$k\cdot10^k\$. The regexp gives the indices of those made only of 0s and 1s; select the first index and multiply by \$k\$ to get the answer.
Will time out on TIO for input greater than 8, but with infinite memory it would work for any input.

Use grepl! 40 bytes. I came here to comment a grepl approach based on my SNOBOL answer and found your regex to be better :-) I had !grepl("^[10]+$",F) for the record.

@Giuseppe Thanks! I knew about grepl but somehow convinced myself that it led to a longer answer... Your version is cleaner!

@Giuseppe Changed again, this time using your original regexp in another grep solution.

Quite clever! Glad I could be of assistance with that! :-)

PHP, 38 bytes
while(($n=decbin(++$x))%$argn);echo$n;

Try it online!
Counts up n in binary and divides it's decimal representation by k until there is no remainder; indicating the first, smallest multiple.

Thanks for your PHP submission and thorough test case coverage! +1

T-SQL, 57 bytes
This script is really slow when using 18 as input
DECLARE @z INT = 18

DECLARE @ int=1WHILE
@z*@ like'%[^10]%'SET @+=1PRINT @z*@

T-SQL, 124 bytes
T-SQL doesn't have binary conversion
This will execute fast:
DECLARE @ int=1,@x char(64)=0,@a int=2WHILE
@x%@z>0or @x=0SELECT
@x=left(concat(@%2,@x),@),@a-=1/~@,@=@/2-1/~@*-~@a
PRINT @x

Try it online

I just can't seem to accept that SQL solves these challenges +1... What is the T- in T-SQL?

@RGS sql really is horrible for golfing, but it is the only language I know well enough to golf at this level, sql is also it is quite readable(maybe not in this case, but that is not the sql part). T stands for Transact.

maybe it wasn't clear, but I am impressed by your submissions! I wasn't trying to put you down or anything! keep up the really interesting work :D

@RGS not to worry, I took it as a compliment. It's cool that you post so many interesting questions.

Thanks for your feedback! I try to, at least :) See you next challenge!

Charcoal, 19 bytes
≔1ηＷ﹪ＩηＩθ≔⍘⊕⍘η²¦²ηη

Try it online! Link is to verbose version of code. Explanation:
≔1η

Start at 1.
Ｗ﹪ＩηＩθ

Repeat until a multiple of n is found, treating the values as base 10.
≔⍘⊕⍘η²¦²η

Convert from base 2, increment, then convert back to base 2.
η

Output the result.

Haskell, 44 38 36 bytes
Saved two bytes by using filter as suggested by @ovs.
f k=filter(all(<'2').show)[0,k..]!!1

Try it online!
This checks all multiples of k and is slow for input 9 and 18.
I much prefer this version which defines the list of all "binary" numbers and searches for the first multiple of k among them. It quickly handles all test cases, but needs  52 bytes:
b=1:[10*x+d|x<-b,d<-[0,1]]
f k=[m|m<-b,mod m k<1]!!0

Try it online!

2 bytes shorter with filter.

@ovs Thanks, that still applies to my newer version. Somehow I always feel that list comprehension must be shorter...

Japt, 11 9 8 bytes
È*nvU}a¤

Try it

Really cool solution, and it is crazy fast +1! Is it fast because of the algorithm used or because of the Japt machinery?

I think this fails for 11.

It's probably because 11 is crossed out in the program length part.

Python 3.8 (pre-release),, 75\$\cdots\$ 50 52 bytes
Saved 2 bytes thanks to Mukundan!!!
Added 2 bytes to fix error kindly pointed out by Giuseppe.
f=lambda k,n=1:(i:=int(f"{n:b}"))%k and f(k,n+1)or i

Try it online!

you can save 2 bytes by doing f'{n:b}' instead of bin(n)[2:] Try it online!

@Mukundan Clever use of f-strings - thanks! :-)

Bash + Unix utilities, 52 bytes
for((n=1;n%$1;));do n=`dc<<<2dio1d$n+p`;done
echo $n

Try it online!
This counts in binary, views the resulting numbers in base 10, and stops when a multiple of the input is reached.

Jelly,  8  7 bytes
‘¡DṀḊƊ¿

Try it online!
How?
Note that in Jelly empty lists are falsey, while other lists are truthy. Also dequeue, Ḋ, is a monadic atom which removes the first item from a list, but when presented with only an integer Jelly will first convert that integer to a list by forming the range [1..n] thus Ḋ yields [2..n].

‘¡DṀḊƊ¿ - Link: integer, k
      ¿ - while...
     Ɗ  - ...condition: last three links as a monad:
  D     -     decimal digits   e.g. 1410 -> [1,4,1,0]  or 1010 -> [1,0,1,0]
   Ṁ    -     maximum                       4                     1
    Ḋ   -     dequeue (implicit range of)   [2,3,4]               []
        -                                   (truthy)              (falsey)
 ¡      - ...do: repeat (k times):
‘       -     increment

For some reason, when the body of a while loop, ¿, is a dyad each iteration sets the left argument to the result and then sets the right argument to the value of the left argument, so the 6 byte +DṀḊƊ¿ does not work. (For example given 3 that would: test 3; perform 3+3; test 6; perform 6+3; test 9; perform 9+6; test 15; perform 15+9; etc...)

Previous 8:
DḂƑȧọð1#

(DḂƑ could be DỊẠ too.)
An alternative 8:
DṀ+%Ịð1#

W, 7 6 bytes
-1 because I realized that W has operator overloading over t.
•B⌡≡kü

Uncompressed:
*Tt!iX*

repl.it is quite slow and you need to type in the program in code.w.
Explanation
        % For every number in the range
    i   % from 1 to infinity:
     X  % Find the first number that satisfies
*       %     Multiply the current item by the input
 T      %     The constant for 10
  t     %     Remove all digits of 1 and 0 in the current item
        %     Both operands are converted to a string, just like in 05AB1E.
   !    %     Negate - checks whether it contains only 1 and 0.

      * % Multiply that result with the input (because it's the counter value).
```

Thanks for your W submission! I never understood why you include some code, and then right after it you say "uncompressed" and then include some other code. What does it mean?

The first code snippet is a compressed form of the W program, compressed in order to use up all 256 codepoints of CP437. However, there's also another non-compressed form that is human-writable (I compress my source code from on this form). The next code snippet is a human-readable non-compressed form of the W program (hence the "uncompressed"), which is part of the explanation.

Ok, I think I understand better now.

Where is the "get smallest" part?

The wiki says X is SW and S is swap while W is described as "keeps the specified items...", is something in the wiki wrong or have I misinterpreted or missed something? Also could you link to an online evaluator (e.g. get it on TIO)? (By the way I did not know you replied, do use @)

@JonathanAllan Whoops, I forgot to add that W's behavior is different with an infinity value. Nice catch. There isn't an online interpreter with a permalink for W yet, I'm waiting for Dennis to recover.

Retina 0.8.2, 68 bytes
.+
$*1:1,1;
{`^(1+):\1+,(.+);
$2
T`d`10`.1*;
,0
,10
1+,(.+)
$1$*1,$1

Try it online! Somewhat slow so no test suite. Explanation:
.+
$*1:1,1;

Initialise the work area with n in unary, k in unary, and k in decimal.
{`^(1+):\1+,(.+);
$2

If n divides k then delete everything except the result. This causes the remaining matches to fail and eventually the loop exits because it fails to achieve anything further.
T`d`10`.1*;
,0
,10

Treat k as a binary number and increment it.
1+,(.+)
$1$*1,$1

Regenerate the unary conversion of k.

Bash + Core utilities, 40 bytes
seq $1 $1 $[10**$1]|grep ^[01]*$|head -1

Try it online!

Nice bash submission +1! Also harnessing the power of regexs, aren't you?

This is really nice.  Is it mathematically guaranteed that the solution will be less than or equal to 10^input?

@Jonah Yes, in the question, RGS posted a link to a proof that there is always some value that works, and the proof actually yields that upper bound. Here’s the link: https://mathspp.com/blog/binary-multiples

@Jonah In fact, the upper bound proven is 10^input - 1 but it would take more bytes in the bash code to stop at that point.  Of course, there's no harm done by producing the one extra value.

@Jonah Sorry, the upper bound proven is the number consisting of n 1s, which is even less than I had said.

Ruby, 42 40 36 bytes
->k{z=k;z+=k until z.digits.max<2;z}

Try it online!
Very slow for 18, but ultimately gets the job done.
4 bytes golfed down by G B.

Java 10, 62 59 58 bytes
n->{var r=n;for(;!(r+"").matches("[01]+");)r+=n;return r;}

Try it online.
Explanation:
n->{             // Method with long as both parameter and return-type
  var r=n;       //  Result-long, starting at the input
  for(;!(r+"").matches("[01]+");)
                 //  Loop as long as `r` does NOT consists of only 0s and 1s
    r+=n;        //   Increase `r` by the input
  return r;}     //  After the loop is done, return `r` as result

This method above only works for binary outputs \$\leq1111111111111111111\$. For arbitrary large outputs - given enough time and resources - the following can be used instead (99 70 64 bytes):
n->{var r=n;for(;!(r+"").matches("[01]+");)r=r.add(n);return r;}

Try it online.

Isn't the reason the first code fails numeric type limitations, and doesn't everybody pretend they do not exist?

@mypronounismonicareinstate You're correct. I just figured I'd add a lambda function using java.math.BigInteger instead of int/long to prove it is possible to support an arbitrary large output if you'd want to.

Perl 5, 21 +2 (-ap) = 23 bytes
$_+=$F[0]while/[^01]/

Run with -a and -p, input to stdin. Just keeps repeatedly adding the input for as long as the result contains anything other than digits 0 and 1.
Try it online!

C (gcc), 80 bytes
r,m,n;b(h){for(r=0,m=1;h;h/=2)r+=h%2*m,m*=10;h=r;}f(k){for(n=1;b(++n)%k;);b(n);}

This can probably be improved some but I have yet to find a way.
Converts the integer into binary and checks if it's a multiple.
Brute-force.
Try it online!

Very clever how f() only needs to call b() (which assigns return value to parameter) rather than assign return value to parameter!

@Noodle9 I wish I could omit the double-call but div puts the result of modulo in eax (which means eax will always be 0 after the loop).

Do you mean the modulo result is in edx?

@640KB Yes. I didn't look up the docs beforehand.

J, 24 23 22 bytes
+^:(0<10#@-.~&":])^:_~

Try it online!
Add the number to itself + while ^:...^:_ the following is true:
(0<10#@-.~&":]) - Something other than the digits 0 and 1 appear in the stringified number.

I like your submission. Can't even tell why

Python 3, 50 48 bytes
f=lambda k,n=0:n*({*str(n)}<={*"01"})or f(k,n+k)

Try it online!
Explanation

n represents the current multiple of k.
{*str(n)}<={*"01"} checks if n only contains digits 0 or 1. This is done by creating a set of characters of n, then checks if that set is a subset of \$\{0,1\}\$.
n*({*str(n)}<={*"01"}) or f(k,n+k) is arranged such that the recursive call f(k,n+k) is only evaluated when n is 0 or n is not a binary multiple of k. Here multiplication acts as a logical and.

Wolfram Language (Mathematica), 49 bytes
(x=#;While[Or@@(#>1&)/@IntegerDigits@x,x=x+#];x)&

Try it online!

This fails on 11 (and, likely, 9) - the code should output the smallest binary multiple, and this one outputs the first one that has both zeroes and ones. 0-byte fix

This does not work for 3! Ping me as soon as you fix it!

@RGS Ping......

@S.S.Anne thanks! My pinger is broken

Burlesque, 13 bytes
rimo{>]2.<}fe

Try it online!
9 & 18 do work, but take a while because they're such large multiples. So I've taken them out of tests.
ri    # Read to int
mo    # Generate infinite list of multiples
{
 >]   # Largest digit
 2.<  # Less than 2
}fe   # Find the first element s.t.

C# (Visual C# Interactive Compiler), 53 49 bytes
turns out Max can cast chars to codes implicitly
I tried a recursive version, but it was longer. Can't think of a way to replace the loop with LINQ...
a=>{int r=a;while($"{r}".Max()>49)r+=a;return r;}

Try it online!

I don't think LINQ will be better

@ExpiredData Well, that "can't think of a way" part was implicitly followed by "without doubling the byte count" :)

It's not that far off 16 bytes more.. maybe there's a way to golf it down.

Thanks for your C# submission! What is the LINQ thing?

@RGS: Language INtegrated Query (LINQ) is an series of APIs in .Net that allow you to handle collections with a query language. It has two syntaxes: 1. SQL-like syntax 2. Fluent syntax on the IEnumerable interface. See here for the official documentation: https://docs.microsoft.com/en-us/dotnet/standard/using-linq

MathGolf, 9 bytes
0ô+_▒╙2<▼

Try it online. (Test cases n=9 and n=18 are excluded, since they time out.)
Explanation:
0          # Start with 0
        ▼  # Do-while false with pop,
 ô         # using the following 6 commands:
  +        #  Add the (implicit) input-integer to the current value
   _       #  Duplicate it
    ▒      #  Convert it to a list of digits
     ╙     #  Pop and push the maximum digit of this list
      2<   #  And check if this max digit is smaller than 2 (thus 0 or 1)
           # (after the do-while, the entire stack joined together is output implicitly)

Question: if you answered 10 seconds ago, how come you already golfed it down from 10 to 9 bytes..? +1 for the mathgolf submission though

@RGS Yeah, could have just gone with the 9-byter, haha. I golfed it while adding the explanation (thus before posting) and realizing it could be shorter. EDIT: I've removed the strike-through 10.

If I golf my answer within the grace period then I never strike through because there's no way to recover the previous version.

Red, 52 bytes
func[n][i: 0 until[""= trim/with to""i: i + n"01"]i]

Try it online!
Red, 54 bytes
func[n][i: 0 until[parse to""i: i + n[any["0"|"1"]]]i]

Try it online!

Stax, 9 bytes
ü◘ø⌠Δ>0↔å

Port of my MathGolf answer. This is only my second Stax answer, so there might be a shorter alternative.
Try it online or try it online unpacked (10 bytes).
Explanation (of the unpacked version):
0             # Start at 0
 w            # While true without popping, by using everything else as block:
  x+          #  Add the input-integer
    c         #  Duplicate the top of the stack
     E        #  Convert it to a list of digits
      |M      #  Get the maximum of this list
        1>    #  And check that it's larger than 1
              # (after the while, the top of the stack is output implicitly as result)

Cool Stax submission +1! Was stax created by someone from CG.SE?

@RGS yep, by recursive. :)

Nice! Didn't know about that meta question.

I'm not a really good Stax golfer. Run and debug it

@a'_' That unfortunately won't work for inputs that are already correct, like 1, 10, 11,100, etc.

Icon, 50 bytes
procedure f(n)
i:=seq(n,n)&0=*(i--10)
return i
end

Try it online!
seq(n,n) generates an "infinite" (seq operator doesn’t work with large integers) sequence starting at n with step n
&is conjunction - Icon evaluates the next expression and if it fails, than backtracks to the expression to its left - so generates the next integer.
i--10 finds the difference of the string representation of i with the string 10 - Icon automatically casts number to strings when an operation on strings is used.
*(1--10) finds the length of the difference of i and 10 (which is a string)
0=*(1--10) - if the length is 0, the number is composed only of 1's and 0's.

Another uncommon language :D

@RGS Yes, it's true! Icon is an old language with some nice features, especially for its time. I'll write a short explanation of my code.

Husk, 9 7 bytes
ḟoΛεd∫∞

Try it online!
-2 bytes from Leo.

M*N would save you 1 byte over m*⁰N, but this can be even shorter by summing the input to itself repeatedly with ∫∞ Try it online!

I thought of ¡+₁, but ∫∞ is a lot smarter.

Pyth, 10 bytes
.Bf!%s.BTQ

Try it online!
f: Filter of all integers in increasing order, starting from an input of 1. Output the first matching input.
.BT: Convert the input to binary, as a string.
s: Convert the string to a base 10, as a integer.
% ... Q: Modulo the input
!: Boolean negation - returns true only if divisible.
.B: Convert the output of the filter back to a binary string and print it.

Thanks for your Pyth submission! +1

There is also a much less efficient 10 byter.

GolfScript, 31 bytes
:i;1{).{2 base}:b~{`+}*~i%}do b

Worked for 2-15 wen I tried them out, didn't bother doing more. May post explanation later, just wanted to get a brute submission down.
Try it online!

Gaia, 10 9 bytes
⟨:$2…⁻⟩+↺

Try it online!
		| implicit input, n
⟨     ⟩		| (1) monadic link:
 :$		| dup, and get decimal digits
   2…⁻		| remove all 1s and zeros
	↺	| if the result is truthy (non-empty)
       +	| add n and repeat from (1)
		| implicitly print result.

Times out on n=9...
Gaia, 10 bytes
1⟨bdĖ⟩#ebd

Try it online!
Somewhat more interesting and also a lot faster; finds the first integer where: converting it to binary and interpreting as decimal digits are divisible by the input (and ebd converts it to the decimal form).

Wolfram Language (Mathematica), 40 bytes
(For[x=#,Max@IntegerDigits@x>1,x+=#];x)&

Try it online!
Ignoring maximum iteration limits, 37 bytes
#//.a_?(Max@IntegerDigits@#>1&):>a+#&

Try it online!
This will halt when the depth of 65536 is reached (i.e. if the result is larger than 65536 * (input)).

#//.a_?(Max@IntegerDigits@#>1&):>a+#& could have worked with 37 bytes if it didn't have the built-in iteration limit of 65536.

I am pretty sure it is ok to use the 37 byte solution. Recursive Python solutions also have a recursion depth of 1000 and those are valid solutions.

Roj, 178 173 171 161 160 156 153 152 141 bytes
Because I am completely new to Roj, there may still be potential golfs out here.
readint I;C=0;while 1 do
C=C+I;i=C;L=0<1;while i do
c=0;while c<=i/10 do
c=c+1
end;c=c-1;L=L and(i-10*c)<2;i=c
end;if L do
out C;halt
end
end

Explanation
It's made primarily for me to find potential golfs.
Indented:
readint I; $ Take an input integer & save it into the variable I $
C = 0;     $ C: The counter that stores the current value $

while 1 do $ Forever: $

    C = C + I; $ Add the counter by the input $

    i = C; $ Copy the counter to a mutable variable $

    L = 0 < 1; $ Set the "Logic" variable to a truthy value $

               $ "0<1" is shorter than directly hard-coding "True", a 4-byte value $

    $ Check whether the input is made of 0 and 1 $

    $ This modifies the L variable $

    while i do $ Do the following "Scan" until we run out of digits $
        $ "Scan" over the input until we reach the end of the input $

        $ Current procedure: floor the value of the multiple / 10 $
        c = 0; $ Set the flooring result to the variable c $

        while c <= i / 10 do $ While the current counter is less $
                             $ than or equal to the multiple / 10 $
            c = c + 1        $ Increment the counter $
        end;
        c = c - 1;           $ Since we have one extra +1 to break $
                             $ out of the loop, we decrement the counter $

        L = L and (i - 10 * c)<2; $ Finally! Compare the currently-scanned $
                             $ number's equality with 1 or 0 $

        $ (i - 10 * c) Calculates i - 10 * (i // 10) $
        $ We already calculated (i // 10), $
        $ Hence the weird output expression $

        i = c                $ Divide the multiply by 10, floor that result $
    end;

    if L do         $ If this multiple is made of binary digits: $
        out C;      $ Output this multiple $
        halt        $ Stop the program $
    end
end
```

I might be looking at the 50 rep winner! Good job here

@RGS Have you made any other languages? I feel obliged to popularize them.

I haven't, no :p

JavaScript (Node.js), 50 bytes
(x,i=1,g=v=>v.toString(2))=>g(i)/x%1?f(x,++i):g(i)

Try it online!

Thanks for your submission! Have you checked out this JS answer? :D

C (gcc), 53 48 bytes
n,m;F(k){for(n=m=k;m>1;m=m%10>1?n+=k:m/10);n=n;}

Try it online!
Explanation:
int F(int k)
{
    int n = k;
    int m = k;

    for (; m > 1;)
    {
        if (m % 10 > 1)     // no solution if least significant digit nether 0 nor 1. Try next multiple of k.
        {
            n += k;
            m = n;
        }
        else                // if the least significant digit is 0 or 1 divide by ten
        {
            m /= 10;
        }
    }

    return n;
}

Edit: removed return

APL (Dyalog Unicode), 13 bytesSBCS
+⍣{∧/2>⍎¨⍕⍺}⍨

Try it online!
Straightforward algorithm: Repeat adding self until all digits are less than 2.
How it works
+⍣{∧/2>⍎¨⍕⍺}⍨  ⍝ Input: n
+⍣{        }⍨  ⍝ Repeat adding n with starting value of n, until ... is true:
       ⍎¨⍕⍺    ⍝   Extract the digits
   ∧/2>        ⍝   All of the digits are less than 2

Japt, 9 bytes
_%U}f_Ä ¤

Try it

Python 2, 42 bytes
f=lambda k,n=0:max(`n`)!='1'and k+f(k,n+k)

Try it online!
A recursive function. We terminate when the maximum character of the string representation is 1. We can't quite use '<2' instead because zero would trigger it, and we don't have a good way not to start at zero.
The larger outputs run out of recursion depth, at least with the default value. We'll also eventually get another issue with huge inputs when Python 2's backticks string representation appends an L for "long" to numbers starting with 2**63, which will always be the maximum.

Python 2, 42 bytes
n=k=input()
while'1'<max(`n`):n+=k
print n

Try it online!
A program, using a pretty straightforward loop.

SNOBOL4 (CSNOBOL4), 68 55 bytes
	N =INPUT
A	X =X + N
	X NOTANY(10)	:S(A)
	OUTPUT =X
END

Try it online!
Adds N to X; if X contains any non-binary digits, repeat. Then print X.

This feels like a very exotic submission! Thanks :D

@RGS I like the challenge of golfing in a half-century old language.

Jelly, 9 bytes
1BḌọɗ1#BḌ

Try it online!
A monadic link taking an integer \$n\$ and returning an integer.
Two bytes longer than @JonathanAllan’s solution, but a different approach so I still thought worth posting.
Explanation
1   ɗ1#   | Starting with 1, find the first integer for which the following is true, using n as the right argument:
 B        | - Convert to binary
  Ḍ       | - Convert from decimal digits to integer
   ọ      | - Number of times divisible by n
       B  | Convert to binary
        Ḍ | Convert from decimal digits to integer

Another alternative Jelly, 9 bytes
2*B€ḌọƇ⁸Ḣ

Try it online!

(now at 2 bytes longer :P ) Thanks for posting the alternative solution!

Perl 6, 29 bytes
{first /^[0|1]+$/,(1..*X*$_)}

Try it online!
Find the first multiple of the input that is only composed of ones and zeroes

Thanks for your Perl submission! Using regexs here, hun? :D

Haskell, 38 bytes
f x=filter(all(<'2').show)[x,x+x..]!!0

Try it online!
Explanation
We make all the multiples of x with [x,x+x..], filter them to contain only digits smaller than two filter(all(<'2').show) and then take the first one !!0

Really cool solution +1 Thanks for it.

You may want to compare with mine.

Julia 1.0, 38 bytes
f(k,n=k)="10"⊇repr(n) ? n : f(k,n+k)

Try it online!

It is fairly annoying that you need spaces around ?:, isn't it?

Pip, 16 12 bytes
TMXa<2a+:@ga

-4 bytes from Dlosc (removed unnecessary function)
The same general approach that most other answers are using: Loop until we reach a multiple that can also be a binary number. Takes very long for numbers \$>17\$.
Try it online!
Pip, 27 bytes
x:a
MN({a%x?0a}MTB,2**a)RM0

Converts all numbers till \$2^n\$ to binary and checks divisibility. Then removes all the 0's and gets the minimum. Takes very long for numbers \$>14\$.
Try it online!

Nice use of @g! -4 bytes because UQ isn't necessary and neither are the parentheses.

For the second version, you can use FIlter instead of map-to-zero-and-remove-zeros.

why's it say that FI is not a unary operator? https://tio.run/##K8gs@P@/wiqRy9dPw80zxEnHSEsrUTPI1@D///9mAA

Because I added unary FI just yesterday.. Unfortunately, TIO isn't getting updates at the moment, so it's unclear when or whether new features will be available there. :( In the meantime, you can either run Pip from command-line or use _FI on TIO.

Cool, I'll try it.

PowerShell, 41 bytes
for(;++$n%"$args"-or$n-match'[2-9]'){}
$n

Try it online!

PowerShell, 41 bytes
for(;++$n%"$args"-or$n-replace'0|1'){}
$n

Try it online!

PowerShell, 74 bytes
param($x)for(){$n=iex ([convert]::tostring(++$i,2));if(!($n%$x)){$n;exit}}

Try it online!

K (ngn/k), 17 bytes
{(|/1<10\)(x+)/x}

Try it online!
Sets up a straightforward while-over, seeded with x. Runs until (|/1<10\) returns 0 when executed on the result.

(...)(x+)/x generate the next multiple of the original input, starting with the initial input
(|/1<10\)(...)/x the condition tested after each iteration

10\ convert to digits
|/1< check if any digit is larger than 1

Thunno 2, 5 bytes
(G⁻;+

Try it online!
Explanation
(G⁻;+  # Implicit input
(  ;   # While loop
 G     # (condition)  Maximum of (implicit cast to digits of) top of stack
  ⁻    #              Decrement (i.e. not equal to one)
    +  # (body)  Add the input to the top of stack
       # Implicit output

Vyxal, 38 bitsv1, 4.75 bytes
{:₀F|+

Try it Online!
Ports Thunno 2 but with fractional bytes.
Explained
{:₀F|+
{   |   # While:
  ₀F    #   The numbers from 10 removed from
 :      #   A copy of the top of a stack is not empty
    |   # Do:
     +  #   Add the input to the top of the stack

 Created with the help of Luminespire at https://vyxal.github.io/Luminespire

Python 3, 230 bytes
def f(n):
 s="1"
 while 2>1:
  if int(s)%n==0:
   return s
  if "0" in s:
   for j in range(0,len(s)):
    if s[j]=="0":
     q=j
   t=s[:q]
   for k in range(q,len(s)):
    t=t+str(1-int(s[k]))
   s=t
  else:
   s=str(10**len(s))

This seems a bit long to me, any suggestions that don't involve using lambdas would be appreciated.

Scala, 67 bytes
Port of @ovs's Python answer in Scala.

Try it online!
def f(k:Int,n:Int=0):Int=if(n>0&&n.toString.max<'2')n else f(k,n+k)


text:
Computing a specific coefficient in a quotient of polynomials
Context
After "Computing a specific coefficient in a product of polynomials", asking you to compute a specific coefficient of polynomial multiplication, I wish to create a "mirror" challenge, asking you to compute a specific coefficient from polynomial division.
Polynomial division
Let us establish an analogy with integer division. If you have two integers a and b, then there is a unique way of writing a = qb + r, with q, r integers and 0 <= r < b.
Let p(x), a(x) be two polynomials. Then there is a unique way of writing a(x) = q(x)p(x) + r(x), where q(x), r(x) are two polynomials and the degree of r(x) is strictly less than the degree of p(x).
Algorithm
Polynomial division can be performed through an iterative algorithm:

Initialize the quotient at q(x) = 0
While the degree of a(x) is at least as big as the degree of p(x):

let n = degree(a) - degree(p), let A be the coefficient of the term of highest degree in a(x) and P be the coefficient of highest degree in p(x).
do q(x) = q(x) + (A/P)x^n
update a(x) = a(x) - p(x)(A/P)x^n

q(x) is the quotient and what is left at a(x) is the remainder, which for our case will always be 0.

Task
Given two polynomials a(x), p(x) such that there exists q(x) satisfying a(x) = p(x)q(x) (with all three polynomials having integer coefficients), find the coefficient of q(x) of degree k.
(Yes, we are assuming the remainder is 0)
Input
Two polynomials (with integer coefficients) and an integer.
Each input polynomial can be in any sensible format. A few suggestions come to mind:

A string, like "1 + 3x + 5x^2"
A list of coefficients where index encodes exponent, like [1, 3, 5]
A list of (coefficient, exponent) pairs, like [(1, 0), (3, 1), (5, 2)]

An input format must be sensible AND completely unambiguous over the input space.
The integer k is a non-negative integer. You may take it in any of the usual ways. You can assume k is less than or equal to the differences of the degrees of a(x) and p(x), i.e. k <= deg(a) - deg(p) and you can assume deg(a) >= deg(p).
Output
The integer corresponding to the coefficient of x^k in the polynomial q(x) that satisfies the equality a(x) = q(x)p(x).
Test cases
The input order for the test cases is a(x), p(x), integer k.
[12], [4], 0 -> 3
[0, 0, 6], [0, 3], 0 -> 0
[0, 0, 6], [0, 3], 1 -> 2
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 0 -> 7
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 1 -> 0
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 2 -> 1
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 3 -> 6
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 0 -> -5
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 1 -> 7
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 2 -> -10
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 3 -> -8
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 4 -> 1
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 5 -> 0
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 6 -> -1

This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!
(This is not part of the RGS Golfing Showdown)

related

The 4,5,6 examples are wrong: q(x)=7 + x^2 + 6 x^3 so coefficients {0,1,2,3} = {7,0,1,6}

Note to self: never do test cases by hand and late at night again

@J42161217 thanks, I had skipped the test case with only x and counted wrong :p fixed!

Also in first test case 15/4 = 15/4 not 3

@J42161217 where? :P

https://rosettacode.org/wiki/Polynomial_synthetic_division#Python

MATL, 6 bytes
Y-PiQ)

The inputs contain the coefficients in order of decreasing powers.
Try it online! Or verify all test cases
Explanation

(De)convolution is the key to success

     % Implicit inputs: two numerical vectors
Y-   % Deconvolution
P    % Flip
i    % Input: integer
Q    % Add 1
)    % Get the entry at that position
     % Implicit display

Really short answer! Didn't know of that "deconvolution" operation

Wolfram Language (Mathematica), 31 bytes
Coefficient[Factor[#/#2],x,#3]&

Try it online!

Nice you managed to reduce the byte count!

A different approach with the same byte count:  Limit[D[#/#2,{x,#3}]/#3!,x->0]&  (It calculates the kth-order coefficient in the Taylor series of the quotient, which will just be the polynomial coefficient.  Note that setting x to 0 via ... /.x->0 doesn't work for all polynomials.)

Unfortunately, SeriesCoefficient[#/#2,{x,0,#3}]& is two bytes longer.

@MichaelSeifert yes, I tried many things myself but they didn't work for all cases...

JavaScript (ES6), 81 bytes
Takes input as (a,p,k). The polynomial coefficients are expected from highest to lowest.
(a,[c,...p],k)=>a.slice(p.length+k).map((_,n)=>p.map(v=>a[++n]-=v*q,q=a[n]/c))&&q

Try it online!

What is going on with the &&q at the end? Is it just to return the coefficient you want? q stores the intermediate coefficients of the quotient, right?

@RGS Yes, the last $q$ is the answer.

Python 3, 51 49 48 bytes
Input: a, p, k. The format for the polynomials a and p is a list of coefficients, in order of highest to lowest degree.
lambda*p,k:numpy.polydiv(*p)[0][~k]
import numpy

Try it online!

Turns out importing numpy gives a really short answer! +1 well played

Pari/GP, 24 bytes
f(a,p,k)=polcoeff(a/p,k)

Try it online!

I see :p really short submission! Good job +1

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Is it really time?
A time in the format hhMMss is represented by six numbers in the range 0..9 (e.g.100203 for 3 seconds after 2 minutes after 10am (10:02.03), or 155603 for three seconds after 56 minutes after 3pm (15:56.03).
Treating these times as integers, these numbers are therefore in the range 000000 to 235959; but not all numbers in that range are valid times.
Normally, though, integers aren't represented with leading 0s, right?
So, this challenge is to take a numeric input (without leading 0s), and say whether it represents a proper time or not when the leading 0s are put back.
Input
Any integer, as a string or an integer type, in the range 0..235959 inclusive. all numbers as strings will be input with no leading 0s (e.g. 2400, not 002400). The time 000000 maps to 0; or exceptionally as  . Inputs outside of this range should return Falsy, but there is no requirement that they are supported.
Output
Truthy/Falsy value - by which I mean there must be a consistent distinction in the output between True and False - e.g. True could be output as 1 and False could be any other output (or even a variable output) - as long as it can be documented how to tell what is True and what is not.
More Challenge Details
Given the input integer, figure out if the number represents a time (Truthy) or not (Falsy).
A number represents a time if a time (hhMMss) with leading 0s removed is the same as the number.
e.g. 00:00.24 is represented by 24
e.g. 00:06.51 is represented by 651
e.g. 00:16.06 is represented by 1606
e.g. 05:24.00 is represented by 52400
e.g. 17:25.33 is represented by 172533
There are therefore some numbers that can't represent times:
e.g. 7520 - this can't represent hhMMss because 00:75:20 isn't a time
As a general rule, the valid numbers fall into the pattern:
trimLeadingZeros([00..23][00..59][00..59]);
The following numbers are the entire set of inputs and the required answers for this challenge
Seconds only (e.g. 00:00.ss, with punctuation and leading 0s removed, -> ss)
0 to 59 - Truthy
60 to 99 - Falsy
Minutes and seconds (e.g. 00:MM.ss, with punctuation and leading zeros removed, -> MMss)
100 to 159 - Truthy
160 to 199 - Falsy
etc, up to:
2300 to 2359 - Truthy
2360 to 2399 - Falsy
2400 to 2459 - Truthy
2460 to 2499 - Falsy
etc, up to:
5900 to 5959 - Truthy
5960 to 9999 - Falsy
Hours 0..9, minutes and seconds (e.g. 0h:MM.ss with punctuation and leading zeros removed -> hMMss)
10000 to 10059 - Truthy
10060 to 10099 - Falsy
etc, up to:
15800 to 15859 - Truthy
15860 to 15899 - Falsy
15900 to 15959 - Truthy
15960 to 19999 - Falsy
20000 to 20059 - Truthy
20060 to 20099 - Falsy
20100 to 20159 - Truthy
20160 to 20199 - Falsy
etc, up to:
25800 to 25859 - Truthy
25860 to 25899 - Falsy
25900 to 25959 - Truthy
25960 to 25999 - Falsy
etc, up to:
95800 to 95859 - Truthy
95860 to 95899 - Falsy
95900 to 95959 - Truthy
95960 to 99999 - Falsy
Hours 10..23, minutes and seconds (e.g. hh:MM.ss with punctuation and leading zeros removed -> hhMMss)
100000 to 100059 - Truthy
100060 to 100099 - Falsy
100100 to 100159 - Truthy
100160 to 100199 - Falsy
etc, up to:
105800 to 105859 - Truthy
105860 to 105899 - Falsy
105900 to 105959 - Truthy
105960 to 109999 - Falsy
This pattern is then repeated up to:
235900 to 235959 - Truthy
(236000 onwards - Falsy, if supported by program)
Leading 0s must be truncated in the input, if strings are used.
Code golf, so least bytes wins - usual rules apply.
code-golf

I just can't find the left-pad built-in ...

Related (the portion about verifying whether a 6-digit number is a valid time)

You say input is in the range 0..235959 inclusive, but then you have a test case for 236000 onwards. You should clarify what's the actual range of inputs we need to support (I'd suggest 0..999999).

@Grimmy if your program accepts inputs outside of the range 0..235959 they should be falsy, but the specification doesn't require your program to be able to deal with inputs outside of that range

It's probably too late now, but I think this challenge would be more fun if the range could be beyond the 235959 and possibly even beyond the 999999. Now it simply boils down to (in pseudo-code) max(hh,mm,ss)<60 and we can just ignore the check on hours, since it's guaranteed to be valid.

Strictly speaking as long as it can be documented how to tell what is True and what is not means we can no-op. I believe you really want outputs to be in one of these four pairs: truthy vs falsey; falsey vs truthy; unique value, x vs anything but x; anything but x vs unique value x.

This is assuming a day with no leap second, or possibly TAI. For example, 2016-12-31 18:59:60 US/Eastern is a valid time.

@KevinCruijssen yes, you're right, I didn't think that through and it has led to an easier challenge

W, 6 bytes
Source compression ftw!
♀♥@p▒ö

Uncompressed:
2,a60<A

Explanation
2,      % Split number into chunks of length 2
        % The splitting is right-to-left *instead* of left-to-right.
      A % Is all items in the list ...
  a60<  % ... less than 60?

Does 2, split from right-to-left? If not, wouldn't this fail for an input like 659, which I assume becomes [65,9] instead of [6,59]?

Ah ok, nice, +1 from me in that case. (Your first sentence of your comment is reversed, but your edit in the answer is correct.) Most languages I know would split from left-to-right, so I was surprised to see it works from right-to-left in W. Btw, has there been any word from Dennis when W might be added to TIO? I think this is the third answer I see you post in W.

Python, 45 43 38 27 bytes
For inputs up until 239999:
lambda n:n/100%100<60>n%100

You can try it online! Thanks @Jitse and @Scurpulose for saving me several bytes ;)
For inputs above 239999 go with 36 bytes:
lambda n:n/100%100<60>n%100<60>n/4e3

@ElPedro thanks!! :) May be still more golfable

Also, the Python 2 solution works in Python 3, too. Float instead of int division does not matter.

Can save some more bytes by using n/4100 instead of n/c**2*2.5. Try it online!

@SurculoseSputum good find! But divide by 4000 then, as 100**2/2.5 = 4000. As variable c is now redundant, this can be reduced to lambda n:max(n%100,n/100%100,n/4e3)<60 for 38 bytes.

@Jitse Nice golf! For some reason I thought that245959 was a valid time, hence the 4100 :(

Note that the the program doesn't have to support input greater than 235959, so we can do away with the hour check.

Even keeping the hour check, lambda n:n%100<60>n/100%100<60>n/4e3 is 2 bytes shorter

Perl 6, 33 25 bytes
-7 bytes thanks to Kevin Cruijssen
60>*.polymod(100,100).max

Try it online!

26 bytes

You could also use a regex like some of the other answers for 20 bytes

APL (Dyalog Extended), 19 bytesSBCS
-10 bytes thanks to Kevin Cruijssen.
Anonymous tacit prefix function. Takes argument as integer.
⍱59<100∘⊤

Try it online!
100∘⊤ convert To base-100
59< are they, each, greater than 59?
⍱ are none of them true?

I don't know APL, but can't you save some bytes by checking if the maximum is $<60$ after the 100∘⊤? It halved the byte-counts of both my MathGolf answer and the 05AB1E answer, so I assume it should be able to save some bytes for your solution as well. (Note that the challenge states the valid input is in the range $[0,235959]$, so we won't need to check the hours.. I liked the challenge more when a larger range was possible tbh.)

@KevinCruijssen Yes, of course, since we know that we'll never get 240000 or above. Thanks!

Python, 35 bytes
f=lambda n:n<1or(n%100<60)*f(n/100)

A recursive function which returns 1 or True (which are truthy) if valid or 0 (which is falsey) if not.
Try it online! *
How?
True and False are equivalent to 1 and 0 respectively in Python.
The function (f=lambda n:...) checks that the last up-to-two digits as an integer (n%100) are less than sixty (<60), chops them off (n/100) and multiplies by a recursive call *f(...) until an input of zero is reached (n<1or) at which point True is returned. If at any stage the check fails a False is placed in the multiplication, which will then evaluate to 0 (a falsey value).

* Only f(0) evaluates to True, but set((True, 1, 1, ..., 1)) evaluates to {True} due to the equivalence of True and 1 in Python.

Java 8, 38 bytes
n->n%100<60&n%1e4<6e3&n%1e6<24e4&n<1e6

Try it online!
Basically an improvement of @Kevin Cruijssen's solution; I don't have enough reputation for a comment.

05AB1E, 14 13 12 bytes, supports inputs > 235959
твR₅0šR12*‹P

Try it online!
тв             # convert input to base 100
  R            # reverse
   ₅           # 255
    0š         # convert to list and prepend 0: [0, 2, 5, 5]
      R        # reverse: [5, 5, 2, 0]
       12*     # times 12: [60, 60, 24, 0]
          ‹    # a < b (vectorizes
           P   # product

You beat me to it. I was just working on an answer. Had already prepared a test suite, so feel free to edit it in. XD

You can shorten the [60, 60, 24] for 11 bytes

@ExpiredData Although smart, the unprintable isn't part of 05AB1E's codepage, so in that case the entire program should be counted in a different codepage (i.e. UTF-8), and it would only increase. Still a good way to save bytes if the 24 was $\geq32$, though.

@KevinCruijssen why doesn't TIO count it as extra then, like it does with mathematica when using the extended symbols?

@KevinCruijssen here's 12 then

@ExpiredData Nice 12-byter alternative! :) And TIO only shows UTF-8 encoding correct a.f.a.i.k., for languages which uses UTF-8 like your mentioned Mathematica or Java for example. Any codegolf language with a custom code-page on TIO simply uses the 'SBCS encoding' (which basically means each character is counted as a single byte). I forgot what SBCS stands for, but I thought it was something along the lines of Single Byte Code Source (not sure about the CS part..)

6 bytes I liked this challenge more when inputs above 235959 were allowed as input..

@KevinCruijssen probably CS stands for character set?

Perl 5 -p, 27 22 18 bytes
Saved 4 bytes when @NahuelFouilleul pointed out that it doesn't need to be a look-ahead in the regex
$_=!/[6-9].(..)*$/

Try it online!
Since the input is guaranteed to be less than 236000, the hours can be ignored as they will always be valid.  This pattern match checks if there is a 6, 7, 8, or 9 in the tens digit of the minutes or seconds.  The match is then negated to get truthy for valid dates and falsy for invalid ones.

what about 18 bytes

Jelly, 13 7 bytes
bȷ2<60Ạ

Try it online!
A monadic link taking an integer and returning 1 for true and 0 for false.
Thanks to @KevinCruijsen for saving 6 bytes!

I don't know Jelly, but based on that “<<ð‘ (which I think is [60,60,24]?) you can probably save some bytes with a different approach: convert to base 100 as list, get the maximum, check if it's smaller than 60. (In pseudo-code: max(hh,mm,ss)<60.) The range is guaranteed to be $[0,235959]$.

Posted a couple of different sevens too.

LibreOffice Calc, 43 bytes
=MAX(MOD(A1,100),MOD(A1/100,100),A1/4e3)<60

Basically a blatant rip-off respectful port of @RGS excellent Python answer so go and upvote them. Only posted as I have not seen a LibreOffice Calc answer on here before and I was messing about while calculating my tax return this evening (code golf is much more fun). Screenshot of some test cases below.

Retina 0.8.2, 12 bytes
[6-9].(..)?$

Try it online! Link includes test cases. Accepts input from 0 to 239999 and outputs 0 for times, 1 for non-times. Explanation: Simply checks whether the second or fourth last digit is greater than 5.

J, 32 26 23 16 bytes
60*/ .>100#.inv]

Try it online!
-16 bytes (!!) thanks to Adam.  This new solution uses the approach from his APL answer so be sure to upvote that.
Convert the input to base 100, check that all digits are less than 60.
Note the most significant digit is guaranteed to be less than 24 by the allowed inputs.

Can you not combine [:*/ and > into */ .> ?

No need to stringify. You can take the argument as a string.

Re: your first comment, you can indeed and it's cool observation but doesn't change the byte count.  I'll change per your 2nd comment in a sec.

26: 24 60 60*/ .>_3{.100&#.inv Try it online!

Very nice, I like that much better than my original approach.  Thanks Adam!

You're welcome. It is simply a port of mine.

23: 24 60 60*/ .>(3$100)&#: Try it online!

16: 60*/ .>100#.inv] Try it online!

Ah because the input constraint gives us the 24, nice!

Java 8, 45 43 bytes
n->n%100<60&n%1e4/100<60&n%1e6/1e4<24&n<1e6

Improved by @Joja's Java answer by removing the divisions, so make sure to upvote him/her as well!
Try it online.
Explanation:
n->              // Method with integer parameter and boolean return-type
  n%100<60       //  Check whether the seconds are smaller than 60
  &n%1e4/100<60  //  and the minutes are smaller than 60
  &n%1e6/1e4<24  //  and the hours are smaller than 24
  &n<1e6         //  and the entire number is smaller than 1,000,000

Charcoal, 11 bytes
‹⌈⍘Ｎ⭆¹⁰⁰℅ι<

Try it online! Link is to verbose version of code. Accepts input from 0 to 239999 and outputs a Charcoal boolean, - for times, no output for non-times. Explanation:
     ¹⁰⁰    Literal 100
    ⭆       Map over implicit range and join
         ι  Current index
        ℅   Unicode character with that ordinal
   Ｎ        Input as a number
  ⍘         Convert to string using string as base
 ⌈          Character with highest ordinal
‹           Is less than
          < Character with ordinal 60
            Implicitly print

BaseString always returns 0 for a value of 0 (bug?) but fortunately this is still less than <.
Alternative solution, also 11 bytes:
⌈⍘Ｎ⭆¹⁰⁰›ι⁵⁹

Try it online! Link is to verbose version of code. Accepts input from 0 to 239999 and outputs 0 for times, 1 for non-times. Explanation:
    ¹⁰⁰     Literal 100
   ⭆        Map over implicit range and join
        ι   Current index
       ›    Greater than
         ⁵⁹ Literal 59
  Ｎ         Input as a number
 ⍘          Convert to a string using string as base
⌈           Maximum
            Implicitly print

BaseString doesn't require the string base to have distinct characters, so this string just has 60 0s and 40 1s.
Unfortunately taking the base numerically returns an empty list for an input of zero, which takes an extra three bytes to handle, pushing the byte count above 11. But fortunately I can substitute an acceptable non-zero number in only two bytes, so another 11-byte alternative is possible:
›⁶⁰⌈↨∨Ｎχ¹⁰⁰

Try it online! Link is to verbose version of code. Accepts input from 0 to 239999 and outputs a Charcoal boolean, - for times, no output for non-times. Explanation:
 ⁶⁰         Literal 60
›           Is greater than
      Ｎ     Input as a number
     ∨      Logical Or
       χ    Predefined variable `10`
    ↨   ¹⁰⁰ Convert to base 100 as a list
   ⌈        Maximum
            Implicitly print

Turing Machine Code, 336 548 bytes
Prints 't' for true and 'f' for false.
0 * * r !
! * * r "
! _ _ l b
b * _ l t
" * * r £
" _ _ l c
c * * l c
c _ _ r 4
£ * * r $
£ _ _ l d
d * * l d
d _ _ r 3
$ * * r ^
$ _ _ l e
e * * l e
e _ _ r 2
^ * * r &
^ _ _ l g
g * * l g
g _ _ r 1
& * * l &
& _ _ l O
O 1 1 r a
O 2 2 r 1
O * * * f
a * * r 2
1 0 0 r 2
1 1 1 r 2
1 2 2 r 2
1 3 3 r 2
1 * * * f
2 0 0 r 3
2 1 1 r 3
2 2 2 r 3
2 3 3 r 3
2 4 4 r 3
2 5 5 r 3
2 * * * f
3 * * r 4
4 0 0 r t
4 1 1 r t
4 2 2 r t
4 3 3 r t
4 4 4 r t
4 5 5 r t
4 * * * f
f * * l f
f _ _ r n
n * _ r n
n _ f * halt
t * * l t
t _ _ r y
y * _ r y
y _ t r halt

Try it online!
Added a chunk of bytes thanks to @Laikoni for spotting my misread of the question.

Looks like this fails for hours >2, e.g. 30000 returns f though it is a valid time.

Upon closer inspection, it looks like you require leading zeros, as e.g. 3 fails but 000003 does not. However, the point of the challenge is that no leading zeros are given.

@Laikoni, Thanks, I read through that too quickly and thought it simply meant I had to handle leading zeros, not actually imply them myself in the input myself. I'll sort it out....

As friendly competition, I also gave it a shot: https://codegolf.stackexchange.com/a/200153/56433. To keep the byte count down, I took a rather liberal approach to indicate true or false, though this is usually fine for challenge on this site.

K (ngn/k), 14 9 bytes
-5 bytes thanks to ngn
*/60>100\

Try it online!
Based on Adám's APL solution and Kevin Cruijssen's suggestion.

0= -> ~ and rm { x}

@ngn Thanks, I always seem to forget about negation.

negation could be pushed to the comparison: */60>100\  turning + into * (or ∨ into ∧) like in de morgan's laws

@ngn Yes, it's very useful!

Japt, 7 bytes
ìL e<60

Try it

I love an answer in Japt! I've just noticed that this will fail on anything where the hour is between 24 and 59.

x86-16, IBM PC DOS, 46  44  39 bytes
00000000: d1ee 8a0c ba30 4c88 5401 03f1 4ed1 e9fd  .....0L.T...N...
00000010: b303 ad86 e0d5 0a4b 7502 b628 3ac6 7d02  .......Ku..(:.}.
00000020: e2f0 d6b4 4ccd 21                        ....L.!

Build and test ISTIME.COM with xxd -r.
Unassembled listing:
D1 EE       SHR  SI, 1              ; SI = 80H
8A 0C       MOV  CL, BYTE PTR[SI]   ; CX = input length
BA 4C30     MOV  DX, 4C30H          ; DH = 60+16, DL = '0'
88 54 01    MOV  BYTE PTR[SI+1], DL ; 'zero' pad byte to the left of input
03 F1       ADD  SI, CX             ; SI to end of input string
4E          DEC  SI                 ; remove leading space from length
D1 E9       SHR  CX, 1              ; CX = CX / 2
FD          STD                     ; read direction downward
B3 03       MOV  BL, 3              ; counter to test if third iteration (meaning hours)
        LOD_LOOP:
AD          LODSW                   ; AX = [SI], SI = SI - 2
86 E0       XCHG AH, AL             ; endian convert
D5 0A       AAD                     ; binary convert
4B          DEC  BX                 ; decrement count
75 02       JNZ  COMP               ; if not third time through, go compare
B6 28       MOV  DH, 40             ; if third, set test to 24+16
        COMP:
3A C6       CMP  AL, DH             ; is number less than DL?
7D 02       JGE  NOT_VALID          ; if not, it's invalid
E2 F0       LOOP LOD_LOOP           ; otherwise keep looping
        NOT_VALID:
D6          SALC                    ; Set AL on Carry
B4 4C       MOV  AH, 4CH            ; return to DOS with errorlevel in AL
CD 21       INT  21H                ; call DOS API

A standalone PC DOS executable.  Input via command line, output DOS exit code (errorlevel) 255 if Truthy 0 if Falsy.
I/O:
Truthy:

Falsy:

Thanks to @PeterCordes for:

-2 bytes use DOS exit code for Truthy/Falsy result
-3 bytes eliminate ASCII conversion before AAD

Isn't [SI+1] (81h) the first byte of the arg string that you're overwriting?  I would have thought you'd want to store to [si] and just replace the length byte with '0' padding.

@PeterCordes [80h] is the length byte and [81h] is the char (can only be a space (20H) or a forward slash) between the command invocation and the start of the command line argument string that starts at [82h].

Ah, https://cs.lmu.edu/~ray/notes/x86assembly/ and How to pass/retrieve DOS command-line parameters in a 16-bit assembly program? weren't clear about that.  Makes sense now, I'd forgotten that DOS allowed a non-whitespace separator between command and args.

Yes, it's quite annoying really because that leading space is counted in the length byte, so you pretty much always have to decrement that before you can use it.

You're spending a bunch of bytes to check that hours <= 24.  The problem statement in the question guarantees that the max integer is 23... so you can make a version that only solves that simpler problem.  Also, I think your code will accept repeated hours pairs, like 23230000, so not arbitrary integer.  You could just check the tens digits (AH) for being <= '5' in the loop, instead of aad those bytes into a binary integer.  (And BTW, I think you can skip the sub ax, '00' before AAD: 10*0x30 + 0x30 = 0x210, so you just need to check that the AAD result in AL is < 60+16 or 24+16).

Can you use a non-zero exit status instead of printing a '0/1' to save bytes?  At least the ret could go.

@PeterCordes yeah, I know I could shave off a few bytes not making it callable and not a standalone DOS .com, just return a ZF or CF.  What stopped me was having to refactor everything when I couldn't count on being able to overwrite input string pointer - 1 with the zero pad.  I think the only way to return an exit code is to use INT 21H / AH=4CH (a lot more bytes).  Give me a bit to digest your previous post and see what we can squeeze out!

I didn't mean a function, I meant a DOS program that exits with int 21h/ah=4Ch with an exit status of AL = 0 or -1 (from salc = Set AL from Carry - a 1-byte (undocumented) instruction that's like sbb al,al without writing flags).  That should save 2 bytes net: drop the ret and turn the 2-byte adc into 1-byte salc.  Code-golf answers don't even have to be fully portable, and salc works in 16 and 32-bit mode on at least every Intel CPU including current ones.

@PeterCordes brilliant idea eliminating the ASCII conversion before AAD in this case!  That never would have occurred to me that it would work in this case!  I've changed it to return a DOS exit code instead of output to console. So odd that SALC would be left in all chips and not documented, wonder why? Thanks as always!

@PeterCordes you said the code will accept repeated hour pairs.  Is that a problem?  Rules state input will be only in the range of 0..235959 so shouldn't have to handle 23230000 right?

re: 23232323: it's not a problem per-se, but if you're spending extra bytes to apply a tight bound for hours, it might not make sense if you don't catch other too-high-number problems.  (You could look at it as formatting error vs. semantic error, though.)  Re: undocumented opcodes: perhaps an extremely conservative approach to maintaining backwards compat with possible existing binaries?  That was Agner Fog's guess in his Stop the Instruction Set War article.

Red, 63 bytes
f: func[n][either n % 100 > 59[return 0][if n > 1[f n / 100]]1]

Try it online!
Of course the recursive function with integers is much shorter than the below version that works on strings.
Red, 139 130 115 bytes
func[s][s: pad/left/with s 6 #"0"
not any collect[foreach n collect[loop 3[keep to 1 take/part s 2]][keep n > 60]]]

Try it online!

I don't know Red, but you can probably save some bytes by checking if the maximum after the [s: pad/left/with s 6 #"0" t: collect[loop 3[keep to 1 take/part s 2]]] is smaller than 60.

@Kevin Cruijssen Red's max function takes exactly 2 arguments and doesn't work on lists.

Ah ok. Yeah, Java is the same unfortunately. It would only increase the byte-count instead of decreasing it. :)

MathGolf, 18 9 bytes
◄+░2/i╙╟<

Try it online.
Explanation:
◄+        # Add builtin 10,000,000 to the (implicit) input-integer
  ░       # Convert it to a string
   2/     # Split it into parts of size 2: [10,hh,mm,ss]
     i    # Convert each to an integer
      ╙   # Pop and push the maximum
       ╟< # And check if it's smaller than builtin 60
          # (after which the entire stack joined together is output implicitly)

JavaScript (V8), 50 48 46 bytes
-2 bytes each thanks to @kanine and @l4m2
a=>a.padStart(6,0).match(/../g).every(x=>x<60)

Try it online!

Doesn't this fail for e.g. 60000?

Yeah you're right @Neil thanks

you can replace the quoted '0' to just 0

Doesn't this fail for, say, 240000, as 24 isn't a valid hour?

@RedwolfPrograms no since the domain is 0 - 239999.. so an input of 240000 is undefined for the challenge

Why do you need \d? It's anyway an integer, every char is \d

Bash, 33 32 bytes
p=%100\<60;echo $[$1$p&$1/100$p]

Try it online!
Input is passed as an argument.
Output is 0 (falsey) or 1 (truthy).
(I've deleted an earlier 45-byte version that used egrep.]

Zsh, 28 bytes
e=%100/60;(($1$e||$1/100$e))

Try it online!
Returns via exit code.
Since $parameters are expanded before ((arithmetic)), $e expands to %100/60 before arithmetic is done.
There are 2 other 28 byte solutions I found as well, albeit not as interesting:
((h=100,$1%h/60||$1/h%h/60))

(($1%100/60||$1/100%100/60))

T-SQL, 42 41 bytes
Saved 1 byte thanks to @Neil
Supports all positive integer input
Returns 1 for true, 0 for false
DECLARE @ INT=235959

PRINT-1/~(@/240000+@/100%100/60+@%100/60)

Does @/240000 not work?

@Neil it sure would. I wonder how I missed it. Thanks a lot much appreciated.

[JavaScript (Node.js)], 26 bytes
f=>!/[6-9].(..)?$/.test(f)

Simple Javascript Regular Expression
JavaScript (Node.js) – Try It Online

You've got a stray space after the >, I think you can use . instead of \d, and you can probably simplify the condition, e.g. by using test.

Thanks @Neil, I used test, but changed the logic.

You don't use recursive so you can omit t=

Turing Machine Simulator, 299 272 269  bytes
0 _ _ l 1
0 * * r 0
1 * _ l 2
* _ t * t
2 6 f * f
2 7 f * f
2 8 f * f
2 9 f * f
2 * _ l 3
3 * _ l 4
4 6 f * f
4 7 f * f
4 8 f * f
4 9 f * f
4 * _ l 5
5 0 _ l 6
5 1 _ l 6
5 2 _ l 6
5 3 _ l 6
5 * _ l 7
6 _ t * t
6 1 t * t
6 2 t * t
6 * f * f
7 _ * * t
7 1 _ * t
7 * f * f

Run in Turing Machine Simulator.
Halts with t on the tape for true inputs and a prefix of the input and f for false inputs.

Yeah I tend to pontificate a bit with my true/false outputs. This is nice, very succinct. I only too briefly considered the idea of starting at the end of the input.

VBA, 177 bytes
Sub a()
x=1: i=""
If Len(i)<6 Then Do Until Len(i)=6: i="0"&i: Loop
s = Right(i, 2): m = Left(Right(i,4),2): h = Left(i,2)
If s>59 Or m>59 Or h>23 Then x=0
Debug.Print s
End Sub

Works for values above 235959, assigns x to output 1 or 0 with input as i

You can replace the If and Do Until with Do While which will check the condition before the loop even starts. I don't specifically know VBA but does it not have some sort of function declaration? Normally answers are required to be either functions or full programs that include I/O (Input, Print etc.)

It does have function declaration, yeah. I'll edit my answer to follow the rules. Thank you!

Hi there and Welcome to PPCG! I recommend that you take a look at our Tips for Golfing in VBA for some hints on how to get your code even shorter, and for some general rules on input and out as they relate to VBA (VBA is weird to the rules are weird)

As it stands, unfortunately, your response is not quite valids, as it does not properly take input (see rules above), but it is functionally correct.

If you use our tips and some tricks, like removing whitespace, using integer division, abbreviate the print statement, use Right("000000"&i,6) and use the mid function instead of the left and right calls for calculating m, you can get your solution way down in size. With vanilla VBA, you can get down to 85 bytes w/ Sub a(i):v=Right("000000"&i,6):Debug.?v\1E4<24*(Mid(v,3,2)<60)*(v Mod 100<60):End Sub and if you use an Excel VBA immediate window function you can get down to 65 as v=Right("000000"&[A1],6):?v\1E4<24*(Mid(v,3,2)<60)*(v Mod 100<60)

Wolfram Language (Mathematica), 76 bytes
supports any number
!FreeQ[FromDigits/@Join@@@IntegerDigits/@Tuples[Range/@{24,6,10,6,10}-1],#]&

Try it online!

T-SQL, 64 bytes
SELECT*FROM t WHERE 60>LEFT(RIGHT('000'+v,4),2)AND 60>RIGHT(v,2)

Input is taken from pre-existing table t with varchar field v, per our input standards.
Outputs 1 row (with the original value) for "true", and 0 rows for "false".
Accepts only values in the specified range (0 to 235959), so doesn't validate the first 2 digits.

Python 3, 90 85 bytes
lambda t:{t}&s
s={0}
import time
while len(s)<86400:s|={int(time.strftime("%H%M%S"))}

Try it online!
The idea is to simply create a set of all valid time (as int), then check if the given number is in the set. The set is created by repeatedly adding the current time to the set until all 86400 distinct values are added.
Returns: non-empty set if t is valid time, otherwise empty set.

JavaScript (ES6),  27 26  21 bytes
Takes input as an integer in hhmmss format. Returns \$0\$ or \$1\$.
n=>n%100<60&n%1e4<6e3

Try it online!
How?
n=>n%100<60&n%10000<6000

is just as long as:
n=>n%100<60&n/100%100<60

But from there we can use the scientific notation to save 3 bytes:
n%10000<6000
n%1e4<6e3

JavaScript (Babel Node), 71 52 bytes
t=i=>{[,,m,,s]=(i+'').padStart(6,0);return m<6&&s<6}

Try it online!

48 bytes

PHP, 60 bytes
<?=preg_match('#\d+([01]\d|2[0-3])([0-5]\d){2}#',$argn+1e6);

Try it online!
Basically regex and not much golfable, but fun. Inputs above 235959 are indeterminate.

Wolfram Language (Mathematica), 44 bytes
#&@@TimeObject[x=IntegerDigits[#,100,3]]==x&

Try it online!
Works for values above 235959!
The built-in TimeObject command can automatically round up each element!
Explanation
x=IntegerDigits[#,100,3]

Split input in base-100 (i.e. in chunks of 2 digits), padded to length 3. Store that list in x.
TimeObject[...]

Convert that to a TimeObject.
#&@@...

Extract the rounded string
...==x

Check if that is equal to x (i.e. nothing rounded up).
The boring version, 28 bytes
Max@IntegerDigits[#,100]<60&

Try it online!

C (gcc), 30 bytes
f(n){n=n%100<60&n/100%100<60;}

Doesn't check hours.
Try it online!
C (gcc), 39 bytes
f(n){n=n%100<60&n/100%100<60&n/1e4<24;}

Checks hours.
Try it online!

MUMPS, 74 70 64 40 bytes
t(t) s l=$l(t)-5 f f=l:2:7 q:$e(t,f,f+1)>$s(f-l:59,1:23)
 q f>5

Ah, I didn't consider that you only need to handle values up to 239999. That drops it from 64 to 40.
t(t) f f=$l(t)-3:2:7 q:$e(t,f)>5
 q f>5

Jelly, 7 bytes
ṚHÐoṀ<6

Try it online!
How?
ṚHÐoṀ<6 - Link: integer, n                 e.g.  236059
Ṛ       - (implicit digits of n) reversed        [9  , 5  , 0  , 6  , 3  , 2  ]
  Ðo    - apply to odd indices:
 H      -   halve                                [4.5, 5  , 0  , 6  , 1.5, 2  ]
    Ṁ   - maximum                                6
      6 - six                                    6
     <  - less than?                             0

Alternative 7:
ṚḊm2Ṁ<6 - reverse, dequeue, modulo-2-slice, maximum, less than 6?

PowerShell, 56 bytes
param($a)!(1-in(0..2|%{$a%100-ge60;$a/=100})-or$a-ge.24)

Try it online.

ArnoldC, 676 bytes
IT'S SHOWTIME
HEY CHRISTMAS TREE n
YOU SET US UP 0
GET YOUR ASS TO MARS n
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
HEY CHRISTMAS TREE s
YOU SET US UP 0
GET TO THE CHOPPER s
HERE IS MY INVITATION n
I LET HIM GO 100
ENOUGH TALK
HEY CHRISTMAS TREE m
YOU SET US UP 0
GET TO THE CHOPPER m
HERE IS MY INVITATION n
HE HAD TO SPLIT 100
I LET HIM GO 100
ENOUGH TALK
HEY CHRISTMAS TREE o
YOU SET US UP 0
GET TO THE CHOPPER o
HERE IS MY INVITATION 60
LET OFF SOME STEAM BENNET m
ENOUGH TALK
GET TO THE CHOPPER o
HERE IS MY INVITATION 60
LET OFF SOME STEAM BENNET s
KNOCK KNOCK o
ENOUGH TALK
TALK TO THE HAND o
YOU HAVE BEEN TERMINATED

Try it online!

PowerShell, 25 bytes
port of Neil's solution
$args-match'[6-9].(..)?$'

Try it online!
Accepts input from 0 to 239999 and outputs $null for times and the input for non-times.

Perl 5, 42 39 +1 (-p) = 40 bytes
$_=0|!($_%100>59|$_/1e4%10>5|$_/1e5>23)

Saved 3 bytes by changing to exponent notation (1000 => 1e4)
Try it online!

05AB1E, 6 bytes
твà60‹

Only works for the range \$[0, 235959]\$.
Try it online or verify all test cases.
Explanation:
тв      # Convert the (implicit) input-integer to base-100 as list
  à     # Pop and push the maximum
   60‹  # Check if it's smaller than 60
        # (after which the result is output implicitly)

PowerShell, 40 bytes
param($n)($n%100-lt60)-and($n%1e4-lt6e3)

Try it online!

@mazzy I could also use -and. Thanks for the reminder

also you can use * instead -and in this case. Try it online!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Impress Donald Knuth by counting polyominoes on the hyperbolic plane
This challenge is inspired by a talk about Schläfli symbols, etc that I gave in a Geometry seminar. While I was putting together this challenge, I saw that Donald Knuth himself was interested in (some subset of) this problem. In October 2016, he commented on a related OEIS sequence:

If [the OEIS author] is wrong about the hyperbolic {4,5} pentominoes, the next number is probably mistaken too. I don't have [time] right now to investigate further.

Successful completion of this challenge will have you investigating something that Donald Knuth might have investigated if only he had more time, and will result in new additions (and perhaps a rare correction) to the On-Line Encyclopedia of Integer Sequences.

Challenge
This code-golf challenge will have you create a function that counts "free polyforms" on the hyperbolic plane. In particular, you will write a function that takes three positive integer parameters p, q, and n and counts the number of \$n\$-cell "free polyforms" on the tiling of the hyperbolic plane given by the Schläfli symbol \$\{p,q\}\$.
Shortest code wins.

Definitions
The Schläfli symbol \$\{p,q\}\$ describes a tiling of the hyperbolic plane by \$p\$-gons, where each vertex touches exactly \$q\$ of the polygons. As an example, see the Wikipedia page for the \$\{4,5\}\$ tiling that Donald references above.
A free polyform is a collection of regular polygons that meet at their edges, counted up to rotation and reflection.

Input
You can assume that the values of p and q which define the tiling indeed describe an actual tiling of the hyperbolic plane. This means that \$p \geq 3\$, and

when \$p = 3\$, \$q \geq 7\$,
when \$p = 4\$, \$q \geq 5\$,
when \$p = 5\$, \$q \geq 4\$,
when \$p = 6\$, \$q \geq 4\$, and
when \$p \geq 7\$, \$q \geq 3\$.

Data
OEIS sequence A119611 claims that f(4,5,n) = A119611(n), but Donald Knuth disputes the reasoning for the value of \$A119611(5)\$. (When I counted by hand, I got Knuth's answer, and I've included it in the table below.)

\$p\$
\$q\$
\$n\$
\$f(p,q,n)\$

3
7
1
1

3
7
2
1

3
7
3
1

3
7
4
3

3
7
5
4

3
7
6
12

3
7
7
27

3
9
8
82

4
5
3
2

4
5
4
5

4
5
5
16

6
4
3
3

7
3
1
1

7
3
2
1

7
3
3
3

8
3
3
4

9
3
3
4

Note: these values are computed by hand, so let me know if you suspect any mistakes.
Final notes
The output of this program will result in quite a lot of new, interesting sequences for the OEIS. You are of course free to author any such sequences—but if you're not interested, I'll add the values you compute to the Encylopedia with a link to your answer.

Is this [tag:code-golf] or [tag:code-challenge]?

It's a code-golf challenge: the shortest code wins. But I expect that the shortest solution might be quite long, as in this answer to a previous code-golf challenge.

Can you provide a reference implementation or some pseudocode?

@S.S.Anne, I don't know of any implementation of this problem, but I do know of an implementation of a non-uniform tiling of the Euclidean plane and many implementions of f(4,4,n) (which is not a part of this challenge), and an implementation of f(3,6,n) and f(6,3,n) (also not parts of this challenge). I expect that a modification of this code may do the trick.

@S.S.Anne this may also be interesting to you: $f(3,N,n) = A000207(n)$ for sufficiently large $N$ (depending on $n$).

I don't know this stuff so I probably won't be able to do it. Can you maybe tell how you did it by hand?

Regarding the bounty: we generally discourage tie-breaking by shortest code.

Monomino. Do do do-do-do. ♫♪

There's nothing very wrong with p=2 (which you could visualise as segments of a beachball, or pizza slices on an infinite plane with a single vertex at infinity) and/or q=2 (which you could visualise as a north and south hemisphere, with the equator divided into p edges). The infinite plane for p=2 with pizza slices could be the hyperbolic plane, I suppose. But the finite cases are fiddly to include, so I'm glad you've excluded them.

GAP and its kbmag package, 711 682 658 bytes
Note that the kbmag package consists not only of GAP code, it contains C programs that have to be compiled (see the package's README file).
LoadPackage("kbmag");I:=function(p,q,n)local F,H,R,r,s,x,c;F:=FreeGroup(2);s:=F.1;r:=F.2;R:=KBMAGRewritingSystem(F/[s^2,r^p,(s*r)^q]);AutomaticStructure(R);H:=SubgroupOfKBMAGRewritingSystem(R,[r]);AutomaticStructureOnCosets(R,H);x:=w->ReducedCosetRepresentative(R,H,w);c:=function(n,U,S,P)local N,Q,Z;if n=0 then Z:=Set(U,t->Set(U,p->(p/t)));return 1/Size(SetX(Union(Z,Set(Z,Q->Set(Q,q->(MappedWord(q,[s,r],[s,r^-1]))))),[1..p],{Q,i}->Set(Q,q->x(q*r^i))));fi;if P=[]then return 0;fi;N:=P[1];Q:=P{[2..Size(P)]};Z:=Filtered(Set([1..p],i->x(s*r^i*N)),w->not w in S);return c(n,U,S,Q)+c(n-1,Union(U,[N]),Union(S,Z),Union(Q,Z));end;return c(n,[],[r/r],[r/r]);end;

This is the result of removing indentation and newlines from this version, and some inlining:
LoadPackage("kbmag");
I:=function(p,q,n)
  local F,G,H,R,r,s,x,c;
  F:=FreeGroup(2);
  s:=F.1;r:=F.2;
  G:=F/[s^2,r^p,(s*r)^q];
  R:=KBMAGRewritingSystem(G);
  AutomaticStructure(R);
  H:=SubgroupOfKBMAGRewritingSystem(R,[r]);
  AutomaticStructureOnCosets(R,H);
  x:=w->ReducedCosetRepresentative(R,H,w);
  c:=function(n,U,S,P)
    local N,Q,Z;
    if n=0 then
      Z:=Set(U,t->Set(U,p->(p/t)));
      Z:=Union(Z,Set(Z,Q->Set(Q,q->(MappedWord(q,[s,r],[s,r^-1])))));
      Z:=SetX(Z,[1..p],{Q,i}->Set(Q,q->x(q*r^i)));
      return 1/Size(Z);
    fi;
    if P=[]then return 0;fi;
    N:=P[1];Q:=P{[2..Size(P)]};
    Z:=Filtered(Set([1..p],i->x(s*r^i*N)),w->not w in S);
    return c(n,U,S,Q)+c(n-1,Union(U,[N]),Union(S,Z),Union(Q,Z));
  end;
  return c(n,[],[r/r],[r/r]);
end;

If the line containing {Q,i}-> doesn't work, your GAP is too old. You can then replace that line with:
Z:=SetX(Z,[1..p],function(Q,i)return Set(Q,q->x(q*r^i));end);

Several of the Set operations could be slightly faster List operations (the improved version at least uses that it is a set for even more golfing and a little speed compensation), but that would cost one byte each time.
And yes, Knuth's and your result is confirmed:
gap> Read("i.gap");
─────────────────────────────────────────────────────────────────────────────
Loading  kbmag 1.5.9 (Knuth-Bendix on Monoids and Automatic Groups)
by Derek Holt (https://homepages.warwick.ac.uk/staff/D.F.Holt/).
Homepage: https://gap-packages.github.io/kbmag
─────────────────────────────────────────────────────────────────────────────
gap> I(4,5,5);
16
gap> I(4,5,6);
55
gap> I(4,5,7);
224
gap> I(4,5,8);
978
gap> I(4,5,9);
4507
gap> I(4,5,10);
21430

The \$n=7\$ computation already takes several minutes. My computations also agree with the other results in the table.

Pretty awesome!

I'm blown away by this. Even if someone writes something faster for the current bounty, I'll make another one to give to you.

This appears to work for polyhedra and tilings of the plane too?

@PeterKagey Yes, since all the groups are automatic.

bc, 673 670 bytes
-3 bytes thanks to @ceilingcat
define y(){t[z=u[x[++n]=e]/p]=1;for(o=p;o--;){if(!u[a=z*p+o]){v(u[u[a]=c=s]=a);s+=p;v(c)}}}define j(e,i){return(e%p+p+i)%p+e/p*p}define v(e){auto l;for(l=j(e,b=1);y=u[e];++b){e=j(y,-1)};for(;y=u[l];++b){l=j(y,1)};if(b==q)v(u[u[l]=e]=l)}p=read();q=read();g=read();u[e=s=2*p]=p;y();e=p;for(y();e==p;){while(n-1){if(t[e/p]*!t[u[e]/p]){c=y();for(o=6;o-=2;){for(d=s;d--;){i[a=w=2]=f=u[d];if(t[d/p]*t[f/p]){i[b=1]=d;m[d/p]=m[f/p]=++r;for(z=0;w-z++;){for(f=i[z];f=j(f,o-3)!=i[z];a*=2){if(t[y=u[f]/p]){b+=a;if(m[y]<r){i[++w]=u[f];m[y]=r}}}};if(c<b)c=b}}};for(k[h]=c;k[o++]-c;){};if(o>h){++h;if(n<g){e=p;break};++l};t[u[e]/p]=0;--n};while(++e>s){t[u[e=x[n--]]/p]=0}}};l;if(g<3)1

Try it online!
This is a golfed version of the C code I'm about to post. Here, you have to supply the parameters (p, q and n) on standard input when bc is running. The code spits out lots of numbers while it calculates (because statements such as i+=1 are silent, but ++i is a value and is printed) -- the answer is the final number.
n<3 has to be handled as a special case. Infinite planar grids are handled OK (which gives us lots of test cases). Finite grids (the Platonic solids, but also p=2 and/or q=2) are not handled reliably.
Here we are counting "free" polyominoes, unique up to translation, rotation and reflection. If you had asked the same question but disallowing reflection, I could have saved a few bytes and even beaten Christian's excellent answer as it stands. (I don't know if that answer would be shorter for the not-free question.) Here's the not-free code:
Try it online! (655 652 bytes, answering a different question).
Here's the main code unwrapped:
 define y(){
 t[z=u[x[++n]=e]/p]=1;
 for(o=p; o--;){
  if(!u[a=z*p+o]){
   v(u[u[a]=c=s]=a);
   s+=p;
   v(c)
  }
 }
}
define j(e,i){
 return(e%p+p+i)%p+e/p*p
}
define v(e){
 auto l;
 for(l=j(e,b=1); y=u[e]; ++b){
  e=j(y,-1)
 };
 for(; y=u[l]; ++b){
  l=j(y,1)
 };
 if(b==q)v(u[u[l]=e]=l)
}
p=read();
q=read();
g=read();
u[e=s=2*p]=p;
y();
e=p;
for(y(); e==p;){
 while(n-1){
  if(t[e/p]*!t[u[e]/p]){
   c=y();
   for(o=6; o-=2;){
    for(d=s; d--;){
     i[a=w=2]=f=u[d];
     if(t[d/p]*t[f/p]){
      i[b=1]=d;
      m[d/p]=m[f/p]=++r;
      for(z=0; w-z++;){
       for(f=i[z]; f=j(f,o-3)!=i[z]; a*=2){
        if(t[y=u[f]/p]){
         b+=a;
         if(m[y]<r){
          i[++w]=u[f];
          m[y]=r
         }
        }
       }
      };
      if(c<b)c=b
     }
    }
   };
   for(k[h]=c; k[o++]-c;){
   };
   if(o>h){
    ++h;
    if(n<g){
     e=p;
     break
    };
    ++l
   };
   t[u[e]/p]=0;
   --n
  };
  while(++e>s){
   t[u[e=x[n--]]/p]=0
  }
 }
};
l;
if(g<3)1

C (gcc),  753 745 705 bytes
-8 bytes thanks to @ceilingcat
-40 bytes, @ceilingcat strikes again!
#define X[99999]
#define S o=p;F[z=N[O[++n]=e]/p]=1 W o--)N[a=z*p+o]||v(c,s+=p,v(N[N[a]=c=s]=a))
#define W;while(
#define T atoi(*++V)
long C X,a,b,c,p,q,o,N X,F X,s,O X,A,n,P,e,m X,Q X,d,f,j,w,z,r;I(e,i){return(e%p+p+i)%p+e/p*p;}v(e,l){l=I(e,b=1)W N[e])++b,e=I(N[e],-1)W N[l])l=I(N[l],1),++b;b-q||v(N[N[l]=e]=l);}main(M,V)int**V;{p=T;q=T;M=T;N[e=s=2*p]=S;e=S;G:e=p W~-n){if(F[e/p]&!F[N[e]/p]){S;c=0;o=4 W o){d=s W d--)if(F[d/p]&F[(Q[a=w=2]=j=N[d])/p]){Q[b=1]=d;m[d/p]=m[j/p]=++r;z=0 W w-z++){f=Q[z]W(f=I(f,o-3))-Q[z])j=N[f],F[j/p]&&m[b+=a,j/p]<r?Q[++w]=j,m[j/p]=r:0,a+=a;}c=c<b?b:c;}o-=2;}C[P]=c W C[o++]-c);if(o>P){++P;if(n<M)goto G;++A;}F[N[e]/p]=0;--n;}W++e>s)F[N[e=O[n--]]/p]=0;}printf("%d",M<3?:A);}

Try it online!
Parameters p, q and n are supplied as command-line arguments.
The array C[99999] contains a characteristic value for each polyomino found, of the specified size and all smaller (down to n=2). For p less than 7 or 8 or so, this is probably the limit on how far you can go up a sequence. For larger p, you might well run out of edges, for example in the array N[99999]. There is also a constraint that the characteristic values need (p-1)*n bits, and here we are using 63ish bits. If we stick to unambitious values of p, q and n, I could save a handful of bytes with int and 9999. If you exceed any of the limits, there is no error trapping.
Here's the code unwrapped, but it's still fairly dense:
#define X[99999]
#define S o=p;F[z=N[O[++n]=e]/p]=1;while(o--)N[a=z*p+o]||v(c,s+=p,v(N[N[a]=c=s]=a))
#define T atoi(*++V)
long C X,a,b,c,p,q,o,N X,F X,s,O X,A,n,P,e,m X,Q X,d,f,j,w,z,r;
I(e,i){
  return(e%p+p+i)%p+e/p*p;
}
v(e,l){
  l=I(e,b=1);
  while(N[e])++b,e=I(N[e],-1);
  while(N[l])l=I(N[l],1),++b;
  b-q||v(N[N[l]=e]=l);
}
main(M,V)int**V;
{
  p=T;
  q=T;
  M=T;
  N[e=s=2*p]=S;
  e=S;
G:e=p;
  while(~-n){
    if(F[e/p]&!F[N[e]/p]){
      S;
      c=0;
      o=4;
      while(o){
        d=s;
        while(d--)if(F[d/p]&F[(Q[a=w=2]=j=N[d])/p]){
          Q[b=1]=d;
          m[d/p]=m[j/p]=++r;
          z=0;
          while(w-z++){
            f=Q[z];
            while((f=I(f,o-3))-Q[z])
              j=N[f],F[j/p]&&m[b+=a,j/p]<r?Q[++w]=j,m[j/p]=r:0,a+=a;
          }
          c=c<b?b:c;
        }
        o-=2;
      }
      C[P]=c;
      while(C[o++]-c);
      if(o>P){
        ++P;
        if(n<M)goto G;
        ++A;
      }
      F[N[e]/p]=0;
      --n;
    }
   ;
    while(++e>s)F[N[e=O[n--]]/p]=0;
  }
  printf("%d",M<3?:A);
}

This post seems rather long already, so I'll link to TIO with a copy of ungolfed code with comments. The golfed code uses basically the same approach:
Try it online!
In the ungolfed code, if you supply p, q, and n, it will try the size-n problem, then size-(n+1) and so on until something breaks. If limits are exceeded, the program is meant to terminate with a message. You can supply a fourth parameter to cap n.
The ungolfed code should handle finite grids (Platonic solids, or p=2 and/or q=2).
If you want to look at the different question of counts up to translation and rotation only, compile the ungolfed code with -DNOTFREE.
The golfed code can be checked against existing planar values as well as the values in the question. For example:
p=4,q=4,    n=11: a000105(11)=17073
p=3,q=99999,n=13: a000207(13)=24834
p=6,q=3,    n=10: a000228(10)=30490
p=3,q=6,    n=14: a000577(14)=26166
p=4,q=99999,n=10: a005036(10)=32721
p=4,q=5,    n=10: a119611(10)=21430

Most of these run within TIO's timeout of 60s. In other sequences, such as a330659 {3,7}, the golfed code can replicate and extend the current known values in OEIS:
p=3,q=7,    n=10: a330659(10)=  637
p=3,q=7,    n=11: a330659(11)= 1870
p=3,q=7,    n=12: a330659(12)= 5797
p=3,q=7,    n=13: a330659(13)=17866
p=3,q=7,    n=14: a330659(14)=56237

The ungolfed code has more checks, uses more memory and runs quicker (because, for example, it uses a hash table rather than a flat array for storing characteristics), so I'll add to the OEIS using that code. For example, extending a330659 to n=19 takes around 1000 seconds:
p=3,q=7,    n=14: a330659(14)=56237
p=3,q=7,    n=15: a330659(15)=177573
p=3,q=7,    n=16: a330659(16)=566904
p=3,q=7,    n=17: a330659(17)=1818527
p=3,q=7,    n=18: a330659(18)=5874180
p=3,q=7,    n=19: a330659(19)=19065038

Suggest e+i instead of e%p+p+i


text:
Counting Distinct Real Roots of Low-Degree Polynomials
Challenge: I want to know about the real roots of polynomials. As a pure mathematician, I care about the existence of such roots, rather than their numeric values.
The challenge is to write the shortest program that takes a polynomial, of degree at most 4, and simply returns how many distinct real roots said polynomial has. Polynomials with degree 4 or less have the unique property that there exist closed forms (such as the quadratic formula), which give all their roots. You can google these forms or find some useful related information in the appendix.
Input: the coefficients of a polynomial. For simplicity, we shall only care about polynomials with integer coefficients.
You may input this as a list, get the coefficients one at a time, or use any other reasonable method. You may, for example, require polynomials of degree d to inputted as lists of length d+1.
You should specify how you convert a polynomial of degree at most 4 into a valid input.
Output: the number of distinct real roots of said polynomial. (meaning roots with multiplicity are only counted once)
You must output one of the integers 0,1,2,3,4 for valid polynomials, and trailing spaces are completely fine. (the special case of the polynomial, \$P(x) = 0\$, is discussed in the scoring section)
Examples: in these examples, we represent a polynomial, \$P\$, as a list L, where L[i] contains the coefficient of \$x^i\$ in \$P\$. (with index starting at 0)
\$P(x) = 1\$, input: [1], output: 0
\$P(x) = 1+2x\$, input: [1,2],  output: 1
\$P(x) = 1+x^2\$, input: [1,0,1], output: 0
\$P(x) = 1+x+x^2+x^3 = (x+1)(1+x^2)\$, input: [1,1,1,1], output: 1
\$P(x) = 2+3x+x^2 = (x+2)(x+1)\$, input: [2,3,1], output: 2
\$P(x) = 1-2x+x^2 = (x-1)^2\$, input: [1,-2,1], output: 1
Scoring:
-5 bytes if the polynomial, \$P(x) = 0\$, outputs a representation of infinity, such as: the infinity float in python, the Unicode symbol ∞, or a string that can be mathematically interpreted to evaluate to infinity, like "1/0". (otherwise, you don't need to handle this case)
Otherwise, shortest code wins. (however I am personally quite interested in seeing answers which don't rely on built-in root finders)
Appendix: Closed Forms
Starting with the basics:
Degree 0: \$P(x) = a\$, roots: none, (or all reals, if a = 0)
Degree 1: \$P(x) = ax+b\$, roots: \$x=-b/a\$
Degree 2: \$P(x) = ax^2+bx+c\$, roots: \$x = \frac{-b \pm \sqrt{b^2-4ac}}{2a}\$
Then, we have the harder ones. For these, it becomes quite verbose to state the closed forms. I've paraphrased some ways you can deduce the number of roots by considering discriminants, you may also seek to find the closed forms of the roots.
Degree 3: From Wikipedia. \$ P(x) = ax^3+bx^2+cx+d\$. We define the discriminant as \$\Delta = 18abcd -4b^3d+b^2d^2-4ac^3-27a^3d^2\$.
If \$\Delta > 0\$ then there are 3 distinct roots, if \$\Delta = 0\$, then there are two distinct real roots, otherwise then \$ \Delta < 0\$ and there is only one real root.
Degree 4: From Wikipedia.\$ P(x) = ax^4+bx^3+cx^2+dx+e\$. We define the discriminant as $$\begin{align}
\Delta\ =\ &256 a^3 e^3 - 192 a^2 b d e^2 - 128 a^2 c^2 e^2 + 144 a^2 c d^2 e - 27 a^2 d^4 \\
&+ 144 a b^2 c e^2 - 6 a b^2 d^2 e - 80 a b c^2 d e + 18 a b c d^3 + 16 a c^4 e \\
&- 4 a c^3 d^2 - 27 b^4 e^2 + 18 b^3 c d e - 4 b^3 d^3 - 4 b^2 c^3 e + b^2 c^2 d^2
\end{align}$$
If \$\Delta > 0\$ then there are two distinct real roots. Otherwise things get more complicated.
Defining \$P = 8ac - 3b^2\$, \$D = 64 a^3 e - 16 a^2 c^2 + 16 a b^2 c - 16 a^2 bd - 3 b^4\$, then if \$ \Delta < 0 \$ and \$ P < 0\$ and \$ D < 0 \$ then there are 4 distinct real roots. Otherwise, if \$ \Delta < 0\$, there are 2 distinct real roots.
Finally, if \$\Delta = 0\$, we define \$\Delta_0=c^2-3bd+12ae\$ and \$R= b^3+8da^2-4abc\$.
If \$D =0\$, then:

\$ P < 0\$ implies two distinct real roots
\$ P > 0\$ implies zero distinct real roots
\$P = 0\$ implies four distinct real roots

Else, if \$\Delta_0 = 0\$, then there are two distinct real roots.
Else, if \$P<0\$ and \$D <0\$ there are three distinct real roots.
Else, there are one real root.

Is it not possible for polys of degree 5?

@Anush The polynomial $x^5-x+1$ is an example of a polynomial with a root which cannot be expressed with radicals. (instead, we need hypergeometric functions) Since the roots no longer have a nice expression, we can't get an easy closed form, making considering higher degrees much less simple.

@Grimmy, yeah, I'll fix that.

OK but we could still ask them to find the number of roots right? They just can't do it via the radical root.

@Anush, I'm also interested in programs that don't use built-in functions.  To the best of my knowledge, this is only feasible with the restriction of degree, unless you use much deeper and complicated math formulas, or you repeat the premise of https://codegolf.stackexchange.com/questions/11694/find-real-roots-of-a-polynomial?rq=1.

@Anush On the other hand, finding rational roots of a polygon of integer coefficients is trivial for arbitrary degree.

I suggest you add an example with mixed (real and complex) roots, such as [1, 0, 3, 1], which has 1 real root and 2 complex roots.

@ZacharyHunter: if you are specifically interested in non-built-in solutions, maybe next time consider another challange than #codegolf, which more or less encourages us to use built-ins...

@Neil How is trivial?

@Anush https://en.m.wikipedia.org/wiki/Rational_root_theorem

For the record, "count the number of roots in an interval" is a task that does not require being able to write down the roots; Sturm's theorem is a bit technical to explain, but it is a simple algorithm to count the number of roots of a polynomial over an interval (or over the whole real line) (and this is used in the answers)

I'm wondering if a golfy approach here would be to evaluate the polynomial at a huge number of equally spaced points, and count the intervals where it crosses zero or nearly touches it. This would require a mesh size small enough to separate any two roots, and an epsilon where anything approaching that close to an axis must actually be multiple root touching it. I suspect something suitably small in the polynomial degree and coefficients will suffice, but don't now how to prove it.

JavaScript (Node.js),  285 ... 248  247 - 5 = 242 bytes
Fixed a bug and saved a couple of bytes by borrowing @Grimmy's method for the final count of the real roots
Expects the coefficients from highest to lowest.
This is an implementation of Sturm's theorem, and therefore works for any degree, which might be a bit overkill for this challenge.
p=>1/p[1]?(h=(A,[[c,...q],[...p]]=A,n=q.length)=>n?h([(g=i=>1/p[(j=i)+n]?g(i+1,q.map(v=>p[++j]-=v*p[i],p[i]/=c)):p.slice(-n).map(v=>-v))(0),...A]):A)([p.flatMap(v=>1/p[++i]?(p.length-i)*v:[],i=k=s=0),p]).map(p=>s+=Math.sign(k*(k=p[0])))|s:1/!!+p-1

Try it online!
How?
We first test whether the degree is \$0\$, which is an edge case:
p =>                   // p[] = polynomial coefficients
  1 / p[1] ?           // if p[1] is defined:
    ...                //   general case
  :                    // else:
    1 / !!+p - 1       //   return +Infinity if p[0] = 0, or 0 otherwise

For the general case, we use the recursive function \$h\$ to build the Sturm sequence of polynomials in reverse order \$[p_n,...,p_1,p_0]\$, where \$p_0\$ is the input and \$p_n\$ is of degree \$0\$.
The initial call to \$h\$ is performed with \$[q,p]\$ where \$q\$ is the derivative of \$p\$ computed as follows:
p.flatMap(v =>         // for each coefficient v in p[]:
  1 / p[++i] ?         //   increment i; if p[i] is defined:
    (p.length - i) * v //     multiply v by the exponent at this position - 1
  :                    //   else:
    [],                //     this is the constant term: discard it
  i = k = s = 0        //   start with i = 0 (k and s are used later)
)                      // end of flatMap()

Below is the definition of \$h\$:
h = (                  // h is a recursive function taking:
  A,                   //   A[] = current Sturm sequence, which is split into:
  [[c, ...q], [...p]]  //     c = 1st coefficient of the divisor
  = A,                 //     q[] = other coefficients of the divisor
                       //     p[] = copy of the dividend
  n = q.length         //   n = number of coefficients in q[]
) =>                   //
  n ?                  // if n is not equal to 0:
    h([g(0), ...A])    //   preprend a new polynomial to A[], using g (see below)
  :                    // else:
    A                  //   end of recursion: return A[]

Where \$g\$ computes the remainder of \$p/q\$, multiplied by \$-1\$:
g = i =>               // g is a recursive function taking a counter i
  1 / p[(j = i) + n] ? // copy i into j; if p[j + n] is defined:
    g(                 //   do a recursive call:
      i + 1,           //     with i + 1
      q.map(v =>       //     for each coefficient v in q[]:
        p[++j] -=      //       increment j; subtract from p[j]:
          v * p[i],    //         v multiplied by p[i]
        p[i] /= c      //       start by normalizing p[i], using c
      )                //     end of map()
    )                  //   end of recursive call
  :                    // else:
    p.slice(-n)        //   end of recursion: isolate the remainder
    .map(v => -v)      //   and invert all signs

Finally, we compute the number of real roots by applying the following code to the Sturm sequence:
.map(p =>              // for each polynomial p in the sequence:
  s += Math.sign(      //   add to s the sign of:
    k *                //     multiply the previous leading coefficient
    (k = p[0])         //     by the leading coefficient of p (and update k)
  )                    //   NB: k and s are initialized to 0 earlier in the code
) | s                  // end of map(); yield s

When roots fall together, suchs as in the last example ([1,-2,1]) in the question, your code counts them as separate solutions. So [1,-2,1] returns 2, but should return 1. Although +1 for implementing Sturm theorem!

@agtoever This is now fixed.

05AB1E, 39 bytes
gŠ¦ƶ‚íλ£¬/D₂0š*₂-2£δ*˜0š2ôO+(¦¦}€нüP.±O

Try it online!
05AB1E doesn't have a built-in to get the roots of a polynomial, so we use Sturm's theorem
g                   # length of the input (degree + 1)
 Š                  # push two more copies of the input
  ¦                 # drop the first coefficient
   ƶ                # multiply each coefficient by its 1-based index
                    # => this is the derivative of the input
    ‚               # pair the input with its derivative
     í              # reverse both, so the constant coeff is now last

λ£            }     # recursively compute the Sturm's sequence:
                    # (initially, a(n-2) = input and a(n-1) = derivative)
  ¬/                #  divide a(n-1) by its first element
    D               #  duplicate
     ₂              #  push a(n-2)
      0š            #  prepend a 0
        *           #  multiply
         ₂-         #  subtract a(n-2)
           2£       #  keep the first two coefficients
                    #  => this is the polynomial division -a(n-2) / a(n-1)
  δ*                #  double-vectorized multiplication
    ˜               #  flatten
     0š             #  prepend a 0
       2ô           #  split in groups of 2
         O          #  sum each group
          +         #  add a(n-2)
                    #  => this is the remainder
           (        #  negate
            ¦¦      #  drop the two leading zeroes

€н                  # keep only the highest-order coefficient of each polynom
  üP                # pairwise product
    .±              # sign of each
      O             # sum

Amazing! Could you explain how it works?

@ZacharyHunter explanation added.

Wolfram Language (Mathematica), 25 32 31 27 bytes
+7 bytes for bugfix
-4 bytes thanks to @JungHwanMin
Length@#&@@RootIntervals@#&

Try it online!

@JungHwanMin this was posted before as a comment.. and still fails for 2 + 3x + x^2.. I'll leave this comment up this time so nobody posts it again

Ah, right, it would be a vertical vector. This works, but is same length.

27 bytes, for real this time

Tr fails for cubic

Ok yeah thanks good point @JungHwanMin

Jelly, 12 bytes - 5 = 7
ÆrQṠṠƑ€SµİẸ?

A monadic link accepting a list of coefficients from highest degree to lowest which yields a number or the list [inf] if all the integers given were zero. As a full program prints the number or inf.
Try it online!
How?
ÆrQṠṠƑ€SµİẸ? - Link: list of coefficients
           ? - if...
          Ẹ  - ...condition: any?
        µ    - ...then: the monadic chain:
Ær           -   roots
  Q          -   de-duplicate
   Ṡ         -   sign if real; complex conjugate if complex (vectorises)
      €      -   for each:
     Ƒ       -     is invariant under?:
    Ṡ        -       sign if real; complex conjugate if complex
       S     -   sum
         İ   - ...else: inverse

Pari/GP, 8 bytes
Pari/GP has a built-in for this.
It takes an polynomial as input, e.g., 1-2*x+x^2.
polsturm

Try it online!

Python 3, 91 bytes
lambda c:sum(f.real==f for f in set(polyroots(c)))
from numpy.polynomial.polynomial import*

Try it online!
Had to include set() to take care of "double" roots. polyroots([1, -2, 1]) gives [1., 1.]...

R, 44 bytes
sum(!Im(unique(zapsmall(polyroot(scan())))))

Try it online!
zapsmall is necessary to deal with numerical imprecision, as otherwise e.g. 2 3 1 test case would fail.

Jelly, 9 13 - 5 = 8 bytes
Monadic link expecting list of coefficients from lowest to highest.
ÆrÆiṪÐḟQLµİẸ?

You can try it online! How it works:
Ær        Find the roots of the polynomial
  Æi       and split each root into [real part, imaginary part]
     Ðḟ   Filter the list, removing elements
    Ṫ      where the imaginary part is Truthy (i.e. other than 0)
       Q  Remove duplicates
        L  and return the length of that.

This is the main part. Then µİẸ? checks if there is any non-zero coefficient. If not, returns infinity. If there is, just run the previous program I described.
Borrowed the final four bytes µİẸ? from Jonathan Allan's Jelly answer, increasing my count by 4 but gaining the bonus -5, for a total of -1.