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

Advent of Code - Day 6, 2024: BFS and FSM

-
Image
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC. Day 6 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); List map = new List (); int startRow = 0; int startCol = 0; while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); map.Add(new StringBuilder(line)); int indexStart = line.IndexOf('^'); ...
Read more

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    G...
Read more

Advent of Code - Day 7, 2024: Backtracking and Eval

-
Image
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC. Day 7 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) r...
Read more