[Question]
  [
# Task
Write a program/function that when given a positive integer \$n\$ splits the numbers from \$1\$ to \$n\$ into two sets, so that no integers \$a, b, c\$, satisfying \$a^2 + b^2 = c^2\$ are all in the same set. For example, if \$3\$ and \$4\$ are in the first set, then \$5\$ must be in the second set since \$3^2+4^2=5^2\$.
Acceptable Output Formats:
* One of the sets
* Both the sets
* An array of length \$n\$ where the \$i\$-th element (counting from 1) is one of two different symbols (e.g. 0 and 1, a and b, etc.) which represent which set \$i\$ belongs to.The reverse of this is also fine
# Constraints
You can expect \$n\$ to be less than \$7825\$. This is because \$7824\$ is [proven](https://www.cs.utexas.edu/%7Emarijn/ptn/) to be the largest number to have solution (which also implies that all numbers less than 7825 have a solution).
# Scoring
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so shortest bytes wins.
# Sample Testcases
```
3 -> {1}
3 -> {}
5 -> {1, 2, 3}
5 -> {1, 2, 3}, {4, 5}
5 -> [0, 0, 0, 1, 1]
5 -> [1, 1, 0, 0, 1]
10 -> {1, 3, 6}
10 -> {1, 2, 3, 4, 6, 9}
41 -> {5, 6, 9, 15, 16, 20, 24, 35}
```
A checker to verify your output can be found [here](https://tio.run/##hZDNCsIwEITveYoRL4l/kIgXwavgYwRNNaVuQxIFn75uQ9WKBw8Lw@zMlyXhkS8trbtuigOFW8a@jVebt2IK4ql8TBnJ8QR7dKyCiza7kxCEHTxl6fuaVEqIpNnirCy2QtVGeM5giKxSaHyJJjMko6Wzk3oBwhxaKSyRNJM@KMxmMB9U0tx@13@2hs@4l7JtGvnaz1EXoUBtLjmOjJBF14P2FduTHWrFJPOf9PX8iGTGJBFi/yn9aZZOYLDquo3QME8 "Python 3 – Try It Online")
---
*Inspired by [The Problem with 7825 - Numberphile](https://www.youtube.com/watch?v=1gBwexpG0IY)*
  
[Answer]
# [J](http://jsoftware.com/), 37 bytes
Brute forces through the possible sets, outputs the bit mask.
```
((-&.#.+./@,)[(e.~+/~)/.*:@#\)^:_@#&1
```
[Try it online!](https://tio.run/##DcNBCoAgEAXQfaf4JJiTOmbLiUAIWrVqW9SqoA7h1a0H7y01NzdGQQOHDvL3jGld5mKM16zYckiONnNxtiFT4FaS2umQMykdC5XK4MbwV4iweJjQdx8 "J – Try It Online") (Also outputs list as numbers for easier comparison.)
### How it works
```
((-&.#.+./@,)[(e.~+/~)/.*:@#\)^:_@#&1
                                  #&1 convert to list of N 1's
(                            )^:_     do until list does not change
                        *:@#\         right: convert to 1,4,9…,N^2
             [                        left: the bit mask
                      /.              partition left based on right, for each set:
                  +/~                 make M*M addition table
               e.~                    any element of that in the same set?
       +./@,                          OR all answers: 1 on conflict, 0 if finished
  -&.#.                               list: from base 2, subtract that^, to base 2
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~132~~ 116 bytes
```
{1}.SatisfiabilityInstances[And@@(And[Or@@#,Nand@@#]&/@Map[x,Select[#~Tuples~3,{1,1,-1}.#^2==0&],{2}]),x/@#]&@*Range
```
[Try it online!](https://tio.run/##FYzLCsIwEAB/RQgUldU@9FpYjx58YL2FCGsaNdCG0kSohPbXY3qZw8BMS@6jWnJaUrj22jgefD5uq2jsS9NTN9r9jsY6MlJZfjA14jKSX3pEBmeaBRNJiifq@ACVapR0nE33b9coO@3A55DDJj7ZoyjLLBHgi1GsYEjnDtc3Mm8VcLHPRPgD "Wolfram Language (Mathematica) – Try It Online")
This uses Mathematica's SAT solver to label the integers 1 through the input as `True` and `False`.
* This is composed with `Range`, so what feeds into the main function is a list of the integers from 1 to the input.
* `Select[#~Tuples~3,{1,1,-1}.#^2==0&]` generates all the Pythagorean triples (multiple times actually, but that's okay).
* `And[Or@@#,Nand@@#]&` is true if at least one, but not all, of the elements of its input is true.
* `{1}.SatisfiabilityInstances[...,x/@#]` uses the SAT solver. Since `SatisfiabilityInstances` returns a list containing one solution, we use `{1}.` to get its first element.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 18 bytes
```
œc3²SHeƊ$Ƈ
ÇŒpÇÞḢQ
```
**[Try it online!](https://tio.run/##y0rNyan8///o5GTjQ5uCPVKPdakca@c63H50UsHh9sPzHu5Y9B/Eebhzxv//RiYA "Jelly – Try It Online")** (too inefficient for \$n>25\$ on TIO).
### How?
Strategy: Find all Pythagorean triples using \$[1,n]\$ then find a way to pick 1 element from each of them such that the resulting set contains no Pythagorean triples. That way we have a set which both contains no Pythagorean triple and blocks the other set from having any.
```
œc3²SHeƊ$Ƈ - Link 1, find all Pythagorean triples: list of integers OR number
œc3        - all combination of length 3 (given n uses [1..n])
         Ƈ - keep those for which:
        $  -   last two links as a monad:
   ²       -     square each of them
       Ɗ   -     last three links as a monad:
    S      -       sum (of the three squares)
     H     -       halved
      e    -       exists in (the squares)?
ÇŒpÇÞḢQ - Main Link: n
Ç       - call Link 1 as a monad -> all Pythagorean triples using [1,n]
 Œp     - Cartesian product -> all ways to pick one from each
    Þ   - sort those by:
   Ç    -   call Link 1 as a monad (empty lists are less than non-empty ones)
     Ḣ  - head
      Q - deduplicate (if n < 7825 this is a valid answer)
```
[Answer]
# JavaScript (ES6), ~~118~~ 117 bytes
Much slower for -1 byte.
```
f=(n,a=[],b=a)=>n?f(n-1,[n,...a],b)||f(n-1,a,[n,...b]):[a,b][E='every'](o=>o[E](x=>o[E](y=>o[E](k=>k*k-x*x+y*y))))&&b
```
[Try it online!](https://tio.run/##ZchBC8IgGIDhez9k06XSgi7BZ6f9CvHwuVzUho4thsL@uwl5id7LC88LN1z75Tm/ufN3m9IAxDEEpZkBpCDdbSCOt0w5JoTAzHTfv4QFjaZXhcxo1UFtN7vEWhMP0qtOk1Aey0eQYzPy0IRjbCLNVZVJvXern6yY/IMM5ELp4Vfa0x@dM6UP "JavaScript (Node.js) – Try It Online")
---
# JavaScript (ES6), ~~122 119~~ 118 bytes
Returns one of the sets as an array.
```
f=(n,a=[],b=a)=>[a,b][S='some'](o=>o[S](x=>o[S](y=>o[S](k=>k*k==x*x+y*y))))?0:n?f(n-1,[n,...a],b)||f(n-1,a,[n,...b]):b
```
[Try it online!](https://tio.run/##ZcyxDoIwFIXh3RehraUBowvJhYdgbDrcIhgt9Boxhia8eyWxi@Esf/IN54EfnLvX/fnOPV37GAdgXiJoIy0gh1qjtEa3kM009ZlhBDXp1rAlNaQ6qJ1wAItYjkEEvq0pKt8MzOel1F4qpXA75ev6I0xoDa9s7MjPNPZqpBsb2IXzw7@UxY5OezpvFL8 "JavaScript (Node.js) – Try It Online")
Solution found locally for \$n=41\$:
```
[ 5, 6, 9, 15, 16, 20, 24, 35 ]
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 14 bytes
Port of the 17 byte Jelly answer. (`Læ3ùʒDnO;tå}€н` is the same length)
```
Læ3ùʒnRćsOQ}€н
```
[Try it online!](https://tio.run/##ASEA3v9vc2FiaWX//0zDpjPDucqSblLEh3NPUX3igqzQvf//MjQ "05AB1E – Try It Online")
## Explanation
```
L              Length range
 æ             Powerset
  3ù           Pick truples (length-3 tuples)
    ʒ          Filter:
     n             Square all items
      R            Reverse the list
       ć           Head-extract (head on top)
        s          Swap
         O         Sum the remaining list
          Q}       Equal?
            €н Take head of each
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), ~~30~~ 26 bytes
```
œ|/L=³
Œc§œ&
ŒP²ÇẸƊÐḟŒcÑƇḢ
```
[Try it online!](https://tio.run/##y0rNyan8///o5Bp9H9tDm7mOTko@tPzoZDUgI@DQpsPtD3ftONZ1eMLDHfOBMocnHmt/uGPR////TQE "Jelly – Try It Online")
## How?
This does a more brute-force approach, filtering subsets of `[1..n]` based on whether they contain any Pythagorean triples. Then, it finds two triple-less subsets that have all `n` elements between them
```
œ|/L=³         # Test if a pair of sets unions to [1..n]
œ|/              # Set intersection  
   L             # Is the length
    =³           # equal to n?       
Œc§œ&          # Does a pair exist that sums to another?
Œc               # Compute all pairs of squares
  §              # Sum each
   œ&            # Set intersection with the set of squares (nonempty & truthy if a pair of squares sum to another square)
ŒP²ÇẸƊÐḟŒcÑƇḢ  # Main link
ŒP               # All subsets of 1..n
     ƊÐḟ         # Remove those where:
  ²                # of the squares,
   ÇẸ              # a pair of the squares exists that sum to another square
        Œc       # All pairs of these triple-less subsets
          ÑƇ     # Filter the pairs by whether they union to [1..n]
            Ḣ    # Head; get the first one
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 1664 bytes
works for all n (1 to 7824) instantly
```
IntegerDigits[Uncompress@"1:eJwllsmRHDkMRXWVGfIAKwGYoKtMGAfG/5veT0V0dHVlkiDwN/av//7/87t+/vjhPfem6tm+K6+yqFft5e/e9fXzeH6W62050307NdsTzYtIe/mMApOd/mJY5G/Yn9FdxidPe95uu/lGRNu2+U2n1c6zypfbWza7m80S99pKerF625V9oeNuzW1ywnt92jfZUcXbV94eHrael5Evyo1vHazcy3LPpOa7fXNlmW6d0xF0QXvLBHP+ikf2mKuDBp+1v94BBtvQlEDVdrdRfES8pIPsR1mmfAOUUXdeN2f8DvZzxNFc64c5VWJjPGie0rHls/TaOo4TmoGXtwx4Ry/rHzwDEtbwMwYbMDW2xhkvg18BoPva04zBJqAwisL+AbcLa34OLdSBUGpa1VlDJp3G2wqtA+zTgmz4sTh7YxCVN1RCFYy7x3z5ivIghVhm/s3vBxM6F1S0KJO5k8GpRiuMbRCaRT1eF1NoRSGflb7OUYgJJSYNOoRzyIDMLEaCQgAxNFWsRkq5zPxGDYZLewakSRvgCRNrcJ92EFzis1FSIhnoZ8pYZ3HeA4TJfUwq+RiyB478gA7UA7QgUxl05yvcKDHgOonYOcLfciywwgKLC+ICNSWqFNaLYFEzQ6ANmsEBJ96ZhnEwE5prPX06RBYD20FJPVk6EyrYfOoK3dnniG+kCBBbCY1Ra/FGBfDtMzB/vEItgKMRAYiHqDREkghhA5KiC6jFTp8nGAycUCi+dg6B4ZdSGxMVXb8bGWLYOgQDzFe0fG3wztNPk/edjBV6v5m1uOgvMKCxOwBWtr5OoAYuFmUyTAkdkiNoytgrx32iBDDEjzsfsdQJltIFFnaAQztkUigpUtSiG+Y98Jz56Ejgv0eXhBAiwhtKBVYjqpJdqB8KHPQN60QCRj+gnFWejUKLrUQAuHIcwmUh/sQAYIqxlBAGcHCF2S+pCdPsY/hHMAZKEVBCn9AUeyB0wEcZZClbIEmXLkyZ5YMM5dSobQkJQbjyQoYAE4J05LbAcwpAlJQu8VIKW4M4PsccBJFi4TxOPiyRKUJMcc7LIO1JVgWiwpHoIWA4oTj0Ri2yAqsiQZS6Cm9QIXpLtwCGIU0lb3TzkcyM0iEvsA5mHPLi5OPH/SBx4zj6IeMfwxnC/HQ68ouCiGBS42nw6ErC/eIaJYEQoHIWgIFRSo7QA2ZomqcKfSEKyDdKcsUXPXAlYNf40HqfbCBMzgKVc5pFvs6nxodtJ9xV9+kOITFIVFAfdYMAWrfQY03joC+08pt2kZgpz584m4EWhA4x/I0WHNjo7xBP4ifFGfgf3VIIueRHe0jyaL+rkQhEk6xGhpXi8LlBu4YBYYyAnaAHw1MeBRUXMLoAfK5S3IfisZWE+7jYKN4EGG2SlkBlKICHzEOaLxFKWuMImiBA0bLMAi3IBR/wUNnByvhCD1uTcsJLN04oGBu9SaKGlJFAKs24krEs9NKZ7h0oxTkMTAYUyjn91xAKWMCFv8CZyock+EGWMjCutNANrdZOqY0Z0T66Yr2oJswJ+FBaKHORK8sOAbUuruSWkR5gRbZoLuYPer7CORkDULwUjQgHD++RLKBOR0p3EkvGh0VG4pbCOyt+QBs99V9DtuSl",2][[;;#]]&
```
[Try it online!](https://tio.run/##DdFXDqRWAkDRrYw80vxgCYoCCmxZ8nvknAooaPUHOYciw@Z7egf36PbxWuV9vNZp/Kv855c8rHmZz1xd1uvywxvSsZ/mfFn@/ePxV64cXbf0jsS1uvMJfLGQgXqI4aiuuggKESX3/I35WCb5XVtzh4HGO4q@UPq1IujeVFaR99TaIyqFXF@hWMkczZnic@cSFVA4RmJP7GVky/sOVzlHex1MZob2SkiKaDgwQnbWmZUz5LahnegYG454@PBIqfuaiiS441dPYy7DTGo@CxRO@syYG9sdPK5jWBm8KSIv/SQ@Q@TSHOcdye/X@Nil@E6vp2ZNZvwqPkbXB1SGnQJmf3YNShZStwXeqxsHJ@SxMwSE6253POdnc@YUvEtPsrU4j74vgOl5nyw38ILm9ug@DSGliJT0A6WxxDrHZqlb0HdsjsS7H8XPepyEc6GzdB8cvyaHfoSJzgX4WbV7@aDhaO0xRtxQ@YKjXjQEJKkWPwlTy1zoiVP88DtOmZ4ifnxXgNzvsr@J5V29wpP1jYfDCuH1Op83We9yWflVjy7PHZ46JTxcTFVMsqXFyak3PXHY2Hk/cuFhjI4rFl3yMr2wVBQ3NMzRuS@Z0zU@Zu0S/CYFi9N@yds6RS6MtPyIW9fZS9Yx5lRhcF646@UhuHI1jBE9hdFTygHxVgrv@CJOfUHiRZfg5YGXXXpnh5HXnqqcVJrjEJqpVqT1dRylqrGIzBpu8BWMWAsF/rYpYPQLDxWGiqqBP3hymq0PRjkw5HBMUCy/pfhrDgtzVJ/ZMNQi0rIQJmz4cGJUEGHBrfoN0Z2X11LVHRDW0pdz@LasKkCqNUs1wnuiBxFcqcfWSFZSkIgyVzx1/5PQiRhooVna3C3kWCE@j3s1rBbNswb61E72j80sd11lT/OAwTqT5gjCTei96w3arK2N8VrL@XziNeQ4vrmXYslspVtlQRhiYN9r69Xl5K3u7@yQoZWbpPim3LH8U0FQH9WqQj9svpOSfSGtSpZtUJjNOg1SDkKQN56qzZ4NNklOj96r0MUGofw9OwjEVGIF3EUmNrOWEK0kHUQq70N2YICXXxA7@DSK2C6R@f6jtVdEhrpOZu6Y2K1iJ81ljyHgCQUjtQSkxwQ6xd5oX1YDQiesJU2hItTE@zSt@nJUT9HT9KXJ5kPxy6A@JmmUA0CM7wZzavwC36W2I5die8aWP5O2Hqwoe1iXPN93m146VvP7AshesrSaNC0JdeFJ3A0l53pxnAOLSjZFjxtbi9Al8OGg@JlFczlWQt4eJTkoZcFxx5cN8Gjsv6lauLx6cZmaLt7H@oAuNAoCk75FwkL9LlU/JSdhX6jhHLNVYU6fQVpTfguyL4AiC3UQzIUdYs9mZBGMnla8jcrpJmmiJ/igAsSJylggGc34OqFF1IUgFmXx9GV5yx0px5or1pC5tSu@pU6xmj41rXVwI0IYhhf4vV06HnoOHe@jayMoVNJ9ykW9RAGPvJpQNQheFHG3a2Gnyqx082asnYIabLrc1xBgiaaD@ilDBz08Y4DXXrHcY3uni6IZGDGKcGPcWBU7RQDqghPtzC@MoUavChvPd6u/QehdzcA8TqAGOivsNBtdY9oivBjoDbutBjDmLDK/IRZhb4oKZ3xUlkNBBBirkumo9GKCxNvmzQ1ahyydJBq1LbTy@cWaTst52uE1dilxCOJoKjQdbHry7S5WmC8SU8Ka14rYcGEYn@HWze3@@BP/@ePH33//9@fP//2y5npY//Nv@eNF48TPX7/@Dw "Wolfram Language (Mathematica) – Try It Online")
[Answer]
# [R](https://www.r-project.org/), ~~99~~ 95 bytes
```
n=scan():1
f=function(j)outer(a<-n[j]^2,a,`+`)%in%a
while(any(f(i<-sample(!0:1,n,T)),f(!i)))0 
i
```
[Try it online!](https://tio.run/##DcdNCoNADAbQvbdwISQ0glO6cvQW3YliEIdG9FP8ofT0U9/u7TGiPgYFcel8qMOF4bQVNPF6neNOWuVoprZ7ikr/6DkzZOq/H5tHUvwokFX5oct2Py1KJ5A3swRKjZkLb/HlkgSNtfEP "R – Try It Online")
Outputs a vector of `TRUE` and `FALSE` representing in reverse order which set each integer belongs to. (The footer of the TIO transforms this into a list of integers in the first set.)
Works by random sampling: repeatedly draw a random subset of `1:n` until neither the subset nor its complement contain any Pythagorean triples (checked by the function `f`).
It will finish in finite time for any input <7825, but will in expectation take a very long time for largeish `n`. TIO starts timing out around `n=90`.
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 74 bytes
```
ＮθＦθＦιＦκＦ⁼Ｘ⊕ι²ΣＸ⊕⟦κλ⟧²⊞υ⊕⟦ικλ⟧≔⁰ηＷ¬ⅉ«≔Ｅυ§κ÷ηＸ³λζ≦⊕η≔Ｘζ²ε¿¬⊙ε⊙ε№ε⁺κμＩ⁻Ｅθ⊕κζ
```
[Try it online!](https://tio.run/##bU87a8MwEJ6TX3HjGVToa@tk0g4eEgydSumg2kokLEuxHkmb0t@uniIXGqhAnMT3vE5y11muU2rMPoZNHN@Fw6l6WG6tA3rAeap5DvN8miLXHlt7JHZjOidGYYLoicjglu5zHP9BXwcG@u1MoQNt9BIjgwuKYlBY1KH2Xu0MXjOQ9DtKpQXgxgZ8waz/Wi5mxprvs1EdGtOLDxyyZ3hUB9ULlAxKkzuyzbkMTuS2IM2s/pNfkn5ti@5UVhIZUNtSoDafKCiwjJWNJuRHq6PP6WNVlQ2dImDFfcC1MoTlotPlxkNpRO7fKd3fpKuD/gE "Charcoal – Try It Online") Well, for `n<50`, otherwise it gets too slow. Link is to verbose version of code. Based on @JonathanAllen's answer. Explanation:
```
Ｎθ
```
Input `n`.
```
ＦθＦιＦκ
```
Loop through all potential Pythagorean triples.
```
Ｆ⁼Ｘ⊕ι²ΣＸ⊕⟦κλ⟧²
```
If this is indeed a triple,
```
⊞υ⊕⟦ικλ⟧
```
then push it to the empty list.
```
≔⁰η
```
Start iterating through the ways of picking one element of each triple.
```
Ｗ¬ⅉ«
```
Repeat until output has been generated.
```
≔Ｅυ§κ÷ηＸ³λζ
```
Pick one element from each triple.
```
≦⊕η
```
Increment the loop counter.
```
≔Ｘζ²ε
```
Square the elements.
```
¿¬⊙ε⊙ε№ε⁺κμ
```
Check for Pythagorean triples.
```
Ｉ⁻Ｅθ⊕κζ
```
If none, then output one of the sets.
]