public
Created

Programming Challenge #71 /w Comments

  • Download Gist
Program.cs
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
class Program
{
//Problem:
// A^2 + B^2 = C^2
// A + B + C = Q
// For a given Q Find all int A,B,C that this is true
 
//Some Reasoning:
// C = SQRT(A^2 + B^2)
// SQRT(A^2 + 2AB + B^2) = A + B
// therefore C <= A + B
 
// and also C >= A, C >= B, so C <
// 1/3CONST <= C <= 1/2CONST
 
// Pick a C, aka Ci,
// Then solve using quadratic formula (not iterate)
// Find B in terms of Ci, and Constant Q
 
// A = Q - (C + B)
// A^2 + B^2 = C^2
// (Q - (C + B))^2 + B^2 = C^2
// Q^2 -2Q(C + B) + (C+B)^2 + B^2 = C^2
// Q^2 - 2QC - 2QB + C^2 + 2CB + B^2 + B^2 = C^2
// Q^2 - 2QC - 2QB + 2CB + 2B^2 = 0
// Q^2 - 2QC + (-2Q + 2C)B + 2B^2 = 0
// We can use the quadratic formula with these constants
// a = 2
// b = 2C - 2Q
// c = Q^2 - 2QC
 
// 2Q - 2C +- SQRT((4C^2 - 8CQ + 4Q^2) - 8Q^2 + 16QC))
// -------------------------------
// 4
 
// 2Q - 2C +- SQRT(4C^2 + 8CQ - 4Q^2)
// -------------------------------
// 4
 
// 2Q - 2C +- 2 * SQRT(C^2 + 2CQ - Q^2)
// -------------------------------
// 4
 
// Q - C +- SQRT(C^2 + 2CQ - Q^2)
// -------------------------------
// 2
 
// Q - C +- SQRT(C^2 + 2CQ - Q^2)
// ------------------------------- = B (and A turns out to be the other root)
// 2
 
static void Triples(long inputSum)
{
long CONSTANT_SUM = inputSum;
 
long low = CONSTANT_SUM / 3 - 1;
long high = CONSTANT_SUM / 2 - 1;
 
DateTime StartTime = DateTime.Now;
 
for (long ci = low; ci <= high; ci++)
{
long insideSqrt = ci * ci + 2 * CONSTANT_SUM * ci - CONSTANT_SUM * CONSTANT_SUM;
if (insideSqrt >= 0)
{
double sqrt = Math.Sqrt((double)insideSqrt);
if (sqrt % 1 == 0)
{
long b_value_1 = (CONSTANT_SUM - ci + (long) sqrt) / 2;
long b_value_2 = (CONSTANT_SUM - ci - (long) sqrt) / 2;
Console.WriteLine("Triple: {0}, {1}, {2}", ci, b_value_1, b_value_2);
}
}
}
Console.WriteLine("Took {0}", DateTime.Now - StartTime);
 
Console.ReadKey(true);
}
 
static void Main(string[] args)
{
Triples(504);
}
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.