Artem's blog

Mainly .NET (C#, ASP.NET) and my projects

Archives for Mathematics

Interesting features of numerical roots

Imagine following: you ask your fellow to pick any number they like, and later multiply it by your number. Once they have the result, you will ask them to circle one digit in their answer (except zero). Finally, you ask them to tell you digits that are left in any order, and you will be able to tell the circled digit.

This is simply done using some basic concepts of numerical roots. Once you know these, you will be able to construct different kinds of tricks, based on this principle.

Numerical root: A numerical root is calculated by summing up the digits in a number. Say we have 85732, so the numerical root will be 8+5 which gives you 13. Then, because 13 is bigger then 10, you take 1+3 to get 4, and add it to 7 (the third digit). So, 4+7 = 11, hence 1+1=2. Now 2+3=5, and 5+2=7. So, the numerical root of 85732 is 7. (if you know modulo arithmetic, you simply take the sum modulo 9, i.e. 8+5+7+3+2 mod 9 = 7, however, the described method is handy because it does not require that much calculations)

Interesting feature: If the numerical root is equal to 9, you can perform either addition and/or multiplication of any random number, and the numerical root will still stay the same. This is interesting because you can let your fellow to add or multiply your number with any number, any amount of times, and still know that the numerical root is 9. Let’s see how this works:

If I pick a number with a numerical root of 9, i.e. 54, and you pick 9876 (which I obviously do not know), and later you multiply these two together, and get 533304. I ask you to circle a number, you choose 5, and I ask you for the rest of the digits, i.e. 33304 (note, the order does not matter here). So, I know that the numerical root stays the same, so I find it for your digits, 3+3=6, 6+3=9, 9+4=13, 1+3=4 (as you might already see, this result is obtained when we subtract 9 from 13). So, the numerical root is 4, and I need to add 5 to get 9, hence 5 is the circled digit!

Reference:

Matematicheskie chudesa i tajny, M. Gardner, published in 1986, Moscow. (work in translation)

Vigenère cipher, programming contest

Yesterday I was solving an interesting question that has been used on the Swedish Computer Science contest – a programming contest, in 2010, which probably is simple, but interesting because it emphasises sequences, et cetera.

The question introduced the Vigenére cipher in a classical way, with two disks containing letters of the English alphabet. In the beginning, we know several things about the encrypted text, which are to help us when we are going to crack the message.
bokstavssnurra

  • The disks might have different number configurations, i.e. there is still a shift, which is unknown.
  • In order to “make it harder” for the enemy, each time we have obtained a letter, we continue by using a new shift, and this shift is increased by a constant value.
  • Fortunately, we get to know that each message contains the word “HEJ” – a Swedish word for “hello”, which might be used as  “bye”, I think.

Also, we get some examples as well, for instance:

Example 1:
Encrypted text: LRIJOUZRIYAQIRAG
Message: HEJVITARENFIKANU – means let’s take a “fika”

Example 2:
Encrypted text: GCGDJJI
Message: HEJHOPP – hello in an optimistic manner

There is also an example of this sequence,in Example 1, which is tells us that the difference is 9, 12, 15, 18… (common difference 3).

I’m solving this using a recurrence, and I’m not simplifying this arithmetic progression in any way, I just add d all the time.

The code below has passed all their tests, which are located at the end of this post.

        static void Main(string[] args)
        {
            /* 
             * Copyright (C) 2013 Artem Los,
             * All rights reserved.
             * 
             * This code-snippet can be found at: 
             *      http://clizware.net/
             */

            string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

            Console.Write("Enter the message: ");

            string message = Console.ReadLine();

            int H = alphabet.IndexOf("H");
            int E = alphabet.IndexOf("E");
            int J = alphabet.IndexOf("J");

            int dA = mod(alphabet.IndexOf(message[0]) - H, alphabet.Length);
            int dB = mod(alphabet.IndexOf(message[1]) - E, alphabet.Length);
            int dC = mod(alphabet.IndexOf(message[2]) - J, alphabet.Length);

            int init1 = dB - dA;
            int init2 = dC - dB;

            int dConst = init2 - init1;
            int dPrev = dC;

            Console.Write("Output message: HEJ");
            for (int i = 3; i < message.Length; i++)
            {
                init2 += dConst;
                dPrev = mod(dPrev + init2, alphabet.Length);

                int X = alphabet.IndexOf(message[i]);
                Console.Write(alphabet[mod(X - dPrev, alphabet.Length)]);
            }

            Console.ReadLine();
        }

        static int mod(int n, int b)
        {
            return n - b * (int)Math.Floor((double)n / b);
        }
    }

Example 1
RIPIWDUXRS
HEJSOVERNI

Example 2
IGNUFAKPXYVSF
HEJNUKOMMERDE

Example 3
PAJESQBIPOOPKAP
HEJKOMHITGENAST

Reference:
http://www.progolymp.se/Oldpage/arkiv/kval10.pdf
http://www.progolymp.se/Oldpage/arkiv/kvalsvar10.pdf

Finding polynomial, given one output

Sometimes, we can get a question like: Find a polynomial, such that.

f(7)=89183, 0 leq a_i < 7

Basically, the question asks us for the polynomial that will give as 89183, given that the coefficients are less than 7 and bigger than or equal to 0. Let’s illustrate this:

f(7)=a*7^5+b*7^4+c*7^3+d*7^2+e*7^1+f

Please consider that there might be more or less coefficients, this is just to facilitate the interpretation.

Probably, you might already see, that the number 89183 is in radix 10, and the number, using the coefficients, is in radix 7(abcdef)_7. When we used our polynomial to obtain the value of it, when x=7, we actually converted a number to radix 10.

Therefore, if you convert the result we got in radix 10 to radix 7, the number we get is the answer to this polynomial problem!

89183_1_0=521003_7

Now, we use these coefficients to construct the polynomial:

f(x)=5x^5+2x^4+x^3+3

Conclusion:

f(x)=y
y_x=(a_na_n_-_1...a_1a_0)_x

where a_i are the coefficients of the polynomial.

/Artem

Page 2 of 2:« 1 2