Write a program which will express an integer using only the number 2 (with the exception of 0 for exponents), using any mathematical operations to do so. Try to make it express the amount efficiently, rather than the easy and lazy way of 2+2+2... for evens and 2+2+2... -2^0 for odds.
Any language is acceptable.
For example: anus@prog ~ $ ./2 num=50
(((2^(2+2+2))-2^(2+2))+2)
anus@prog ~ $
if(argc < 2){
printf("please give a number!\n");
return 1;
}
printf("%s is %s\n", argv[1], powers(atoi(argv[1])));
return 0;
}
$ for i in $(jot 9 0); do ./power2 $i; done
0 is 0
1 is 2^(0)
2 is 0+ 2^(2^(0))
3 is 2^(0)+ 2^(2^(0))
4 is 0+ 0+ 2^(0+ 2^(2^(0)))
5 is 2^(0)+ 0+ 2^(0+ 2^(2^(0)))
6 is 0+ 2^(2^(0))+ 2^(0+ 2^(2^(0)))
7 is 2^(0)+ 2^(2^(0))+ 2^(0+ 2^(2^(0)))
8 is 0+ 0+ 0+ 2^(2^(0)+ 2^(2^(0)))
MODE LEAF = UNION(ADD, MUL, POW, NUM), TREE = REF LEAF;
MODE ADD = STRUCT(TREE al, ar), MUL = STRUCT(TREE ml, mr), POW = STRUCT(TREE pl, pr), NUM = BOOL;
LEAF one := TRUE, two := FALSE;
OP + = (TREE l, r)TREE: HEAP LEAF := ADD(l, r);
OP * = (TREE l, r)TREE: HEAP LEAF := MUL(l, r);
OP ^ = (TREE l, r)TREE: HEAP LEAF := POW(l, r);
OP L = (ADD t)TREE: al OF t, L = (MUL t)TREE: ml OF t, L = (POW t)TREE: pl OF t;
OP R = (ADD t)TREE: ar OF t, R = (MUL t)TREE: mr OF t, R = (POW t)TREE: pr OF t;
OP ? = (TREE t)INT: (t | (NUM n): (n | 1 | 0), (POW): 1, (MUL): 2, (ADD): 3);
PRIO ? = 8, OP ? = (TREE t, INT n)BOOL: ? t > n;
PRIO // = 7, OP // = (BOOL b, STRING s)STRING: (b | "(") + s + (b | ")");
OP // = (INT n, TREE t)STRING: t ? n // P t;
OP E = (TREE t)INT:
( t |
(ADD t): E L t + E R t,
(MUL t): E L t * E R t,
(POW t): E L t ^ E R t,
(NUM n): (n | 1 | 2)
);
OP P = (TREE t)STRING:
( t |
(ADD t): P L t + "+" + P R t,
(MUL t): 2 // L t + "*" + 2 // R t,
(POW t): 1 // L t + "^" + 0 // R t,
(NUM n): (n | "2^0" | "2")
);
PROC split = (INT n)TREE:
( INT res = ENTIER sqrt(n)
; n = 1
| one
|: n = 2
| two
|: NOT ODD n
| two * split(n % 2)
|: n = res^2
| split(res) ^ two
|: res = 1
| split(n - 1) + one
|: res = 2
| split(n - 4) + two ^ two
| split(n - res^2) + split(res) ^ two
);
FOR i FROM 1 TO 1500 DO print((i, " ", P split(i), new line)) OD
>>12
How not? How a binary representation not going to abide by the rules of the challenge?
Name:
Anonymous2013-03-18 18:50
It would actually be pretty neat if you could recursively define the powers of two in binary in order to implement this. Like to represent 8 you would need 2^3, so first you'd have to represent 3 which would be 2^1 + 2/2, etc.