# Enumerate the primes using only unary arithmetic

Write a program which prints the sequence of prime numbers. The shortest solution wins!

All numbers must have a unary representation (not just in the output, but throughout the entire program). This could be a string of 1s, a list of 1s, Peano-style objects, etc.

No particular output format is required, as long as numbers are recognizable. 111, [1, 1, 1], and S(S(S(0))) are all acceptable representations of 3, for example.

Examples of permissible operations:

• Appending or prepending a constant value to a string/list
• Deleting a constant number of elements from a string/list
• Comparing something with a constant, such as "11"
• Calling is_empty on a string/list

Examples of what's not allowed:

• Any operations on non-unary integers or floats, such as +, %, == or <
• Built-in functions which operate on multiple strings/lists, like + or ==

Sample programs

x⊡[1]=print x>>p x
x⊡s@(_:r)=s∇x where[]∇[]=p x;_∇[]=x⊡r;[]∇y=s∇y;(_:t)∇(_:y)=t∇y
p x=(1:x)⊡x
main=p[1]


The sieve was fun to implement, but simple exhaustive remainder checking is smaller. Strictly adheres to the terms. Unary numbers are represented as lists of 1.

First ten primes:

& runhaskell 13159-UnaryPrimes.hs | head
[1,1]
[1,1,1]
[1,1,1,1,1]
[1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]


No library functions are used at all in the computation. In fact, the only library function used is print, which you can't get away from since you need some library function to output.

## C, 220 chars

o(void**n){putchar(n?33:10);n&&o(*n);}
d(void**a,void**b,void**c){return a?d(*a,b,c?*c:*b):c;}
q(void**a,void**b){return a?q(*a,*b):b;}
p(a,s){return!q(&s,a)||d(a,&s,0)&&p(a,&s);}
z;
e(n){p(&n,&z)&&o(&n);e(&n);}
main(){e(&z);}


Explanations:

1. Numbers are represented as linked lists. NULL is 0, a pointer to N is N+1.
2. e enumerates numbers by calling itself with &n, i.e. with n+1. It uses p to test for primality and o to print.
3. p(a,s) tests if a is prime, checking divisors starting from s.
4. q(a,b) returns false if the numbers are equal. It only works for a<=b.
5. d(a,b,0) returns false if b divides a. The 3rd parameter is for recursion.
6. o(n) prints n exclamation marks, followed by a newline.
• I get a segfault in the first q call when dereferencing b, though I haven't figured out why - it looks fine to me. I'm running i686-apple-darwin11-gcc-4.2.1. – Daniel Lubarov Nov 11 '13 at 20:54
• @Daniel, I can see why it would fail on 64bit, but i686 means 32bit, right? Anyway, you can try adding void * to z and parameters in p and e (I saved precious characters by making them implicitly int, but they're actually pointers). – ugoren Nov 12 '13 at 10:19

## Perl 39 bytes

$_.=1while/^(11+)\1+$/||print$_||=11,$/


Interestingly enough, a well-known Perl primality test actually relies on unary logic.

• Heh, I thought of this but couldn't think of a good rule to prohibit it. My intention was to exclude all built-in functions besides a few, like (if we're using Lisp) cons and cdr, which would exclude regex matching. But +1 since I didn't make that clear. – Daniel Lubarov Nov 9 '13 at 6:59
• One might argue that the regex above uses 'variable length comparison', which seems to be at odds with specifically allowing constant comparison. By that logic, something like /11/ would be allowed, but /11+/ would not. – primo Nov 9 '13 at 7:12

# Mathematica, 81 chars

a=s@s@0;b={};While[1<2,Print@a;b~AppendTo~a;While[Or@@((a//.#:>0)==0&/@b),a=s@a]]


### Output:

s[s[0]]
s[s[s[0]]]
s[s[s[s[s[0]]]]]
s[s[s[s[s[s[s[0]]]]]]]
s[s[s[s[s[s[s[s[s[s[s[0]]]]]]]]]]]
......

### Explanation:

Numbers are represented as Peano numbers. For example, s[s[0]] means 2. I use suffix notation in my code. s@s@0 is just short for s[s[0]].

a//.#:>0 repeatedly replace the pattern # in a with 0. Both a and # in this expression are Peano numbers. In fact, it is equivalent to a mod #. For example, s[s[s[0]]]]]//.s[s[0]]:>0 returns s[0]. So (a//.#:>0)==0 if and only if a is divisible by #.

• I didn't want string functions like find-and-replace to be used, but my fault for not making that clear. A nice solution in any case. – Daniel Lubarov Nov 12 '13 at 21:34

## Action Script 3 | Many bytes

var endOfTheWorld:Object = new Object();
var timeToEndOfTheWorld:Number = 1;

while(!endOfTheWorld){
var busted:boolean = false;
timeToEndOfTheWorld++;

for (var k:Object in endOfTheWorld) {
if(timeToEndOfTheWorld % Number(k) == 0){
busted = true;
break;
}
}
if(busted){
continue;
}

timeToEndOfTheWorld[timeToEndOfTheWorld] = timeToEndOfTheWorld;
trace(timeToEndOfTheWorld);
}


P.S If you think I got wrong with the time to end of the world, then prove it ;)

• This is just a stack of ordinary numbers, with explicit arithmetic operations: ++, %, and ==. The aim was to use Paeno or unary numbers, and to avoid all arithmetic operations built into the language. – MtnViewMark Nov 12 '13 at 16:20