using System;
using System.Collections.Generic;
namespace _2016_New_Years_Puzzle_2
{
class Program
{
static void Main(string[] args)
{
using (System.IO.StreamWriter oStream = new System.IO.StreamWriter("Output.txt"))
{
int r = 2016;
// The hypotensuse need not be any bigger than
// 2r^2 + 2r + 1.
int maxHypotenuse = (2 * r * r) + (2 * r) + 1;
List<ValidTriplet> TripletList = new List<ValidTriplet>();
long lastGoodCmB = (int)(1.4142 * r); // ~(r)sqrt(2) sounds like a good place to start to ensure a < b.
// c is surely greater than 2r, so let's start with c = 2r and go from there.
for (long c = 2 * r; c <= maxHypotenuse; c++)
{
// Our starting b for this loop need not be smaller than the previously successful c - b.
// This is because both c and b are monotonically increasing, but b increases faster.
for (long b = c - lastGoodCmB; b < c; b++)
{
// 2r = a + b - c
long a = (2 * r) + c - b;
if ((a * a) + (b * b) == (c * c))
{
// Got one! Add it to the list.
ValidTriplet triplet = new ValidTriplet(a, b, c);
TripletList.Add(triplet);
// Make comment to screen and output file.
Console.WriteLine("a = " + a + ", b = " + b + ", c = " + c);
oStream.WriteLine("a = " + a + ", b = " + b + ", c = " + c);
// Update last good c - b.
lastGoodCmB = c - b;
// Since we've found a triple for this hypotenuse, let's
// move on to the next one.
break;
}
}
}
Console.WriteLine(Environment.NewLine + "Number of triples = " + TripletList.Count + Environment.NewLine + "Press a key to exit.");
oStream.WriteLine(Environment.NewLine + "Number of triples = " + TripletList.Count);
Console.ReadKey();
}
}
}
class ValidTriplet
{
// Assumed that a < b < c.
// Also assumed that a, b, and c are all positive.
public long a;
public long b;
public long c;
public ValidTriplet(long a, long b, long c)
{
this.a = a;
this.b = b;
this.c = c;
}
}
}using System;
using System.Collections.Generic;namespace _2016_12_03_thing
{
class Program
{
static void Main(string[] args)
{
int rMax = 2016;
int twoRmax = 2 * rMax;
int cMax = (2 * rMax * rMax) + (2 * rMax) + 1;
List<ValidTriple> primTriples = new List<ValidTriple>();
// Create matricies for triple generation
// See https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples
// for details.
Matrix A = new Matrix
(1, -2, 2,
2, -1, 2,
2, -2, 3);
Matrix B = new Matrix
(1, 2, 2,
2, 1, 2,
2, 2, 3);
Matrix C = new Matrix
(-1, 2, 2,
-2, 1, 2,
-2, 2, 3);
// Generate list of primitive Pythagorean triples.
List<ValidTriple> currentLevelTriples = new List<ValidTriple>();
currentLevelTriples.Add(new ValidTriple(3, 4, 5)); // seed triple.
bool finishedGenerating = false;
while (!finishedGenerating)
{
List<ValidTriple> nextLevelTriples = new List<ValidTriple>();
foreach (ValidTriple triple in currentLevelTriples)
{
// Add triple to total primitive triple list.
primTriples.Add(triple);
// Generate next level of triples based on this one.
nextLevelTriples.Add(A * triple);
nextLevelTriples.Add(B * triple);
nextLevelTriples.Add(C * triple);
}
// Clear out currentLevelTriples list.
currentLevelTriples.Clear();
// transfer nextLevelTriples to CurrentLevelTriples.
finishedGenerating = true; // Set this true for the moment.
foreach(ValidTriple triple in nextLevelTriples)
{
if (triple.c <= cMax)
{
currentLevelTriples.Add(triple);
finishedGenerating = false;
}
}
}
// if radius of a valid triple evenly divides rMax
// we scale it accordingly and put it in a new list.
List<ValidTriple> rMaxTriples = new List<ValidTriple>();
foreach(ValidTriple triple in primTriples)
{
if(twoRmax % triple.twoR == 0)
{
int scale = twoRmax / triple.twoR;
rMaxTriples.Add(scale * triple);
}
}
// Output list.
using (System.IO.StreamWriter oStream = new System.IO.StreamWriter("Output.txt"))
{
foreach(ValidTriple triple in rMaxTriples)
{
Console.WriteLine("a = " + triple.a + ", b = " + triple.b + ", c = " + triple.c);
oStream.WriteLine("a = " + triple.a + ", b = " + triple.b + ", c = " + triple.c);
}
Console.WriteLine(Environment.NewLine + "Triple count: " + rMaxTriples.Count + Environment.NewLine + "Press a key to exit.");
oStream.WriteLine(Environment.NewLine + "Triple count: " + rMaxTriples.Count);
}
Console.ReadKey();
}
}
class ValidTriple
{
public int a { get; private set; }
public int b { get; private set; }
public int c { get; private set; }
public int twoR { get; private set; }
public ValidTriple(int a, int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
twoR = a + b - c;
}
public ValidTriple mult(int N)
{
return new ValidTriple(N * a, N * b, N * c);
}
public static ValidTriple operator *(int N, ValidTriple triple)
{
return triple.mult(N);
}
public static ValidTriple operator *(ValidTriple triple, int N)
{
return triple.mult(N);
}
}
class Matrix
{
int[,] elem;
public Matrix
(int a00, int a01, int a02,
int a10, int a11, int a12,
int a20, int a21, int a22)
{
elem = new int[3, 3];
elem[0, 0] = a00;
elem[0, 1] = a01;
elem[0, 2] = a02;
elem[1, 0] = a10;
elem[1, 1] = a11;
elem[1, 2] = a12;
elem[2, 0] = a20;
elem[2, 1] = a21;
elem[2, 2] = a22;
}
public ValidTriple mult(ValidTriple trip)
{
int a; int b; int c;
a = (elem[0, 0] * trip.a) + (elem[0, 1] * trip.b) + (elem[0, 2] * trip.c);
b = (elem[1, 0] * trip.a) + (elem[1, 1] * trip.b) + (elem[1, 2] * trip.c);
c = (elem[2, 0] * trip.a) + (elem[2, 1] * trip.b) + (elem[2, 2] * trip.c);
return new ValidTriple(a, b, c);
}
public static ValidTriple operator *(Matrix A, ValidTriple B)
{
return A.mult(B);
}
}
}PeroK said:
Thanks for that, @PeroK .
using System;
using System.Collections.Generic;
namespace _2016_01_05_Pythagorean_triple_s_fun_based_on_PeroK_advice
{
class Program
{
static void Main(string[] args)
{
ulong Number = 2016; // Radius of Pythagorean triples
using (System.IO.StreamWriter oStream
= new System.IO.StreamWriter("Output.txt"))
{
Console.WriteLine("Year: " + Number + Environment.NewLine);
oStream.WriteLine("Year: " + Number + Environment.NewLine);
}
// list of triples (ultimate goal of this program)
List<ValidTriple> tripleList = new List<ValidTriple>();
// Generate primes.
PrimeGenerator pGen = new PrimeGenerator(Number);
// Find prime factors of Number.
PrimeFactorGenerator facGen = new PrimeFactorGenerator(Number, pGen);
// Write prime factors to output file and screen.
using (System.IO.StreamWriter oStream
= new System.IO.StreamWriter("Output.txt", true))
{
Console.Write("Prime factors: ");
oStream.Write("Prime factors: ");
foreach (ulong prime in facGen.factors.Keys)
{
Console.Write(prime + "^" + facGen.factors[prime] + " ");
oStream.Write(prime + "^" + facGen.factors[prime] + " ");
}
Console.Write(Environment.NewLine + Environment.NewLine);
oStream.Write(Environment.NewLine + Environment.NewLine);
}
// Create an initialize the Combinator and LegalComboChecker
Combinator combinator = new Combinator(3, true);
LegalComboChecker legalChecker = new LegalComboChecker();
// Add prime factors into the combinator
foreach (ulong factor in facGen.factors.Keys)
for (int i = 0; i < facGen.factors[factor]; i++)
combinator.AddBall(factor);
// The first combination is aldready present in the
// combinator, and is guaranteed to be valid.
// (We can check validity anyway though.) Create the
// first triple here.
if (legalChecker.IsLegal(combinator))
{
tripleList.Add(GenerateTriple.GetTriple(combinator));
}
// Loop through all possible combinations. Check for
// valid combinations and create Phythorean triples
// of the valid ones.
while(!combinator.FinishedLooping)
{
// Increment state of combinator
combinator.AdvanceToNewCombination();
// Check if combinator contains a valid triple.
// If so, generate triple and add it to the list.
if (legalChecker.IsLegal(combinator))
{
tripleList.Add(GenerateTriple.GetTriple(combinator));
}
}
// Write the Pythagorean triples to the screen and file
using (System.IO.StreamWriter oStream
= new System.IO.StreamWriter("Output.txt", true))
{
foreach (ValidTriple triple in tripleList)
{
Console.WriteLine("a = " + triple.a
+ ", b = " + triple.b
+ ", c = " + triple.c);
oStream.WriteLine("a = " + triple.a
+ ", b = " + triple.b
+ ", c = " + triple.c);
}
Console.WriteLine(Environment.NewLine
+ "Total number of Pythagorean triples: "
+ tripleList.Count);
oStream.WriteLine(Environment.NewLine
+ "Total number of Pythagorean triples: "
+ tripleList.Count);
}
Console.ReadKey();
}
}
// Just a helper class with a static function
// that generates a ValidTriple from
// the current state of a Combinator. Assumes,
// Combinator.Buckets[0]: k
// Combinator.Buckets[1]: s
// Combinator.Buckets[2]: (t - s)
// Then generates (a, b, c) triple,
// a = k(t^2 - s^2)
// b = 2kst
// c = k(t^2 + s^2)
class GenerateTriple
{
public static ValidTriple GetTriple(Combinator combinator)
{
ulong k = combinator.Buckets[0].BallProduct;
ulong s = combinator.Buckets[1].BallProduct;
ulong tms = combinator.Buckets[2].BallProduct;
ulong t = tms + s;
ulong a = k * ((t * t) - (s * s));
ulong b = 2 * k * s * t;
ulong c = k * ((t * t) + (s * s));
return new ValidTriple(a, b, c);
}
}
// Checks for combinations in the associated
// Combinator instance whether it satisfies
// the requirements to form a Pythagorean
// triplet. It assumes that the associated
// Combinator.Buckets[0]: factors in k
// Combinator.Buckets[1]: factors in s
// Combinator.Buckets[2]: factors in tms
// The method IsLegal returns true if
// conditions are satisfied: s and tms
// must be coprime, and no factors of
// 2 can be in tms.
class LegalComboChecker
{
List<Tuple> previousGoodTuples;
// Constructor
public LegalComboChecker()
{
previousGoodTuples = new List<Tuple>();
}
public bool IsLegal(Combinator combinator)
{
// t must be greater than s for the combo
// to be valid. So make sure tms > 0
ulong tms = combinator.Buckets[2].BallProduct;
if (tms <= 0) return false;
// Check for '2' factors in the tms bucket.
if (combinator.Buckets[2].ContainsFactor(2))
return false;
List<ulong> sFactors = combinator.Buckets[1].GetFactors();
List<ulong> tmsFactors = combinator.Buckets[2].GetFactors();
// check if any sFactors are in tmsFactors
foreach (ulong factor in sFactors)
if (tmsFactors.Contains(factor)) return false;
// check if any tmsFactors are in sFactors
foreach (ulong factor in tmsFactors)
if (sFactors.Contains(factor)) return false;
// If we've gotten this far, it's a valid combination
// for a triple, unless it has been used before. So now
// we check for repeats
ulong k = combinator.Buckets[0].BallProduct;
ulong s = combinator.Buckets[1].BallProduct;
foreach (Tuple tuple in previousGoodTuples)
if ((tuple.k == k) && (tuple.s == s) && (tuple.tms == tms))
return false; // it's a repeat.
// And now we have a unique, valid combination.
previousGoodTuples.Add(new Tuple(k, s, tms));
return true;
}
}
// Just a set of three ulong numbers.
class Tuple
{
public ulong k;
public ulong s;
public ulong tms;
// Constructor
public Tuple(ulong k, ulong s, ulong tms)
{
this.k = k;
this.s = s;
this.tms = tms;
}
}
// Combinator creates a list of buckets. Each bucket
// can contain balls. Balls are added to the Combinator
// using the AddBall method, where a "factor" of a ball
// is specified; the ball's ID is assigned automatically.
// When a ball is added, Combinator
// automatically places it in a bucket of its own
// choosing. After all the balls
// have been added, Combinator can then, setp by step,
// loop through every possible combination of buckets
// and balls.
class Combinator
{
// List of buckets
public List<Bucket> Buckets { get; }
// Total number of balls in the combinator
public int BallCount { get { return _ballCount; } }
// Number of buckets in the combinator
public int BucketCount { get { return _bucketCount; } }
public bool FinishedLooping { get { return _loopingFinished; } }
private int _ballCount;
private int _bucketCount;
private int _nextID;
private bool _loopingStarted;
private bool _loopingFinished;
private List<Ball> _balls;
private bool _keep2factorFromLastBucket;
// Constructor
public Combinator(
int numberOfBuckets,
bool keep2factorFromLastBucket= false)
{
_bucketCount = numberOfBuckets;
Buckets = new List<Bucket>();
_balls = new List<Ball>();
for (int i = 0; i < _bucketCount; i++)
{
Bucket bucket = new Bucket();
Buckets.Add(bucket);
bucket.ID = Buckets.IndexOf(bucket);
}
_ballCount = 0;
_nextID = 0;
_loopingStarted = false;
_loopingFinished = false;
_keep2factorFromLastBucket = keep2factorFromLastBucket;
}
// Takes the specified factor, creates a ball
// with that factor. Then assigns that ball
// a uniquie ID and puts it in the first bucket.
public void AddBall(ulong factor)
{
if (_loopingStarted)
{
throw new Exception("Too late to get new balls.");
}
else
{
// Make the ball and put it in the bucket
Ball ball = new Ball(factor, _nextID);
Buckets[0].Add(ball);
_nextID++;
_ballCount++;
// Also add it to a private list of balls.
_balls.Add(ball);
}
}
// This is the main combinitorics (sort of) thing.
// With each call it advances the balls to a new
// unique combination of balls. All balls and
// buckets are considered distinguishable.
// Consideration of non-distigushable balls (i.e.,
// repeated prime factors) and legality of
// combinations (i.e., coprime or even/odd
// parameters) must be checked externally.
// Method returns 'true' when all combinations
// have been exhausted.
// A special optimization, specific for finding
// Pythagorean triples, was created to keep
// balls with a factor of '2' out of the last bin
// if _keep2factorFromLastBucket is set to 'true'.
public bool AdvanceToNewCombination()
{
// Set flag that looping has started.
_loopingStarted = true;
for(int i = 0; i < _ballCount; i++)
{
int modifiedBucketCount = _bucketCount;
if(_keep2factorFromLastBucket && (_balls[i].factor == 2))
{
// Special case where _balls[i] contains factor
// 2, and we want to keep it out of the tms
// bucket.
modifiedBucketCount = _bucketCount - 1;
}
if(_balls[i].BucketID < modifiedBucketCount - 1)
{
// Ball is not yet in last bucket.
// Place it in a higher bucket.
Buckets[_balls[i].BucketID].Remove(_balls[i].ID);
Buckets[_balls[i].BucketID + 1].Add(_balls[i]);
break; // We have a new combination. Quit loop.
}
else
{
// Ball is already in the last bucket. Move
// it to the first bucket, and let the loop
// handle the "carry" with the next ball.
Buckets[_balls[i].BucketID].Remove(_balls[i].ID);
Buckets[0].Add(_balls[i]);
}
}
// Check to see if the looping is finished. Return
// with answer either way.
foreach (Ball ball in _balls)
{
if (_keep2factorFromLastBucket && (ball.factor == 2))
{
if ((ball.BucketID < _bucketCount - 2))
return false;
}
else if (ball.BucketID < _bucketCount - 1)
return false;
}
// If we've got this far, the looping is finished.
_loopingFinished = true;
return true;
}
}
// Buckets hold balls.
class Bucket
{
// List of balls.
public List<Ball> Balls { get; set; }
// Returns the number of balls in the bucket.
public int BallCount { get { return Balls.Count; } }
// Returns the product of all Ball.factor of all
// balls in the bucket, multiplied together.
public ulong BallProduct
{
get
{
ulong tempProd = 1;
foreach (Ball ball in Balls)
tempProd *= ball.factor;
return tempProd;
}
}
public int ID { get; set; } // set externally
// Constructor
public Bucket()
{
Balls = new List<Ball>();
}
// Adds a ball to the bucket.
public void Add(Ball ball)
{
Balls.Add(ball);
ball.BucketID = ID;
}
// Removes the first ball from the bucket with
// specified ID.
public void Remove (int ballID)
{
foreach (Ball ball in Balls)
if (ball.ID == ballID)
{
Balls.Remove(ball);
break;
}
}
// Returns true if a ball in the bucket
// contains a ball with the specified
// factor.
public bool ContainsFactor(uint factor)
{
foreach (Ball ball in Balls)
if (ball.factor == factor) return true;
return false;
}
// Returns a collection of unique factors in the
// bucket (factors are not repeated, even if
// multiple balls in the bucket contain that
// factor)
public List<ulong> GetFactors()
{
List<ulong> factors = new List<ulong>();
foreach (Ball ball in Balls)
if (!factors.Contains(ball.factor))
factors.Add(ball.factor);
return factors;
}
}
// Simply stores a single prime factor (no repeats).
// Each ball can have its own ID. IDs are assigned
// externally, at the time of instantiation.
// BucketID can be changed externally at any time.
class Ball
{
public int ID { get; } // each ball can have it's own ID.
public ulong factor { get;} // prime factor associated with ball.
public int BucketID { get; set; } // changed externally.
public Ball (ulong factor, int ID)
{
this.ID = ID;
this.factor = factor;
}
}
// Generates a dictionary of prime factors.
//
// The TKey of the returned dicationary is the collection of prime numbers
// up to NumberToBeFactored.
// Each element of TValue corresponds to the
// number of particular primes that make up the factoring. For example,
// NumberToBeFactored = 20 will produce this result:
// Key Value
// 2 2
// 5 1
// The above meaning the prime factors contain two 2s and one 5.
// These get stored in the factors property.
class PrimeFactorGenerator
{
// Public properties
public Dictionary<ulong, int> factors { get; private set; }
// Private properties
private PrimeGenerator _primeGenerator;
private ulong _maxNumber;
// constructor
public PrimeFactorGenerator(ulong maxNumber, PrimeGenerator primeGenerator,
bool generatePrimeList = false)
{
_maxNumber = maxNumber;
_primeGenerator = primeGenerator;
if (generatePrimeList) primeGenerator.generatePrimes(maxNumber);
// Instantiate the dictionary of factors.
factors = new Dictionary<ulong, int>();
// Generate the factors.
generateFactors();
}
// generates the factors.
public void generateFactors()
{
ulong workingMaxNumber = _maxNumber;
while (workingMaxNumber > 1)
{
foreach (uint prime in _primeGenerator.primes)
{
int repetition = 0;
while ((workingMaxNumber % prime) == 0)
{
repetition++;
workingMaxNumber = workingMaxNumber / prime;
}
if (repetition > 0) factors.Add(prime, repetition);
}
}
}
}
// Prime number generator that implements the Sieve of Sundaram.
// For that it generates a list of prime numbers up to the
// specified max integer of interest.
class PrimeGenerator
{
// Prime number list.
public List<ulong> primes { get; private set; }
// Constructor
public PrimeGenerator(ulong maxNumber)
{
generatePrimes(maxNumber);
}
// Main algorithm to generate primes
public void generatePrimes(ulong maxNumber)
{
primes = new List<ulong>();
// The boolArray is what we start with. It will
// eventually tell us which numbers are prime,
// based on the individual bits in the array.
// The array comes in chucks of 32 bits (type int),
// which is why we divide by 32 and such. There's
// not much reason to alter the hardoded 32 to
// softcoded, since the size is fixed in the
// hardware.
uint[] boolArray = new uint[(maxNumber / 32) + 1];
ulong m = (maxNumber / 2) + 1;
// Fill boolArray with true.
for (ulong i = 0; i < (ulong)boolArray.Length; i++)
boolArray[i] = 0xblackff;
// Here's the first part of the Sieve of Sundaram.
for (ulong i = 1; i <= m; i++)
{
for (ulong j = i; j <= (m - i) / ((2 * i) + 1); j++)
{
ulong firstCalc = i + j + (2 * i * j);
ulong ByteIdx = fixedQuotient(firstCalc, 32);
uint BitIdx = (uint)fixedRemainder(firstCalc, 32);
// Here we clear that particular bit.
boolArray[ByteIdx]
= ~((~boolArray[ByteIdx]) | (uint)(1 << (int)BitIdx));
}
}
// Now let's get rid of that '1' in the prime list by zeroing
// out bit 0. (The Sieve of Sundaram seems to think 1 is prime for
// some reason.)
boolArray[0] = ~(~boolArray[0] | 1);
// And before we go on, let's add '2' to the actual prime list to
// start, since the Sieve of Sundaram only generates odd primes.
primes.Add(2);
// The final part of the Sieve of Sundaram comes from the known prime
// at 2k + 1, where k represents each the remaining '1's.
// These are completely different 'i' and 'j' than before, by the way.
// Here, i and j are just looping over boolean array elements.
for (ulong i = 0; i < (ulong)boolArray.Length; i++)
{
for (int j = 0; j < 32; j++)
{
if (((boolArray[i] >> j) & (1)) == 1)
{
ulong k = (32 * i) + (ulong)j;
ulong foundPrime = (2 * k) + 1;
if (foundPrime > maxNumber) break;
primes.Add(foundPrime);
}
}
}
}
// These methods calculate the quotient and remainder when doing
// fixed point division. They're important to figure out what
// uint block we need from the boolean array, and which bit from
// that block.
private ulong fixedQuotient(ulong numerator, ulong denominator)
{
return numerator / denominator;
}
private ulong fixedRemainder(ulong numerator, ulong denominator)
{
return numerator % denominator;
}
}
// Represents a valid Pythagorean triple. It's assumed to be valid.
class ValidTriple
{
public ulong a { get; private set; }
public ulong b { get; private set; }
public ulong c { get; private set; }
public ValidTriple(ulong a, ulong b, ulong c)
{
this.a = a;
this.b = b;
this.c = c;
}
}
}
