Smart Dust for a Quasi-Smart Mathematician

Throughout the next few posts, I will shift away from my grandfather’s anomaly and its applications to ASCII toward a research project that I have just initiated in conjunction with my honors electrical engineering advisor, Dr. Julio Urbina. As you shall notice, this project will be one of significant mathematical rigor and quite a challenge for someone not even halfway through the foundational electrical engineering course, EE 210. However, I decided to take on the project (partly through my research seminar course EE 396) to explore a potentially groundbreaking application of my major (EE) and my lifelong passion (mathematics).

What is Smart Dust?

Smart Dust is the collective name given to microscopic drones that function as both satellites and computers, with the ability to communicate with each other to autonomously accomplish a certain task. In a group, the drones resemble a levitating pile of dust (hence the name), and each device may also act as a single spacecraft. Through programming, one is able to synchronize the drones to move, orient themselves, and utilize their sensors in a desired manner. The technology is not widely recognized—only familiarized by me this semester—and research has not been extensive as in other EE applications such as quantum computing, radar, electronic circuit design, etc.

Image Courtesy of Medium

At this stage, I have only amassed research and review papers on the topic and have yet to actually read them in detail. Thus, my decision to shift the focus of this blog (while still emphasizing the purely mathematical aspect) was motivated primarily by my desire to engage with the topic every time I have a chance. While my writing may simply comprise a regurgitation of what I have learned (in terms of the mathematical nature of Smart Dust), I shall treat it as an opportunity to teach a broader audience from my experience, and after all, “to teach is to learn twice.”

Mathematical Aspects?

To convey the nature of the beast that awaits me, I have taken excerpts of equations from a Smart Dust review paper (“A review of Smart Dust architecture, dynamics, and mission applications” by Niccolai, et al.) that I plan to read and analyze from now until Spring Break.

Images Courtesy of Niccolai, et al.

From a mere glance, I recognize an application of linear algebra and vector calculus, covered in courses in which I am currently enrolled (MATH 220 and 230H, respectively). However, applying theoretical-based knowledge of the concepts and operations (resultant from the lack of application in homework problems and exam practice) to a technology of which I know very little will be daunting. Despite this, it is my hope that my passion for mathematics combined with my pursuit of an all-important application of mathematics (EE) will facilitate my learning of and eventual experimentation with (per Dr. Urbina’s request) a device (rather, many devices) that will potentially become ubiquitous yet is currently unheard of among the general public.

Encoding with ASCII (and Extended ASCII)

By its very definition, ASCII is a code system used to express English characters in binary or hexadecimal form. What if one sought an Enigma-like system in which alphanumerics and punctuation are signified by other characters? Could ASCII be used for such a purpose? It is helpful first to re-introduce the ASCII table:

Image Courtesy of Simple Wikipedia

For the following mathematical code systems, it is necessary to take note of the decimal representations of the ASCII characters, not often practically employed (e.g., A = 65, d = 100). Indeed, it is much easier and more useful to learn the hexadecimal (and consequently, binary) representations of the ASCII characters. However, since the aforementioned mathematical quirk arising from the “DeMarchis Riddle” is applicable only in base 10, the base-10 ASCII values should be considered.

Recall the necessary steps to realize the anomaly:

  1. Take any whole number x and subtract it by the sum of its digits [x – digitSum(x)].
  2. Divide that difference by 9 to yield a whole number quotient [(x – digitSum(x)) / 9].
  3. Add that quotient to the original number to obtain y [x + (x – digitSum(x)) / 9 = y].

For each value of x, there is a corresponding and unique value of y obtained by the following formula:

y(x) = [10x – digitSum(x)]/9

To encode a particular ASCII character, simply assign the decimal representation of the character to and rewrite the character as the one corresponding to the decimal value y. For example, the capital A is signified by 65. Inserting 65 into the y(x) function yields 71, which corresponds in ASCII to the capital G. Using this system, I can encode my full first name as:

Gz???{zt{

In attempting to encode the “t,” we encounter a problem. The traditional ASCII table only consists of decimal codes up to 127, and the 116 code signifying the lowercase t is manipulated to 128, which does not appear in the table above. Thus, to encode characters near the end of the table, it is necessary to employ the extended ASCII table, which encodes 128 additional characters with hexadecimal values 80 through FF. Although the extended table is not uniform among the different operating systems, I shall focus on the Apple (Mac OS) version of the table:

Image Courtesy of ASCII-Table

In the table above, a character’s hex code is signified by the digit of its column followed by the digit of its row. Thus, the recognizable Apple logo is encoded as F0. One disadvantage is that the table requires a intermediate conversion from hexadecimal to decimal, certainly not a trivial process. With the decimal number 128 equal to the hex value 80, I can now express my complete first name with ASCII and extended ASCII characters:

GzÄ{zt{

What is your name expressed in this new code? Of course, any attempted representations of high-value extended ASCII characters (e.g., the degree symbol) are futile, as there is no additional ASCII table for hex values larger than FF; this would require more than one byte per character. I am currently working on a Python program that will output encoded letters for a given input (e.g., a word). Although this particular code system is not the most secure or most difficult to grasp, it illustrates a working combination of both the ASCII system and the intriguing arithmetical anomaly discovered (to our knowledge) by my grandfather little more than five years ago.

0100000101010011010000110100100101001001

It would be no surprise if I had decided to write this entire post in binary digits. In fact, I have been infatuated with binary for nearly six years. In June of 2014 (at a measly 13 years old), I read Code by Charles Petzold (2000), consisting of a hypothetical step-by-step guide to constructing a computer from the logic gates to the operating system. Impressed by Petzold’s simplification of an overwhelmingly complex device and his compelling narrative-like style, I could never seem to put the book down, having read it cover-to-cover nearly ten times as of now. It is what sparked my interest in electrical engineering, and I referenced it multiple times in my application essays for Schreyer. In essence, I am enrolled in this very course—and this very university—partly due to Petzold and his work.

Image Courtesy of Goodreads

Once I read Code, I was driven to learn more about the base-2 number system (binary), the quintessential facet of digital computing. I began by practicing binary-to-decimal conversion, the process of rendering a familiar base-10 number (e.g., 25) into its binary form (11001 in the case of 25). In the base-10 decimal system—taken for granted to such an extent that alternative systems seem almost inconceivable—each digit in a number (0-9) represents a multiple of a power of 10. This is illustrated below for the number 3851:

3581 = 3 x 10^3 + 5 x 10^2 + 8 x 10^1 + 1 x 10^0

In the binary system, with only two digits, each digit represents a power of two. Conceptually, each position can be regarded as being turned “on” (multiplied by 1) or “off” (multiplied by 0, or annihilated):

1001101 = 1 x 2^6 + 0 x 2^5 + 0 x 2^4 + 1 x 2^3 + 1 x 2^2 + 0 x 2^1 + 1 x 2^0

However, base-conversion arithmetic wound up becoming tedious and uninteresting, with little potential application beyond fundamental mathematical skill. I thus turned to pursuing a system touched on by Petzold but imperative to the operation of machines everywhere: text representation via the American Standard Code for Information Interchange (ASCII).

Before the ASCII table is presented, it is helpful to have knowledge of the hexadecimal (base-16) number system, consisting of the digits 0-9 and six additional “digits” signified by the letters A-F (representing 10 through 15, respectively).

Image Courtesy of String Functions

In a two-digit hexadecimal number, each digit (or nibble) can be expressed as a string of exactly four binary digits. Zero (0) is signified by 0000, F is signified by 1111, and intermediate conversions are displayed below:

Image Courtesy of Geeks for Geeks

The ASCII system consists of common English characters (e.g., alphanumerics, $, &, !, [space]) each represented by a two-digit hexadecimal—and consequently, 8-bit binary—code. Applying the terminology that 8 bits corresponds to one byte, it holds that ASCII represents each character as a single byte. That is, a word or expression made of n characters occupies n bytes of storage or memory. The complete ASCII table is shown below:

Image Courtesy of Wikimedia

One may immediately note that the table only displays the first half of the hexadecimal codes and excludes 80 through FF. Such secondary codes comprise the extended ASCII system, which consists of more obscure characters and is unique to each operating system (Windows or Mac). Moreover, the ASCII hexadecimal codes 00 through 31 can essentially be ignored (except 09 through 0F), as these are primarily applicable to archaic typewriters, the main writing tools at the time of ASCII’s inception. Using ASCII, my complete first name can be written as follows:

Hexadecimal:  416E746F6E696F

Binary: 01000001011011100111010001101111011011100110100101101111

In the comments section, please try expressing your name in hexadecimal or binary using the ASCII table! Additionally, there are myriad online “text to binary converters” at your disposal. Many programs (and, if you noticed above, Petzold on the front cover of Code) yield only 7 binary digits per character, as 8 are necessary only if extended ASCII is incorporated. However, to maintain evenness and the “one byte per character” standard, the convention is to annex a leading zero to represent a character with 8 bits.

In the next blog post, I will detail my endeavors to mathematically apply ASCII to formulate a code system, particularly in relation to my grandfather’s riddle and the supplementary curiosity with the number 9.

How So Quickly?

This week, I showcase my effort to prove an intriguing mathematical curiosity in the DeMarchis Riddle written by my grandfather. Such a proof, as will be demonstrated, has been as elusive as the quirk itself has been fascinating for nearly four years now.

Quirk in the Riddle

As you may recall, the woman’s house number was 9489. Now take that number, and perform the following operation:

However many digits are remaining in the number, subtract it by the number consisting of the largest string of common digits such that the difference remains positive.

Surely an example is necessary to convey such convoluted language. Considering that we have 9489, what is the largest four-digit number consisting of the same digits (e.g., 1111, 2222, 3333,…) that we can subtract to keep the number positive? Clearly, it is 8888.

9489 – 8888 = 601

Now, perform the same operation on the resultant difference. To maintain positivity, one must subtract 555 from 601:

601 – 555 = 46

We keep subtracting in this manner until we are left with a single-digit number, upon which we subtract it from itself to yield 0:

46 – 44 = 2

2 – 2 = 0

What do you notice about the strings of digits we utilized (8888, 555, 44, 2)? In fact each separate digit constitutes an age of one of the children (i.e., the answer to last week’s problem: 8, 5, 4, and 2)!

That is, if you take any positive integer, subtract it by its digit sum, divide that difference by 9, and add the resultant quotient to the original number, you obtain an integer which may be used to recover the original number via the operations described above. This is precisely how the salesman from the problem was able to deduce the children’s ages so quickly, as noted in the description.

Attempt at a Proof

I begin by writing out the operation that transforms a given positive integer x into a related integer y.

(x – digitSum(x))/9 + x = y

The function digitSum is mathematically defined as an expression of modulo terms and exponential summations, which be abbreviated to the eponymous name for now.

Multiplying the equation above by 9 to obtain common denominators, I obtain the following linear equation:

10x – digitSum(x) = 9y

The main question is: Why can the output y be defined as a summation of the strings of digits of x, with the length of each string proportional to the position of that digit in x? That is, how can it be that, when one performs a digitSum subtraction, division by 9, and an addition to the original x, he or she obtains the summation of the strings of digits of x?

Surely, the answer must lie with the number 9. A less significant though interesting quirk is the fact that x – digitSum(x) is always divisible by 9. Additionally, along with and higher multiples, 9 is the only integer such that the divisibility of the digit sum of a given number implies the divisibility of the number itself. For example, 441 is divisible by 9 because 4 + 4 + 1  is also divisible by 9.

Clearly, I have no direction regarding a proof, originally requested by my grandfather. What I have developed, however, is a code system incorporating this very curiosity and my two favorite aspects of computer science: binary and ASCII, the subjects of next week’s post.