Seemingly innovative solution to problem 12

Primes, divisors, arithmetic, number properties, ...
Post Reply

Cool?

0
0
No votes
1
0
No votes
 
Total votes: 0

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

Seemingly innovative solution to problem 12

Post by Hyolobrika » Sat Jun 29, 2019 8:18 pm

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

Post Reply