Digital Root

Published: May 24, 2016

What is digital root? Suppose you are given some digits, say 123456, the digital root will be calculated like this:

1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3

Summing each digit repeatedly to get a single digit is how we get the digital root.

How to effectively find the digital root

An intuitive solution would be to recurse steps: 1. get singles digits from the given number. 2. sum up all. However, if the given number is really big, this is not an effective solution.

Luckily, there’s a formula to calculate the digital root. This wikipedia page explains what the formula and how it works: Digital root.

The formula is:

// n is a given number
int digital_root = n - 9*(int)Math.floor((double)(n-1)/9);

Why this is the answer? The digital root sees how many numbers are there after the closest of multiple of 9 which is less than the given number. If the given number is 123456, its closest, multiple of 9 is 123453. So, the digital root of 123456 is 3.

This post is going to be very different from what I write here. The content is a memo how I create a GCP (Google Cloud Platform) instance for Deep Learning. While I study algorithm stuff, I also have been studying Deep Learning. In my early days, I tried to train my Deep Learning model only on a laptop. My laptop is 2012 model MacBook Pro, so I would say it is reasonably fast. However, when it comes to Deep Learning, the training was quite painful on the such machine. Often, I ran the training over night to get a disappointed result. Still, I didn’t use any of pricey cloud environment since it was my personal study unrelated to my day job. I wanted to save money.

Problems which ask a binary tree traverse, add/delete nodes, etc. are popular in algorithm questions. The binary trees are often just a binary tree or binary search tree. Sometimes, the problem pinpoints a particular type of a binary tree, for example, a balanced binary tree or complete binary tree.

What is Catalan number ? The Catalan number belongs to the domain of combinatorial mathematics. It is a sequence of natural numbers such that: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ... The sequence appears in counting problems. Wikipedia has the details about the sequence: Catalan Number.