text:
Complete the Magic Square
Background
A magic square is an n×n matrix consisting of one of each of the integers from \$1\$ to \$n^2\$ where every row, column, and diagonal sum to the same value. For example, a 3×3 magic square is as follows:
4 9 2
3 5 7
8 1 6

Here, each row, column, and diagonal sum to the magic sum of 15, which can be calculated with the following formula:
$$
n × \frac{n^2 + 1}{2}
$$
Even if you didn't have the full n×n magic square, you could reproduce it without guessing. For example, given just the 4, 9, 2, and 3 of the prior magic square, you could fill
4 9 2    4 9 2    4 9 2    4 9 2    4 9 2    4 9 2
3 _ _ => 3 _ _ => 3 5 _ => 3 5 7 => 3 5 7 => 3 5 7
_ _ _    8 _ _    8 _ _    8 _ _    8 1 _    8 1 6

Task
Given a partially-filled magic square, your program or function should output the full magic square.
The input is guaranteed to be part of of a magic square, such that the only deduction necessary to solve it is taking a row, column, or diagonal in which n-1 values are determined and filling in the final entry (without this rule, 4 9 _ / _ _ _ / _ _ _ would be a valid input since only one magic square starts 4 9, but that would require a more complicated approach or a brute-force of all possibilities).
Input and output may be any reasonable format for a square matrix (n×n matrix datatype; string representations; length-n×n flat array; etc.). In all formats, you may optionally take n as another input.
You may use any character or value other than _ in the input to represent blanks as long as that value is unmistakable for a possible entry.
Related decision-problem variant: Is Magic Possible?
Sample Testcases
(one newline between input and output; three between cases)
4 9 2
3 5 7
8 1 6

4 9 2
3 5 7
8 1 6

4 9 2
3 _ _
_ _ _

4 9 2
3 5 7
8 1 6

4 9 _
_ 5 _
_ _ _

4 9 2
3 5 7
8 1 6

_ _ _
_ 5 7
_ 1 6

4 9 2
3 5 7
8 1 6

_   16  13  _
11  5   _   _
7   9   12  6
_   _   _   15

2   16  13  3
11  5   8   10
7   9   12  6
14  4   1   15

1   23  _   4   21
15  14  _   18  11
_   _   _   _   _
20  8   _   12  6
5   3   _   22  25

1   23  16  4   21
15  14  7   18  11
24  17  13  9   2
20  8   19  12  6
5   3   10  22  25

In your second last example, how are n-1 values determined?

@J42161217 Fixed. It should now be possible and require a diagonal deduction.

MATL, 36 bytes
`nZ@[]etGg)GXz-yt!hs&ytXdwPXdhsh&-ha

The input is an \$ n \times n\$ matrix, with \$0\$ for the unknown numbers.
The code keeps generating random \$ n \times n\$ matrices formed by the numbers \$1, \dots, n^2\$ until one such matrix meets the required conditions. This procedure is guaranteed to finish with probability one.
This is a terrible approach, in that:

running time is random, and unbounded;
average running time increases as \$(n^2)!\$ (that's more than exponentially);
and so it very likely times out in the online interpreter.

... but hey, it's the shortest answer so far!
(Don't) try it online.
See below a sped-up animated GIF of an example run which happened to take about 2 minutes, here compressed to a few seconds.

Explanation
`         % Do...while
  n       %   Number of elements. This implictly takes the input in the first
          %   iteration, or uses the candidate solution from the previous iteration.
          %   Let this number be denoted as N
  Z@      %   Random permutation of integers 1, 2, ..., N
  []e     %   Reshape as a square matrix. This yields a candidate solution
  t       %   Duplicate
  Gg)     %   Push input, convert to logical, index: this produces a column vector
          %   of the entries of the candidate solution that correspond to nonzero
          %   entries in the input matrix
  GXz     %   Push input, take its nonzero elements. Gives a column vector
  -       %   Element-wise difference (*). This will be all zeros for a valid
          %   solution
  y       %   Duplicate second-top object from the stack, that is, the candidate
          %   solution
  t!      %   Duplicate, transpose
  h       %   Concatenate horizontally
  s       %   Sum of columns. This also gives the sum of rows, thanks to the
          %   concatenated, transposed copy. The result is a two-element row
          %   vector (**)
  &y      %   Duplicate third-top object from the stack: the candidate solution
  tXd     %   Duplicate, extract diagonal as a column vector
  wPXd    %   Swap, flip vertically, extract diagonal. This gives the anti-diagonal
          %   as a column vector
  h       %   Concatenate horizontally
  s       %   Sum of each column. This gives the sum of the diagonal and that
          %   of the anti-diagonal
  h       %   Concatenate horizontally with (**)
  &-      %   Matrix of all element-wise differences. This will be a matrix of
          %   zeros for a valid solution (***)
  h       %   Concatenate (*) and (***) horizontally. Since sizes do not match,
          %   both (*) and (***) are first linearized to row vectors, and the
          %   result is a row vector
  a       %   Any. This gives true if any element is non-zero
          % End (implicit). A new iteration is run if the top of the stack is true
          % Display (implicit). The candidate solution from the last iteration is
          % the valid solution

If it isn't guaranteed to solve the problem, is it a valid solution?

@GirkovArpa It is allowed because it terminates with probability 1, unless the challenge explicitly says otherwise.

That's an interesting discussion in the first link, thanks for clarifying.

@Bubbler Thank you. I forgot to mention that. Edited

The GIF is a nice addition.

@GirkovArpa Not as nice as your embedded code snippet :-)

JavaScript, 559 551 bytes
Fast and methodical.
B=Boolean,f=((e,r)=>(v=r*((r**2+1)/2),e.forEach(e=>e.filter(B).length==r-1?e[e.findIndex(e=>!e)]=v-e.reduce((e,f)=>!(e+=f)||e):0),e[0].reduce((f,l,n)=>!(f[0].push(e[n][n])+f[1].push(e[n][r-1-n]))||f,[[],[]]).forEach((f,l)=>{f.filter(B).length==r-1&&(z=f.findIndex(e=>!e),e[z][l?r-1-z:z]=v-f.reduce((e,f)=>!(e+=f)||e))}),e[0].reduce((f,r,l)=>f.forEach((f,r)=>f.push(e[l][r]))||f,new Array(r).fill().map(()=>[])).forEach((f,l)=>f.filter(B).length==r-1?e[f.findIndex(e=>!e)][l]=v-f.reduce((e,f)=>!(e+=f)||e):0),e.flat(2).filter(B).length==r*r?e:f(e,r)));

Live examples:

B=Boolean,f=((e,r)=>(v=r*((r**2+1)/2),e.forEach(e=>e.filter(B).length==r-1?e[e.findIndex(e=>!e)]=v-e.reduce((e,f)=>!(e+=f)||e):0),e[0].reduce((f,l,n)=>!(f[0].push(e[n][n])+f[1].push(e[n][r-1-n]))||f,[[],[]]).forEach((f,l)=>{f.filter(B).length==r-1&&(z=f.findIndex(e=>!e),e[z][l?r-1-z:z]=v-f.reduce((e,f)=>!(e+=f)||e))}),e[0].reduce((f,r,l)=>f.forEach((f,r)=>f.push(e[l][r]))||f,new Array(r).fill().map(()=>[])).forEach((f,l)=>f.filter(B).length==r-1?e[f.findIndex(e=>!e)][l]=v-f.reduce((e,f)=>!(e+=f)||e):0),e.flat(2).filter(B).length==r*r?e:f(e,r)));

console.log(JSON.stringify(f([
  [4, 9, 2],
  [0, 5, 0],
  [0, 0, 0]
], 3)));

console.log(JSON.stringify(f([
  [1, 23, 0, 4, 21],
  [15, 14, 0, 18, 11],
  [0, 0, 0, 0, 0],
  [20, 8, 0, 12, 6],
  [5, 3, 0, 22, 25]
], 5)));

The "un"-golfed version can be seen at this Github repository.

APL (Dyalog Unicode), 60 bytes
{(⍵,m+.×1+⍺*2)⌹(∘.(×⊢×=)⍨⍵)⍪2×m←(⍪↑c(⌽c))⍪(⊢⍪⍴⍴⍉)⍺/c←∘.=⍨⍳⍺}

Try it online!
Not likely the shortest approach, but anyway here is one with Matrix Divide ⌹, a.k.a. Solve Linear Equation. This works because all the cells are uniquely determined by the horizontal/vertical/diagonal sums when joined with the givens. ⌹ has no problem with over-determined systems, as long as there is a solution (otherwise, it finds the least-squares fit).
A dyadic inline function (dfn) where the left argument is the side length and the right argument is the flattened matrix.
In the case of [4 9 2][3 0 0][0 0 0], the coefficient matrix and constant vector are given as follows:
Coefficients        Constants
-------------------------------
Part 1: Givens
1 0 0 0 0 0 0 0 0   4
0 1 0 0 0 0 0 0 0   9
0 0 1 0 0 0 0 0 0   2
0 0 0 1 0 0 0 0 0   3
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0

Part 2: Magic Square sums
2 0 0 0 2 0 0 0 2   30  # diagonals
0 0 2 0 2 0 2 0 0   30
2 2 2 0 0 0 0 0 0   30  # rows
0 0 0 2 2 2 0 0 0   30
0 0 0 0 0 0 2 2 2   30
2 0 0 2 0 0 2 0 0   30  # columns
0 2 0 0 2 0 0 2 0   30
0 0 2 0 0 2 0 0 2   30

which is a set of 17 equations for 9 unknowns.
{(⍵,m+.×1+⍺*2)⌹(∘.(×⊢×=)⍨⍵)⍪2×m←(⍪↑c(⌽c))⍪(⊢⍪⍴⍴⍉)⍺/c←∘.=⍨⍳⍺}

m←(⍪↑c(⌽c))⍪(⊢⍪⍴⍴⍉)⍺/c←∘.=⍨⍳⍺  ⍝ Construct the sums part of the coef matrix
                     c←∘.=⍨⍳⍺  ⍝ ⍺ × ⍺ identity matrix
                   ⍺/  ⍝ ⍺ copies of each horizontally, giving the "rows" part
            (  ⍴⍴⍉)    ⍝ Reshape the transpose of above into the original,
                       ⍝ giving the "columns" part
             ⊢⍪        ⍝ Vertically concatenate two parts
m←(⍪↑c(⌽c))⍪  ⍝ Generate the "diagonals" part and vertically prepend to above

(∘.(×⊢×=)⍨⍵)⍪2×m  ⍝ Construct the entire coef matrix
             2×m  ⍝ Use twos so that we can avoid halving the constant
(          )⍪     ⍝ Vertically concatenate with...
 ∘.(×⊢×=)⍨⍵       ⍝ The square diagonal matrix where nonzero entries of ⍵ give
                  ⍝ a 1 at the corresponding position, 0 otherwise

(⍵,m+.×1+⍺*2)  ⍝ Construct the constant vector
       1+⍺*2   ⍝ Square of ⍺ plus 1
   m+.×        ⍝ Matmul with m, which has ⍺ ones on each row,
               ⍝ giving (# of rows of m) copies of ⍺ times above
 ⍵,            ⍝ Prepend ⍵ to above

⌹  ⍝ Solve the linear system of equations; no postprocessing necessary

JavaScript (ES7),  143 142  140 bytes
Expects (n)(m), where unknown cells in m are filled with 0's.
n=>g=m=>[0,1,2,3].some(d=>m.some((r,i)=>m.map((R,j)=>t^(t-=(v=d?R:r)[x=[j,i,j,n+~j][d]])||(e--,X=x,V=v),e=1,t=n**3+n>>1)&&!e))?g(m,V[X]=t):m

Try it online!
Commented
n =>                          // outer function taking n
  g = m =>                    // inner function taking the matrix m[]
    [0, 1, 2, 3]              // list of directions
    .some(d =>                // for each direction d:
      m.some((r, i) =>        //   for each row r[] at position i in m[]:
        m.map((R, j) =>       //     for each row R[] at position j in m[]:
          t ^ (               //       test whether t is modified:
            t -=              //         subtract from t:
              (v = d ? R : r) //           use v = r[] if d = 0 or v = R[] otherwise
              [x =            //           use:
                [ j,          //             r[j] if d = 0 (rows)
                  i,          //             R[i] if d = 1 (columns)
                  j,          //             R[j] if d = 2 (diagonal)
                  n + ~j      //             R[n - 1 - j] if d = 3 (anti-diagonal)
                ][d]          //
              ]               //
          ) || (              //       if t was not modified:
            e--,              //         decrement e
            X = x,            //         copy x to X
            V = v             //         copy v to V
          ),                  //
          e = 1,              //       start with e = 1
          t = n**3 + n >> 1   //       start with t = n(n²+1)/2
        )                     //     end of map()
        && !e                 //     e = 0 means that there's exactly one cell set
                              //     to zero in this vector
      )                       //   end of inner some()
    ) ?                       // end of outer some(); if truthy:
      g(m, V[X] = t)          //   update V[X] to t and do a recursive call
    :                         // else:
      m                       //   done: return m[]

You beat my entry by a lot!  What does n+~j do?

@GirkovArpa For 32-bit integers, n+~j is essentially the same as n-j-1, saving a byte.

Brachylog, 47 44 bytes
{0∧|}ᵐ²{l⟦₅gj↔ʰc;?z∋₍ᵐġ,?;?\ᵗc+ᵐ=&c≠≤ᵛ√~l?≜}

Try it online!
How it works
In classic Prolog style we replace zeros with uninitiated variables and based on the constraints let Brachylog figure out a solution. In Prolog you could just write [1,_,_] for unknown variables, in Brachylog you would have to write [1,A,B] and that seems too far away from the usual I/O restriction. So we use 0 for unknowns and convert them to uninitiated variables by:
{∧0|}ᵐ²

If a value is 0 try something else, otherwise use the value itself.
l⟦₅gj↔ʰc;?z∋₍ᵐ
l               length of array, N
 ⟦₅             0…N-1
   gj           [0…N-1],[0…N-1]
     ↔ʰc        0…N-1,N-1…0
        ;?z     [[0,first row], …, [N-1,last row],
                 [N-1,first row], …, [0,last row]]
           ∋₍ᵐġ [diagonal \, diagonal /]

This feels a bit long just to get the two diagonals. Basically calculate the indices, zip them with the rows, and get the elements.
,?;?\ᵗc

Append all rows and all transposed rows.
+ᵐ=

Sum every row. All sums (f.e. 15 in the 3x3 case) must be equal to each other. We don't have to calculate 15 explicitly, as this follows from the next constraint:
&c≠≤ᵛ√~l?
 c            the rows concatenated
  ≠           all elements are different
   ≤ᵛ         and are less-equal than X,
     √        and the root of X is
      ~l?     the length of the input
              which is implicitly the output

The numbers are distinct and between 1 and N^2.

R, 169 180 142 135 bytes
Edits: +11 bytes to rotate the magic square back to it's original orientation, -38 bytes by wrapping "replace-only-missing-element" into a function, -7 bytes by various golf obfuscations
function(m,n){while(F%%4|sum(!m)){m[n:1,]=apply(m,1,f<-function(v){if(sum(!v)<2)v[!v]=(n^3+n)/2-sum(v);v})
m[d]=f(m[d<-!0:n])
F=F+1}
m}

Try it online!
Solves rows & the first diagonal, then rotates the matrix anticlockwise (so cols become rows in the opposite order) and repeats, until there are no empty elements left.
Outputs the completed magic-square matrix in one of 4 possible rotated forms.  Then rotates matrix back to its original orientation.
Commented readable version:
solve=function(m,n){
    t=(n^3+n)/2                         # t = desired total of each row/col/diag
    f=function(v){                      # f = function to check if a vector
        if(sum(!v)==1)v[!v]=t-sum(v);v  # has only 1 missing element, and if so
    }                                   # fill it with t-sum(elements).
    while(F%%4|sum(!m)){                # While rotations are not multiple-of-4, or
                                        # there are still some empty elements of m:
        m[n:1,]=                        # rotate the matrix anticlockwise, while
            apply(m,1,f)                # using f() to fix any rows; then
        d=1:(n+1)==1                    # define diagonal as every (n+1)th element,
        m[d]=f(m[d])                    # and use f() to fix diagonal.
        F=F+1                           # Count rotations so far,
    }                                   # and repeat.
    m                                   # Finally, output m.
}

or awfully-slow R, 124 123 109 105 bytes
Edit: -14 bytes thanks to Xi'an
function(m,n){x=m;`?`=rowSums;while(any(sum(x[0:n<1])!=c(sum(diag(x)),?x,?t(x))))x[!m]=sample(n^2)[-m];x}

Try it online!
Generates random permutations of the missing elements until it finds one where all row, column and diagonal sums are all equal.

Swapping rows and columns takes the main diagonal to the main diagonal, so this would never solve the 5th case mirrored across a vertical line

Plus, the output matrix should be in the same orientation as the original square. The partially-filled square has some entries given, so those entries should be in the same location in the output

@fireflame241 note that the function really rotates the matrix, rather than just transposing it (which would be simply swapping rows and columns), so it does exchange the two diagonals.

@fireflame241 I was cheekily hoping that a rotated version of the same matrix was Ok as a 'reasonable' output format for a square matrix, but I realized that this was probably not what was expected (which was why I mentioned it).  I'll amend it to output the original rotation...

suggested edit: "with the matrix rotated (so rows are now cols In the opposite order)"

@fireflame241 Amended (at a cost of +11bytes) to rotate the matrix so that it is consistent with its original orientation.

@LuisMendo It does now (at considerable expense of length, but still shorter than the deductive version).  Thanks for pointing this out: I've now learned a lot about semi-magic squares...!

@DominicvanEssen Glad I could "help" :-)

Defining rowSums in advance and using sample(n) rather than sample(1:n) produces some further gain: the body of the R function reduces to x=m;a=rowSums;while(any(sum(x[1:(n+1)<2])!=c(sum(diag(x)),a(x),a(t(x)))))x[!m]=sample(n^2)[-m];x

Thanks very much!  And also for pointing out diag() to replace my clunky calculation of the diagonal indices.  I've amended the answer with acknowledgment (and defining rowSums was even able to save 2 more bytes by replacing the unary ? operator).

I don't think that would work: sum() is only used twice (=8 bytes), and replacing it would cost 8 (,`~`=sum), as well as 2x 1 byte each time the replacement was used.

I think that's break-even: 105 bytes (current answer without substituting sum) and your version of 105 bytes (substituting sum)...  (and I made a mistake in the earlier comment: 2x sum() is obviously 10 bytes, not 8, so 8+2x1 could be expected to break-even).

05AB1E, 43 41 30 bytes
-2 bytes by replacing Dgt with ¹ to get first input back
-11 bytes thanks to Kevin Cruijssen!
nLœʒ¹ôD©ø®Å\®Å/)O˜Ë}ʒøε¬_sË~}P

Try it online!
Takes input as (n, flattened square), where zeros represent blanks, like
3
[4,9,2,3,0,0,0,0,0]

Works by generating all permutations of the numbers from 1 to n2, filtering to only keep those that are magic squares, and then iterating through and printing all that match the partial input (by input constraints, there will always only be one match). Because of this brute-force approach, it's already very slow for 3x3 magic squares and I doubt 5x5 would terminate. This is my first 05AB1E answer, so I'm sure there's savings to be had here.
The magic square checking is borrowed from Kevin Cruijssen.
Explanation:
n      # Square input (implicit) (3 → 9)
 L     # Generate list from 1 to n^2 ([1,2,...,9])
  œ    # All permutations
   ʒ   # Filter by:
¹       # Recover n by pushing first input again
        # Check if magic square, borrowed from Kevin Cruijssen
 ô      # Split permutation into parts of size n
  D     # Duplicate
   ©    # Store in register (without popping)
    ø   # Zip rows to get columns
®       # Push from register
 Å\     # Take main diagonal
®       # Push from register
 Å/     # Take anti diagonal
)       # Flatten stack into one list
 O      # Take sum (of each row/column/diagonal)
  Ë     # Check if all values are equal
     } # End filter (to get magic squares)
ʒ      # Filter magic squares by:
 ø      # Zip together magic square and input (implicit)
ε       # Map
 ¬       # Push the input again
  _      # Input equals 0 (to produce mask)
s        # Manage stack (swap mask and zipped args)
 Ë       # Partial equals potential match
  ~      # Bitwise OR to combine masks
    }   # End map
P      # Take product (effectively logical AND) to verify
       # that combined mask is all 1s
      # Implicit output

Nice first 05AB1E answer! :) I've golfed 3 bytes in my answer just yet, so you can do the same change: ¹ô©O®øO®Å\O®Å/O) to ¹ôD©ø®Å\®Å/)O (I basically golfed the individual sums to one after we've wrapped the lists into a list). As for some other golfs: 1) You can remove the D in vDyø, since it will use the input implicitly. 2) 0Q has a builtin _. 3) .«& has a builtin P (product). 4) You now loop and print, but you could remove the if-statement and use a second filter instead: vy becomes ʒ and iy, is removed. In total: 30 bytes.

Nice! Thanks for the tips -- looks like I need to familiarize myself with the builtins a bit more for next time.

Wolfram Language (Mathematica), 100 bytes
#/.Solve[Tr/@Flatten[{#,Thread@#,{(d=Diagonal)@#,d@Reverse@#}},1]==Table[(l^3+l)/2,2(l=Tr[1^#])+2]]&

Try it online!

Jelly, 25 bytes
ZṚ,⁸;Jị"$€$§FE
²Œ!ṁ€ÇƇ=ÐṀ

A full program taking n and a list-of-lists-formatted representation of the incomplete square which prints the result in the same format.
Try it online! - too slow for TIO's 60s limit
...so, Try a limited space one which only considers the first 150K permutations - three magic squares two of which match at two and three locations.
How?
Unfortunately, even with the ability to deduce the missing numbers one at a time, I believe brute-forcing will be terser, so that is how this works.
ZṚ,⁸;Jị"$€$§FE - Link 1, Is this a magic-square?: list of lists, M
Z              - transpose (M)
 Ṛ             - reverse (together ZṚ rotate 1/4)
  ,⁸           - pair with chain's left argument (M)
          $    - last two links as a monad:
         €     -   for each (m in (MZṚ, M)):
        $      -     last two links as a monad:
     J         -       range of length = [1..n]
       "       -       zip with:
      ị        -         index into - i.e. get the leading diagonal
    ;          -   concatenate (m with it's diagonal)
           §   - sums
            F  - flatten
             E - all equal?

²Œ!ṁ€ÇƇ=ÐṀ - Main Link: integer, N; list of lists, P
²          - square (n)
 Œ!        - all permutations of (implicit range [1..n²])
   ṁ€      - mould each like (P)
      Ƈ    - filter keep those for which:
     Ç     -   call the last Link as a monad  - i.e. keep magic squares
        ÐṀ - keep those which are maximal under:
       =   -   equals (P) (vectorises) - i.e. keep the one which matches at all givens
           - implicit print, which when given a list containing only one item prints that item

Charcoal, 81 bytes
ＦθＦι⊞υκＵＭθκ≔ＬθηＦυＦ⁺⁺⪪ＥυληＥθ⁺λ×θη⟦×θ⊕η×⊕θ⊖η⟧«≔Ｅκ§υλι¿⁼¹№ι⁰§≔υ§κ⌕ι⁰⁻÷×⊕×ηηη²Σι»Ｉ⪪υη

Try it online! Link is to verbose version of code. Uses zero as the "blank" marker. Explanation:
ＦθＦι⊞υκ

Flatten the input array.
ＵＭθκ

Replace the original array with a range from 0 to n-1.
≔Ｌθη

Also the length of the array is used a lot so capture it in a temporary to save 3 bytes.
Ｆυ

Loop n² times, which is more than enough to track down all the solvable 0s.
Ｆ⁺⁺

Loop over all of the following ranges:
⪪Ｅυλη

the range from 0 to n²-1, split into subranges of length n;
Ｅθ⁺λ×θη

the subranges obtained from the range from 0 to n²-1, but taking every nth element (so effectively the transpose of the above);
⟦×θ⊕η×⊕θ⊖η⟧«

the range from 0 to n²-1 in steps of n+1, which is the main diagonal, and the range from n-1 to n²-n in steps of n-1, which is the main antidiagonal.
≔Ｅκ§υλι

Get the values in the flattened array corresponding to the elements of the current range.
¿⁼¹№ι⁰

Count whether exactly one of them is zero.
§≔υ§κ⌕ι⁰

If so then overwrite that entry in the flattened array...
⁻÷×⊕×ηηη²Σι

... with ½n(n²+1) minus the sum of the (other) elements.
»Ｉ⪪υη

Split the flattened array back into rows and convert the values to strings for implicit print.

authors: Xi'an ні війні


text:
Cleaning up decimal numbers
Background
Sometimes in calculus you're expected to calculate the sum of an infinite series. Sometimes these series are very friendly, like a geometric series, but add anything else onto it and it can quickly get complicated to solve by hand.
Sometimes I like to be lazy - a lot of sums can be found simply by adding the first few terms then making an approximation. Say the sum of the first ten terms is 0.199999983, and the future terms are approaching zero. We can say with a fair degree of certainty that our final answer will be 0.2, or 1/5.
The Challenge
Given a decimal number and an integer as inputs, calculate the best (fully simplified) fractional approximation of the decimal number for all fractions up to a denominator of the given integer. The best fractional approximation will be that which is closest to the decimal number in absolute value.
You may take these inputs any way you like and you may output the numerator and denominator any way you like. The numerator and denominator must always be integers, and you may assume we will deal with only positive numbers because adding a negative sign is trivial.
Test Cases
Input | Output

1.21, 8 | 6/5

3.14159265359, 1000000 | 3126535/995207

19.0, 10000000 | 19/1

3.14159265359, 12 | 22/7

2.7182818, 100 | 193/71

0.8193927511, 22 | 9/11

0.2557463559, 20 | 1/4

0.2557463559, 100 | 11/43

0.0748947977, 225 | 14/187

Scoring
This is code-golf. Shortest code wins!

Decimal is a radix. Do you mean numbers with fractional parts?

@MarquisofLorne when I say decimal numbers I'm referring to what people would commonly call decimal numbers (i.e. numbers with digits after the decimal point). Although technically calling them decimal numbers because they are in the decimal system would also be correct

This reminded me that 22/7 is a well-known rational approximation of pi... And another really good one is 355/113, which is VERY easy to remember if you memorize it as "split 113355 in half and make a fraction with it". (These 2 come from the continued fraction of pi, in case you are wondering)

@RGS I actually included the 22/7 example for this very reason

Python 3, 66 61 bytes
lambda x:Fraction(x).limit_denominator
from fractions import*

Try it online!
The above function takes a floating point number and returns a bound function Fraction.limit_denominator which, in turn, takes the upper bound for the denominator to return a simplified, approximated fraction as requested.
As you can tell, I’m more of an API reader than a golfer.

minus 5 bytes thanks to ovs

Nice find! You can make this a little shorter by currying the function: Try it online!

@ovs Thanks! I didn’t even know that is an option in Code Golf.

Python 3.8 (pre-release), 77 71 bytes
-6 bytes thanks to @ovs !
lambda x,n:min([abs(x-(a:=round(x*b))/b),a,b]for b in range(1,n+1))[1:]

Try it online!
Simply try all denominators from 1 to n, saving all results into a list where each element has the form [error, numerator, denominator]. By taking the min of the list, the fraction with the smallest error is selected.

You can make this a little shorter and lot faster with min.

@ovs I totally missed that, thanks for pointing out!

Python 2, 168, 135, 87 bytes
z=i=1
def f(x,y):exec"r=round(x*i);q=abs(r/i-x)\nif q<z:z=q;t=r;u=i\ni+=1;"*y;print t,u

Try it online!
Thank you all for your recommendations on my first golf!

Welcome to the site, and nice first answer! I'd recommend you check out our Tips for golfing in Python in order to find some neat golfing tricks

Here some more improvements by putting the duplicated code in for(2) loop: 135 bytes. PS: tips for golfing in 'all languages' might also be interesting to read through. And great first answer! Welcome.

@KevinCruijssen how does the for _ in [1]*2 work? I've never seen this before

for _ in[1]*2 basically means to loop twice without using the _. A more readable alternative with the same byte-count in this case could be for q in[0,1]. The [1]*2 will basically make the list [1,1]. And then the for _ in[1,1] will loop over this. There might be a shorter way to execute the code twice perhaps, but I'm not too skilled with Python. I know exec("some_code;"*2) would work for one-liners, but I don't think it will work for the multiple indented lines in this case.

You can get rid of the second for loop using r=round(...) instead of int(...). z can starts at 1, since the error cannot exceed 1. Try it online!

Same program in Python 2 with exec trick. TIO

You don't need abs if you use x-r/i

1,1 is shorter than [1]*2. exec("..."*2) may be shorter.

@Third-party'Chef' I don't think you can remove abs, since r/i can be greater than x. For example, with test 1.19, 8 | 6/5, your solution returns 4/3.

@user202729 I believe for q in"12" is shorter, although it looks like that loop was unneeded.

05AB1E, 11 bytes
î*LãΣ`/¹α}н

Try it online or verify all test cases (except for the two 1000000 test cases, which take too long).
Explanation:
î          # Ceil the (implicit) input-decimal
 *         # Multiply it by the (implicit) input-integer
  L        # Pop and push a list in the range [1, ceil(decimal)*int]
   ã       # Create all possible pairs of this list by taking the cartesian product
    Σ      # Sort this list of pairs by:
     `     #  Pop and push both values separated to the stack
      /    #  Divide them by one another
       ¹α  #  Get the absolute difference with the first input-decimal
    }н     # After the sort: leave only the first pair
           # (after which it is output implicitly as result)

Python 3.8, 169 bytes
Maybe the reason why there was no submissions using Farey sequences is that the code appears rather lengthy.
In short, every proper fraction \$\frac{m}{k}\$ in lowest terms appears in Farey sequence of order \$d\$ if and only if \$k\le d\$.
Farey sequences are constructed by taking mediant of neighboring terms of lower order: \$\left(\frac ab,\frac cd\right)\to\frac{a+c}{b+d}\$, starting from \$\left(\frac 01,\frac 11\right)\$.
And the target number is within one of the intervals \$\left[\frac ab,\frac{a+c}{b+d}\right]\$, \$\left[\frac{a+c}{b+d},\frac cd\right]\$, then we take the interval as a current one.
So the algorithm is:

Take \$\left(\frac ab,\frac cd\right):=\left(\frac 01,\frac 11\right)\$.
Take \$\frac{m}{k}:=\frac{a+c}{b+d}\$ and compare with target.
If \$\frac{m}{k}>\$ target, replace \$\frac{a}{b}\$ by \$\frac{m}{k}\$,
Else replace \$\frac{c}{d}\$ by \$\frac{m}{k}\$.
If the next denominator \$b+d\$ is no more than denominator limit, repeat from 2.
Else return nearest from \$\frac ab,\frac cd\$ to the target.

def f(e,n,g,j):
	if n==0:return e,1
	x=[(0,1),(1,1)]
	while True:
		(a,b),(c,d)=x
		if b+d>j:break
		m,k=a+c,b+d
		x[m*g>n*k]=(m,k)
	m,k=x[2*n/g-a/b>c/d]
	return m+e*k,k

Try it online!
Eats (entire_part,proper_numerator,proper_denominator,denominator_limit) and produces (numerator,denominator), like
>>> f(3,141592653589793,10**len('141592653589793'),57)
(179, 57)
P.S. Recursive version is nothing but shorter, even with all whitespace removed:
f=(lambda e,n,g,j,a=0,b=1,c=1,d=1:
   n and(
       b+d>j and(lambda x,y:(x+e*y,y))(*([(a,b),(c,d)][2*n/g-a/b>c/d]))
       or((m:=a+c)*g>n*(k:=b+d))and f(e,n,g,j,a,b,m,k)or f(e,n,g,j,m,k,c,d)
       )or(e,1)
   )

Try it online!

Charcoal, 31 bytes
Ｎθ⪫…⮌⌊ＥＥＮ⌊⁺·⁵×θ⊕κ⟦↔⁻θ∕ι⊕κ⊕κι⟧²/

Try it online! Link is to verbose version of code. Explanation:
Ｎθ                              Input decimal as a number
        Ｎ                       Input maximum denominator
       Ｅ                        Map over implicit range
                κ               Current index (0-indexed)
               ⊕                Increment (i.e. 1-indexed)
             ×                  Multiplied by
              θ                 Input decimal
         ⌊⁺·⁵                   Round to nearest integer
      Ｅ                         Map over results
                      ι         Current numerator
                     ∕          Divided by
                       ⊕κ       Current denominator
                    θ           Input decimal
                  ↔⁻            Absolute difference
                         ⊕κ     Current denominator
                           ι    Current numerator
                 ⟦          ⟧   Make into list
     ⌊                          Take the minimum (absolute difference)
    ⮌                           Reverse the list
   …                         ²  Take the first two entries
  ⪫                           / Join with literal `/`
                                Implicitly print

I'm not 100% sure that the algorithm is correct, so just in case, here's a 34-byte brute-force solution:
ＮθＦＮＦ⊕⌈×θ⊕ι⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧Ｉ⊟⌊υ/Ｉ⊟⌊υ

Try it online! Link is to verbose version of code. Very slow, so test case is limited to a denominator of 1000. Explanation:
Ｎθ

Input the decimal.
ＦＮ

Loop over the possible denominators (except 0-indexed, so all of the references to the loop variable have to be incremented).
Ｆ⊕⌈×θ⊕ι

Loop until the nearest numerator above.
⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧

Save the fraction difference and the denominator and numerator.
Ｉ⊟⌊υ/Ｉ⊟⌊υ

Print the numerator and denominator of the fraction with the minimum difference.

Japt v2.0a0 -g, 15 bytes
mc ×õ ï ñ@ÎaXr÷

Try it
mc ×õ ï ñ@ÎaXr÷     :Implicit input of array U
m                   :Map
 c                  :  Ceiling
   ×                :Reduce by multiplication
    õ               :Range [1,result]
      ï             :Cartesian product with itself
        ñ           :Sort by
         @          :Passing each pair X through the following function
          Î         :  First element of U
           a        :  Absolute difference with
            Xr÷     :  X reduced by division
                    :Implicit output of first pair

Zig 0.6.0, 149 bytes
fn a(e:f64,m:f64)[2]f64{var n:f64=1;var d=n;var b=d;var c=b;while(d<m){if(n/d>e)d+=1 else n+=1;if(@fabs(n/d-e)<@fabs(b/c-e)){b=n;c=d;}}return.{b,c};}

Try it
Formatted:
fn a(e: f64, m: f64) [2]f64 {
    var n: f64 = 1;
    var d = n;
    var b = d;
    var c = b;
    while (d < m) {
        if (n / d > e) d += 1 else n += 1;
        if (@fabs(n / d - e) < @fabs(b / c - e)) {
            b = n;
            c = d;
        }
    }
    return .{ b, c };
}

Variable declarations are annoying.

Perl 5 -p -MList::Util=min, 65, 61 bytes
-4 bytes thanks to DomHastings
/ /;$_=min map abs($`-($-=.5+$_*$`)/$_)." $-/$_",1..$';s;.* ;

Try it online!

Nice answer! You can save 4 bytes using $- instead of $n (negates need for int) and using ; as the delimeter for your final s///: Try it online!

Thanks, I forgot these tips

R, 61 60 bytes
With a byte saved by Dominic van Essen.
function(x,d,n=round(1:d*x))c(m<-order((x-n/1:d)^2)[1],n[m])

Try it online!

Nice!  I saw you'd made an R answer so I didn't want to look at it until I'd tried myself.  But I didn't think of round so my best attempt was 75 bytes.  Well done.

-1 byte by swapping which.min() for order()[1]

Jelly, 11 bytes
Ċ×⁹p÷/ạ¥Þ⁸Ḣ

A dyadic Link accepting the decimal [evaluated as a float] on the left and the denominator limit on the right which yields a pair [numerator, denominator] representing the simplified fraction.
Try it online! Or see the test-suite (big denominator limit cases removed due to inefficiency.)
How?
Ċ×⁹p÷/ạ¥Þ⁸Ḣ - Link: v, d
Ċ           - ceil (of the decimal value, v)
 ×⁹         - multiplied by chain's right argument (denominator limit, d)
   p        - Cartesian power (d) -> all pairs [[1,1],...,[1,d],[2,1],...,[Ċ×⁹,d]]
                  (note that any pair representing a non-simplified fraction is to
                   the right of its simplified form)
        Þ   - (stable) sort by:
       ¥    -   last two links as a dyad:
     /      -     reduce by:
    ÷       -       division (i.e. evaluate the fraction)
      ạ  ⁸  -     absolute difference with the chain's left argument (v)
          Ḣ - head

Io, 78 bytes
Port of Surculose Sputum's answer.
method(x,y,Range 1to(y)map(a,list((x-(b :=(a*x)round)/a)abs,b,a))min slice(1))

Try it online!
Io, 93 bytes
method(x,y,list(((q :=(r :=Range 0to(y)map(a,(x-(a*x)round/a)abs))indexOf(r min))*x)round,q))

Try it online!
Explanation (ungolfed):
method(x, y,                   // Take two operands
    r := Range 0 to(y) map(a,  // Map in range 0..y (set to r):
        (x-(a*x)round/a)abs    //     |x-round(a*x)/a|
    )                          //     (Aka find the appropriate numerator)
    q :=r indexOf(r min)       // Set q as the 0-index of the smallest number of r
    list((q*x)round,q)         // Output [numerator,denominator]
)                              // End function

Ugh, that's twice this week that someone's based their answer on an answer after mine that uses the same algorithm that mine does... how can I improve my explanations?

@Neil I think one reason is that Python is way more readable than Charcoal for most people. :) A trick that might be useful is to include a TLDR at the top about the answer's big idea, since a lot of the time that's all people need/care about. E.g. when I skim through your answer, I'm mostly interested in the algorithm rather than the specific Charcoal commands, and thus I simply skip all the code block. The "loop through all denominator..." sentence is the most telling to me, yet it's buried in the middle of all the hard-to-understand Charcoal stuff.

APL (Dyalog Unicode), 26 bytes
⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣

Try it online!
A dyadic tacit function that takes the decimal number on its left and the max denominator on its right, and gives a 2-element vector of [denominator, numerator].
How it works
⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣  ⍝ Left: x, Right: d
                  ∘÷∘⍳      ⍝ v←[1, 1/2, ..., 1/d]
    (          |⍨)          ⍝ Remainder of x divided by each of v
          |⍨⌊⊢-             ⍝ Min distance from x to some integer multiple of v
        1+                  ⍝ Add 1 to treat close enough numbers as same
                            ⍝ Otherwise it gives something like 5/20 due to FP error
     ⊃∘⍋                    ⍝ D←The index of minimum (the optimal denominator)
                      ×1,⊣  ⍝ Exact fraction (D,Dx)
⌊.5+                        ⍝ Round both

i don't understand the role of 1+. ⊃∘⍋ is the index of the smallest, right? so when we add 1 to the whole array, shouldn't ⊃∘⍋ remain the same?

if leading spaces are ok: ⌊.5+ -> 0⍕

@ngn Try the test case starting with 0.255... with 20. If you don't 1+, you get 5/20 due to floating point errors that are big enough that APL treats them as different even with CT.

yeah, i saw that, but aren't rounding errors generally considered acceptable in golfing?

(⊃∘⍋1+|⍨⌊⊢-|⍨) -> (⊃∘⍋1+|⌊⊣-|)⍨

R, 75 bytes
function(x,d)c((n=rep(0:1,e=d)+(1:d*x)%/%1)[f<-order((x-n/1:d)^2)[1]],f%%d)

Try it online!
Not a competitive answer as it's already beaten by Kirill, but posting for fun anyway.
I didn't think of the round() function, so this approach rounds down & then up to generate a double-length list of candidate numerators, and then finds the index of the closest fraction.  Since the index might be in the second (rounded-up) part of the list, the denominator is the index mod the length of the single-length list.
I think it's fair to conclude that the round() function indeed serves a useful role...

Wolfram Language (Mathematica), 60 bytes
(t=s=1;While[Denominator[s=Rationalize[#,1/t++]]<#2,j=s];j)&

Try it online!

Julia, 66 bytes
r(x,m)=minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]

or
(x,m)->minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]

source: Stack Exchange

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

sort: votes


text:
The Cantor Function
The Cantor function is continuous everywhere and constant almost everywhere, but has an average slope of 1:

The function can be found recursively:
\$f_0(x)=x\$
\$f_{n+1}(x)=\left\{\begin{matrix}\frac{1}{2}f_n(3x)&x\in[0,\frac{1}{3})\\ \frac{1}{2}&x\in[\frac{1}{3},\frac{2}{3})\\ \frac{1}{2}+\frac{1}{2}f_n(3x-2)&x\in[\frac{2}{3},1] \end{matrix}\right.\$
The Cantor function is the limit of this process, \$\lim\limits_{n\to\infty} f_n(x)\$:

The Challenge
Given real x (which can assume the form of a float or rational number) of the interval \$[0,1]\$ and nonnegative integer n, return \$f_n(x)\$.
Rules

This is code-golf so the shortest answer in bytes wins.

Assume only valid input will be given.

Error should be under one ten-thousandth (±0.0001) for the test cases.

Test Cases
In: 0.3 3
Out: 0.3875

In: 0.1 0
Out: 0.1

In: 0.29 4
Out: 0.375

In: 0.11 5
Out: 0.2415625

Related (draw $f_n$ in ASCII art)

The average slope is actually 0.

Using the average slope formula m=(y2-y1)/(x2-x1) and the points (0,0) and (1,1) one can see the average slope is 1 @PyRulez

In any case, the slope is 0 almost everywhere.

APL (Dyalog Extended), 25 27 bytes
{⊥1⊥1⌊⊤1∘≠⍛×\0,3⊤⍵×3*⍺}÷2*⊣

Try it online!
Inline tacit function, which can be used as n f x.
Uses the method described in Luis Mendo's MATL answer. I changed one part of the algorithm:

This one doesn't consider integer and fractional parts separately; rather, the fractional part is included in the last digit. (e.g. the base-3 representation of 8.1 is [2, 2.1].) Later, at the step where 2s are changed into 1s, all digits ≥2 are reduced by 1 instead, and (+2 bytes) the fractional part of the last digit is removed if its integer part is 1.

{⊥1⊥1⌊⊤1∘≠⍛×\0,3⊤⍵×3*⍺}÷2*⊣  ⍝ Left: n, Right: x
{                ⍵×3*⍺}  ⍝ 3^n*x
               3⊤        ⍝ Convert to base 3; last digit may have fractional part
             0,  ⍝ Prepend 0 to avoid error on ⊤ over an empty array
       1∘≠⍛×\    ⍝ Keep each digit unless at least one 1 appears somewhere on its left
      ⊤  ⍝ Convert each digit to binary
    1⌊   ⍝ Clamp all digits >1 to 1 (effectively cuts the fractional part of
         ⍝ the last digit if its integer part is 1)
  1⊥     ⍝ Treat the binary of each digit as base 1 and convert back to a number
         ⍝ Since all numbers are <3, effectively "decrement if ≥2"
 ⊥  ⍝ Treat as base 2 and convert to single number
÷2*⊣  ⍝ Divide by 2^n

@LuisMendo He doesn't; I was just checking that myself, in case it helped me golf more bytes from my answer. (To be specific, 3 f 0.72 is returning 0.68 instead of the correct 0.625 that your answer gives.)

@LuisMendo Ah, so 1∘≠⍛×\ works for the first n-1 base 3 digits; it's only the case of when the nth digit is a 1 that his answer doesn't work.

Thanks for pointing out the error. I think I have a +2 bytes fix; I'll update the post when I get to my PC.

MATL, 33 bytes
3y^i*1&\3_YAt1=f"O@QJh(wkw]XB+wW/

Inputs are n,  then x.
Try it online! Or verify all test cases.
Approach
The code uses a non-recursive approach, based on the procedure for computing the Cantor function \$f_\infty(x)\$ that appears in Wikipedia, modified so that it computes \$f_n(x)\$ instead:

Multiply \$x\$ by \$3^n\$.
Decompose the result into integer part \$M\$ and decimal part \$F\$.
Express \$M\$ in base \$3\$. Let \$B\$ be the resulting sequence of up to \$n\$ digits from the set \$\{0, 1, 2\}\$.
If \$B\$ contains a \$1\$, replace every digit after the first \$1\$ by \$0\$.
Replace any remaining \$2\$s with \$1\$s.
Interpret the result as a binary number.
If \$B\$ didn't contain \$1\$s, add \$F\$.
Divide by \$2^n\$.

Some golfing tricks

Using a for loop instead of an if branch for step 4 saved quite a few bytes. The value for the branch condition (index of first \$1\$) needed to be used within the branch code (to replace subsequent digits by \$0\$). This is cumbersome in MATL, as the if branch consumes (pops) its condition. Instead, the loop solves this more elegantly: since the branch condition was either empty or a vector of indices of \$1\$s in \$B\$, it can be looped over: if it's empty the loop is simply not entered. And then the loop variable can be used within the loop code. The fact that the loop, unlike the conditional branch, may iterate several times (if there are more than one \$1\$ digit) is not harmful here, because the substitutions in step 4 are idempotent: they simply overwrite some of the previous \$0\$s with new \$0\$s.
Step 7 is partly handled within the for loop. Specifically, if the loop is entered, the decimal part \$F\$ should not be added later on. To implement this, the loop iteration replaces \$F\$ (previously stored in the stack) by \$0\$. This is done by a round-down operation (k), which is convenient because it uses only 1 byte and is, again, idempotent: the result remains equal to \$0\$ in all iterations after the first.
The MATL function that converts from binary to decimal (XB) treats any digit other than \$0\$ as if it were \$1\$, which is useful for steps 5 and 6.

Commented code
3         % Step 1. Push 3
y         % Implicit input: n. Duplicate from below: pushes n below and
          % above the 3
^         % Power: gives 3^n
i*        % Input: x. Multiply: gives x*3^n
1         % Step 2. Push 1
&\        % Two-output modulus: gives modulus (F) and quotient (M)
3_YA      % Step 3. Convert to base 3, with digis 0, 1, 2
t1=       % Step 4 and part of step 7. Duplicate. Compare each entry with 1
f         % Vector (possibly empty) of indices of true values; that is,
          % positions of digit 1
"         % For each index k
  O       %   Push 0
  @Q      %   Push k+1
  Jh(     %   Write 0 at positions k+1, k+2, ..., end
  wkw     %   Swap, round down, swap. This replaces F by 0
]         % End
XB        % Steps 5 and 6. Convert from binary to decimal, with digit 2
          % interpreted as 1
+         % Part of step 7. Add F, or 0
wW/       % Step 8. Swap (brings n to top), 2 raised to that, divide
          % Implicit display

So, much like my second approach, but without the bug... I'd better go back and fix my answer.

@Neil Nah. Your current 34 byte count is perfect :-P

Sadly it didn't work for x=1. (In a deleted comment, @Bubbler pointed out that @fireflame241 had the same problem with his answer.)

(But the good news is that I can use @Bubbler's adjustment to your method, and this actually saves me 2 bytes overall, which is almost back down to the original byte count.)

Yeah, pity that MATL's base conversion cannot handle non-integer values

APL (Dyalog Unicode), 38 bytes
{×⍺×1-⍵:2÷⍨(1∘≤+(1≠⌊)×(⍺-1)∇⊢-⌊)3×⍵⋄⍵}

Try it online!
Combines the cases of the recurrence using
$$
f_{n+1}(x) = \frac{1}{2}\begin{cases}
0+1×f_n(3x-0), x\in[0,1/3) \\
1+0×f_n(3x-1), x\in[1/3,2/3)\\
1+1×f_n(3x-2), x\in[2/3,1]
\end{cases}
$$
which can be condensed (note \$u=3x\$) to
$$
f_{n+1}\left(\frac{1}{3}u\right) = \frac{1}{2}\big(
(u<1)+(\lfloor u\rfloor\neq 1)×f_n(u-\lfloor u \rfloor)\big)
$$ (since comparisons resolve to True=1 or False=0). This fails for x=1 since then ⌊u is 3 instead of 2. Using ceiling instead of floor would then fail for x=0, so it ends up shorter to check specifically for x=1.
{ ... } ⍺=n; ⍵=x
×⍺×1-⍵: ⍝ If n>0 or x≠1:
 3×⍵      ⍝ Let u=3x
  (⍺-1)∇⊢-⌊ ⍝ f(n-1, u-floor(u)) (`1∘|` ←→ `⊢-⌊`)
  (1≠⌊)×    ⍝ Multiply by 1 unless floor(u)=1
  1∘≤+      ⍝ Add 1 unless 1 > u
 2÷⍨      ⍝ Half of this
⋄       ⍝ Else:
 ⍵        ⍝ x

@Bubbler Fixed.

Shouldn't u < 1 in your explanation be u ≥ 1?

If n>0 or x≠1 - you mean and? you can avoid x≠1 by replacing ⊢-⌊ with 2|⊢

Python 3, 54 bytes
f=lambda n,x:n and(1<x*3<2or x//.5+f(n-1,3*x%1))/2or x

Try it online!
Python 3 is used just for the /2 to do float division; Python 2 would be a byte longer with /2..

Wolfram Language (Mathematica), 69 bytes
of course mathematica has a built-in for this: CantorStaircase[x] but you cannot choose n
x_~f~0:=x
x_~f~n_:=If[(y=3x)<1,f[y,n-1]/2,If[y<2,.5,.5+f[y-2,n-1]/2]]

Try it online!
@JonathanAllan saved 2 bytes
Here is also another approach from @att which is great!
Wolfram Language (Mathematica), 57 bytes
If[#2<1,#,If[1<3#<2,1,(s=Boole[2#>1])+#0[3#-2s,#2-1]]/2]&

Try it online!

Using a condition of x<2/3 and swapping the branches would save a byte. Can you place 3x in a variable, say y, in five bytes (or less)? If so you can save a byte (or more) by then replacing 1/3 with 1, 2/3 with 2 and the two occurrences of 3x with y.

57 bytes

Python 3.8 (pre-release), 62 bytes
f=lambda n,x:n and[f(n-1,e:=3*x),1+e//2*f(n-1,e-2)][e>1]/2or x

Try it online!

Jelly, 30 bytes
_2çH+.
ñH¥.ç<2$?<1$?
×3çɗ⁸⁹?’}

A full program accepting \$x\$ and \$n\$ which prints a floating-point representation of \$f_n(x)\$
Try it online!

JavaScript (ES6), 45 bytes
Expects (n)(x).
n=>g=x=>n--?((x*=3)<1?g(x):x<2||1+g(x-2))/2:x

Try it online!
Commented
n =>                   // outer function taking n
  g = x =>             // inner recursive function taking x
    n-- ?              // decrement n; if it was not equal to 0:
      (                //   compute f_n(x):
        (x *= 3) < 1 ? //     multiply x by 3; if the result is less than 1:
          g(x)         //       use g(x)
        :              //     else:
          x < 2 ||     //       use 1 if x is less than 2
          1 + g(x - 2) //       otherwise, use 1 + g(x - 2)
      ) / 2            //   in all cases, divide the result by 2
    :                  // else:
      x                //   stop recursion and return f_0(x) = x

C (gcc), 73 \$\cdots\$ 69 68 bytes
float f(n,x)float x;{x*=3;x=n--?(x<1?f(n,x):x<2?:1+f(n,x-2))/2:x/3;}

Try it online!
Saved 4 bytes thanks to the man himself Arnauld!!!
Save a byte thanks to ceilingcat!!!

I was just about to suggest 69 bytes before your edit.

That's a much better direction to golf in. Was just think how on earth do I factor out the /2 and the x<2, and there you have it: call recursively from two places. Since your golf is based on the original gave you -4 bytes - thanks! :D

@ceilingcat Nice one - thanks! :D

Python 3.8, 70 74 bytes
1 byte saved thanks to @FryAmTheEggman
f=lambda n,x:n and((1<=(t:=x*3))+f(n-1,t-2*(t>=2))*(t>=2or 1>t))/2or x

Try it online!

R, 76 ... 60 58 bytes
-6 bytes thanks to Robin Ryder, +1 byte to fix bug spotted by Neil, -2 bytes thanks to Giuseppe
f=function(x,n,y=x*3)`if`(n,(min(f(y%%2,n-1),1)+!y<2)/2,x)

Try it online!
Un-golfed:
cantor=f=function(x,n){
    y=3*x                               # define y=3*x
                                        # to save characters later.
    if(n==0){ x }                       # if n==0 just return x
    else {                              # otherwise
        (
         min(                           # whichever is smaller of:
            cantor(y%%2,n-1),           # - call self using y mod 2
                                        #   (this works for the first & last thirds
                                        #   but gives a result >1 for middle third)
            1)                          # - 1 (to fix the middle third)
         +(y>=2)                        # for the top third we need to add 1 to
                                        # the result of the self call
        )
        /2                              # finally, we divide all above results by 2
    }
}

72 bytes by avoiding some ifs.

Thanks!  I managed to removed some more bytes in the meantime!

...but combining this with your approach managed to shave-off another 2!  Thanks again!

floor(y) can be y%/%1 for -3 bytes.

Super!  Thanks again!

1 more byte shaved off because operator precedence breaks your way. I think I'm out now!

I'd worry about y=1 except that it can't happen with floating-point numbers since they can't represent 1/3 exactly...

@Neil - Thanks for spotting that.  It was a problem: somehow the non-exact representations seem to cancel-out if we specify 1/3 as x.  Fixed now, I think (at cost of +1 byte [>1 changed to >=1])

Ah, I guess floating-point rounding could trip over this. Glad I could help!

58 bytes.

Thanks for the golfing wizardry, again, Giuseppe!

Perl 5, 78 bytes
sub f{my$b=pop;my$a=pop;$b--?($a<1/3?f(3*$a,$b):$a<2/3?1:1+f(3*$a-2,$b))/2:$a}

Try it online!

Nice again! You can save a few bytes using my($a,$b)=@_; instead of the pops though!

Charcoal, 35 bytes
Ｎθ≔↨×ＮＸ³θ³ηＩ∕↨²Ｅη∧¬№…ηκ¹§⟦ι¹⊖ι⟧ιＸ²θ

Try it online! Link is to verbose version of code. Based on the Wikipedia entry, I convert the 3ⁿx to base 3, then massage the digits so that the result can be interpreted as base 2 and divided by 2ⁿ. Takes input in the order n, x. Explanation:
Ｎθ

Input n.
≔↨×ＮＸ³θ³ηＩ∕

Multiply x by 3ⁿ and convert it to base 3. The last entry includes any remaining fractional part.
Ｅη∧¬№…ηκ¹§⟦ι¹⊖ι⟧ι

Map over the digits. If there was a previous 1 then set this digit to zero, otherwise map the digit to itself, 1, or subtract 1, depending on the floor of the digit. This ensures that the last digit (with the remaining fractional part) is converted correctly.
Ｉ∕↨²...Ｘ²θ

Convert from base 2, divide by 2ⁿ, and output the final decimal as a string.
Previous 34-byte solution did not work for x=1, as it only considered the decimal part of x:
Ｎθ≔×ＮＸ³θη≔⁻η⌊ηζＦθ≔⊘§⟦ζ¹⊕ζ⟧∕ηＸ³ιζＩζ

Try it online! Link is to verbose version of code. Takes input in the order n, x. Explanation:
Ｎθ

Input n.
≔×ＮＸ³θη

Multiply x by 3ⁿ.
≔⁻η⌊ηζ

Take the decimal part of that.
Ｆθ

Loop n times.
≔⊘§⟦ζ¹⊕ζ⟧∕ηＸ³ιζ

Depending on the next base 3 digit of the above product, replace the decimal part with half of itself, half of 1, or half of the sum.
Ｉζ

Output the final decimal as a string.

05AB1E, 31 bytes
3Im*1‰`s3в¹£εTYèsi1V]2βY≠i+}¹o/

Takes the loose inputs in the order \$n,x\$.
Port of @LuisMendo's MATL answer, so make sure to upvote him as well!
Try it online or verify all test cases.
Explanation:
3Im              # Push 3 to the power of the first input-integer
   *             # Multiply it by the (implicit) input-decimal
    1‰           # Get the divmod-1 to split the integer and decimal parts
      `s         # Pop and push them separated to the stack in reversed order
3в               # Convert the integer part to base-3 as list
  ¹£             # Only leave the first input-integer amount of base-3 digits
    ε            # Map this list to:
     T           #  Push 10
      Yè         #  Index `Y` into this
                 #  (`Y` is 2 by default, which wraps modulair indices into the 1)
     si          #  If the current digit we're mapping over is 1:
       1V        #   Set `Y` to 1
    ]            # Close both the if-statement and map
     2β          # Convert the resulting list from base-2 to an integer
       Y≠i }     # If `Y` is NOT 1:
          +      #  Add the decimal part that's still on the stack
            ¹o/  # And divide this by 2 to the power the first input-integer
                 # (after which the result is output implicitly)

If I put in 3 0.72 then I get 0.875 which seems wrong; I think it should be 0.625.

PARI/GP, 71 bytes
Golfed version. Attempt This Online!
f(x,n)={y=3*x;if(n==0,x,if(y<1,f(y,n-1)/2,if(y<2,.5,.5+f(y-2,n-1)/2)))}

Ungolfed version. Attempt This Online!
f(x, n) = {
  my(y = 3*x);
  if(n == 0, x,
    if(y < 1, f(y, n-1)/2,
      if(y < 2, .5, .5 + f(y-2, n-1)/2)
    )
  );
}

print(f(0.3, 3));
print(f(0.1, 0));
print(f(0.29, 4));
print(f(0.11, 5));

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


text:
Distinguish English and Spanish with regular expressions
The task is to to compete for the shortest regex (in bytes) in your preferred programming language which can distinguish between English and Spanish with minimum 60% 90% accuracy.
Silvio Mayolo's submission (pinned as Best Answer) has secured his spot as the winner of original contest against any chance of being contested.  In order to provide room for further submissions, he has generously allowed the scoring requirement to be pushed to 90% accuracy.
Links to wordlists have been replaced due to concerns voiced in the comments.
The following word lists (based on these) must be used: English, Spanish
The Spanish wordlist is already transliterated into ASCII, and there is no word present in either which is also present in the other.
A naive approach to distinguishing Spanish from English might be to match if the word ends in a vowel:
[aeiou]$ i 9 bytes
Here's a live example, where 6 of 8 words are successfully identified, for 75% accuracy:

const regex = /[aeiou]$/i;

const words = [
  'hello',
  'hola',
  'world',
  'mundo',
  'foo',
  'tonto',
  'bar',
  'barra'
];

words.forEach(word => {
  const match = word.match(regex);
  const langs = ['English', 'Spanish'];
  const lang = langs[+!!match];
  console.log(word, lang);
});

(Assuming I understand right that we need to choose two languages and have our code distinguish just those two) I suspect too much of the challenge hinges on finding languages with very stereotypical distinct common patterns within ASCII characters. I'd suspect at this point the regexp's will be simple and golfing them won't be that interesting.

I changed the rules to use only the English and Spanish wordlists, so that the challenge can be focused on golfing regex instead of finding dissimilar languages.

Thanks, I like these changes. Could you please also make a link an ASCII-transliterated Spanish word list? I'm not clear though on how our accuracy is judged. Are we given a word from one of the two word lists (20,000 words total) and our regex judges if it's English of Spanish, with us choosing which one is "match" and "not match"? What about if the string happens to appears in both lists?

When you say shortest regex in any language, does that only count the length of the regex string in that flavor? Or does it count the invocation like re.match(...) as well?

That's some good points, I'll make and link a version of the transliterated wordlists with shared words removed.  By shortest regex in bytes I mean counting only the regex itself.  So for instance in JavaScript you can see my example was [aeiou]$ i even though that RegExp literal would be written as /[aeiou]$/i, and was used as .match(...).  I am not a regex expert and this is my first contest so if there are any problems with that please let me know.

I think this is an interesting challenge, but it needs some refinement. We have a Sandbox on the Meta site (if someone can link to it, I'm on mobile now) for just such a purpose.

Sandbox Link: https://codegolf.meta.stackexchange.com/questions/2140/sandbox-for-proposed-challenges

This was in the Sandbox yesterday.

The Spanish list has the accents and tildes removed - was this intentional?

Yes, as stated in the OP: The Spanish wordlist is already transliterated into ASCII.  Testing for non-English characters would be cheap, don't you think?

Maybe we could use a different scoring system for this one, since it apparently has a fairly unbeatable answer. Accuracy squared multiplied by byte count?

@SilvioMayolo What do you think? Your answer would remain pinned as Best Answer for posterity, while allowing future submissions to compete with the rules mypetlion suggested.

Yeah, I'm not going to be offended if you change the winning condition. My answer is amusing, but it's not like I worked very hard for it. :P Factoring in accuracy should make things very interesting.

Awesome, I appreciate that =) I will update the rules.

@mypetlion Did you mean divided by byte count?

My experience with length-accuracy trade-off scoring formulas is that they're almost always turn out unbalanced or exploitable by answers caring for pretty much just about the one or the other. Moreover, dividing by byte count is usually a bad idea that rewards ultra-short answers when the other factor has a cap. I'd suggest just putting a higher required goal accuracy.

Okay I will put this post in limbo until I figure something out.

Regarding the Sandbox, it's good that you posted there first, but one day is too little time to gather feedback. Three days minimum is usually recommended by default, but with this being not a bog-standard code golf but a challenge with a test battery, I'd suggest a week or two at least.

That metric may not quite be enough. A 2-byte answer can beat my answer if it has accuracy of 84% or above (which may be possible with 2 bytes, but I'm not hopeful). A 3-byte or more answer, even with 100% accuracy, can only get a 0.33 score, at most. I like this challenge, but I'm not sure what the right metric for it is, to be honest.

I'm looking at a scripted list of possible scores right now and yeah I definitely see what you mean.  I edited the OP to say the challenge is frozen until a scoring method can be decided on.

@GirkovArpa Oh right yeah, divided by, because we want a lower score to win. I was thinking backwards.

@GirkovArpa Actually, hold on, I think we've both got it wrong. It should be byte count / accuracy squared. Because a 60% accuracy squared is 0.36. So a 2 byte answer would get a score of 5.555... Whereas a 3 byte answer with the same accuracy would get a score of 8.333...

I’m voting to close this question because "This contest is frozen until a reasonable scoring system can be decided on."

There's also https://codegolf.meta.stackexchange.com/questions/19041/is-a-solution-wins-if-theres-no-strictly-better-solution-in-multiple-measures ... but (you see the votes yourself. Bubbler's answer is at +3/-3.)

(regarding the "3 days": it is written in the "sandbox FAQ", but... nobody read that?)

i'll vote to close because the contest is frozen for now.

Also I think you should provide the lists as plaintext files, one word per line, rather than JSON.

maybe you an ask for shortest code with 90% accuracy or something like that

Not sure how important it is for the challenge, but the Spanish list includes a lot of words that are not Spanish: yyo, kallen, ilama, yankee, oscorp, missy, vinci, tirith, hagrid, spike, finch, vaako, tj, deb, as well as some possibly proper nouns that don't sound Spanish at all: isabelle, ani, shirley, ashford, ming, asher, gwen, brett, jess, kenobi, dickens, dexter, marcy, lizzy, kiddo, olaf, poe, bert, klaus. And I only glanced at the last 500 words in the list...

@qwr That is a good solution, short and easy to understand.

@LuisMendo They are supposedly the 10 000 most common words in the Spanish language, according to the repository I got them from (I did remove words that existed in both the English and Spanish wordlists).  Although, now that you mention Hagrid, I'm having my doubts.  Is Harry Potter really that common?

@GirkovArpa I'm a native Spanish speaker and I see words in that list that I don't recognize as common, and definitely not as Spanish words

If you follow the citation here: https://github.com/oprogramador/most-common-words-by-language It seems the wordlists are derived from Wiktionary.  I am not sure how the frequencies were determined though.

I updated the rules with the suggestion from @qwr.  I hope this can be re-opened.

To be a little specific on LuisMendo's comment, "ei" is not a Spanish word, and is not even on wiktionary.  It is the sort of word that appears as a transcripcion error from "El" or "Él".  I also notice at least one slightly vulgar word, "carajo" which basically means "dick", on the Spanish list.  I don't know if you care about that.

I am not overly attached to these particular wordlists.  If there are better alternatives I'm willing to link those instead.

@GirkovArpa I'm not sure how  github.com/oprogramador/most-common-words-by-language construct its word list. I had just checked the Chinese language version. It claimed the word "the" is a common word in Chinese language. (wtf

I suggest using wordlists if the most common words in a language which you should easily be able to find.

Any Language, 0.3677 (60.6064%, 1 byte)
a

No, I'm not joking. The single-character regular expression a successfully identifies Spanish words over English given your input files 60.6064% of the time, which makes it a valid submission.
Here's a complete, runnable Perl script that checks the percentage of this regular expression, assuming you've downloaded english.json and spanish.json into the same folder as the script.
#!/usr/bin/perl

use strict;
use warnings;
use 5.010;

my @english;
my @spanish;

my $fh;
open $fh, '<', 'english.json';
while (<$fh>) {
    push @english, $1 if /"(\w+)"/;
}
close $fh;

open $fh, '<', 'spanish.json';
while (<$fh>) {
    push @spanish, $1 if /"(\w+)"/;
}
close $fh;

my $correct = 0;
my $total = 0;

my $re = qr/a/;

for (@english) {
    $total++;
    $correct++ unless /$re/;
}
for (@spanish) {
    $total++;
    $correct++ if /$re/;
}

say "$correct / $total (@{[100*$correct/$total]}%)";

Good job!  That's fascinating that just having the letter a makes a word significantly more likely to be Spanish as opposed to English.  Also, maybe I should have consulted a linguist to review the OP before submission :P

Well, can't imagine anybody's going to beat that...

Also amazing how it just barely qualified by 0.6% percentage points.

It's also the only letter that satisfies the criteria. The next best would be o, with 58.69%, then it drops way down to 54.08% with t. On the flipside, n occurs most uniformly, at 50.13% accuracy.

Thanks for the additional info, I was curious to know.  Was a actually the first thing you tried?

I wrote a script to analyze common character sequences in the two files, in the hopes of finding a 3- or 4-character constant regex that would do it. Sure enough, my script came back with a, which made me chuckle.

50 bytes, 90.02% accurate
(a(d?|is|r|se?)|dor|eis|ese|je|n|[ns]te|os?|res?)$
For 18,004 out of the 20,000 words in es_clean.json and en_clean.json, this regex matches iff the input word is Spanish.


text:
And and… and. And.?
Introduction:
Inspired by the Puzzling-stackexchange post with the same name, which I've answered four years ago:

Can you create a perfectly valid English sentence, which makes perfect sense, but which contains the word "and" in it, five times consecutively in a row ?
"Something-or-other and and and and and something-else."

With my answer:

 Let's say we have a store owner and his clerk. The store owner want the clerk to make a sign for the shop, which has the name (for example): "Toys And Puzzles".
 So, the clerk makes the sign and presents it to the owner.

 The owner thinks the spacing isn't really good. It currently looks something like:
Toys And Puzzles
 but he wanted it to look more like:
Toys  And  Puzzles

 So he says to the clerk:
 "The spacing between Toys and And and And and Puzzles should be a bit larger. Could you please fix that?"

Challenge:
Given a string input, replace all occurrences of the word 'and' with five times that word; three in lowercase, interleaved with two of the original cased word.
Some examples:

AND would become and AND and AND and
and would become and and and and and
AnD would become and AnD and AnD and

There is one catch however (restricted-source):
You're not allowed to use the characters aAnNdD in your source code. Any other character is still allowed, even if it's the unicode value of these letters, only these six characters themselves are banned.
Challenge rules:

Your source code cannot contain any of the characters aAnNdD.
You can assume the input-string only contains spaces and letters (both lower- and uppercase)
You can assume the input is non-empty
It is possible that the input-string does not contain the word 'and', in which case it's returned as is
Instead of a string you are also allowed to take the input as a list/array/stream of characters/code-point-integer (or other similar variations)
Don't replace substrings of and if it isn't a standalone word (see test cases with stand, band, and Anderson)

General rules:

This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code (i.e. TIO).
Also, adding an explanation for your answer is highly recommended.

Test cases:
Input:  "Toys And Puzzles"
Output: "Toys and And and And and Puzzles"

Input:  "and"
Output: "and and and and and"

Input:  "AND and anD"
Output: "and AND and AND and and and and and and and anD and anD and"

Input:  "Please stand over there and watch" # note that the "and" in "stand" isn't changed
Output: "Please stand over there and and and and and watch"

Input:  "The crowd loves this band" # note that the "and" in "band" isn't changed
Output: "The crowd loves this band"

Input:  "Toys and And and And and Puzzles"
Output: "Toys and and and and and and And and And and and and and and and and And and And and and and and and and Puzzles"

Input:  "Mr Anderson went for a walk and found a five dollar bill" # note that the "And" in "Anderson" isn't changed
Output: "Mr Anderson went for a walk and and and and and found a five dollar bill"

It's too bad that the ban on andAND letters in code means a lot of language constructs just aren't allowed, making a regex-based method even more tempting. And Python can't print, return, or lambda, and so needs some imagination to even output anything.

@xnor Good point. I just felt that without the restriction I'd only see the basic replace (?i)\band\b with and $0 and $0 and for language with regex, and felt it needed something enforcing people to be a bit more creative with their answers, hence the restricted-source. I also realize this is just a flaw in my base challenge, since do-X-without-Y challenges are usually discouraged, but I felt without it the challenge would be too boring. Out of curiosity: what would you have changed to still have the base challenge, but without only seeing the to-the-point regex-replace approach?

I think the store owner should just say: Enlarge the word spacing in Toys And Puzzles.

Can we take input as an array of words?

@Shaggy Due to the amount of answers already I'd say no, sorry. It indeed doesn't add much to split on spaces at the start and join by spaces at the end. But considering the answers that would need some changes, and since I mentioned only letters and spaces are valid input-characters, I think it's best to leave it as is now. But if you have convincing arguments otherwise, lmk please.

@KevinCruijssen I don't have any good ideas for dealing with regex being too good. Honestly, I often avoid writing string-manipulation challenges because of this.

@xnor Well here's your "imaginative" answer.  I have to say it is not as impressive as you might have suggested.

@AdHocGarfHunter Heh, I didn't mean to hype it as interesting, was just saying the obvious things aren't allowed.

05AB1E, 18 bytes
-(3+1) from Kevin Cruijssen, -1 from ovs, -1 from Neil's Charcoal answer.
#εÐl'€ƒQils‚5∍]˜ðý

Try it online!
Explanation
#                   Space split
 ε                  Map:
  Ð                     Triplicate
   l                    lowercase
    '€ƒQ                == "and"?
        i               If true:
         l                  Lowercase
          s‚                Paired with original
            5∍]             Extend to 5 items
                       (Else: return the current item)
               ˜   Flatten
                ðý Join by spaces

Nice answer. Some things to golf: the I# can be Ð (Duplicate is indeed not allowed, but triplicate is still available); and the ε and } can be removed, since l'€ƒQ vectorizes the list automatically.

Instead of modifying the current word you can intersperse (.ý) ["and", "and", "and"] with it, flatten the list, and the use the final join to add the spaces: #Ðl'€ƒQÅÏ'€ƒ3иs.ý}˜ðý

Nice new approach. You can golf 1 more byte by changing the Þ5£ to 5∍

C (gcc), 179 176 157 152 149 bytes
-3 -3 bytes thanks to ceilingcat
-19 bytes thanks to xibu
L,M,P=543452769;f(s,t)typeof("")s,t;{M=M>>8|*s<<24;t=(M|'    '|L<<24)-P?t:memcpy(t-3,(typeof(0)[]){P,M|=1<<29,P,M,P},20)+19;L=M;(*t=*s)&&f(s+1,t+1);}

Try it online!
Assumptions

ASCII
Little-endian
sizeof(int) == 4
sizeof(int *) >= sizeof(char *) (I cannot imagine what absurd platform this would be false on, but you never know.)
typeof() provided by the compiler.

Breakdown
We step through the input string one character at a time. This character is placed at the top-most byte of M, shifting the previous characters to the left. This makes it so that M continuously holds a record of the four current characters. That's this part:
M=M>>8|*s<<24

Next up, we make M lower-case, and OR our fourth character with the previous character that we had before M. We compare the whole shebang with our magic number P, which represents the string "and ". Why ORing with the previous character like that? Well, it will only be true if that character was 0 (as in we are in the beginning of the string) or a space:
(M|'    '|L<<24)==P

If this is true, we know we have an "and" to deal with. We make sure the last character of M is a space and not NUL, and build an anonymous array of integers to copy into target string.
This array is built from noting that the word "and" (and whatever arbitrary case variant we picked out of the source string) will always be followed by a space (except for the last instance) when expanded to its final form, which means a neat four bytes, which happens to be the size of an integer. The string "and " is represented by P (little-endian makes the string appear reversed when viewed as a number):
M|=1<<29                        Make highest byte of M a space
t=memcpy(
    t-3                         Copy to sightly before target string
    ,(typeof(0)[]){P,M,P,M,P}   Integer array of "and " isotopes
    ,20)
+19                             Increment target string

Why to we copy to three bytes before the current target string? Because we have already copied those bytes before we knew it was an "and". And since this memcpy() is only ever called when we have found the keyword, we will never copy out of bounds.
The rest is straight-forward:
L=M;                            Last = Current
(*t=*s)&&f(s+1,t+1)             Copy byte and go to next bytes
                                in strings if not end-of-string

That is a great solution. I didn't expect an answer in C since 'char' is not allowed. That said typeof("") can be used instead of typeof(*"") because char[] will decay to char* whenever required. Using recursion and the multicharacter literals @ceilingcat suggested your function can be shortened to 154 Bytes without reading past the input string.

@xibu Hm. I shall look into it. But the version you linked uses the forbidden letters, so it will be slightly longer. I did not get the typeof("") to work, since incrementing it would not work. Passing it recursively will of course work, though.

@gastropner your right, here is the solution without forbidden characters.

@gastropner changing typeof(*"")*s,*t,*u; in your code to typeof("")s,t,u; works for me

@xibu You are quite right! Don't know what step along the way I convinced myself it didn't work.

Perl 5 + -p -040 -l, 35 bytes
This script contains unprintables so the link is to a Bash program that builds the script and runs the tests.
$s= ~'...';s/^$s$/$s $& $s $& $s/gi

Try it online!
Explanation
Uses Perl s///ubstitution operator, but necessitates that and is built outside due to the source restriction. To create and, the $s is set to ~"\x9e\x91\x9b" using the raw bytes (hence using xxd). I started with "\x61\x6e\x64" and tried to look for shorter approaches. I also looked at PWQ^"195" and variants of that, and v97.110.100, but ~ was shortest. Once that string is created, it's possible to s///ubstitute it surrounded by start and end anchors (^ and $) due to the -040 command-line switch which uses space (ASCII 32, octal 040) as the record separator (which is also stripped off by -l) making $_ equal just the words themselves, with case-/insensitivity, with the string ($s) and the matched string $& as required, /globally within the input.

Perl 5 + -p040l, 41 bytes
Without using RegEx. Link shows 50 bytes because I'm using the \xXX notation. Will fix when I'm not on mobile!
$s= ~"\x9e\x91\x9b";$_=lc eq$s?"$s $_ $s $_ $s":$_

Try it online!

I can see you've prepared this solution when it was still in the Sandbox, based on the . in the Mr. Anderson test case. I removed it when I just posted it to main, since I mentioned in the rules the input will only contain letters and space. ;) But well done. Looking forward to that explanation.

@KevinCruijssen Hah! I did spot it and played with it last night :P I Hope others enjoy this. I tried a few different attempts to get and but ended up with the slightly less interesting variant, but was fun experimenting with ways to make it.

Python 3.8, 102 bytes
k=iⁿput().split();o=[]
while k:w,*k=k;o+=([w],[x:=w.lower(),w,x,w,x])["\x61\x6e\x64"==x]
priⁿt(*o)

Try it online!

Python 3.8, 106 104 bytes
-2 bytes inspired by this answer from Luis Mendo.
exec('priⁿt(*sum([([x:=w.lower(),w,x,w,x],[w])["\x61\x6e\x64"!=x]for w i\x6e iⁿput().split()],[]))')

Try it online!
Deobfuscated Code:
priⁿt(*sum([([x:=w.lower(),w,x,w,x],[w])["and"!=x]for w in iⁿput().split()],[]))

The "deobfuscated code" is more minimal? Only 80 bytes? https://mothereff.in/byte-counter

@Protectorone but that has prohibited characters :)

Aaah, now I see!

Python 3, 160 151 149 bytes
q='\141\156\144'
l='=l\141mb\144\141 x:'
exec(f"f{l}x {q} x[0]+((q+x[:5])*2+q+f(x[4:])if' {q} '==x[:5].lower()else f(x[1:]));g{l}f(' '+x+' ')[1:-1]")

Try it online!
Since xnor said it would take imagination I've gone ahead and done a python answer.  It is more of a proof of concept than anything else since I am quite rusty on python golf.
Explanation
I wrote the pretty straightforward code:
q='and'
f=lambda x:x and x[0]+((q+x[:5])*2+q+f(x[4:])if' and '==x[:5].lower()else f(x[1:]))
g=lambda x:f(' '+x+' ')[1:-1]

Which would solve the problem if it were not for the character restriction.  Then to get around the restriction I used exec with escape codes on all the problematic characters.
exec("q='\141\156\144';f=l\141mb\144\141 x:x \141\156\144 x[0]+((q+x[:5])*2+q+f(x[4:])if' \141\156\144 '==x[:5].lower()else f(x[1:]));g=l\141mb\144\141 x:f(' '+x+' ')[1:-1]")

And since and appeared in the original source 3 times, I moved the definition of q outside the exec and inserted q in those places to save bytes.  I also wrote a substitution for =lambda x: since it appears twice.
q='\141\156\144'
l='=l\141mb\144\141 x:'
exec(f"f{l}x {q} x[0]+((q+x[:5])*2+q+f(x[4:])if' {q} '==x[:5].lower()else f(x[1:]));g{l}f(' '+x+' ')[1:-1]")

I think this doesn't handle and's at the start and end unfortunately.

@xnor Thanks, it's a bit of an odd requirement.  I've fixed it now.

Dyalog APL, 99 95 93 92 39 bytes
(7⍴'\b',⎕ucs 65 78 68)⎕R(15⍴'\l& & ')⍠1

Try it online!
Golfed ... a lot of bytes thanks to @Adám

Golfed some bytes: (7⍴'\b',⎕ucs 65 78 68)⎕R(15⍴'\l& & ')⍠1 Try it online!

JavaScript (ES6),  76 74  73 bytes
Saved 1 byte thanks to @tsh
s=>s.repl\u0061ce(/\b\x61\x6e\x64\b/gi,(x=(y='\x61\x6e\x64')+' $& ')+x+y)

Try it online!
Without escaped characters, this simply reads as:
s=>s.replace(/\band\b/gi,(x=(y='and')+' $& ')+x+y)

s["repl\x61ce"] -> s.repl\u0061ce

@tsh I did not think about that one. Thank you!

PHP, 97 bytes
Saved 17 bytes thanks to Dom Hastings
<?php $b=chr(97);$c=XWT^"990";echo(preg_repl.$b.ce)("/\b$c\b/i","$c \\0 $c \\0 $c",${$b.rgv}[1]);

Try it online!

PHP, 114 bytes
<?php $b=chr(97);$c=$b.chr(110).chr(100);$e=preg_repl.$b.ce;echo$e("/\b($c)\b/i","$c \\1 $c \\1 $c",${$b.rgv}[1]);

Try it online!
Ungolfed
<?php

$b = chr(97);
$c = $b . chr(110) . chr(100);
$e = "preg_repl{$b}ce";

echo $e("/\b($c)\b/i", "$c \\1 $c \\1 $c", ${$b . "rgv"}[1]);

chr(97) resolves to 'a', chr(110) to 'n', and chr(100) to 'd'.
PHP allows you to define a variable as a string, then execute a function with the standard function syntax. e.g.:
$d = 'print';
$d('hello world'); // Parsed as print('hello world');

Using this I am able to execute the preg_replace function by interpolating the chr(97) from earlier and run a case insensitive regex to perform the necessary operation.
The final issue comes from input variables in PHP being e.g. $argv[1] - and they're always argv. Fortunately PHP has a variable variable syntax, so ${'argv'} is the same as $argv - so I simply concatontate my chr(97) to 'rgv' and execute in variable variable syntax.
Finally, a few bytes are saved by using PHP's assumptions. An unquoted string is how to reference a constant in PHP. Undefined constants are assumed to be their own name.

Nice work! You can save a few bytes though: you don't need to define $e=preg_repl.$b.ce, you can just use echo(preg_repl.$b.ce)(...) directly. You can avoid the capture ($c) in your regex and use \\0 to get the contents instead. You can also use stringwise XOR to get and via $c=XWT^"990" (or many other strings!) and either $b=$c[0] or $b=X^"9" to get the a. I can't find a way to get it working on without calling PHP manually via Bash, but you should be able to use -R to skip the <?php  and use $argn instead of $argv[1] for some more savings, but that might be too far!

You can also skip the quotes around "rgv" :)

@DomHastings Thanks for the pointers! I don't golf enough to know all the tricks yet :) The directly calling preg_replace as a string occurred to me but the specific syntax eluded me and I foolishly assumed it was impossible, Also the quotes around "rgv" are only there in my ungolfed version.

So they are, I must've had an older version open!

Entirely possible, I may have made an edit or 12 :)

Instead of <?php $b=chr(97);$c=XWT^"990";, you can do <?$c=XWT^"990";$b=$c[0];. This removes the unnecessary php and the space after (https://www.php.net/manual/en/ini.core.php#ini.short-open-tag), and also assigns the first character of $c into $b, saving 2 bytes.

In fact, just removing the variable $b and doing (preg_repl.$c[0].ce) and ${$c[0].rgv}[1] should save you more 2 bytes. The final code will be: <?$c=XWT^"990";echo(preg_repl.$c[0].ce)("/\b$c\b/i","$c \\0 $c \\0 $c",${$c[0].rgv}[1]); (88 bytes). You can try it on: http://sandbox.onlinephpfunctions.com/code/129da0dd7d0d928843b7240a0738dbe62b24f10e (Also, if you use php -r, you might save more bytes)

By the way, if you decide to do not use php -r (don't have how to test it, and the Try It Online website is horrible to use) you can just do this instead: <?=(preg_repl.($c=XWT^"990")[0].ce)("/\b$c\b/i","$c \\0 $c \\0 $c",${$c[0].rgv}[1]); which reduces the code to 84 bytes. <?= is the same as <?php echo.

Also, instead of \\0, you can use $0 to save +2 bytes. The final version would look like <?=(preg_repl.($c=XWT^"990")[0].ce)("/\b$c\b/i","$c $0 $c $0 $c",${$c[0].rgv}[1]); (82 bytes). In total, saved 15 bytes from your 97 bytes.

@IsmaelMiguel Nice. I did allude to -R too, but your last suggestions are way better than that!

@DomHastings Thank you. I don't think that php -r is a viable option anymore. Or even php -f. Or whichever option has $argn. You would need to do change ${$c[0].rgv}[1]to${$c[0].rg.$c[1]}, which is 2 bytes longer. And you would need to change the <?=intoecho`, which is 3 bytes longer. I think my suggestions are way better too, and yours were as well!

Excel, 437 435
Closing quotes and parens already discounted. It's not pretty, but I found some surprising optimizations.
Setup
Input: C1
Cells B1 to B9 (One cell per row).
 [SPACE]
=B1&LEFT(RIGHT(TEXT(,"[$-33]MMMM"),4),3)&B1
=UPPER(B2)
=LEFT(B2,2)&RIGHT(B3,3)
=LEFT(B2,3)&RIGHT(B3,2)
=LEFT(B3,3)&RIGHT(B2,2)
=LEFT(B3,2)&RIGHT(B5,3)
=PROPER(B2)
=LEFT(B2,2)&RIGHT(B6,3)

Cells C2 to C9
=SUBSTITUTE(B1&C1&B1,B2,REPT(B2,5))
=SUBSTITUTE(C2,B3,B2&B3&B2&B3&B2)
=SUBSTITUTE(C3,B4,B2&B4&B2&B4&B2)
=SUBSTITUTE(C4,B5,B2&B5&B2&B5&B2)
=SUBSTITUTE(C5,B6,B2&B6&B2&B6&B2)
=SUBSTITUTE(C6,B7,B2&B7&B2&B7&B2)
=SUBSTITUTE(C7,B8,B2&B8&B2&B8&B2)
=TRIM(SUBSTITUTE(C8,B9,B2&B9&B2&B9&B2))

...where C9 is the final output.
How It Works

B2 - TEXT() creates the text "Phando" (EN January) in Venda, an official language of South Africa. The rest of it extracts the "and" from it and surrounds it with spaces.
The rest of the Cells in Column B simply enumerate all possible capitalizations of "and".
C2 - We first surround the input with spaces so edge handling is easier. Then replace "and" with 5 of itself.
After this, the rest of the cells in column C replace occurrences of the corresponding capitalization permutation in column B with the sandwiched string.
In the last cell, trim off the surrounding spaces.

Note

Nesting the C's gives us no advantage because we trade off the equals sign for the auto-closed parens.

sed, 70 \$\cdots\$ 56 52 bytes
Saved 4 bytes thanks to Dom Hastings!!!
s/\b\x61\x6e\x64\b/& \0 & \0 &/Ig;s/&/\x61\x6e\x64/g

Try it online!
Swaps all occurances of and (which is written in escaped hex as \x61\x6e\x64) in any case surrounded by word boundaries (\b) with: a ampersand (&), followed by that occurance, another ampersand, that occurance again, and finally a third ampersand. Since all input only contains spaces and letters, any ampersands present are there because of those swaps. So they're all replaced with and (\x61\x6e\x64) to complete the process.

+1. Good old RegEx! I don't know much about sed, but you should able to save a couple of bytes removing the capturing parens and using \0 instead of \1 in the replacement!

@DomHastings Nice one - thanks! :-)

Jelly,  23 22 21  20 bytes
Note: ɗ is not a d!
Ḳ,@ṁ5Kɗ€Œlẹ¥¦“2ɼ»Ṗ¤K

A monadic Link accepting a list of characters which yields a list of characters.
Try it online!
How?
Note: and is not in Jelly's dictionary, and its compression is “¡ÞṄɱ» which we could use, but I decided to go with “2ɼ»Ṗ¤ which is also five bytes.
Ḳ,@ṁ5Kɗ€Œlẹ¥¦“2ɼ»Ṗ¤K - Main Link: list of characters, S
Ḳ                    - split (S) at spaces -> list of words
                     - (implicitly set the right argument to:)
                  ¤  -   nilad followed by link(s) as a nilad:
             “2ɼ»    -     compression of "andy"
                 Ṗ   -     pop -> "and"                         -
            ¦        - sparse application...
           ¥         - ...indices: last links as a dyad - f(words, "and")
        Œl           -               lower-case (all the words)
          ẹ          -               indices of ("and" in the lower-cased words)
      ɗ€             - ...action: last three links as a dyad for each - f(word,"and"):
  @                  -               with swapped arguments:
 ,                   -                 pair -> ["and", word]
   ṁ5                -                 mould like five -> ["and", word, "and", word, "and"]
     K               -                 join with spaces
                   K - join with spaces

There you go @KevinCruijssen hope it all makes sense.

Thanks for the heads up. :) Out of curiosity: why isn't and in the dictionary? Jelly has a huge dictionary (how many words does it contain actually? - 05AB1E has 10,000 exactly), so a bit weird such a common word is missing. Does it have to do with the small length that would be rather similar in size uncompressed?

@KevinCruijssen the words are just those which were in Dennis' linuxwords file at the time I believe; 'AND' is in there though. There are almost 250K words in there.

Scala 2.12, 126 116 bytes
"(?i)(\\b\u0061\u006e\u0064\\b)".r repl\u0061ce\u0041llI\u006e(_,m=>{v\u0061l x=m+""toLowerC\u0061se;s"$x $m "*2+x})

You do need to assign that function to a variable of type String => String, though, and enable postfix operators (to save 1 byte). This adds 21 more characters.
def f:String=>String="(?i)(\\b\u0061\u006e\u0064\\b)".r repl\u0061ce\u0041llI\u006e(_,m=>{v\u0061l x=m group 0 toLowerC\u0061se;s"$x $m $x $m $x"})

After Scala 2.13, you need to use backticks around variable names when using unicode escapes, hence Scala 2.12.2.
Try it online
Prettier version
val f: String => String = s =>
  raw"(?i)(\band\b)".r.replaceAllIn(s,
    m => {
      val x = m.group(0).toLowerCase
      s"$x $m $x $m $x"
    })

That def has a d.

@xnor Didn't notice that! Fixed now, but had to add 5 extra characters :(

Japt, 22 21 bytes
Work in progress
r`%ß@%b`È3ÇXvÃqXû5}'i

Try it
Original (w/ -S flag)
¸cÈv ¶`ß@`Å?5ogX¸iXv:X

Try it
¸cÈv ¶`ß@`Å?5ogX¸iXv:X     :Implicit input of string
¸                          :Split on spaces
 c                         :Map then flatten
  È                        :Passing each X through the following function
   v                       :  Lowercase
     ¶                     :  Test for equality with
      `ß@`                 :    The compressed string "band" ("and" compressed is also 2 bytes but includes the "d")
          Å                :    Slice off the first character
           ?               :  If true
            5o             :    Range [0,5)
              g            :    Index (0-based) each into
               X¸          :      Split X on spaces, converting it to a single element array
                 i         :      Prepend
                  Xv       :        Lowercase X
                    :X     :  Else return X
                           :Implicit output joined by spaces

Haskell, 177 bytes
r x|_:z:_<-[x..]=z
(#)=elem.r
f(b:t@(c:e:g:h:s))|u<-b:c:e:g:" ",[b,h]<" !",c#"bB",e#"oO",g#"eE",i<-r<$>"`mc"=b:i++u++i++u++i++f(h:s)
f" "=""
f(b:t)=b:f t
g x|_:y<-f$' ':x++" "=y

Try it online!
Explanation
r takes a character and returns the next character in ASCII order.  That is to say its successor.
Then we use this to make (#) which takes a character and a list and checks if that character's successor is in the list.
Then we use that to make f.
Many of the functions I would really like to use from Haskell are missing.
More boring version, 174 bytes
(#)=elem
f(b:t@(c:e:g:h:s))|u<-b:c:e:g:" ",[b,h]<" !",c#"\65\97",e#"\78\110",g#"\68\100",i<-"\97\110\100"=b:i++u++i++u++i++f(h:s)
f" "=""
f(b:t)=b:f t
g x|_:y<-f$' ':x++" "=y

Try it online!
This version forgoes using r to generate forbidden characters and instead escapes them.  Boring but saves 3 bytes.

GNU sed, 38 bytes
s/\<\c!\c.\c$\>/\L&\E & \L&\E & \L&/Ig

"and" is written escaped as \c!\c.\c$. \cx means take the character x, convert it to upper case if it is a lower case letter, and then flip bit 6. The surrounding \< and \> mean word boundaries. & corresponds to the matched string. \L switches to lowercase, and \E switches back. The I modifier means ignore case when matching. The g modifier means replace all matches, not just the first.
Try it online!

Nice answer (based on the description). Could you perhaps add a try it online link with the test cases, assuming the language sed from the list is the one you've used. If GNU sed is not available on TIO, could you perhaps add a screenshot as verification for the answer instead? Oh, and welcome to CGCC! :) Nice first answer.

@KevinCruijssen Thanks. I added the TIO link, as requested. Nowadays, sed pretty much means GNU sed, and it seems to work in the TIO environment.

Thanks for adding it, all seem to work fine, as expected. I had already upvoted, so I can't do it again. Good luck with future challenges, and enjoy your stay! :)

Wolfram Language (Mathematica), 116 112 bytes
-4 bytes thanks to att!
Stri\.6egRepl\.61ce[a:Regul\.61rExpressio\.6e["(?i)\\b"<>#<>"\\b"]:>Stri\.6egRiffle@{#,a,#,a,#}]&@"\.61\.6e\.64"

Try it online! An expression that evaluates to a function. Uses the standard regex (?i)\band\b. For reference, the shortest equivalent function that doesn't use a regex is 118 bytes:
Stri\.6egRepl\.61ce[a=WordBou\.6ed\.61ry;a~~b:#~~a:>Stri\.6egRiffle@{#,b,#,b,#},Ig\.6eoreC\.61se->1>0]&@"\.61\.6e\.64"

112 bytes

Charcoal, 29 bytes
≔“1“$K”η⪫Ｅ⪪Ｓ ⎇⁼↧ιη⪫⟦ηιηιη⟧ ι

Try it online! No verbose mode because it won't "compress" the string for me. Explanation:
≔“1“$K”η

Assign the compressed string and to a variable. (None of the various ways of compressing the string and uses a banned letter; this is just the shortest option, after banning the uncompressed string.)
   Ｓ                    Input string
  ⪪                     Split on literal space
 Ｅ                      Map over words
        ι               Current word
       ↧                Lowercased
      ⁼                 Equals
         η              "and"
     ⎇                  If true then
           ⟦ηιηιη⟧      Alternate lowercase and original word
          ⪫             Join with literal space
                   ι    Otherwise the original word
⪫                       Join everything with literal space
                        Implicitly print

Pip -s, 34 bytes
Y Jz@[i13 3]{(gPEyLC@gQy?,5o)}Mq^s

Try it online!
Explanation
Non-regex solution taking advantage of the "letters and spaces only" rule. Partially inspired by Jonathan Allan's Jelly answer.
Y Jz@[i13 3]{(gPEyLC@gQy?,5o)}Mq^s
                                    z is lowercase alphabet; i is 0; o is 1 (implicit)
   z@[i13 3]                        Get the lowercase letters at indices 0, 13, and 3
  J                                 Join them into the string "and"
Y                                   Yank that into the variable y
                               q    Read a line of input from stdin
                                ^s  Split on spaces
            {                }M     Map this function:
              g                      The list of arguments: [word]
               PEy                    with y prepended: ["and" word]
             (              )        Index this list with the following index:
                        ?             If
                    @g                 the first argument
                  LC                   lowercased
                      Qy               equals y
                         ,5           then range(5)
                           o          else 1

Here's what the indexing does: If the word we're processing is some case-variant of "and", we get the first five elements of the list ["and" word]. With cyclic indexing, this amounts to ["and" word "and" word "and"]. If the word is some other word, we get the element at index 1, which is just word.
The result is a (possibly nested) list, which the -s flag joins on spaces and then autoprints. An example run:
q       "Stand aNd  watch"
q^s     ["Stand" "aNd" "" "watch"]
{ }Mq^s ["Stand" ["and" "aNd" "and" "aNd" "and"] "" "watch"]
Output: Stand and aNd and aNd and  watch

Pip, 34-bytes (no flags)
Y Jz@[i13 3]qR-:yWR`\b`yWR` & `WRy

Try it online!
Explanation
My initial solution using regex:
Y Jz@[i13 3]qR-:yWR`\b`yWR` & `WRy
                                    z is lowercase alphabet; i is 0 (implicit)
   z@[i13 3]                        Get the lowercase letters at indices 0, 13, and 3
  J                                 Join them into the string "and"
Y                                   Yank that into the variable y
            q                       Read a line of input from stdin
             R                      In that string, replace
                y                    the string "and"
                 WR`\b`              wrapped in the regex `\b`: `\band\b`
              -:                     with the case-insensitive flag set: `(?i)\band\b`
                                    with
                       y             the string "and"
                        WR` & `      wrapped in the regex ` & `: ` & and & `
                               WRy   wrapped in the string "and": `and & and & and`
                                     (where & in replacement context stands for the
                                     full match)
                                    Autoprint (implicit)

Stax, 32 26 bytes
å╔é╩⌐╬²ßxæ╬:Ö5ò▌@ Θ5YS₧Ñπε

Run and debug it
I knew packed stax mutation was good for something.
Saved 6 bytes thanks to an anonymous donor.

https://staxlang.xyz/#p=86c982caa9cefde17891ce3a993595dd4020e93559539ea5e3ee&i=and+-+AnD+-+AND%0Aandy%27s+band&a=1&m=2 for 26

Lua, 151 bytes
b="\97\110\100"_G["lo\97\100"]('pri\110t(\97rg[1]:gsub("%w+",fu\110ctio\110(s)retur\110 s:lower()==b '..b..' (b.." "..s.." "):rep(2)..b e\110\100))')()

Try it online!
How It Works
b is a string which is equal to "and" via ASCII escape codes.
_G in Lua is the "global environment table", the data structure containing all global variables. We can index this with a string, which can contain ASCII codes for the forbidden letters.
load() returns a function from the string passed to it (which we immediately call). Again, ASCII codes are used here for forbidden characters.
arg is the command-line arguments table
gsub() is a Global SUBstitution function, it takes a pattern (in this case a sequence of 1 or more alphanumeric characters) and replaces it according to the second parameter, in this case an anonymous function which it calls for every match.
and is a boolean operator which return the right-hand-side of the operation or false.
rep() is a string repetition function.
Readable Version
-- Match Every Word, Replacing Any "and"s
print(arg[1]:gsub("%w+",function(s)
    return s:lower() == "and" and ("and "..s.." "):rep(2).."and"
end))