【数理Computingの基礎】「オイラーのφ関数」について

実際の素数の求め方はこんな感じですが「ある数までに含まれる互いに素な数字の数」なら別の計算でもっと簡単に求められます。それがオイラーのφ関数なんですね。

統計言語R上でのgmpライブラリ動作例

install.packages("gmp")
install.packages("gmp")Installing package into ‘C:/Users/81806/Documents/R/win-library/3.5’(as ‘lib’ is unspecified)trying URL 'https://cran.rstudio.com/bin/windows/contrib/3.5/gmp_0.5-13.5.zip'Content type 'application/zip' length 1110866 bytes (1.1 MB)downloaded 1.1 MB
package ‘gmp’ successfully unpacked and MD5 sums checked
The downloaded binary packages are in C:\Users\81806\AppData\Local\Temp\RtmpyQC7uP\downloaded_packages> library(gmp)
 次のパッケージを付け加えます: ‘gmp’ 
 以下のオブジェクトは ‘package:base’ からマスクされています: 
     %*%, apply, crossprod, matrix, tcrossprod 
Warning message: パッケージ ‘gmp’ はバージョン 3.5.3 の R の下で造られました
factorize(120)
Big Integer ('bigz') object of length 5:
[1] 2 2 2 3 5

統計言語R上でのgmpライブラリ動作例

factorize(12)
Big Integer ('bigz') object of length 3:
[1] 2 2 3
12*(1-1/2)*(1-1/3)
[1] 4
#実際に全列挙すれば，1,5,7,11 の 4個

factorize(90)
Big Integer ('bigz') object of length 4:
[1] 2 3 3 5
90*(1-1/2)*(1-1/3)*(1-1/5)
[1] 24

#実際に全列挙すれば，2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89の24個

それでは1桁の自然数同士の掛け合わせが2桁以内に収まってるケース、すなわち掛け算の九九で使われている数字について当て嵌めてみましょう。

2^n族
2,4,8,16,32,64の6個

factorize(2)
Big Integer ('bigz') :
[1] 2

2*(1-1/2)
[1] 2
factorize(4)
Big Integer ('bigz') object of length 2:
[1] 2 2
4*(1-1/2)
[1] 2

factorize(8)
Big Integer ('bigz') object of length 3:
[1] 2 2 2

8*(1-1/2)
[1] 4

factorize(16)
Big Integer ('bigz') object of length 4:
[1] 2 2 2 2
16*(1-1/2)
[1] 8

factorize(32)
Big Integer ('bigz') object of length 5:
[1] 2 2 2 2 2
32*(1-1/2)
[1] 16

factorize(64)
Big Integer ('bigz') object of length 6:
[1] 2 2 2 2 2 2
64*(1-1/2)
[1] 32

3^n族

3,9,27,81の4個

factorize(3)
Big Integer ('bigz') :
[1] 3
3*(1-1/3)
[1] 2

factorize(9)
Big Integer ('bigz') object of length 2:
[1] 3 3

9*(1-1/3)
[1] 6

factorize(27)
Big Integer ('bigz') object of length 3:
[1] 3 3 3
27*(1-1/3)
[1] 18

factorize(81)
Big Integer ('bigz') object of length 4:
[1] 3 3 3 3
81*(1-1/3)
[1] 54

5^n族

5,25の2個

factorize(5)
Big Integer ('bigz') :
[1] 5
5*(1-1/5)
[1] 4

factorize(25)
Big Integer ('bigz') object of length 2:
[1] 5 5
25*(1-1/5)
[1] 20 

2^m*3^n族

6,12,18,24,36,48,54,72,96の9個だが96がレンジ外（2*2*2*2*2*3が1桁の計算に収まらない）

factorize(6)
Big Integer ('bigz') object of length 2:
[1] 2 3
6*(1-1/2)*(1-1/3)
[1] 2

factorize(12)
Big Integer ('bigz') object of length 3:
[1] 2 2 3
12*(1-1/2)*(1-1/3)
[1] 4

factorize(18)
Big Integer ('bigz') object of length 3:
[1] 2 3 3
18*(1-1/2)*(1-1/3)
[1] 6

factorize(24)
Big Integer ('bigz') object of length 4:
[1] 2 2 2 3
24*(1-1/2)*(1-1/3)
[1] 8

factorize(36)
Big Integer ('bigz') object of length 4:
[1] 2 2 3 3
36*(1-1/2)*(1-1/3)
[1] 12

factorize(48)
Big Integer ('bigz') object of length 5:
[1] 2 2 2 2 3
48*(1-1/2)*(1-1/3)
[1] 16

factorize(54)
Big Integer ('bigz') object of length 4:
[1] 2 3 3 3
54*(1-1/2)*(1-1/3)
[1] 18

factorize(72)
Big Integer ('bigz') object of length 5:
[1] 2 2 2 3 3
72*(1-1/2)*(1-1/3)
[1] 24

factorize(96)
Big Integer ('bigz') object of length 6:
[1] 2 2 2 2 2 3
96*(1-1/2)*(1-1/3)
[1] 32

7^n族

7,49の2個

factorize(7)
Big Integer ('bigz') :
[1] 7
7*(1-1/7)
[1] 6

factorize(49)
Big Integer ('bigz') object of length 2:
[1] 7 7
49*(1-1/7)
[1] 42

2^m*5^m族

10,20,40,50,80の5個だが20と80がレンジ外（2*2*5と2*2**2*2*5が1桁の計算に収まらない）

factorize(10)
Big Integer ('bigz') object of length 2:
[1] 2 5
10*(1-1/2)*(1-1/5)
[1] 4

factorize(20)
Big Integer ('bigz') object of length 3:
[1] 2 2 5
20*(1-1/2)*(1-1/5)
[1] 8

factorize(40)
Big Integer ('bigz') object of length 4:
[1] 2 2 2 5
40*(1-1/2)*(1-1/5)
[1] 16

factorize(50)
Big Integer ('bigz') object of length 3:
[1] 2 5 5
50*(1-1/2)*(1-1/5)
[1] 20

factorize(80)
Big Integer ('bigz') object of length 5:
[1] 2 2 2 2 5
80*(1-1/2)*(1-1/5)
[1] 32

2^m*7^m族

14,28,56,98の4個だが98がレンジ外（2*2*2*2*7が1桁の計算に収まらない）

factorize(14)
Big Integer ('bigz') object of length 2:
[1] 2 7
14*(1-1/2)*(1-1/7)
[1] 6

factorize(28)
Big Integer ('bigz') object of length 3:
[1] 2 2 7
28*(1-1/2)*(1-1/7)
[1] 12

factorize(56)
Big Integer ('bigz') object of length 4:
[1] 2 2 2 7
56*(1-1/2)*(1-1/7)
[1] 24

factorize(98)
Big Integer ('bigz') object of length 3:
[1] 2 7 7
98*(1-1/2)*(1-1/7)
[1] 42

3^m*5^n族

15,45,75の3個だが75がレンジ外（3*5*5が1桁の計算に収まらない）

factorize(15)
Big Integer ('bigz') object of length 2:
[1] 3 5
15*(1-1/3)*(1-1/5)
[1] 8

factorize(45)
Big Integer ('bigz') object of length 3:
[1] 3 3 5
45*(1-1/3)*(1-1/5)
[1] 24

factorize(75)
Big Integer ('bigz') object of length 3:
[1] 3 5 5
75*(1-1/3)*(1-1/5)
[1] 40

3^m*7^n族

21,63の2個だが63がレンジ外（3*3*7が1桁の計算に収まらない）

factorize(21)
Big Integer ('bigz') object of length 2:
[1] 3 7
21*(1-1/3)*(1-1/7)
[1] 12

factorize(63)
Big Integer ('bigz') object of length 3:
[1] 3 3 7
63*(1-1/3)*(1-1/7)
[1] 36 

2^l*3^m^5^n族 

30,60,90の3個だが90がレンジ外（2*3*3*5が1桁の計算に収まらない）

factorize(30)
Big Integer ('bigz') object of length 3:
[1] 2 3 5
30*(1-1/2)*(1-1/3)*(1-1/5)
[1] 8

factorize(60)
Big Integer ('bigz') object of length 4:
[1] 2 2 3 5
60*(1-1/2)*(1-1/3)*(1-1/5)
[1] 16
factorize(90)
Big Integer ('bigz') object of length 4:
[1] 2 3 3 5
90*(1-1/2)*(1-1/3)*(1-1/5)
[1] 24

5^m*7^n族

35の1個

factorize(35)
Big Integer ('bigz') object of length 2:
[1] 5 7
35*(1-1/5)*(1-1/7)
[1] 24

2^l*3^m^7^n族

42,84の2個だが84がレンジ外（2*2*3*7が1桁の計算に収まらない）

factorize(42)
Big Integer ('bigz') object of length 3:
[1] 2 3 7
42*(1-1/2)*(1-1/3)*(1-1/7)
[1] 12

factorize(84)
Big Integer ('bigz') object of length 4:
[1] 2 2 3 7
84*(1-1/2)*(1-1/3)*(1-1/7)
[1] 24

2^l*5^m^7^n族

70の1個だがレンジ外（2*5*7が1桁の計算に収まらない）

factorize(70)
Big Integer ('bigz') object of length 3:
[1] 2 5 7
70*(1-1/2)*(1-1/5)*(1-1/7)
[1] 24

2^h*3^l*5^m^7^n族

10以下の素数をすべて含むと完全レンジ外

factorize(210)
Big Integer ('bigz') object of length 4:
[1] 2 3 5 7
210*(1-1/2)*(1-1/3)*(1-1/5)*(1-1/7)
[1] 48

まとめると…

• 1が1個
• 2^n族(2,4,8,16,32,64)が6個
• 3^n族(3,9,27,81)が4個
• 5^n族(5,25)が2個
• 2^m*3^n族(6,12,18,24,36,48,54,72,96)が9個だが96がレンジ外（2*2*2*2*2*3が1桁の計算に収まらない）
• 7^n族(7,49)が2個

ここまでで掛ける側に登場する数字(1~9)は網羅。小計23個。

• 2^m*5^m族(10,20,40,50,80)が5個だが20と80がレンジ外（2*2*5と2*2**2*2*5が1桁の計算に収まらない）
• 2^m*7^m族(14,28,56,98)が4個だが98がレンジ外（2*2*2*2*7が1桁の計算に収まらない）
• 3^m*5^n族(15,45,75)が3個だが75がレンジ外（3*5*5が1桁の計算に収まらない）
• 3^m*7^n族(21,63)が2個だが63がレンジ外（3*3*7が1桁の計算に収まらない）
• 2^l*3^m^5^n属(30,60,90)が3個だが90がレンジ外（2*3*3*5が1桁の計算に収まらない）
• 5^m*7^n族(35)が1個
• 2^l*3^m^7^n族(42,84)が2個だが84がレンジ外（2*2*3*7が1桁の計算に収まらない）
• 2^l*5^m^7^n族(70)が1個だがレンジ外（2*5*7が1桁の計算に収まらない） 

追加で13個。かくして九九に使用される数字は36個となる。 除外されたのは…

• 100以下1桁以上の素数が11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97の21個
• その倍数まで含めると11族(11,22,33,44,55,66,77,88,99)の9個,13族(13,26,39,52,65,78,91)の7個,17族(17,34,51,68,85)の5個,19族(19,38,57,76,95)の5個,23族(23,46,69,92)の4個,29族(29,58,87)の3個,31族(31,62,93)の3個,37族(37,74)の2個,41族(41,82)の2個,43族(43,86)の2個,47族(47,94)の2個,単独出現(53,59,61,67,71,73,79,83,89,97)が10個で合計54個
• 合成数だが1桁の計算に収まらないのが20,63,70,75,80,84,90,96,98の9個

統計言語Rによる検算用プログラム

#九九で使われる数(36個)
c009<-c(c(1),c(2,4,8,16,32,64),c(3,9,27,81),c(5,25),c(6,12,18,24,36,48,54,72),c(7,49))
c100<-c(c(10,40,50),c(14,28,56),c(15,45),c(21),c(30,60),c(35),c(42))
c99<-c(c009,c100)
length(c99)

[1] 36

#レンジ超過除外分(9個)
ce99<-c(20,63,70,75,80,84,90,96,98)

#100以下1桁以上の素数とその倍数(54個)

d100<-c(c(11,22,33,44,55,66,77,88,99),c(13,26,39,52,65,78,91),c(17,34,51,68,85),c(19,38,57,76,95),c(23,46,69,92),c(29,58,87),c(31,62,93),c(37,74),c(41,82),c(43,86),c(47,94),c(53,59,61,67,71,73,79,83,89,97))

length(d100)

[1] 54

ttl01<-c(c99,ce99,d100)
setdiff(c(1:99),ttl01)

integer(0)

 「レンジオーバー項目の発見と除去」は結局、最終的に人力で遂行。何かうまいアルゴリズムがありますかね？