Special pythagorean triplet: Difference between revisions

Here I present a solution based on the ideas on the discussion page. It finds all Pythagorean triplets whose elements sum to a given value. It runs in O[n] time. Normally I would exclude triplets with a common factor but for this demonstration it is better to leave them.

let fG n g=let i=(n-g)/2L match (n+g)%2L with 0L->if (g*g)%(4L*i)=0L then Some(g,i-(g*g)/(4L*i),i+(g*g)/(4L*i)) else None

|_->if (g*g-2L*i-1L)%(4L*i+2L)=0L then Some(g,i-(g*g)/(4L*i+2L),i+1L+(g*g)/(4L*i+2L)) else None

let E9 n=let fN=fG n in seq{1L..(n-2L)/3L}|>Seq.choose fN|>Seq.iter(fun(n,g,l)->printfn $"%d{n*n}(%d{n})+%d{g*g}(%d{g})=%d{l*l}(%d{l})")

[1L..260L]|>List.iter(fun n->printfn "Sum = %d" n; E9 n)

Sum = 1

Sum = 2

Sum = 3

Sum = 4

Sum = 5

Sum = 6

Sum = 7

Sum = 8

Sum = 9

Sum = 10

Sum = 11

Sum = 12

9(3)+16(4)=25(5)

Sum = 13

Sum = 14

Sum = 15

Sum = 16

Sum = 17

Sum = 18

Sum = 19

Sum = 20

Sum = 21

Sum = 22

Sum = 23

Sum = 24

36(6)+64(8)=100(10)

Sum = 25

Sum = 26

Sum = 27

Sum = 28

Sum = 29

Sum = 30

25(5)+144(12)=169(13)

Sum = 31

Sum = 32

Sum = 33

Sum = 34

Sum = 35

Sum = 36

81(9)+144(12)=225(15)

Sum = 37

Sum = 38

Sum = 39

Sum = 40

64(8)+225(15)=289(17)

Sum = 41

Sum = 42

Sum = 43

Sum = 44

Sum = 45

Sum = 46

Sum = 47

Sum = 48

144(12)+256(16)=400(20)

Sum = 49

Sum = 50

Sum = 51

Sum = 52

Sum = 53

Sum = 54

Sum = 55

Sum = 56

49(7)+576(24)=625(25)

Sum = 57

Sum = 58

Sum = 59

Sum = 60

100(10)+576(24)=676(26)

225(15)+400(20)=625(25)

Sum = 61

Sum = 62

Sum = 63

Sum = 64

Sum = 65

Sum = 66

Sum = 67

Sum = 68

Sum = 69

Sum = 70

400(20)+441(21)=841(29)

441(21)+400(20)=841(29)

Sum = 71

Sum = 72

324(18)+576(24)=900(30)

Sum = 73

Sum = 74

Sum = 75

Sum = 76

Sum = 77

Sum = 78

Sum = 79

Sum = 80

256(16)+900(30)=1156(34)

Sum = 81

Sum = 82

Sum = 83

Sum = 84

144(12)+1225(35)=1369(37)

441(21)+784(28)=1225(35)

Sum = 85

Sum = 86

Sum = 87

Sum = 88

Sum = 89

Sum = 90

81(9)+1600(40)=1681(41)

225(15)+1296(36)=1521(39)

Sum = 91

Sum = 92

Sum = 93

Sum = 94

Sum = 95

Sum = 96

576(24)+1024(32)=1600(40)

Sum = 97

Sum = 98

Sum = 99

Sum = 100

Sum = 101

Sum = 102

Sum = 103

Sum = 104

Sum = 105

Sum = 106

Sum = 107

Sum = 108

729(27)+1296(36)=2025(45)

Sum = 109

Sum = 110

Sum = 111

Sum = 112

196(14)+2304(48)=2500(50)

Sum = 113

Sum = 114

Sum = 115

Sum = 116

Sum = 117

Sum = 118

Sum = 119

Sum = 120

400(20)+2304(48)=2704(52)

576(24)+2025(45)=2601(51)

900(30)+1600(40)=2500(50)

Sum = 121

Sum = 122

Sum = 123

Sum = 124

Sum = 125

Sum = 126

784(28)+2025(45)=2809(53)

Sum = 127

Sum = 128

Sum = 129

Sum = 130

Sum = 131

Sum = 132

121(11)+3600(60)=3721(61)

1089(33)+1936(44)=3025(55)

Sum = 133

Sum = 134

Sum = 135

Sum = 136

Sum = 137

Sum = 138

Sum = 139

Sum = 140

1600(40)+1764(42)=3364(58)

1764(42)+1600(40)=3364(58)

Sum = 141

Sum = 142

Sum = 143

Sum = 144

256(16)+3969(63)=4225(65)

1296(36)+2304(48)=3600(60)

Sum = 145

Sum = 146

Sum = 147

Sum = 148

Sum = 149

Sum = 150

625(25)+3600(60)=4225(65)

Sum = 151

Sum = 152

Sum = 153

Sum = 154

1089(33)+3136(56)=4225(65)

Sum = 155

Sum = 156

1521(39)+2704(52)=4225(65)

Sum = 157

Sum = 158

Sum = 159

Sum = 160

1024(32)+3600(60)=4624(68)

Sum = 161

Sum = 162

Sum = 163

Sum = 164

Sum = 165

Sum = 166

Sum = 167

Sum = 168

441(21)+5184(72)=5625(75)

576(24)+4900(70)=5476(74)

1764(42)+3136(56)=4900(70)

Sum = 169

Sum = 170

Sum = 171

Sum = 172

Sum = 173

Sum = 174

Sum = 175

Sum = 176

2304(48)+3025(55)=5329(73)

3025(55)+2304(48)=5329(73)

Sum = 177

Sum = 178

Sum = 179

Sum = 180

324(18)+6400(80)=6724(82)

900(30)+5184(72)=6084(78)

2025(45)+3600(60)=5625(75)

Sum = 181

Sum = 182

169(13)+7056(84)=7225(85)

Sum = 183

Sum = 184

Sum = 185

Sum = 186

Sum = 187

Sum = 188

Sum = 189

Sum = 190

Sum = 191

Sum = 192

2304(48)+4096(64)=6400(80)

Sum = 193

Sum = 194

Sum = 195

Sum = 196

Sum = 197

Sum = 198

1296(36)+5929(77)=7225(85)

Sum = 199

Sum = 200

1600(40)+5625(75)=7225(85)

Sum = 201

Sum = 202

Sum = 203

Sum = 204

2601(51)+4624(68)=7225(85)

Sum = 205

Sum = 206

Sum = 207

Sum = 208

1521(39)+6400(80)=7921(89)

Sum = 209

Sum = 210

1225(35)+7056(84)=8281(91)

3600(60)+3969(63)=7569(87)

3969(63)+3600(60)=7569(87)

Sum = 211

Sum = 212

Sum = 213

Sum = 214

Sum = 215

Sum = 216

2916(54)+5184(72)=8100(90)

Sum = 217

Sum = 218

Sum = 219

Sum = 220

400(20)+9801(99)=10201(101)

Sum = 221

Sum = 222

Sum = 223

Sum = 224

784(28)+9216(96)=10000(100)

Sum = 225

Sum = 226

Sum = 227

Sum = 228

3249(57)+5776(76)=9025(95)

Sum = 229

Sum = 230

Sum = 231

Sum = 232

Sum = 233

Sum = 234

4225(65)+5184(72)=9409(97)

5184(72)+4225(65)=9409(97)

Sum = 235

Sum = 236

Sum = 237

Sum = 238

Sum = 239

Sum = 240

225(15)+12544(112)=12769(113)

1600(40)+9216(96)=10816(104)

2304(48)+8100(90)=10404(102)

3600(60)+6400(80)=10000(100)

Sum = 241

Sum = 242

Sum = 243

Sum = 244

Sum = 245

Sum = 246

Sum = 247

Sum = 248

Sum = 249

Sum = 250

Sum = 251

Sum = 252

1296(36)+11025(105)=12321(111)

3136(56)+8100(90)=11236(106)

3969(63)+7056(84)=11025(105)

Sum = 253

Sum = 254

Sum = 255

Sum = 256

Sum = 257

Sum = 258

Sum = 259

Sum = 260

3600(60)+8281(91)=11881(109)

</pre>

I present results with timing for increasing powers of 10 to demonstrate its O[n] running.

<pre>

E9 1000L

Real: 00:00:00.001

E9 10000L

4000000(2000)+14062500(3750)=18062500(4250)

Real: 00:00:00.000

E9 100000L

400000000(20000)+1406250000(37500)=1806250000(42500)

478515625(21875)+1296000000(36000)=1774515625(42125)

Real: 00:00:00.001

E9 1000000L

40000000000(200000)+140625000000(375000)=180625000000(425000)

47851562500(218750)+129600000000(360000)=177451562500(421250)

Real: 00:00:00.005

E9 10000000L

54931640625(234375)+23814400000000(4880000)=23869331640625(4885625)

4000000000000(2000000)+14062500000000(3750000)=18062500000000(4250000)

4785156250000(2187500)+12960000000000(3600000)=17745156250000(4212500)

Real: 00:00:00.040

E9 100000000L

5493164062500(2343750)+2381440000000000(48800000)=2386933164062500(48856250)

400000000000000(20000000)+1406250000000000(37500000)=1806250000000000(42500000)

478515625000000(21875000)+1296000000000000(36000000)=1774515625000000(42125000)

Real: 00:00:00.382

E9 1000000000L

549316406250000(23437500)+238144000000000000(488000000)=238693316406250000(488562500)

40000000000000000(200000000)+140625000000000000(375000000)=180625000000000000(425000000)

47851562500000000(218750000)+129600000000000000(360000000)=177451562500000000(421250000)

Real: 00:00:03.704