text:
Single swaps of an array
Inspired by Taken from a question at Stack Overflow.
The challenge
Given an integer n>1, output all arrays that can be obtained by swapping exactly two entries in the array [1, 2, ..., n].
The arrays can be produced in any order.
You can consistently use [0, 1, ..., n-1] (0-based) instead of [1, 2, ..., n] (1-based).
Additional rules

Input and output are flexible as usual.

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

Shortest code in bytes wins.

Test cases
Input 2 gives output (assumed 1-based)
2 1

Input 3 gives output (note that the three arrays could be in any order)
1 3 2
2 1 3
3 2 1

Input 4 gives output
1 2 4 3
1 3 2 4
1 4 3 2
2 1 3 4
3 2 1 4
4 2 3 1

Input 7 gives output
1 2 3 4 5 7 6
1 2 3 4 6 5 7
1 2 3 4 7 6 5
1 2 3 5 4 6 7
1 2 3 6 5 4 7
1 2 3 7 5 6 4
1 2 4 3 5 6 7
1 2 5 4 3 6 7
1 2 6 4 5 3 7
1 2 7 4 5 6 3
1 3 2 4 5 6 7
1 4 3 2 5 6 7
1 5 3 4 2 6 7
1 6 3 4 5 2 7
1 7 3 4 5 6 2
2 1 3 4 5 6 7
3 2 1 4 5 6 7
4 2 3 1 5 6 7
5 2 3 4 1 6 7
6 2 3 4 5 1 7
7 2 3 4 5 6 1

Entries at indexes given by https://oeis.org/A211369 plus one (or two if 0-indexing) in a lexicographically sorted list of all the permutations of length n.

I appreciate the flexibility of [0 ... n-1] vs [1 ... n]! I always feel a little annoyed when I have to tack on a 1+ because J zero-indexes.

Jelly, 11 8 bytes
ŒcżU$y€R

Try it online!
How it works
ŒcżU$y€R  Main link. Argument: n

Œc        Take all 2-combinations of [1, ..., n].
  żU$     Zip the result with the reversed pairs.
       R  Range; yield [1, ..., n].
     y€   For each [[i, j], [j, i]] in the result to the left, yield the result to
          the right, with i replaced by j and vice versa.

What exactly does y do? It's always been a bit of a mystery to me.

It performs replacements. For example, [1,2],[4,3]y1,2,3 replaces each 1 in [1, 2, 3] with 4, and each 2 with 3.

R, 54 bytes
function(n)combn(n,2,function(x){z=1:n
z[x]=rev(x)
z})

Try it online!
Returns a matrix where each column is a permutation.
combn(n,k) generates all combinations of size k from the list n, or from 1:n if n is a single integer. It also optionally takes a function FUN to be applied to the resultant combinations. So we write a function that performs the swap and returns the swapped list. The results are then all accumulated into an array, which is in this case 2-dimensional and hence a matrix.

Python 2, 71 bytes
r=range(input())
print[map({i:j,j:i}.get,r,r)for i in r for j in r[:i]]

Try it online!
Uses this tip.

Haskell, 62 bytes
f n=[[1..x-1]++y:[x+1..y-1]++x:[y+1..n]|x<-[1..n],y<-[x+1..n]]

Try it online!
I just generate the permutation, given the x and y to swap, for each x,y

Python 2, 72 bytes
r=range(input())
for j in r:
 for i in r[:j]:t=r*1;t[i]=j;t[j]=i;print t

Try it online!

Wolfram Language (Mathematica), 43 bytes
r/.{#->#2,#2->#}&@@@Subsets[r=Range@#,{2}]&

Try it online!
Explanation: Subsets[Range@#,{2}] generates all subsets of {1,2,...,n} of size 2, then for each subset, /. swaps those two things in the list {1,2,...,n}.
That approach is disappointingly similar to many of the other submissions, but here's one that's more unique to Mathematica, for 3 extra bytes:
r~Permute~Cycles@{#}&/@Subsets[r=Range@#,{2}]&

Try it online!

An even more idiomatic Mathematica solution would be ReplaceList[Range@#,{a___,b_,c___,d_,e___}:>{a,d,c,b,e}]&. I like how simple it is (or how directly it encodes the problem), but unfortunately the pattern matching syntax is so verbose that this ends up being 57 bytes.

Haskell, 62 bytes
g n|b<-[1..n]=[[last$k:[j|k==i]++[i|k==j]|k<-b]|i<-b,j<-b,j<i]

Try it online!
i<-b                -- loop 'i' through [1..n]
     j<-b           -- loop 'j' through [1..n]
          j<i       -- consider only cases where j<i
 [            k<-b] -- make a list by looping 'k' through [1..n]
  last              -- pick
          [i|k==j]  -- 'i' if k==j
       [j|k==i]     -- 'j' if k==i
     k              -- 'k' else

Haskell, 71 bytes
f 0=[]
f x=map(++[x])(f$x-1)++[[1..y-1]++x:[y+1..x-1]++[y]|y<-[1..x-1]]

Try it online!

This adds the current number to the end of all the permutations of last and then computes all the swaps that include the new number.

MATL, 12 bytes
:2XN!"G:@tP(

Try it online!
            %implicit input, say, 4
:           %range, stack is {[1,2,3,4]}
2           %push 2
XN          %nchoosek, compute all combinations of [1,2,3,4] taken 2 at a time
            %this results in a matrix where each row is a combination, i.e.,
            %[1, 2;
              1, 3;
              1, 4;
              2, 3;
              2, 4;
              3, 4]
!           %transpose, because "for" iterates over columns
"           %begin for loop
G:          %push input and range, stack is now [1,2,3,4]
@t          %push "for" index (the column), say, [1;2], twice
P           %flip array, so stack is now: {[1,2,3,4],[1;2],[2;1]}
(           %assignment index, sets [1,2,3,4]([1;2])=[2;1],
            %resulting in [2,1,3,4]
            %implicit end of loop, implicit end of program, print the stack implicitly.

2 bytes shorter than the code I used to generate the test cases, and way more effcient :-)

@LuisMendo How did you generate the test cases? I was worried mine was longer since the order wasn't the same!

I used :tY@wy=~!s2=Y). Same approach as rahnema1's Octave answer, I think

C, 93 bytes
i,j,k;f(n){for(i=0;i++<n;)for(j=i;j++<n;puts(""))for(k=0;k++<n;)printf("%d ",k-i?k-j?k:i:j);}

Try it online!

Octave, 38 bytes
@(n)(p=perms(k=1:n))(sum(p~=k,2)==2,:)

Try it online!
Generates all permutations of 1:n and select from them those that have two elements different from 1:n.

Clean, 90 82 bytes
import StdEnv
$n#n=[1..n]
=tl(removeDup[[if(c<>b)if(c<>a)c b a\\c<-n]\\b<-n,a<-n])

It can be done in 80 bytes, but it turns into a direct translation of the Haskell answers.
Try it online!

JavaScript (ES6), 81 bytes
Prints 0-indexed arrays.
n=>(a=[...Array(n).keys()]).map(i=>a.map(j=>i>j&&alert(a.map(k=>k-i?k-j?k:i:j))))

Demo
alert() is replaced with console.log() in this snippet for user-friendliness.

let f =

n=>(a=[...Array(n).keys()]).map(i=>a.map(j=>i>j&&alert(a.map(k=>k-i?k-j?k:i:j))))

alert = s => console.log(JSON.stringify(s));

f(4)

Husk, 9 bytes
!2§kδ#≠Pḣ

Try it online!
Explanation
!2§kδ#≠Pḣ  Input is an integer n.
        ḣ  Range: r=[1,2,..,n]
       P   Permutations of r.
   k       Classify by
     #     number of elements
      ≠    that are different from
  § δ      the corresponding element of r.
!2         Take the second class.

Ruby, 55 53 bytes
->n{n.times{|x|x.times{|y|(w=*0...n)[w[x]=y]=x;p w}}}

Try it online!
0-based solution
The trick here is that the inner loop always "skips" an iteration: the first time it's not executed at all, then only once on the second pass, and so on.
I was happy with 55 bytes until I saw that R could be golfed down to 54, so I had to get it to 53.

Very clever use of flexible output constraints.

Python 2, 75 bytes
lambda n:[r(i)+[j]+r(i+1,j)+[i]+r(j+1,n)for j in r(n)for i in r(j)]
r=range

Try it online!

05AB1E, 15 9 bytes
LœʒD{αĀO<

Try it online!
Explanation
L            # push range [1 ... input]
 œ           # get all permutations
  ʒ          # filter, keep only elements that are true when
     α       # absolute value is taken with
   D{        # a sorted copy
      Ā      # each non-zero value in the resulting array is converted to 1
       O     # the array is summed
        <    # and the sum is decremented

Python 2, 90 bytes
f=lambda n,r=range:n*[n]and[a+[n]for a in f(n-1)]+[r(1,i)+[n]+r(i+1,n)+[i]for i in r(1,n)]

Try it online!

Ruby, 66 bytes
->n{a=*1..n
a.permutation.select{|b|b.zip(a).count{|c,d|c!=d}==2}}

Try it online!

Pyth, 11 bytes
fq2snVTUQ.p

Try it online
Not as short as isaacg's approach, but different enough to post.
Explanation
fq2snVTUQ.p
         .pQ  Take the permutations of the (implicit) range [0,...,input].
f     T       Filter to get the permutations...
   snV UQ     ... where the number of differences with [0,...,input]...
 q2           ... is 2.

Java 8, 109 105 bytes
n->{String r="";for(int i=0,j,k;i++<n;)for(j=i;j++<n;r+="\n")for(k=0;k++<n;)r+=k!=i?k!=j?k:i:j;return r;}

I'm rusty.. Haven't code-golfed in months.. Ended up porting @Steadybox' C answer.. Can probably be golfed some more.
Try it here.

Ruby, 80 bytes
-12 bytes thanks to Unihedron.
->n{(r=1..n).map{|x|r.map{|y|r.map{|i|i==x ?y:i==y ?x:i}}}.flatten(1).uniq[1,n]}

Try it online!
I had an approach in mind that best translated to Ruby for some reason so... I don't even really know Ruby...

I outgolfed this: https://codegolf.stackexchange.com/a/152652/21830. Sorry!

No need to apologize! I think I speak for most PPCG users when I say that the competition is what makes PPCG cool.

As for your code, 1. you could assign 1..n to a one-char variable and reuse it (separate statements with newline or semicolons), 2. do without brackets in the termary statements: i==x ?y:i==y ?x:i (note where I have the spaces to seperate the potential shebang) and 3. uniq[1,n] instead of uniq[1..-1].

Pyth, 9 bytes
t{.rLQ*=U

Demonstration
The easiest way to swap two values is to use .r, which is Pyth's rotary translation function. .r<list>[A, B] will swap all occurrences of A and B in list.
Therefore, by applying the translation function to UQ, the list from 0 to n-1 with each two element list of different numbers in the list, we will generate the desired output. Q is the input, n, and U is the range function.
The easy way to do this would be:
.rLUQ.cUQ2

.cUQ2 generates all 2 element combinations of distinct elements in the range, and .rLUQ maps the .r function over them and the list UQ.
However, that would be 10 bytes.
Instead of making .cUQ2, the distinct ordered pairs, we can make all pairs with *=U. This is implicitly equivalent to *=UQQ. It starts by overwriting Q with UQ, then taking the Cartesian product of UQ and UQ. This gives all pairs of numbers in the range, not necessarily ordered or distinct.
.rLQ swaps using each list. Recall that Q is now equal to the list from 0 to n-1, not n.
Because the pairs were not ordered, there are duplicates. { removes duplicates. Because the pairs were not distinct, the unchanged list is present. This list will always be first after deduplication, because { preserves the order of the first appearance and the unchanged list is produced by rotating by [0,0]. t removes the first element, giving the desired list of swaps.


text:
Maximum run between identical elements

This is a overhaul of this now deleted question by ar kang. If the OP of that question would like to reclaim this question or has a problem with me posting this I'd be happy to accommodate

Given a list of integers as input find the maximum possible sum of a continuous sublist that starts and ends with the same value.  The sublists must be of length at least 2.  For example for the list
[1, 2, -2, 4, 1, 4]

There are 2 different continuous sublists start and end with the same value
[1,2,-2,4,1] -> 6
[4,1,4]      -> 9

The bigger sum is 9 so you output 9.
You may assume every input contains at least 1 duplicate.
This is code-golf so answers will be scored in bytes with fewer bytes being better.
Test cases
[1,2,-2,4,1,4]  -> 9
[1,2,1,2]       -> 5
[-1,-2,-1,-2]   -> -4
[1,1,1,8,-1,8]  -> 15
[1,1,1,-1,6,-1] -> 4
[2,8,2,-3,2]    -> 12
[1,1,80]        -> 2
[2,8,2,3,2]     -> 17

Should [2,8,2,3,2] be 12 or 17? I presume 17.

@NikoNyrh It should be 17.

Hooray for CC BY/SA.  You have the right to post a derivative question of another one, even if it would be later flagged dupe by community members. It just seems you should add a link to the OP's page as I get from this blog post. "3. Show the author names for every question and answer [...] 4. Hyperlink each author name directly back to their user profile page on the source site" - I don't have privileges to see deleted questions, so I don't know who made the original one.

@Mindwin Thanks, I've added a link to the OP's page.  I left it out originally because I figured if the OP deleted their post they might want to avoid being linked to the question.

The reason for deletion is irrelevant and not transparent to the common user (me). But attribution is of the opt-out kind. By submitting and agreeing to the license they granted us those rights under those conditions. Anything outside it is an exception. GJ.

Haskell, 62 bytes
f takes a list of integers and returns an integer.
f l=maximum[x+sum m-sum n|x:m<-t l,y:n<-t m,x==y]
t=scanr(:)[]

Try it online!
How it works

t is the standard "get all suffixes of a list without importing Data.List.tails" function.
In f l, the list comprehension iterates through all the non-empty suffixes of the argument list l, with first element x and remainder m.
For each, it does the same for all nonempty suffixes of m, selecting first element y and remainder n.
If x and y are equal, the list comprehension includes the sum of the elements between them. This sublist is the same as x:m with its suffix n stripped off, so the sum can be calculated as x+sum m-sum n.

JavaScript (ES6), 68 62 bytes
a=>a.map(m=(x,i)=>a.map((y,j)=>m=j<=i||(x+=y)<m|y-a[i]?m:x))|m

Test cases

let f =

a=>a.map(m=(x,i)=>a.map((y,j)=>m=j<=i||(x+=y)<m|y-a[i]?m:x))|m

console.log(f([1,2,-2,4,1,4] )) // -> 9
console.log(f([1,2,1,2]      )) // -> 5
console.log(f([-1,-2,-1,-2]  )) // -> -4
console.log(f([1,1,1,8,-1,8] )) // -> 15
console.log(f([1,1,1,-1,6,-1])) // -> 4
console.log(f([2,8,2,-3,2]   )) // -> 12
console.log(f([1,1,80]       )) // -> 2

Commented
a =>                    // a = input array
  a.map(m =             // initialize m to a function (gives NaN in arithmetic operations)
    (x, i) =>           // for each entry x at position i in a:
    a.map((y, j) =>     //   for each entry y at position j in a:
      m =               //     update m:
        j <= i ||       //       if j is not after i
        (x += y) < m |  //       or the sum x, once updated, is less than m
        y - a[i] ?      //       or the current entry is not equal to the reference entry:
          m             //         let m unchanged
        :               //       else:
          x             //         update m to the current sum
    )                   //   end of inner map()
  ) | m                 // end of outer map(); return m

I was slightly confused by the ordering of y - a[i] and (x += y) < m - IMHO the code would be slightly clearer with them exchanged, since then it looks like a simple golf from (x += y) < m || y != a[i].

@Neil I see your point but (x+=y)<m|y-a[i] could be misinterpreted as (x+=y)<(m|y-a[i]) just as well. I'm not sure it would really strip away the ambiguity. (Edited anyway because I tend to prefer this version.)

Well, that assumes that they wouldn't misinterpret y-a[i]|(x+=y)<m as (y-a[i]|(x+=y))<m...

Husk, 10 bytes
▲mΣfΓ~€;ṫQ

Try it online!
Explanation
▲mΣfΓ~€;ṫQ  Input is a list, say x=[1,2,-2,4,1,4]
         Q  Slices: [[1],[2],[1,2],..,[1,2,-2,4,1,4]]
   f        Keep those that satisfy this:
    Γ        Deconstruct into head and tail, for example h=2 and t=[-2,4,1]
        ;    Wrap h: [2]
      ~€     Is it an element of
         ṫ   Tails of t: [[-2,4,1],[4,1],[1]]
            Result: [[1,2,-2,4,1],[4,1,4]]
 mΣ         Map sum: [6,9]
▲           Maximum: 9

Jelly, 12 bytes
ĠŒc€Ẏr/€ịḅ1Ṁ

Try it online!
How it works
ĠŒc€Ẏr/€ịḅ1Ṁ  Main link. Argument: A (array)

Ġ             Group the indices of A by their corresponding values.
 Œc€          Take all 2-combinations of grouped indices.
    Ẏ         Dumps all pairs into a single array.
     r/€      Reduce each pair by range, mapping [i, j] to [i, ..., j].
        ị     Index into A.
         ḅ1   Convert each resulting vector from base 1 to integer, effectively
              summing its coordinates.
           Ṁ  Take the maximum.

Python, 62 bytes
f=lambda l:l and max(f(l[1:]),[sum(l)]*(l.pop()in l[:1]),f(l))

Try it online!
Outputs a singleton list.

R, 108 103 90 88 83 bytes
function(l)max(combn(seq(l),2,function(x)"if"(rev(p<-l[x[1]:x[2]])-p,-Inf,sum(p))))

Try it online!
combn strikes again! Generates all sublists of length at least 2, sets the sublist sum to -Inf if the first and last are not equal, and takes the max of all the sums.
The "if" will raise a bunch of warnings but they are safely ignorable -- that's probably the best golfing trick here, rev(p)-p is zero in the first element iff p[1]==tail(p,1), and "if" uses the first element of its condition with a warning.

Haskell, 66 bytes
maximum.f
f(x:y)=[sum$x:take a y|(a,b)<-zip[1..]y,b==x]++f y
f x=x

Try it online!

Python 3, 81 bytes
lambda x,e=enumerate:max(sum(x[i:j+1])for i,a in e(x)for j,b in e(x)if(a==b)*j>i)

Try it online!

Jelly, 13, 12 bytes
=ṚṖḢ
ẆÇÐfS€Ṁ

Try it online!
One byte saved by Mr. Xcoder, who is currently competing with me. :D
Explanation:
        # Helper link:
=Ṛ      # Compare each element of the list to the element on the opposite side (comparing the first and last)
  Ṗ     # Pop the last element of the resulting list (so that single elements return falsy)
   Ḣ    # Return the first element of this list (1 if the first and last are equal, 0 otherwise)

        # Main link:
Ẇ       # Return every sublist
 Ç      # Where the helper link
  Ðf    # Returns true (1)
    S€  # Sum each resulting list
      Ṁ # Return the max

Wolfram Language (Mathematica), 54 bytes
Max@SequenceCases[#,{a_,b___,a_}:>2a+b,Overlaps->All]&

Try it online!

Jelly, 11 bytes
Uses some features that post-date the challenge.
Ẇµ.ịEȧḊµƇ§Ṁ

Try it online!
How it works?

Ẇµ.ịEȧḊµƇ§Ṁ  || Full program. Takes input from CLA, outputs to STDOUT.
Ẇ            || Sublists.
 µ     µƇ    || Filter-Keep those
    ȧḊ       || ... Which have length at least 2 and ...
 .ị          || ... The elements at floor(0.5) and ceil(0.5) (modular, 1-indexed) ...
    E        || ... Are equal.
         §   || Sum each.
          Ṁ  || Maximum.

-1 with help from caird.

Python 2, 86 bytes
Outgolfed by Dennis
lambda x:max(sum(x[i:j+1])for i,v in enumerate(x)for j in range(i+1,len(x))if v==x[j])

Try it online!
Generates all sublists larger than length 2, where the first element is equal to the last, then maps each to its sum and selects the largest value.

88 bytes using a lambda function

@HalvardHummel 86 bytes using enumerate.

Outgolfed by Dennis – Honestly, what did you expect?

@Mr.Xcoder I would have got his solution, but I went to sleep :(

Pyth, 15 bytes
eSsMf&qhTeTtT.:

Try it online
Explanation
eSsMf&qhTeTtT.:
             .:Q  Take all sublists of the (implicit) input.
    f qhTeT       Take the ones that start and end with the same number...
     &     tT     ... and have length at least 2.
  sM              Take the sum of each.
eS                Get the largest.

05AB1E, 9 bytes
ŒʒćsθQ}OZ

Try it online!
Explanation
Œ          # push sublists of input
 ʒ    }    # filter, keep values where
  ć        # the head of the list, extracted
     Q     # is equal to
   sθ      # the last element of the rest of the list
       O   # sum the resulting sublists
        Z  # get the max

Clean, 94 90 86 bytes
import StdEnv,StdLib
@l=last(sort[sum(l%(i,j))\\e<-l&i<-[0..],j<-elemIndices e l|j>i])

Try it online!

I'm afraid this fails for the [1, 1, 80] test case.

@ØrjanJohansen fixed it

Ruby, 64 bytes
->l{w,*r=0;(z=l.index w)&&r<<w+l[z..-1].sum while w=l.pop;r.max}

Try it online!

Julia 0.6, 70 bytes
a->maximum(sum(a[i:k]) for b=[findin(a,x) for x=a] for i=b,k=b if k>i)

Try it online!

Java 8, 129 byes
a->a.stream().map(b->a.subList(a.indexOf(b),a.lastIndexOf(b)+1).stream().mapToLong(Long::intValue).sum()).reduce(Long::max).get()

For each integer X in the list, the function finds the sum of the largest sublist with start and end X. Then, it finds the maximum sum as the OP specifies.

I haven't tested it, but that looks to me like it might fail on the [2,8,2,-3,2] test case, and possibly [1,1,80] too.

C, 104 bytes
i,j,s,l;f(a,n)int*a;{for(i=0,l=1<<31;i<n;++i)for(s=a[j=i];++j<n;l=a[j]-a[i]?l:s>l?s:l)s+=a[j];return l;}

Try it online!
C (gcc), 99 bytes
i,j,s,l;f(a,n)int*a;{for(i=0,l=1<<31;i<n;++i)for(s=a[j=i];++j<n;l=a[j]-a[i]?l:s>l?s:l)s+=a[j];l=l;}

Try it online!

99 bytes, if you like undefined behaviour.

Batch, 179 bytes
@set s=%*
@set/a"m=-1<<30
:l
@set/at=n=%s: =,%
@set s=%s:* =%
@for %%e in (%s%)do @set/at+=%%e&if %%e==%n% set/a"m+=(m-t)*(m-t>>31)
@if not "%s%"=="%s: =%" goto l
@echo %m%

Takes input as command-line parameters.

Clojure, 92 bytes
#(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))

Perl, 61 59 bytes
Includes +3 for -p:
max_ident_run.pl:
#!/usr/bin/perl -p
s:\S+:$%=$&;($%+=$_)<($\//$%)||$_-$&or$\=$%for<$' >:eg}{

Run as:
max_ident_run.pl <<< "1 2 -2 4 1 4 1"

source: Stack Exchange

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

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

sort: votes


text:
Write it into number theory style
Write a mathematical statement, using the symbols:

There exists at least one non-negative integer (written as E, existential quantifier)
All non-negative integers(written as A, universal quantifier)
+ (addition)
* (multiplication)
= (equality)
>, < (comparison operators)
&(and), |(or), !(not)
(, ) (for grouping)
variable names

which is equivalent to the statement

There exists a rational number a, such that π + e * a is rational.

(of course, \$\pi =3.1415...\$ is the mathematical constant equal to the circumference divided by the diameter of a circle, and \$e=2.7182...\$ is Euler's number)
You must prove that your statement is indeed equivalent to the statement above.
Obviously, the “shortest” way to go about this is to prove the statement true or false, and then answer with a trivially true or false statement, as all true statements are equivalent to one another, as are all false statements.
However, the given statement’s truth value is an unsolved problem in mathematics: we don't even know if \$\pi+e\$ is irrational! Therefore, barring groundbreaking mathematical research, the challenge is to find a “simple” equivalent statement, prove its equivalence, and describe it as briefly as possible.
Scoring
E A + * = > < & | and ! each add 1 to the score. ( and ) don't add anything to the score. Each variable name adds 1 to the score.
E.g. E x (A ba x+ba>x*(x+ba)) score 13 (E x A ba x + ba > x * x + ba)
Lowest score wins.

Note:
Disclaimer: This note was not written by the OP.

This is not a code-golf challenge. Answers are not required to contain code.
This is similar to, but not, a proof-golf challenge, as you need to write a statement and prove it being equivalent to another statement.
You are allowed to submit a trivially-true (e.g., for all x, x = x Ax x=x) or a trivially-false statement (e.g., for all x, x > x Ax x>x) if you can prove the statement above is true/false.
You are allowed to use additional symbols (similar to lemma in proof-golf), but the score would be counted the same as you not using them.
For example, if you define a => b to mean (!a) | b, each time you use => in your proof, your score increases by 2.
Because constants are not listed in the allowed symbols, you must not use them.
For example: The statement 1 > 0 can be written as

Forall zero: ( zero + zero = zero ) =>
Forall one: ( Forall x: x * one = x ) =>
one > zero

at the score of 23. (remember that => costs 2 per use).

Hints

To use natural constants, you may do E0, 0+0=0 & E1, At 1*t=t & (so you don't need => which is more expansive); for numbers larger than 1, just add some 1's

I like the concept here, but the statement is really hard to write and I'd be impressed by any solution no matter the score. I would have suggested using something simpler so more people participate.

You require a mathematical statement which is equivalent to the given one. In which sense should they be equivalent? If I am correct, the given statement is a false one. So its equivalence with other statements is hard for me to grasp. For example, is it equivalent to There exists a rational number a, such that i + e * a is rational (where i is the imaginary unit)?

Current note just say You are allowed to submit a trivially-true (e.g., for all x, x = x Ax x=x) or a trivially-false statement (e.g., for all x, x > x Ax x>x) if you can prove the statement above is true/false.. The statement is now neither proved nor disproved, so I really don't mind if problem gets boring because such a problem is solved

The question as written seemed to majorly bury the lede, and avoid explaining what’s really going on, so I wrote a little explanation in the notes (that the non-triviality of the challenge is hinged on the currently unknown truth value of the given statement).

I'd be impressed by any solution no matter the score. The score was only to make an aim for those who can solve this problem

p.s. if constants are allowed, each add 1 or 2 to the score, will the solution score have a big fall?

270
E1                                                                              { Exist 1, defined when Any k introduced }
Ec1 Ec2 Ec3 Ec4 Ec5 Ak k*1=k & c3>1 & ( En0 An n<n0 |                           { for large enough n, |(c1-c4)e+c3(4-pi)/8+(c2-c5)|<1/k }
Ex Ep Ew Emult At (Eb ((b>1 & Eh b*h=t) &! Eh h*p=b)) |                         { x read in base-p, then each digit in base-w. t as a digit }
Ee1 Ee2 Ehigher Elower e2<p & lower<t & ((higher*p+e1)*p+e2)*t+lower=x &        { last digit e1, this digit e2 }
    { Can infer that e2=w+1 | e1<=e2 & u1<=u2 & i1<=i2 & s1<=s2 & t1<=t2, so some conditions omitted }
Ei1 Es1 Et1 Eu1 (((u1*w)+i1)*w+t1)*w+s1=e1 &                                    { (u,i,t,s) }
Ei2 Es2 Et2 Eu2 i2<w & s2<w & t2<w & (((u2*w)+i2)*w+t2)*w+s2=e2 &               { e2=1+w is initial state u=i=0, s=t=1 }
(e2=w+1 | e1=e2 | i2=i1+1+1 & s2=s1*(n+1) & t2=t1*n &                           { i=2n, s=(n+1)^n, mult=t=n^n, s/mult=e }
Eg1 Eg2 g1+1=(i2+i2)*(i2+i2) & g1*u1+mult=g1*u2+g2 & g2<g1) &                   { u/mult=sum[j=4,8,...,4n]1/(j*j-1)=(4-pi)/8. mult=g1*(u2-u1)+g2 }
(t>1 | i2=n+n & t2=mult & Ediff Ediff2                                          { check at an end t=1 }
c1*s2+c2*mult+c3*u2+diff=c4*s2+c5*mult+diff2 & k*(diff+diff2)<mult))            { |diff-diff2|<=diff+diff2<mult/k, so ...<1/k }

a|b&c is a|(b&c) since I think removing these parentheses makes it look better, anyway they're free.
Used JavaScript "(expr)".replace(/\{.*?\}/g,'').match(/[a-z0-9]+|[^a-z0-9\s\(\)]/g) to count tokens.

Why can you take mult = t? Also since x can only have finitely many digits, you’ll need to allow for e1 = e2 = 0 for sufficiently large t. Also you’ll need more parentheses or other disambiguation for  ambiguous constructs like _ & _ | _.

@AndersKaseorg I multiply every item mult. Don't see any problem mult=t2 at the end. e1=e2=0 should be fixed but not that certain, so I currently don't change the acception.

If a & b | c is (a & b) | c then your t*1=t is definitely in the wrong place. Also you haven't excluded the trivial solution c1 = c4 & c2 = c5 & c3 = 0 & diff = diff2.

@AndersKaseorg Do my reason why diff≠diff2 work?

Anyway I can use !(c2=c5) as we already know e is irrational, so even if this don't work score won't increase

wait it's an optimizing point

671
E a (a+a>a*a & (E b (E c (E d (A e (A f (f<a | (E g (E h (E i ((A j ((!(j=(f+f+h)*(f+f+h)+h | j=(f+f+a+i)*(f+f+a+i)+i) | j+a<e & (E k ((A l (!(l>a & (E m k=l*m)) | (E m l=e*m))) & (E l (E m (m<k & g=(e*l+(j+a))*k+m)))))) & (A k (!(E l (l=(j+k)*(j+k)+k+a & l<e & (E m ((A n (!(n>a & (E o m=n*o)) | (E o n=e*o))) & (E n (E o (o<m & g=(e*n+l)*m+o))))))) | j<a+a & k=a | (E l (E m ((E n (n=(l+m)*(l+m)+m+a & n<e & (E o ((A p (!(p>a & (E q o=p*q)) | (E q p=e*q))) & (E p (E q (q<o & g=(e*p+n)*o+q))))))) & j=l+a+a & k=j*j*m))))))) & (E j (E k (E l ((E m (m=(k+l)*(k+l)+l & (E n (n=(f+m)*(f+m)+m+a & n<e & (E o ((A p (!(p>a & (E q o=p*q)) | (E q p=e*q))) & (E p (E q (q<o & j=(e*p+n)*o+q))))))))) & (A m (A n (A o (!(E p (p=(n+o)*(n+o)+o & (E q (q=(m+p)*(m+p)+p+a & q<e & (E r ((A s (!(s>a & (E t r=s*t)) | (E t s=e*t))) & (E s (E t (t<r & j=(e*s+q)*r+t))))))))) | m<a & n=a & o=f | (E p (E q (E r (!(E s (s=(q+r)*(q+r)+r & (E t (t=(p+s)*(p+s)+s+a & t<e & (E u ((A v (!(v>a & (E w u=v*w)) | (E w v=e*w))) & (E v (E w (w<u & j=(e*v+t)*u+w))))))))) | m=p+a & n=(f+a)*q & o=f*r)))))))) & (E m (m=b*(h*f)*l & (E n (n=b*(h*f+h)*l & (E o (o=c*(k*f)*i & (E p (p=c*(k*f+k)*i & (E q (q=d*i*l & (m+o<q & n+p>q | m<p+q & n>o+q | o<n+q & p>m+q))))))))))))))))))))))))))
How it works
First, multiply through by the purported common denominators of a and (π + e·a) to rewrite the condition as: there exist a, b, c ∈ ℕ (not all zero) with a·π + b·e = c or a·π − b·e = c or −a·π + b·e = c.  Three cases are necessary to deal with sign issues.
Then we’ll need to rewrite this to talk about π and e via rational approximations: for all rational approximations π₀ < π < π₁ and e₀ < e < e₁, we have a·π₀ + b·e₀ < c < a·π₁ + b·e₁ or a·π₀ − b·e₁ < c < a·π₁ + b·e₀ or −a·π₁ + b·e₀ < c < −a·π₀ + b·e₁.  (Note that we now get the “not all zero” condition for free.)
Now for the hard part.  How do we get these rational approximations?  We want to use formulas like
2/1 · 2/3 · 4/3 · 4/5 ⋯ (2·k)/(2·k + 1) < π/2 < 2/1 · 2/3 · 4/3 · 4/5 ⋯ (2·k)/(2·k + 1) · (2·k + 2)/(2·k + 1),
((k + 1)/k)k < e < ((k + 1)/k)k + 1,
but there’s no obvious way to write the iterative definitions of these products.  So we build up a bit of machinery that I first described in this Quora post.  Define:
divides(d, a) := ∃b, a = d·b,
powerOfPrime(a, p) := ∀b, ((b > 1 and divides(b, a)) ⇒ divides(p, b)),
which is satisfied iff a = 1, or p = 1, or p is prime and a is a power of it.  Then
isDigit(a, s, p) := a < p and ∃b, (powerOfPrime(b, p) and ∃q r, (r < b and s = (p·q + a)·b + r))
is satisfied iff a = 0, or a is a digit of the base-p number s.  This lets us represent any finite set using the digits of some base-p number.  Now we can translate iterative computations by writing, roughly, there exists a set of intermediate states such that the final state is in the set, and every state in the set is either the initial state or follows in one step from some other state in the set.
Details are in the code below.
Generating code in Haskell
{-# LANGUAGE ImplicitParams, TypeFamilies, Rank2Types #-}

-- Define an embedded domain-specific language for propositions.
infixr 2 :|

infixr 3 :&

infix 4 :=

infix 4 :>

infix 4 :<

infixl 6 :+

infixl 7 :*

data Nat v
  = Var v
  | Nat v :+ Nat v
  | Nat v :* Nat v

instance Num (Nat v) where
  (+) = (:+)
  (*) = (:*)
  abs = id
  signum = error "signum Nat"
  fromInteger = error "fromInteger Nat"
  negate = error "negate Nat"

data Prop v
  = Ex (v -> Prop v)
  | Al (v -> Prop v)
  | Nat v := Nat v
  | Nat v :> Nat v
  | Nat v :< Nat v
  | Prop v :& Prop v
  | Prop v :| Prop v
  | Not (Prop v)

-- Display propositions in the given format.
allVars :: [String]
allVars = do
  s <- "" : allVars
  c <- ['a' .. 'z']
  pure (s ++ [c])

showNat :: Int -> Nat String -> ShowS
showNat _ (Var v) = showString v
showNat prec (a :+ b) =
  showParen (prec > 6) $ showNat 6 a . showString "+" . showNat 7 b
showNat prec (a :* b) =
  showParen (prec > 7) $ showNat 7 a . showString "*" . showNat 8 b

showProp :: Int -> Prop String -> [String] -> ShowS
showProp prec (Ex p) (v:free) =
  showParen (prec > 1) $ showString ("E " ++ v ++ " ") . showProp 4 (p v) free
showProp prec (Al p) (v:free) =
  showParen (prec > 1) $ showString ("A " ++ v ++ " ") . showProp 4 (p v) free
showProp prec (a := b) _ =
  showParen (prec > 4) $ showNat 5 a . showString "=" . showNat 5 b
showProp prec (a :> b) _ =
  showParen (prec > 4) $ showNat 5 a . showString ">" . showNat 5 b
showProp prec (a :< b) _ =
  showParen (prec > 4) $ showNat 5 a . showString "<" . showNat 5 b
showProp prec (p :& q) free =
  showParen (prec > 3) $
  showProp 4 p free . showString " & " . showProp 3 q free
showProp prec (p :| q) free =
  showParen (prec > 2) $
  showProp 3 p free . showString " | " . showProp 2 q free
showProp _ (Not p) free = showString "!" . showProp 9 p free

-- Compute the score.
scoreNat :: Nat v -> Int
scoreNat (Var _) = 1
scoreNat (a :+ b) = scoreNat a + 1 + scoreNat b
scoreNat (a :* b) = scoreNat a + 1 + scoreNat b

scoreProp :: Prop () -> Int
scoreProp (Ex p) = 2 + scoreProp (p ())
scoreProp (Al p) = 2 + scoreProp (p ())
scoreProp (p := q) = scoreNat p + 1 + scoreNat q
scoreProp (p :> q) = scoreNat p + 1 + scoreNat q
scoreProp (p :< q) = scoreNat p + 1 + scoreNat q
scoreProp (p :& q) = scoreProp p + 1 + scoreProp q
scoreProp (p :| q) = scoreProp p + 1 + scoreProp q
scoreProp (Not p) = 1 + scoreProp p

-- Convenience wrappers for n-ary exists and forall.
class OpenProp p where
  type OpenPropV p
  ex, al :: p -> Prop (OpenPropV p)

instance OpenProp (Prop v) where
  type OpenPropV (Prop v) = v
  ex = id
  al = id

instance (OpenProp p, a ~ Nat (OpenPropV p)) => OpenProp (a -> p) where
  type OpenPropV (a -> p) = OpenPropV p
  ex p = Ex (ex . p . Var)
  al p = Al (al . p . Var)

-- Utility for common subexpression elimination.
cse :: Int -> Nat v -> (Nat v -> Prop v) -> Prop v
cse uses x cont
  | (scoreNat x - 1) * (uses - 1) > 6 = ex (\x' -> x' := x :& cont x')
  | otherwise = cont x

-- p implies q.
infixl 1 ==>

p ==> q = Not p :| q

-- Define one as the unique n with n+n>n*n.
withOne ::
     ((?one :: Nat v) =>
        Prop v)
  -> Prop v
withOne p =
  ex
    (\one ->
       let ?one = one
       in one + one :> one * one :& p)

-- a is a multiple of d.
divides d a = ex (\b -> a := d * b)

-- a is a power of p (assuming p is prime).
powerOfPrime a p = al (\b -> b :> ?one :& divides b a ==> divides p b)

-- a is 0 or a digit of the base-p number s (assuming p is prime).
isDigit a s p =
  cse 2 a $ \a ->
    a :< p :&
    ex
      (\b -> powerOfPrime b p :& ex (\q r -> r :< b :& s := (p * q + a) * b + r))

-- An injection from ℕ² to ℕ, for representing tuples.
pair a b = (a + b) ^ 2 + b

-- πn₀/πd < π/4 < πn₁/πd, with both fractions approaching π/4 as k
-- increases:
-- πn₀ = 2²·4²·6²⋯(2·k)²·k
-- πn₁ = 2²·4²·6²⋯(2·k)²·(k + 1)
-- πd = 1²⋅3²·5²⋯(2·k + 1)²
πBound p k cont =
  ex
    (\s x πd ->
       al
         (\i ->
            (i := pair (k + k) x :| i := pair (k + k + ?one) πd ==>
             isDigit (i + ?one) s p) :&
            al
              (\a ->
                 isDigit (pair i a + ?one) s p ==>
                 ((i :< ?one + ?one :& a := ?one) :|
                  ex
                    (\i' a' ->
                       isDigit (pair i' a' + ?one) s p :&
                       i := i' + ?one + ?one :& a := i ^ 2 * a')))) :&
       let πn₀ = x * k
           πn₁ = πn₀ + x
       in cont πn₀ πn₁ πd)

-- en₀/ed < e < en₁/ed, with both fractions approaching e as k
-- increases:
-- en₀ = (k + 1)^k * k
-- en₁ = (k + 1)^(k + 1)
-- ed = k^(k + 1)
eBound p k cont =
  ex
    (\s x ed ->
       cse 3 (pair x ed) (\y -> isDigit (pair k y + ?one) s p) :&
       al
         (\i a b ->
            cse 3 (pair a b) (\y -> isDigit (pair i y + ?one) s p) ==>
            (i :< ?one :& a := ?one :& b := k) :|
            ex
              (\i' a' b' ->
                 cse 3 (pair a' b') (\y -> isDigit (pair i' y + ?one) s p) ==>
                 i := i' + ?one :& a := (k + ?one) * a' :& b := k * b')) :&
       let en₀ = x * k
           en₁ = en₀ + x
       in cont en₀ en₁ ed)

-- There exist a, b, c ∈ ℕ (not all zero) with a·π/4 + b·e = c or
-- a·π/4 = b·e + c or b·e = a·π/4 + c.
prop :: Prop v
prop =
  withOne $
  ex
    (\a b c ->
       al
         (\p k ->
            k :< ?one :|
            (πBound p k $ \πn₀ πn₁ πd ->
               eBound p k $ \en₀ en₁ ed ->
                 cse 3 (a * πn₀ * ed) $ \x₀ ->
                   cse 3 (a * πn₁ * ed) $ \x₁ ->
                     cse 3 (b * en₀ * πd) $ \y₀ ->
                       cse 3 (b * en₁ * πd) $ \y₁ ->
                         cse 6 (c * πd * ed) $ \z ->
                           (x₀ + y₀ :< z :& x₁ + y₁ :> z) :|
                           (x₀ :< y₁ + z :& x₁ :> y₀ + z) :|
                           (y₀ :< x₁ + z :& y₁ :> x₀ + z))))

main :: IO ()
main = do
  print (scoreProp prop)
  putStrLn (showProp 0 prop allVars "")

Try it online!

"which is satisfied iff a = 1, or p is prime and a is a power of it" - you can also have p = 1. Although p > 1 is implied by isDigit, the only place you use it.

@ØrjanJohansen Thanks, I fixed that note. (It actually doesn’t matter which sets powerOfPrime and isDigit wind up representing in unexpected cases, as long as there’s some way to represent every finite set.)

If a has score 7 or higher, I think, then it will be worth adding an ex (\a' -> a' := a :& ... ) wrapper to isDigit.

@ØrjanJohansen Sure, that saves 68. Thanks!

I believe you need to require k>0, as eBound gives a zero denominator (and one zero numerator) in the k==0 case, so all the alternatives fail.

@ØrjanJohansen Good catch, fixed.

I think your new continuation passing style essentially becomes macro expansion of those let-bound arguments, so you might want to check if they need to be CSE'd again. (At this point the CSE is looking so complicated it might need automation...)

@ØrjanJohansen The let-bound arguments are only used once as part of larger CSEs—this was the motivation for switching them to CPS. It would be nice to automate this, yes…

Looks like the definition of 1 can save 2 bytes

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

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


text:
Am I a 'Redivosite' Number?
Redivosite is a portmanteau word invented for the sole purpose of this challenge. It's a mix of Reduction, Division and Composite.
Definition
Given an integer N > 6:

If N is prime, N is not a Redivosite Number.
If N is composite:

repeatedly compute N' = N / d + d + 1 until N' is prime, where d is the smallest divisor of N greater than 1
N is a Redivosite Number if and only if the final value of N' is a divisor of N

Below are the 100 first Redivosite Numbers (no OEIS entry at the time of posting):
14,42,44,49,66,70,143,153,168,169,176,195,204,260,287,294,322,350,414,462,518,553,572,575,592,629,651,702,726,735,775,806,850,869,889,891,913,950,1014,1023,1027,1071,1118,1173,1177,1197,1221,1235,1254,1260,1302,1364,1403,1430,1441,1554,1598,1610,1615,1628,1650,1673,1683,1687,1690,1703,1710,1736,1771,1840,1957,1974,2046,2067,2139,2196,2231,2254,2257,2288,2310,2318,2353,2392,2409,2432,2480,2522,2544,2635,2640,2650,2652,2684,2717,2758,2760,2784,2822,2835

Examples

N = 13: 13 is prime, so 13 is not a Redivosite Number
N = 32: 32 / 2 + 3 = 19; 19 is not a divisor or 32, so 32 is not a Redivosite Number
N = 260: 260 / 2 + 3 = 133, 133 / 7 + 8 = 27, 27 / 3 + 4 = 13; 13 is a divisor or 260, so 260 is a Redivosite Number

Your task

Given an integer N, return a truthy value if it's a Redivosite Number or a falsy value otherwise. (You may also output any two distinct values, as long as they're consistent.)
The input is guaranteed to be larger than 6.
This is code-golf, so the shortest answer in bytes wins!

I really wish all of these "number sequence" challenges that are just sequences of numbers with a certain property would just be asked as decision problems. I highly doubt there's any way to generate these directly, so the only possible solution is to solve the decision problem and then wrap it in a loop that finds the Nth or the first N or all integers that satisfy this property.

I like [tag:sequence] challenges that are not [tag:decision-problem]s in general, but for this one I think a [tag:decision-problem] would be a better fit. I see no relation between the terms such that you print the nth or the first n in a clever manner, so maybe allow taking n as input and checking if it is redivosite?

@MartinEnder & Mr.Xcoder That was my initial intention (hence the original title which I've just rollbacked to) and I changed my mind. I guess this should not ruin any WIP solution (for the reasons you say), so I've edited it.

@Mr.Xcoder Yeah, that's what I meant. I don't mind sequence challenges which actually make sense as a sequence (either because you can compute a(n) directly, or because you can compute a term from previous ones). Thanks, Arnauld, for changing the challenge. :)

Haskell, 91 85 83 80 75 74 bytes
n#m=([n#(div m d+d+1)|d<-[2..m-1],mod m d<1]++[mod n m<1&&m<n])!!0
f x=x#x

Try it online!
f x=x#x                           -- call # with x for both parameters
n#m
         |d<-[2..m-1],mod m d<1   -- for all divisors d of m
    [n#(div m d+d+1)           ]  -- make a list of recursive calls to #,
                                  -- but with m set to m/d+d+1
   ++ [mod n m<1&&m<n]            -- append the Redivosite-ness of n (m divides n,
                                  -- but is not equal to n)
                           !!0    -- pick the last element of the list
                                  -- -> if there's no d, i.e. m is prime, the
                                  --    Redivosite value is picked, else the
                                  --    result of the call to # with the smallest d

Edit: -2 bytes thanks to @BMO, -3 bytes thanks to @H.PWiz and -5 -6  bytes thanks to @Ørjan Johansen

75 bytes

Actually, make that 74

@ØrjanJohansen: Thanks again.

C (gcc), 94 89 bytes
m,n;o(k){for(m=1;m++<k;)if(k%m<1)return m;}
F(N){for(n=N;m=o(n),m-n;n=n/m-~m);N=m<N>N%n;}

Try it online!
Explanation
m,n;                  // two global integers
o(k){                 // determine k's smallest divisor
 for(m=1;m++<k;)      // loop through integers 2 to n (inclusive)
  if(k%m<1)return m;} // return found divisor
F(N){                 // determine N's redivosity
 for(n=N;             // save N's initial value
  m=o(n),             // calculate n's smallest divisor (no name clash regarding m)
  m-n;                // loop while o(n)!=n, meaning n is not prime
                      //  (if N was prime, the loop will never be entered)
  n=n/m-~m);          // redivosite procedure, empty loop body
 N=m<N>N%n;}          // m<N evaluates to 0 or 1 depending on N being prime,
                      //  N%n==0 determines whether or not N is divisible by n,
                      //  meaning N could be redivosite => m<N&&N%n==0
                      //  <=> m<N&&N%n<1 <=> m<N&&1>N%n <=> (m<N)>N%n <=> m<N>N%n

Husk, 14 bytes
?¬Ṡ¦ΩṗoΓ~+→Πpṗ

Try it online!
-3 thanks to H.PWiz.

14 bytes with a cleaner function inside Ω

@H.PWiz just can't understand Γ...

Here Γ, given a list [a,b,c...] will apply ~+→Π to a and [b,c...]. ~+→Π adds a+1 to product[b,c...]. a is the smallest divisor, product[b,c...] is N/d

@H.PWiz And I did think of using prime factors...

Jelly, 14 bytes
ÆḌḊ
Ç.ịS‘µÇ¿eÇ

Try it online!
How it works
ÆḌḊ         Helper link. Argument: k

ÆḌ          Yield k's proper (including 1, but not k) divisors.
  Ḋ         Dequeue; remove the first element (1).

Ç.ịS‘µÇ¿eÇ  Main link. Argument: n

     µ      Combine the links to the left into a chain.
      Ç¿    While the helper link, called with argument n, returns a truthy result,
            i.e., while n is composite, call the chain to the left and update n.
Ç             Call the helper link.
 .ị           At-index 0.5; return the elements at indices 0 (last) and 1 (first).
              This yields [n/d, d].
   S          Take the sum.
    ‘         Increment.
        Ç   Call the helper link on the original value of n.
       e    Test if the result of the while loop belongs to the proper divisors.

Python 2, 97 91 bytes
r=0;e=d=i=input()
while r-e:e=i;r=[j for j in range(2,i+1)if i%j<1][0];i=i/r-~r
d%e<1<d/e<q

Try it online!
Outputs via exit code.
Ungolfed:
r = 0                             # r is the lowest divisor of the current number,
                                  # initialized to 0 for the while loop condition.
e = d = i = input()               # d remains unchanged, e is the current number
                                  # and i is the next number.
while r != e:                     # If the number is equal to its lowest divisor,
                                  # it is prime and we need to end the loop.
    e = i                         # current number := next number
    r = [j for j in range(2, i+1) # List all divisors of the number in the range [2; number + 1)
         if i%j < 1][0]           # and take the first (lowest) one.
    i = i/r+r+1                   # Calculate the next number.
                                  # We now arrived at a prime number.
print d%e == 0 and d != e         # Print True if our current number divides the input
                                  # and is distinct from the input.
                                  # If our current number is equal to the input,
                                  # the input is prime.

Try it online!

05AB1E, 17 16 bytes
[Dp#Òć©sP+>]Ö®p*

Try it online!
Explanation
[                  # start loop
 Dp#               # break if current value is prime
    Ò              # get prime factors of current value
     ć©            # extract the smallest (d) and store a copy in register
       sP          # take the product of the rest of the factors
         +>        # add the smallest (d) and increment
           ]       # end loop
            Ö      # check if the input is divisible by the resulting prime
             ®p    # check if the last (d) is prime (true for all composite input)
               *   # multiply

Pyth, 20 bytes
<P_QiI.WtPHh+/ZKhPZK

Try it here!
How it works

iI.WtPHh+/ZKhPZK || Full program.

  .W             || Functional while. It takes two functions as arguments, A and B.
                 || While A(value) is truthy, turn the value into B(value). The
                 || starting value is the input.
    tPH          || First function, A. Takes a single argument, H.
     PH          || .. The prime factors factors of H.
    t            || .. Tail (remove first element). While truthy (H is composite):
       h+/ZKhPZK || The second function, B. Takes a single argument, Z:
         /Z      || .. Divide Z, by:
           KhP   || .. Its lowest prime factor, and assign that to K.
       h         || .. Increment.
        +      K || And add K.
iI               || Check if the result (last value) divides the input.

And the first 4 bytes (<P_Q) just check if the input is not prime.
With help from Emigna, I managed to save 3 bytes.

Can you use something like head(P) instead of the fiITZ2 part, since the smallest divisor greater than 1 will always be a prime?

@Emigna Ninja'd, fixed and thanks!

Python 3, 149 bytes
def f(N):
	n=N;s=[0]*-~N
	for p in range(2,N):
		if s[p]<1:
			for q in range(p*p,N+1,p):s[q]=s[q]or p
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

Try it online!
Using a sieve approach. Should be fast (O(N log log N) = time complexity of the sieve of Eratosthenes) even with large N (but stores O(N) integers in memory)
Note:

It can be proven that all intermediate values of n does not exceed N, and for N > 7 p can be in range(2,N) instead of range(2,N+1) for sieving.
/ doesn't work, // must be used, because of list index.
Storing range into another variable doesn't help, unfortunately.

Explanation:

-~N == N+1.
At first, the array s is initialized with N+1 zeroes (Python is 0-indexing, so the indices are 0..N)
After initialization, s[n] is expected to be 0 if n is a prime, and p for p the minimum prime which divides n if n is a composite. s[0] and s[1] values are not important.
For each p in range [2 .. N-1]:

If s[p] < 1 (that is, s[p] == 0), then p is a prime, and for each q being a multiple of p and s[q] == 0, assign s[q] = p.

The last 2 lines are straightforward, except that n//s[n]-~s[n] == (n // s[n]) + s[n] + 1.

Python 3, 118 bytes
def f(N):
	n=N;s=[0]*-~N
	for p in range(N,1,-1):s[2*p::p]=(N-p)//p*[p]
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

Try it online!
At the cost of slightly worse performance. (This one runs in O(N log N) time complexity, assume reasonable implementation of Python slices)

The equivalent full program is 117 bytes.

You can use n//s[n]-~s[n] instead of n//s[n]+s[n]+1 for 149 bytes.

Also I think or p can be |p

@Mr.Xcoder No, or p performs logical or, while |p performs bitwise or. That is, a or b is b if a == 0 else a.

You can modify the outer for to use slice instead another for. The range is reversed, so lower indexes will overwrite the larger ones, and starting the slice at 2*p you won't replace s[0] or s[p].

@Rod 123 bytes.

@JonathanFrech 116 on python2

@Rod Using Python 2, it can even go down to 115 bytes.

@JonathanFrech Thanks!

Haskell, 110 bytes
f n|mod(product[1..n-1]^2)n>0=1<0|1>0=n`mod`u n<1
u n|d<-[i|i<-[2..],n`mod`i<1]!!0=last$n:[u$n`div`d+d+1|d/=n]

Try it online!
Not very happy...

Octave, 92 bytes
function r=f(n)k=n;while~isprime(k)l=2:k;d=l(~mod(k,l))(1);k=k/d+d+1;end;r=~mod(n,k)&k<n;end

Try it online!

APL (Dyalog), 50 bytes
{(0=n|⍵)∧⍵>n←{⍬≢k←o/⍨0=⍵|⍨o←2↓⍳⍵:∇1+d+⍵÷d←⌊/k⋄⍵}⍵}

Try it online!

Japt, 25 24 bytes
I fear I may have gone in the wrong direction with this but I've run out of time to try a different approach.
Outputs 0 for false or 1 for true.
j ?V©vU :ßU/(U=k g)+°UNg

Try it

Perl 5, 291+1(-a) = 292 bytes
Darn Perl for not having a native prime checker.

use POSIX;&r($_,$_);
sub p{$n=shift;if($n<=1){return;}if($n==2||$n==3){return 1;}if($n%2==0||$n%3==0){return;}for(5..ceil($n/2)){if($n%$_==0){return;}}return 1;}
sub r{$n=shift;$o=shift;if(&p($n)){print $o%$n==0&&$n!=$o?1:0;last;}for(2..ceil($n/2)){if($n%$_==0){&r(($n/$_)+$_+1, $o);last;}}}

Ungolfed version,
use POSIX;
&r($_,$_);
sub p{
    my $n=shift;
    if($n<=1){
        return;
    }
    if($n==2||$n==3){
        return 1;
    }
    if($n%2==0||$n%3==0){
        return;
    }
    for(5..ceil($n/2)){
        if($n%$_==0){
            return;
        }
    }
    return 1;
}
sub r{
    my $n=shift;
    my $o=shift;
    if(&p($n)){
        print $o%$n==0&&$n!=$o ? 1 : 0;
        last;
    }
    for(2..ceil($n/2)){
        if($n%$_==0){
            &r(($n/$_)+$_+1, $o);
            last;
        }
    }
}

Try it online!

APL NARS, 43 chars, 85 bytes
{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}

(hoping that it converge for all number>6) test:
h←{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}
v←⍳100
v,¨h¨v
   1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0  10 0  11 0
   12 0  13 0  14 1  15 0  16 0  17 0  18 0  19 0  20 0
   21 0  22 0  23 0  24 0  25 0  26 0  27 0  28 0  29 0
   30 0  31 0  32 0  33 0  34 0  35 0  36 0  37 0  38 0
   39 0  40 0  41 0  42 1  43 0  44 1  45 0  46 0  47 0
   48 0  49 1  50 0  51 0  52 0  53 0  54 0  55 0  56 0
   57 0  58 0  59 0  60 0  61 0  62 0  63 0  64 0  65 0
   66 1  67 0  68 0  69 0  70 1  71 0  72 0  73 0  74 0
   75 0  76 0  77 0  78 0  79 0  80 0  81 0  82 0  83 0
   84 0  85 0  86 0  87 0  88 0  89 0  90 0  91 0  92 0
   93 0  94 0  95 0  96 0  97 0  98 0  99 0  100 0

The idea of using 2 anonymous functions I get to other Apl solution.
 {(⍵≤60)∨π⍵:0⋄ -- if arg ⍵ is prime or <=6 return 0
  ⍵{1=⍴t←π⍵:0=⍵|⍺⋄ -- if list of factors ⍵ has length 1 (it is prime)
                    -- then return ⍺mod⍵==0
  ⍺∇1+↑t+⍵÷↑t}⍵}   -- else recall this function with args ⍺ and 1+↑t+⍵÷↑t

Wolfram Language (Mathematica), 64 bytes
Straightforward implementation using recursive pattern replacement
(replacing "\[Divides]" with the "∣" symbol saves 7 bytes)
(g=!PrimeQ@#&)@#&&(#//.x_/;g@x:>x/(c=Divisors[x][[2]])+c+1)\[Divides]#&

Try it online!

Clean, 128 117 114 bytes
import StdEnv
@n#v=hd[p\\p<-[2..]|and[gcd p i<2\\i<-[2..p-1]]&&n rem p<1]
|v<n= @(n/v+v+1)=n
?n= @n<n&&n rem(@n)<1

Try it online!

Pyt, 44 bytes
←⁻0`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹ṗ⇹3Ș⊽

See the code below for an explanation - the only differences are (1) that N is decremented before to account for the incrementation at the beginning of the loop, and (2) it uses NOR instead of OR.

Try it online!

I made this before I re-read the question and noticed that it only wanted a true/false.
Pyt, 52 bytes
60`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹Đṗ⇹3Ș∨ł⇹Đƥ⇹ŕ1ł

Prints an infinite list of Redivosite numbers.
Explanation:
6                                                            Push 6
 0                                                           Push unused character
  `                   ł                     ł      ł         Return point for all three loops
   ŕ                                                         Remove top of stack
    ⁺                                                        Increment top of stack (n)
     ĐĐ                                                      Triplicate top of stack (n)
       ϼ↓                                                    Get smallest prime factor of n (returns 1 if n is prime)
         Đ                                                   Duplicate top of stack
          3Ș⇹                                                Manipulate stack so that the top is (in descending order): [d,(N,N'),d]
             ÷+⁺                                             Calculates N'=(N,N')/d+d+1
                Đṗ¬                                          Is N' not prime?
                   ⇹⁻⇹                                       Decrement N' (so the increment at the beginning doesn't change the value), and keep the boolean on top - end of innermost loop (it loops if top of stack is true)
                       ŕ                                     Remove top of stack
                        á                                    Convert stack to array
                         Đ                                   Duplicate array
                          0⦋Đ                                Get the first element (N)
                             ↔ĐŁ⁻⦋                           Get the last element ((final N')-1)
                                  ⁺                          Increment to get (final N')
                                   |¬                        Does N' not divide N?
                                     ⇹Đṗ                     Is N prime?
                                        ⇹3Ș∨                 Is N prime or does N' not divide N? - end of second loop (loops if top of stack is true)
                                             ⇹Đƥ⇹ŕ           Print N, and reduce stack to [N]
                                                  1          Push garbage (pushes 1 so that the outermost loop does not terminate)

Try it online!

J, 35 bytes
(~:*0=|~)(1+d+]%d=.0{q:)^:(0&p:)^:_

Try it online!
The minimum divisor being the first prime factor was stolen from @Dennis's Jelly solution (previously I was using <./@q:).
There should be a better way to do the iteration, but I can't seem to find it. I thought of avoiding doing the primality test (^:(0&p:)) and instead using adverse but it seems like that will be a bit longer since you'll need a _2{ and some changes which might not give a net reduction.
I really feel like there must be a way to avoid having parens around the primality check, too.
Explanation (expanded)
(~: * 0 = |~)(1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Input: N
             (1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Find the final N'
                                       ^:        ^:_  Do while
                                           0&p:       N is not prime
                                   q:                 Get prime factors (in order)
                               0 {                    Take first (smallest divisor)
                          d =.                        Assign this value to d
             1 + d + ] %  d                           Compute (N/d) + 1 + d
(~: * 0 = |~)                                        Is it redivosite?
      0 = |~                                          N = 0 (mod N'), i.e. N'|N
    *                                                 And
 ~:                                                   N =/= N', i.e. N is not prime


text:
Strategic Vanishers

This post is loosely inspired by this mathoverflow post.

A Vanisher is any pattern in Conway's Game of life that completely disappears after one step.  For example the following pattern is a size 9 Vanisher.

An interesting property of Vanishers is that any pattern can be made into a vanishing one by simply adding more live cells.  For example the following pattern can be completely enclosed into a vanishing pattern like so

However we can make that pattern into a Vanisher by adding even fewer live cells.

Your task is to write a program that does this task for us.  That is given a pattern as input find and output a vanishing pattern containing the input.  You do not necessarily have to find the optimal pattern just a pattern that works.
Scoring
To score your program you will have to run it on all of the size 6 polyplets (not double counting symmetrically equivalent cases).  Here is a pastebin containing each polyplet on its own line.  There should be 524 of them total.  They are represented as a list of six coordinates ((x,y) tuples) each being the location of a live cell.
Your score will be the total number of new cells added to make all of these polyplets into Vanishers.
Ties
In the case of ties I will provide a list of the size 7 polyplets for the programs to be run on.
IO
I would like IO to be pretty flexible you can take input and output in reasonable formats however you are probably going to want to take input in the same format as the raw input data I provided.  Your format should be consistent across multiple runs.
Timing
Your program should run in a reasonable amount of time (approx <1 day) on a reasonable machine. I'm not going to really be enforcing this too much but I'd prefer if we would all play nice.

(of course you must be able to score your own code)

Related meta for the last paragraph

Are you going to ban hardcoding?

@FlipTack I'm pretty sure its already a standard loophole.  Plus a well written program is probably just as good as a human anyway.

Is this a [tag:test-battery]?

@H.PWiz Looks like it is.  For some reason I had a different idea of what [tag:test-battery] was.

the first person to successfully score their program [...] will be the winner [tag:fastest-scoring]?

@EriktheOutgolfer I guess?  It's the second tie breaker so I don't really anticipate having to break that out.

"well written program is probably just as good as a human"... or even better... depends on the objective. Also... @WheatWizard The format of the test cases are a list of a (row, column) tuple, correct?

@user202729 Yes, I'll make that clear in the question. Although it doesn't matter if it's row,column or column,row because of symmetry.

Just to clarify, it has to work for any size of polyplets?

@Οurous In theory it should work for any input pattern.  You are free to optimize for polyplets though.

Would it not make more sense to have the tie break be runtime speed? Since people have different time-zones, the fastest posted scoring could disadvantage some people by many hours, simply because they're sleeping or at work.

@Οurous I think I'll just remove the third tie breaker.

Python + Z3, score = 3647
Runs in 14 seconds on my eight core system.
from __future__ import print_function

import ast
import multiprocessing
import sys
import z3

def solve(line):
    line = ast.literal_eval(line)
    x0, x1 = min(x for x, y in line) - 2, max(x for x, y in line) + 3
    y0, y1 = min(y for x, y in line) - 2, max(y for x, y in line) + 3
    a = {(x, y): z3.Bool('a_{}_{}'.format(x, y)) for x in range(x0, x1) for y in range(y0, y1)}
    o = z3.Optimize()
    for x in range(x0 - 1, x1 + 1):
        for y in range(y0 - 1, y1 + 1):
            s = z3.Sum([
                z3.If(a[i, j], 1 + ((i, j) != (x, y)), 0)
                for i in (x - 1, x, x + 1) for j in (y - 1, y, y + 1) if (i, j) in a
            ])
            o.add(z3.Or(s < 5, s > 7))
    o.add(*(a[i, j] for i, j in line))
    o.minimize(z3.Sum([z3.If(b, 1, 0) for b in a.values()]))
    assert o.check() == z3.sat
    m = o.model()
    return line, {k for k in a if z3.is_true(m[a[k]])}

total = 0
for line, cells in multiprocessing.Pool().map(solve, sys.stdin):
    added = len(cells) - len(line)
    print(line, added)
    x0, x1 = min(x for x, y in cells), max(x for x, y in cells) + 1
    y0, y1 = min(y for x, y in cells), max(y for x, y in cells) + 1
    for y in range(y0, y1):
        print(''.join('#' if (x, y) in line else '+' if (x, y) in cells else ' ' for x in range(x0, x1)))
    total += added
print('Total:', total)

Full output

A decent explanation of how this works would be good and would win my upvote. It seems it tries a brute force of adding cells to a rectangular area surrounding the polyplet?

It was unclear to me why there are + disconnected from the main shape in some cases but it seems they are necessary to avoid spawning new cells. Are these solutions therefore optimal?

Out of curiosity, why use z3.Or instead of vanilla a or b? Is it purely performance, or does it have a different functionality?

@cairdcoinheringaahing Looks like that's a symbolic solution.

@LevelRiverSt Z3 is a constraint solver from Microsoft Research that’s much more intelligent than brute force. All that’s happening is this code is declaring the constraints to hand to Z3. We tell Z3 that every cell in some rectangle might be alive or dead, add constraints saying that the next frame is entirely dead, add constraints saying that the given cells are currently alive, and ask it to minimize the number of live cells. All the real work happens in Z3 inside o.check().

@cairdcoinheringaahing s < 5 is a constraint, not a boolean, so the Python or operator cannot be used. (Operators like < are overloaded to work on Z3 symbolic expressions, but or cannot be overloaded.)

@AndersKaseorg 1. you haven't answered my comment asking if your solutions are optimal. This is of great importance to anyone else considering posting an answer. 2. If you don't explain what Z3 does in your answer I can only guess what it does, as I don't have time to read the documentation, hence my random guess of brute force. 3 This answer deserves an upvote (in fact it deserves many upvotes) for its code, but I won't upvote until an explanation covering the above two points is added to the answer.

@LevelRiverSt "What Z3 does"... "constraint solver", that's it. How it solves the constraints and whether it's optimal is implementation-defined. Although, a link to documentation would be useful.

@user202729 The main thing is whether the constraint solver ifinds optimal solutions or not, and "yes / no / don't know if if it finds optimal solutions" is something the OP should be able to answer and would be best included the post as it is relevant to scoring. That's my main issue. That said, additional details of what OP's code does and what the Z3 functions do would also also enhance the post. I hate having to squint through code to work out what it does when it contains an import from an unfamiliar library.

The problem arises because the constraint solver has clearly done an excellent job and many of the solutions are clearly optimal! Whether they are in theory all optimal / in practice all optimal is another thing.

@LevelRiverSt Any failure of Z3 to find the optimal solution like we asked for would be a bug in Z3. I am amused that you think you can control my writing style by holding upvotes hostage. Any post will have some readers who are familiar with the language and libraries and some readers who aren’t (I don’t think every Retina answer should feel obligated to explain what regular expressions are). Although Z3 is kind of a big deal in the world of constraint solvers, it’s fine if you personally haven’t heard of it. You’re welcome to follow the link I already provided or Google for more information.

(That said, I haven’t attempted to prove that extending the rectangle by two cells is sufficient to encompass the optimal solution, although it empirically seems to be sufficient.)

@AndersKaseorg Any failure to find the optimal solution...would be a bug in Z3 This cannot be deduced from your post by someone unfamiliar with Z3 as indicated by user202729. Thank you for answering my question, I am now upvoting, though I would suggest you include your comments in the post as it would make it easier for others unfamiliar with Z3 to appreciate it.

As for holding upvotes hostage... I'm free to vote as I please and you to write as you please. I usually comment when I downvote  -  It's a common complaint that people don't leave reasons for downvotes. Here I merely chose to express the conditions under which I would upvote (and from by the upvote on my comment, someone else has a similar view.) I like your post a lot and spent some time trying to understand it. I find it odd that you would seek to restrict your audience to those familiar with Z3 or inclined to read its documention when it would be simple to explain briefly, but your choice.


text:
Biggest square in a grid
Challenge
Given a grid like this,
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .

write a piece of code that can determine the size of the largest square that does not include a '#'. (The answer to this input is 5x5 as the bottom right 5x5 grid is the biggest square possible).
The square must have sides parallel to the x and y axes.
As some small details: the original grid is always a square and its side length is given to you. The coordinates of the '#' symbols are also given to you.
Input Details
First line: N (1 <= N <= 1000), the side length of the square grid, and T (1 <= T <= 10,000) the number of '#' signs.
Next T Lines: The coordinates of each of the T #'s
Test Cases
Input #1:
8 3
2 2
2 6
6 3

Result #1: 5
================
Input #2:
8 4
1 1
1 8
8 1
8 8

Result #2: 6
================
Input #3:
5 1
3 3

Result #3: 2
This is a fastest-code problem, so the fastest code tested on the rextester compiler wins.
Have fun!

Related.

For fastest-code 1000x1000 is too small, though

But rextester doesn't support Jelly or Hexagony.

@user202729 I guess you meet memory lack first

As capable as rextester is, may I recommend using try it online instead? It contains many more langauges, and is community run.

@ATaco https://codegolf.meta.stackexchange.com/questions/12707/is-tio-acceptable-for-fastest-code-questions

maybe TIO as pretest?

"the fastest code tested on the rextester compiler wins" - fastest on what input?

@user202729 rextester should have exactly the same problems.

Node.js
Takes input as (w, l), where w is the width and l is an array of coordinates [x, y]. (This may be changed if the input format really is as strict as described.) Works in O(w²).
f = (w, l) => {
  var x, y,
      W = w * w,
      a = new Uint16Array(W),
      best = 0;

  l.forEach(([x, y]) => a[(y - 1) * w + x - 1] = 1);

  for(y = w; y < W; y += w) {
    for(x = y + 1; x < y + w; x++) {
      if(a[x]) {
        a[x] = 0;
      }
      else {
        best = Math.max(
          best,
          a[x] = Math.min(a[x - 1], a[x - w], a[x - w - 1]) + 1
        );
      }
    }
  }

  return best;
}

Try it online!

  1000,
  [...Array(10000)].map(_=>[Math.random()*1000+1|0,Math.random()*1000+1|0])
)); ``` cost 114ms, though it might be the language's low efficiency

It's more like 8ms inside f() after JIT compilation. (But yeah... answers are not going to be scored that way.)

I doubt the OP will add a more objective winning criteria...

C (gcc)
No fancy algorithm here, just almost-bruteforce... but hey, C is fast.
Input: Takes input from stdin.
Output: Writes output to stdout.
#include <stdio.h>
#include <stdint.h>

int main(void) {
    uint_fast16_t n, t, i, j, h, x, y, flag, biggest = 0;
    scanf("%hi %hi", &n, &t);
    uint_fast8_t m[n][n];
    for (uint_fast16_t c = 0; c < t; ++c) {
        scanf("%hi %hi", &i, &j);
        m[i-1][j-1] = '#';
    }
    for (i = 0; i < n - 1; ++i) {
        for (j = 0; j < n - 1; ++j) {
            flag = 1;
            for (h = 1; flag && i + h < n + 1 && j + h < n + 1; ++h) {
                for (y = i; flag && y < i + h; ++y) {
                    for (x = j; flag && x < j + h; ++x) {
                        if (m[y][x] == '#') flag = 0;
                    }
                }
                if (flag && h > biggest) biggest = h;
            }
        }
    }
    printf("%d", biggest);
}

Try it online!


text:
Balanced ternary logic
Balanced ternary logic
Ternary is normally another name for base 3, that is to say, each digit is 0, 1, or 2, and each place is worth 3 times as much as the next place.
Balanced ternary is a modification of ternary which uses digits of -1, 0 and 1. This has the advantage of not needing a sign. Each place is still worth 3 times as much as the next place. The first few positive integers are therefore [1], [1, -1], [1, 0], [1, 1], [1, -1, -1] while the first few negative integers are [-1], [-1, 1], [-1, 0], [-1, -1], [-1, 1, 1].
You have three inputs x, y, z. z is either -1, 0, or 1, while x and y can be from -3812798742493 to 3812798742493 inclusive.
The first step is to convert x and y from decimal to balanced ternary. This should give you 27 trits (TeRnary digITS). You then have to combine the trits from x and y in pairs using a ternary operation and then convert the result back to decimal.
You can choose which values of z map to one of these three ternary operations each:

A: Given two trits, if either is zero, then the result is zero, otherwise the result is -1 if they are different or 1 if they are the same.
B: Given two trits, if either is zero, then the result is the other trit, otherwise the result is zero if they are different or the negation if they are the same.
C: Given two trits, the result is zero if they are different or their value if they are the same.

Example. Suppose x is 29 and y is 15. In balanced ternary, these become [1, 0, 1, -1] and [1, -1, -1, 0]. (The remaining 23 zero trits have been omitted for brevity.) After each of the respective operations they become A: [1, 0, -1, 0], B: [-1, -1, 0, -1], C: [1, 0, 0, 0]. Converted back to decimal the results are 24, -37 and 27 respectively. Try the following reference implementation for more examples:

function reference(xd, yd, zd) {
    var rd = 0;
    var p3 = 1;
    for (var i = 0; i < 27; i++) {
        var x3 = 0;
        if (xd % 3 == 1) {
            x3 = 1;
            xd--;
        } else if (xd % 3) {
            x3 = -1;
            xd++;
        }
        var y3 = 0;
        if (yd % 3 == 1) {
            y3 = 1;
            yd--;
        } else if (yd % 3) {
            y3 = -1;
            yd++;
        }
        var r3 = 0;
        if (zd < 0) { // option A
            if (x3 && y3) r3 = x3 == y3 ? 1 : -1;
        } else if (zd > 0) { // option B
            if (!x3) r3 = y3;
            else if (!y3) r3 = x3;
            else r3 = x3 == y3 ? -x3 : 0;
        } else { // option C
            r3 = x3 == y3 ? x3 : 0;
        }
        rd += r3 * p3;
        p3 *= 3;
        xd /= 3;
        yd /= 3;
    }
    return rd;
}

<input type=number id=x><input type=number id=y><select id=z><option value=-1>A</option><option value=1>B</option><option value=0>C</option><select>

The reference implementation follows the steps given above but you are of course free to use any algorithm that produces the same results.
This is code-golf, so the shortest program or function that violates no standard loopholes wins!

If the native format for numbers is balanced ternary (as opposed to binary), are we allowed to take it as input in the usual way (which results in no conversion to balanced ternary)?

related

@wizzwizz4 ... I guess...

does z have to be one of -1,0,1 or can we pick any three consistent and distinct values? I've selected 1,2,3 in my answer, and there's some confusion about it.

@Giuseppe Sorry, only balanced ternary digits are allowed.

I read something trasverse... Too much words and no formula

Clean, 231 ... 162 bytes
import StdEnv
$n=tl(foldr(\p[t:s]#d=sign(2*t/3^p)
=[t-d*3^p,d:s])[n][0..26])
@x y z=sum[3^p*[(a+b)/2,[1,-1,0,1,-1]!!(a+b+2),a*b]!!(z+1)\\a<- $x&b<- $y&p<-[0..26]]

Defines the function @, taking three Ints and giving an Int.
Operators map as 1 -> A, 0 -> B, -1 -> C.
Try it online!
The function $ folds a lambda over the digit places [0..26], into a list of ternary digits. It uses the head of the list it yields to keep a current total difference from the requisite number (which is why it is tailed prior to returning), and sign(2*t/3^p) to determine the current digit to yield. The sign trick is equivalent to if(abs(2*t)<3^p)0(sign t).

I don't know Clean, but I'm intrigued at how you've converted to balanced ternary, with $n(I think). Could you add an explanation for that?

@Giuseppe Absolutely, I'll add an explaination today when I've got time.

@Giuseppe does that answer your question?

Yes! That makes sense. Quite clever!

R, 190 172 151 bytes
function(a,b,z){M=t(t(expand.grid(rep(list(-1:1),27))))
P=3^(26:0)
x=M[M%*%P==a,]
y=M[M%*%P==b,]
k=sign(x+y)
switch(z+2,x*y,k*(-1)^(x+y+1),k*!x-y)%*%P}

Try it online!
Computes all combinations of trits and selects the right one. It'll actually throw a memory error with 27, since 3^27 is a somewhat large number, but it would in theory work. The TIO link has only 11 trit integer support; I'm not sure at what point it times out or memory errors first, and I don't want Dennis to get mad at me for abusing TIO!
old answer, 170 bytes
This one should work for all inputs, although with only 32-bit integers, there's the possibility of imprecision as R will automatically convert them to double.
function(a,b,z){x=y={}
for(i in 0:26){x=c((D=c(0,1,-1))[a%%3+1],x)
y=c(D[b%%3+1],y)
a=(a+1)%/%3
b=(b+1)%/%3}
k=sign(x+y)
switch(z+2,x*y,k*(-1)^(x+y+1),k*!x-y)%*%3^(26:0)}

Try it online!
Takes -1 for A, 0 for B, and 1 for C.
Ports the approach in this answer for converting to balanced ternary, although since we're guaranteed to have no more than 27 balanced trits, it's optimized for that.
R, 160 bytes
function(a,b,z){s=sample
x=y=rep(0,27)
P=3^(26:0)
while(x%*%P!=a&y%*%P!=b){x=s(-1:1,27,T)
y=s(-1:1,27,T)}
k=sign(x+y)
switch(z+2,x*y,k*(-1)^(x+y+1),k*!x-y)%*%P}

Try it online!
This version will terminate extremely slowly. The bogosort of base conversion, this function randomly picks trits until it somehow magically (3^-54 chance of it occurring) finds the right trits for a and b, and then does the required operation. This will basically never finish.

I think z is restricted to {-1, 0, 1}.

@EriktheOutgolfer You can choose which values of z map to one of these three ternary operations each: [...]

@Dennis z is either -1, 0, or 1, and I think those are the "values of z" being referred to.

It's a two-byte difference, replacing switch(z,...) with switch(z+2,...) so it would be a trivial change regardless.

Jelly, 39 bytes
×=
×
+ị1,-,0
A-r1¤ṗœs2ṚẎị@ȯµ€Uz0ZU⁹ŀ/ḅ3

A full program taking two arguments, [x,y], and z
...where z is {A:-1, B:0, C:1}
which prints the result
Try it online! Note: the golfed method makes it slow - this altered version is faster (logs by 3, ceils and increments prior to each Cartesian product)
How?
×=       - Link  1 (1), B: list of trits L, list of trits R
×        - L multiplied by... (vectorises):
 =       -   L equal R? (vectorises)

×        - Link -1 (2), A: list of trits L, list of trits R
×        - L multiplied by R (vectorises)

+ị1,-,0  - Link  0 (3), C: list of trits L, list of trits R
+        - L plus R (vectorises)
  1,-,0  - list of integers = [1,-1,0]
 ị       - index into (vectorises) - 1-based & modular, so index -2 is equivalent to
         -                           index 1 which holds the value 1.

A-r1¤ṗœs2ṚẎị@ȯµ€Uz0ZU⁹ŀ/ḅ3 - Main link: list of integers [X,Y], integer Z
              µ€           - for each V in [X,Y]:
A                          -   absolute value = abs(V)
    ¤                      -   nilad followed by link(s) as a nilad:
 -                         -     literal minus one
   1                       -     literal one
  r                        -     inclusive range = [-1,0,1]
     ṗ                     -   Cartesian power, e.g. if abs(V)=3: [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]
                           -                   (corresponding to: [-13       ,-12      ,-11      ,-10      ,-9      ,-8      ,-7       ,-6      ,-5      ,-4       ,-3      ,-2      ,-1      ,0      ,1      ,2       ,3      ,4      ,5        ,6       ,7       ,8       ,9      ,10      ,11     ,12     ,13     ] )
        2                  -   literal two
      œs                   -   split into equal chunks           [[[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0]],[[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]]]
         Ṛ                 -   reverse                           [[[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]],[[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0]]]
          Ẏ                -   tighten                            [[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1],[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0]]
                           -                   (corresponding to: [1      ,2       ,3      ,4      ,5        ,6       ,7       ,8       ,9      ,10     ,11      ,12     ,13     ,-13       ,-12      ,-11      ,-10      ,-9      ,-8      ,-7       ,-6      ,-5      ,-4       ,-3      ,-2      ,-1      ,0      ] )
           ị@              -   get item at index V (1-based & modular)
             ȯ             -   logical OR with V (just handle V=0 which has an empty list)
                U          - upend (big-endian -> little-endian for each)
                  0        - literal zero           }
                 z         - transpose with filler  } - pad with MSB zeros
                   Z       - transpose              }
                    U      - upend (little-endian -> big-endian for each)
                       /   - reduce with:
                      ŀ    -   link number: (as a dyad)
                     ⁹     -     chain's right argument, Z
                         3 - literal three
                        ḅ  - convert from base

I can't for the life of me read golfing languages, so when you say 'slow', how bad is the time complexity?

To get the balanced ternary of N it creates a list of all (3^n) length abs(N) lists of trits (0,-1, and 1). So O(3^max(abs(X),abs(Y)))

Thanks, and for the explanation I see you added too!

Also added a speedier version using the same method :)

Jelly, 47 bytes
×=
×
N0⁼?ȯȧ?"
ḃ3%3’
0Çḅ3$$⁼¥1#ḢÇṚµ€z0Z⁹+2¤ŀ/Ṛḅ3

Try it online!
Full program.
-1 = C, 0 = A, 1 = B
Argument 1: [x, y]
Argument 3: z

I don't think taking x and y in balanced ternary is allowed: "x and y can be from -3812798742493 to 3812798742493 inclusive. The first step is to convert x and y from decimal to balanced ternary."

@JonathanAllan comment clarification

...but the native format for numbers is not balanced ternary in Jelly.

@JonathanAllan Oh, looks like I misunderstood....

@JonathanAllan eugh...fixed

You'd need to handle non-equal length values (e.g. [3,5],0 -> -3)

...also (noticed while making mine) [0,0] and any z should produce 0.

Let us continue this discussion in chat.


text:
Integer Division Loops
Challenge
Given any positive integer supported by your language:

Take the input and divide it into two halves. For all divisions in this program, if the input is odd, round one half up and one half down (ex: 7 -> 3,4, not 7 -> 3.5,3.5).
Divide either number in half, then take the larger of these two new halves and add it back to the number that wasn’t split. Ex: 3,4 -> (1,2),4 -> 1,6 or 3,4 -> 3,(2,2) -> 5,2.
Repeat step 2 until you reach a set you have seen before. Ex: 5 -> 3,2 -> (1,2),2 -> 1,4 -> 1,(2,2) -> 3,2. Since we’ve seen 3,2 before, we may stop repeating. You may completely exhaust a stack in the process of doing this. Ex: 5 -> 3,2 -> (1,2),2 -> 1,4 -> (0,1),4 -> 0,5.
Output each pair in the loop (i.e. the above without the intermediate steps, from the first appearance of a pair until the second, but not including the second). Ex: 3,2 -> 1,4. If the input is included, don’t output a 0 with it - 5 -> 3,2 -> 1,4, not 0,5 -> 3,2 -> 1,4.
Repeat steps 1-4 by splitting the pairs differently.

I/O
Input is a positive integer larger than 1 and smaller than either the maximum integer supported by your language or the maximum integer that won’t crash the computer, whichever is smaller.
Output is the loops from above in any format you want (string, list, array, etc.). Trailing white space is allowed.
Do not output the same loop twice, nor different versions of the same loop. Ex: 2 -> 1,1 and 1,1 -> 2 are both valid loops, but they describe the same loop, beginning at different points on the loop. Likewise, two loops that are identical but go in the reverse order should not be outputted. Ex: 3 -> 1,2 -> 2,1 and 3 -> 2,1 -> 1,2 are the same loop, but they go in the opposite direction from each other.
You may use any delimiter to differentiate between the pairs, between each number in the pairs, and between each loop, provided that they are three distinct chars or strings. Above, I divided the numbers using commas, the pairs using ->’s, and the loops using boring instructions. In my examples below, I will use parentheses around each pair, commas between each number within a pair, and new lines between each loop.
Examples
Credit to @WheatWizard’s code for fixing up my examples list. As I said in an earlier draft, I was sure I was missing a few since I was doing it by hand, but boy was I missing some.
Input: 2
Output: (2)(1,1)
Input: 3
Output:
(3)(1,2)
(1,2)(2,1)
(3)(1,2)(2,1)

Input: 4
Output:
(4)(2,2)(1,3)
(1,3)(3,1)
(4)(2,2)(1,3)(3,1)
(4)(2,2)(3,1)(1,3)
(3,1)(1,3)
(4)(2,2)(3,1)

Input: 5
Output:
(5)(2,3)(1,4)
(1,4)(3,2)
(2,3)(1,4)(3,2)(4,1)
(5)(2,3)(1,4)(3,2)(4,1)
(2,3)(4,1)
(5)(2,3)(4,1)

Input: 6
Output:
(6)(3,3)(1,5)
(1,5)(4,2)(2,4)
(4,2)(2,4)
(1,5)(4,2)(5,1)(2,4)
(4,2)(5,1)(2,4)
(6)(3,3)(1,5)(4,2)(5,1)
(6)(3,3)(5,1)(2,4)(1,5)
(2,4)(1,5)(4,2)
(5,1)(2,4)(1,5)(4,2)
(2,4)(4,2)
(5,1)(2,4)(4,2)
(6)(3,3)(5,1)

Input: 7
Output:
(7)(3,4)(1,6)
(1,6)(4,3)(2,5)
(2,5)(5,2)
(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(7)(3,4)(1,6)(4,3)(2,5)(5,2)(6,1)
(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)
(2,5)(1,6)(4,3)
(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(7)(3,4)(5,2)(2,5)(1,6)(4,3)(6,1)
(5,2)(2,5)
(3,4)(5,2)(6,1)
(7)(3,4)(5,2)(6,1)

Scoring
This is code-golf, so the lowest byte count wins.

This is my first challenge here, so any feedback would be greatly appreciated. Link to sandbox here.
Fun fact: I was bored one day and playing with random little pieces of pencil lead in this manner and eventually noticed that I could keep going in these types of loops. For some reason my first reaction was “hey, this would be a great challenge for code golf.”

Welcome to PPCG, nice first challenge!

May we print (a,0) in the place of (a)?  This tends to make sense in strongly typed languages.

@WheatWizard Nope. When printing the input you just print the input without the zero. I haven’t seen a challenge on here where it comes down to just one or two bytes.

Ok, that's fair enough.  But for the record, I certainly wouldn't call it one or two bytes.  For me it looks like about 30% of my byte count is from removing the zero.

Since the same loop in reverse is the same, can we output the loops in reverse?

@Οurous Careful, not all loops are reversible. But the ones that are, yes.

Is 2 -> 1,1 one loop or two loops? Since there are two ways to split 1,1 (0,1+1 and 1+1,0), but they both give the same formatted result (2).

@Οurous Just one loop. That’s part of why I was so insistent before that a 0 not be included with the input.

Clean, 267 ... 167 bytes
import StdEnv
f s l|any((==)s)l=[dropWhile((<>)s)l]#[h,t:_]=s
|1>h*t=f[max h t]l=f[h/2,(h+1)/2+t](l++[s])++(f[(t+1)/2+h,t/2](l++[s]))
@n=removeDup(f[n/2,(n+1)/2][[n]])

Try it online!
Ungolfed:
loops num
    = removeDup (half (divide num) [[num]])
where
    divide num
        = [num/2, (num+1)/2]
    half [_, 0] list
        = list
    half [0, _] list
        = list
    half [a, b] list
        | isMember [a, b] list
            = [dropWhile ((<>) [a, b]) list]
        # [u, v: _]
            = divide a
        # [x, y: _]
            = divide b
        = (half [u, v+b] (list ++ [a, b])) ++ (half [a+y, x] (list ++ [a, b]))

Haskell, 227 203 bytes
17 bytes saved thanks to Οurous
(%)=div
u x|odd x=x%2+1|1>0=x%2
[0,b]!l=[b]!l
[b,0]!l=[b]!l
t!l|elem t l=[dropWhile(/=t)l]
t@[a,b]!l|q<-l++[t]=[a%2,u a+b]!q++[u b+a,b%2]!q
f x|q<-[x%2,u x]![[x]]=[a|(a,b)<-zip q[0..],notElem a$take b q]

Try it online!

Wouldn't using lists be shorter than tuples, since you could handle both the 1 and 2 element cases with the same show?

@Οurous Actually you are right it is shorter it just takes some work.


text:
Is it a shuffle?
Yesterday I asked this question about riffle shuffles.  It seems that yesterdays question was a bit too hard so this question is a related but much easier task.
Today you are asked to determine if a permutation is in fact a riffle shuffle.  Our definition of riffle shuffle is adapted from our last question:
The first part of the shuffle is the divide.  In the divide partition the deck of cards in two.  The two subsections must be continuous, mutually exclusive and exhaustive.  In the real world want to make your partition as close to even as possible, however in this challenge this is not a consideration, all partitions including ones that are degenerate (one partition is empty) are of equal consideration.
After they have been partitioned, the cards are spliced together in such a way that cards maintain their relative order within the partition they are a member of.  For example, if card A is before card B in the deck and cards A and B are in the same partition, card A must be before card B in the final result, even if the number of cards between them has increased.  If A and B are in different partitions, they can be in any order, regardless of their starting order, in the final result.
Each riffle shuffle can then be viewed as a permutation of the original deck of cards.  For example the permutation
1,2,3 -> 1,3,2

is a riffle shuffle.  If you split the deck like so
1, 2 | 3

we see that every card in 1,3,2 has the same relative order to every other card in it's partition.  2 is still after 1.
On the other hand the following permutation is not a riffle shuffle.
1,2,3 -> 3,2,1

We can see this because for all the two (non-trivial) partitions
1, 2 | 3
1 | 2, 3

there is a pair of cards that do not maintain their relative orderings.  In the first partition 1 and 2 change their ordering, while in the second partition 2 and 3 change their ordering.
Task
Given a permutation via any reasonable method, determine if it represents a valid riffle shuffle.  You should output two distinct constant values one for "Yes, this is a riffle shuffle" and one for "No, this is not a riffle shuffle".
This is code-golf so answers will be scored in bytes with less bytes being better.
Test Cases
1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False

Can the output be inconsistent, but truthy / falsy in our language? Like (Python, where, among the integers only 0 is falsy) 0 for falsy but any integer in [1, +∞) for truthy?

@Mr.Xcoder I don't like the truthy/falsy values because they are rather hard to define well.  Answers should stick to the current rules.

Suggested test case: [3,1,4,2,5].

Sorry about this, but: [2,3,6,1,4,5].

Can we take permutations of [0, ..., n-1] instead of [1, ..., n] as input?

@Dennis Sure,  I was just starting at 1 for consistency any reasonable form of input is fine by me.

JavaScript (ES6), 47 bytes
Takes input as an array of integers. Returns a boolean.
([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

Test cases

let f =

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

;[
  [1,3,2      ],  // -> True
  [3,2,1      ],  // -> False
  [3,1,2,4    ],  // -> True
  [2,3,4,1    ],  // -> True
  [4,3,2,1    ],  // -> False
  [1,2,3,4,5  ],  // -> True
  [1,2,5,4,3  ],  // -> False
  [3,1,4,2,5  ],  // -> True
  [2,3,6,1,4,5]   // -> False
]
.forEach(a => console.log(JSON.stringify(a) + ' -> ' + f(a)))

How?
The input array A is a valid riffle shuffle if it consists of at most two distinct interlaced sequences of consecutive integers.
The challenge rules specify that we're given a permutation of [1...N]. So we don't need to additionally check that the sorted union of these sequences actually results in such a range.
We use a counter x initialized to A[0] and a counter y initially undefined.
For each entry z in A, starting with the 2nd one:

We check whether z is equal to either x+1 or y+1. If yes, we increment the corresponding counter.
Else: if y is still undefined, we initialize it to z.
Else: we make the test fail.

Haskell, 41 bytes
n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l

Try it online!
Checks if the list concatenated to itself contains the numbers 0..n-1 in order as a subsequence.

Python 2, 39 bytes
l=input()
n=0
for x in l*2:n+=n==x
l[n]

Try it online!
Takes the list 0-indexed and outputs via exit code.

Haskell, 43 bytes
s takes a list of integers as in the OP examples and returns a Bool.
s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter

Try it online!
How it works

The list comprehension tries each element x of p in turn and checks if it can be the first element of the second partition of the shuffle. Then or returns True if any of the checks were True.
The comprehension does this by partitioning (with filter) p into elements smaller and larger than (or equal to) x, concatenating, and checking if the resulting list is [1..length p], i.e. the elements in order.
The check for whether the resulting list is [1..length p] is done by seeing if the result is strictly smaller than the infinite list [1..] == [1,2,3,etc.], which gives the same result for any permutation.

Jelly, 13 6 bytes
ỤIṢḊRẠ

Try it online!
Alternate version, postdates challenge, 5 bytes
Ụ>ƝSỊ

Try it online!
How it works
ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])

Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.

Brachylog, 9 bytes
o~cĊ⟨⊆⊇⟩?

Try it online!
The predicate succeeds if the input represents a riffle shuffle and fails if it does not, meaning among other things that if the predicate is run as an entire program success will print true. and failure will print false.. Input is taken as a list of any sorts of items and interprets it as representing a permutation of itself sorted.
   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.

I feel like there's something in the spirit of ⊆ᵐ which should work in the place of the four-byte "sandwich" construct ⟨⊆⊇⟩.

I think you are the first person to use a sandwich in a PPCG answer (and it's a beautiful symmetric one :))

Python 2, 75 60 47 bytes
thanks to Dennis for -13 bytes
x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q

Try it online!
Output is via exit code.

Pyth, 5 bytes
}SQy+

Test suite
}SQy+

    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted

Checks whether the doubled input list contains a sorted version of itself as a subsequence.
Thanks to Erik the Outgolfer for 1 byte taking better advantage of implicit input with +QQ rather than *2Q.

5 bytes: }SQy+. It gets expanded to }SQy+QQ.

@EriktheOutgolfer Nice one, thanks.

Ruby, 35 bytes
->l{l.any?{|a|l&[*1..a]|l==l.sort}}

Try it online!
How?

l & [*1..a] | l applies an intersection and then an union: first get the elements of l that are <=a and then add the remaining elements of l without changing the order. If a is the number we are looking for, then this operation is the same as sorting l.

Clean, 56 55 bytes
import StdEnv
?l=any(\e=sortBy(\a b=a<e&&b>=e)l<[1..])l

Try it online!

Pyth, 9 bytes
!t-.+xLQS

Test suite.
Saved 3 bytes thanks to isaacg.
Pyth, 14 bytes
}SQm.nS.Tcd2./

Try it here! or Verify all the test cases.
Outputs True and False for riffle-shuffle and non-riffle-shuffle respectively.
How?

}SQm.nS.Tcd2./ ~ Full program. Reads input from STDIN and outputs to STDOUT.

            ./ ~ Return all divisions of the input into disjoint substrings (partition).
   m           ~ Map over the above using a variable d.
         cd2   ~ Chop d into two-element lists.
       .T      ~ Justified transpose, ignoring absences.
      S        ~ Sort (lexicographically).
    .n         ~ Deep-flatten.
}              ~ Check if the above contains...
 SQ            ~ The sorted input.

Furthermore, <#0 can be replaced by - for 2 more bytes.

@isaacg Oh yeah facepalm thanks. Edited. Edited.

Husk, 7 bytes
±§#OoṖD

Test suite!

C (gcc), 61 bytes
a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}

Try it online!

Perl, 28 bytes
Includes +1 for a
Input on STDIN, 1 based
perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"

Uses xnor's algorithm