What rules can I apply for divisible numbers?

Question

I'm trying to solve Project Euler problem 12. I've figured out a fast algorithm for the triangle numbers, but to see if they are devisable is just a pain...

## Code in Python ##

def checkdivisable_function(num):

    dev=    500 # Devisable By 501 numbers (as set in task)
    j=      0   # Counts by how many numbers it can be divided. 
    i=      0   # Running integer of the current divisor.

    while i<=num:
        i=i+1           
        if num%i==0:       # Success! A new divisor.
            j+=1                

        if j==dev:         # Success! Sufficient number of devisors.
            print "Solution:",num
            print "Finished!"
            exit()
    return False

In a nutshell: It takes a triangle number, and for every number below that using the running integer i it tries to divide. If it is devisable (num%i==0) it will add that to the running integer j, that counts how many numbers it has been divisable by.

This algorithm is by brute force and has turned out to be veeerryyy slow. I'm wondering if there's any rule or relationship for this which I can implement to speed it up; do divisible numbers have some property that I've missed?

Not asking to rewrite my code here, that's simply for reference, but asking what other properties I might use to quickly eliminate unintersting numbers :)

score 1 · Answer 1 · answered May 05 '14 at 23:41

1

The $n$th triangular number is $1+2+ \cdots + n = \frac{n(n+1)}2$. Now for a given triangluar number, take the square root of it and check around the square root to find what $n$ is. And since $\gcd(n,n+) = 1$, it suffices to check for the prime factors of $n$ and $n+1$ separately. Just keep in mind when $n \equiv 2 \pmod 4$, that you need to omit two from the list of prime factors.

answered May 05 '14 at 23:41

Sandeep Silwal

8,135

You don't have to check around. Given a triangular number $t$, you can solve the quadratic $2t=n^2+n$ to get $n$ directly. – Ross Millikan May 05 '14 at 23:44
I did not know how much time it takes to solve a quadratic versus checking maybe around $2\sqrt{n}$ numbers. – Sandeep Silwal May 05 '14 at 23:48

score 1 · Answer 2 · answered May 05 '14 at 23:48

The number of divisors function $\tau(n)$ is one of the basic functions from number theory. There is a simple recurrence for it:

$\tau(p^n) = n+1$ for any prime $p$
$\tau(mn) = \tau(m) \tau(n)$ whenever $m$ and $n$ are relatively prime

so if you find the factorization of a number $n$, you can compute $\tau(n)$ rather quickly.

What rules can I apply for divisible numbers?

2 Answers2