Code: Select all

```
// Project Euler task 12:
// find the smallest triangle number
// to have over 500 factors including
// 1 and the number itself
//(https://projecteuler.net/problem=12)
// This draft is the work of Jacob Freddie "Hyolobrika" Stewart (jacob.freddie@btinternet.com), June 2019. You can see it's SHA1 hash on the blockchain.
// Instead of traditional binary place-value numbers most of the numbers are in what I like to call factor-exponent notation/representation.
// Numbers in f-e representation are stored as a list of signed integers representing the number of times each respective prime number up to a point goes into it (exponent). Although in this case the exponents are stored as unsigned integers because we are not dealing with fractions here, only positive integers
// This representation has the advantage that its faster and easier to multiply and divide simply by adding and subtracting exponents. On the other hand, I have yet to find a way of adding and subtracting this way.
// This code finds the next triangle number after n(n+1)/2 by first dividing by n and multiplying by (n+2)
// PROBLEM: n must be a f-e number, but then how do we add 2 to it? If we first convert to place value notation and use the standard C/C++ tools and convert back (using brute-force trying every possible prime factor) then we might as well use place-value for the triangle numbers and use brute-force to count the factors
// This, however is still faster than that simple brute-force approach because instead of finding the factors for every triangle no. we find them for an equall no. of even positive integers, which are much smaller
// At each step through the triangle numbers we can find the number of factors by finding the number of combinations of prime factors of sizes 1 to n where n = total no. of p factors = sum of all exponents
// F-E numbers are each a list of the exponents of all prime numbers from 2 to the FE_LENGTHth prime, 131
#define FE_LENGTH 32
typedef exponent_t unsigned char;
// declare by: exponent_t number [FE_LENGTH]
const unsigned short * primes =
// TODO: hardcode list of first FE_LENGTH primes in primes
#include <cmath>
typedef uint unsigned int;
uint fe2pv (
exponent_t number [FE_LENGTH]
) {
uint result = 0;
for (char i = 0; i < FE_LENGTH; ++i)
{
result +=
pow( primes[i], number[i] );
}
return result;
}
exponent_t * pv2fe (
uint number
) {
for (uint i = 0; i < FE_LENGTH; ++i)
{
exponent_t expwp = 0;
while true
{
if
bool operator== (
exponent_t lhs [FE_LENGTH],
exponent_t rhs [FE_LENGTH]
) {
for (uint i = 0; i < FE_LENGTH; ++i)
{
if (lhs[i] != rhs[i])
{
return false;
}
}
return true;
}
//the following two functions do not correct for overflow errors
exponent_t * operator* (
exponent_t lhs [FE_LENGTH],
exponent_t rhs [FE_LENGTH]
) {
exponent_t result [FE_LENGTH];
for (uint i = 0; i < FE_LENGTH; ++i)
{
result[i] = lhs[i] + rhs[i]
}
return result;
}
exponent_t * operator/ (
exponent_t lhs [FE_LENGTH],
exponent_t rhs [FE_LENGTH]
) {
exponent_t result [FE_LENGTH];
for (uint i = 0; i < FE_LENGTH; ++i)
{
result[i] = lhs[i] - rhs[i]
}
return result;
}
//TODO: write function to extract number of factors from f-e num, from prime factors. Use combination formulae.
uint numfactors(exponent_t * input);
#define THRESHOLD 500
int main() {
exponent_t tri [FE_LENGTH]; for (exponent_t * wp = tri; wp < tri+FE_LENGTH; ++wp) *wp = 0; tri[1] /*3*/ = 1; //initialise to the second triangle number
exponent_t n [FE_LENGTH]; for ( wp = n; wp < tri+FE_LENGTH; ++wp) *wp = 0; n[0] /*2*/ = 1; //n=2
uint nint = 2; //n=2
while (true) {
if (numfactors(tri) > THRESHOLD)
break;
//tri = n(n+1)/2
//next tri = (n+1)(n+2)/2
//.: next tri = tri*(n+2)/n
tri /= n; //tri=(n+1)/2
n = pv2fe( nint + 2 ); //<- the slow bit
tri *= n; //tri=(n+1)(n+2)/2 = next tri
```