05AB1E, 3 bytes

3BZ

Try it online!

Explanation:

3B means convert to base 3. The Z means output the maximum, which is 1 (truthy) for inputs that do not have a 2 in their tenary representation and 2 (falsy) for inputs that have a 2 in their tenary representation.

This code shows which values form 1 to 81 give truthy outputs.

Regex (or Retina), 9 bytes

^[0268]*$

Try it online!

For any two different numbers composed of 0, 2, 6, 8 in decimal, at any digit position where they differ, their average has 1, 3, 4, 5, or 7, and thus does not satisfy the condition.

This condition includes asymptotically \$ 4^{log_{10}n} = n^{log_{10}4} \approx n^{0.602}\$ of the first \$n\$ numbers.

Re:direction, 12 bytes

+++>
v +>
 <

Try it online!

Outputs by exit code, 0 for False and 1 (by queue underflow) for True. (This is a bit dubious; it matches the usual convention for numbers in general, but is the opposite of the convention normally used for exit codes.)

The condition used is that the number consists only of 0s and 2s in ternary, which is another variation that also works. This program goes into an infinite loop on 0, which thankfully does not need to be handled.

The following notation will be used for the contents of the queue: a number means that many ►s, and | means one ▼. If the input number is N, the initial queue is N|.

The possibilities are as shown:

Электроника МК-52/МК-61, 20 bytes

X→П0 3 - Fx≥0 18 П→X0 3 ÷ K{x} Fx≠0 19 FBx K[x] 1 + X→П0 БП 01 1 С/П

or, in bytecode:

40 03 11 59 18 60 03 13 35 57 19 0F 34 01 10 40 51 01 01 50

Port of loopyWalt's Python answer.

The MK-52 and MK-61 were the most advanced Soviet programmable calculators to use keystroke programming (later models, like the MK-85 and MK-90, had a form of BASIC). Despite looking more like macros than "real" programs, the language is actually Turing-complete. Each instruction occupies 1 byte in memory. Code-golfing was in fact very popular with these calculators in the 80s, because one had to fit the program in 104 bytes – however, even quite complex games were written with this limitation.

Online emulator here. Turn on the calculator (switch labeled Вкл), paste the above bytecode into the text area on the right and click "Ввести в память" ("Write to memory"). Input number into calculator and press В/О, then С/П to run program. Outputs 1 for true and 0 for false (not exactly quickly though...)

BQN, 15 14 13 bytes

Edit: -1 byte thanks to Razetime

⌊´2-3|⊢⌊∘÷3⋆↕

Try it at BQN online REPL

             ↕      # range from 0...input-1
           3⋆       # get 3 to the power of those
        ⌊∘÷         # now use these to divide & floor (=integer division)
       ⊢            # the input
     3|             # get each one modulo 3
   2-               # subtract it from 2
 ⌊´                 # and find the minimum

The final 2>·⌈´ ⌊´2- part seems a bit clunky to me (although now improved a bit): I'd want to be able to do something like ¬2∊ (NOT is 2 a member of), but unfortunately this returns an array which doesn't seem to work as a boolean.

x86 32-bit machine code, 10 bytes

48 25 AA AA AA AA 0F 94 C0 C3

Try it online!

Uses the regparm(1) calling convention – argument in EAX, result in AL.

This implements a slightly different criterion from the one most other answers use: n-1 consists of only 0s and 1s in base 4. This still works, and barely satisfies the \$e(n) < n^2\$ condition; removing the subtraction of 1 would make it fail that condition.

This modified criterion is simple to implement, by checking whether the odd-position bits in n-1 are all zero.

In assembly:

f:
    dec eax
    and eax, 0xAAAAAAAA
    setz al
    ret

Python 2, 27 bytes

f=lambda n:n>n%3/2>-f(n/3) 

Try it online!

Swaps True and False.

Python 2, 29 bytes (@xnor)

f=lambda n:n<1or n%3<2*f(n/3)

Try it online!

Thanks to @Jonathan Allan for convincing me that @xnor's switching to A005836 (without its first element) is actually perfectly good.

Python 2, 31 bytes (@KevinCruijssen)

f=lambda n:n<2or n%3>0<f(n/3+1)

Attempt This Online!

Improved logic is inspired by @alephalpha's PARI/GP answer. Could save another two bytes by allowing any nonzero value for True.

Python, 33 bytes

f=lambda n:n<2or n%3and f(n//3+1)

Attempt This Online!

Uses the base 3 characterisation at OEIS. Returns 0 and True.

Whitespace, 110 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][N
S S N
_Create_Label_FUNC][S N
S _Duplicate_input][S S S T S N
_Push_2][T  S S T   _Subtract][N
T   T   T   N
_If_negative_Jump_to_Label_TRUTHY][S N
S _Duplicate_input][S S S T T   N
_Push_3][T  S T T   _Modulo][S S S N
_Push_0][S N
T   _Swap_top_two][T    S S T   _Subtract][N
T   T   S N
_If_negative_Jump_to_label_CONTINUE][N
N
N
_Exit_Program][N
S S S N
_Create_Label_CONTINUE][S S S T T   N
_Push_3][T  S T S _Integer_divide][S S S T  N
_Push_1][T  S S S _Add][N
S N
N
_Jump_to_Label_FUNC][N
S S T   N
_Create_Label_TRUTHY][S S S T   N
_Push_1][T  N
S T _Print_1_as_number]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Port of @loopyWalt's Python answer.

Whitespace doesn't have any booleans, but this will output 1 for truthy and nothing for falsey (could also output 0 for falsey at the cost of 8 additional bytes).

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer n = STDIN as number
FUNC:
  If(n-2 is negative):
    Jump to TRUTHY
  If(0-(n%3-1) is negative):
    Jump to CONTINUE
  Exit program (falsey result)

CONTINUE:
  n = n//3+1
  Jump to FUNC

TRUTHY:
  Print 1 as number to STDOUT
  (implicitly stop the program with an error stating 'no exit is defined')

Ruby, 23 bytes

->n{(n-1).to_s(3)!~/2/}

Try it online!

Factor + math.unicode, 23 bytes

[ 1 - 3 >base "10"⊂ ]

Try it online!

Based on @allxy's Vyxal/Jelly answers. Subtract 1 from the input, convert it to base 3, but instead of checking whether each digit is less than two, check whether the result is a subset of "10" since that's shorter in Factor.

Retina 0.8.2, 26 bytes

.+
$*
+`^1?(1*)\1\1$
$1
^$

Try it online! Link includes test cases. Outputs 1 if the input is a member of A005836, 0 if not. Explanation:

.+
$*

Convert to unary.

+`

Repeat as many times as possible...

^1?(1*)\1\1$
$1

... integer divide by 3, but only if the remainder is not 2.

^$

Test to see whether it was possible to reach 0.

Charcoal, 7 6 bytes

›²⌈↨Ｎ³

Try it online! Link is to verbose version of code. Outputs - if the input is a member of A005836, nothing if not. Explanation: Another port of @allxy's solution.

 ²      Literal integer `2`
›       Is greater than
  ⌈     Maximum of
    Ｎ   Input number
   ↨    Converted to base
     ³  Literal integer `3`
        Implicitly print

Previous 7-byte version:

›2⌈⍘⊖Ｎ³

Try it online! Link is to verbose version of code. Outputs - if the input is a member of A003278, nothing if not. Explanation:

 2      Literal characater `2`
›       Is greater than
  ⌈     Maximum of
     Ｎ  Input integer
    ⊖   Decremented
   ⍘    Converted to base
      ³ Literal integer `3`
        Implicitly print

String base conversion is used because array base conversion returns an empty array for an input of 1 (decremented) which has no maximum.

A003278 is infinitesimally denser than A005836 because it effectively includes an extra element at the beginning, so given any finite integer, the number of terms in A003278 less than that integer is always at least as many as the number of terms in A005836 less than that integer, but I don't know whether A003278 always beats all other possible subsets in this way.

A simple greedy approach gives the set [1, 2, 4, 5, 10, 11, 13, 14...]. This is probably optimal.

It can be constructed by:

• Start with the set [1]
• Forever:
  • Take the maximum value of the set, double it, and subtract 1
  • Add that to each value of the set
  • Append that to the current set

Here's an example program to do this.

After a bit of digging on OEIS, we find that the sequence we're looking for is A003278.

A more convenient way of constructing this set is to use one of the definitions on said OEIS page - Try it Online!

This one takes the infinite list of nonnegative integers, converts each to binary and from ternary, and increments them.

This definition is really easy to implement as a check. We simply check that (n-1) in ternary contains no twos.

The sequence plus or minus any constant has the same properties so we can check if n in ternary contains no twos. Thanks to Jonathan Allan for this insight, saving a byte on both versions.

Finally:

Vyxal, 5 bytes

3τ2<A

Try it Online!

3τ    # Convert to base 3
    A # Are all elements
  2<  # Less than 2?

Jelly has a convenient builtin for this which saves a byte:

Jelly, 4 bytes

b3ỊȦ

Try it online!

b3   # Convert to base 3
   Ȧ # Are all elements
  Ị  # Less than two?

PARI/GP, 22 bytes

f(n)=n<2||f(n\3+1)*n%3

Attempt This Online!

A port of loopy walt's Python answer.

JavaScript (ES6), 25 bytes

A port of loopy walt's answer.

24 bytes if we can return zero / non-zero.

f=n=>n<2||n%3&&f(-~(n/3))

Try it online!

Python 3.8 (pre-release), 68 bytes

lambda n,s={1}:any(n in(s:=s|{a+max(s)*2-1for a in s})for _ in[0]*n)

Try it online!

By no means the shortest solution, but a fun one!
Builds up the set using the method described by @allxy's Jelly answer and checks if n is in it.