text:
Boil eggs using hourglasses
These are the classical puzzles:

You need to boil eggs for exactly 9 minutes, or else the visiting Duchess will complain, and you will lose your job as head chef.
But you have only 2 Hourglasses, one measures 7 minutes, and the other measures 4 minutes. How can you correctly measure 9 minutes?
(taken from here)

Let's write a program which will produce a solution for any such puzzle.
Input: 3 numbers a, b, x
Here a and b are the durations of the hourglasses, and x is the required time for boiling the eggs. Let's assume the following:

0 < a < b (without loss of generality)
x is not divisible by a or b (to make the problem non-trivial)
x > 0
x is divisible by gcd(a, b) (to ensure a solution exists)

Output: a string which contains commands, such that after executing the commands, we get our eggs boiled for exactly x minutes.
The possible commands are:

'A' - turn hourglass A
'B' - turn hourglass B
'a' - wait until hourglass A runs out
'b' - wait until hourglass B runs out
's' - start boiling the eggs

You may use any single non-whitespace character to encode each command.
You may also use longer strings to encode commands, but then the string of commands must contain separators between each pair of commands.
You may also add a special command "stop boiling the eggs" if it makes implementation easier (naturally, you cannot restart the boiling - the "stop" command is for the case your algorithm cannot restrain itself from printing additional commands after it prints the solution).
You don't need to optimize your string of commands: it may use an inefficient algorithm or contain unnecessary commands, as long as the result is correct.
Test cases:
3, 5, 1 => ABaAbBsa
4, 7, 9 => ABaAbBsaAaAa
7, 11, 15 => ABaAsbBb
69, 105, 42 => ABaAbBaAaAbBaAbBaAaAbBaAsb
60, 256, 2020 => ABaAaAaAaAbBaAaAaAaAbBaAsaAaAaAbBaAaAaAaAaAbBaAaAaAaAbBaAaAaAaAbBaAaAaAaAbBaAaAaAaAaAbBaAaAaAaAbBb

Note: these solutions were generated by a script, so they contain completely unnecessary commands.

I take it the inputs will be (positive) integers?

Yes. I couldn't imagine otherwise.

related

Can you output the "start" and "stop" commands multiple times, as long as the nth "stop" command occurs x minutes after the nth "start" command?

No. The string is meant as instructions which should be interpreted literally. If you execute such a string, the result will be a disaster!

It'd be nice if you can include a program to verify if a command string results in the correct time. Feel free to use this Python program.

Yes, this is a great program!

Cryptically related

Since the solutions don't need to be optimal, this is not an error, but it might be useful to note that the last 'B' in the first test case is unnecessary. 'ABaAbsa' is sufficient to boil the egg 1 minute.

None of these test cases are optimal. I created them by a simple C++ program, just to show the general syntax of the output. Manually generated solutions would never contain such unnecessary commands.

05AB1E, 29 bytes
∞*.Δ³-²Ö}©ƒN¹Ö₃*N²Ö₂*®³-NQJ0K

Port of @SurculoseSputum's Python answer, so make sure to upvote him!!
Takes the inputs in the same order as the challenge description: a,b,x.
Outputs 95261 instead of aAbBs respectively.
Try it online or verify all test cases or verify the results with the Python script.
Explanation:
∞           # Push an infinite positive list: [1,2,3,...]
 *          # Multiply each by the (implicit) input `a`: [a,2a,3a,...]
  .Δ        # Get the first item in this list which is truthy for:
    ³-      #  Subtract the third input `x`
      ²Ö    #  And check if it's divisible by the second input `b`
  }©        # After we've found our value: store it in variable `®` (without popping)
    ƒ       # Loop `N` in the range [0, `®`]:
     N¹Ö    #  Check if `N` is divisible by the first input `a`
        ₃*  #  Multiply this by 95 (so 95 if truthy; 0 if falsey)
     N²Ö    #  Check if `N` is divisible by the second input `b`
        ₂*  #  Multiply this by 26 (so 26 if truthy; 0 if falsey)
     ®³-NQ  #  Check if `®` minus the third input `x` is equals to `N`
            #  (1 if truthy; 0 if falsey)
     J      #  Join all values on the stack together
      0K    #  And remove all 0s
            # (after the loop, the result is output implicitly)

Python 2, 157 154 108 103 bytes
a,b,c=input()
t=c
while t%a:t+=b
print"".join("aA"[i%a*2:]+"bB"[i%b*2:]+"s"[i^t-c:]for i in range(t+1))

Try it online! or Check all test cases!
Input: from STDIN, 3 positive integers a,b,c representing the 2 hourglass times and the time needed for the egg to boil.
Output: print to STDOUT a string of commands following the specification.
Big idea
There exists positive integers \$x,y\$ such that:
$$ax-by=c$$
(Proof in the last section)
Thus, if we continuously flip both hourglasses, the time between when the second hourglass finishes \$y\$ flips and when the first hourglass finishes \$x\$ flips is exactly equal to the time needed to boil the egg.
Code overview
t keeps track of \$by+c\$. We increment \$y\$ until \$\frac{by+c}{a}\$ is an integer.
When a valid value of t is found, t will be the time needed to flip the first hourglass \$x\$ times, and also the time when the egg should be done. t-c is the time when the second hourglass finishes \$y\$ flips, and also the time when the egg should start to be boiled.
The command string is created by increasing the time i, and insert "aA" or "bB" every time \$a\$ or \$b\$ divides the current time. "s" is inserted when the time is t-c.
Proof of the existence of \$x\$ and \$y\$.
Since \$c\$ is a multiple of \$gcd(a,b)\$, Bézout's identity claims that there exists integers \$k_1, k_2\$ (which can be negative) such that:
$$k_1a-k_2b=c$$
Since \$ba - ab = 0\$, we can increase \$k_1\$ and \$k_2\$ by \$b\$ and \$a\$ without changing the result:
$$(k_1+b)a-(k_2+a)b=c$$
Thus, we can keep increasing \$k_1\$ and \$k_2\$ until they are both positive.

JavaScript (ES6), 93 bytes
Takes input as (a)(b)(x).
A=>(B,k=0)=>g=X=>(k+X)%A?"bB"+(h=n=>"aA".repeat(n+1))(-~~(~-k/A+1)+(k+=B)/A)+g(X):"bs"+h(X/A)

Try it online!
or Check the results online! with @SurculoseSputum's script
How?
The algorithm used requires to count the number of multiples of \$A\$ between \$k\$ (a multiple of \$B\$) and \$k+B\$ (included). This is done with the following formula:
$$\left\lfloor\frac{k+B}{A}\right\rfloor-\left\lceil\frac{k}{A}\right\rceil+1$$
which is translated as the following JS code:
(k + B) / A - ~~(~-k / A + 1) + 1

whose result is implicitly floored.
Commented
\$h\$ is a helper function that repeats "aA" \$n+1\$ times:
h = n => "aA".repeat(n + 1)

Main function:
A =>                     // A = duration of hourglass A
(B, k = 0) =>            // B = duration of hourglass B; k = counter
g = X =>                 // g is a recursive function taking the boiling time X
  (k + X) % A ?          // if k + X is not a multiple of A:
    "bB" +               //   append "bB"
    h(                   //   repeat "aA" as many times as there are ...
      -~~(~-k / A + 1) + //     ... multiples of A between k and k + B (included),
      (k += B) / A       //     using the formula described above
    ) +                  //
    g(X)                 //   append the result of a recursive call
  :                      // else:
    "bs" +               //   append "bs"
    h(X / A)             //   repeat "aA" floor(X / A) + 1 times

Charcoal, 44 bytes
ＮθＮηＮζ⭆⊗×θη⁺⎇﹪ιθω⁺aA⎇﹪⁺ιζηωs⎇﹪ιηω⁺bB⎇﹪⁻ιζθωS

Try it online! Link is to verbose version of code. Uses S to stop boiling, so the actual boiling time is from the first s to the first S after the first s. Explanation:
ＮθＮηＮ

Input a, b and x.
ζ⭆⊗×θη⁺

Loop from 0 to 2ab.
⎇﹪ιθω⁺aA

If this is a multiple of a then stop and start the a hourglass.
⎇﹪⁺ιζηωs

In addition if this plus x is a multiple of b then start boiling.
⎇﹪ιηω⁺bB

If this is a multiple of b then stop and start the b hourglass.
⎇﹪⁻ιζθωS

In addition if this minus x was a multiple of a then stop boiling.

I get more surprised every single time I see what Charcoal can do.

Python 3.7, 158 bytes
I'm very new to this, so if there's some convention on explanations/proofs that should be included please helpfully point me in the right direction.
My Solution:
1.) Not including 's', there is only one move that can be done without returning to a previous point. Wait for a timer to run out if both are running, or if a timer is empty flip that timer. Since timer 'a' is shorter than 'b', you start both, keep flipping 'a' until 'b' runs out, keep flipping 'b' until 'a' runs out (only once), and repeat this cycle indefinitely. It will of course return eventually to a previous position, but if a solution exists it will be found first.
2.) Keeping track of the time left on 'a' when 'b' runs out, you see that it is always some number 'd' less than or equal to 'a'. If a solution exists, eventually the time to cook the egg is a multiple 'n' of 'a' plus or minus 'd'.
3.) If the time to cook is 'n' x 'a' + 'd', start the egg, continue cycling 'a' until the egg is done. If the time to cook is 'n' x 'a' - 'd', start the egg, flip 'a' so it runs backwards 'd' minutes, and continue cycling 'a' until the egg is done.
My Code:
a,b,c=3,5,1
d,i,j,k=a,2,'AB','Aa'
while i:
 i+=1;d,j=((b-d)%a,j+k*((b-d)//a+1)) if i%2 else (a-d,j+'bB')
 if c%a==d:j+='s'+'A'*(i%2)+'a'+k*(c//a);i=0;print(j)

Try it online

Java 8, 115 bytes
(a,b,c)->{int t=c,i=0;for(;t%a>0;)t+=b;for(;i<=t;)System.out.print((i%a<1?"aA":"")+(i%b<1?89:"")+(i++==t-c?1:""));}

Port of @SurculoseSputum's Python answer, so make sure to upvote him!!
Outputs 891 instead of bBs respectively.
Try it online or verify the results with the Python script.


text:
Does base n have any Rotate-Left-Double numbers?
Task
A Rotate-Left-Double number in base \$n\$ is a number \$m\$, when its base-\$n\$ digits are rotated left once, equals \$2m\$. The base-\$n\$ representation of \$m\$ cannot have leading zeros.
One example in base 7 is the number 480, or \$1254_7\$. When rotated left once, the value becomes \$2541_7 = 960\$.
Given the base \$n \ge 2\$, determine if there exists a Rotate-Left-Double number in base \$n\$.
You can use your language's convention to represent truthy/falsy, or use two distinct values for truthy and falsy respectively.
Scoring and winning criterion
Standard code-golf rules apply. Shortest code in bytes wins.
Test cases
n -> answer (example if true)
-----------------------------
2 -> false
3 -> false
4 -> false
5 -> true (13 x 2 = 31)
6 -> false
7 -> true (1254 x 2 = 2541)
8 -> true (25 x 2 = 52)
9 -> true (125 x 2 = 251)
10 -> false
11 -> true [3,7]
12 -> true [2,4,9,7]
13 -> true [1,2,4,9,5,11,10,8,3,7]
14 -> true [4,9]
15 -> true [1,2,4,9,3,6,13,12,10,5,11,8]
16 -> true [2,4,9]
17 -> true [1,2,4,9]

Reference implementation in Python.

Did you wind up figuring out if these numbers are those of the form 2^k+2 and 2? I think it's likely true.

@xnor I didn't, but Kevin Cruijssen apparently has a proof.

Is the challenge then "determine if n-2 is a power of 2 or is zero"? I think this is likely a dupe. Or do we have to prove the fact ourselves?

@xnor Essentially yes to the former, but answers using that property would technically be not an answer until someone actually posts a proof (because it's not a publicly known fact yet). Such a restriction sounds weird though.

That strikes me as a bad idea. It basically seems like a race to post m&-m==m with m=n-2  after a proof is posted, or prove it yourself. Would it be too late to change the challenge to something like counting Rotate-Left-Double numbers, which is hopefully less shortcuttable?

Make that n-2&n-3.

05AB1E, 6 5 bytes
ÍD<&Ā

-1 byte thanks to @xnor and @Noodle9.
Try it online or verify the first \$[2,100]\$ test cases.
Explanation:
Í       # Decrease the (implicit) input-integer by 2
        # Check that this input-2 is a power of 2 by:
 D      #  Duplicating it
  <     #  Decrease the copy by 1 (so integer-3)
   &    #  Take the bitwise-AND of input-2 and input-3
    Ā   #  Check that this is NOT 0
        # (after which the result is output implicitly)

But wait, I don't see any use of bases nor rotation!
When I saw the challenge in the Sandbox and was working on a solution, I noticed that the only falsey values in the first \$n=[2,500]\$ bases formed the sequence A056469: number of elements in the continued fraction for \$\sum_{k=0}^n (\frac{1}{2})^{2^k}\$, which could be simplified to \$a(n)=\left\lfloor2^{n-1}+2\right\rfloor\$. Here a copy of the first 25 numbers in that sequence as reference:
2, 3, 4, 6, 10, 18, 34, 66, 130, 258, 514, 1026, 2050, 4098, 8194, 16386, 32770, 65538, 131074, 262146, 524290, 1048578, 2097154, 4194306, 8388610

It can also be note that all the numbers in this sequence are of the form \$a(n)=2^n+2\$, so checking whether \$n-2\$ is a power of \$2\$ will verify whether it's in this sequence. Since we want to do the invert here, and having a falsey result if it's in this sequence (or truthy if it's NOT in this sequence), we'll do just that, resulting in the code above.
Mathematical proof that all falsey cases of the Left-Rotate-Double numbers are of the form \$2^n+2\$:
Quote from @saulspatz at the Math SE, who provided me with this Mathematical proof to back up my theory I based on the first \$n=[2,500]\$ test cases. So all credit for this proof goes to him/her.
If \$m\$ is a \$(d+1)\$-digit Rotate-Left-Double number in base \$n\$, then $$m=xn^d+y\tag1$$ where \$d\geq1,\ 0<x<n,\ 0\leq y<n^d\$. (Includes the rule that the number can't start with \$0\$.) Rotating \$m\$ gives \$ny+x\$, so we have \$2xn^d+2y=ny+x\$ or $$(n-2)y=(2n^d-1)x\tag2$$ If \$n=2^k+2\$ then \$(2)\$ gives \$(n-2)|x\$ (which means \$x\$ is divisible by \$(n-2)\$), since \$2n^s-1\$ is odd. But then \$y\geq 2n^d-1\$ which contradicts \$y<n^d\$.
To show that these are the only falsey numbers, let \$p\$ be an odd prime dividing \$n-2\$.  (Such a \$p\$ exists because \$n-2\$ is not a power of \$2\$.) In \$(2)\$ we can take \$x=\frac{n-2}p<n\$ and we have to show that there exist an exponent \$d>0\$ and \$0\leq y<n^d\$ such that $$py = 2n^d-1$$ If we can find a \$d\$ such that \$p|(2n^d-1)\$, we are done, for we can take \$y = \frac{2n^d-1}p<n^d\$.
By assumption, \$n-2\equiv0\pmod{p}\$ so \$n\equiv 2\pmod p\$. Therefore, $$2n^d\equiv1\iff 2\cdot2^d\equiv1 \iff 2^{d+1}\equiv 1\pmod p,$$ and by Fermat's little theorem, which states that \$a^{p-1}\equiv 1\pmod p\$, we can take \$d=p-2\$, because $$2^{p-2+1}\equiv 1 \iff 2^{p-1}\equiv 1 \pmod p$$
This completes the proof.

Amazing. That also explains the pattern in the minimal answers: the minimal digit length is the multiplicative order of 2 modulo p. But the proof makes the challenge itself not a very good one :(

@Bubbler Yeah, unfortunately this proof kinda makes it a chameleon challenge. :( I did still upvote it, since it was fun figuring all this out based on your Python reference implementation, the OEIS sequence, and the mathematical proof provided from the Math SE. But I can imagine most people would just create a port of this or the comment provided by xnor, and not look at the bases or rotation at all. :(

$(n−2)|x$ means $(n−2)$ is a divisor of $x$.

@Neil Oops, accidentally swapped the definition. Thanks for noticing!

Surely you can golf this by using my test for a power of 2 (i.e. $n&n-1 = 0$).

@Noodle9 Ah, didn't realize it's shorter in 05AB1E.. I had already seen xnor mention it a couple of hours ago in the challenge comments. Thanks for the reminder, because it's indeed a byte shorter than my approach of checking whether $\log_2(n-2)$ is NOT an integer.

Found my test here.

@Noodle9 Yeah, I've used it a few times before in some past Java answers. :) Can't really find an example, but I've seen it before.

The real use of that site is for speed hehehe. :D

Cool proof! Alternative 5: Í.²θĀ (legacy 05AB1E only, this seems like a bug with modern θ).

@Grimmy Ah, I like that alternative. My original 6-byter used $\log_2$ as well, but didn't think about the θĀ, that's pretty smart! :) (And weird θ doesn't work on decimal numbers in the new version, even though it does with integers.. I would expect the implementation of θ to be something along the pseudo-code lines of: Convert to string, take first character of string.)

Given that powers of 2 have a digital sum of 1 when written in binary, and only 1 is truthy in 05AB1E, could an answer in the form x-2 bin digitsum (space separated commands) be shorter? Not too familiar with 05AB1E or I'd write a sample program

Decided to dive into the 05AB1E wiki. This should work for 4 bytes, assuming you can output falsey if not and truthy if so

@cairdcoinheringaahing Nice find, but I'm afraid it fails for input 2. :(

Python 3, 19 18 bytes
Uses Kevin Cruijssen's formula.
Returns True/False.
Saved a byte thanks to dingledooper!!!
lambda n:n-2&n-3>0

Try it online!

18 bytes by replacing !=0 with >0.

@dingledooper Nice one - thanks! :-)

Retina 0.8.2, 21 bytes
.+
$*
^11(1(11)+)\1*$

Try it online! Link includes test cases. Explanation: The first stage converts to unary, while the last stage uses @KevinCruijssen's observation that a solution exists if n-2 has a nontrivial odd factor.

APL (Dyalog Extended), 9 bytes
⊃∧/⊤⎕-2 3

Try it online!
A full program that takes a single number \$n\$ from stdin, and prints 1 for true, 0 otherwise. APL doesn't have bitwise functions, so we need to explicitly convert to binary and apply boolean functions on each bit.
How it works
⊃∧/⊤⎕-2 3  ⍝ Input: n (from stdin)
    ⎕-2 3  ⍝ [n-2, n-3]
   ⊤       ⍝ Convert to binary
           ⍝ (each number becomes a column in a matrix, aligned to bottom)
⊃∧/        ⍝ Check if the MSB of both numbers are 1,
           ⍝   i.e. the bit lengths of the two are the same

C (gcc), 19 bytes
Uses Kevin Cruijssen's formula.
Returns \$1\$ for falsy and \$0\$ for truthy.
f(n){n=!(n-2&n-3);}

Try it online!

16 bytes with zero for falsy and nonzero for truthy

Bash, 22 20 bytes
Uses Kevin Cruijssen's formula.
Returns \$1\$ for falsy and \$0\$ for truthy.
Saved 2 bytes thanks to dingledooper!!!
echo $[!($1-2&$1-3)]

Try it online!

20 bytes

@dingledooper Ah yes, good one - thanks! :-)

Ruby, 14 bytes
Port of Kevin Cruijssen's answer, remember to upvote them!
->x{x-2&x-3>0}

Try it online!

JavaScript (Node.js), 10 bytes
In JS 0 is falsy and everything else is truthy. Again, another port of Kevin Cruijssen's answer!
x=>x-2&x-3

Try it online!

GolfScript, 5 bytes
In GolfScript 0 is falsy while any other value is truthy.
2-.(&

Try it online!

Charcoal, 8 bytes
‹¹Σ⍘⊖⊖Ｎ²

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if RLD numbers exist otherwise no output. Explanation:
      Ｎ     Input as a number
    ⊖⊖      Decremented twice
   ⍘   ²    Converted to base 2
  Σ         Digital sum
‹¹          Is greater than 1

The only binary numbers with a digital sum of 1 or less are 0 and powers of 2, so by @KevinCruijssen's proof a solution exists for all other values of n.

Husk, 6 bytes
¬εΣḋ≠2

Try it online!
This one got simplified really quickly.

Jelly, 5 bytes
_2&’$

Try it online!
Uses the fact that a given \$n\$ returns \$0\$ iff \$n-2\$ is a power of \$2\$, as pointed out by Kevin Cruijssen and the n-2 & n-3 trick
How they work
_2&’$ - Main link. Takes n on the left
_2    - n-2
    $ - To n-2:
   ’  -   Decrement; n-3
  &   -   n-2 & n-3

source: Stack Exchange

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

sort: votes


text:
Code golf edit distance 2
The edit distance between two strings is the minimum number of single character insertions, deletions and substitutions needed to transform one string into the other.
This task is simply to write code that determines if two strings have edit distance exactly 2 from each other.  The twist is that your code must run in linear time. That is if the sum of the lengths of the two strings is n then your code should run in O(n) time.
Example of strings with edit distance 2.
elephant elepanto
elephant elephapntv
elephant elephapntt
elephant lephapnt
elephant blemphant
elephant lmphant
elephant velepphant

Examples where the edit distance is not 2. The last number in each row is the edit distance.
elephant elephant 0
elephant lephant 1
elephant leowan 4
elephant leowanb 4
elephant mleowanb 4
elephant leowanb 4
elephant leolanb 4
elephant lgeolanb 5
elephant lgeodanb 5
elephant lgeodawb 6
elephant mgeodawb 6
elephant mgeodawb 6
elephant mgeodawm 6
elephant mygeodawm 7
elephant myeodawm 6
elephant myeodapwm 7
elephant myeoapwm 7
elephant myoapwm 8

You can assume the input strings have only lower case ASCII letters (a-z).
Your code should output something Truthy if the edit distance is 2 and Falsey otherwise.
If you are not sure if your code is linear time, try timing it with pairs of strings of increasing length where the first is all 0s and the second string is one shorter with one of the 0s changed to a 1.  These all have edit distance 2. This is not a good test of correctness of course but a quadratic time solution  will timeout for strings of length 100,000 or more where a linear time solution should still be fast.

Given that the word size is $W$, would an $O(NW)$ solution be allowed?

@dingledooper I don’t fully understand what you mean but I suspect the answer is yes. Normally if you are to be very fussy you regard word level operations as constant time. But I don’t want to get stuck  in these details here.

My bad, what I meant was the distinct number of characters in the strings, which seems to be 26 in this question (lowercase letters from a to z).

@dingledooper Yes that is fine.

Uh, Anush, could you look at the list of your newest questions? I see far too many patterns there

@mypronounismonicareinstate The average edit distance between Anush's challenge titles has gone down lately :P

I am very glad to provide a service to fill in the terrible gap in edit distance questions which codegolf.se has had. When there are as many edit distance questions as quine questions my job will be done.

I request an [tag:edit-distance] tag.

Retina 0.8.2, 76 58 bytes
^(.*)(.*¶)\1
$2
(.*)(¶.*)\1$
$2
^.?¶.?$

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

Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:
^(.*)(.*¶)\1
$2

Delete the common prefix.
(.*)(¶.*)\1$
$2

Delete the common suffix.
^.?¶.?$

Ignore an edit distance of less than two.
^.?(.*).?¶.?\1.?$

Check that only the first and last characters have been edited, so that the edit distance cannot be greater than two in this case.
From a code golf point of view this can be done in 51 bytes but then the regex becomes unbearably slow to execute for longer strings:
^(?!(.*).?(.*)¶\1.?\2$)(.*).?(.*).?(.*)¶\3.?\4.?\5$

Try it online! Takes the two strings on separate lines, but link includes test suite which takes space-separated strings instead, so that I can easily use the test cases. Explanation:
^

Match the whole input.
(?!(.*).?(.*)¶\1.?\2$)

Don't match strings with an edit distance less than two.
(.*).?(.*).?(.*)¶\3.?\4.?\5$

Match strings with an edit distance less than three.

This looks great but I am not sure what you have done. Take the strings abab and babz.  They have no common prefix or suffix.  What does your code do next?

@Anush It checks that the middles of the two strings are the same, but at least one of the strings must have its first character skipped and at least one of the strings must have its last character skipped.

@Anush Actually I've tweaked the code slightly now so that it simply tests all permutations of removing leading and trailing characters from both strings to see whether the remainder matches. As this now matches any strings with an edit distance of less than three I've also had to tweak my rejection to include all edits with a distance of less than two.

It's a very nice and simple solution to what could have been a hard question. It also runs fast!

@Anush Actually not quite as fast as it should... a one byte golf I made earlier makes the suffix removal really slow, so I've reverted that change. But if it's slow you want, I've got a 51 byte solution ;-)

Do you think you could make this work for edit distance 3 or 4 as well?

@Anush I would have thought that for a distance of 4 you wouldn't be able to improve on the time complexity of the standard algorithm. I'm not sure for 3; I guess it depends on how clever the regex engine is.

For any fixed edit distance there is a linear time algorithm. I was just wondering if your nice approach might be simpler.

@Anush Sorry, I was referring to the time complexity of this approach, rather than the time complexity of an optimal algorithm.

Haskell, 124 121 99 88 bytes
3 bytes saved by Bubbler
x%y=[0,0]==x#y
u@(a:b)#v@(c:d)|a==c=b#d|k<-zipWith(+)=0:k(d#u)(k(b#v)$b#d)
a#b=a++b>>[0]

Try it online!
This is a modification of the below algorithm which uses a bit of complex short-circuiting to accomplish the task.
I owe much to xnor's comment that initially proposed the idea, and to Noughtmare's SO answer which explained why xnor's initial version didn't work.
99 Bytes
x%y=2==(x#y)0
(u@(a:b)#v@(c:d))x|a==c=b#d$x|x<2=minimum$[d#u,b#v,b#d]<*>[x+1]
(a#b)x=x+length(a++b)

Try it online!
We start by looking at a naive version of edit distance:
lDistance :: ( Eq a ) => [a] -> [a] -> Int
lDistance [] t = length t   -- If s is empty the distance is the number of characters in t
lDistance s [] = length s   -- If t is empty the distance is the number of characters in s
lDistance (a:s') (b:t') =
  if
    a == b
  then
    lDistance s' t'         -- If the first characters are the same they can be ignored
  else
    1 + minimum             -- Otherwise try all three possible actions and select the best one
      [ lDistance (a:s') t' -- Character is inserted (b inserted)
      , lDistance s' (b:t') -- Character is deleted  (a deleted)
      , lDistance s' t'     -- Character is replaced (a replaced with b)
      ]

(I wrote this program for Wikipedia here)
This is pretty bad because every time it finds a discrepancy between the two strings it branches into 3 options (insert, delete or replace) so in the worst case it will have the time complexity of \$O(3^n)\$.
The thing to notice though is that whenever we branch we increase the total distance by 1.  So if we are on a particular search path that has already branched 2 times and we would branch another time, we can just stop there and say return the total we have for the branch.  All values above 2 are the same as far as we are concerned.
Now there is a hard limit on the number of branches that can occur, \$3^2 = 9\$, so our computation is \$O(n)\$.
In general this strategy has a complexity of \$O(3^mn)\$ where \$m\$ is the limiting distance and \$m < n\$.

121

I was trying to use Haskell's lazy evaluation to shortcut edit distance greater than 2, but it seems not to work: TIO. Not sure why. I thought that since, say, min[0,0][0,0..] short-circuits evaluation it's wouldn't evaluate branches with with results above [0,0] for distance 2.

I timed it with two strings of length 100k and 100k  - 1.  It takes about 1s which indicates to me it is linear but do you understand why it is taking that long?  The Retina solution takes about 1/10th of the time.

@Anush An empty Haskell program on TIO also seems to take about a second to run.

@xnor Aha!  That solves it.

@xnor I finally got a lazy evaluation version working and it saved a lot of bytes.   One year later but thanks.  I've linked an explanation as to why it didn't work initially.

Python 3.8, 273 \$\cdots\$316 312 bytes
Added 30 bytes to fix bugs kindly pointed out by Bubbler.
Added 12 bytes to fix a bug kindly pointed out by ovs.
Saved 9 bytes thanks to ovs!!!
def f(*x,i=0):
 b,a=w=sorted(x,key=len);d,c=map(len,w)
 while a[i]==b[i]:
  if(i:=i+1)==d:return i==c-2
 while a[c-1]==b[d-1]:
  if d==1:return c==3
  c-=1;d-=1
 a=a[i:c]
 b=b[i:d]
 return c-i>1and((x:=a[1:-1])==(y:=b[1:-1])or a[:-1]==y or a[1:]==y or a[:-1]==b[1:]or a[1:]==b[:-1]or x==b[:-1]or x==b[1:]or x==b)

Try it online!

This fails with a max recursion depth error for strings that aren't very short. This means I can't test if it is really running in linear time.

I think a[1:] is linear time itself in python at it copies the list.

I get a syntax error when I try to run the code now. https://bpaste.net/NXVQ

Could you paste a standalone python program to bpaste.net please?

@Anush It's probably using version less than Python 3.8. Run it on your laptop with Python 3.8.

Let us continue this discussion in chat.

I still don't think it's linear time. Try  length = 1000; a = ''.join(str(x) for x in [0]length);
b = ''.join(str(x) for x in [0](length-1));
print(f(memoryview(bytes(a, encoding='utf8')),memoryview(bytes(b, encoding='utf8')))) . That doesn't terminate for me.

@Anush All good to go now, works with very large strings in TIO.

The first few lines can be def f(*x,i=0): b,a=w=sorted(x,key=len);d,c=map(len,w).

In the first loop the two lines can be combined with an assignment expression to if(i:=i+1)==d:return i==c-2.

@ove Very nice golfs - thanks! :-)

JavaScript, 120 bytes
a=>b=>a.reduce((t,c,i)=>t.map((n,j)=>p=Math.min(n-(c==b[i+j-2]),p,t[j+1]||4)+1,p=4),[4,4,1,2,3])[b.length-a.length+2]==3

Try it online!
Try a large one!
Traditional DP solution, with modification the formula by \$dp_{i,k}=\infty \text{ if } \left|i-k\right|>2 \$. And we use \$ k=i+j-2 \$ here.
t is initialed to [4,4,1,2,3] which means (the edit distance of an empty string and first j-2 characters of b) plus 1. Any number greater than 3 here means Infinity. After i-th iteration, t[j] is (the edit distance of substring a[0..i], and, b[0..(i+j-2)]) plus 1; Or anything greater than 3 if the edit distance is greater than 2.

Could you add some explanation please? Have you tried it on two strings of length roughly 100,000?

@Anush As it only contains 2 nested loops, one repeat a.length times, and the inner one repeat 5 times. It will cost O(a.length*5) time to run, which meet the complexity requirement.

@Anush And do you mean add some testcases like this one?

Thank you. What do the magic numbers 4,4,1,2,3 signify?

Thank you for adding that test case!

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


text:
Check membership of an infinite list
As input you will receive

An integer \$a\$

A list of integers that is infinite and strictly-monotonic1.

Your program should check in finite time if \$a\$ appears the list.
You should output one of two distinct values.  One if \$a\$ appears in the list and the other if \$a\$ does not.
This is code-golf so answers will be scored by their length in bytes with fewer bytes being better.

You may take an infinite lists in any of the following formats:

A list, stream, iterator or generator if your language allows them to be infinite.

A function or pointer to a function that outputs the next value when queried with no input.

A function or pointer to a function that outputs the \$n\$th value when passed \$n\$ as an input.

Additionally you may repeatedly query STDIN with the assumption that each query will provide the next term in the sequence.

Test cases
Since I cannot put infinite lists in the body of a challenge I will provide the first couple terms along with a description of the list and a definition in Haskell.
6
1 2 3 4 5 6 7 8 9 10 ... (positive integers) l=[1..]
 =>
True

6
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 ... (negative integers) l=[-1,-2..]
 =>
False

109
0 2 4 6 8 10 12 14 16 18 20 ... (non-negative even integers) l=[0,2..]
 =>
False

-5
200 199 198 197 196 195 194 193 192 ... (integers smaller than 201) l=[200,199..]
 =>
True

256
1 2 3 5 8 13 21 34 55 89 144 ... (unique Fibonacci numbers) l=1:2:zipWith(+)l(tail l)
 =>
False

1
1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 ... (integers less than 2) l=[1,0..]
 =>
True

1: A strictly monotonic sequence is either entirely increasing or entirely decreasing.  This means if you take the differences between consecutive elements they will all have the same sign.

Does a theoretically infinite list fall within the rules?

@S.S.Anne I'm not sure what a theoretically infinite list is.

Meaning memory or memory model limits restrict the length of the list but given infinite memory and an unbounded memory model it would work.

@S.S.Anne Let's continue this discussion in chat.

I like how you made this challenge so it's impossible to write a solution that's against the rules.

Let's say a language supports infinite lists, but doesn't have functions. Can we put the infinite list in the header as an argument that is already on the stack, or perhaps put it in a variable that we can use?

Your program should check in finite time if a appears the list. what if a doesn't appear?

@l4m2 Then after finite time it should output false (or equivalent).

Python 2, 43 bytes
Takes as input the target integer \$a\$, and a lambda function \$g\$. Since the list is always either strictly increasing or decreasing, we only need to check if \$a\$ appears in the next \$ |a-g(0)|+1 \$ numbers.
lambda a,g:a in map(g,range(abs(a-g(0))+1))

Try it online!

This is good. How hard was it to come up with?

Thanks! I wouldn't call it hard, since it was the first and only method I came up with.

Haskell, 33 bytes
t#l@(a:r)=t==a||(a<t)==(l<r)&&t#r

Try it online!

convey, 144 92 bytes
 v<<<<<<<<<<<
>;  >">>??>=@]
"">>,<1[v)>#,
v}^>)?:`(#>#^
v{^"9>v]^",^
>;@">>@`"#^
1>0   >>>^

Try it online!

Input is given as a list of integers with the first integer being the goal and the remaining being the list.  Since there is no way to accept infinite input, this program instead only consumes a prefix of the input.  You can see this in that there is a very long relay line to stop additional input.
Explanation
To start we need to split the first element off the input, to be used.  To do this I use a simple switch, and because we want to use the input a bunch I feed it into a sort of generating vortex to continuously pump out new copies.

Now we split the main stream in two, and calculate the differences on one of the parts.  This will tell us if the list is ascending or descending.

Now we use the difference stream to redirect the main stream, to the two different comparison sites.  If the list is ascending we want to go until the element is greater than or equal to n if it is descending we want to go until it is less than or equal to n.

So that stream coming out now will give us some ones and then at some point switch to zeros.  What we are concerned about is the first number that gives a zero.  We want to know if it is equal to n.  So we create another stream and get whether that is equal to n.

At this point I'm going to stop with the gifs, since they really look like the end product mostly.  We redirect the streams with each other, discarding all the elements before the comparison starts giving zero.  Then we use a lock to grab just the first equality.  We output this and send a signal to stop taking input.  With no input the machine slowly winds down and halts.

Congratulations, you are the first other convey user! I'm really happy that it's apparently usable for someone else, thanks! :-) If there is a fixed number of elements, you can often use ? instead of @, e.g. at the top instead of 01@v…>(, ?v…>(. Or at the bottom ? to just have one element: this should be equivalent. And there seems to be a bug that & omits every second item in this configuration, will try to fix that now.

@xash Thank you convey is a lot of fun!  I figured how to use ? a bit on my second try (which is a lot shorter).  On the topic of bugs is # supposed to act like a queue? It has been a bit of a source of frustration for me and I don't see it in the docs.

… finally fixed # and & passing all my tests and both your solutions. They shouldn't queue, but I guess the paths shouldn't block each other. Nice second solution!

Python 3.8 (pre-release), 61 bytes
def f(l,v):
 a=l()
 while(a-v)*(b:=a-l())>0:a-=b
 return a==v

Try it online!
Input is a function that returns the next value on every call and an integer.

Python 3.8 (pre-release), 70 69 bytes
1 byte shorter thanks to @JonathanAllan.
def g(l,v):
 a=next(l)
 while(a-v)*(b:=a-next(l))>0:a-=b
 return a==v

Try it online!
Input is a generator and an integer, can probably be shorter with one of other input formats.

\nN=next has cost a byte

@JonathanAllan thanks for pointing it out.

Python 3.8 is already released, by the way.

@user2357112 It's not manually typed out. That's just the way TIO has it on there.

a*(b:=a-l())>v*b for a byte saved

Haskell, 43 bytes
a#k@(b:c)|k>c=(-a)#map(0-)k|b<a=a#c|1>0=b>a

Try it online!
This outputs False if the integer is present and True if it is not although I have added a not to the handler because that sort of output is confusing to me.

Explanation
The first check we do is k>c, that is whether the input is greater than its own tail.  Since this list is strictly monotonic the heads of these lists cannot be equal so k>c is a short way of comparing their heads.  This check thus tells us whether the first element is larger than the second and by extension whether the input is decreasing. If the input is decreasing we negate everything to make it increasing
(-a)#map(0-)k

The next check is whether b<a, that is the head of the list is less than the thing we are looking for.  If it is then we should find a later in the list so we discard b and go again
a#c

If that fails then a<=b meaning that either b is a or b should come before a.  Since b is the first element we know that the only way for a to be present is for it to be b.  Thus we halt returning
b>a

Which is a shorter way of writing b/=a since we know already that b>=a.

Bash + GNU utilities, 47 44 43 42 bytes
read m
sed 1$[(m-($1))**2]q\;i$m|grep ^$1$

Try the test suite online!
3 bytes off thanks to user41805's pointing out that a single sed could be used to replace both the echo and the head.
1 more byte thanks to user41805 again.
And now 1 more from user41805.
The target integer (the integer \$a\$ in the challenge description) is passed as an argument, and the infinite list is read from stdin.  (The challenge says: "Additionally you may repeatedly query STDIN with the assumption that each query will provide the next term in the sequence.")
The output is the program's exit code (0 for truthy, 1 for falsey).

Explanation:
The program reads the first number in the infinite list into \$m\$.
Let \$a\$ be the target integer that we're looking for (it's $1 in the program).  In principle we need to check, after \$m\$, at most \$\left| m-a \right|\$ additional values in the infinite list, because we're starting at \$m\$ and either going up by at least 1 for each number in the list or going down by at least 1 for each number in the list.
However, the program actually checks (more than) \$(m-a)^2\$ additional values.  That's OK, because \$(m-a)^2\ge\left|m-a\right|\$.  We may be checking additional (unnecessary) values, but that's harmless.
The original version checked exactly \$(m-a)^2\$ additional numbers (using head). Unfortunately, replacing head -${n} with sed -${n}q doesn't work if the value of n is 0, so we need to enlarge the number of items checked.  To do this, I simply prepend a 1 to the number (which takes one fewer byte than adding 1 to it).
The golfing benefit in doing all this is that, in bash, squaring a number requires fewer bytes than taking the absolute value of a number (as far as I can see).

You should be able to convert (echo $m;head -$[(m-($1))**2]) into a single sed 'call', and so remove the need for the parens

@user41805 Thanks -- I hadn't thought of using sed to replace both the echo and the head.  (I had tried replacing head with sed early on but just doing that didn't shorten things.)

Nice including the 1 in front of the number, I missed that, this now allows you to bring 1i$m after the q statement, saving on the newline and the quotes. Additionally, the 1 can be dropped as well. Hm I wonder if awk would be shorter

@user41805  Thanks again -- reversing the order of the sed commands saved a byte.  It got rid of the quotes, but the newline had to be replaced with the 2 characters \;.  I haven't looked into using awk.

You should be able to remove the 1 in 1i$m

@user41805  Thank you.  Yes, that requires the program to look through twice as many items before it reaches the target or gives up, but I'm already having it look through far more items than that!

Pyth, 20 17 16 9 bytes
Takes a on STDIN, then a list of values on STDIN.
Edit: Wow, under 10 bytes now! Really shows how powerful Pyth is :P
}Q+JEmEaJ

Try it online!
Port of @dingledooper's Python answer.
}Q+JEmEaJ
 Q              # Initialize Q to be the first input from STDIN
   JE           # Initialize J to be the next input from STDIN
}Q              # Return true if Q is in:
  +             #   The union of
   JE           #      - the first element of the sequence
     mEaJ(Q)    #      - abs(J-Q) more inputs from STDIN (Q appended implicitly)

8 bytes, if we can return the index of a in the list
x+JEmEaJ

Try it online!
x+JEmEaJ
x          (Q)  # Find index of Q in:
 +              #   The union of:
  JEmEaJ(Q)     # J and the next abs(J-Q) elements

05AB1E, 14 13 bytes
D¥нdiIë(I(}.i

-1 byte thanks to @Grimmy.
05AB1E has infinite lists, but no functions. So it assumes the infinite list is already at the top of the stack. Assuming this is allowed for stack-based languages according to the meta, but it explicitly mentions functions, so not sure how to handle it here.
Alternatively, the infinite list can be put in a pre-defined variable (i.e. X), in which case this would be 15 bytes with that X as additional leading byte.
Try it online or verify all test cases. The second line of the header contains the infinite list(s). In the output the first 10 values are printed as example sublist, so you know which infinite list was used in the program.
Explanation:
05AB1E has a builtin to check if an integer is in an infinite list that is guaranteed to be non-decreasing, which is .i. Using that builtin, we have the following program:
D         # Duplicate the infinite list at the top of the stack
 ¥        # Take it's deltas / forward-differences
  н       # Pop and push the first difference of this list
   di     # If it's non-negative:
     I    #  Simply push the input-integer
    ë     # Else (it's negative):
     (    #  Negate all values in the infinite list
      I(  #  Push the input-integer, and negate it as well
    }     # After the if-else, where we now have a non-decreasing infinite list
     .i   # Check if the (possibly negative) input we pushed is inside this infinite list
          # (after which the result is output implicitly)

Note that this approach only works because the infinite list is guaranteed to be either only increasing or only decreasing. With an infinite list that is both (i.e. \$a(n) = \left\lfloor10\tan(n)\right\rfloor\$ → [0, 15, -22, -2, 11, -34, -3, 8, -68, -5, ...]), this approach of course wouldn't work.

Is the 11th byte y or I?

@GregMartin Oops.. error curing copy-paste from the test suite. It's supposed to be I (push input). Thanks for noticing.

0‹ can be d by switching the two branches.

Here's a 7

@Grimmy Nice approach! I think it might be better if you post it as a separated answer, since it's completely different from my approach with .i. :)

Posted as a separate answer (also i golfed another byte).

K (ngn/k), 21 bytes
{|/x=y'!1+|/-:\x-y.0}

Try it online!
Explanation
x is number, y is function representing infinite list.

1+|/-:\x-y.0 equivalent to 1 + abs(x - y(0))
! range
y' apply y to each element
|/x= find x

GolfScript, 33 bytes
(@:k\-abs:r;0:g;{(k=g+:g;}r*;r!g+

Try it online!
This is a very, very quick and dirty way of doing this problem.
TL;DR
Check if the first number is the number we're looking for. If not, then find the difference between our number (finite) and the first number (finite) to get the maximum number of elements we need to search (finite). This is a clusterfuck, clumsy, and messy, but it does the job adequately. There's probably a builtin I'm missing, but I'll come back to this later to refine it and to make code short enough worthy of an explanation.

Charcoal, 24 bytes
ＮθＮηＮζＷ›Π⁻⟦θη⟧ζ⁰Ｎζ№⟦ηζ⟧θ

Try it online! Link is to verbose version of code. Reads each value as a separate line on STDIN and outputs - only if a appears in the monotonic list. Explanation:
Ｎθ

Input a.
ＮηＮζ

Input the first two terms of the list.
Ｗ›Π⁻⟦θη⟧ζ⁰

Repeat while the last term of the list so far lies between a and the first term.
Ｎζ

Read another term from the list.
№⟦ηζ⟧θ

Output - if a is the first term or the term just read.

APL (Dyalog Unicode), 15 bytesSBCS
{⍵∊⍺⍺⍳1+|⍵-⍺⍺1}

Try it online! Uses dingledooper's idea.
{             } ⍝ Operator accepting function on the left and integer on the right
   ⍺⍺           ⍝ Apply the input function to
     ⍳           ⍝ the range of integers from 1 to
      1+         ⍝ 1 plus
        |        ⍝ the absolute value of
         ⍵-      ⍝ the input number minus
           ⍺⍺1   ⍝ the first value of the input function.
 ⍵∊              ⍝ Finally check if the input number is in that list.

You need to include {} in a dfn, because by itself it isn't a valid function

@user41805 Are you sure? :'(

@RGS Yes.

@Adám damn it, went from "winning by 1 byte" to "2nd place by 1 byte" :)

@RGS Don't worry about it; you're still winning big in the "production languages" category!

Ruby, 39 bytes
->a,g{[]!=[a]&(0..a*a+g[0]**2).map(&g)}

Try it online!

Unfortunately, it gives me error on 4th test case: The request exceeded 60 second time limit and was terminated.

05AB1E, 7 6 bytes
α¬>£0å

Try it online! or verify all test cases.
Takes the infinite list input via the stack, like Kevin's 05AB1E answer.
α              # absolute difference of the number with each element of the infinite list
               # this list contains 0 iff the original list contains the number
 ¬             # get the first element
  >            # increment
   £           # get the first n elements, where n = first element + 1
    0å         # check if 0 is in those elements

Wolfram Language (Mathematica), 31 bytes
#2@Range@Abs[#-#2@0]~MemberQ~#&

Port of dingledooper's python 2 solution.
Try it online!
Other similar attempts:
⌊#⌋==#&&#>=1&@InverseFunction[#2]@#&

and:
Tr[1^Solve[#2@x==#,x,PositiveIntegers]]==1&

9 bytes
Mathematica doesn't have iterators or generators in the same way python does, but Regions and Domains take their place. If you allow Regions as an equivalent,
{#}∈#2&

just tests if the 1d point of the first argument is in the Region. RAW (Rules as written) don't allow Regions, so I'm going to leave the port as the main answer.
Try it online!
The best solution is just Mathematica's built-in Element over a domain, but Domains do not seem to be able to be defined by the users, only the premade handful exist.

Desmos, 41 bytes
f(k)=∑_{n=0}^{(k-g(0))^2}0^{(g(n)-k)^2}

Because Desmos does not support infinite lists and does not support functions as arguments, the input list should be represented as a function named g.
Pretty much a port of dingledooper's Python answer, except I replaced absolute value with square because that is golfier.
Try It On Desmos!
Try It On Desmos! - Prettified

JavaScript (ES7), 49 bytes
Using @dingledooper's method
Takes input as (integer)(generating_function). Returns \$0\$ or \$1\$.
n=>g=>(F=k=>k*k>(g(0)-n)**2?0:g(k)-n?F(k+1):1)(0)

Try it online!

JavaScript (ES6), 54 bytes
Takes input as (integer)(generating_function). Returns a Boolean value.
n=>g=>(F=k=>(v=g(k),g(1)>g(0)?v<n:v>n)?F(k+1):v)(0)==n

Try it online!

You don't need $$k^2>(g(0)-n)^2$$, $$k$$ being some larger is not a problem

C (gcc), 59 bytes
t;f(a,p)int*p;{for(t=abs(a-*p)+2;t-->0;)t=*p++-a?t:-1;++t;}

Takes a pointer to an "infinite" array. The way I implement this is to only calculate the numbers that are used (and then a "safe buffer" at the end to make sure I don't have any off-by-one errors, but this won't skew the result).
Es un puerto de la solución de dingledooper.
-1 byte thanks to ceilingcat!
Try it online!

Nice, but did you forget to remove that ‘n’ at the beginning, because I don’t really see the point of it.

That was from the old way, with the generator function. I'll get rid of it when I have access to my computer.

How would it stop in case of the second case? (6 in -1,-2,...)

@VaradMahashabde That's what the abs is for in the initialization of the counter variable.

Pip -x, 24 bytes
W(Y(bi))CMa=yCM(bUi)_a=y

Uses the third format of infinite list: "A function... that outputs the nth value when passed n as an input." Takes a number and a function as command-line arguments. Attempt This Online!
Explanation
W(Y(bi))CMa=yCM(bUi)_a=y
                          a is the number, b is the function, i is 0 (implicit)
W                         While...
   (bi)                     Call b with argument i
  Y                         Yank the result into y
 (     )CMa                 Compare that value with a (returns -1, 0, or 1)
           =                Equals
            yCM             Compare y with
               (b  )        Call b with argument
                 Ui         Increment i
                          ... loop:
                    _       No-op
                          When the loop exits, we've either reached or passed a
                     a=y  1 if the most recent sequence value equals a, 0 otherwise
                          Autoprint (implicit)

Perl 5, 55 bytes
sub f{$f=pop;@L=($F=&$f,map&$f,0..abs$_[0]-$F);pop~~@L}

Try it online!
More or less a translation of @dingledooper's Python2 answer.

perl -lE, 34 bytes
$t=<>;{$_=<>;$_<$t?redo:say$_==$t}

Try it online!
Prints 1 followed by a newline if the first element of the list appears elsewhere; otherwise, it just prints a newline. The program terminates after reading the first number which is equal or larger than the first number.

I don't think this works for decreasing input sequences: Try it online!

Java (JDK), 67 bytes
a->s->{int p=s.get(),n;for(;p*(n=p-s.get())>a*n;)p-=n;return p==a;}

Try it online!
Credits

-2 bytes thanks to ceilingcat

C++ (gcc), 114 bytes 106 bytes
#include<iostream>
int f(int a){int p,t;std::cin>>t;if(t-=a)for(;p=t,std::cin>>t,t-=a,p*t>t*t;);return!t;}

Try it online!

Explanation :
Our only hope of finding \$\alpha\$ in the future terms of the list \$t\$ is if :

We don't skip over \$\alpha \implies\$ The difference of \$\alpha\$ and \$t_n\$ doesn't change signs \$\implies \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0 \space \forall \space  n\in N, n > 1\$.(If it is zero, one of the terms is our target)
The series approaches our target \$\implies {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|}\$

We can then combine these two conditions :
$$
{\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|}
$$
$$
\implies {\left| \alpha - t_n\right|} \cdot {\left| \alpha - t_{n-1}\right|} < {\left( \alpha - t_{n-1}\right)}^2$$
$$
\text{Since we need that}\left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0,
$$
$$
\text{Condition } P \equiv \left( {\left| \alpha - t_n\right|} < {\left| \alpha - t_{n-1}\right|} \right) \land \left( \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right)>0 \right)
$$
$$
P \equiv \left(\alpha - t_n\right)\cdot\left(\alpha - t_{n-1}\right) < {\left(\alpha - t_{n-1}\right)}^2
$$
Hence if \$P\$ is found to be false the either the target has been found or we have passed it (or never reach it).

Ruby, 56 bytes
f=->a,g,t=1{a==g[t]||(g[2]-g[1])*(g[t]-a)<0&&f[a,g,t+1]}

Recursively, checks if current term g[t] == a, then return true. Else, check if the product of difference g[2] - g[1] and a - g[t] are of opposite sign, if yes, then return false
Try it online!

Ruby, 40 bytes
Port of dingledooper's Python answer!
->a,g{(1..(a-g[0]).abs+1).map(&g).any?a}

Try it online!

Julia, 23 bytes
N\~=N∈.~(0:abs(N-~0))

Try it online!
takes a zero-indexed function as input
port of dingledooper's solution. The solution I found on my own was exactly double the length


text:
Decode Arabic to Arabic Presentation Form
Objective
Given an Arabic string consisting of ISO/IEC 8859-6 Arabic letters (U+0621–063A, 0640–064A), decode it to Arabic Presentation Forms-B (U+FE70–FEFF).
Behavior of Arabic letters
ISO/IEC 8859-6 Arabic letters change their displayed form to letters in Arabic Presentation Forms-B, which are categorized to isolated, initial, medial, or final letters.

If a letter is the first letter or follows another letter in isolated or final form:

If it is also the last letter or it lacks an initial form, it is in isolated form.
Otherwise, it is in initial form.

Otherwise, if the letter is not the last letter, its medial form is available, and the next letter is not ء(U+0621), it is in medial form.
Otherwise, the letter is in final form.
ـ (U+0640) is a special case. It doesn't have a presentation form, and always will be mapped to itself. It will be assumed to appear only where a letter in medial form could appear.

Note that Arabic letters are written right-to-left.
Mapping

Note that we don't care about ligatures (U+FEF5–FEFC).
Rule
If the string contains a letter not within U+0621–063A nor U+0640–064A, the challenge falls in don't care situation.
Example
The following word:
الله (U+0627 U+0644 U+0644 U+0647)

is decoded to:
ﺍﻟﻠﻪ (U+FE8D U+FEDF U+FEE0 U+FEEA)

The following word:
تكبر (U+062A U+0643 U+0628 U+0631)

is decoded to:
تكبر (U+FE97 U+FEDC U+FE92 U+FEAE)

The following word:
سلـام (U+0633 U+0644 U+0640 U+0627 U+0645)

is decoded to:
ﺳﻠـﺎﻡ (U+FEB3 U+FEE0 U+0640 U+FE8E U+FEE1)

The following word:
شيء (U+0634 U+064A U+0621)

is decoded to:
ﺷﻲﺀ (U+FEB7 U+FEF2 U+FE80)

I think more test cases would be nice!

"Note that Arabic letters are written right-to-left." - does this affect the challenge? (The examples seem to have been treated left-to-right.)

When you say "first" and "last" is that with respect to the entire input string/list or a "word"? If the latter what splits words?

@JonathanAllan In the examples, the Arabic letters are written right-to-left, but the code points are written left-to-right. Since the string doesn't contain whitespaces, the string is a single "word."

@Arnauld All fixed.

Could you quite a few more test cases, especially for the special cases. Like one that contains ـ (U+0640) and two test cases with ء (U+0621): one before a medial form and one with ء (U+0621) somewhere else in the word. My current approach works for the two examples, but I haven't even implemented anything for these special cases yet.. Also, a test case where the last letter is a final form would also be useful.

May our code take and return a list of code points?

@Arnauld I'll permit it.

Is the rule about TATWEEL (U+0640) true? Shouldn't U+0640 followed by U+064B be mapped to U+FE71?

05AB1E, 110 107 bytes
1ƵFLŽ$§R©+ε•7Ö›±ćY¨Γ∊%•ƵBвNåi1‚1ª]˜4ô®¸šIŽ6d-D₂›6*-èRćURviy2èDiyнsë0ëyθDΘIN>èŽ6dQ~i\y1è1ë0]Xs_i¦}н)IŽ6ηDŠkǝ

-3 bytes due to looser I/O rules.
I/O as a list of code-point integers.
Try it online or verify all test cases.
Explanation:
1                   # Push a 1 (which we'll use later on)

We start by creating the lookup table:
 ƵF                 # Push compressed integer 116
   L                # Pop and push a list in the range [1,116]
    Ž$§             # Push compressed integer 25156
       R            # Reverse it to 65152
        ©           # Store this value in variable `®` (without popping)
         +          # Add it to each value in the list, to make the range [65153,65268]
ε                   # Map each value to:
 •7Ö›±ćY¨Γ∊%•       #  Push compressed integer 35731296019285847629599
             ƵB     #  Push compressed integer 112
               в    #  Convert the larger integer to base-112 as list:
                    #   [1,3,5,7,13,19,41,43,45,47,109,111]
 Nåi                #  If the map-index is in this list:
    1‚1ª            #   Pair it with a 1, and add a second 1 to this list
]˜                  # Close the map and if-statement, and flatten the list of values
  4ô                # Split it into parts of size 4
    ®¸š             # Prepend [65152] (from variable `®`) in front of this list

Which will now hold the following list:
[[65152],[65153,65154,1,1],[65155,65156,1,1],[65157,65158,1,1],[65159,65160,1,1],[65161,65162,65163,65164],[65165,65166,1,1],[65167,65168,65169,65170],[65171,65172,1,1],[65173,65174,65175,65176],[65177,65178,65179,65180],[65181,65182,65183,65184],[65185,65186,65187,65188],[65189,65190,65191,65192],[65193,65194,1,1],[65195,65196,1,1],[65197,65198,1,1],[65199,65200,1,1],[65201,65202,65203,65204],[65205,65206,65207,65208],[65209,65210,65211,65212],[65213,65214,65215,65216],[65217,65218,65219,65220],[65221,65222,65223,65224],[65225,65226,65227,65228],[65229,65230,65231,65232],[65233,65234,65235,65236],[65237,65238,65239,65240],[65241,65242,65243,65244],[65245,65246,65247,65248],[65249,65250,65251,65252],[65253,65254,65255,65256],[65257,65258,65259,65260],[65261,65262,1,1],[65263,65264,1,1],[65265,65266,65267,65268]]

Which corresponds to the following table:
ISO 8859-6   Isolated      Final         Initial       Medial
1569[0621]   65152[FE80]
1570[0622]   65153[FE81]   65154[FE82]   1[n\a]        1[n\a]
1571[0623]   65155[FE83]   65156[FE84]   1[n\a]        1[n\a]
1572[0624]   65157[FE85]   65158[FE86]   1[n\a]        1[n\a]
1573[0625]   65159[FE87]   65160[FE88]   1[n\a]        1[n\a]
1574[0626]   65161[FE89]   65162[FE8A]   65163[FE8B]   65164[FE8C]
1575[0627]   65165[FE8D]   65166[FE8E]   1[n\a]        1[n\a]
1576[0628]   65167[FE8F]   65168[FE90]   65169[FE91]   65170[FE92]
1577[0629]   65171[FE93]   65172[FE94]   1[n\a]        1[n\a]
1578[062A]   65173[FE95]   65174[FE96]   65175[FE97]   65176[FE98]
1579[062B]   65177[FE99]   65178[FE9A]   65179[FE9B]   65180[FE9C]
1580[062C]   65181[FE9D]   65182[FE9E]   65183[FE9F]   65184[FEA0]
1581[062D]   65185[FEA1]   65186[FEA2]   65187[FEA3]   65188[FEA4]
1582[062E]   65189[FEA5]   65190[FEA6]   65191[FEA7]   65192[FEA8]
1583[062F]   65193[FEA9]   65194[FEAA]   1[n\a]        1[n\a]
1584[0630]   65195[FEAB]   65196[FEAC]   1[n\a]        1[n\a]
1585[0631]   65197[FEAD]   65198[FEAE]   1[n\a]        1[n\a]
1586[0632]   65199[FEAF]   65200[FEB0]   1[n\a]        1[n\a]
1587[0633]   65201[FEB1]   65202[FEB2]   65203[FEB3]   65204[FEB4]
1588[0634]   65205[FEB5]   65206[FEB6]   65207[FEB7]   65208[FEB8]
1589[0635]   65209[FEB9]   65210[FEBA]   65211[FEBB]   65212[FEBC]
1590[0636]   65213[FEBD]   65214[FEBE]   65215[FEBF]   65216[FEC0]
1591[0637]   65217[FEC1]   65218[FEC2]   65219[FEC3]   65220[FEC4]
1592[0638]   65221[FEC5]   65222[FEC6]   65223[FEC7]   65224[FEC8]
1593[0639]   65225[FEC9]   65226[FECA]   65227[FECB]   65228[FECC]
1594[063A]   65229[FECD]   65230[FECE]   65231[FECF]   65232[FED0]
1601[0641]   65233[FED1]   65234[FED2]   65235[FED3]   65236[FED4]
1602[0642]   65237[FED5]   65238[FED6]   65239[FED7]   65240[FED8]
1603[0643]   65241[FED9]   65242[FEDA]   65243[FEDB]   65244[FEDC]
1604[0644]   65245[FEDD]   65246[FEDE]   65247[FEDF]   65248[FEE0]
1605[0645]   65249[FEE1]   65250[FEE2]   65251[FEE3]   65252[FEE4]
1606[0646]   65253[FEE5]   65254[FEE6]   65255[FEE7]   65256[FEE8]
1607[0647]   65257[FEE9]   65258[FEEA]   65259[FEEB]   65260[FEEC]
1608[0648]   65261[FEED]   65262[FEEE]   1[n\a]        1[n\a]
1609[0649]   65263[FEEF]   65264[FEF0]   1[n\a]        1[n\a]
1610[064A]   65265[FEF1]   65266[FEF2]   65267[FEF3]   65268[FEF4]

not in the list:
1600[0640]                                             1600[0640]

After that, we'll use the input to get a quartet from this list:
I                   # Push the input-list of codepoint integers
 Ž6d                # Push compressed integer 1569
    -               # And subtract it from each integer in the list
     D              # Duplicate this list
      ₂›            # Check which are larger than 26 (1 if truthy; 0 if falsey)
        6*          # Multiply that by 6 (6 if truthy; 0 if falsey)
          -         # And subtract that from the values in the list as well
           è        # Then index it into our list of quartets

And now we apply the rules specified in the challenge description on these quartets of [isolated, final, initial, medial].
R                   # Reverse the list
 ć                  # Extract the head; pop and push remainder-list and head separated
  U                 # Pop the head, and store it in variable `X`
                    # (`X` now holds the last letter)
   R                # Reverse the list back
v                   # Loop `y` over each remaining quartet:
 i                  #  If the top of the stack is 1 (it's an isolated or final form):
                    #  (which is always truthy for the first letter, since we pushed a 1 at the start)
  y2è               #   Get the initial form of `y`
     D              #   Duplicate it
      i             #   If it's 1, thus no initial form is available:
       yн           #    Push the isolated form of `y` instead
         s          #    And swap so the 1 is at the top for the next iteration
      ë             #   Else, thus an initial form is available:
       0            #    Push a 0 for the next iteration
 ë                  #  Else (it's an initial or medial form instead):
  yθ                #   Get the medial form of `y`
    DΘ              #   Duplicate it, and 05AB1E-truthify it (1 if 1; else 0)
    I               #   Push the input-list of codepoints again
     N>             #   Use the loop-index+1
       è            #   To index into this list for the next letter codepoint
        Ž6d         #   Push compressed integer 1569
           Q        #   And check if this next codepoint is equal to it (1 if truthy; 0 if falsey)
            ~i      #   If either of the two checks is truthy:
              \     #    Discard the duplicated medial form that's on the stack
               y1è  #    Get the final form of `y`
                  1 #    And push a 1 for the next iteration
             ë      #   Else (it's a medial, and the next character is NOT `ء` (U+0621)):
              0     #    Push a 0 for the next iteration
]                   # Close the loop and all inner if-else statements
 X                  # Push the last letter from variable `X`
  s_i               # If we ended with a 0 (thus an isolated or medial form)
     ¦              #  Remove the first item from `X`
    }н              # After the if-statement: pop and push the first item of `X`
                    # (so the isolated form if we ended with an isolated or final form,
                    #  or the final form if we ended with an initial or medial form)
)                   # Wrap all values on the stack into a list
 I                  # Push the input-list of codepoints again
  Ž6η               # Push compressed integer 1600
     DŠ             # Duplicate it, and triple swap (`®`,1600,1600 to 1600,`®`,1600)
       k            # Get the index of 1600 inside the codepoints list (-1 if not present)
        ǝ           # And insert the 1600 at that index in our created list
                    # (which doesn't work on negative indices)
                    # (after which this list of codepoint integers is output implicitly)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why ƵF is 116; Ž$§ is 25156; •7Ö›±ćY¨Γ∊%• is 35731296019285847629599; ƵB is 112; •7Ö›±ćY¨Γ∊%•ƵBв is [1,3,5,7,13,19,41,43,45,47,109,111]; Ž6d is 1569; or Ž6η is 1600.

JavaScript (ES6),  231 ... 148  146 bytes
I/O format: list of code points
a=>a.map(t=(c,i)=>c%32?(g=A=>n^c%49?g([x=n%32<26,k*x,x&=454642>>n++*25%54%26,x].map(x=>x&&++k)):A[t=t>1^2*(a[i+1]>1569)]||A[t^=2])(n=k=0)+65151:c)

Try it online!
a =>                             // a[] = input array
a.map(t = (c, i) =>              // for each code point c at position i in a[]:
  c % 32 ?                       //   if c is not 0x0640:
    ( g = A =>                   //     g is a recursive function taking a list A[]
        n ^ c % 49 ?             //       if we haven't reached the correct character:
          g(                     //         do a recursive call:
            [                    //           build a list describing the existence of:
              x = n % 32 < 26,   //           - isolated: if not in range 0x063B-0x0640
              k * x,             //           - final: same as isolated, except for the
                                 //             first entry which is undefined
              x &=               //           - initial: we use a lookup bit-mask
                454642 >> n++    //             with the following hash formula:
                * 25 % 54 % 26,  //               ((n * 25) mod 54) mod 26
              x                  //           - medial: same as initial
            ].map(x => x && ++k) //           turn it into a list of indices
          )                      //         end of recursive call
        :                        //       else:
          A[                     //         output the relevant entry from A[]:
            t =                  //           update t:
              t > 1 ^ 2 * (      //             (previous was initial or medial) XOR
                a[i + 1] > 1569  //             2 * (this is not the last letter
              )                  //             and the next letter is not 0x0621)
          ] ||                   //         if A[t] is not defined:
            A[t ^= 2]            //           use A[t ^ 2] instead
    )(n = k = 0)                 //     initial call to g with n = k = 0
    + 65151                      //     add 0xFE7F
  :                              //   else:
    c                            //     output c unchanged
)                                // end of map()


text:
Maintain diagonal symmetry when placing N items on a square grid
Write a program that takes in two non-negative integers S and N in that order. S represents the side length of a square grid of . characters. N represents the number of those .'s that need to be changed to x's. You may assume N is no greater than S squared.
Your program needs to output this S×S square of .'s and N x's but the requirement is that the square must always have a diagonal line of symmetry from its top left to its bottom right. Any grid arrangement is valid output as long as it has this symmetry.
For example, if S is 3 and N is 4 here are several grids that have this diagonal symmetry and would be valid output:
x.x
...
x.x

x..
.xx
.x.

...
.xx
.xx

The following grids however would not be valid:
.x.
xxx
...
(lacks diagonal symmetry)

..x
xx.
.x.
(has diagonal symmetry but not from the top left to the bottom right)

x.x
.x.
x.x
(incorrect number of x's)

This is code golf so the shortest program in bytes wins!
Details:

A trailing newline after the grid is fine.

You may use any two distinct printable-ASCII characters in place of . and x if you prefer.

If you prefer you may even output a binary-matrix instead of a string.

When N is 0 the output will be a pure S×S square of .'s with no x's.

When S is 0 the output will be an empty string (or single trailing newline).

The output does not need to be deterministic, as long as it is always guaranteed to be valid.

More Examples:
Not all valid arrangements are listed for each example input. Your output might look different yet still be valid.
S = 0, N = 0
[empty string]

S = 1, N = 0
.

S = 1, N = 1
x

S = 2, N = 0
..
..

S = 2, N = 1
x.
..

..
.x

S = 2, N = 2
x.
.x

.x
x.

S = 2, N = 3
xx
x.

.x
xx

S = 2, N = 4
xx
xx

S = 3, N = 2
x..
.x.
...

..x
...
x..

S = 4, N = 1
....
.x..
....
....

S = 4, N = 5
x..x
.x..
..x.
x...

xxx.
x...
x...
....

S = 5, N = 23
xxxxx
xxxxx
xxxxx
xxx.x
xxxx.

xxxxx
xxxxx
xxxxx
xxxx.
xxx.x

S = 7, N = 13
...x...
...x...
...x...
xxxxxxx
...x...
...x...
...x...

xxxxxxx
x......
x......
x......
x......
x......
x......

Can we return a 2D array or a flattened 1D array? Can we use 2 other distinct values instead of . and x?

This is a nice challenge but I think it would have been even better as binary-matrix rather than string. (Unless there are more clever ways of doing it with string manipulation than with matrix manipulation, but this seems a bit unlikely.)

@Arnauld Alright. Updated so both string and binary-matrix are valid. I'm just less familiar for the usual output formats allowed for those.

Python 2, 116 113 112 101 bytes
lambda s,n:[[[n>i<s-(s+n&1),[i*~-i+2*j,j*~-j+2*i][i<j]<n-s][j!=i]for j in range(s)]for i in range(s)]

Try it online!
Input: 2 integers s and n
Output: A 2D list of True and False, representing x and . respectively.
Explanation
The strategy is to put as many xs on the diagonal as possible.

If \$s\$ and \$n\$ has the same parity, then we can fill \$min(s,n)\$ diagonal squares.
If \$s\$ and \$n\$ has different parity, then we can fill \$min(s-1,n)\$ diagonal squares.

The remaining xs can be split symmetrically between the 2 triangular half of the grid. For the bottom triangle, we fill from top to bottom, where each row is filled left to right. The upper triangle mirrors the bottom triangle (fill left to right, each column from top to bottom)
Thus, we can determine if a square is filled just based on its indices \$(i,j)\$:

If \$i=j\$ (the square is on the diagonal), then that square is filled if \$i<n\$ and \$i<s-t\$, where \$t\$ is 0 or 1 depending on whether \$s\$ and \$n\$ have the same or different parity.
The following snippet evaluates to True or False if the diagonal square should be filled or not.

[n>i<s-(s+n&1), ...case when square is not diagonal... ][j!=i]

If \$i>j\$ (the square is in lower triangle), then the number of squares in the lower triangle before this square (in fill order) is \$m = \frac{i(i-1)}{2} + j\$. Thus if this square is filled, then the number of squares filled before it is \$2m = i(i-1)+2j\$. We need to make sure that \$2m<n-s\$, otherwise the diagonal cannot be filled to the maximum.
Similarly, if \$i>j\$, then we fill if \$j(j-1)+2i<n-s\$.
The following snippet evaluates to True or False if the non-diagonal square is filled or not:

[i*~-i+2*j,j*~-j+2*i][i<j]<n-s

Combined together, this big expression evaluates to whether a square \$(i,j)\$ should be filled:
[n>i<s-(s+n&1),[i*~-i+2*j,j*~-j+2*i][i<j]<n-s][j!=i]

Thanks @ovs for saving 4 bytes in a previous solution!

g=eval(`s*[s*["."]]`) is the same length for your third line, after that you can save 4 bytes by not assigning R.

@ovs That's amazing! Thanks!

@JonathanFrech unfortunately that doesn't work. :( I need the negation to happens before the division, which only happens if the - is unary.

Oh, I remember now ... sorry for the inconvenience!

Np, I appreciate the attempt.

JavaScript (ES6),  116 114  110 bytes
Takes input as (s)(n). Returns a matrix of Boolean values.
s=>n=>[...Array(s)].map((_,y,a)=>a.map((_,x)=>(p=Math.min(n&~1,s*s-s),x-y?(x<y?y*y-y+2*x:x*x-x+2*y)<p:x<n-p)))

Try it online!
How?
The output matrix is divided into 2 parts:

the cells located on the main diagonal (type A)
all other cells (type B)

Whenever a type-B cell is set, its symmetrical counterpart must be set as well. We want to set as many type-B cells as possible and this number is given by:
$$p_{n,s}=\min\left(2\left\lfloor\frac{n}{2}\right\rfloor,s(s-1)\right)$$
The number of type-A cells is therefore given by:
$$q_{n,s}=n-p_{n,s}$$
We define \$T(k)\$ as the \$k\$-th triangular number:
$$T(k)=\frac{k(k+1)}{2}$$
To figure out whether the type-B cell at \$(x,y)\$ must be set or not, we assign it the following ID and compare it with \$\dfrac{p_{n,s}}{2}\$:
$$\begin{cases}
T(y-1)+x,&\text{if $x<y$}\\
T(x-1)+y,&\text{if $x>y$}\\
\end{cases}$$
Example for \$s=5\$:
$$\begin{pmatrix}
-&0&1&3&6\\
0&-&2&4&7\\
1&2&-&5&8\\
3&4&5&-&9\\
6&7&8&9&-
\end{pmatrix}$$
To figure out whether the type-A cell at \$(x,x)\$ must be set or not, we simply use \$x\$ as its ID and compare it with \$q_{n,s}\$.
Example for \$s=5\$:
$$\begin{pmatrix}
0&-&-&-&-\\
-&1&-&-&-\\
-&-&2&-&-\\
-&-&-&3&-\\
-&-&-&-&4
\end{pmatrix}$$

Why are you calling "anti diagonal" to the main diagonal?

@RGS Probably because I'm currently working on a new Chess engine and was thinking 'anti-diagonal of the board'. :-) Fixed.

Fair enough! Will said engine end up online? Can I follow its development?

@RGS This is just a very early prototype. At this point, I'm not even sure it's going to work as expected. But I'll ping you If something goes online.

ok, I'll be waiting for it ;)

MATL, 21 20 bytes
U:<~Zc`tnZ@)[]ett!-z

Try it online!
Characters are # and . The output is random, that is, it may be different every time the program is run. Running time is also random, but the program is guaranteed to finish in finite time.
How it works
General idea
The code first generates a numeric vector with N ones and S^2-N zeros (U:<~), and transforms it into a string replacing 1 and 0 by the two mentioned characters (Zc). Then, a random permutation is applied (tnZ@)) , the result is reshaped into a square matrix of characters ([]e), and this is repeated (`) until the matrix equals its transpose (t!-z), while leaving a copy (t) for the next iteration or as final result.
Detailed steps
U        % Input (implicit): S. Push S^2
:        % Range [1 2 ... S^2]
<~       % Input (implicit): N. Greater-or-equal, element-wise. Gives
         % [1 1 ... 1 0 0 ... 0] with N ones and S^2-N zeros
Zc       % String where 1 becomes '#'  and 0 becomes space
`        % Do...while
  tn     %   Duplicate. Number of elements. Gives S^2
  Z@     %   Random permutation of the integers 1, 2, ..., S^2
  )      %   Apply as an index. This shuffles the previous string
         %   or char matrix, and gives a string as result
  []e    %   Reshape as a square matrix of chars
  tt!    %   Duplicate twice, and transpose the second copy
  -      %   Subtract element-wise
  z      %   Number of nonzeros. This is the loop condition. The loop
         %   is exited when the result is 0, meaning that the matrix
         %   and its transpose are equal
         % End (implicit)
         % Display (implicit). The stack contains a copy of the latest
         % matrix of chars, which is the first that was found to
         % satisfy the symmetry condition

Wolfram Language (Mathematica), 113 bytes
Searches random matrices [S,N] until matrix g is equal to Transpose(g)
Outputs a binary matrix
If[#<1,"",g=(P=Partition)[k=Join@@{1~Table~#2,Table[0,#^2-#2]},#];While[g!=Transpose@g,g=P[RandomSample@k,#]];g]&

Try it online!
Wolfram Language (Mathematica), 75 bytes
Here is also a deterministic version that searches all possible matrices
(it works only up to 4x4 due to memory limitations)
If[#<1,"",x=#2;Select[{0,1}~Tuples~{#,#},#==Transpose@#&&Tr[Tr/@#]==x&,1]]&

Try it online!
-2 bytes by @my pronoun is monicareinstate

You're now allowed to output a binary matrix.

@Arnauld thanks for letting me know!

Select takes a third argument - the number of elements to choose (1 here); 75 bytes: Try it online! Is the #<1 check really necessary?

@mypronounismonicareinstate yes, you are right. the #<1 check is necessary : "When S is 0 the output will be an empty string"

Bash + Unix utilities, 152 bytes
a=`dc<<<4dk$2*1+v1-2/0k1/p`
for((q=$2-a*a-a,b=++a<$1?q/2:0;i<$1;++j>=$1?j=0,i++:0)){ printf $[i-j?i<a&j<a?1:i==a&j<b|j==a&i<b?1:0:i<q-2*b?1:0]\ ;}|rs $1

Try the test suite online!
\$S\$ and \$N\$ are read from stdin, and the output is printed to stdout.  The characters used are 0 and 1 (for (for . and x, respectively).
This program prints a space between successive characters, which I think looks better (the grids are more squarish and easier to read), and it saves me a byte.  If that's not acceptable, use fold instead of rs as follows (for 153 bytes):
a=`dc<<<4dk$2*1+v1-2/0k1/p`
for((q=$2-a*a-a,b=++a<$1?q/2:0;i<$1;++j>=$1?j=0,i++:0)){ printf $[i-j?i<a&j<a?1:i==a&j<b|j==a&i<b?1:0:i<q-2*b?1:0];}|fold -$1

How it works:
First we use dc to compute $$a=\left\lfloor\frac{\sqrt{4N+1}-1}{2}\right\rfloor.$$
You can check that \$a\$ is the greatest integer such that \$a(a+1) \leq N.\$  The reason this is useful is that $$a(a+1)=2(1+2+\dots+a).$$
The for loop that comes next runs through each position \$(i, j)\$ where each of the variables goes from \$0\$ to \$S-1.\$  It prints a 0 or a 1 for each \$(i,j)\$.
For convenience, \$a\$ is incremented during the for loop initialization, so it's actually \$1\$ higher than the above value during the body of the loop.
The following entries are filled in with 1s (the others are all 0s):
(1) Fill in each \$(i,j)\$ where \$0 \le i \lt a\$ and \$0 \le j \lt a.\$
(2) If \$a<S\$ (so that there's at least one row and one column left untouched still), fill in the entries at positions \$(a,i)\$ and \$(i,a)\$ (starting from \$i=0\$ and keeping \$i\$ below \$a-1\$), up to the number of additional entries that are still needed after step 1. These are always entered in pairs.
(3) If we still haven't marked enough entries (which can happen because we ran out of room off the main diagonal, or simply because we needed to mark an odd number of entries, but everything so far has been in pairs), then fill in entries \$(i,i)\$ on the main diagonal, starting at \$i=0,\$ until we've filled in the right number of 1s.
Finally, the rs (or fold) at the end formats it all as a square array.

Perl 5, 139 bytes
sub f{($s,$n)=@_;$_='-'x$s x$s;$i=-1;while($n){$j=++$i%$s*$s+int$i/$s;$n<2&&$i-$j&&next;for$o($i,$j){$n-=s,^(.{$o})-,$1x,}}s/.{$s}/$&\n/gr}

Try it online!
sub fungolfed {
  ($s,$n) = @_;                     # input params s and n
  $_ = '-' x $s x $s;               # $_ is the string of - and x
  $i=-1;                            # start at position i=0, due to ++ below
  while($n){                        # while more x's to place (n>0)
    $j = ++$i % $s * $s + int$i/$s; # j is the symmetrical position of i
    $n<2 && $i-$j && next;          # place x only in diagonal if one x left (n=1)
    for $o ($i,$j){                 # place x at positions i and j
      $n -= s/^(.{$o})-/$1x/        # ...and decrease n if - was replaced by x
                                    # ...that is if the position was not aleady x
    }
  }
  s/.{$s}/$&\n/gr                   # put \n after each s'th char and return that
}

Test:
for my $s (0..7){
  for my $n (0..$s*$s){
    print "\n__________________ s=$s n=$n\n";
    print f($s,$n) =~ s/./$& /gr;                 }  }

Part of the output:
__________________ s=3 n=0
- - -
- - -
- - -
__________________ s=3 n=1
x - -
- - -
- - -
__________________ s=3 n=2
x - -
- x -
- - -
__________________ s=3 n=3
x x -
x - -
- - -
__________________ s=3 n=4
x x -
x x -
- - -
__________________ s=3 n=5
x x x
x - -
x - -
__________________ s=3 n=6
x x x
x x -
x - -
__________________ s=3 n=7
x x x
x x -
x - x
__________________ s=3 n=8
x x x
x x x
x x -
__________________ s=3 n=9
x x x
x x x
x x x

PowerShell, 153 140 136 bytes
param($l,$n)if($l--){0..$l|%{$y=$_
-join(0..$l|%{$n-=$a=($_-eq$y-and$n)+2*($_-gt$y-and$n-gt1)
'.x'["$y;$_"-in($c+=,"$_;$y"*$a)-or$a]})}}

Try it online!
Unrolled:
param($length,$n)
if($length--){
    0..$length|%{
        $y=$_
        -join(0..$length|%{
            $draw = 1*($_ -eq $y -and $n) +         # draw 1 element on the diagonal
                    2*($_ -gt $y -and $n -gt 1)     # draw 2 elements in the corners
                                                    # or draw 0 elements (draw field char '.')
            $n-=$draw                               # reduce the number of drawing elements
            $coordCache += ,"$_;$y" * $draw         # add one element or two identical elements
            '.x'[$draw -or "$y;$_" -in $coordCache] # draw element directly or draw from cache
        })
    }
}

Charcoal, 39 bytes
ＮθＮηＧ←↑⊖θ.ＵＭ✂ＫＡ⁰⊘η¹x↑‖Ｍ↗Ｐ↘⭆θ§.x›η⁺ι№ＫＡx

Try it online! Link is to verbose version of code. Explanation:
ＮθＮη

Input S and N.
Ｇ←↑⊖θ.

Fill a triangle of size S-1 with .s.
ＵＭ✂ＫＡ⁰⊘η¹x

Change up to N/2 of those .s to xs.
↑‖Ｍ↗

Reflect to create the diagonal symmetry, but leaving the diagonal empty.
Ｐ↘⭆θ§.x›η⁺ι№ＫＡx

Count the number of xs and complete the diagonal using xs and .s as necessary to end up with N xs.

Ruby, 97 bytes
->s,n{t=(?.*s+$/)*s
i=1
(t[i*-~s/s]=t[i/s-i%s*~s]=?X;i+=1)until 2>m=n-t.count(?X)
m>0&&t[0]=?X
t}

Try it online!
Llamda function. Returns a newline separated string with X and . can be shorter if a single line string is acceptable.
Very simple:

Make a newline separated string of s lines of s .
Set i=1 and scan through all indexes of i interpreting this as both [row-then-column] and [column-then-row] and change the relevant . to X . The total number of X added per iteration will be 1 if it is the cell is on the diagonal, and either 2 or 0 if it is not, depending on whether the cells already contain X.
End the loop when less than 2 more X need to be added.
If there is still one X to be added, put it at top left (index 0)
Return the string