Magic number: A magic number is a number in which the eventual sum of the digits is equal to 1. For example: 28=2+8=10=1+0=1

The logic for the testing whether or not a positive integer is a magic number or not essentially consists of finding the sum of all digits repeatedly till the sum is more than 9. Once the sum becomes less than 10 the original number is a magic number if the final sum is 1. The Java implementation is as follows:

class MagicTest{ public static boolean isMagicNumber1(int n){ int sum; do{ sum=0; for(int temp=n; temp > 0; temp /=10){ sum+=temp%10; } n=sum; }while( sum > 9 ); return sum==1; } public static void main(String args[]){ System.out.println("28"+isMagicNumber1(28)); System.out.println("29"+isMagicNumber1(29)); } }

In the above code the outer loop is for repeatedly finding the sum till it’s more than 9. Also note that we are making the sum as the number just after the inner loop so that next time the we get the sum of the digits of the number we got as sum. The inner loop is actually finding the sum of digit of the number n. We will take out the last digit by finding the remainder of number divided by 10. We then remove the last digit by dividing the number by 10. Since both the dividend and divisor are integers we get the integer answer. This process is repeated till the number is more than 0, that is till there are digits left in the number.

However, it has been observed that all magic numbers satisfy the following relation:

number%9 == 1

The above logic is highly efficient because it’s just a simple mathematical expression without any loop. Now, since I do not have a mathematical proof of the above relation I tested it empirically by testing the above relation for magic number for the entire range of positive integers, that is from 1 to 2^{31}-1. The code that I used for testing the above relation for magic number is as follows:

class MagicTest{ public static boolean isMagicNumber1(int n){ int sum; do{ sum=0; for(int temp=n; temp > 0; temp /=10){ sum+=temp%10; } n=sum; }while( sum > 9 ); return sum==1; } public static boolean isMagicNumber2(int n){ return ( n%9 )==1; } public static void main(String args[]){ boolean status=true; int i; for(i=1; i < Integer.MAX_VALUE-1; i++){ if(isMagicNumber1(i) && !isMagicNumber2(i)){ status=false; break; } } if(status) System.out.println("Test successful"); else System.out.println("Test failed for "+i); } }

The method isMagicNumber2() is the function implementing the new logic that is

n%9 is equal to 1 for all magic numbers. The main method runs a loop for all positive integers from 1 to 2^{31}-1. Note that we are running the loop till Integer.MAX_VALUE-1 (that is 2^{31}-2) because if we take the loop till Integer.MAX_VALUE then the number will become negative once it reaches Integer.MAX_VALUE due to the i++ in the *for* loop; negative number will obviously be less than Integer.MAX_VALUE and it will again start increasing, thus the loop will become infinite. For details of why the loop will become infinite please see my earlier post.

~~If anyone has the mathematical proof/derivation of why/how the relation number%9 == 1 is true for all the positive integers, please use the comment facility of this blog to enlighten me and the readers of the blog.~~

Please see the comment made my Mohit Nanda or visit Digital Root from Wolfram MathWorld (http://mathworld.wolfram.com/DigitalRoot.html) for the mathematical details of this relation.

Mohit NandaYes your conditional-check is correct and here is the mathematics associated with it.

1. The sum of digits of number, recursively, until the result is a single digit number is called “Digital Root”[1] of a number.

The formula[1] to calculate Digital Root of a non-zero integer is `DigitalRoot(n) = n MOD 9`

2. By your problem statement, a Magic Number is a number whose Digital Root is 1.

With this new information, the solution to your problem involves checking if Digital root of a given number N is 1 i.e.

-> DigitalRoot(N) == 1

-> N % 9 ==1

[1] Digital Root from Wolfram MathWorld, http://mathworld.wolfram.com/DigitalRoot.html

Vinay SinghPost authorThank you Mohit for spending your valuable time on Digital Roots!

🙂

Pingback: Composite Magic Number.Solved ISC 2014, Computer Science Practical