title: Count edits accounting for grace period

text:
# Question
Title: Count edits accounting for grace period
When you edit a post on SE, any further edits within a 5-minute grace period are merged into it. Given a list of times you edit a post, count the edits not in a grace period.

Say you edit at minutes `[0,3,4,7,9,10,11,12]`. This results in 3 edits at times `[0,7,12]`, with the rest happening in their grace periods.

```
0:  [3,4]
7:  [9,10,11]
12: []

```
* The first edit is at minute 0. The edits at minutes 3 and 4 are within its 5-minute grace period, and so don't count.
* The second edit is at minute 7. The edits at minutes 9, 10, 11 are within its grace period.
* The third edit at minute 12 is just past the edge of the 5-minute grace period starting at minute 7.

So, the output is 3.

The list of times in minutes will be an list of increasing integers. The first number will always be 0 for the initial posting, which we count as an edit.

**Test cases:**

```
[0]
[0,3,5,7]
[0,3,4,7,9,10,11,12]
[0,30,120]
[0,4,8,12,16]
[0,4,8,12,16,20]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
[0,5,10,15,20]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
[0,1,4,5,9,11,12,14,16,18,23,24,26,28,29,30]

```

Outputs:

```
1
2
3
3
3
3
4
5
5
6

```

For ease of copying, here are the inputs, outputs, and input/output pairs:

```
[[0], [0, 3, 5, 7], [0, 3, 4, 7, 9, 10, 11, 12], [0, 30, 120], [0, 4, 8, 12, 16], [0, 4, 8, 12, 16, 20], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], [0, 5, 10, 15, 20], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], [0, 1, 4, 5, 9, 11, 12, 14, 16, 18, 23, 24, 26, 28, 29, 30]]
[1, 2, 3, 3, 3, 3, 4, 5, 5, 6]
[([0], 1), ([0, 3, 5, 7], 2), ([0, 3, 4, 7, 9, 10, 11, 12], 3), ([0, 30, 120], 3), ([0, 4, 8, 12, 16], 3), ([0, 4, 8, 12, 16, 20], 3), ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 4), ([0, 5, 10, 15, 20], 5), ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], 5), ([0, 1, 4, 5, 9, 11, 12, 14, 16, 18, 23, 24, 26, 28, 29, 30], 6)]

```

**Leaderboard:**

```
var QUESTION_ID=141949,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/141949/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 21 votes
# JavaScript, 36 bytes

```
f=$=>$>f&&1+f($.filter(b=>b-$[0]>4))

```

Try it online!

### How it works

In each recursive call we delete all elements from the array which are more than 4 minutes distant from the first element.
There is a little trick with variable name `$`. The check `$>f` firstly converts the array to a string and then compare it to the string representation of the function `f` and then compares them lexicographically. The first character of stringified array is a digit and therefore only one-char variable name whose ascii index is smaller than indices of all digits is `$`. Replacing `$` with any other variable name will always return `false`.

# Answer
> 8 votes
# Mathematica, ~~46~~ ~~40~~ ~~37~~ 33 bytes

```
(i=1;j=0;#-j<5||(i++;j=#)&/@#;i)&

```

### Explanation

```
i=1;j=0

```

Set `i` to `1` and `j` to `0`.

```
... /@#

```

Map onto all elements of the input...

```
#-j<5||(i++;j=#)&

```

If `(element) - j < 5` is false, then increment `i` and set `j` to the element (short-circuit evaluation).

```
;i

```

Output `i`.

# Answer
> 6 votes
# Husk, 8 bytes

```
Γ(→₀f>+4

```

Try it online!

## Explanation

```
Γ(→₀f>+4  Implicit input, a list of numbers.
Γ(        Deconstruct into head n and tail x (if empty, return 0).
    f>+4  Keep those elements of x that are greater than n+4.
   ₀      Call main function recursively on the result.
  →       Increment.

```

# Answer
> 5 votes
# Python 2, 58 bytes

```
a=input()
x=[0]
for k in a:x+=[k]*(k-x[-1]>4)
print len(x)

```

Try it online!

* Saved 2 bytes thanks to @Mr. Xcoder.

## 49 bytes

```
f=lambda a:a>[]and-~f([x for x in a if x-a[0]>4])

```

Using the recursive method shown in @ThePirateBay's solution.

* Saved a byte thanks to @Mr. Xcoder.
* Saved 2 bytes thanks to @Halvard Hummel.

Try it online!

# Answer
> 5 votes
## Husk, 6 bytes

```
Lüo<+5

```

Try it online!

```
  o<+5        a function that takes two arguments and checks if
              the second is less than the the first plus 5
 ü            remove equal elements from the input list using the above
              function as the equality test
L             return the length of the remaining list

```

# Answer
> 4 votes
# MATLAB, 34 bytes

```
@(x)nnz(uniquetol(x+1,4/max(x+1)))

```

Anonymous function that inputs an array and outputs a number.

This uses the `uniquetol` function, specifically its form `y = uniquetol(x, t)`, which gives `y` containing unique elements of `x` with tolerance `t`. In doing so, the function seems to follow a "lazy" approach: sort `x`, pick its first entry, and keep skipping entries for as long as they are within tolerance of the latest picked entry. That is exactly what is needed here.

The `uniquetol` function automatically scales the specified tolerance by the maximum absolute value in `a`. This is why we need the division here. `x+1` is used instead of `x` to avoid division by 0.

Verification of test cases:

```
>> f = @(x)nnz(uniquetol(x+1,4/max(x+1)));
>> inputs = {...
       [0] ...
       [0,3,5,7] ...
       [0,3,4,7,9,10,11,12] ...
       [0,30,120] ...
       [0,4,8,12,16] ...
       [0,4,8,12,16,20] ...
       [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] ...
       [0,5,10,15,20] ...
       [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] ...
       [0,1,4,5,9,11,12,14,16,18,23,24,26,28,29,30] ...
   };
>> outputs = cellfun(f, inputs)
outputs =
     1     2     3     3     3     3     4     5     5     6

```

# Answer
> 3 votes
# , 20 bytes

```
[:#(,}.~5>(-{.))/@|.

```

Try it online!

## Explanation

```
[:#(,}.~5>(-{.))/@|.  Input: array A
                  |.  Reverse
                /@    Reduce from right-to-left
            {.          Head of RHS
           -            Subtract with LHS
        5>              Less than 5
     }.~                Drop that many from
    ,                   Join
[:#                   Length

```

# Answer
> 2 votes
# Haskell, ~~31~~ 30 bytes

```
f(x:y)=f[z|z<-y,z-4>x]+1
f x=0

```

Try it online!

Saved 1 byte thanks to Zgarb

# Answer
> 2 votes
# 05AB1E, ~~20~~ ~~19~~ ~~18~~ ~~15~~ ~~14~~ 11 bytes

```
v®y‹iy4+©\¼

```

**Explanation:**

```
v          # loop on input
 ®          # push register_c, start at -1
  y‹i         # if current item greater than last item
   y4+         # push new max on stack
    ©\          # push new max on register_c, and pop it from stack
     ¼           # increment counter_variable
                  # implicit print of counter_variable

```

Try it online!

**Edit**

* -3 bytes thanks to Riley and the usage of counter\_variable
* no need for counter\_variable after all
* -3 bytes again thanks to Riley and the usage of register\_c

# Answer
> 1 votes
# Perl 5, 54 bytes

52 bytes of code +2 for `-ap`

```
{$_++;$p=shift@F;1while$F[0]<$p+5&&shift@F;@F&&redo}

```

Try it online!

# Answer
> 1 votes
# Pyth, 14 bytes

```
L&lbhyfg-Thb5b

```

This is a recursive function. Call it with `y[0 1 2 3 4 5 6 7 8)`, where `[...)` is your list.

Alternatively, **Try it here!** or **Verify all the test cases.**

---

# Explanation

This is roughly equivalent to the Python solution. A translation would give the following results:

```
def y(b):
 return (len(b) and y(filter(lambda T:T>=b[0]+5,b)) + 1)

```

### Code Breakdown

```
L&lbhyfg-Thb5b   - Function called y that accepts a list parameter b.

L                - Define the function.
  lb             - The length of b...
 &               - ... Logical AND ...
    h            - Increment by 1.
     y           - The result given by calling the function recursively on the following:
      f      b     - b filtered...
        -Thb       - ... For the elements whose difference compared to the first element...
       g    5      - ... Is greater than or equal to 5.

```

# Answer
> 1 votes
# 05AB1E, 14 bytes

```
æʒ¬s¥4›Ps_*}θg

```

Try it online!

# Answer
> 1 votes
# Retina, ~~32~~ 26 bytes

```
.+
$*11
(1+)(¶1{1,4}\1)*\b

```

Try it online! Explanation:

```
.+
$*11

```

Convert to unary, but add 1, because 0 is a tricky concept in Retina.

```
(1+)(¶1{1,4}\1)*\b

```

Count the number of edits, but include all the grace edits in each match.

# Answer
> 1 votes
# Ly, 29 bytes

```
&nr5+sp[[lL[pp2$]p5+sp>`<]]>`

```

Try it online!

It took a long time to get here.

# Answer
> 1 votes
# Java 8, ~~78~~ ~~61~~ ~~60~~ ~~59~~ 56 bytes

***Port of @JungHwanMin's answer***

```
a->{int i=0;for(int l:a)if(l-a[i]>4)a[++i]=l;return-~i;}

```

Try it online!

# Answer
> 1 votes
# MATL, ~~13~~ 12 bytes

```
`ttX<4+>)t}@

```

Try it online! Or verify all test cases.

### Explanation

```
`        % Do..while
  t      %   Duplicate. Takes input (implicitly) the first time
  tX<    %   Duplicate and get minimum, i.e the first entry
  4+     %   Add 4
  >      %   Greater than? Element-wise
  )      %   Keep entries that fulfill that
  t      %   Duplicate. This is used as loop condition
}        % Finally (execute at the end of the loop)
  @      %   Push number of iterations. This is the output
         % End (implicit). A new iteration is run if top of the stack is truthy

```

# Answer
> 1 votes
# C# .NET, 63 bytes

```
a=>{int e=0;foreach(int l in a)if(l-a[e]>4)a[++e]=l;return-~e;}

```

**Explanation:**

Try it here.

```
a=>{                   // Method with integer-array parameter and integer return-type
  int e=0;             //  Amount of edits (starting at 0)
  foreach(int l in a)  //  Loop over the input-array
    if(l-a[e]>4)       //   If the current value minus the current edit is larger than 4:
      a[++e]=l;        //    Raise the edit-count by 1 first,
                       //    and set the current value to this next current edit
                       //  End of loop (implicit / single-line body)
  return-~e;           //  Return the amount of edits + 1
}                      // End of method

```

# Answer
> 1 votes
# Pip, 20 bytes

```
Fxg{Ix>i+4{++oi:x}}o

```

Attempt This Online!

#### Explanation

```
Fxg{Ix>i+4{++oi:x}}o  # Implicit input on the command line
Fxg{              }   # for x in input:
    Ix>i+4{      }    #  if x > i+4:
           ++o        #   increment o (defaults to 1)
              i:x     #   i = x
                   o  # print o

```

# Answer
> 0 votes
# Jelly, 11 bytes

```
+4Ḣ<x@µÐĿL’

```

Try it online!

## Explanation

```
+4Ḣ<x@µÐĿL’  Input: array A
      µÐĿ    Repeat until the results converge
+4             Add 4
  Ḣ            Head
   <           Greater than
    x@         Copy only the true values
         L   Length
          ’  Decrement

```

## 12 bytes

```
;I4<1;x@;ð/L

```

Try it online!

## Explanation

```
;I4<1;x@;ð/L  Input: array A
         ð/   Reduce A from left-to-right using
;               Concatenate
 I              Increment
  4<            Greater than 4
    1;          Prepend 1
      x@        Times each of
        ;       Concatenate
           L  Length

```

# Answer
> 0 votes
# Pyth, 25 bytes

```
J1K5FN.+Q=-KNIg0K=hJ=K5;J

```

Try it here: http://pyth.herokuapp.com

# Answer
> 0 votes
# Proton, 40 bytes

Heavily inspired by the Python solution.

```
f=a=>len(a)and-~f(filter(x=>x>a[0]+4,a))

```

Try it online!

# Answer
> 0 votes
# Kotlin, 52 bytes

*Posting as a function, if this is not acceptable I will change it to a method*

## Submission

```
{var x=it[0]
var o=1
it.map{if(it>x+4){o++
x=it}}
o}

```

## Beautified

```
{
    // Last counted edit
    var x=it[0]
    // Current edit total
    var o = 1
    // For each edit
    it.map{
        // If it was 5 or more minutes ago
        if (it>x+4) {
            // Increase edit count
            o++
            // Make it the last counted edit
            x=it
        }
    }
    // Return the edit count
    o
}

```

## Test

```
var r:(IntArray)->Int=
{var x=it[0]
var o=1
it.map{if(it>x+4){o++
x=it}}
o}

fun main(args: Array<String>) {
    println(r(intArrayOf(0)))
    println(r(intArrayOf(0,3,5,7)))
    println(r(intArrayOf(0,3,4,7,9,10,11,12)))
    println(r(intArrayOf(0,30,120)))
    println(r(intArrayOf(0,4,8,12,16)))
    println(r(intArrayOf(0,4,8,12,16,20)))
    println(r(intArrayOf(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19)))
    println(r(intArrayOf(0,5,10,15,20)))
    println(r(intArrayOf(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)))
    println(r(intArrayOf(0,1,4,5,9,11,12,14,16,18,23,24,26,28,29,30)))
}

```

TryItOnline

# Answer
> 0 votes
# PowerShell, 74 bytes

```
for($x,$y=$args[0];$y;$x,$y=$y){if($l-le$x-5){$i++;$l=$x}}$i+1+($l-le$x-5)

```

Iterative solution. Lengthy because of fenceposting on the `for` loop requiring an additional check on the end. *Golfing suggestions welcome.*

We take input `$args[0]` as a literal array, peel off the first element into `$x` and the remaining into `$y`. Then, so long as there are elements still in `$y`, we loop.

Each iteration, we check whether the current timestamp `$x` is `5` or more away from the `$l`ast edit timestamp. If so, we increment our counter `$i++` and set our timestamp to be current. Then, on the iteration of the loop, we peel off the next element into `$x` and leave the remaining in `$y`.

Once we're out of the loop, we output `$i`, plus `1` for the initial edit, plus whether the final timestamp is more than five away from the last edit (with the Boolean value implicitly cast to integer). That result is left on the pipeline and output is implicit.

Try it online!

# Answer
> 0 votes
# , 52 bytes

```
function(l){while(sum(l|1)){l=l[l-l[1]>=5]
F=F+1}
F}

```

Try it online!

Simple anonymous function that iteratively removes elements from the list that are less than 5 away from the first element until the list is empty, then returns the counter.

# Answer
> 0 votes
## Clojure, 53 bytes

```
#(count(set(reductions(fn[r v](if(<(- v r)5)r v))%)))

```

This keeps track of the "edit starting times", and then returns their distinct count.

# Answer
> 0 votes
# Japt, ~~14~~ 12 bytes

```
Ê©ÒßUfÈ-UÎ¨5

```

Try it

# Answer
> 0 votes
# C (gcc), ~~62~~ 61 bytes

*-1 byte thanks to @ceilingcat*

```
f(v,t,c)int*v;{for(t=c=0;*++v;)*v-t>4&&(t=*v)&++c;return-~c;}

```

Try it online!

# Answer
> 0 votes
# Nekomata, 7 bytes

```
ˡ{C4+>‼

```

Attempt This Online!

A port of @Zgarb's Husk answer.

```
ˡ{C4+>‼N
ˡ{          Iterate the following block until it fails, and counts the number of iterations
  C           Split the list into its head and tail
   4+         Add 4 to the head
     >‼       Filter the tail by whether it is greater than the head + 4

```

# Answer
> 0 votes
# Scala, 51 bytes

Modified from @Roberto Graham's Java answer.

Golfed version. Try it online!

```
a=>{var i=0;for(l<-a)if(l-a(i)>4)a({i+=1;i})=l;i+1}

```

---
Tags: code-golf, sequence, counting, subsequence
---


title: How many sorting networks?

text:
# Question
Title: How many sorting networks?
Below on the left is a picture of a sorting network that can sort 4 inputs. On the right you can see it sorting the input `3,2,4,1`.

A sorting network of size `n` consists of a set of `n` horizontal wires where two wires can be connected by a vertical wire. The inputs to a sorting network move from the left to the right on the horizontal wires and whenever a vertical wire connects two elements they swap places if the lower element comes before the higher element.

The example sorting network above has the property that it correctly sorts all inputs. You could add even more wires but the behavior would not change. But if you removed a wire then there would be some inputs that it would not sort anymore.

Two networks behave the same if for every input permutation they produce the same output permutation. Your task is to find out how many possible behaviors there are for a given size. That is, output a sequence of the number of behaviors (equivalence classes) for n=1,2,3,... etc.

Your code will be scored based on its speed on an AMD Ryzen 1800X Linux system. The code should output the sequence described above. I'll run each submission for 5 minutes and with a 16GiB ram limit. Whichever code has outputted most of the sequence wins. Ties are broken by whichever program outputted the final number first.

You can use a probabilistic algorithm, however it must be in the 5 sigma threshold, meaning that the chance that your program outputs the incorrect result must be less than one in 3.5 million. If it's good enough for particle physics, it's good enough for this challenge.

Sequence output

```
1
2
11
261
43337
72462128

```

A lower bound on the seventh value is 4.6 billion, but personally I'd guess it's around a trillion.

# Leaderboard

| Score | Language | Author |
| --- | --- | --- |
| 6 in 10.75s | Rust | gsitcia |
| 6 in 23.97s | Rust | isaacg |
| 6 in 70.93s | Rust | Anders Kaseorg |
| 5 in 0.188s | Haskell | Roman Czyborra |
| 5 in 1.437s | JS (Node.js) | Arnauld |
| 4 in 0.038s | Haskell | Roman Czyborra |

# Answer
# Rust, \\$n = 6\\$ in ≈ 59 seconds

The main simplifying observation here is that we don’t need to run the network on all \\$n!\\$ permutations; it suffices to run it on all \\$2^n\\$ binary strings. We can do this efficiently on all strings simultaneously using bitwise operations.

**`Cargo.toml`**

```
[package]
name = "sorting"
version = "0.1.0"
edition = "2021"

[dependencies]
hashbrown = "0.13.2"
typed-arena = "2.0.2"

```

**`src/main.rs`**

```
use hashbrown::HashSet;
use typed_arena::Arena;

type Item = u64;
const LOG_BITS: usize = Item::BITS.trailing_zeros() as usize;

fn search<'a>(arena: &'a Arena<Item>, found: &mut HashSet<&'a [Item]>, state: &mut [Item]) {
    let n = state.len();
    for i in 0..n - 1 {
        let p = state[i];
        for j in i + 1..n {
            let q = state[j];
            if p & !q != 0 {
                state[i] = p & q;
                state[j] = p | q;
                let mut inserted = false;
                found.get_or_insert_with(state, |state| {
                    inserted = true;
                    arena.alloc_extend(state.iter().copied())
                });
                if inserted {
                    search(arena, found, state);
                }
                state[i] = p;
                state[j] = q;
            }
        }
    }
}

fn count_networks(n: usize) -> usize {
    assert!(n <= LOG_BITS);
    let mut state = Vec::from_iter((0..n).map(|i| !0 / (1 << (1 << i) | 1)));
    let arena = Arena::new();
    let mut found = HashSet::new();
    found.insert(&*arena.alloc_extend(state.iter().copied()));
    search(&arena, &mut found, &mut state);
    found.len()
}

fn main() {
    for n in 1..=LOG_BITS {
        println!("{}", count_networks(n));
    }
}

```
> 12 votes

# Answer
# Rust, \\$n=6\\$ in roughly ~~50~~ ~~48~~ ~~43~~ ~~41~~ 23 seconds.

*Thanks to @AnttiP for a 44% speedup!*

My solution is based off of @AndersKaseorg's solution. I originally posted my changes as comments there, but with the number of changes I've made, I thought it'd be better to post as a separate answer.

**`Cargo.toml`**

```
cargo-features = ["profile-rustflags"]

[package]
name = "sorting"
version = "0.1.0"
edition = "2021"

[dependencies]
hashbrown = "0.13.2"
rustc-hash = "1.1.0"

[profile.release]
rustflags = ["-C", "target-cpu=native"]

```

**`src/main.rs`**

```
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;
type HashSet<V> = hashbrown::HashSet<V, BuildHasherDefault<FxHasher>>;

type Item = u64;
const LOG_BITS: usize = Item::BITS.trailing_zeros() as usize;

/*
    Extract just the nontrivial bits that can actually change:
    0..57 from state[0]
    0..57 from state[1]
    0..57 from state[2]
   11..57 from state[3]
   26..57 from state[4]
     none from state[5]

    A bit position is either trivial or can't change
    if in the input, all wires after that position were 1s.
    That position is either forced to be a 1,
    or reconstructible from the other earlier wires.

    It turns out to be safe to just treat trivial bits as if
    they're already zeroed out, rather than zeroing them manually.
    Empirically, this causes no collisions.
    I wasn't sure that this would work, but it does,
    and that's good enough for me.
*/
type CompactState = [Item; 4];
const fn compact(state: &[Item; LOG_BITS]) -> CompactState {
    let out_0 = state[0] ^ (state[1] << 57);
    let out_1 = (state[1] >> 7) ^ (state[2] << 50);
    let out_2 = (state[2] >> 14) ^ (state[3] << (43 - 11));
    let out_3 = (state[3] >> (21 + 11)) ^ state[4];
    [out_0, out_1, out_2, out_3]
}

fn search<'a>(
    found: &mut HashSet<CompactState>,
    state: &mut [Item; LOG_BITS],
    last_i: usize,
    last_j: usize,
) {
    for i in 0..LOG_BITS - 1 {
        let p = state[i];
        for j in i + 1..LOG_BITS {
            if i < last_i && j != last_i && j != last_j {
                continue;
            }
            let q = state[j];
            if p & !q != 0 {
                state[i] = p & q;
                state[j] = p | q;
                let compact_state = compact(state);
                let inserted = found.insert(compact_state);
                if inserted {
                    search(found, state, i, j);
                }
                state[i] = p;
                state[j] = q;
            }
        }
    }
}
// Inputs that are already sorted are removed.
fn initial_state(n: usize) -> [Item; LOG_BITS] {
    // Remove inputs that are already sorted
    let inputs: Vec<u64> = (0..1 << n)
        .rev()
        .filter(|i| (0..n - 1).any(|b| i & (1 << b) > 0 && i & (1 << (b + 1)) == 0))
        .collect();
    let mut state = [0; LOG_BITS];
    for (wire_index, wire_mut) in state.iter_mut().enumerate() {
        if wire_index < n {
            for (bit_index, input) in inputs.iter().enumerate() {
                if input & 1 << wire_index > 0 {
                    *wire_mut |= 1 << bit_index;
                }
            }
        } else {
            // If n < LOG_BITS, pad with all-ones wires.
            *wire_mut = !0;
        }
    }
    // Debugging printout
    if false {
        for wire in state {
            println!("{wire:#066b}");
        }
    }
    state
}
fn count_networks(n: usize) -> usize {
    assert!(n <= LOG_BITS);
    let mut state = initial_state(n);
    let mut found: HashSet<CompactState> = HashSet::default();
    let compact_state = compact(&state);
    found.insert(compact_state);
    search(&mut found, &mut state, 0, 0);
    found.len()
}

fn main() {
    for n in 1..=LOG_BITS {
        println!("{}", count_networks(n));
    }
}

```

The basic idea of this program, and of @AndersKaesorg's solution, is to maintain a state consisting of the effect of a sorting network on all possible inputs of \\$n\\$ bits, from `000000` to `111111`. The state is internally represented as a vector of \\$n\\$ 64-bit integers, where each of the first \\$2^n\\$ bit indexes represents one possible input. All possible comparisons are performed, and a hash table is used to check if any comparisons give a new result. If so, it's added to the hash table and the comparison function is called recursively.

The changes I've made, starting from @AndersKaesorg's solution, are:

* Track the last pair of wires that were compared in order to reach the current state. If that pair doesn't overlap with the current comparison being considered, and the current comparison is earlier lexicographically that the last comparison, skip the current comparison. In other words, we shouldn't consider both comparing `[1, 2]` then `[3, 4]` and also comparing `[3, 4]` then `[1, 2]` \- both orderings give the same result.
* When inserting a state into the HashSet to check if it's a new state, leave out the final wire of the state. Because a comparison doesn't change the total number of 0s and 1s, the contents of the last wire are implicit in the other wires.
* Change the hash function from ahash, Rust's default hashing function, to FxHash, which is what the rust compiler uses. It's less collision-resistant, but much faster, and the tradeoff is worth it.
* Store the hash table values as fixed-width arrays, rather than variable-width slices. This communicates more information about the hash values to the compiler, allowing it to produce more optimized code.
* Enable optimizations for my specific machine: `rustflags = ["-C", "target-cpu=native"]`.
* When generating the initial state with all possible inputs, remove the \\$n+1\\$ inputs that are already in sorted order, as these inputs don't distinguish anything. Move the remaining inputs to the low-order bits of the 64-bit integers in the state. This helps because FxHash is asymmetrical: It makes more use of entropy in the low-order bits than the high-order bits, because it performs a multiplication by a large constant and discards the overflow.
* Extract just the nontrivial bits from the state, and use those as the HashSet value. This amounts to only 4 u64s, rather than 5 previously. This isn't a huge time saving, only 1-2 seconds, because of the extra work that needs to be done to generate the smaller value. However, this change dramatically shrinks the peak memory usage, from about 70% of my machine's RAM to about 40% of it.
* Simplify the hash value extraction with some arcane magic.
* Store the HashSet values directly in the HashSet, rather than in a separate allocation. This is slightly less memory efficient, but much faster. It only became possible because of the previous memory efficiency improvements.

In my timing on my machine, these changes brought the runtime down from ~75 seconds to ~23 seconds.
> 6 votes

# Answer
# Rust, n=6 in ~~~12~~ 1 second

This answer is based on @Anders Kaseorg's solution and uses some of @isaacg's improvements.

I got the answer 1,530,608,978,810 for n=7 in about 12 hours using more than 100 gigabytes of ram. (I'm not completely sure it's correct, since I don't know how to prove the conjectures this relies on).

The basic strategy is to count the total number of networks using the principle of inclusion-exclusion (splitting into groups based on the first swap).

**`Cargo.toml`**

```
cargo-features = ["profile-rustflags"]

[package]
name = "sorting_networks"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
hashbrown = "0.13.2"
rustc-hash = "1.1.0"
nohash-hasher = "0.2.0"

[profile.release]
rustflags = ["-C", "target-feature=+crt-static"]

```

**`main.rs`**

```
use std::{
    cmp::min,
    iter::repeat,
    mem::{replace, swap},
    time::{Duration, Instant},
};

use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;
type HashSet<V> = hashbrown::HashSet<V, BuildHasherDefault<FxHasher>>;
type HashMap<K, V> = hashbrown::HashMap<K, V, BuildHasherDefault<FxHasher>>;

macro_rules! networks {
    ($n:expr) => {
        networks::<{ $n }, { ($n * $n - $n) / 2 }>()
    };
}

type Item = u64;

fn main() {
    let then = Instant::now();
    networks!(1);
    networks!(2);
    networks!(3);
    networks!(4);
    networks!(5);
    networks!(6);
    // networks!(7);
    println!("Total time: {:?}", Instant::now().duration_since(then));
}

/**
 * Calculates number of networks
 */
fn networks<const N: usize, const N2: usize>() -> i64 {
    let then = Instant::now();
    let v: Vec<(i64, i64, Duration, Vec<u64>)> = counter(N)
        .into_iter()
        .map(|(sizes, multiplier)| {
            let then = Instant::now();
            let a = count_specific::<N, N2>(&sizes);
            (a, multiplier, Instant::now().duration_since(then), sizes)
        })
        .collect();
    let o = v.iter().map(|(a, m, _, _)| a * m).sum::<i64>() + 1;
    println!(
        "n={}: {} (took {:?})",
        N,
        o,
        Instant::now().duration_since(then)
    );
    v.iter().for_each(|(a, m, duration, sizes)| {
        println!(
            "  {:?}: {} = {} * {} (took {:?})",
            sizes,
            a * m,
            a,
            m,
            duration
        );
    });
    o
}

/**
 * Calculate multipliers for PIE
 */
fn counter(n: usize) -> HashMap<Vec<Item>, i64> {
    let mut counts = HashMap::default();
    if n == 1 {
        return counts;
    }
    let mut uf = UnionFind::new(n);
    counter_(&mut uf, n, 0, 1, 1, &mut counts);
    counts
}

fn counter_(
    uf: &mut UnionFind,
    n: usize,
    i: usize,
    j: usize,
    m: i64,
    counts: &mut HashMap<Vec<Item>, i64>,
) {
    let mut j1 = j + 1;
    let i1 = if j1 == n {
        j1 = i + 2;
        i + 1
    } else {
        i
    };
    uf.save();
    uf.join(i, j);
    *counts.entry(uf.get_sizes()).or_insert(0) += m;
    if j1 < n {
        counter_(uf, n, i1, j1, -m, counts);
    }
    uf.rollback();
    if j1 < n {
        counter_(uf, n, i1, j1, m, counts);
    }
}

/**
 * Counts number of networks that start with sorts that have given sizes
 */
fn count_specific<const N: usize, const N2: usize>(sizes: &Vec<Item>) -> i64 {
    let mut base_state = [0; N];
    let mut num_bits = 0;
    if sizes.iter().filter(|&v| v & 1 == 1).count() > (N & 1) {
        // no symmetric starting states
        let filter: Vec<_> = sizes
            .iter()
            .copied()
            .scan(0, |state, i| {
                let offset = *state;
                *state += i;
                Some(((1 << i) - 1, offset))
            })
            .collect();
        (1..1 << N)
            .filter(|&v| {
                // filter out states that aren't sorted in given ranges
                filter.iter().all(|&(mask, offset)| {
                    let n = (v >> offset) & mask;
                    n & (n + 1) == 0
                })
            })
            .filter(|&v: &Item| v & (v + 1) != 0) // filter out states that are completely sorted
            .for_each(|v| {
                // convert to state
                (0..N).rev().fold(v, |acc, i| {
                    base_state[i] = (base_state[i] << 1) | (acc & 1);
                    acc >> 1
                });
                num_bits += 1;
            });
        if num_bits > Item::BITS {
            panic!("Too big? {} > {} {:?}", num_bits, Item::BITS, sizes);
        }

        let mut states: HashSet<[Item; N]> = HashSet::default();

        visit_notree::<N, N2>(&mut base_state, &mut states); // populate states
        states.len() as i64
    } else {
        let mut state_to_idx: HashMap<[Item; N], usize> = HashMap::default();
        let mut tree: Vec<[usize; N2]> = Vec::new();
        let filter: Vec<_> = sizes
            .iter()
            .copied()
            .scan(0, |state, i| {
                // filter divides range so [3,2] => 0b1001001, 0b0100010
                let w = i / 2;
                let mask = (1 << w) - 1;
                let offset0 = *state;
                let mask0 = mask << offset0;
                let offset1 = N as Item / 2;
                let mask1 = (i & 1) << offset1;
                let offset2 = N as Item - (w + offset0);
                let mask2 = mask << offset2;
                *state += w;
                Some((
                    mask0,
                    offset0,
                    mask1,
                    offset1 - w,
                    mask2,
                    offset2 - w - (i & 1),
                ))
            })
            .collect();
        (1..1 << N)
            .filter(|v: &Item| {
                // filter out states that aren't sorted in given ranges
                filter.iter().all(|&(m0, o0, m1, o1, m2, o2)| {
                    let n = (v & m0) >> o0 | (v & m1) >> o1 | (v & m2) >> o2;
                    n & (n + 1) == 0
                })
            })
            .filter(|&v: &Item| {
                // filter out states that are completely sorted or states that have a smaller dual state
                (0..=N / 2).contains(&(v.count_ones() as usize)) && (v & (v + 1) != 0)
            })
            .map(|v| {
                // convert states to smaller states (this one is for situations like 010011 vs 001101)
                min(
                    v,
                    (((1 << N) - 1) - v).reverse_bits() >> (Item::BITS as usize - N),
                )
            })
            .collect::<HashSet<Item>>() //remove duplicates
            .into_iter()
            .for_each(|v| {
                // convert to state
                (0..N).rev().fold(v, |acc, i| {
                    base_state[i] = (base_state[i] << 1) | (acc & 1);
                    acc >> 1
                });
                num_bits += 1;
            });
        if num_bits > Item::BITS {
            panic!("Too big? {} > {} {:?}", num_bits, Item::BITS, sizes);
        } // currently, the largest this gets (for sizes=[2] and N=7) is 44

        let r = visit(&mut base_state, &mut tree, &mut state_to_idx); // build tree ("tree")

        double::<N, N2>(tree, r) as i64 // doubles (more like squares) tree
    }
}

/**
 * Finds all states that are descendants of the input state and maps them to numbers in topological order.
 * "tree" is an adjacency list on the numbers
 */
fn visit<const N: usize, const N2: usize>(
    state: &mut [Item; N],
    tree: &mut Vec<[usize; N2]>,
    state_to_idx: &mut HashMap<[Item; N], usize>,
) -> usize {
    if let Some(&idx) = state_to_idx.get(state) {
        idx
    } else {
        let mut l: Vec<Option<usize>> = vec![];
        for a in 0..N - 1 {
            let p = state[a];
            for b in a + 1..N {
                let q = state[b];
                if p & !q == 0 {
                    // self loop
                    l.push(None);
                } else {
                    state[a] = p & q;
                    state[b] = p | q;
                    l.push(Some(visit::<N, N2>(state, tree, state_to_idx)));
                    state[a] = p;
                    state[b] = q;
                }
            }
        }
        let v = state_to_idx.len();
        state_to_idx.insert(*state, v);
        tree.push(
            l.iter()
                .copied()
                .map(|x| x.unwrap_or(v))
                .collect::<Vec<usize>>()
                .try_into()
                .unwrap(),
        );
        v
    }
}

/**
 * Finds all descendant states from input_state
 */
fn visit_notree<const N: usize, const N2: usize>(
    state: &mut [Item; N],
    states: &mut HashSet<[Item; N]>,
) {
    if !states.contains(state) {
        for a in 0..N - 1 {
            let p = state[a];
            for b in a + 1..N {
                let q = state[b];
                if p & !q != 0 {
                    state[a] = p & q;
                    state[b] = p | q;
                    visit_notree::<N, N2>(state, states);
                    state[a] = p;
                    state[b] = q;
                }
            }
        }
        states.insert(*state);
    }
}

/**
 * Combines a graph with the reverse of the graph
 */
fn double<const N: usize, const N2: usize>(tree: Vec<[usize; N2]>, r: usize) -> usize {
    // does bfs on the graph, because visit returns in topological order, we can discard states with smaller rank, which saves memory
    let choices: Vec<(usize, usize)> = (0..N - 1).flat_map(|a| repeat(a).zip(a + 1..N)).collect();
    let choices_idx: HashMap<(usize, usize), usize> = choices
        .iter()
        .copied()
        .enumerate()
        .map(|(a, b)| (b, a))
        .collect();
    let rev: Vec<usize> = choices
        .iter()
        .copied()
        .map(|(a, b)| *choices_idx.get(&(N - 1 - b, N - 1 - a)).unwrap())
        .collect();
    let tree_rev: Vec<[usize; N2]> = tree
        .iter()
        .map(|t| {
            rev.iter()
                .map(|&v| t[v])
                .collect::<Vec<usize>>()
                .try_into()
                .unwrap()
        })
        .collect();
    let tl = tree.len();
    let mut queues: Vec<HashSet<usize>> = (0..2 * tl - 1).map(|_| HashSet::default()).collect();
    queues[2 * r].insert(r);
    let mut center = 0;
    let mut num_seen = 0;
    let mut rank = 2 * tl - 1;
    while !queues.is_empty() {
        rank -= 1;
        queues.pop().unwrap().drain().for_each(|a| {
            let b = rank - a;
            if a == b {
                center += 1;
            }
            num_seen += 1;
            for (&a1, &b1) in tree[a].iter().zip(tree_rev[b].iter()) {
                if a1 > b1 {
                    if a != b && (a != b1 || b != a1) {
                        queues[b1 + a1].insert(b1);
                    }
                } else if a != a1 || b != b1 {
                    queues[a1 + b1].insert(a1);
                }
            }
        });
    }
    2 * num_seen - center
}

// union-find with backtracking whatever
struct BacktrackArray<T> {
    data: Vec<T>,
    history: Vec<(usize, T)>,
    checkpoints: Vec<usize>,
}

impl<T: Copy> BacktrackArray<T> {
    pub fn new(data: Vec<T>) -> BacktrackArray<T> {
        BacktrackArray {
            data,
            history: vec![],
            checkpoints: vec![],
        }
    }
    pub fn rollback(&mut self) {
        self.history
            .drain(self.checkpoints.pop().unwrap_or(0)..)
            .rev()
            .for_each(|(idx, v)| self.data[idx] = v);
    }
    pub fn save(&mut self) {
        self.checkpoints.push(self.history.len());
    }
    pub fn set(&mut self, idx: usize, value: T) {
        self.history
            .push((idx, replace(&mut self.data[idx], value)));
    }
    pub fn get(&self, idx: usize) -> T {
        self.data[idx]
    }
}

impl<V: Copy> FromIterator<V> for BacktrackArray<V> {
    fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
        BacktrackArray::new(Vec::from_iter(iter))
    }
}

impl<V: Copy> From<Vec<V>> for BacktrackArray<V> {
    fn from(val: Vec<V>) -> Self {
        BacktrackArray::new(val)
    }
}

struct UnionFind {
    num_unions: BacktrackArray<usize>,
    parent: BacktrackArray<usize>,
    size: BacktrackArray<Item>,
    representatives: BacktrackArray<usize>,
    rep_ptrs: BacktrackArray<usize>,
}

impl UnionFind {
    pub fn new(n: usize) -> UnionFind {
        UnionFind {
            num_unions: vec![n].into(),
            parent: (0..n).collect(),
            size: repeat(1).take(n).collect(),
            representatives: (0..n).collect(),
            rep_ptrs: (0..n).collect(),
        }
    }
    pub fn save(&mut self) {
        self.num_unions.save();
        self.parent.save();
        self.size.save();
        self.representatives.save();
        self.rep_ptrs.save();
    }
    pub fn rollback(&mut self) {
        self.num_unions.rollback();
        self.parent.rollback();
        self.size.rollback();
        self.representatives.rollback();
        self.rep_ptrs.rollback();
    }
    pub fn get_sizes(&self) -> Vec<Item> {
        let n = self.num_unions.get(0);
        let mut v: Vec<Item> = self
            .representatives
            .data
            .iter()
            .take(n)
            .map(|&i| self.size.get(i))
            .filter(|&v| v > 1)
            .collect();
        v.sort_unstable();
        v
    }
    pub fn join(&mut self, i: usize, j: usize) {
        let mut i = self.find(i);
        let mut j = self.find(j);
        if i != j {
            let mut s_i = self.size.get(i);
            let mut s_j = self.size.get(j);
            if s_i < s_j {
                swap(&mut s_i, &mut s_j);
                swap(&mut i, &mut j);
            }
            self.parent.set(j, i);
            self.size.set(i, s_i + s_j);
            let n = self.num_unions.get(0) - 1;
            self.num_unions.set(0, n);
            let r = self.representatives.get(n);
            let r_idx = self.rep_ptrs.get(j);
            self.representatives.set(r_idx, r);
            self.rep_ptrs.set(r, r_idx);
        }
    }
    pub fn find(&mut self, i: usize) -> usize {
        let i1 = self.parent.get(i);
        if i1 == i {
            i
        } else {
            let i2 = self.find(i1);
            self.parent.set(i, i2);
            i2
        }
    }
}

```

**`Output:`**

```
n=1: 1
n=2: 2
  [2]: 1 = 1 * 1 (took 7.73µs)
n=3: 11
  [2]: 12 = 4 * 3 (took 9.617µs)
  [3]: -2 = 1 * -2 (took 783ns)
n=4: 261
  [2]: 366 = 61 * 6 (took 17.105µs)
  [2, 2]: -48 = 16 * -3 (took 3.853µs)
  [3]: -64 = 8 * -8 (took 2.727µs)
  [4]: 6 = 1 * 6 (took 1.088µs)
n=5: 43337
  [2]: 62480 = 6248 * 10 (took 440.742µs)
  [2, 2]: -14100 = 940 * -15 (took 76.582µs)
  [5]: -24 = 1 * -24 (took 1.818µs)
  [2, 3]: 1280 = 64 * 20 (took 9.063µs)
  [3]: -6780 = 339 * -20 (took 35.228µs)
  [4]: 480 = 16 * 30 (took 3.91µs)
n=6: 72462128
  [2, 3]: 1741440 = 14512 * 120 (took 3.553571ms)
  [4]: 169650 = 1885 * 90 (took 164.134µs)
  [2, 2, 2]: 831870 = 55458 * 15 (took 3.841656ms)
  [2]: 103912905 = 6927527 * 15 (took 553.271018ms)
  [2, 2]: -28154610 = 625658 * -45 (took 43.410737ms)
  [3, 3]: -20480 = 512 * -40 (took 67.739µs)
  [5]: -4608 = 32 * -144 (took 4.743µs)
  [6]: 120 = 1 * 120 (took 2.899µs)
  [3]: -5991120 = 149778 * -40 (took 33.794472ms)
  [2, 4]: -23040 = 256 * -90 (took 49.235µs)
n=7: 1530608978810
  [2, 2]: -701933448825 = 6685080465 * -105 (took 1777.016031993s)
  [7]: -720 = 1 * -720 (took 22.07µs)
  [2, 2, 3]: -684133800 = 3257780 * -210 (took 424.2515ms)
  [2, 3]: 26000250360 = 61905358 * 420 (took 7.892396883s)
  [4]: 754063170 = 3590777 * 210 (took 282.065867ms)
  [2, 2, 2]: 39011470995 = 371537819 * 105 (took 67.801355981s)
  [2]: 2244447515625 = 106878453125 * 21 (took 40712.141796623s)
  [3, 4]: 1720320 = 4096 * 420 (took 431.995µs)
  [2, 5]: 516096 = 1024 * 504 (took 93.822µs)
  [5]: -5283432 = 10483 * -504 (took 809.017µs)
  [6]: 53760 = 64 * 840 (took 13.258µs)
  [3]: -76668548810 = 1095264983 * -70 (took 215.344123884s)
  [3, 3]: -174011040 = 621468 * -280 (took 176.875932ms)
  [2, 4]: -141184890 = 224103 * -630 (took 93.090671ms)
Total time: 42782.049221178s

```

The correctness of this solution relies on two conjectures.

Before that, notation.

There are \\$N\\$ wires, \\$1\\$ through \\$N\\$ (the set of them is denoted by \\$\[N\]\\$).

\\$U\\$ is the set of all possible networks over the \\$N\\$ wires. \\$2^U\\$ is the powerset of \\$U\\$ (that is, the set of all subsets of \\$U\\$).

We'll let \\$G=\ (U, E)\\$ be a directed graph with vertices \\$U\\$ and an edge from \\$a\\$ to \\$b\\$ iff \\$b\\$ can be expressed by appending a single vertical wire to the right of \\$a\\$. We also denote by \\$G\_x\\$ (for network \\$x\\$) the set of networks reachable from \\$x\\$.

Define \\$S(A):\ 2^{\[N\]}\rightarrow U\\$ to mean the network that sorts the wires in \\$A\\$.

This is sort of an abuse of notation, but for \\$A\subseteq\[N\]\\$, we will write \\$G\_{S(A)}\\$ as \\$G\_A\\$

Define \\$F(\\{A\_1, ..., A\_k\\}): 2^{\left(2^{\[N\]}\right)}\rightarrow 2^U\\$ (where \\$A\_i \subseteq \[N\]\\$ and the \\$A\_i\\$ are pairwise disjoint) to mean \\$G\_{A\_1}\cap G\_{A\_2}\cap\ ...\cap\ G\_{A\_k}\\$.

The first conjecture is that \\$\\|F(\\{A\_1,...,A\_k\\})\\|=\\|F(\\{B\_1,...,B\_k\\})\\|\\$ if \\$\\|A\_i\\|=\\|B\_i\\|\\$ for \\$1\le i\le k\\$.

The second conjecture is that given \\$X\_1, X\_2, ..., X\_m \subseteq \[N\]\\$ (possibly overlapping), \\$G\_{X\_1}\cap G\_{X\_2}\cap ...\cap\ G\_{X\_m}=F({A\_1,A\_2,...,A\_k})\\$ for some pairwise disjoint \\$A\_i\\$ with \\$k\le m\\$.

To be more specific, if we make a graph with vertices in \\$\[N\]\\$ and an edge between vertices \\$a\\$ and \\$b\\$ if there is some \\$i\\$ for which \\$a,b \in X\_i\\$, then the \\$A\_j\\$ are the connected components of that graph.
> 6 votes

# Answer
# JavaScript (Node.js), \\$n=5\\$

Naive brute force.

```
for(let n = 1; n <= 5; n++) {
  console.log(n, solve(n));
}

function getPermutations(a) {
  let list = [];

  (function P(a, ...p) {
    if(a.length) {
      a.forEach((v, i) => P(a.filter(_ => i--), ...p, v));
    }
    else {
      list.push(p);
    }
  })(a);

  return list;
}

function solve(n) {
  let connector = [];

  for(let i = 0; i < n; i++) {
    for(let j = i + 1; j < n; j++) {
      connector.push([i, j]);
    }
  }

  let perm = getPermutations([...Array(n)].map((_, n) => n)),
      lookup = {};

  perm.forEach((p, i) => lookup[p] = i);

  let transform = connector.map(([ i, j ]) =>
    perm.map(([...p]) => {
      if(p[i] > p[j]) {
        [ p[i], p[j] ] = [ p[j], p[i] ];
      }
      return lookup[p];
    })
  );

  let set = new Set();

  (function search(list) {
    let key = JSON.stringify(list);

    if(!set.has(key)) {
      set.add(key);

      transform.forEach(t => {
        let update = 0;

        let newList = list.map(permNdx => {
          let newNdx = t[permNdx];
          update |= newNdx != permNdx;
          return newNdx;
        });
        if(update) {
          search(newList);
        }
      });
    }
  })(perm.map((_, n) => n));

  return set.size;
}

```

Try it online!
> 3 votes

# Answer
# Haskell, n≤4

```
import Data.List
import Data.List.Ordered
pairs[]=[]
pairs(i:k)=[[i,j]|j<-k]++pairs k
end(a:b:c)=last$end(b:c):[a|a==b]
b n=length$end$iterate behave[permutations[1..n]]where
 gate[i,j]z=last$z:[[z!!last(l:[i+j-l|l==i||l==j])|l<-[0..n-1]]|z!!i>z!!j]
 behave bs=nubSort$bs++[map(gate[i,j])b|b<-bs,[i,j]<-pairs[0..n-1]]

```

Try it online!
> 2 votes

# Answer
# Haskell, n≤5

```
import Data.Array
import Data.Bits
import Data.List
import qualified Data.Set as S

b n = S.size$visit 1 2 ini (S.singleton$hash ini)
 where
  ini = listArray(1,n)$map((sum::[Integer]->Integer).zipWith(*)(iterate(2*)1))$transpose$sequence$replicate n[0,1]

  hash = id

  visit i j s visited
   |i>n =visited
   |j>n =visit(i+1)(i+2)s visited
   |s!i.&.complement(s!j)>0&&S.notMember (hash newState) visited
        =visit i(j+1)s$visit 1 2 newState(S.insert (hash newState) visited)
   |0<1 =visit i(j+1)s visited
         where newState=s//[(i,s!i.&.s!j),(j,s!i.|.s!j)]

main=mapM_(print.b)[1..5]

```

Try it online!
> 0 votes

# Answer
# Scala, \\$n \leq 5\\$

Port of @Arnauld's Javascript answer in Scala.

Naive brute force.

Try it online!

```
import scala.collection.mutable.ListBuffer
import scala.annotation.tailrec

object Main extends App {
  for (n <- 1 to 5) {
    println(s"$n ${solve(n)}")
  }
  def factorial(n: BigInt): BigInt = {
    @tailrec
    def factorialHelper(n: BigInt, accumulator: BigInt): BigInt = {
      if (n <= 1) accumulator
      else factorialHelper(n - 1, n * accumulator)
    }

    factorialHelper(n, 1)
  }

  def solve(n: Int): Int = {
    var connector = (for {
      i <- 0 until n
      j <- i + 1 until n
    } yield (i, j)).toList

    val perm = (((0 until n).toList).permutations).toList
    val lookup = perm.zipWithIndex.toMap

    val transform = connector.map { case (i, j) =>
      perm.map { p =>
        val mutableP = p.toBuffer
        if (mutableP(i) > mutableP(j)) {
          val temp = mutableP(i)
          mutableP(i) = mutableP(j)
          mutableP(j) = temp
        }
        lookup(mutableP.toList)
      }
    }

    var set = Set[String]()

    def search(list: List[Int]): Unit = {
      val key = list.mkString(",")

      if (!set.contains(key)) {
        set += key

        transform.foreach { t =>
          var update = false

          val newList = list.map { permNdx =>
            val newNdx = t(permNdx)
            update |= (newNdx != permNdx)
            newNdx
          }
          if (update) {
            search(newList)
          }
        }
      }
    }

    search((0 until factorial(n).toInt).toList)
    set.size
  }
}

```
> 0 votes

---
Tags: math, sequence, permutations, fastest-code
---


# Question
Title: Add without addition (or any of the 4 basic arithmetic operators)
**Problem:**

Your goal is to add two input numbers without using any of the following math operators: `+,-,*,/`.

Additionally, you can't use any built-in functions that are designed to replace those math operators.

**Scoring:**

Smallest code (in number of bytes) wins.

**Update**

> Most of the programs i've seen either concatenate two arrays containing their numbers, or make `first number` of a character, append `second number` characters, then count them all.
>
> Shortest array counter: APL with 8 chars, by Tobia
>
> Shortest array concatenation: Golfscript with 4 chars, by Doorknob
>
> Shortest logarithmic solution: TI-89 Basic with 19 chars, by Quincunx
>
> Integration solution: Mathematica with 45 chars, by Michael Stern
>
> Coolest, in my opinion: bitwise operators in javascript, by dave

# Answer
# Smalltalk, 21 13

All of the following only work on positive integers. See the ***other Smalltalk*** answer for a serious one.

### version1

shifting to a large integer and asking it for its high bit index (bad, ST indexing is 1-based, so I need an additional right shift):

```
(((1<<a)<<b)>>1)highBit

```

### version2

similar, and even a bit shorter (due to Smalltalk precedence rules, and no right shift needed):

```
1<<a<<b log:2

```

### version3

another variation of the "collection-concatenating-asking size" theme,
given two numbers a and b,

```
((Array new:a),(Array new:b)) size

```

using Intervals as collection, we get a more memory friendly version ;-) in 21 chars:

```
((1to:a),(1to:b))size

```

not recommended for heavy number crunching, though.

### version4

For your amusement, if you want to trade time for memory, try:

```
Time secondsToRun:[
   Delay waitForSeconds:a.
   Delay waitForSeconds:b.
]

```

which is usually accurate enough (but no guarantee ;-)))

### version5

write to a file and ask it for its size

```
(
    [
        't' asFilename
            writingFileDo:[:s |
                a timesRepeat:[ 'x' printOn:s ].
                b timesRepeat:[ 'x' printOn:s ]];
            fileSize
    ] ensure:[
        't' asFilename delete
    ]
) print

```
> 3 votes

# Answer
## Javascript (25)

```
while(y)x^=y,y=(y&x^y)<<1

```

This adds two variables x and y, using only bitwise operations, and stores the result in x.

This works with negative numbers, too.
> 50 votes

# Answer
## C - 38 bytes

```
main(){return printf("%*c%*c",3,0,4);}

```

---

I do cheat a bit here, the OP said to not use any *math* operators.

The `*` in the `printf()` format means that the field width used to print the character is taken from an argument of `printf()`, in this case, 3 and 4. The return value of `printf()` is the number of characters printed. So it's printing one `' '` with a field-width of 3, and one with a field-width of 4, makes 3 + 4 characters in total.

The return value is the added numbers in the `printf()` call.
> 22 votes

# Answer
# Python - 49 bytes

Assuming input by placement in variables `x` and `y`.

```
from math import*
print log(log((e**e**x)**e**y))

```

This **61 byte** solution is a full program:

```
from math import*
print log(log((e**e**input())**e**input()))

```

Considering that you did not ban exponentiation, I had to post this. When you simplify the expression using properties of logarithms, you simply get `print input() + input()`.

This supports both negative and floating point numbers.

Note: I followed gnibbler's advice and split this answer into three. This is the Mathematica solution, and this is the TI-89 Basic solution.
> 19 votes

# Answer
## JavaScript \[25 bytes\]

```
~eval([1,~x,~y].join(''))

```
> 18 votes

# Answer
# GolfScript, ~~6~~ 4 characters/bytes

Input in the form of `10, 5` (=\> `15`).

```
~,+,

```

The `+` is array concatenation, not addition.

How it works is that `,` is used to create an array of the length that the number is (`0,1,...,n-2,n-1`). This is done for both numbers, then the arrays are concatenated. `,` is used again for a different purpose, to find the length of the resulting array.

Now, **here's the trick**. I really like this one because it abuses the input format. It *looks* like it's just inputting an array, but really, since the input is being executed as GolfScript code, the first `,` is already done for me! (The old 6-character version was `~,\,+,` with input format `10 5`, which I shaved 2 chars off by eliminating the `\,` (swap-array)).

**Old version (12)**:

Creates a function `f`.

```
{n*\n*+,}:f;

```

The `*` and `+` are string repetition and concatenation respectively, not arithmetic functions.

Explanation: `n` creates a one-character string (a newline). This is then repeated `a` times, then the same thing is done with `b`. The strings are concatenated, and then `,` is used for string length.
> 13 votes

# Answer
## Mathematica, 21 bytes

There are a number of ways to do this in Mathematica. One, use the Accumulate function and toss everything but the final number in the output. As with my other solution below, I assume the input numbers are in the variables `a` and `b`. 21 bytes.

```
Last@Accumulate@{a, b}

```

More fun, though it is 45 characters, use the numbers to define a line and integrate under it.

```
Integrate[Fit[{{0, a}, {2, b}}, {x, 1}, x], {x, 0, 2}]

```

As a bonus, both solutions work for all complex numbers, not just positive integers as seems to be the case for some other solutions here.
> 13 votes

# Answer
## C, 29 27 Bytes

Using pointer arithmetic:

```
f(x,y)char*x;{return&x[y];}

```

`x` is defined as a pointer, but the caller should pass an integer.

An anonymous user suggested the following - also 27 bytes, but parameters are integers:

```
f(x,y){return&x[(char*)y];}

```
> 10 votes

# Answer
# Brainf\*ck, 9 36

```
,>,[-<+>]

```

```
++[->,[->>[>]+[<]<]<]>>>[<[->+<]>>]<

```

This works without using simple addition; it goes through and lays a trail of 1's and then counts them up

Note: The `+` and `-` are merely single increments and nothing can be done in brainf\*ck without them. They aren't really addition/subtraction so I believe this still counts.
> 9 votes

# Answer
# J (6)

You didn't say we couldn't use the succ function:

```
>:@[&0

```

Usage:

```
   9>:@[&0(8)
17

```

It just does 9 repetitions of `>:` on 8.

The list concatenation approach works, too: `#@,&(#&0)`. And - I know it's against the rules - I can't let this answer go without the most J-ish solution: `*&.^` (multiplication under exponentiation).
> 7 votes

# Answer
## Postscript, 41

We define function with expression 41 bytes long as:

```
/a{0 moveto 0 rmoveto currentpoint pop}def

```

Then we call it e.g. as:

```
gs -q -dBATCH -c '/a{0 moveto 0 rmoveto currentpoint pop}def' -c '10 15 a ='

```

Which gives

```
25.0

```

It easily handles negatives and floats, unlike most competitors:-)
> 6 votes

# Answer
bash, 20 chars

```
(seq 10;seq 4)|wc -l

```
> 5 votes

# Answer
# Dash, 18 bytes

```
time -f%e sleep $@

```

Requires GNU time 1.7 or higher. Output is to STDERR.

Try it online!

Note that this will not work in **B**ash, since its builtin time command differs from GNU time.

At the cost of one additional byte, `\time` can be used instead of `time` to force Bash to use the external command.
> 4 votes

# Answer
# Smalltalk (now seriously), 123 118 105(\*)

Sorry for answering twice, but consider this a serious answer, while the other one was more like humor. The following is actually executed right at this very moment in all of our machines (in hardware, though). Strange that it came to no one else's mind...

By combining two half-adders, and doing all bits of the words in parallel, we get (inputs a,b; output in s) readable version:

```
  s := a bitXor: b.
  c := (a & b)<<1.

  [c ~= 0] whileTrue:[
     cn := s & c.
     s := s bitXor: c.
     c := cn<<1.
     c := c & 16rFFFFFFFF.
     s := s & 16rFFFFFFFF.
  ].
  s

```

The loop is for carry propagation. The masks ensure that signed integers are handled (without them, only unsigned numbers are possibe). They also define the word length, the above being for 32bit operation. If you prefer 68bit addition, change to 16rFFFFFFFFFFFFFFFFF.

golf version (123 chars) (avoids the long mask by reusing in m):

```
[:a :b||s c n m|s:=a bitXor:b.c:=(a&b)<<1.[c~=0]whileTrue:[n:=s&c.s:=s bitXor:c.c:=n<<1.c:=c&m:=16rFFFFFFFF.s:=s&m].s]

```

(\*) By using -1 instead of 16rFFFFFFFF, we can golf better, but the code no longer works for arbitrary precision numbers, only for machine-word sized smallIntegers (the representation for largeIntegers is not defined in the Ansi standard):

```
[:a :b||s c n|s:=a bitXor:b.c:=(a&b)<<1.[c~=0]whileTrue:[n:=s&c.s:=s bitXor:c.c:=n<<1.c:=c&-1.s:=s&-1].s]

```

this brings the code size down to 105 chars.
> 4 votes

# Answer
# APL, 8 and 12

Nothing new here, the array counting version:

```
{≢∊⍳¨⍺⍵}

```

and the log ○ log version:

```
{⍟⍟(**⍺)**⍵}

```

I just thought they looked cool in APL!

```
{≢     }       count
  ∊            all the elements in
   ⍳¨          the (two) sequences of naturals from 1 up to
     ⍺⍵        both arguments

```

```
{⍟⍟        }   the double logarithm of
   (**⍺)       the double exponential of ⍺
        *      raised to
         *⍵    the exponential of ⍵

```
> 4 votes

# Answer
# sed, 359 bytes (without the fancy formatting)

Sorry for the late answer, and probably the longest answer here by far. But I wanted to see if this is possible with sed:

```
                       s/([^ ]+) ([^ ]+)/\1:0::\2:/
                       :d /^([^:]+):\1::([^:]+):/tx
                       s/(:[^:]*)9([_:])/\1_\2/g;td
s/(:[^:]*)8(_*:)/\19\2/g;s/(:[^:]*)7(_*:)/\18\2/g;s/(:[^:]*)6(_*:)/\17\2/g
s/(:[^:]*)5(_*:)/\16\2/g;s/(:[^:]*)4(_*:)/\15\2/g;s/(:[^:]*)3(_*:)/\14\2/g
s/(:[^:]*)2(_*:)/\13\2/g;s/(:[^:]*)1(_*:)/\12\2/g;s/(:[^:]*)0(_*:)/\11\2/g
                       s/:(_+:)/:1\1/g; y/_/0/; # #
                       bd;  :x  s/.*::([^:]+):/\1/;
                       # # # # # # #  # # # # # # #

```

This is similar to https://codegolf.stackexchange.com/a/38087/11259, which simply increments numbers in a string. But instead it does the increment operations in a loop.

Input is taken from STDIN in the form "x y". That is first transformed to "x:0::y:". Then we increment all numbers that come after ":" characters, until we get "x:x::(x+y):". Then we finally return (x+y).

# Output

```
$ printf "%s\n" "0 0" "0 1" "1 0" "9 999" "999 9" "12345 67890" "123 1000000000000000000000"  | sed -rf add.sed
0
1
1
1008
1008
80235
1000000000000000000123
$

```

Note that this only works for the natural numbers. However (in theory at least) it works for arbitrarily large integers. Because we are doing x increment operations on y, ordering can make a big difference to speed: x \< y will be faster than x \> y.
> 4 votes

# Answer
## Javascript (67)

There is probably much better

```
a=Array;p=Number;r=prompt;alert(a(p(r())).concat(a(p(r()))).length)

```
> 3 votes

# Answer
Ruby, 18 chars

```
a.times{b=b.next}

```

And two more verbose variants, 29 chars

```
[*1..a].concat([*1..b]).size

```

Another version, 32 chars

```
(''.rjust(a)<<''.rjust(b)).size

```
> 3 votes

# Answer
# Ruby 39

```
f=->a,b{[*1..a].concat([*1..b]).length}

```
> 3 votes

# Answer
# C# - on the fly code generation

Yeah, there is actually an addition in there, but not the + operator and not even a framework function which does adding, instead we generate a method on the fly that does the adding.

```
public static int Add(int i1, int i2)
{
    var dm = new DynamicMethod("add", typeof(int), new[] { typeof(int), typeof(int) });
    var ilg = dm.GetILGenerator();
    ilg.Emit(OpCodes.Ldarg_0);
    ilg.Emit(OpCodes.Ldarg_1);
    ilg.Emit(OpCodes.Add);
    ilg.Emit(OpCodes.Ret);
    var del = (Func<int, int, int>)dm.CreateDelegate(typeof(Func<int, int, int>));
    return del(i1, i2);
}

```
> 3 votes

# Answer
# K, 2 bytes

```
#&

```

Usage example:

```
  #&7 212
219

```

Apply the "where" operator (monadic `&`) to the numbers in an input list (possibly taking liberty with the input format). This will produce a list containing the first number of zeroes followed by the second number of ones:

```
  &3 2
0 0 0 1 1

```

Normally this operator is used as a "gather" to produce a list of the indices of the nonzero elements of a boolean list, but the generalized form comes in handy occasionally.

Then simply take the count of that list (monadic `#`).

If my interpretation of the input requirements is unacceptable, the following slightly longer solution does the same trick:

```
{#&x,y}

```
> 3 votes

# Answer
# Python -- 22 characters

```
len(range(x)+range(y))

```
> 2 votes

# Answer
## TI-BASIC, 10

Adds `X` and `Y`

```
ln(ln(e^(e^(X))^e^(Y

```
> 2 votes

# Answer
## R 36

```
function(x,y)length(rep(1:2,c(x,y)))

```

where `rep` builds a vector of `x` ones followed by `y` twos.
> 2 votes

# Answer
Thanks to Michael Stern for teaching me Mathematica notation.

# Mathematica - ~~21~~ 20 bytes

```
Log@Log[(E^E^x)^E^y]

```

This uses the same approach as this solution, but it is in Mathematica to make it shorter. This works for negative and floating point numbers as well as integers in `x` and `y`.

Simplifying the expression using log rules yields `x+y`, but this is valid since it uses exponentiation, not one of the 4 basic operators.
> 2 votes

# Answer
# TI Basic 89 - 19 bytes

Run this in your TI-89 (Home screen or programming app):

```
ln(ln((e^e^x)^e^y))

```

This uses log rules to compute `x+y`, just like in this solution. As a bonus, it works for decimal and integer numbers. It works for all real numbers. If the logarithm rules are still valid with complex exponents, then this works for complex numbers too. However, my calculator spits out junk when I try to insert complex exponents.
> 2 votes

# Answer
# C# - string arithmetics

We convert both numbers to strings, do the addition with string cutting (with carry and everything, you know), then parse back to integer. Tested with i1, i2 in 0..200, works like a charm. Find an addition in this one!

```
public static int Add(int i1, int i2)
{
    var s1 = new string(i1.ToString().Reverse().ToArray());
    var s2 = new string(i2.ToString().Reverse().ToArray());
    var nums = "01234567890123456789";
    var c = '0';
    var ret = new StringBuilder();
    while (s1.Length > 0 || s2.Length > 0 || c != '0')
    {
        var c1 = s1.Length > 0 ? s1[0] : '0';
        var c2 = s2.Length > 0 ? s2[0] : '0';
        var s = nums;
        s = s.Substring(int.Parse(c1.ToString()));
        s = s.Substring(int.Parse(c2.ToString()));
        s = s.Substring(int.Parse(c.ToString()));
        ret.Append(s[0]);
        if (s1.Length > 0)
            s1 = s1.Substring(1);
        if (s2.Length > 0)
            s2 = s2.Substring(1);
        c = s.Length <= 10 ? '1' : '0';
    }
    return int.Parse(new string(ret.ToString().ToCharArray().Reverse().ToArray()));
}

```
> 2 votes

# Answer
# C (79)

```
void main(){int a,b;scanf("%d%d",&a,&b);printf("%d",printf("%*c%*c",a,0,b,0));}

```
> 2 votes

# Answer
**APL: 2**

```
1⊥

```

This converts the numbers from base 1, so (n\*1^1)+(m\*1^2) which is exactly n+m.

Can be tried on TryApl.org
> 2 votes

# Answer
# Pyth, 29 bytes

```
AQW!qG0=k.&GH=HxGH=k.<k1=Gk)H

```

Try it online!

My first submission here!

This compiles to:

```
assign('Q',eval_input())     # Q
assign('[G,H]',Q)            #A
while Pnot(equal(G,0)):      #  W!qG0
  assign('k',bitand(G,H))    #       =k.&GH
  assign('H',index(G,H))     #             =HxGH  (index in this case is XOR)
  assign('k',leftshift(k,1)) #                  =k.<k1
  assign('G',k)              #                        =Gk)
imp_print(H)                 #                            H

```
> 2 votes

# Answer
# PowerShell, 22 bytes

```
($args|%{,1*$_}).Count

```

Try it online!

Where `*` is an repeat element operator.
> 2 votes

# Answer
# Python 3, 38 bytes

```
f=lambda a,b:b and f(a^b,(a&b)<<1)or a

```

Try it online!

Uses bitwise operations recursively to work out the sum.
Works with *some* negative numbers (works as long as both are positive, or their sum is less than zero).
> 2 votes

# Answer
# Vyxal, ~~8~~ 6 bytes

```
ẋ??ẋJL

```

Try it Online!

I can't get base-1 to work.

-2 thx to lyxal
> 2 votes

# Answer
## Perl, 23

Since the question does not specify input types and formats, we assume that the input will be natural numbers in the unary number system.

```
chop($s=<>);print $s.<>

```

For example, if we are to sum 2 (in base 10) and 3 (in base 10), we input `11` and `111` and we get `11111`.
> 1 votes

# Answer
## Python 16 (Using Cheat)

```
print sum((a,b))

```

## Python 36 (Using Tricks)

```
print len("%%0%dd%%0%dd"%(5,7)%(0,0))

```
> 1 votes

# Answer
## Perl 28

```
print length('0'x$a.'0'x$b);

```
> 1 votes

# Answer
# Javascript - 43, 39, 13 and 4 characters

* The second number must be integer and non-negative.
* The first number can be negative or not an integer.

If the code must take the input and show output, here it is, in 43 characters:

```
a=prompt,x=a(),y=a();while(y--)x++;alert(x)

```

But if the code need not take input and output, and just a function that does the sum in needed, then we can do in 39 characters:

```
function s(x,y){while(y--)x++;return x}

```

But if you just need an instruction to add two variables `x` and `y` (and don't bother in destroying the original value of both), here it is in 13 characters:

```
while(y--)x++

```

And, as suggested by @Ismael Miguel (althought he was not exactly suggesting this), by really abusing the rules underspecification, we can note that only `+`, `-`, `*` and `/` operators were forbidden, but `+=` was not, so it is allowed (it is not a built-in function either, since it is not even a function). This way, we can express the instruction with just 4 characters (and it will always work with negatives and non-integers too for both values):

```
y+=x

```
> 1 votes

# Answer
**PHP**

This function works recursively for positive interger values for x and y.

```
function plus($x,$y) {
    return $x?ceil(plus(--$x,$y).".1"):$y;
}

```

The result of

```
echo plus(3,4);

```

is

```
7

```
> 1 votes

# Answer
# JavaScript \[32 bytes\]

```
Array(a).concat(Array(b)).length

```

This code adds two non-negative variables `a` and `b`. Test in any browser console.
> 1 votes

# Answer
# K, 11

```
{#,/!:'x,y}

```

Creates two vectors of length x and y (the two inputs), raze into a single list and then get the length.
> 1 votes

# Answer
### x86 machine code (32 bit): 3 bytes

here provided in hexadecimal form for ease of reading:

```
8d 04 18

```

(no, it's not `add eax,ebx`)
> 1 votes

# Answer
# Assembly (x86),

Taking a shot at this, not sure if it breaks rule 2 set by the question.

First, assume input 1 was loaded into %eax, and input 2 was loaded into %ecx

```
leal    (%eax, %ecx), %eax

```

EDIT: apparently the scale defaults to one, so I'll just take that off there.
> 1 votes

# Answer
# Maxima, 12

```
[a,b].[1,1];

```

I just made use of the dot operator to multiply matrices. In this case I get the inner product of the vectors (a,b) and (1,1) which is of course a+b.
> 1 votes

# Answer
**Excel - 31**

(presuming numbers in cells A1 and A2)

```
=LEN(REPT("X",A1)&REPT("X",A2))

```

The digital equivalent of counting on fingers. :)
> 1 votes

# Answer
# Prolog (SWI), 49 bytes

```
s(0,Y,Y).
s(X,Y,S):-succ(W,X),s(W,Y,R),succ(R,S).

```

Defines a predicate `s` that takes in the two numbers and unifies the result with its third argument (which is the standard way of "returning" a value in Prolog). On Linux, put the code in a file and pass it to `swipl -qs`; then enter queries at the prompt. Sample run:

```
dlosc@dlosc:~/golf$ swipl -qs addWithoutAdding.prolog
?- s(3,5,X).
X = 8 .

?- s(14,42,X).
X = 56 .

```

This actually seems like a fairly Prolog-ish way to do addition--the language does have arithmetic operations, but they've always felt bolted-on to me.

* If the first argument is `0`, unify the result with the second argument.
* Otherwise, let `W` be the predecessor of `X` (the `succ` predicate can go either direction), let `R` be the result of adding `W` and `Y`, and let `S` be the successor of `R`.

Because of how `succ` works, only nonnegative integers are supported.
> 1 votes

# Answer
# Python 3, 46 Bytes

```
def s(a,b):
 for i in range(b):a=-~a
 return a

```
> 1 votes

# Answer
# Ruby, ~~41~~ 20 bytes

```
->a,b{(-a...b).size}

```

Try it online!
> 1 votes

# Answer
# SmileBASIC, 55 bytes

```
INPUT A,B
SPSET.,0SPROT.,A
SPANIM.,12,1,B
WAIT?SPROT(0)

```

Doesn't use any mathematical or string functions

Explained:

```
INPUT A,B 'input
SPSET 0,0 'create sprite 0 with definition 0
SPROT 0,A 'set the angle of sprite 0 to A degrees
SPANIM 0,"R+",1,B 'rotate sprite 0 by B degrees relative to its current rotation
WAIT 'wait 1 frame so sprite can update
PRINT SPROT(0) 'output the angle of sprite 0

```
> 1 votes

# Answer
# Octave, ~~62 39~~ 37 bytes

```
@(a,b)fix(toc(tic,pause(a),pause(b)))

```

Unsigned integers only. Try it online!

-2 thanks to @MarcinKonowalczyk
> 1 votes

# Answer
# Jelly - 2,4 bytes

```
‘¡

```

If we're allowed to increment, then this increments x y times.

```
,RFL

```

`,R` create a nested list \[\[1,2,...,x\],\[1,2...,y\]\]. `FL` flatten the list and count the elements to get your number.
> 1 votes

# Answer
# PowerShell, 31 bytes

```
param($a,$b)(,1*$a+,1*$b).Count

```

Try it online!

The `+` and `*` are not arithmetic signs, but array concatenation and element repetition operators respectively. Big thanks to @mazzy for handling `0`.
> 1 votes

# Answer
# Keg `-hr`, 10 bytes

```
(2|(¿|0))!

```

Try it online!

Places a whole bunch of 0's onto the stack, and then prints the length of the stack. It then uses the `hr` flag to print the top of the stack raw.
> 1 votes

# Answer
# MarioLANG, 31 bytes

```
;
)
;
>[!(
"=#:
  -
) (
!+<
#="

```

Try it online!

*Note: `+` and `-` are INCREMENT and DECREMENT respectively, NOT addition and subtraction.*
> 1 votes

# Answer
**Python ~~48~~ 47 Bytes**

```
print(len({*range(x)}|{(j,)for j in range(y)})

```

Does not use `+`, even as concat. ~~41~~ 40 without `print`.

Removed space before for thanks to user8397947.
> 1 votes

# Answer
# Excel, 29 bytes

```
=LEN(CONCAT(REPT("x",A1:A2)))

```

Creates two strings of "x" repeated A1 and A2 times; concatenates the two strings and returns the length of the concatenated string. No built-in sum or sum-like functions.
> 1 votes

# Answer
# Javascript/JScript ~~78~~ 76 bytes:

I know this is a long answer, but here is another approach:

`function(a,b,c,d,l){c=[],d=[];c[l='length']=a+!!a,d[l]=b+!!b;return(c+d)[l]}`

How this works:

It creates 2 arrays with size `a+!!a` and `b+!!b`.

I know it has the `+` in there, but it is 'adding' a `Number` with a `Boolean` value.

Basically, it isn't an arithmetic operator anymore!

In the `return`, it will convert both arrays to string and concatenate them.

To run this, just wrap it in `()`, add `(n1,n2)` to the end and you will have the result.

**Notice**:

It CANNOT handle negative numbers, `NaN`, `Infinity` and other non-numeric inputs.
> 0 votes

# Answer
```
int Ad(int a,int b){while(b){int c=a & b;a=a ^ b;b=c<<1;}return a;}

```
> 0 votes

# Answer
**Objective-C - Base 1 & Base 10**

Actually a fun little project... converted everything to base-1 then just made it a string and took the length. In base one everything is zeros so 5 would be 00000 and 3 would be 000 so I just made two strings of the input in base-one, appended the strings, then printed the length of the string (which converts base 1 to base 10)

*Assuming positive integers for inputs* \*(*Note: calculation takes as many seconds as the sum of the integers inputted)*

---

Golf version (644 characters):

```
int i1=#;int i2=#;NSString *h;BOOL f1;BOOL f2;[NSTimer scheduledTimerWithTimeInterval:1 target:self selector:@selector(a1) userInfo:nil repeats:i1];[NSTimer scheduledTimerWithTimeInterval:1 target:self selector:@selector(a2) userInfo:nil repeats:i2];[NSTimer scheduledTimerWithTimeInterval:i1 target:self selector:@selector(s1) userInfo:nil repeats:0];[NSTimer scheduledTimerWithTimeInterval:i2 target:self selector:@selector(s2) userInfo:nil repeats:0];-(void)a1{h=[h stringByAppendingString:@"0"];}-(void)a1{h=[h stringByAppendingString:@"0"];}-(void)s1{f1=1;[self p];}-(void)s2{f2=1;[self p];}-(void)p{if((f1)&&(f2)){NSLog(@"%i",h.length);}}

```

---

Understandable version (1210 characters):

```
int input1 = #;//these can be any positive integer
int input2 = #;//these can be any positive integer
NSString *holder = @"";
BOOL finishedAddingFirst = NO;
BOOL finishedAddingSecond = NO;

[NSTimer scheduledTimerWithTimeInterval:1.0 target:self selector:@selector(addFirst) userInfo:nil repeats:input1];
[NSTimer scheduledTimerWithTimeInterval:1.0 target:self selector:@selector(addSecond) userInfo:nil repeats:input2];
[NSTimer scheduledTimerWithTimeInterval:input1 target:self selector:@selector(stopAddingFirst) userInfo:nil repeats:0];
[NSTimer scheduledTimerWithTimeInterval:input2 target:self selector:@selector(stopAddingSecond) userInfo:nil repeats:0];

-(void)addFirst {
    holder = [holder stringByAppendingString:@"0"];
}
-(void)addSecond {
    holder = [holder stringByAppendingString:@"0"];
}

-(void)stopAddingFirst {
    finishedAddingFirst = YES;
    [self printFinalAnswer];
}
-(void)stopAddingSecond {
    finishedAddingSecond = YES;
    [self printFinalAnswer];
}

-(void) printFinalAnswer {
    if ((finishedAddingFirst) && (finishedAddingSecond)) {
        NSLog(@"Base-One Sum: %@", holder);
        int output = (int)[holder length];
        NSLog(@"Base-Ten Sum: %i", output);
    }
}

```
> 0 votes

# Answer
# AutoHotkey - 54 Bytes

This accepts two command line parameters and outputs the result as an error message.

For each command line parameter, it runs a loop with that number and in each iteration, it concatenates one character to a string, then it outputs the length of the string.

It outputs it as an error message because the command to throw an error message is shorter than the commands that show a message box or send something to standard output.

```
a=a
loop,%1%
b.=a
loop,%2%
b.=a
throw % StrLen(b)
```
> 0 votes

# Answer
# F# - 36

```
(String('a',a)+String('b',b)).Length

```

The `+` here is not addition, but string concatenation.
> 0 votes

# Answer
## Batch - 71 bytes

For every iteration of a for loop, which will count to each inputted number, this outputs a `.` to a file named `f`. It then uses find to count the number of appearances of `.`.

```
@(for %%a in (%1 %2)do @for /l %%b in (1,1,%%a)do.)>f 2>e&@find/c"." f

```

-

```
h:\MyDocuments\uprof>test.bat 2 4

---------- F: 6

```

**Old Method - 157 bytes**

```
@setLocal enableDelayedExpansion&for /L %%a in (1,1,%1)do @set o=!o!.
@for /L %%b in (1,1,%2)do @set o=!o!.
@set/p"=%o%"<nul>f&for %%c in (f)do @echo %%~zc

```

This will take two values as input, count up to them, creating a variable that is the length of the two values added, then output that to a file (using `set /p` trick instead of echo to avoid a carriage return, which would add an extra two bytes), then gets the size of the file in bytes, which will be the sum of the two input values.

```
H:\uprof>test.bat 2 3
5

H:\uprof>test.bat 25 112
137

```
> 0 votes

# Answer
# Go \[43 bytes\]

```
len(append(make([]int,a),make([]int,b)...))

```
> 0 votes

# Answer
**Perl, 38 chars**

```
for(0..1){push @a,0for(1..<>)}print~~@a

```
> 0 votes

# Answer
**Ruby ~~49~~ 47**

```
a=gets;b="";gets.to_i.times{b+=".succ"};eval(a+b)

a=gets;b=gets;a.to_i.times{b+=".succ"};eval(b)

```
> 0 votes

# Answer
# C, 14 bytes

```
while(x--)y++;

```

Avoids `+`, `-`, `*` and `/`.

Note that `++` and `--` compile to machine code for INCR and DECR, so there is no addition or subtraction.
> 0 votes

# Answer
**JAVA, 79 bytes**

```
int Add(int x, int y){while (y != 0){int carry=x&y;x=x^y;y=carry<<1;}return x;}

```
> 0 votes

# Answer
# Python (36)

I think I'll switch to this for daily use , it's very efficient.

```
c=range(a);c.extend(range(b));len(c)

```
> 0 votes

# Answer
# Python, 118

This uses a binary approach. I didn't really try to golf it as much as I tried to make it interesting; I've already built binary addition in Minecraft in an 8x3x5 space per bit (!!!) and wanted to compare.

```
r,c="",0
if b>a:a,b=b,a
while a:
 a,b,e,d=a>>1,b>>1,a%2,b%2
 r=str(e^d^c)+r;c=(c&d)|(c&e)|(d&e)
r=int(str(c)+r,2)

```

**Thanks to @Sp3000** for shaving off about 50 chars and getting it to actually *work* in the chat ;D
> 0 votes

# Answer
# Python 3, 27 bytes

```
len("".join(["."*x,"."*y]))

```

where `x` is input 1 and `y` is input 2

(Okay, okay fine it's really 49 bytes including "true code":

```
len("".join(["."*int(input()),"."*int(input())]))

```

Note that `*` is for string duplication, although that *might* be a "standard operator"
> 0 votes

# Answer
## Dart - 30

```
s(a,b)=>a>0?s((a&b)<<1,a^b):b;

```

After writing this, I realized it was equivalent to the JavaScript solution already posted above - and because Dart has bignums, not just int32, it doesn't work for negative numbers. So, not a big win :(

Termination can be proven by seeing that the number of bits in a and b together reduces for each iteration until a becomes zero.
> 0 votes

# Answer
# Microscript, 9 bytes

A variant of the array concatenation solution (although this one uses a stack.)

`ics]ics]#`

Technically not a valid competing entry, however; as the language is too new.

Requires that both inputs be nonnegative.

---

A seven-byte version using a new command added shortly after I originally posted this:

`i$si$s#`
> 0 votes

# Answer
**X86 (2)**

`rep movb` two bytes `f3` `A4`,

adds ecx to esi (and to edi) result in esi but has side-effects if ds:esi != es:edi
> 0 votes

# Answer
# Python 2, Python 3, 41 bytes

```
i,j=input(),input()
while j>0:i=-~i;j=~-j

```

*If using the `- number` operator is allowed.*

---

# Python 2, Python 3, 40 bytes

```
i,j=input(),input()
while j>0:i=-~i;j-=1

```

*If using the `- number` and `literal -= number` operators is allowed.*

---

Works on positive integers. Takes `a` and `b` and prints `a`+`b`.
> 0 votes

# Answer
# Java, 85 bytes

```
import java.math.*;class a{BigInteger A(BigInteger b,BigInteger B){return b.add(B);}}

```

`BigInteger` isn't located in `java.lang`, `java.util`, `java.io` (is it even possible for a numeric type to be related to I/O?) or their subpackages, so its `add` method doesn't count as a language feature. Problem?
> 0 votes

# Answer
# PHP, ~~91~~ ~~78~~ 51 bytes

bit logic and shifting ... what else?

```
function p($x,$y){return$y?p($x^$y,($x&$y)<<1):$x;}

```

also works for negative integers
> 0 votes

# Answer
# Haskell, 25 bytes

```
n+m=length$[1..m]++[1..n]

```

We can no longer use the old `+`? No problem, we can just define a new one. This approach doesn't work with negative numbers, I have yet to figure out something else for them.
> 0 votes

# Answer
# R, 80 bytes

Went for a recursive function doing bit operations.

```
f=function(a,b){d=bitwXor(a,b);e=bitwShiftL(bitwAnd(a,b),1);ifelse(!e,d,f(d,e))}

```

Ungolfed:

```
f=function(a,b){
    d=bitwXor(a,b)            # xors a and b.(tells us bits that are 1 in end)
    f=bitwAnd(a,b)            # tells us which bits need to carry over 1
    e=bitwShiftL(e,1)         # carries those bits over
    if (e==0) d else f(d,e)   # if carried nothing, return xored bits.
}                             # otherwise, recursively call fn on xored and
                              # carried bits.

```

It would have been shorter -- but R really does not intend for bit operations.
> 0 votes

# Answer
# Turing Machine Code, 1184 bytes

A golfed version of a machine I posted to my googology wiki user blog a while ago. Supports signed ints. Try it online!

```
0 _ * l B
0 - * r AAA
0 * * r *
B 0 9 l *
B 9 8 r C
B 8 7 r C
B 7 6 r C
B 6 5 r C
B 5 4 r C
B 4 3 r C
B 3 2 r C
B 2 1 r C
B 1 0 r C
B _ * r AA
B * * * AA
C _ * r D
C * * r *
D _ * l E
D - * r 8
D * * r *
E 0 1 l F
E 1 2 l F
E 2 3 l F
E 3 4 l F
E 4 5 l F
E 5 6 l F
E 6 7 l F
E 7 8 l F
E 8 9 l F
E 9 0 l *
E _ * r S1
E M * r S1
F _ * l B
F * * l *
AA _ * r BB
AA * _ r *
BB M - * halt
BB * * * halt
S1 0 1 r S0
S0 0 0 r S0
S0 _ 0 * F
AAA 0 9 l *
AAA 9 8 r BBB
AAA 8 7 r BBB
AAA 7 6 r BBB
AAA 6 5 r BBB
AAA 5 4 r BBB
AAA 4 3 r BBB
AAA 3 2 r BBB
AAA 2 1 r BBB
AAA 1 0 r BBB
AAA _ * r BB
AAA * * * BB
BBB _ * r CCC
BBB * * r *
CCC _ * l DDD
CCC - * * ZZZ
CCC * * r *
DDD 9 8 l EEE
DDD 8 7 l EEE
DDD 7 6 l EEE
DDD 6 5 l EEE
DDD 5 4 l EEE
DDD 4 3 l EEE
DDD 3 2 l EEE
DDD 2 1 l EEE
DDD 1 0 l EEE
DDD 0 9 l *
DDD _ * r FFF
EEE _ * l *
EEE * * * AAA
FFF _ * * GGG
FFF * _ r *
GGG _ * l *
GGG * * * HHH
HHH 0 1 * halt
HHH 1 2 * halt
HHH 2 3 * halt
HHH 3 4 * halt
HHH 4 5 * halt
HHH 5 6 * halt
HHH 6 7 * halt
HHH 7 8 * halt
HHH 8 9 * halt
HHH 9 0 l *
8 _ * l 9
8 * * r *
9 9 8 l F
9 8 7 l F
9 7 6 l F
9 6 5 l F
9 5 4 l F
9 4 3 l F
9 3 2 l F
9 2 1 l F
9 1 0 l F
9 0 9 l *
9 * * * FFF
ZZZ * M r E

```
> 0 votes

# Answer
# Julia, 29 bytes

```
a$b=next(countfrom(a,b),a)[2]

```

Julia has iterators that can count up by an arbitrary amount at a time. It's usually used to create arithmetic sequences, but it can be definitely pressed into service as a ersatz adder.
> 0 votes

# Answer
# Java 8, 42 bytes

```
(x,y)->{for(int c;y!=0;c=x&y,x^=y,y=c<<1);return x;};

```

Try it online!
Based on https://www.geeksforgeeks.org/add-two-numbers-without-using-arithmetic-operators/
> 0 votes

# Answer
# Python 2 & 3, ~~39~~ 30 bytes (function)

```
lambda x,y:eval("-~"*x+str(y))

```

Try it online!

The `-`, `*` and `+` are negation, string repetition and string concatenation respectively, not mathematical operators.

## Explanation

`-~y` effectively increments `y`, so doing `-~-~...-~-~y` `x` times increments `y` `x` times.

---

These two are just for fun c:

# Python 2, ~~54~~  45 bytes (program)

```
x,y=input(),str(input());print eval("-~"*x+y)

```

# Python 3, ~~55~~ 46 bytes (program)

```
x,y=int(input()),input();print(eval("-~"*x+y))

```
> 0 votes

# Answer
## , ~~6~~ 5 bytes

```
1.MJk

```

## Explanation

```
  M   % Map the (implicit) input with ...
1.    % generate a list with this length
   J  % Join the array (NOT using the error-proof apply addition.)
    k % Find the length of the array

```
> 0 votes

# Answer
# APL (Dyalog Classic), 3 bytes

Good ol' base 1...

```
1⊥⎕

```

Try it online!

## Explanation

```
  ⎕ Take an input
1⊥  Convert from base-1

```

# APL (Dyalog Classic), 4 bytes

```
≢⎕/1

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 2 bytes

Nothing really new. All three are programs are already done in other languages, and simply ported to 05AB1E. Just like all other answers, it assumes positive integers are used.

Convert the (implicit) input-pair from base-1 to an integer:

Try it online.

Loop the first (implicit) input amount of times, and increment that second (implicit) input by 1 each iteration:

```
F>

```

Try it online.

(3 bytes) Convert both values in the (implicit) input-pair to a list in the range `[1,value]`; flatten the list; and take the total length:

```
L˜g

```

Try it online.
> 0 votes

# Answer
# Excel, 15

This should fit the bill, but it's boring.

```
=SUMPRODUCT(1:1

```

Inputs go anywhere in row 1.

Assuming just `SUM()`/`SUMIF()` is cheating. I'd say it's not, technically, as it's more capable than the `+` operator (for one thing `1+""` gives an error), but I'm guessing people won't like that.

## Other solutions

### Regular formula, 15

* `=SUBTOTAL(9,1:1`. This is shorter than the `AGGREGATE()` way.

### Matrix Multiplication, 19

* Inputs are A1, B2
* Set cell A2 to `1`
* `=MMULT(A1:B1,B1:B2`
> 0 votes

# Answer
# Octave, 36 bytes

```
@(a,b)size(conv2(eye(a),eye(b)),1)+1

```

Try it online!
> 0 votes

# Answer
## Pascal, 9 B

In Extended Pascal (ISO standard 10206) the built‑in `succ` and `pred` functions accept a second argument. To calculate the sum of two integral values write:

```
succ(x,y)

```

“But!” you will say:

> Additionally, you can't use any built-in functions that are designed to replace those math operators.

`succ` and `pred` are not designed to replace `+`/`-`. You can write

```
program sucks;
type
    enumeration = (a, b, c);
var
    x: enumeration value a;
begin
    x := succ(x, 2);
    { x is now c }
end.

```

but

```
    x := x + 2;

```

is illegal. Therefore, `succ` is not a substitute for `+`, neither is `pred` a replacement for . Moreover, `succ` and `pred` will refuse operating on `real` values.
> 0 votes

# Answer
# Japt, 2 bytes

Takes input as an array and simply converts it from base-1.

```
ì1

```

Try it
> 0 votes

# Answer
# C (gcc), 34 bytes

```
f(a,b){a=a&b?f(a^b,(a&b)<<1):a^b;}

```

Try it online!

A probably cheating 13-byte version (from @dave's Java submission):

```
f(a,b){a+=b;}

```

Try it online!
> 0 votes

---
Tags: code-golf
---