Problem of the Month (April 2004)

Strobogrammatic numbers (SNs) are numbers that are the same when viewed upside down: 0, 1, 8, 11, 69, 88, 96, .... These are sequence 000787 at the Encyclopedia of Integer Sequences. This month we consider Strobogrammatic Expressions (SEs): mathematical expressions that describe the same number when viewed upside down. Only the digits 0, 1, 6, 8, and 9, addition, subtraction, multiplication, division, exponentiation, and parentheses are allowed. I was also convinced to allow subscripts so 6₉ means "6 in base 9". Here are some simple examples: 91–8/8–16, 68+68+61, and 9^(9–6), which describe the numbers 74, 197, and 729 respectively.

Every number can be represented by a SE of the form 1+1+1+.... What are the shortest (in terms of the minimum number of symbols used) SEs that represent the integers from 1 to 100? We are particularly interested in shortest SEs that do not use any SNs.

ANSWERS

Joseph DeVincentis and Richard Sabey sent SEs for 1-100, many of which beat my best.

Jeremy Galvagni found lots of SEs involving exponents.

Philippe Fondanaiche sent alternatives to some shortest expressions.

Gavin Theobald improved some expressions.

Shortest Known Strobogrammatic Expressions

Number	Symbols	Shortest SE
1	1	1
2	3	1+1
3	3	9–6
4	5	9–6+1
5	5	6¹–1⁹
6	2	6₉ (GT)
7	4	6₉+1 (GT)
8	1	8
9	3	8+1 9^1⁶
10	5	9¹+1⁶ 8+1+1 9^1⁶+1
11	2	11
12	4	11+1 11₁₁ (GT)
13	6	11+1+1
14	4	6₉+8 (GT)
15	3	6+9
16	3	8+8
17	5	8+8+1 8+9^1⁶ 6₉+11 (GT)
18	5	18^1⁸¹
19	4	11+8
20	6	11+8+1
21	5	89–68
22	5	11+11
23	5	6+8+9
24	5	8+8+8
25	7	8+8+8+1 8+9^1⁶+8 6₉+8+11 (GT) 99–8–66 (GT)
26	6	6+11+9
27	6	8+11+8
28	8	8+11+1+8 8+11+9^1⁶ 6₉+11+11 (GT)
29	7	89–68+8
30	7	6+6+9+9 11+8+11 191–161 696–666 (GT)
31	7	6+8+8+9
32	7	8+8+8+8 99–1–66
33	5	99–66
34	7	99–66+1 61–8–19 (JD)
35	8	8+8+8+11

Number	Symbols	Shortest SE
36	5	6^1+1⁹ (GT) 6₉×6₉ (GT)
37	7	6^1+1⁹+1 (GT) 6₉×6₉+1 (GT)
38	9	6+6+8+9+9 11+8+8+11 101+18–81 (JD)
39	8	99–66+6₉ (GT)
40	8	8(6¹–1⁹)
41	7	61–1–19
42	5	61–19
43	7	61–19+1
44	7	6^1+1⁹+8 (GT) 6₉×6₉+8 (GT)
45	7	9×9–6×6
46	6	6/9×69 (JD)
47	8	6/9×69+1 (JD) 6₉×6₉+11 (GT)
48	4	6₉×8 (GT)
49	6	6₉×8+1 (GT)
50	7	61–19+8
51	7	6×9+6–9
52	8	81–11–18
53	7	61¹–8₉₉ (GT)
54	3	6×9
55	5	6×9+1
56	6	6₉×8+8 (GT)
57	7	6×9+9–6 61₈+8₁₉ (GT)
58	8	69+6–8–9 (GT)
59	7	6₉×8+11 (GT)
60	6	6₉+6×9 (GT)
61	5	61^1¹⁹
62	5	6×9+8
63	5	81–18
64	3	8×8
65	5	8×8+1
66	5	66^1⁹⁹ 6₉×11 (GT)
67	7	68¹–1⁸⁹ 66¹+1⁹⁹ 66^1⁹⁹+1 8×8+9–6 91–8–16 (JD) 6₉×11+1 (GT)
68	5	68^1⁸⁹
69	2	69
70	4	69+1 19₆₁ (GT)
71	6	1+69+1

Number	Symbols	Shortest SE
72	5	8×8+8 (RS)
73	7	8×8+8+1 (RS)
74	7	91–1–16 66^1⁹⁹+8 111×6/9 (GT) 6₉×11+8 (GT)
75	5	91–16 6₉+69 (GT)
76	7	91–16+1 68^1⁸⁹+8 6₉+19₆₁ (GT)
77	4	69+8
78	6	69+8+1 69+9^1⁶
79	7	9+8×8+6 (GT) 81₉+6₁₈ (GT)
80	5	69+11 61+19 (PF)
81	5	81^1¹⁸
82	7	81¹+1¹⁸ 81^1¹⁸+1
83	7	91–16+8 6₉+69+8 (GT)
84	6	6+69+9
85	6	88+6–9
86	5	86^1⁹⁸
87	7	86¹+1⁹⁸ 86^1⁹⁸+1
88	2	88
89	4	88+1 18₈₁ (GT)
90	6	1+88+1
91	5	91^1¹⁶
92	7	91¹+1¹⁶ 91^1¹⁶+1 86+6₉–0 (GT)
93	6	96+6–9
94	5	6₉+88 (GT)
95	7	96¹–1⁹⁶ (GT) 6₉+18₈₁ (GT)
96	2	96
97	4	96+1 16₉₁ (GT)
98	5	98^1⁸⁶
99	5	88+11 99^1⁶⁶ 81+18 (PF)
100	7	88+11+1 99^1⁶⁶+1 81+1+18 (PF) 11₈₁+18 (GT)

Richard Sabey sent solutions for many other numbers less than 1000 as well.

Joseph DeVincentis also sent some SEs that are different expressions upside down. Here are some short primitive expressions that can be used to manufacture other examples.

Number	Symbols	Shortest Non-Symmetric SE
1	3	1^6¹
10	8	8¹+1⁰+1⁶
16	8	6¹+9+1⁶
17	6	98¹–81
62	8	81¹+0–19
87	8	98+0–11¹
100	8	98+1⁸+1⁹

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 4/23/06.