Recursively define a "valid arithmetic expression":

  1. Any natural number is a valid arithmetic expression.
  2. If s is a valid arithmetic expression, then so is (-s).
  3. If p and q are valid arithmetic expressions, then so is (p+q).

In the above, a "natural number" is recursively defined as follows:

  1. 0 1 2 3 4 5 6 7 8 9 are natural numbers.
  2. If a natural number n is not 0, then n0 n1 n2 n3 n4 n5 n6 n7 n8 n9 are natural numbers.

Alternatively, via the regex /^(0|[1-9][0-9]*)$/

Examples of valid arithmetic expressions:


Examples of invalid arithmetic expressions:


The challenge is to print every valid arithmetic expression line by line, i.e. create a program that will output strings line by line with the constraint that every valid arithmetic expression is eventually printed, and that no invalid arithmetic expression is ever printed.

The valid arithmetic expressions can be printed more than once.

The challenge is to do so in as few bytes as possible, since this is .

Standard loopholes apply.

  • 2
    \$\begingroup\$ The output should be infinite, presumably? How can we demonstrate that every valid expression will be printed? \$\endgroup\$
    – Phil H
    Apr 16, 2018 at 12:46
  • 1
    \$\begingroup\$ @PhilH well you can challenge an answer that doesn't meet the criterion and the author of the answer would have to justify it... \$\endgroup\$
    – Leaky Nun
    Apr 16, 2018 at 12:49
  • 1
    \$\begingroup\$ @PhilH then the entry is invalid. \$\endgroup\$
    – Leaky Nun
    Apr 16, 2018 at 13:27
  • 1
    \$\begingroup\$ @PhilH That doesn't satisfy "every valid arithmetic expression is eventually printed", as (-0) is never printed. \$\endgroup\$
    Apr 16, 2018 at 13:40
  • 1
    \$\begingroup\$ @PhilH Seems that you misunderstood the rules? The validity criteria is "for all expression E, there exists a (finite) natural number N, such that the N'th line printed is E" Your example does not satisfy that. \$\endgroup\$
    Apr 16, 2018 at 15:19

3 Answers 3


Jelly, ... 33 bytes


Try it online!

Wow, writing a correct submission is hard.

Python pseudocode equivalent:

import itertools

# Jelly: ⁾()j
def wrap_in_parentheses(x):
 return str(x).join(['(',')'])
 # or equivalently, `return '('+str(x)+')'

# Jelly: p`j”+Ç$€;;”-;ÇƊ€;®‘©¤Ṅ€
register = 0
def expand_and_print(expressions):
 # Jelly: p`
 result = list(itertools.product(expressions, repeat=2))

 # Jelly: j”+Ç$€
 result = [wrap_in_parentheses('+'.join(expr)) for expr in result]

 # Jelly: ;

 # Jelly: ;”-;ÇƊ€
 result.extend([wrap_in_parentheses('-'+expr) for expr in expression])

 # Jelly: ;®‘©¤
 global register
 register += 1

 # Jelly: Ṅ€
 for expr in result:

 return result

# Jelly: WÇ1¿
expressions = ['0']
while 1:
 expressions = expand_and_print(expressions)

JavaScript ES6, 79 bytes

  • \$\begingroup\$ 1. Infinite large integer in variable, assumed; 2. Totally unrunnable in fact \$\endgroup\$
    – l4m2
    Apr 16, 2018 at 14:10

Python, 241 bytes

g=lambda n,s=0:s<6 and(l+r for x in(["\x13 8"]+list("I-x</"))[s]for a in range(n)for l in g(a,ord(x)%12)for r in g(n-a,ord(x)//12))or[]if n^1else s>7and["(-)+"[s-8]]or list("0123456789"[s==7:])*(s%6<2)
while i:print("\n".join(g(i)));i+=1

This isn't too short, but it's a table-driven approach that's semi-automatically generated from a CFG I wrote for this language. It's unreasonably fast (speed sacrificed for bytes) :)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.