862:, but it only needs linear runtime if the input is presented in unary. However, this is potentially misleading. Using a unary input is slower for any given number, not faster; the distinction is that a binary (or larger base) input is proportional to the base 2 (or larger base) logarithm of the number while unary input is proportional to the number itself. Therefore, while the run-time and space requirement in unary looks better as function of the input size, it does not represent a more efficient solution.
877:
but not strongly NP-complete. A problem in which the input includes some numerical parameters is strongly NP-complete if it remains NP-complete even when the size of the input is made artificially larger by representing the parameters in unary. For such a problem, there exist hard instances for which
932:. The larger the number, the more likely the email is considered spam. Using a unary representation instead of a decimal number lets the user search for messages with a given rating or higher. For example, searching for
784:, a character drawn with three strokes. (One and two are represented similarly.) In China and Japan, the character 正, drawn with 5 strokes, is sometimes used to represent 5 as a tally.
761:, in which the value of a digit depends on its position within a number. For instance, the unary form of a number can be exponentially longer than its representation in other bases.
818:
or population count operation that counts the number of nonzero bits in a sequence of binary values may also be interpreted as a conversion from unary to
1052:
854:
problems), where it is used to "artificially" decrease the run-time or space requirements of a problem. For instance, the problem of
710:
750:, that is, the absence of a symbol. Numbers 1, 2, 3, 4, 5, 6, ... are represented in unary as 1, 11, 111, 1111, 11111, 111111, ...
430:
1592:
1551:
1314:
1248:
886:
In addition to the application in tally marks, unary numbering is used as part of some data compression algorithms such as
858:
is suspected to require more than a polynomial function of the length of the input as run-time if the input is given in
263:
1278:, NBS Special Publication, vol. 503, U.S. Department of Commerce / National Bureau of Standards, pp. 146–156
1434:
1371:
1344:
1032:
1007:
980:
1653:
866:
54:
842:, the unary system is inconvenient and hence is not used in practice for large calculations. It occurs in some
497:
1534:
Magaud, Nicolas; Bertot, Yves (2002), "Changing data structures in type theory: a study of natural numbers",
1134:
703:
278:
1272:
Blaxell, David (1978), "Record linkage by bit pattern matching", in Hogben, David; Fife, Dennis W. (eds.),
623:
450:
757:. However, although it has sometimes been described as "base 1", it differs in some important ways from
633:
510:
1663:
1171:
606:
375:
1643:
696:
23:
1205:
Lunde, Ken; Miura, Daisuke (January 27, 2016), "Proposal to Encode Five
Ideographic Tally Marks",
1074:
1048:
686:
470:
67:
331:
1658:
1232:
1226:
370:
286:
1391:
1334:
1273:
1206:
1129:
997:
1424:
1361:
970:
859:
855:
847:
768:
in counting is an application of the unary numeral system. For example, using the tally mark
488:
1575:
Jansen, Jan Martin (2013), "Programming in the λ-calculus: from Church to Scott and back",
1561:
1482:
1306:
1299:
1258:
1115:
870:
811:
754:
583:
437:
318:
1608:
8:
1648:
1002:, Computer Science and Scientific Computing (2nd ed.), Academic Press, p. 117,
839:
758:
665:
655:
530:
481:
293:
225:
80:
41:
1579:, Lecture Notes in Computer Science, vol. 8106, Springer-Verlag, pp. 168–180,
120:
1508:
1486:
1459:
1188:
1151:
1057:
895:
578:
168:
163:
110:
999:
Computability, Complexity, and
Languages: Fundamentals of Theoretical Computer Science
115:
1588:
1547:
1538:, Lecture Notes in Comput. Sci., vol. 2277, Springer, Berlin, pp. 181–196,
1504:
1430:
1367:
1340:
1310:
1244:
1028:
1003:
976:
660:
650:
638:
618:
573:
568:
504:
336:
308:
215:
148:
138:
125:
90:
85:
1490:
1457:(1978), "'Strong' NP-completeness results: Motivation, examples, and implications",
553:
1580:
1539:
1516:
1468:
1454:
1450:
1420:
1236:
1180:
1143:
1103:
1066:
950:
843:
781:
563:
457:
210:
198:
143:
133:
100:
75:
1584:
1557:
1478:
1366:, Emergence, Complexity and Computation, vol. 18, Springer, pp. 83–86,
1254:
1111:
903:
899:
675:
645:
588:
558:
543:
303:
271:
243:
220:
203:
62:
158:
1294:
827:
823:
815:
728:
670:
613:
593:
548:
421:
153:
105:
31:
1107:
810:
are particularly simple in the unary system, as they involve little more than
1637:
1543:
1520:
1387:
1330:
1290:
1240:
921:
887:
819:
476:
365:
298:
238:
173:
95:
1094:
Zdanowski, Konrad (2022), "On efficiency of notations for natural numbers",
826:
is more cumbersome and has often been used as a test case for the design of
1231:, Lecture Notes in Comput. Sci., vol. 960, Springer, Berlin, pp.
945:
891:
747:
628:
1473:
1401:(January 2007 draft ed.), Cambridge University Press, §17, pp. 32–33
1070:
913:
874:
807:
765:
598:
463:
415:
405:
1275:
Computer
Science and Statistics--Tenth Annual Symposium on the Interface
1192:
1155:
851:
400:
1610:
Email, Spam
Control, How to get service for departmental email servers
1360:
Rendell, Paul (2015), "5.3 Larger
Example TM: Unary Multiplication",
777:
410:
1629:
sequence A000042 (Unary representation of natural numbers)
1184:
1147:
917:
803:
791:, which are also written as sequences of ones but have their usual
1625:
792:
788:
395:
380:
1336:
The New Turing
Omnibus: Sixty-Six Excursions in Computer Science
385:
910:
390:
352:
313:
1628:
1301:
Introduction to
Automata Theory, Languages, and Computation
1228:
Logic and computational complexity (Indianapolis, IN, 1994)
1130:"The Evolution of Modern Numerals from Ancient Tally Marks"
1392:"The computational model —and why it doesn't matter"
996:
Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994),
1225:
Sazonov, Vladimir Yu. (1995), "On feasible numbers",
878:
all parameter values are at most polynomially large.
743:
1298:
995:
1635:
1363:Turing Machine Universality of the Game of Life
1169:Hsieh, Hui-Kuang (1981), "Chinese Tally Mark",
1289:
1025:Programming Structures: Machines and Programs
704:
1536:Types for proofs and programs (Durham, 2000)
1533:
1449:
1419:
936:yield messages with a rating of at least 4.
727:is the simplest numeral system to represent
1399:Computational Complexity: A Modern Approach
1198:
1047:
787:Unary numbers should be distinguished from
1386:
1204:
1027:, vol. 1, Prentice Hall, p. 33,
711:
697:
1472:
1093:
869:, unary numbering is used to distinguish
780:cultures, the number 3 is represented as
1127:
1513:IEEE Transactions on Information Theory
1429:, Oxford University Press, p. 29,
1359:
1339:, Computer Science Press, p. 209,
1329:
1271:
1265:
1224:
1636:
1574:
1503:
972:One to Nine: The Inner Life of Numbers
968:
735:, a symbol representing 1 is repeated
1168:
772:(𝍷), the number 3 is represented as
1022:
902:is used to represent numbers within
13:
898:. A form of unary notation called
894:for formalizing arithmetic within
890:. It also forms the basis for the
14:
1675:
1619:
1262:. See in particular p. 48.
873:problems from problems that are
742:In the unary system, the number
1601:
1568:
1527:
1497:
1443:
1413:
1380:
1353:
1323:
1283:
881:
867:computational complexity theory
1218:
1162:
1121:
1087:
1041:
1016:
989:
962:
916:tag messages with a number of
1:
1577:The Beauty of Functional Code
1135:American Mathematical Monthly
1128:Woodruff, Charles E. (1909),
975:, Anchor Canada, p. 14,
956:
833:
798:
746:(zero) is represented by the
1585:10.1007/978-3-642-40355-2_12
1096:Theoretical Computer Science
848:theoretical computer science
7:
1423:; Mertens, Stephan (2011),
939:
10:
1680:
840:positional numeral systems
795:numerical interpretation.
431:Non-standard radices/bases
1426:The Nature of Computation
1172:The American Statistician
1108:10.1016/j.tcs.2022.02.015
1544:10.1007/3-540-45842-5_12
1521:10.1109/TIT.1966.1053907
1307:Example 7.7, pp. 158–159
1241:10.1007/3-540-60178-3_78
755:bijective numeral system
731:: to represent a number
969:Hodges, Andrew (2009),
687:List of numeral systems
1654:Elementary mathematics
1515:, IT-12 (3): 399–401,
1509:"Run-length encodings"
1390:; Barak, Boaz (2007),
1474:10.1145/322077.322090
856:integer factorization
838:Compared to standard
55:Hindu–Arabic numerals
16:Base-1 numeral system
1214:, Proposal L2/16-046
1071:10.1511/2001.40.3268
871:strongly NP-complete
812:string concatenation
759:positional notations
725:unary numeral system
584:Prehistoric counting
360:Common radices/bases
42:Place-value notation
531:Sign-value notation
1460:Journal of the ACM
1305:, Addison Wesley,
1295:Ullman, Jeffrey D.
1208:Unicode Consortium
1058:American Scientist
1023:Hext, Jan (1990),
896:mathematical logic
774:|||
187:East Asian systems
1594:978-3-642-40354-5
1553:978-3-540-43287-6
1421:Moore, Cristopher
1316:978-0-201-02988-8
1291:Hopcroft, John E.
1250:978-3-540-60178-4
721:
720:
520:
519:
1671:
1664:Formal languages
1627:
1614:
1613:
1605:
1599:
1597:
1572:
1566:
1564:
1531:
1525:
1523:
1501:
1495:
1493:
1476:
1447:
1441:
1439:
1417:
1411:
1409:
1408:
1406:
1396:
1384:
1378:
1376:
1357:
1351:
1349:
1327:
1321:
1319:
1304:
1287:
1281:
1279:
1269:
1263:
1261:
1222:
1216:
1215:
1213:
1202:
1196:
1195:
1166:
1160:
1158:
1125:
1119:
1118:
1091:
1085:
1084:
1083:
1082:
1073:, archived from
1045:
1039:
1037:
1020:
1014:
1012:
993:
987:
985:
966:
951:One-hot encoding
846:descriptions in
844:decision problem
713:
706:
699:
502:
486:
468:
458:balanced ternary
455:
442:
48:
47:
19:
18:
1679:
1678:
1674:
1673:
1672:
1670:
1669:
1668:
1644:Numeral systems
1634:
1633:
1622:
1617:
1607:
1606:
1602:
1595:
1573:
1569:
1554:
1532:
1528:
1502:
1498:
1448:
1444:
1437:
1418:
1414:
1404:
1402:
1394:
1385:
1381:
1374:
1358:
1354:
1347:
1328:
1324:
1317:
1288:
1284:
1270:
1266:
1251:
1223:
1219:
1211:
1203:
1199:
1185:10.2307/2683999
1167:
1163:
1148:10.2307/2970818
1142:(8–9): 125–33,
1126:
1122:
1092:
1088:
1080:
1078:
1046:
1042:
1035:
1021:
1017:
1010:
994:
990:
983:
967:
963:
959:
942:
904:lambda calculus
900:Church encoding
884:
836:
828:Turing machines
801:
729:natural numbers
717:
681:
680:
603:
589:Proto-cuneiform
534:
533:
522:
521:
516:
515:
500:
484:
466:
453:
440:
427:
356:
355:
343:
342:
323:
283:
268:
259:
258:
249:
248:
230:
189:
188:
179:
178:
130:
72:
58:
57:
45:
44:
32:Numeral systems
17:
12:
11:
5:
1677:
1667:
1666:
1661:
1656:
1651:
1646:
1632:
1631:
1621:
1620:External links
1618:
1616:
1615:
1600:
1593:
1567:
1552:
1526:
1496:
1467:(3): 499–508,
1455:Johnson, D. S.
1442:
1435:
1412:
1388:Arora, Sanjeev
1379:
1372:
1352:
1345:
1331:Dewdney, A. K.
1322:
1315:
1282:
1264:
1249:
1217:
1197:
1161:
1120:
1086:
1040:
1033:
1015:
1008:
988:
981:
960:
958:
955:
954:
953:
948:
941:
938:
883:
880:
835:
832:
824:multiplication
820:binary numbers
816:Hamming weight
800:
797:
719:
718:
716:
715:
708:
701:
693:
690:
689:
683:
682:
679:
678:
673:
668:
663:
658:
653:
648:
643:
642:
641:
636:
631:
621:
616:
610:
609:
602:
601:
596:
591:
586:
581:
576:
571:
566:
561:
556:
551:
546:
540:
539:
538:Non-alphabetic
535:
529:
528:
527:
524:
523:
518:
517:
514:
513:
508:
495:
479:
474:
461:
448:
434:
433:
426:
425:
418:
413:
408:
403:
398:
393:
388:
383:
378:
373:
368:
362:
361:
357:
350:
349:
348:
345:
344:
341:
340:
334:
328:
327:
322:
321:
316:
311:
306:
301:
296:
290:
289:
287:Post-classical
282:
281:
275:
274:
267:
266:
260:
256:
255:
254:
251:
250:
247:
246:
241:
235:
234:
229:
228:
223:
218:
213:
208:
207:
206:
195:
194:
190:
186:
185:
184:
181:
180:
177:
176:
171:
166:
161:
156:
151:
146:
141:
136:
129:
128:
123:
118:
113:
108:
103:
98:
93:
88:
83:
78:
71:
70:
68:Eastern Arabic
65:
63:Western Arabic
59:
53:
52:
51:
46:
40:
39:
38:
35:
34:
28:
27:
15:
9:
6:
4:
3:
2:
1676:
1665:
1662:
1660:
1659:Coding theory
1657:
1655:
1652:
1650:
1647:
1645:
1642:
1641:
1639:
1630:
1624:
1623:
1612:
1611:
1604:
1596:
1590:
1586:
1582:
1578:
1571:
1563:
1559:
1555:
1549:
1545:
1541:
1537:
1530:
1522:
1518:
1514:
1510:
1506:
1500:
1492:
1488:
1484:
1480:
1475:
1470:
1466:
1462:
1461:
1456:
1452:
1446:
1438:
1436:9780199233212
1432:
1428:
1427:
1422:
1416:
1400:
1393:
1389:
1383:
1375:
1373:9783319198422
1369:
1365:
1364:
1356:
1348:
1346:9780805071665
1342:
1338:
1337:
1332:
1326:
1318:
1312:
1308:
1303:
1302:
1296:
1292:
1286:
1277:
1276:
1268:
1260:
1256:
1252:
1246:
1242:
1238:
1234:
1230:
1229:
1221:
1210:
1209:
1201:
1194:
1190:
1186:
1182:
1178:
1174:
1173:
1165:
1157:
1153:
1149:
1145:
1141:
1137:
1136:
1131:
1124:
1117:
1113:
1109:
1105:
1101:
1097:
1090:
1077:on 2014-01-11
1076:
1072:
1068:
1064:
1060:
1059:
1054:
1050:
1044:
1036:
1034:9780724809400
1030:
1026:
1019:
1011:
1009:9780122063824
1005:
1001:
1000:
992:
984:
982:9780385672665
978:
974:
973:
965:
961:
952:
949:
947:
944:
943:
937:
935:
931:
927:
923:
922:e-mail header
919:
915:
912:
907:
905:
901:
897:
893:
889:
888:Golomb coding
879:
876:
872:
868:
863:
861:
857:
853:
849:
845:
841:
831:
829:
825:
821:
817:
813:
809:
805:
796:
794:
790:
785:
783:
779:
775:
771:
767:
762:
760:
756:
751:
749:
745:
740:
738:
734:
730:
726:
714:
709:
707:
702:
700:
695:
694:
692:
691:
688:
685:
684:
677:
674:
672:
669:
667:
664:
662:
659:
657:
654:
652:
649:
647:
644:
640:
637:
635:
632:
630:
627:
626:
625:
624:Alphasyllabic
622:
620:
617:
615:
612:
611:
608:
605:
604:
600:
597:
595:
592:
590:
587:
585:
582:
580:
577:
575:
572:
570:
567:
565:
562:
560:
557:
555:
552:
550:
547:
545:
542:
541:
537:
536:
532:
526:
525:
512:
509:
506:
499:
496:
493:
492:
483:
480:
478:
475:
472:
465:
462:
459:
452:
449:
446:
439:
436:
435:
432:
429:
428:
423:
419:
417:
414:
412:
409:
407:
404:
402:
399:
397:
394:
392:
389:
387:
384:
382:
379:
377:
374:
372:
369:
367:
364:
363:
359:
358:
354:
347:
346:
338:
335:
333:
330:
329:
325:
324:
320:
317:
315:
312:
310:
307:
305:
302:
300:
297:
295:
292:
291:
288:
285:
284:
280:
277:
276:
273:
270:
269:
265:
262:
261:
257:Other systems
253:
252:
245:
242:
240:
239:Counting rods
237:
236:
232:
231:
227:
224:
222:
219:
217:
214:
212:
209:
205:
202:
201:
200:
197:
196:
192:
191:
183:
182:
175:
172:
170:
167:
165:
162:
160:
157:
155:
152:
150:
147:
145:
142:
140:
137:
135:
132:
131:
127:
124:
122:
119:
117:
114:
112:
109:
107:
104:
102:
99:
97:
94:
92:
89:
87:
84:
82:
79:
77:
74:
73:
69:
66:
64:
61:
60:
56:
50:
49:
43:
37:
36:
33:
30:
29:
25:
21:
20:
1609:
1603:
1576:
1570:
1535:
1529:
1512:
1505:Golomb, S.W.
1499:
1464:
1458:
1451:Garey, M. R.
1445:
1425:
1415:
1403:, retrieved
1398:
1382:
1362:
1355:
1335:
1325:
1300:
1285:
1274:
1267:
1227:
1220:
1207:
1200:
1176:
1170:
1164:
1139:
1133:
1123:
1099:
1095:
1089:
1079:, retrieved
1075:the original
1062:
1056:
1053:"Third Base"
1043:
1024:
1018:
998:
991:
971:
964:
946:Unary coding
933:
930:X-SPAM-LEVEL
929:
925:
914:spam filters
908:
892:Peano axioms
885:
882:Applications
864:
837:
802:
786:
773:
769:
763:
752:
748:empty string
741:
736:
732:
724:
722:
490:
451:Signed-digit
444:
326:Contemporary
193:Contemporary
1049:Brian Hayes
875:NP-complete
850:(e.g. some
822:. However,
808:subtraction
766:tally marks
764:The use of
753:Unary is a
629:Akṣarapallī
599:Tally marks
498:Non-integer
1649:1 (number)
1638:Categories
1179:(3): 174,
1081:2013-07-28
1065:(6): 490,
957:References
926:X-Spam-Bar
852:P-complete
834:Complexity
799:Operations
778:East Asian
666:Glagolitic
639:Kaṭapayādi
607:Alphabetic
511:Asymmetric
353:radix/base
294:Cistercian
279:Babylonian
226:Vietnamese
81:Devanagari
918:asterisks
634:Āryabhaṭa
579:Kharosthi
471:factorial
438:Bijective
339:(Iñupiaq)
169:Sundanese
164:Mongolian
111:Malayalam
1507:(1966),
1491:18371269
1333:(1989),
1297:(1979),
1102:: 1–10,
1051:(2001),
940:See also
924:such as
804:Addition
789:repunits
661:Georgian
651:Cyrillic
619:Armenian
574:Etruscan
569:Egyptian
477:Negative
337:Kaktovik
332:Cherokee
309:Pentadic
233:Historic
216:Japanese
149:Javanese
139:Balinese
126:Dzongkha
91:Gurmukhi
86:Gujarati
24:a series
22:Part of
1562:2044538
1483:0478747
1405:May 10,
1259:1449655
1193:2683999
1156:2970818
1116:4410388
793:decimal
739:times.
564:Chuvash
482:Complex
272:Ancient
264:History
211:Hokkien
199:Chinese
144:Burmese
134:Tibetan
121:Kannada
101:Sinhala
76:Bengali
1591:
1560:
1550:
1489:
1481:
1433:
1370:
1343:
1313:
1257:
1247:
1191:
1154:
1114:
1031:
1006:
979:
920:in an
860:binary
814:. The
770:|
676:Hebrew
646:Coptic
559:Brahmi
544:Aegean
501:
485:
467:
454:
441:
304:Muisca
244:Tangut
221:Korean
204:Suzhou
116:Telugu
1487:S2CID
1395:(PDF)
1233:30–51
1212:(PDF)
1189:JSTOR
1152:JSTOR
911:email
909:Some
776:. In
671:Greek
656:Geʽez
614:Abjad
594:Roman
554:Aztec
549:Attic
464:Mixed
422:table
314:Quipu
299:Mayan
154:Khmer
106:Tamil
1626:OEIS
1589:ISBN
1548:ISBN
1431:ISBN
1407:2017
1368:ISBN
1341:ISBN
1311:ISBN
1245:ISBN
1029:ISBN
1004:ISBN
977:ISBN
934:****
806:and
723:The
319:Rumi
174:Thai
96:Odia
1581:doi
1540:doi
1517:doi
1469:doi
1237:doi
1181:doi
1144:doi
1104:doi
1100:915
1067:doi
928:or
865:In
351:By
159:Lao
1640::
1587:,
1558:MR
1556:,
1546:,
1511:,
1485:,
1479:MR
1477:,
1465:25
1463:,
1453:;
1397:,
1309:,
1293:;
1255:MR
1253:,
1243:,
1235:,
1187:,
1177:35
1175:,
1150:,
1140:16
1138:,
1132:,
1112:MR
1110:,
1098:,
1063:89
1061:,
1055:,
906:.
830:.
416:60
411:20
406:16
401:12
396:10
26:on
1598:.
1583::
1565:.
1542::
1524:.
1519::
1494:.
1471::
1440:.
1410:.
1377:.
1350:.
1320:.
1280:.
1239::
1183::
1159:.
1146::
1106::
1069::
1038:.
1013:.
986:.
782:三
744:0
737:N
733:N
712:e
705:t
698:v
507:)
505:φ
503:(
494:)
491:i
489:2
487:(
473:)
469:(
460:)
456:(
447:)
445:1
443:(
424:)
420:(
391:8
386:6
381:5
376:4
371:3
366:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.