# Construct the natural numbers with sets

This construction is a way of representing the Natural Numbers.

In this representation, 0 is defined as the empty set and for all other numbers, n is the union of {0} and {n-1}.

For example to construct 3 we can follow the algorithm:

3 =
{ø, 2} =
{ø, {ø, 1}} =
{ø, {ø, {ø}}}


As you may have guessed your task is to take in a natural number (including zero) and output its construction.

You may output as a either a string or as a set object if your language of choice supports such objects.

If you choose to output as a string you should represent a set with curly braces ({}). You may optionally represent the empty set as ø (otherwise it should be a set with no entries {}). You may also choose to add commas and whitespace between and after entries in the set.

Order is not important, however you may not have any repeated elements in the sets you output (e.g. {ø,ø})

This is so the goal is to have the fewest bytes

# Test cases

Here are some test cases with some example outputs.

0 -> {}
1 -> {{}}
2 -> {{}{{}}}
3 -> {{}{{}{{}}}}
4 -> {{}{{}{{}{{}}}}}

• @mbomb007 It doesn't matter whether the definition is "wrong" or not. It's still a fine challenge (and a different one). – Martin Ender Mar 6 '17 at 17:53
• Closely related. – Martin Ender Mar 6 '17 at 17:53
• @mbomb007 The test cases and the definition given in this challenge match up, and are different from the other challenge. If anything, the link could be improved, but I don't think the link is relevant to the challenge itself. – Martin Ender Mar 6 '17 at 17:54
• He called it the Von Neumann construction, though, and that's not what this challenge is. That's what the dup is. It follows that each natural number is equal to the set of all natural numbers less than it – mbomb007 Mar 6 '17 at 17:55
• Can we return a set-like object such as a list of lists from a function or print our language's representation to STDOUT? – Dennis Mar 6 '17 at 18:14

# Python, 28 bytes

lambda x:"{{}"*x+x*"}"or"{}"


Try it online!

This is a pretty bland solution to the problem. For numbers greater than zero you can get the representation with the string formula "{{}"*x+"}"*x. However this doesn't work for zero where this is the empty string. We can use this fact to short circuit an or to return the empty set.

I wanted to use python's builtin set objects to solve this problem but unfortunately:

TypeError: unhashable type: 'set'


You cannot put sets inside of sets in python.

• You can move the x to "{{}"*x+x*"}"or saving a byte – Rod Mar 6 '17 at 18:00
• f= could be removed. – Yytsi Mar 6 '17 at 19:17
• – BallpointBen Mar 6 '17 at 19:32
• There's frozenset but ain't nobody got bytes for that... – Esolanging Fruit Jul 15 '17 at 9:39

f 0="{}"
f n=([1..n]>>)=<<["{{}","}"]


Try it online!

Until 10 minutes ago an answer like this would have made no sense to me. All credits go to this tips answer.

Basically, we use >> as concat $replicate (but passing it a list of n elements instead of simply n), and =<< as concatMap, replicating then n times each of the strings in the list and concatenating the result into a single string. The 0 case is treated separately as it would return an empty string. • @Laikoni I tried something like that too, but you would need to special case f 1 too to make it work correctly – Leo Mar 7 '17 at 18:22 • Indeed. Then I like your version even more. – Laikoni Mar 7 '17 at 18:26 ## JavaScript, 28 bytes f=n=>n?--n?[[],f(n)]:[[]]:[]  Represents sets using arrays. 38-byte nonrecursive solution: n=>'{{}'.repeat(n)+'}'.repeat(n)||'{}'  Returns the example output strings. ## Mathematica, 27 bytes I've got two solutions at this byte count: Nest[{{}}~Union~{#}&,{},#]& Union//@Nest[{{},#}&,{},#]&  • Near miss at 32 bytes: #//.{1->{{}},x_/;x>1->{{},x-1}}&. Although I guess it messes up input 0 – Greg Martin Mar 6 '17 at 22:09 # Perl 6, 37 bytes {('{}','{{}}',{q:s'{{}$_}'}...*)[$_]}  Try it ## Expanded: { # bare block lambda with implicit parameter ｢$_｣

(
# generate a sequence

'{}',   # seed it with the first two values
'{{}}',

{   # bare block lambda with implicit parameter ｢$_｣ q # quote :scalar # allow scalar values '{{}$_}'  # embed the previous value ｢$_｣ in a new string } ... # keep using that code block to generate values * # never stop )[$_ ] # get the value at the given position in the sequence
}

• Are you missing a quote terminator : or is this something new to Perl 6? – CraigR8806 Mar 7 '17 at 19:36
• @CraigR8806 You can't use colons to delimit quoting constructs in Perl 6 because the are used for adverbs. (look at the expanded version) – Brad Gilbert b2gills Mar 7 '17 at 20:21

# 05AB1E, 6 5 bytes

### Code

ƒ)¯sÙ


Uses the CP-1252 encoding. Try it online! or Verify all test cases!.

### Explanation

ƒ       # For N in range(0, input + 1)..
)      #   Wrap the entire stack into an array
¯     #   Push []
s    #   Swap the two top elements
Ù   #   Uniquify the array

• F¯), does that not work? – Magic Octopus Urn Mar 14 '17 at 19:31
• @carusocomputing I don't think that works for n=0, since the output is empty (not an empty set). – Adnan Mar 14 '17 at 22:52

## Retina, 22 bytes

.+
$* \. {{} { ^$
{}


Try it online!

### Explanation

.+
$*  Convert the input to unary. \. {{}  Replace each unary digit with {{} and print the result without a trailing linefeed (\). {  Remove the opening {s, so that the remaining } are exactly those we still need to print to close all the sets. However, the above procedure fails for input 0, where we wouldn't print anything. So... ^$
{}


If the string is empty, replace it with the empty set.

• I was wondering how to repeat a string n times in Retina... – Neil Mar 6 '17 at 19:45

# Brain-Flak, 135 bytes

Includes +1 for -A

(({}())<{({}[()]<((((((()()()()()){}){}){}())()){}{})>)}{}({}[()()])>)(({})<{({}[()]<(((({}()())[()()])))>)}{}>[()]){(<{}{}{}>)}{}{}{}


Try it online!

(({}())<                 # Replace Input with input + 1 and save for later
{({}[()]<              # For input .. 0
(...)                # Push '}'
>)}{}                  # End for and pop counter
({}[()()])             # change the top '}' to '{'. This helps the next stage
# and removes the extra '}' that we got from incrementing input
>)                       # Put the input back on

(({})<                   # Save input
{({}[()]<              # For input .. 0
(((({}()())[()()]))) # Replace the top '{' with "{{{}"
>)}{}                  # end for and pop the counter
>[()])                   # Put down input - 1
{(<{}{}{}>)}             # If not 0, remove the extra "{{}"
{}{}{}                   # remove some more extras


# Röda, 37 bytes

f n{[[[],f(n-1)]]if[n>1]else[[[]]*n]}


# CJam, 11 bytes

Lri{]La|}*p


Prints a set-like object consisting of lists of lists. CJam prints empty lists as empty strings, since lists and strings are almost interchangeable.

Try it online!

Explanation

L            Push an empty array
ri          Read an integer from input
{    }*   Run this block that many times:
]          Wrap the entire stack in an array
La        Wrap an empty list in an array, i.e. [[]]
|       Set union of the two arrays
p  Print the result


# Old answer, 21 18 bytes

This was before it was confirmed that it was OK to print a nested list structure. Uses the string repetition algorithm.

Saved 3 bytes thanks to Martin Ender!

ri{{}}3/f*~_{{}}|


Explanation

ri                  Read an integer from input
{{}}             Push the string "{{}}"
3/           Split it into length-3 subtrings, gives ["{{}" "}"]
f*         Repeat each element of that array a number of times equal to the input
~_       Dump the array on the stack, duplicate the second element
{{}}|  Pop the top element, if it's false, push an empty block, which gets
printed as "{}". An input of 0 gives two empty strings on the
repetition step. Since empty strings are falsy, we can correct the
special case of 0 with this step.


# Jelly, 6 bytes

⁸,⁸Q$¡  This is a niladic link that reads an integer from STDIN and returns a ragged array. Try it online! ### How it works ⁸,⁸Q$¡  Niladic link.

⁸       Set the return value to [].
$Combine the three links to the left into a monadic chain. ,⁸ Pair the previous return value with the empty array. Q Unique; deduplicate the result. ¡ Read an integer n from STDIN and call the chain to the left n times.  # Python 3, 32 bytes f=lambda n:[[],n and f(n-1)][:n]  Not the shortest way, but I just had to do this with recursion. Try it online! # Cardinal, 51 50 bytes %:#>"{"#? v x ^?-"}{"< v <8/ ?< > 8\ v"}"< >?-?^  Try it online! ## Explanation %:# x  Receive input and send down and left from the #  >"{" ? v ^?-"}{"<  Print "{" one time then print "{}{" n-1 times if n>1 then print "{}" if n>0  # v <8/ ?< > 8\  Hold onto the input value until the first loop completes v"}"< >?-?^  Print "}" once then repeat n-1 times if n>1 # AHK, 55 bytes IfEqual,1,0 s={{}{}} Loop,%1% s={{ 2}{}}%s%{}} Send,%s%  It's not the shortest answer but I enjoyed this because the idiosyncrasies of AutoHotkey make this recursion method look super wrong. If and Loop statements assume the next line is the only thing included if brackets aren't used. Curly brackets are escape characters so you have to escape them with other curly brackets to use them as text. Also, the variable 1 is the first passed argument. When I read the code without knowing those tidbits, the logic looks like this: • If 1=0, then set s equal to the wrong answer • Loop and add a bunch of brackets to the beginning and a few to the end every time • Return by sending the resulting string to the current window Without all the bracket escape characters, it would look like this: IfEqual,1,0 s={} Loop,%1% s={{}%s%} Send,%s%  # JavaScript 50 bytes g=n=>n==0?"":"{{}"+g(n-1)+"}" z=m=>m==0?"{}":g(m)  • when a number is equal to 0 it is a falsy value for JavaScript. So you can remove the ==0 if you reverse your ternary expressions – fəˈnɛtɪk Mar 6 '17 at 19:05 # tinylisp, 52 bytes (d f(q((n)(i n(i(e n 1)(c()())(c()(c(f(s n 1))())))(  Try it online! (test harness). ### Explanation Note that (cons x (cons y nil)) is how you build a list containing x and y in Lisp. (d f Define f to be (q( a quoted list of two items (which acts as a function): (n) Arglist is a single argument n (i n Function body: if n is truthy (i.e. nonzero) (i(e n 1) then if n equals 1 (c()()) then cons nil to nil, resulting in (()) (c else (if n > 1) cons () nil to (c cons (f(s n 1)) (recursive call with n-1) to ()))) nil ())))) else (if n is 0) nil  # C (gcc), 52 bytes n(i){putchar(123);i>1&&n(0);i&&n(i-1);putchar(125);}  Taking advantage of some short circuit evaluation and recursion. Try it online! # Pure Bash, 4948 41 bytes for((;k++<$1;)){ s={{}$s};};echo${s-{\}}


Try it online!

# dc, 46 bytes

[[{}]]sx256?^dd3^8d^1-/8092541**r255/BF*+d0=xP


Try it online!

Input on stdin, output on stdout.

This works by computing a formula for the desired output as a base-256 number. The P command in dc is then used to print the base-256 number as a string.

Further explanation:

Let n be the input n. The dc program computes the sum of

A = floor(256^n / 255) * 125     (BF is interpreted by dc as 11*10+15 = 125)

and

B = floor((256^n)^3 / (8^8-1)) * 8092541 * (256^n).

For A:

Observe that 1 + 256 + 256^2 + ... + 256^(n-1) equals (256^n-1)/255, by the formula for a geometric progression, and this equals floor(256^n / 255). So this is the number consisting of n 1's in base 256.

When you multiply it by 125 to get A, the result is the number consisting of n 125's in base 256 (125 is a single digit in base 256, of course). It's probably better to write the digits in base 256 as hex numbers; 125 is hex 7D, so A is the base-256 number consisting of n 7D's in a row.

B is similar:

This time observe that 1 + 16777216 + 16777216^2 + ... + 16777216^(n-1) equals (16777216^n - 1)/16777215, and this equals floor(16777216^n/16777215).

Now, 256^3 = 16777216, and 8^8-1 = 16777215, so this is what we're computing as floor((256^n)^3 / (8^8-1)).

From the geometric series representation, this number in base 256 is 100100100...1001 with n of the digits being 1 and the rest of the digits being 0.

This is multiplied by 8092541, which is 7B7B7D in hexadecimal. In base 256, this is a three-digit number consisting of the digits 7B, 7B, and 7D (writing those digits in hex for convenience).

It follows that the product written in base 256 is a 3n-digit number consisting of the 3 digits 7B 7B 7D repeated n times.

This is multiplied by 256^n, resulting in a 4n-digit base-256 number, consisting of the 3 digits 7B 7B 7D repeated n times, followed by n 0's. That's B.

Adding A + B now yields the 4n-digit base-256 number consisting of the 3 digits 7B 7B 7D repeated n times, followed by n 7D's. Since 7B and 7D are the ASCII codes for { and }, respectively, this is the string consisting of n copies of {{} followed by n copies of }, which is exactly what we want for n > 0. The P command in dc prints a base-256 number as a string, just as we need.

Unfortunately, n=0 has to be treated as a special case. The computation above happens to yield a result of 0 for n=0; in that case, I've just hard-coded the printing of the string {}.

• That's a very interesting approach using the less known behavior of that printing command. Nicely done! An explanation of how this works would improve the answer. – seshoumara Mar 10 '17 at 8:16
• @seshoumara Thanks -- I've added a detailed explanation. – Mitchell Spector Mar 14 '17 at 17:27

# Java 7, 61 bytes

String p(int p){return p<1?"{}":p<2?"{{}}":"{{}"+p(p-1)+"}";}


Try it online!

## Batch, 88 bytes

@set s={}
@if %1 gtr 0 set s=&for /l %%i in (1,1,%1)do @call set s={{}%%s%%}
@echo %s%


# Brainf***, 99 bytes

>+>+>+>+<[>[-<+++++>]<-<]>--[->+>+<<]
>[-<+>]>++<,[[->>+>+<<<]>>[-<<<..>>.>]>[-<<.>>]+[]]<.>>.


(newline for aesthetics) Since it's brainf***, it takes input as ascii char codes (input "a" corresponds to 96)

# Braineasy, 60 bytes

Also, in my custom language (brainf** based, interpreter here):

#123#[->+>+<<]>++<,[[-<+<+>>]<[->>>..<.<<]<[->>>.<<<]!]>>.<.


You have to hardcode the program input into the interpreter because i'm lazy.

• Welcome to the site! Why is there a []? It seems like it could be removed – Wheat Wizard Mar 14 '17 at 16:19
• If you don't have that, it will output an extra {} at the end (it infinitely loops). – internet_user Mar 14 '17 at 16:51

# 05AB1E, 5 3 bytes

F¯)


Try it online!

This version is after he clarified that sets are okay.

F   # From 1 to input...
¯  # Push global array (default value is []).
) # Wrap stack to array.


Old version (that makes use of ø):

# 05AB1E, 5 4 bytes

FX¸)


Try it online!

Where 1 is equivalent to ø.

F    # From 1 to input...
X   # Push value in register X (default is 1).
¸  # Wrap pushed value into an array.
) # Wrap whole stack into an array.
# Implicit loop end (-1 byte).
# Implicit return.