CODEWITHSUNDEEP
javaalgorithm
Peter
Peter

Reputation: 33

Project euler 45

I'm not yet a skilled programmer but I thought this was an interesting problem and I thought I'd give it a go.

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

  • Triangle T_(n)=n(n+1)/2 1, 3, 6, 10, 15, ...
  • Pentagonal P_(n)=n(3n−1)/2 1, 5, 12, 22, 35, ...
  • Hexagonal H_(n)=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Is the task description.

I know that Hexagonal numbers are a subset of triangle numbers which means that you only have to find a number where Hn=Pn. But I can't seem to get my code to work. I only know java language which is why I'm having trouble finding a solution on the net womewhere. Anyway hope someone can help. Here's my code

public class NextNumber {

    public NextNumber() {
    next();
    }

    public void next() {


int n = 144;
int i = 165;
int p = i * (3 * i - 1) / 2;
int h = n * (2 * n - 1);
        while(p!=h) {
            n++;
           h = n * (2 * n - 1);

            if (h == p) {
                System.out.println("the next triangular number is" + h);
            } else {
                while (h > p) {
                    i++;
                    p = i * (3 * i - 1) / 2;
                }
                if (h == p) {
                    System.out.println("the next triangular number is" + h); break;
                    }
                 else if (p > h) {
                    System.out.println("bummer");
                }
            }

            }

    }
}

I realize it's probably a very slow and ineffecient code but that doesn't concern me much at this point I only care about finding the next number even if it would take my computer years.

Upvotes: 3

Views: 2633

Answers (4)

Eric
Eric

Reputation: 24904

Math

The key is:

ti = hi*2 - 1

where ti and hi are indices of T and H respectively.

That means for any H(hi), there is always a T(ti).
Thus only need to find the P(pi) = H(hi), and that can be solved linear.

Code (go)

  • Solution:

    package p45

// refer:   https://projecteuler.net/problem=45

func NextAllEqual(startHi, startPi int32) (v int64, hi, pi int32) {
    start := calculateH(startHi)
    h, p := nextH(start, startHi), nextP(start, startPi)
    hi, pi = startHi+1, startPi+1

    for h != p {
        if hi <= 0 || pi <= 0 { // out of range,
            return -1, -1, -1
        }

        if h < p {
            h = nextH(h, hi)
            hi++
        } else {
            p = nextP(p, pi)
            pi++
        }
    }

    return h, hi, pi
}

// h(i) = i * (2*i - 1)
func calculateH(i int32) int64 {
    return int64(i) * (int64(i)<<1 - 1)
}

// h(i+1) = h(i) + (4*i + 1)
func nextH(h int64, i int32) int64 {
    return h + (int64(i)<<2 + 1)
}

// p(i+1) = p(i) + (3*i + 1)
func nextP(p int64, i int32) int64 {
    return p + (3*int64(i) + 1)
}

// ti = 2*hi- 1
func TQiFromHi(hi int32) int32 {
    return hi<<1 - 1
}

  • Test case:

    package p45

import (
    "fmt"
    "testing"
)

const (
    zeroHi, zeroPi   = int32(1), int32(1)
    firstHi, firstPi = 143, 165
)

func TestNextAllEqual_first(t *testing.T) {
    // runOnce_NextAllEqual(t, zeroHi, zeroPi)
    runOnce_NextAllEqual(t, firstHi, firstPi)
}

func runOnce_NextAllEqual(t *testing.T, preHi, prePi int32) (v int64, hi, pi int32) {
    v, hi, pi = NextAllEqual(preHi, prePi)
    if v > 0 {
        ti := TQiFromHi(hi)
        fmt.Printf("v = %d, indices:\n\tti = %d, pi = %d, hi = %d\n\n", v, ti, pi, hi)

    } else {
        fmt.Println("Done, index out of range of int32")
    }

    return v, hi, pi
}

// find all with indices in range of int32,
func TestNextAllEqual_all_int32_indices(t *testing.T) {
    hi, pi := zeroHi, zeroPi
    var v int64
    for seq := 1; ; seq++ {
        fmt.Printf("[%d]\t", seq)
        v, hi, pi = runOnce_NextAllEqual(t, hi, pi)
        if v <= 0 {
            break
        }
    }
}

Result

(Run on an old laptop)

  • For problem 44:
    It took about 2ms.

    === RUN   TestNextAllEqual_first
v = 1533776805, indices:
    ti = 55385, pi = 31977, hi = 27693

--- PASS: TestNextAllEqual_first (0.00s)

  • To find all such indices within range of signed 32 bits.
    It took about 5.4s, there are 4 such values, not including the start one (1,1,1).

    === RUN   TestNextAllEqual_all_int32_indices
[1] v = 40755, indices:
    ti = 285, pi = 165, hi = 143

[2] v = 1533776805, indices:
    ti = 55385, pi = 31977, hi = 27693

[3] v = 57722156241751, indices:
    ti = 10744501, pi = 6203341, hi = 5372251

[4] v = 2172315626468283465, indices:
    ti = 2084377905, pi = 1203416145, hi = 1042188953

[5] Done, index out of range of int32
--- PASS: TestNextAllEqual_all_int32_indices (5.33s)

Upvotes: 0

ROMANIA_engineer
ROMANIA_engineer

Reputation: 56684

Another solution that takes 2 ms:

public class P45 {

    public static void main(String[] args) {
        long H = 0;
        long i = 144;
        while(true) {
            H = i*((i<<1)-1);
            if ( isPentagonal(H) && isTriangle(H) ) {
                break;
            }
            i++;
        }
        System.out.println(H);
    }

    private static boolean isPentagonal(long x) {
        double n = (1 + Math.sqrt(24*x+1)) / 6;
        return n == (long)n;
    }

    private static boolean isTriangle(long x) {
        double n = (-1 + Math.sqrt((x<<3)+1)) / 2;
        return n == (long)n;
    }

}

Improved:

  • You already specified that: hexagonal numbers are triangle numbers, but I add a short proof: k*(2*k-1) can be written in the following form i*(i+1)/2 if i = 2*k-1.
  • In this case isTriangle can be removed.
  • The performance will be similar because that function was called seldom (it was called only when the number was pentagonal).

Upvotes: 1

moinudin
moinudin

Reputation: 138377

We know that T285 = P165 = H143 = 40755. We start with nt=286, np=166 and nh=144 and work out the respective triangle, pentagonal, and hexagonal numbers. Whichever resulting number is smallest, we bump up its n value. Continue doing this until all numbers are equal and you have your answer.

A Python implementation of this algorithm runs in 0.1 seconds on my computer.

The problem with your code is overflow. While the answer fits into a 32 bit int, the temporary values i * (3 * i - 1) overflows before reaching the answer. Using 64 bit long values fixes your code.

Upvotes: 7

Blastfurnace
Blastfurnace

Reputation: 18652

Your code looks like it will produce the correct answer fairly quickly. The while loop can be simplified if you just print the result after the loop terminates:

while (p != h) {
    n++;
    h = n * (2 * n - 1);
    while (h > p) {
        i++;
        p = i * ((3 * i - 1) / 2);
    }
}
System.out.println("the next triangular number is" + h);

Note: your inner loop looks very much like the inner loop of my C++ solution. It produced the desired answer in about 0.002 seconds on my machine.

Upvotes: 1

Related Questions