Kotlin: 互いに素なピタゴラス数を求める

Kotlin で、 互いに素なピタゴラス数を求めてみました。

環境

Kotlin 1.1.2-2

方針

互いに素なピタゴラス数 ( a, b, c ( a leq b lt c ) ) を考えます。ピタゴラス数: ディオファントスの式にも書きましたが、このとき ( c ) は奇数で、 ( a ), ( b ) は偶数と奇数です。

そこで、 ( c ) を奇数のループにします。 ( b ) を ( frac{c}{sqrt{2}} lt [frac{c}{sqrt{2}}] + 1 leq b lt c ) の範囲でループさせます。そして ( a = sqrt{ b ^ 2 – c ^ 2 } ) が整数になる場合にそれをピタゴラス数とします。ただし互いに素である必要があるため、共通因数を持つ場合は排除します。

この方針で、 ( c leq 1000 ) となるピタゴラス数をすべて抽出します。

コード

共通因数が存在するか否かは Kotlin: ユークリッドの互除法で最大公約数を求めるのコードを流用します。

まずはピタゴラス数を格納するクラスを作っておきます。これはリストや配列でもOKです。

package com.improve_future.math
data class PythagorasNumber(
var a: Long,
var b: Long,
var c: Long
) {
override fun toString(): String {
return "($a, $b, $c)"
}
}

package com.improve_future.math

data class PythagorasNumber(

var a: Long,

var b: Long,

var c: Long

) {

override fun toString(): String {

return "($a, $b, $c)"

}

こちらがメインの処理です。計算の最後に、ピタゴラス数をすべて出力し、計算されたピタゴラス数の件数を出力します。

package com.improve_future.math
object Main {
@JvmStatic
fun main(args: Array<String>) {
val pythagorasList =
mutableListOf<PythagorasNumber>()
val m = 1000L
for (c in 5L..m step 2) {
for (b in c - 1 downTo
(c.toDouble() / Math.sqrt(2.0) + 1).
toLong()) {
val a = Math.sqrt(
Math.pow(c.toDouble(), 2.0) -
Math.pow(b.toDouble(), 2.0))
if (a % 1 == 0.0 &&
calcGcm(mutableListOf<Long>(
a.toLong(), b, c)) == 1L) {
pythagorasList.add(
PythagorasNumber(a.toLong(), b, c))
}
}
}
pythagorasList.forEach{ println(it) }
println(pythagorasList.count())
}
fun calcGcm(numList: MutableList<Long>): Long {
var newList =
numList.distinct().sorted() as MutableList
var r: Long = 0
while (newList.count() > 1) {
r = newList[0]
newList = newList.
takeLast(newList.count() - 1).map {
it % newList[0]} as MutableList
newList.add(r)
newList = newList.distinct().sorted().
filter { it != 0L } as MutableList<Long>
}
return r
}
}

package com.improve_future.math

object Main {

@JvmStatic

fun main(args: Array<String>) {

val pythagorasList =

mutableListOf<PythagorasNumber>()

val m = 1000L

for (c in 5L..m step 2) {

for (b in c - 1 downTo

(c.toDouble() / Math.sqrt(2.0) + 1).

toLong()) {

val a = Math.sqrt(

Math.pow(c.toDouble(), 2.0) -

Math.pow(b.toDouble(), 2.0))

if (a % 1 == 0.0 &&

calcGcm(mutableListOf<Long>(

a.toLong(), b, c)) == 1L) {

pythagorasList.add(

PythagorasNumber(a.toLong(), b, c))

}

pythagorasList.forEach{ println(it) }

println(pythagorasList.count())

}

fun calcGcm(numList: MutableList<Long>): Long {

var newList =

numList.distinct().sorted() as MutableList

var r: Long = 0

while (newList.count() > 1) {

r = newList[0]

newList = newList.

takeLast(newList.count() - 1).map {

it % newList[0]} as MutableList

newList.add(r)

newList = newList.distinct().sorted().

filter { it != 0L } as MutableList<Long>

}

return r

}

実行結果

( c leq 1000 ) では 158件みつかりました。

(3, 4, 5)
(5, 12, 13)
(8, 15, 17)
(7, 24, 25)
(20, 21, 29)
(12, 35, 37)
(9, 40, 41)
(28, 45, 53)
(11, 60, 61)
(16, 63, 65)
(33, 56, 65)
(48, 55, 73)
(13, 84, 85)
(36, 77, 85)
(39, 80, 89)
(65, 72, 97)
(20, 99, 101)
(60, 91, 109)
(15, 112, 113)
(44, 117, 125)
(88, 105, 137)
(17, 144, 145)
(24, 143, 145)
(51, 140, 149)
(85, 132, 157)
(119, 120, 169)
(52, 165, 173)
(19, 180, 181)
(57, 176, 185)
(104, 153, 185)
(95, 168, 193)
(28, 195, 197)
(84, 187, 205)
(133, 156, 205)
(21, 220, 221)
(140, 171, 221)
(60, 221, 229)
(105, 208, 233)
(120, 209, 241)
(32, 255, 257)
(23, 264, 265)
(96, 247, 265)
(69, 260, 269)
(115, 252, 277)
(160, 231, 281)
(161, 240, 289)
(68, 285, 293)
(136, 273, 305)
(207, 224, 305)
(25, 312, 313)
(75, 308, 317)
(36, 323, 325)
(204, 253, 325)
(175, 288, 337)
(180, 299, 349)
(225, 272, 353)
(27, 364, 365)
(76, 357, 365)
(252, 275, 373)
(135, 352, 377)
(152, 345, 377)
(189, 340, 389)
(228, 325, 397)
(40, 399, 401)
(120, 391, 409)
(29, 420, 421)
(87, 416, 425)
(297, 304, 425)
(145, 408, 433)
(84, 437, 445)
(203, 396, 445)
(280, 351, 449)
(168, 425, 457)
(261, 380, 461)
(31, 480, 481)
(319, 360, 481)
(44, 483, 485)
(93, 476, 485)
(132, 475, 493)
(155, 468, 493)
(217, 456, 505)
(336, 377, 505)
(220, 459, 509)
(279, 440, 521)
(92, 525, 533)
(308, 435, 533)
(341, 420, 541)
(33, 544, 545)
(184, 513, 545)
(165, 532, 557)
(276, 493, 565)
(396, 403, 565)
(231, 520, 569)
(48, 575, 577)
(368, 465, 593)
(240, 551, 601)
(35, 612, 613)
(105, 608, 617)
(336, 527, 625)
(100, 621, 629)
(429, 460, 629)
(200, 609, 641)
(315, 572, 653)
(300, 589, 661)
(385, 552, 673)
(52, 675, 677)
(37, 684, 685)
(156, 667, 685)
(111, 680, 689)
(400, 561, 689)
(185, 672, 697)
(455, 528, 697)
(260, 651, 701)
(259, 660, 709)
(333, 644, 725)
(364, 627, 725)
(108, 725, 733)
(216, 713, 745)
(407, 624, 745)
(468, 595, 757)
(39, 760, 761)
(481, 600, 769)
(195, 748, 773)
(56, 783, 785)
(273, 736, 785)
(168, 775, 793)
(432, 665, 793)
(555, 572, 797)
(280, 759, 809)
(429, 700, 821)
(540, 629, 829)
(41, 840, 841)
(116, 837, 845)
(123, 836, 845)
(205, 828, 853)
(232, 825, 857)
(287, 816, 865)
(504, 703, 865)
(348, 805, 877)
(369, 800, 881)
(60, 899, 901)
(451, 780, 901)
(464, 777, 905)
(616, 663, 905)
(43, 924, 925)
(533, 756, 925)
(129, 920, 929)
(215, 912, 937)
(580, 741, 941)
(301, 900, 949)
(420, 851, 949)
(615, 728, 953)
(124, 957, 965)
(387, 884, 965)
(248, 945, 977)
(473, 864, 985)
(696, 697, 985)
(372, 925, 997)
158

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

(3, 4, 5)

(5, 12, 13)

(8, 15, 17)

(7, 24, 25)

(20, 21, 29)

(12, 35, 37)

(9, 40, 41)

(28, 45, 53)

(11, 60, 61)

(16, 63, 65)

(33, 56, 65)

(48, 55, 73)

(13, 84, 85)

(36, 77, 85)

(39, 80, 89)

(65, 72, 97)

(20, 99, 101)

(60, 91, 109)

(15, 112, 113)

(44, 117, 125)

(88, 105, 137)

(17, 144, 145)

(24, 143, 145)

(51, 140, 149)

(85, 132, 157)

(119, 120, 169)

(52, 165, 173)

(19, 180, 181)

(57, 176, 185)

(104, 153, 185)

(95, 168, 193)

(28, 195, 197)

(84, 187, 205)

(133, 156, 205)

(21, 220, 221)

(140, 171, 221)

(60, 221, 229)

(105, 208, 233)

(120, 209, 241)

(32, 255, 257)

(23, 264, 265)

(96, 247, 265)

(69, 260, 269)

(115, 252, 277)

(160, 231, 281)

(161, 240, 289)

(68, 285, 293)

(136, 273, 305)

(207, 224, 305)

(25, 312, 313)

(75, 308, 317)

(36, 323, 325)

(204, 253, 325)

(175, 288, 337)

(180, 299, 349)

(225, 272, 353)

(27, 364, 365)

(76, 357, 365)

(252, 275, 373)

(135, 352, 377)

(152, 345, 377)

(189, 340, 389)

(228, 325, 397)

(40, 399, 401)

(120, 391, 409)

(29, 420, 421)

(87, 416, 425)

(297, 304, 425)

(145, 408, 433)

(84, 437, 445)

(203, 396, 445)

(280, 351, 449)

(168, 425, 457)

(261, 380, 461)

(31, 480, 481)

(319, 360, 481)

(44, 483, 485)

(93, 476, 485)

(132, 475, 493)

(155, 468, 493)

(217, 456, 505)

(336, 377, 505)

(220, 459, 509)

(279, 440, 521)

(92, 525, 533)

(308, 435, 533)

(341, 420, 541)

(33, 544, 545)

(184, 513, 545)

(165, 532, 557)

(276, 493, 565)

(396, 403, 565)

(231, 520, 569)

(48, 575, 577)

(368, 465, 593)

(240, 551, 601)

(35, 612, 613)

(105, 608, 617)

(336, 527, 625)

(100, 621, 629)

(429, 460, 629)

(200, 609, 641)

(315, 572, 653)

(300, 589, 661)

(385, 552, 673)

(52, 675, 677)

(37, 684, 685)

(156, 667, 685)

(111, 680, 689)

(400, 561, 689)

(185, 672, 697)

(455, 528, 697)

(260, 651, 701)

(259, 660, 709)

(333, 644, 725)

(364, 627, 725)

(108, 725, 733)

(216, 713, 745)

(407, 624, 745)

(468, 595, 757)

(39, 760, 761)

(481, 600, 769)

(195, 748, 773)

(56, 783, 785)

(273, 736, 785)

(168, 775, 793)

(432, 665, 793)

(555, 572, 797)

(280, 759, 809)

(429, 700, 821)

(540, 629, 829)

(41, 840, 841)

(116, 837, 845)

(123, 836, 845)

(205, 828, 853)

(232, 825, 857)

(287, 816, 865)

(504, 703, 865)

(348, 805, 877)

(369, 800, 881)

(60, 899, 901)

(451, 780, 901)

(464, 777, 905)

(616, 663, 905)

(43, 924, 925)

(533, 756, 925)

(129, 920, 929)

(215, 912, 937)

(580, 741, 941)

(301, 900, 949)

(420, 851, 949)

(615, 728, 953)

(124, 957, 965)

(387, 884, 965)

(248, 945, 977)

(473, 864, 985)

(696, 697, 985)

(372, 925, 997)

158

The Life

Kotlin: 互いに素なピタゴラス数を求める

環境

方針

コード

実行結果

関連記事

この記事を見た人は次の記事も見ています

A Life Summary of an Gypsy