James sutton 188689 James sutton 188689 Finding Primes in Phone Numbers
Published September 02, 2017. Edited September 03, 2017

Yesterday, I learned of an interview question regarding finding phone numbers that are primes (a number greater than 1 that's only divisible by 1 and itself). Specifically, the task was to write a Ruby script to fetch prime phone numbers from Twilio's API, demonstrating both the competence to write a simple script and the ability to read and interact with an API.

I love this challenge, because it's deceptively simple and leads to several more questions. Immediately I had questions.

  • How common are prime phone numbers?
  • How feasible is finding a prime number through Twilio's API?
  • Does Twilio's API allow batch phone number requests?
  • Does Twilio's API return paginated, unique phone numbers?
  • If prime numbers are uncommon, will Twilio rate-limit me before I can find one?
  • Assuming ten-digit phone numbers, how long does it take a computer to calculate whether a number is prime or not, especially in Ruby?

My first response was to Google how common 10-digit prime numbers are. 30 seconds later, a random article suggests that about 4.2% of 10-digit numbers are prime.

Side note: Isn't is awesome that we can find answers to some of the most random questions in under a minute nowadays?

The Test

Anyway, I wanted to test this myself. Figuring the script wouldn't take long to write, I got started and immediately ran into trouble. For instance, Twilio's API's ruby example for getting available phone numbers appears to either have a typo or out-of-date compatibility with the newest twilio-ruby gem. Their example says to use

@client.account.available_phone_numbers

but it's missing the api method in there. It should actually read

@client.api.account.available_phone_numbers

Additionally, their API doesn't mention pagination, but their gem does include attributes like limit and page_size. I'm not sure if I was just missing something, or if these attributes have been deprecated, but these attributes and others seemed to have zero effect. My queries would return between 30 and 60 phone numbers, often with many duplicate numbers from the previous requests. After numerous requests, I ended up with only ~220 unique numbers. This was OK, but not ideal for testing.

I learned from the source of the interview question that querying Twilio's API with a specified area code will return better results, so I updated the script to grab available numbers from random area codes. Next thing I know, I have thousands of phone numbers!

I highly recommend trying it out for yourself, but I ultimately discovered that Twilio seems to be pretty close to the rate for prime number occurrences at ~4.7% of Twilio's numbers being prime.

Awesome! This got me curious. Who do I know with a prime phone number? I exported a CSV of my contacts from Google and wrote a new script to parse my contacts for prime numbers. After a little bit of tinkering and cleaning up number formatting, I had a working script! I've already reached out to those contacts, but 3.7% of my contacts had prime phone numbers!

The Results

This was a really fun waste of time, but I did learn a few things in addition to the answers to my questions above.

  • Prime phone numbers sort of uncommon, but 4.2% was higher than I expected.
  • It's not hard to find prime numbers through Twilio's API at all, despite their documentation issues!
  • Twilio's API leaves something to be desired in batching, pagination, and uniqueness, but this use-case is extremely uncommon anyway.
  • Twilio did not seem to rate-limit at all! Some requests were occasionally slow, but they don't seem to care too much about querying available numbers as fast as they can return results.
  • Ruby's not known for its performance, but it was totally fast enough for my use-case at around 10ms per phone number!
  • It is extremely likely that you have at least one prime phone number in your contacts list!

A few fun odds calculations:

  • If you have 50 contacts, there's an ~88% chance at least one of them has a prime phone number.
  • If you have 200 contacts, there's a ~99.98% chance that at least one of them has a prime phone number.
  • If you have 500 contacts, there's a ~99.99999995% chance that at least one of them has a prime phone number! That's roughly a 1 in 2 Billion chance of not having a prime number in your contact list!

The Code

If you're curious to check out your own contacts, I've embedded the script and instructions how to use it below:

# primes.rb
# This script will parse an exported Google Contacts CSV file and output any
#   contacts with prime phone numbers
#
# How to export Google Contacts CSV file:
#   1. Visit the 'old' Contacts website: https://www.google.com/contacts/?cplus=0
#   2. Click the 'More' dropdown at the top and select 'Export...'
#   3. Select the contacts you want to export, and click 'Export'
#
# Run this script by passing the path of an exported Google Contacts CSV file
#   e.g. `ruby primes.rb ~/Downloads/google.csv`

require 'prime'
require 'csv'

filename = ARGV[0]
numbers = CSV.read(filename, headers: true)

primes = []

numbers.each do |row|
  ['Phone 1 - Value','Phone 2 - Value','Phone 3 - Value'].each do |header|
    number = row[header]
    next if number.nil? || number.length < 10

    number = number.gsub(/^\+1|-|\s|\(|\)/,'').gsub(/^1(\d{10})/, '\1').to_i

    if Prime.prime?(number)
      puts "#{row['Name']}: #{number}, #{row[header]}"
      primes << number
    end
  end
end

percent = primes.length.to_f/numbers.length
puts "Primes: #{primes.length}/#{numbers.length} (#{(percent * 100).round(2)}%)"

Happy hacking. :)

ruby
experiments