A narcissistic number is a integer where the sum of each digit raised to the power of the number of digits equals the number itself. For example, 153 is narcissistic: it has three digits 1, 5 and 3, and 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.
The goal of the program is to print the first 25 narcissistic numbers.
The algorithm is fairly simple
- Look at each positive integer in turn
- Find number of digits
- Sum up each digit raised to the power of the number of digits
- Compare to the number and if equals, print it
- Stop after 25 narcissistic numbers found
To find the number of digits we can convert the number to a string and take its length. To extract each digit we need to divide by 10, take the integer part and multiply by 10 again and subtract the original number as there is no modulus operator.
100 rem UM BASIC program to print the first 25 narcissistic numbers 110 let c = 0 /* Count of narcissistic numbers found 120 * 130 rem Start of loop to find and print narcissistic numbers 140 for n = 0 to 10000000 /* Number to check for narcissism 150 if c >= 25 then: stop /* End after 25 numbers 160 * 170 let nn = nts(n) /* Number as a string 180 let d = len(nn) /* Number of digits 190 let x = n /* Copy of number 200 let y = 0 /* Result of narcissistic calculation 210 * 220 rem Start of loop to calculate narcissistic number 230 for i = 1 to d /* For each digit 240 let x1 = int(x/10) /* Get all but last digit of x 250 let x0 = x - (10 * x1) /* Get last digit of x 260 let y = y + (x0 ** d) /* Accumulate digit ** num digits 270 let x = x1 /* Shift off last digit from x 280 next i 290 * 300 if int(y) <> n then 400 /* Not a narcissistic number, jump next 310 print n /* Print narcissistic number 320 let c = c + 1 /* Increase count found 330 * 400 next n /* Try next number 410 * 500 stop /* Fall through
And here's the output:
0 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315
Unfortunately this takes a long time to run - 6 minutes and 46 seconds of CPU time - so let's see how we can improve this.
There are several optimisations we can try:
a ** b, for a and b between 0 and 9, as we do this for each digit in the inner loop and it is likely to be an expensive operation. The precomputed powers are stored in a 2D matrix
pby the routine starting on line 600. This saves 123 seconds.
- Exit early from the calculation inner loop when the accumulated total is larger than the number being tested. This saves 32 seconds.
- Use integer comparison to find the number of digits rather than converting to a string. This saves 54 seconds.
Here's the final listing, taking 3m17s. There are probably further optimisations that can be made - any suggestions?
100 rem UM BASIC program to print the first 25 narcissistic numbers 110 rem Second, faster version 120 * 130 let c = 0 /* Count of narcissistic numbers found 140 dim p(9, 9) /* p(x, y) will contain x ** y 150 gosub 600 /* Precompute p 160 * 170 rem Start of loop to find and print narcissistic numbers 180 for n = 0 to 10000000 /* Number to check for narcissism 190 if c >= 25 then: stop /* End after 25 numbers 200 * 210 gosub 700 /* Get number of digits in d 220 let x = n /* Copy of number 230 let y = 0 /* Result of calculation 240 * 250 rem Start of loop to calculate narcissistic number 260 for i = 1 to d /* For each digit 270 let x1 = int(x/10) /* Get all but last digit of x 280 let x0 = x - (10 * x1) /* Get last digit of x 290 let y = y + p(x0, d) /* Accumulate digit ** num digits 300 if y > n then 400 /* Bail out if too big already 310 let x = x1 /* Shift off last digit from x 320 next i /* Loop for next digit 330 * 340 if y <> n then 400 /* Not a narcissistic number, jump next 350 print n /* Print narcissistic number 360 let c = c + 1 /* Increase count found 370 * 400 next n /* Try next number 410 * 500 stop /* Fall through 510 * 520 * 599 rem Subroutine to populate p(a, b) with a ** b 600 for a = 0 to 9 /* Digit 610 p(a, 0) = 0 /* a ** 0 = 0 620 p(a, 1) = a /* a ** 1 = a 630 for b = 2 to 9 /* Power to raise to 640 p(a, b) = p(a, b-1) * a /* Calc next power in series 650 next b /* Loop power 660 next a /* Loop digit 670 return 698 * 699 rem Subroutine to get number of digits in n 700 if n >= 1000000 then 800 710 if n >= 100000 then 810 720 if n >= 10000 then 820 730 if n >= 1000 then 830 740 if n >= 100 then 840 750 if n >= 10 then 850 760 goto 860 800 let d = 7 801 return 810 let d = 6 811 return 820 let d = 5 821 return 830 let d = 4 831 return 840 let d = 3 841 return 850 let d = 2 851 return 860 let d = 1 861 return
Closing thoughts on BASIC
The strength and weaknesses of the BASIC language are that it is, well, basic. With only a handful of features it is hard to get lost, but doing anything more complex than the above would be painful. From a modern programming viewpoint, the need for line numbers, restrictions on variable names and lack of types makes it quite different from what we would do now so despite some nostalgia for 80s home computing I can see why this is a bad choice for even a beginner's programming language today. But it's also clear to see how revolutionary BASIC was when first introduced and how it opened the door to programming for a whole new set of people.
Likewise, the self contained environment for UM BASIC makes it easy to start writing code without having to know much about MTS, but you lose the access to useful tools like a full screen editor. I think this, and the fact that better languages were available, explains why BASIC was not a popular choice for general users of MTS - according to Introduction to programming and debugging in MTS, only 2% by frequency of use in 1984.
There's more on the mathematics of narcissistic numbers at Wolfram MathWorld.
Source code for these programs can be found on Github.