M.Hiroi's Home Page

Memorandum

プログラミングに関する覚え書や四方山話です。
[ Home | 2023年 1月, 2月, 5月 ]

2023 年 5 月

5月27日

●ナルシシスト数

n 桁の自然数 m において、各桁の n 乗の和が m に等しい数を「ナルシシスト数 (narcissistic number)」といいます。定義により 1 桁の数 (1 - 9) はナルシシスト数になります。2 桁のナルシシスト数はありませんが、3 桁のナルシシスト数は以下の 4 つがあります。

153 = 13 + 53 + 33 = 1 + 125 + 27 = 153
370 = 33 + 73 + 03 = 27 + 343 + 0 = 370
371 = 33 + 73 + 13 = 27 + 343 + 1 = 371
407 = 43 + 03 + 73 = 64 + 0 + 343 = 407

ナルシシスト数は有限個しかありません。n 桁のナルシシスト数の最小値は 10n-1 で、最大値は n * 9n です。ナルシシスト数が存在するには次の不等式が成立しないといけません。

10n-1 <= n * 9n

両辺を 9n-1 で割ると以下の式になります。

(10 / 9)n-1 <= 9 * n

n が小さいとき上式は成立しますが、n が大きくなると指数関数の値は爆発的に増加するので、上式はいづれ不成立になります。具体的には n が 60 を超えると不成立になります。

n = 60: (10 / 9)59 = 500.8327, 9 * 60 = 540, 成立
n = 61: (10 / 9)60 = 556.4808, 9 * 61 = 549, 不成立

●プログラムの作成

ナルシシスト数を求める場合、たとえば 4 桁のナルシシスト数であれば、1000 - 9999 までの整数値を順番に生成し、各桁の 4 乗和の計算結果が元の整数と等しければ、その数はナルシシスト数と判定することができます。ただし、この方法はとても非効率です。1634 は 4 桁のナルシシスト数ですが、それ以外の数字の並び方 (23 通り) はナルシシスト数にはなりません。

各桁の n 乗和は数字の並びに関係なく計算することができるので、この場合は 0 - 9 から n 個の数字を選ぶ重複組み合わせを求めたほうが効率的です。選んだ数字の組み合わせから整数値を生成し、その値を桁ごとに分解した結果、元の組み合わせと同じであれば、その数をナルシスト数と判定することができます。

重複組み合わせを生成するプログラムを Python3 で作ると次のようになります。

リスト : 重複組み合わせの生成

def combinations(f, n, m, a):
    if n == 0:
        f(a)
    elif m < len(a):
        a[m] += 1
        combinations(f, n - 1, m, a)
        a[m] -= 1
        combinations(f, n, m + 1, a)

関数 combinations は、0 から len(a) 未満の数字から n 個の数字を選ぶ重複組み合わせを生成します。選択した数字の個数は引数の配列 a に格納します。引数 m が選ぶ数字を表します。n が 0 ならば組み合わせを一つ生成したので、引数の関数 f を呼び出します。

m が len(a) よりも小さければ、数字 m を選ぶことができます。a[m] の個数を +1 してから、combinations を再帰呼び出しします。そのあと、a[m] を -1 してから m を選ばない組み合わせを生成します。

簡単な実行例を示します。

>>> combinations(print, 2, 0, [0,0])
[2, 0]
[1, 1]
[0, 2]
>>> combinations(print, 3, 0, [0,0])
[3, 0]
[2, 1]
[1, 2]
[0, 3]
>>> combinations(print, 3, 0, [0,0,0])
[3, 0, 0]
[2, 1, 0]
[2, 0, 1]
[1, 2, 0]
[1, 1, 1]
[1, 0, 2]
[0, 3, 0]
[0, 2, 1]
[0, 1, 2]
[0, 0, 3]

n 乗和と数値を桁に分解するプログラムも簡単です。プログラムと実行例を示します。

リスト : n 乗和と数の分解

# n 乗和
def power_sum(n, a):
    return sum([x * (i ** n) for i, x in enumerate(a)])

# 数値を桁ごとに分解
def split_digit(n):
    a = [0] * 10
    while n > 0:
        a[n % 10] += 1
        n //= 10
    return a
>>> split_digit(1634)
[0, 1, 0, 1, 1, 0, 1, 0, 0, 0]
>>> power_sum(4, split_digit(1634))
1634
>>> split_digit(45678)
[0, 0, 0, 0, 1, 1, 1, 1, 1, 0]
>>> power_sum(5, split_digit(45678))
61500

最後に n 桁のナルシシスト数を求める関数 solver を作ります。

リスト : n 桁のナルシシスト数を求める

def solver(n):
    def check(a):
        x = power_sum(n, a)
        b = split_digit(x)
        if a == b: print(x)
    combinations(check, n, 0, [0] * 10)

combinations に局所関数 check を渡して呼び出します。生成した組み合わせは check の引数 a に渡されます。power_sum で累乗輪を求めて変数 x にセットし、split_digit で x を桁ごとに分解して変数 b にセットします。a と b が等しければ、x はナルシシスト数です。print で x を表示します。

それでは実行してみましょう。使用する処理系は PyPy3 です。

$ pypy3 --version
Python 3.8.13 (7.3.9+dfsg-1, Apr 01 2022, 21:41:47)
[PyPy 7.3.9 with GCC 11.2.0]
>>>> from narci import *
>>>> import time
>>>> for x in range(1, 19):
....     print('-----', x, '-----')
....     s = time.time()
....     solver(x)
....     e = time.time()
....     print(e - s)
....
----- 1 -----
1
2
3
4
5
6
7
8
9
0.0016078948974609375
----- 2 -----
0.0008893013000488281
----- 3 -----
370
407
153
371
0.009445667266845703
----- 4 -----
8208
1634
9474
0.018713951110839844
----- 5 -----
93084
92727
54748
0.024398088455200195
----- 6 -----
548834
0.004481315612792969
----- 7 -----
9800817
4210818
1741725
9926315
0.01246333122253418
----- 8 -----
24678050
24678051
88593477
0.018772125244140625
----- 9 -----
146511208
912985153
472335975
534494836
0.038550615310668945
----- 10 -----
4679307774
0.08915567398071289
----- 11 -----
32164049650
40028394225
42678290603
49388550606
32164049651
94204591914
44708635679
82693916578
0.13814592361450195
----- 12 -----
0.21680974960327148
----- 13 -----
0.3555634021759033
----- 14 -----
28116440335967
0.5982820987701416
----- 15 -----
0.9512383937835693
----- 16 -----
4338281769391370
4338281769391371
1.538985252380371
----- 17 -----
35875699062250035
21897142587612075
35641594208964132
2.4040043354034424
----- 18 -----
3.643921375274658

18 桁程度であれば PyPy でもナルシシスト数を簡単に求めることができるようです。これ以上桁数を増やすには、より高速なプログラミング言語を使う、何かしらの枝刈りを入れる、あるいはその両方を行う必要があると思います。参考 URL 3 によると、ナルシシスト数は全部で 88 個あり、最大桁数は 39 になるそうです。deepgreen さんは、参考 URL 1 ですべてのナルシシスト数を求めています。興味のある方は挑戦してみてください。

●参考 URL

  1. 計算パズル集, (deepgreen さん)
  2. ナルシシスト数について | 高校数学の美しい物語, (マスオさん)
  3. ナルシシスト数 -- Wikipedia

2023 年 2 月

2月15日

●複素数の逆双曲線関数

複素数 z の逆双曲線関数 acosh(z) の定義に式 (2) を追記しました。

asinh z = log (z + √(z2 + 1))
acosh z = log (z + √(z2 - 1)) -- (1)
        = log (z + (√(z + 1)) * (√(z - 1))) -- (2)
atanh z = (1 / 2) * log((1 + z) / (1 - z))
        = (1 / 2) * (log(1 + z) - log(1 - z))

参考 URL 2 によると、acosh(z) を式 1 でプログラムすると「分枝切断線」が複雑になるため、他の式 (たとえば式 2 など) でプログラムする処理系が多いようです。ちなみに、ANSI Common Lisp では acosh(z) を次の式で定義しています。

acosh(z) = 2 * log(sqrt((z + 1)/2) + sqrt((z - 1)/2))

●参考 URL

  1. 逆双曲線関数 - Wikipedia
  2. 逆双曲線関数と逆三角関数の branch cut | 雑記帳

2月8日

●フォントの優先順位

Linux のフォントはライブラリ fontconfig を使って管理されています。ユーザーがフォントの優先順位を変更するときは、fontconfig の設定ファイル ~/.config/fontconfig/fonts.conf で行うことができるようです。詳しい説明は fonts.conf のドキュメント (man fonts-conf) や下記 URL をお読みください。

  1. fonts-conf, (ドキュメントの HTML 版)
  2. フォント設定 - ArchWiki
  3. フォント設定/サンプル - ArchWiki
  4. manjaro linux の日本語フォントを直す - 雑記帳, (にゃおみんさん)

M.Hiroi は URL 3, 4 を参考に、fonts.conf を下記のように定義したところ、設定を Noto フォントに変更することができました。

リスト : fonts.conf

<?xml version='1.0'?>
<!DOCTYPE fontconfig SYSTEM 'fonts.dtd'>
<fontconfig>

<!-- Default font (no fc-match pattern) -->
 <match>
  <edit mode="prepend" name="family">
   <string>Noto Sans CJK JP</string>
  </edit>
 </match>

<!-- Default font for the ja_JP locale (no fc-match pattern) -->
 <match>
  <test compare="contains" name="lang">
   <string>ja</string>
  </test>
  <edit mode="prepend" name="family">
   <string>Noto Sans CJK JP</string>
  </edit>
 </match>

<!-- Default sans-serif font -->
 <match target="pattern">
   <test qual="any" name="family"><string>sans-serif</string></test>
   <edit name="family" mode="prepend" binding="same"><string>Noto Sans CJK JP</string>  </edit>
 </match>

<!-- Default serif fonts -->
 <match target="pattern">
   <test qual="any" name="family"><string>serif</string></test>
   <edit name="family" mode="prepend" binding="same"><string>Noto Serif CJK JP</string>  </edit>
 </match>

<!-- Default monospace fonts -->
 <match target="pattern">
   <test qual="any" name="family"><string>monospace</string></test>
   <edit name="family" mode="prepend" binding="same"><string>Noto Sans Mono CJK JP</string></edit>
 </match>
</fontconfig>
$ fc-match
NotoSansCJKjp-Regular.otf: "Noto Sans CJK JP" "Regular"
$ fc-match sans
NotoSansCJKjp-Regular.otf: "Noto Sans CJK JP" "Regular"
$ fc-match serif
NotoSerifCJKjp-Regular.otf: "Noto Serif CJK JP" "Regular"
$ fc-match mono
NotoSansMonoCJKjp-Regular.otf: "Noto Sans Mono CJK JP" "Regular"

2023 年 1 月

1月11日

●Wayland

Wayland は X Window System (X11) の後継を目指して開発されている通信プロトコル (初版 2008 年 9 月) です。Weston というリファレンス実装も公開されています。Wayland だけでは今までの X11 アプリケーションが動作しないので、XWayland という X サーバー互換の機能も用意されています。

現在、ほとんどの Linux ディストリビューションが Wayland に対応しています。GUI ツールキットでも、GTK 3.0 や Qt 5 など多くのツールキットが対応済みです。そして、WSLg が Wayland (Weston) を採用しています。

M.Hiroi が Wayland のことを知ったのは WSL2 + WSLg を使うようになってからです。WSLg で X11 アプリが動作するのは、中で X サーバーが動いているからだと思っていました。実際には、X サーバーではなく WayLand の XWayland が機能していたわけです。Wayland のことはよくわかっていないので、参考 URL を読んで勉強してみようかなと思っています。

●参考 URL

  1. Wayland, (英語)
  2. GitHub: microsoft/wslg, (英語)
  3. X11 and Wayland Applications in WSL (PDF), (英語)
  4. Wayland - 通信用語の基礎知識
  5. Wayland - ArchWiki
  6. Wayland - Wikepedia

1月7日

●Ubuntu 22.04 LTS

お正月ということで、あらためて Ubunts 22.04 LTS を WSL にインストールしてみました。今回は日本語の設定もうまくいきました。

sudo apt install language-pack-ja
sudo update-locale LANG=ja_JP.UTF8
sudo apt install manpages-ja
sudo apt install manpages-ja-dev
sudo apt install fontconfig

なお、WSL の Ubuntu には日本語フォントがインストールされていません。昔の Ubuntu は日本語フォントに Takao フォントが用いられてきましたが、Ubuntu 18.04 からは Noto フォントになりました。Noto Sans CJK JP がゴシック体、Noto Serif CJK JP が明朝体になります。

これらのフォントは apt で簡単にインストールすることができます。

sudo apt install fonts-not-cjk

もう一つ方法があって、WSL から Windows のフォントを利用することもできます。フォントのインストールは次のページが参考になると思います。

  1. Windows11 WSL2 & WSLg Ubuntu の初期設定, (hiro20180901 さん)
  2. How to install fonts on Linux, (妹尾 賢 さん)

M.Hiroi は Windows に Noto フォントをインストールしてあるので、1 の方法を使わせてもらいました。有益な情報を公開されてる作者様に感謝いたします。

ところが、フォントの優先順位が Ubuntu 20.04 と Ubuntu 22.04 で異なっているようです。Ubuntu 20.04 で fc-match を実行すると Noto Sans CJK JP になったのですが、Ubuntu 22.04 では次のようになります。

$ fc-match
msgothic.ttc: "MS ゴシック" "標準"
$ fc-match sans
msgothic.ttc: "MS ゴシック" "標準"
$ fc-match serif
msmincho.ttc: "MS 明朝" "標準"
$ fc-match mono
msgothic.ttc: "MS ゴシック" "標準"

フォントの優先順位は変更できると思うのですが、Linux のことは勉強不足でよくわかりませんでした。Noto フォントを使いたい場合、各々のアプリケーション (Tcl/Tk や Python/Tkinter など) でフォントを指定する、または、Windows 側のフォントを使わずに、Ubuntu 側にフォントをインストールしたほうが簡単なのかもしれませんね。


1月1日

あけましておめでとうございます

旧年中は大変お世話になりました
本年も M.Hiroi's Home Page をよろしくお願い申し上げます


Copyright (C) 2023 Makoto Hiroi
All rights reserved.

[ Home ]