Counting Divisors

A little over a year ago I started working on Project Euler problems. Used them as a handy way of learning Python. About that time I ran into a problem that stumped me completely. Problem 12 wanted to know the first triangle number with more than 500 divisors.

A triangle number of order (n) is defined as the sum of the arithmetic sequence from 1 to n, so triangle(3)=1+2+3=6 and triangle(7)=1+2+3+4+5+6+7=28. Calculating a triangle number is trivial. Figuring out how many divisors it has is a bit more challenging. I was trying various things that first time with caching the number of divisors for various numbers as you go up so that you don't have to calculate it again. Honestly, I don't really remember exactly what I did, but I remember that it was big and it took far more than the 1 minute maximum that any Project Euler problem should take. It took so long that I didn't even have the patience to let it run until it found a solution.

I skipped the problem then and let it sit undone for a long time. Until today. I fired up my trusty editor and busted out a solution. And it worked. And I'm thrilled. Not least because the code I came up with for finding the divisor takes all of 4 lines and only breaks the 1 second execution time mark at around n=1e+13 . Here's the code:

def divisors(n):
    total = 2
    for i in xrange(2, int(math.sqrt(n)) + 1):
        total += 2 if n % i == 0 else 0
    if math.sqrt(n) == math.floor(math.sqrt(n)):
        total -= 1
    return total

This works for n greater than 1.

Blackberry Dial Tone

In case anybody was wondering, the little sequence of dial tones that the Blackberry Curve 8330 makes when you hit send is the dual-tone number sequence 7933409.

I recorded the sound, analyzed it in Audacity, and found the following main frequency peaks:

  • 859 1207
  • 856 1480
  • 703 1481
  • 707 1479
  • 781 1217
  • 939 1340
  • 852 1481

These come fairly close to the following standard frequency pairs:

  • 852 1209
  • 852 1477
  • 697 1477
  • 697 1477
  • 770 1209
  • 941 1336
  • 852 1477

Which match to the keypad numbers 7933409.

Not sure what all of this means, but there's is a version of the sound generated from sequences of pure sine tones of the second set of frequencies, mixed together, and then passed through a low pass filter at a cutoff of 1600 to eliminate the clicks between silence and sound.

So 7933409 it is.