Construct the natural numbers with sets

Question

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}} =
{ø, {ø, {ø}}}

Task

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 code-golf 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 -> {{}{{}{{}{{}}}}}

Answer 1

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.

Answer 2

Haskell, 37 bytes

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.

Answer 3

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.

Answer 4

Mathematica, 27 bytes

I've got two solutions at this byte count:

Nest[{{}}~Union~{#}&,{},#]&
Union//@Nest[{{},#}&,{},#]&

Answer 5

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
}

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

Röda, 37 bytes

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

Answer 11

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.

Answer 12

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

Answer 13

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!

Answer 14

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%

Answer 15

JavaScript 50 bytes

g=n=>n==0?"":"{{}"+g(n-1)+"}"
z=m=>m==0?"{}":g(m)

Answer 16

Pure Bash, 49 48 41 bytes

for((;k++<$1;)){ s={{}$s};};echo ${s-{\}}

Try it online!

Answer 17

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

Answer 18

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!

Answer 19

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 {}.

Answer 20

Java 7, 61 bytes

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

Try it online!

Answer 21

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%

Answer 22

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.

Answer 23

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.