阿姆斯壯數

說明

在n位的整數中，若加總每個數字的n次方後等於該整數，該整數稱為阿姆斯壯數（Armstrong number），又稱自戀數（Narcissistic number）（因為各數字n次方後加總又等於本身，感覺很自戀？）。例如153可以滿足1³ + 5³ + 3³ = 153，153就是個阿姆斯壯數，阿姆斯壯數有88個，最大為39位數的 115132219018763992565095597973971522401，已證實超過39位數不存在阿姆斯壯數。

解法

阿姆斯壯數的尋找，基本上是在問如何將一個數字分解為個位數、十位數、百位數......，這只要使用除法與餘數運算就可以了，例如要找出所有三位數阿姆斯壯數。輸入input為n位數，則可如下分解出位數：

個位 (input / 10⁰) % 10
十位 (input / 10¹) % 10
百位 (input / 10²) % 10
...
n 位 (input / 10^n-1) % 10

底下列出的實作僅逐一列舉數字並判斷是否為阿姆斯壯數，位數大時求解時間會急劇拉長。可改進的方法之一：

對於同樣為n位數而言，數字的n次方重複運算是不必要的，這部份可先製表而後直接查表並進行加總（像是Java實作中的例子）。
進行數字裁剪，將同為n位數的數劃分為數個集合，將尋找阿姆斯壯數縮剪為尋找包括阿姆斯壯數的集合。例如3位數中，122、212、221會屬於同一集合（因此需要搭配快速排列組合），詢問此集合是否包括1³ + 2³ + 2³ = 17則答案為否（因而需要搭配有序集合以快速確認是否包括），而135、315、153屬於同一集合，詢問此集合是否包括1³ + 3³ + 5³ = 153則答案為是，則153為阿姆斯壯數，在位數多時，可藉由集合裁剪掉大量單獨數字加總後測試的需求，從而加快求解速度。

實作：C Java Python Scala Ruby JavaScript Haskell

#include <stdio.h> 
#include <stdlib.h> 

int isNarcissistic(double);
void narcissistic(double*, int);

int main(void) { 
    double armstrongs[88] = {0};
    narcissistic(armstrongs, 3);
    int i;
    for(i = 0; armstrongs[i] != 0; i++) {
        printf("%.0f\n", armstrongs[i]);
    }
    return 0; 
} 

int isNarcissistic(double number) {
    int digits[39] = {0};
    double num = number;
    int i;
    for(i = 0; num != 0; i++) {
        digits[i] = (int) num % 10;
        num = (int) (num / 10);
    }
    double sum = 0.0;
    int j;
    for(j = 0; j <= i; j++) {
        sum += pow(digits[j], i);
    }
    return sum == number;
}

void narcissistic(double* armstrongs , int n) {
    double bound = pow(10, n < 40 ? n : 39);
    double i;
    int j;
    for(i = 0, j = 0; i < bound; i++) if(isNarcissistic(i)) {
        armstrongs[j] = i; j++;
    }
}

Java

import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;

public class Armstrong {
    private static double[][] pows;
    
    public static List<Double> narcissistic(int n) {
        pows = new double[n + 1][];
        pows[1] = new double[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        for(int i = 2; i <= n; i++) {
            pows[i] = new double[] {
                0, 1, pows[i - 1][2] * 2, pows[i - 1][3] * 3, 
                pows[i - 1][4] * 4, pows[i - 1][5] * 5, 
                pows[i - 1][6] * 6, pows[i - 1][7] * 7, 
                pows[i - 1][8] * 8, pows[i - 1][9] * 9
            };
        }
    
        List<Double> armstrongs = new ArrayList<>();
        double bound = pow(10, n < 40 ? n : 39);
        for(double i = 1; i < bound; i++) if(isNarcissistic(i)) {
            armstrongs.add(i);
        }
        return armstrongs;
    }
    
    public static boolean isNarcissistic(double number) {
        List<Integer> digits = new ArrayList<>();
        double num = number;
        while(num != 0) {
            digits.add((int) num  % 10);
            num = floor(num / 10);
        }
        double sum = 0;
        for(Integer d : digits) {
            sum += pows[digits.size()][d];
        }
        return sum == number;
    }
    

    public static void main(String[] args) {
        for(Double d : narcissistic(7)) {
            System.out.printf("%.0f%n", d);
        }
    }
}

Python

from functools import reduce

def toDigits(num):
    return [] if num == 0 else ([num % 10] + toDigits(num // 10))

def isNarcissistic(number):
    digits = toDigits(number)
    return reduce(lambda sum, d: sum + d ** len(digits), 
               digits, 0) == number

def narcissistic(n):
    return [i for i in range(1, 10 ** (n if n < 40 else 39)) 
                  if isNarcissistic(i)]

print(narcissistic(3))

Scala

import scala.math.BigInt
import scala.math.pow

def toDigits(num: BigInt): List[Int] = {
    if(num == 0) Nil else (num % 10).toInt :: toDigits(num / 10)
}

def isNarcissistic(number: BigInt) = {
    val digits = toDigits(number)
    (0 /: digits) { (sum, d) => sum + pow(d, digits.size).toInt } == number
}

def narcissistic(n: Int) = {
    for(i <- BigInt(1) until BigInt(10).pow(if(n < 40) n else 39)
        if isNarcissistic(i)) yield i
}

narcissistic(3).foreach(println _)

Ruby

def toDigits(num)
    num == 0 ? [] : ([num % 10]) + toDigits(num / 10)
end

def isNarcissistic(number)
    digits = toDigits(number)
    digits.reduce(0) {|sum, d| sum + d ** digits.size} == number
end

def narcissistic(n)
    (1...10 ** (n < 40 ? n : 39)).select {|i| isNarcissistic(i)}
end

print(narcissistic(3))

JavaScript

function isNarcissistic(number) {
    var digits = [];
    var num = number;
    while(num != 0) {
        digits.push(num  % 10);
        num = parseInt(num / 10);
    }
    var sum = 0;
    for(var i = 0; i < digits.length; i++) {
        sum += Math.pow(digits[i], digits.length);
    }
    return sum == number;
}
    
function narcissistic(n) {
    var armstrongs = [];
    var bound = Math.pow(10, n < 40 ? n : 39);
    for(var i = 1; i < bound; i++) if(isNarcissistic(i)) {
        armstrongs.push(i);
    }
    return armstrongs;
}

print(narcissistic(3));

Haskell

toDigits num =
    if num == 0 then [] else (num `mod` 10) : toDigits (num `div` 10)

isNarcissistic number = 
    number == (foldl (\sum d -> sum + d ^ (length digits)) 0 digits)
    where digits = toDigits number

narcissistic n =
    [i | i <- [1..10 ^ (if n < 40 then n else 39)], isNarcissistic(i)]

main = print \$ narcissistic 3