C++でデューデニー数（Dudeney Number）を判定する方法

デューデニー数とは？

デューデニー数（Dudeney Number）とは、数論で定義される特殊な自然数の一つです。「ある自然数が、別の自然数の完全立方数に等しく、かつ元の数の各桁の数字和が、その立方根となる数の桁和と一致する」とき、その数をデューデニー数と呼びます（Wikipediaより）。

この数は、イギリスの著名なパズル作家であるヘンリー・デューデニー（Henry Dudeney）によって発見されました。数学的には次の式で表されます。

有名な例としては 512 = 8³ が挙げられます。512 の桁和は 5 + 1 + 2 = 8 となり、立方根である 8 と一致するため、512 はデューデニー数です。

本記事では、与えられた整数 n に対して、「n がデューデニー数であるかどうかを判定する」プログラムを C++ で実装します。

問題の例

入力：N = 17592

出力：No

説明：

この数はデューデニー数ではありません。

解法のアプローチ

解法の鍵は、デューデニー数の基本的な定義にあります。すなわち、「ある数の立方根が、その数自身の桁の和と等しい」とき、その数はデューデニー数であるという性質を利用します。

アルゴリズム

ステップ1：n が完全立方数であるかどうかを確認します。

ステップ2.1：完全立方数である場合、n の立方根が n の桁和と等しいかを確認します。

ステップ2.2.1：等しい場合、その数はデューデニー数です。

ステップ2.2.2：等しくない場合、その数はデューデニー数ではありません。

ステップ2.2：完全立方数でない場合も、その数はデューデニー数ではありません。

C++による実装例

以下は、上記アルゴリズムの動作を示す C++ プログラムです。

#include <bits/stdc++.h>
using namespace std;

int calcDigitSum(int n){

    int digitSum = 0;
    int digitVal;
    while (n > 0) {
        digitVal = n % 10;
        digitSum += digitVal;
        n /= 10;
    }
    return digitSum;
    
}
int checkDudeney(int N) {
    
    int cubeRoot = int( round( cbrt(N) ) );
    
    if(pow(cubeRoot, 3.0) != N){
        return 0;
    }

    int sumOfDigit = calcDigitSum(N);
    
    if (cubeRoot != sumOfDigit)
        return 0;

    return 1;
}

int main() {
    int N = 104323;
    cout<<"The number "<<N;
    if (checkDudeney(N))
        cout<<" is a dudeney number.";
    else
        cout<<" is not a dudeney number.";
    return 0;
}

出力結果

The number 104323 is not a dudeney number.

まとめ

このように、デューデニー数の判定は「完全立方数であること」と「立方根と桁和の一致」という2つの条件を順に確認するだけで実装できます。計算量も少なく、シンプルな数学的性質を活かした美しいアルゴリズムと言えるでしょう。