Does Your Name Sums Up To A Prime Number?

Development, , ,

I just finished a wonderful book! The Curious Incident Of The Dog In The Night-time is a masterpiece, written by Mark Haddon, a famous English children’s book writer who decided to write this book for adults.

That’s a sequence of curious events in the life of a 15-year-old boy, called Christopher, with Asperger syndrome. It’s narrated by himself in a very unique way, telling his efforts to write a book about a small crime that has happened in his street while intercalating the story with his gifted mathematical and logical insights.

A curious thing is that chapters are numbered after prime numbers, rather than conventional successive numbers. The last chapter is 233, which is the 51° prime number. In the chapter 19, he describes a simple algorithm to figure out prime numbers. In his words:

“… you write down all the positive whole numbers in the world. Then you take away all the numbers that are multiples of 2. Then you take away all the numbers that are multiples of 3. Then you take away all the numbers that are multiples of 4 and 5 and 6 and 7 and so on. The numbers that are left are prime numbers”

In one of his insights, he used to get someone’s name, give each letter a value from 1 to 26 and sum the values of each letter of the name to check whether the total is a prime number. So, I thought it would be fun to explore this unique way of seeing things using Clojure. First, we create a map of letters and numbers, where the letters are keys in a map and numbers are their respective values:

(def numbered-alphabet {\a 1  \b 2  \c 3  \d 4  \e 5  \f 6 
                        \g 7  \h 8  \i 9  \j 10 \k 11 \l 12
                        \m 13 \n 14 \o 15 \p 16 \q 17 \r 18
                        \s 19 \t 20 \u 21 \v 22 \w 23 \x 24
                        \y 25 \z 26 \space 0})

The keys are literal characters and the numbers are positive integers. Using the map, we sum the characters of a name:

(defn sum-characters [name]
  ; lower-casing the name to keep the map small
  (let [name (clojure.string/lower-case name)]
    ; given a sequence of characters, reduce it to the sum
    ; of the respective numbers.
    (reduce #(+ (if (char? %1) 
                    (get numbered-alphabet %1) 
                    %1)
                (get numbered-alphabet %2)) 
            (seq name))))

(sum-characters "hildeberto")
>> 98

Is 98 a prime number? No, because it’s even and even numbers have at least 3 divisors: 1, 2 and itself. The algorithm that applies this one and other rules is the following:

(defn is-prime [x]
  (if (or (= x 2) (= x 3))
    true
    ; eliminate even numbers
    (if (even? x)
      false
      ; Number is odd, so it deserves some more attention.
      ; After eliminating even numbers, the maximum divisor
      ; of a number is less than its square root
      (let [max-div (Math/ceil (Math/sqrt x))]
        (loop [i 3]
	  (if (zero? (rem x i))
              false
	      (if (> i max-div)
                  ; it is a prime number
                  true
                  (recur (inc i)))))))))

(is-prime (sum-characters "Hildeberto"))
>> false

That’s a pity my own name doesn’t sum up to a prime number, but the book gave some names to test the code:

(is-prime (sum-characters "Jesus Christ"))
>> true
(is-prime (sum-characters "Scooby Doo"))
>> true
(is-prime (sum-characters "Sherlock Holmes"))
>> true
(is-prime (sum-characters "Doctor Watson"))
>> true

Wait a minute… he uses first and last names! So, let me test with mine:

(is-prime (sum-characters "Hildeberto Mendonca"))
>> true

Yeeeeeesssss! I’m prime-numered!!!

Fluffy Encryption of Numbers Within URLs

Development, , ,

In the REST web services world, a resource is anything that’s important enough to be referenced as a thing in itself. It is something that can be stored on a computer and represented as a stream of bits such as a document, a row in a database, or the result of running an algorithm. The book RESTful Web APIs explains very well that every resource has to have at least one URI, which is the name and address of that resource. The URL to a resource in a typical web application looks like {database-table-name}/{record-id}. For example: /blogs/myblog/entries/134 goes from the general to the specific, from a list of blogs to a particular blog, to the entries in that blog, to a particular entry.

I don’t know about you, but when I look at those URLs and see those record ids I feel very uncomfortable. I’m not sure if it has security implications, but it’s strange to let everybody know that they are dealing with the product number 14 or the order number 35. Maybe I’m being paranoid, but it is worth sharing a trick to replace those ids by fake ones.

The method is simple. We will need two secret numbers that should be configurable for each installation of an application. The secret numbers compose a formula to encrypt a number, as illustrated in Clojure:

(def secret-n1 345)
(def secret-n2 3)

(defn encrypt [id] 
  (bit-xor (* id secret-n1) 
           secret-n2))

(encrypt 35)
>> 12072

The id is multiplied by the first secret number (secret-n1) and the result is used to perform a binary XOR (bitwise exclusive or) with the second secret number (secret-n2). The result is a number that gives no clue about the id it is hiding. Here is an example of applying the function encrypt:

; Original URL
(def id 35)
(def url-entries "http://mywebsite.com/myblog/entries/%d")
(def url-entry (format url-entries id))
(format "Original URL: %s" url-entry)
>> Original URL: http://mywebsite.com/myblog/entries/35

; Modified URL
(def url-entry (format url-entries (encrypt id)))
(format "Modified URL: %s" url-entry)
>> Modified URL: http://mywebsite.com/myblog/entries/12072

Notice that 35 is not exposed anymore. In its place we have 12072, which is not a real id or it’s not related to the current record. But how can we recover the original id after processing the request with 12072? Now comes the decrypt function to recover the original id:

(defn decrypt [request-id] 
  (/ (bit-xor request-id secret-n2) 
     secret-n1))

(decrypt 12072)
>> 35

The secret numbers are used here as well but inverting the calculation. This time, we perform the binary XOR first, with the id that comes in the request and the second secret number (secret-n2), and we divide (instead of multiply) the result by the first secret number (secret-n1).

These ids are maybe meaningless to concern us so much, but what about a global user id or a social security number or even a phone number? This method can protect them all.

The only downside I have identified for this technique is that in the event of compromising the security of the secret numbers, all URLs will change when at least one secret number changes. It means that these URLs are not permanent, thus useless to bookmark them. This is not a serious concern, but you should think about the implications before adopting it.

Think of a number between 1 and 10

Development

You were probably confronted once by a friend, who claimed to be able to read your mind, doing the following trick: Think of a number between 1 and 10; multiply it by 9; sum the digits of the result (e.g. 23 -> 2 + 3 = 5); and subtract 5 from the sum. At this point you may have reached the value 4. How do I know that? Using the same trick of your friend. Let me show you using Clojure. First, we are going to write a function that sums the digits of a number:

(defn sum-digits [val]
  (apply + 
         (map #(Integer. (str %)) 
              (str val))))

The value is transformed into a string, the map function transforms each digit character into a list of integers and the function apply sums the list of integers, returning the total to the caller of the function sum-digits. We are going to use this function to compose the calculations of the trick:

(defn puzzle [x] 
  (- (sum-digits (* x 9)) 5))

The function puzzle performs the calculations in the sequence that your friend has asked you to do. First, it multiplies the number we thought by 9, then it sums the digits of result and finally subtracts the total by 5. Next, we are going to write another function to unveil the trick:

(defn unveil []
  (map #(puzzle %) (range 1 11)))

The function range produces a sequence of numbers starting from 1 to 10 where 11 is not included (1 2 3 4 5 6 7 8 9 10). The function map applies the function puzzle to each number in the list and produces another list with the results. Now, execute the function unveil to see the result:

(unveil)

(4 4 4 4 4 4 4 4 4 4)

Oh, look! For the range of 1 to 10, the result will always be 4. In other words, a pattern. Patterns are very present in multiplications and when you remove all of them you have prime numbers, as pointed by Mark Haddon in his book “The Curious Incident of the Dog in the Night-Time“. Daniel Tammet exemplify some patterns in his book “Thinking in Numbers: How Maths Illuminates Our Lives“. When we multiply any even number by 5 we always get numbers ending in zero (e.g. 12 x 5 = 60) and when we do it with odd numbers we always get numbers ending in 5. In the case of 9, every time we multiple 9 by a number between 1 and 10 and we sum its digits we always get 9.

In the sequence, subtracting 5 from 9 will just distract your attention from the multiplication pattern and even improve the trick. For instance: imagine that each letter of the alphabet has a corresponding number (A – 1, B – 2, C – 3, …). Now, take the result (4) and get its respective letter; think of a country that starts with this letter; take the fourth letter of this country and think of an animal that starts with this letter. There is a high probability that your final answer will be “Denmark” and “monkey”. Before you think I’m reading your mind, let me explain what just happened.

First, there is not many countries that starts with “D”, the fourth letter of the alphabet. Among Denmark, Djibouti, Dominica, and Dominican Republic, you will easily remember Denmark. The fourth letter of Denmark is “M” and no animal that starts with “M” is more famous than the monkey, which comes immediately into your mind.

I’m having fun programming in Clojure, not just because Clojure is fun to learn and teach, but because programming is not always about serious things. Being able to program just enough code to make things happen stimulates thinking, problem solving and creativity over structure, patterns, conventions and styles. Coding is supposed to be relaxing not stressful. Enjoy it!

Calculating Your Level of Naughtiness

Development, ,

To motivate his students, a computer science teacher of the Federal University of Ceará has challenged his class to develop an algorithm to calculate how naughty you are based on your birth date. The challenge is very silly, but it became a Brazilian hit.

The teacher said his original intention was to teach students to call functions from other functions, which is as much silly as the goal of the challenge, but no doubt that the idea is pretty effective on motivating young students.

safadao_questao_materia

The problem consists on writing a function that calculates the percentage of naughtiness and the remaining level of innocence of a person based on his/er birth date. The formula to calculate the level of naughtiness is:

naughtiness = incremental_sum(month) + (year / 100) * (50 - day)

where incremental_sum is a function that, given a number, calculates de sum of all numbers from 1 to the informed number included. The solution below is written in Clojure:

(defn inc-sum [num]
  (reduce + (range (inc num))))

(defn naughtness [day month year]
  (let [naughty (+ (* (- 50 day) (/ year 100.0)) (inc-sum month)) 
        angel (-  100 naughty)] 
    {:naughty naughty 
     :angel angel}))

(naughtness 10 9 78)
=> {:naughty 76.2, :angel 23.8}

The formula has absolutely no sense and doesn’t have any scientific foundation, but the result of the function is great fun to play with friends! Maybe the subject can push you to learn Clojure, doesn’t it?! 😉

Keeping Confidential Information Out Of Git

Development, ,

I’ve launched yet another open source project on GitHub a couple of months ago and now it’s time to use it in production. For that, I had to put some confidential information in a file that is currently tracked by Git. That was the database connection credentials that I keep in a property file. Obviously, I couldn’t push that file to GitHub and I did’t want to keep that file in my staging area forever, but I still wanted to keep the file in the repository, so people could use it to configure their own development/production databases as well.

The file I’m talking about is usi4biz/resources/db-config.edn. Notice that I’ve put pretty dumb credential information there just to make it work in my development environment. This file doesn’t exist anymore in the master branch. I had to do a little tweak, inspired by WordPress, to address the issue.

Before adding any confidential info, I renamed the file to db-config-example.edn:

$ git mv resources/db-config.edn resources/db-config-example.edn
$ git add resources/db-config-example.edn
$ git commit -m "Renamed the database configuration file"

Then, I copied the file and named it after the original name:

$ cp resources/db-config-example.edn resources/db-config.edn

I edited the new file and added the production credentials. Now, I just have to ask Git to ignore it:

$ echo -e "resources/db-config.edn\n" >> .gitignore

This way, db-config.edn will be always out of my staging area whenever I change it. I just have to remember that if I ever need to add a new property I have to do it in both files. For the moment, I just explained in the README file that those wiling to use the application have to copy the file db-config-example.edn with the name db-config.edn because the code refers the file db-config.edn.