The discussion centers on determining the divisibility of N, the number of Pythagorean triples with integer sides and an inradius of 2016, by the integers 2, 3, 5, and 7. Participants clarified that N represents unique right triangles, counted only once regardless of congruence. A solution was proposed that does not require a computer program, followed by the development of a generalized computer program to calculate N for any positive integer year greater than or equal to 2.
PREREQUISITESMathematicians, educators, students studying number theory, and programmers interested in mathematical algorithms.
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;
}
}
}