Narcissistic Numbers

-
The Narcissistic Numbers are just a toy in number theory. They are defined as follows: given a number M = d1d2...dn, M is said to be "Narcissistic" if and only if:

d1^n + d2^n + ... + dn^n = M.

For example, 153 is a very well-known Narcissistic Number since 1^3 + 5^3 + 3^3 = 153. There is a Numberphile video that talks about this number too.

These numbers, unlike many other sequences in Math, are finite: there are only 89 of those numbers, all listed here.

In this post I'll consider two other related sequences of numbers, but not as "glamorous" as Narcissistic Numbers. The sequences will be the Quasi-Narcissistic-Numbers or QNN, and the Retro-Narcissistic-Numbers or RNN.

Let's define QNN first. A number M=d1d2...dn is said to be a QNN if and only if:

a) It is not a Narcissistic Number
b) It follows the same properties as the Narcissistic Numbers except that one, and only one, of the exponents in d1^n + d2^n + ... + dn^n is off by one.

What (b) above means is that there is an "error" and one (and only one) of the exponents must be off by one. That's why the number is said to be "Quasi" Narcissistic, or "Almost" Narcissistic. For example, the number 135 is a QNN because 1^3+3^2+5^3 = 135.

Let's now define RTT. A number M=d1d2...dn is said to be a RNN if and only if:

a) It is not a Narcissistic Number
b) n^d1 + n^d2 + ... + n^dn = M

As you can see we're now inverting the property and instead of raising the digit to the number of digits, we "retro" that and raise the number of digits to each digit, and then sum them all up.

OK, so the challenge is to find all the QNN and RNN numbers up to 12 digits long.

The idea will be a brute-force DFS with aggressive tree-pruning. The code for both QNN and RNN are below, they are very similar, but I'll explain the QNN since it is more convoluted than the RNN.

First, store all the real Narcissistic Numbers in memory; remember, we're talking about 89 numbers only. Put those in a hash-table, you'll need them to compare with the QNN and RNN.
The algorithm then does a recursive DFS call going thru all digits and trying to create a QNN (it is called a constructive algorithm). The moment that we exceed the max number of digits, it is pointless to continue since from that point onward the sum will always exceed the max number of digits. The only tricky part for the RNN construction is to keep track of the "erroneous" exponent: you need to have at least one, and when trying the "error" one, you need to try it being off by adding one, or being off by subtracting one. When you find a QNN (and RNN), you need to ensure that the number is not one one the 89 Narcissistic numbers: numbers such as 153, which is Narcissistic, could also be a QNN since

1^4 + 5^3 + 3^3 = 153

That's why we have condition (a) for both QNN and RNN. Here is the result for all the digits up to 12 digits long. Notice that there is one, and only one, RNN: 4624. You can check for yourself.

---------------------------------------
Processing N=1

Found false QNN (because it is also an NN): 0
Found false QNN (because it is also an NN): 1

For N=1, Found 0 Quasi-Narcissistic Numbers

Found false RNN (because it is also an NN): 1

For N=1, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=2

Found QNN: 24
Found QNN: 43
Found QNN: 63
Found QNN: 89

For N=2, Found 4 Quasi-Narcissistic Numbers


For N=2, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=3

Found false QNN (because it is also an NN): 370
Found false QNN (because it is also an NN): 407
Found false QNN (because it is also an NN): 153
Found false QNN (because it is also an NN): 371
Found QNN: 135
Found QNN: 175
Found QNN: 935
Found QNN: 445

For N=3, Found 4 Quasi-Narcissistic Numbers


For N=3, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=4

Found false QNN (because it is also an NN): 8208
Found false QNN (because it is also an NN): 1634
Found QNN: 8825
Found QNN: 3543
Found QNN: 9947
Found QNN: 5858

For N=4, Found 4 Quasi-Narcissistic Numbers

Found RNN: 4624

For N=4, Found 1 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=5

Found false QNN (because it is also an NN): 93084
Found QNN: 64730
Found QNN: 70478
Found QNN: 17133
Found QNN: 64731
Found QNN: 69146
Found QNN: 92348
Found QNN: 27549
Found QNN: 38456

For N=5, Found 8 Quasi-Narcissistic Numbers


For N=5, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=6

Found QNN: 285610
Found QNN: 285054
Found QNN: 770593
Found QNN: 285611
Found QNN: 586813
Found QNN: 985972
Found QNN: 626339
Found QNN: 697332
Found QNN: 548348
Found QNN: 357586

For N=6, Found 10 Quasi-Narcissistic Numbers


For N=6, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=7

Found false QNN (because it is also an NN): 9800817
Found false QNN (because it is also an NN): 4210818
Found QNN: 9930560
Found QNN: 1637109
Found QNN: 9930561
Found QNN: 5075439
Found false QNN (because it is also an NN): 1741725
Found false QNN (because it is also an NN): 9926315
Found QNN: 5971136
Found QNN: 9631294
Found QNN: 5971263
Found QNN: 7849513
Found QNN: 7432773

For N=7, Found 9 Quasi-Narcissistic Numbers


For N=7, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=8

Found false QNN (because it is also an NN): 24678050
Found false QNN (because it is also an NN): 24678051
Found QNN: 23017585
Found QNN: 25068547
Found QNN: 45202693
Found QNN: 45593062
Found QNN: 49034374
Found QNN: 61582192
Found QNN: 45596324
Found QNN: 48782567
Found QNN: 84579856

For N=8, Found 9 Quasi-Narcissistic Numbers


For N=8, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=9

Found false QNN (because it is also an NN): 146511208
Found QNN: 690071326
Found QNN: 909380412
Found QNN: 911018395
Found false QNN (because it is also an NN): 912985153
Found QNN: 141717364
Found QNN: 391432155
Found QNN: 612489177
Found QNN: 574291863
Found QNN: 441397465
Found QNN: 586374659

For N=9, Found 9 Quasi-Narcissistic Numbers


For N=9, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=10

Found false QNN (because it is also an NN): 4679307774
Found QNN: 3787284108
Found QNN: 3790212645
Found QNN: 2431388740
Found QNN: 7649910754
Found QNN: 2268682240
Found QNN: 2431388741
Found QNN: 2268682241
Found QNN: 2784765148
Found QNN: 8343923975
Found QNN: 4496627557
Found QNN: 4985564276

For N=10, Found 11 Quasi-Narcissistic Numbers


For N=10, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=11

Found false QNN (because it is also an NN): 32164049650
Found false QNN (because it is also an NN): 40028394225
Found false QNN (because it is also an NN): 42678290603
Found false QNN (because it is also an NN): 49388550606
Found false QNN (because it is also an NN): 32164049651
Found false QNN (because it is also an NN): 94204591914
Found false QNN (because it is also an NN): 44708635679
Found QNN: 81944480970
Found QNN: 68080982873
Found QNN: 43086765960
Found QNN: 81944480971
Found QNN: 63492620319
Found QNN: 32160563934
Found QNN: 52816890475
Found QNN: 37741796530
Found QNN: 43086765961
Found QNN: 34190556764
Found QNN: 28362586840
Found QNN: 72099355864
Found false QNN (because it is also an NN): 82693916578
Found QNN: 13169481616
Found QNN: 21187783345
Found QNN: 63544991162
Found QNN: 37741796531
Found QNN: 13571665486
Found QNN: 28362586841
Found QNN: 31533495453
Found QNN: 57913773558
Found QNN: 34925423229
Found QNN: 67545267994
Found QNN: 44768926756
Found QNN: 37734456497

For N=11, Found 24 Quasi-Narcissistic Numbers


For N=11, Found 0 Retro-Narcissistic Numbers
---------------------------------------

---------------------------------------
Processing N=12

Found QNN: 368405102729
Found QNN: 571695026940
Found QNN: 571695026941
Found QNN: 668035792976
Found QNN: 637994112158
Found QNN: 438376185639

For N=12, Found 6 Quasi-Narcissistic Numbers


For N=12, Found 0 Retro-Narcissistic Numbers
---------------------------------------

Code is below. Cheers, Marcelo.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;
using System.Collections;
using System.IO;

namespace QuasiNarcissisticNumbers
{
    class Program
    {
        static void Main(string[] args)
        {
            Hashtable htNN = ReadNN("nn.txt");

            for (int numberOfDigits = 1; numberOfDigits <= 12; numberOfDigits++)
            {
                Console.WriteLine("---------------------------------------");
                Console.WriteLine("Processing N={0}", numberOfDigits);
                Console.WriteLine();
                BigInteger limit = BigInteger.Pow(10, numberOfDigits) - 1;
                int[] digits = new int[numberOfDigits];
                Hashtable htQNN = new Hashtable();
                FindQNN(limit, numberOfDigits, 0, 0, digits, 0, htNN, htQNN, false);

                int solution = 0;
                foreach (BigInteger k in htQNN.Keys)
                {
                    if ((bool)htQNN[k]) solution++;
                }

                Console.WriteLine();
                Console.WriteLine("For N={0}, Found {1} Quasi-Narcissistic Numbers", numberOfDigits, solution);
                Console.WriteLine();

                digits = new int[numberOfDigits];
                Hashtable htRNN = new Hashtable();
                FindRNN(limit, numberOfDigits, 0, 0, digits, 0, htNN, htRNN);

                solution = 0;
                foreach (BigInteger k in htRNN.Keys)
                {
                    if ((bool)htRNN[k]) solution++;
                }

                Console.WriteLine();
                Console.WriteLine("For N={0}, Found {1} Retro-Narcissistic Numbers", numberOfDigits, solution);
                Console.WriteLine("---------------------------------------");
                Console.WriteLine();
            }
        }

        static Hashtable ReadNN(string fileName)
        {
            Hashtable htNN = new Hashtable();
            FileInfo fi = new FileInfo(fileName);
            StreamReader sr = fi.OpenText();
            while (!sr.EndOfStream)
            {
                string line = sr.ReadLine().Trim();
                string[] parts = line.Split(',');
                foreach (string part in parts)
                {
                    BigInteger n = BigInteger.Parse(part);
                    if (!htNN.ContainsKey(n))
                    {
                        htNN.Add(n, true);
                    }
                }
            }
            sr.Close();

            return htNN;
        }

        static bool FindQNN(BigInteger limit,
                            int numberOfDigits,
                            int currentDigitIndex,
                            int currentDigit,
                            int[] digits,
                            BigInteger currentNumber,
                            Hashtable htNN,
                            Hashtable htQNN,
                            bool errorIntroduced)
        {
            if (currentNumber.ToString().Length > limit)
            {
                return false;
            }

            if (currentDigitIndex >= numberOfDigits)
            {
                if (!errorIntroduced) return true;

                //Check
                int[] arrayCount = new int[10];
                for (int i = 0; i < currentDigitIndex; i++)
                {
                    arrayCount[digits[i]]++;
                }

                if (currentNumber == 0)
                {
                    arrayCount[(int)currentNumber]--;
                }
                else
                {
                    BigInteger temp = currentNumber;
                    while (temp > 0)
                    {
                        int tIndex = (int)(temp % 10);
                        temp /= 10;
                        arrayCount[tIndex]--;
                    }
                }
                for (int i = 0; i < arrayCount.Length; i++)
                {
                    if (arrayCount[i] != 0)
                    {
                        return true;
                    }
                }
                if (!htQNN.ContainsKey(currentNumber))
                {
                    if (htNN.ContainsKey(currentNumber))
                    {
                        Console.WriteLine("Found false QNN (because it is also an NN): {0}", currentNumber);
                        htQNN.Add(currentNumber, false);
                    }
                    else
                    {
                        Console.WriteLine("Found QNN: {0}", currentNumber);
                        htQNN.Add(currentNumber, true);
                    }
                }
                return true;
            }

            for (int i = currentDigit; i < 10; i++)
            {
                digits[currentDigitIndex] = i;
                if (errorIntroduced)
                {
                    if (!FindQNN(limit, numberOfDigits, currentDigitIndex + 1, i, digits, currentNumber + BigInteger.Pow(i, numberOfDigits), htNN, htQNN, true)) return false;
                }
                else
                {
                    //Intro error - lower exp
                    if (!FindQNN(limit, numberOfDigits, currentDigitIndex + 1, i, digits, currentNumber + BigInteger.Pow(i, numberOfDigits - 1), htNN, htQNN, true)) return false;
                    //Dont
                    if (!FindQNN(limit, numberOfDigits, currentDigitIndex + 1, i, digits, currentNumber + BigInteger.Pow(i, numberOfDigits), htNN, htQNN, false)) return false;
                    //Intro error - higher exp
                    if (!FindQNN(limit, numberOfDigits, currentDigitIndex + 1, i, digits, currentNumber + BigInteger.Pow(i, numberOfDigits + 1), htNN, htQNN, true)) return false;
                }
            }

            return true;
        }

        static bool FindRNN(BigInteger limit,
                            int numberOfDigits,
                            int currentDigitIndex,
                            int currentDigit,
                            int[] digits,
                            BigInteger currentNumber,
                            Hashtable htNN,
                            Hashtable htRNN)
        {
            if (currentNumber.ToString().Length > limit)
            {
                return false;
            }

            if (currentDigitIndex >= numberOfDigits)
            {
                //Check
                int[] arrayCount = new int[10];
                for (int i = 0; i < currentDigitIndex; i++)
                {
                    arrayCount[digits[i]]++;
                }

                if (currentNumber == 0)
                {
                    arrayCount[(int)currentNumber]--;
                }
                else
                {
                    BigInteger temp = currentNumber;
                    while (temp > 0)
                    {
                        int tIndex = (int)(temp % 10);
                        temp /= 10;
                        arrayCount[tIndex]--;
                    }
                }
                for (int i = 0; i < arrayCount.Length; i++)
                {
                    if (arrayCount[i] != 0)
                    {
                        return true;
                    }
                }
                if (!htRNN.ContainsKey(currentNumber))
                {
                    if (htNN.ContainsKey(currentNumber))
                    {
                        Console.WriteLine("Found false RNN (because it is also an NN): {0}", currentNumber);
                        htRNN.Add(currentNumber, false);
                    }
                    else
                    {
                        Console.WriteLine("Found RNN: {0}", currentNumber);
                        htRNN.Add(currentNumber, true);
                    }
                }
                return true;
            }

            for (int i = currentDigit; i < 10; i++)
            {
                digits[currentDigitIndex] = i;
                if (!FindRNN(limit, numberOfDigits, currentDigitIndex + 1, i, digits, currentNumber + BigInteger.Pow(numberOfDigits, i), htNN, htRNN)) return false;
            }

            return true;
        }
    }
}

Comments

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

-
Image
If you work with graphics and eventually you want to pivot a binary tree using a different node as the root, this might be interesting to you. Here is the problem:  Change the Root of a Binary Tree - LeetCode 1666. Change the Root of a Binary Tree Medium 6 14 Add to List Share Given the  root  of a binary tree and a  leaf  node, reroot the tree so that the  leaf  is the new root. You can reroot the tree with the following steps for each node  cur  on the path  starting from the  leaf  up to the  root ​​​  excluding the root : If  cur  has a left child, then that child becomes  cur 's right child. Note that it is guaranteed that  cur  will have at most one child. cur 's original parent becomes  cur 's left child. Return  the new root  of the rerooted tree. Note:  Ensure that your solution sets the  Node.parent  pointers correctly after rerooting or you will receive "Wrong Answer".   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7 Output: [7,2,nul
Read more

Prompt Engineering and LeetCode

-
Image
With AI it becomes super interesting to try to "guide" it to solve a coding (LeetCode) problem. An example would be this one here:  The Knight’s Tour - LeetCode 2664. The Knight’s Tour Medium 11 0 Add to List Share Given two positive integers  m  and  n  which are the height and width of a  0-indexed  2D-array  board , a pair of positive integers  (r, c)  which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the  board  gets visited  exactly  once (the starting cell is considered visited and you  shouldn't  visit it again). Return  the array   board   in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight). Note that a  knight  can  move  from cell  (r1, c1)  to cell  (r2, c2)  if  0 <= r2 <= m - 1  and  0 <= c2 <= n - 1  and  min(abs(r1 - r2), abs(c1 - c2)) = 1  and  max(abs(r1 - r2), abs(c1 - c2)) = 2 .  
Read more

ProjectEuler Problem 719 (some hints, but no spoilers)

-
Image
Last time that I solved a ProjectEuler (PE) problem was in 2015... This is their latest problem as of today:  https://projecteuler.net/problem=719 Number Splitting        Problem 719 We define an  S S -number to be a natural number,  n n , that is a perfect square and its square root can be obtained by splitting the decimal representation of  n n  into 2 or more numbers then adding the numbers. For example, 81 is an  S S -number because  81 − − √ = 8 + 1 81 = 8 + 1 . 6724 is an  S S -number:  6724 − − − − √ = 6 + 72 + 4 6724 = 6 + 72 + 4 . 8281 is an  S S -number:  8281 − − − − √ = 8 + 2 + 81 = 82 + 8 + 1 8281 = 8 + 2 + 81 = 82 + 8 + 1 . 9801 is an  S S -number:  9801 − − − − √ = 98 + 0 + 1 9801 = 98 + 0 + 1 . Further we define  T ( N ) T ( N )  to be the sum of all  S S  numbers  n ≤ N n ≤ N . You are given  T ( 10 4 ) = 41333 T ( 10 4 ) = 41333 . Find  T ( 10 12 ) The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat abo
Read more