We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #12: Highly divisible triangular number
  4. Discussions

Project Euler #12: Highly divisible triangular number

Sort by

recency

|

125 Discussions

|

  • muchomichael1
     + 0 comments

    Pefect Solution In Python You can use the property that the number of divisors of a triangle number T_n = n*(n+1)//2 is the product of the number of divisors of n//2 and n+1 (if n is even), or n and (n+1)//2 (if n is odd). This allows you to factorize smaller numbers and reuse results.

    def count_divisors(n):
    cnt = 1
    i = 2
    while i * i <= n:
        power = 0
        while n % i == 0:
            n //= i
            power += 1
        cnt *= (power + 1)
        i += 1
    if n > 1:
        cnt *= 2
    return cnt

def first_triangle_with_divisors(limit):
    n = 1
    while True:
        if n % 2 == 0:
            a = n // 2
            b = n + 1
        else:
            a = n
            b = (n + 1) // 2
        divisors = count_divisors(a) * count_divisors(b)
        if divisors > limit:
            return n * (n + 1) // 2
        n += 1

T = int(input())
Ns = [int(input()) for _ in range(T)]
for N in Ns:
    print(first_triangle_with_divisors(N))

  • spran444219
     + 0 comments

    Using Seive C++

    include

    using namespace std; using ll = long long; ll mx = 1e5; vector cntDiv(mx+1);

    void solve () {

    ll n;
cin >> n;

for (ll i=1; i<=mx; i++){
    ll div;
    if(i%2 == 0) {
        div = cntDiv[i/2] * cntDiv[i+1];
    }else{
        div = cntDiv[i] * cntDiv[(i+1)/2];
    }
    if(div>n){
        cout << (i*(i+1)) / 2 << "\n";
        return;
    }
}

    }

    int main () {

     for (ll i=1; i<=mx; i++) {
     for (ll j=i; j<=mx; j+=i) {
         cntDiv[j]++;
     }
 }

 ll t;
 cin >> t;
 while ( t--) {
    solve();
 }

    }

  • valogonor
     + 0 comments

    Here's an efficient solution in Python that takes advantage of the fact that the formula for the nth triangular number is n * (n+1) // 2 and the fact that n and n + 1 are coprime:

    def count_factors(num):
    ans = 0
    for i in range(1, int(num**.5) + 1):
        if num % i == 0:
            ans += 1 if i * i == num else 2
    return ans
    
def solve(mindivs):
    n = 1
    while True:
        trinum = n * (n + 1) // 2
        if n % 2 == 0:
            divcount = count_factors(n // 2) * count_factors(n + 1)
        else:
            divcount = count_factors((n+1)//2) * count_factors(n)
        if divcount > mindivs:
            return trinum
        n += 1

t = int(input())
for _ in range(t):
    n = int(input())
    print(solve(n))

  • yonahel
     + 0 comments

    Haskell

    import Control.Applicative
import Control.Monad
import System.IO
import Prelude
import Data.List

isqrt :: Int -> Int -- Thanks StackOverflow
isqrt = ceiling . sqrt . fromIntegral

triangle_num :: Int -> Int
triangle_num n = (n * (n + 1)) `div` 2

triangle_nums = map triangle_num [1..]

primes = 2 : [i | i <- [3..1000],  
              and [rem i p > 0 | p <- takeWhile (\p -> p^2 <= i) primes]]

num_subdivisions :: Int -> Int -> Int -> Int
num_subdivisions num divisor rem
    | num `mod` divisor /= 0 = rem
    | otherwise = num_subdivisions (num `div` divisor)  divisor (rem+1)

num_divisors :: Int -> Int
num_divisors 1 = 1
num_divisors n = product [((num_subdivisions n x 0) + 1) | x <- (filter (<= ((isqrt n) + 1)) primes), n `mod` x == 0]

smallestTri :: Int -> [Int] -> Int
smallestTri n xs
    | num_divisors (head xs) > n = head xs
    | otherwise = smallestTri n (tail xs)

main :: IO ()
main = do
    t_temp <- getLine
    let t = read t_temp :: Int
    forM_ [1..t] $ \a0  -> do
        n_temp <- getLine
        let n = read n_temp :: Int
        let smallTri = smallestTri n triangle_nums
        print(smallTri)

  • vishwasshivamog1
     + 0 comments

    include

    include

    include

    using namespace std;

    int main() { const int MAX_PRIMES = 1000; vector primes(MAX_PRIMES, 0); primes[0] = 2; primes[1] = 3; primes[2] = 5; primes[3] = 7; int count1 = 4; long long num = 9; while(count1 < MAX_PRIMES) { bool isprime = true; int sqrt_num = sqrt(num);

        for(int i = 0; primes[i] <= sqrt_num && i < count1; i++) {
        if(num % primes[i] == 0) {
            isprime = false;
            break;
        }
    }
    if(isprime) {
        primes[count1] = num;
        count1++;
    }
    num += 2;
}

int t;
cin >> t;
while(t--) {
    long long n;
    cin >> n;

    long long sum = 1;
    long long result = 1;
    long long j = 2;

    while(true) {
        sum += j;
        long long temp = sum;
        result = 1;  
        for(int k = 0; k < count1 && primes[k] > 0; k++) {
            int count2 = 1;
            while(temp % primes[k] == 0) {
                temp /= primes[k];
                count2++;
            }
            result *= count2;
            if(temp == 1) {
                break;
            }
        }
        if(result > n) {
            break;
        }
        j++;
    }
    cout << sum << endl;
}
return 0;

    }