## Seemingly innovative solution to problem 12

Primes, divisors, arithmetic, number properties, ...

## Cool?

0
0
1
0

Hyolobrika
Posts: 1
Joined: Sat Jun 29, 2019 9:11 pm

### Seemingly innovative solution to problem 12

https://termbin.com/j7zt is where I am at the moment. It's not finished, but a cool concept nonetheless.

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