Number Theory

To borrow from Programming Challenges, number theory in programming contests includes the following:

• Prime Numbers
• Divisibility
• Modular Arithmetic

References

• Programming Challenges
• Basic Number Theory Every Programmer Should Know...

Primes

In general, I believe 99% of dealing with primes in a problem boils down to loading a list with the first N prime numbers via the Sieve of Erasthones:

    primeCnt = 0;
    for (i=0; i< UPPERLIMIT; i++) a[i] = i;
    for (i=2; i<UPPERLIMIT; i++)
     { /* for */
        if (0 != a[i])
         { /* found a prime */
            p[primeCnt] = i;
            primeCnt++;
            for (j=i*2; j < UPPERLIMIT; j=j+i) a[j] = 0;
         } /* found a prime */
     } /* for */ 

Of course, what do you do with the list? Using it to determine prime factors might be common.

Divisibility

In one sense divisibility is easy -- use mod. Here are some neat rules for divisibility:

• 2 - even, number is divisible if last digit is
• 3 - if repeated sum of digits is 3, 6, or 9 then number is divisible by 3
• 4 - if last 2 digits are divisible by 4
• 5 - ends in 0 or 5
• 6 - both rules 2 and 3 are true
• 7 - repeat: double last digit and subtract from number with last digit removed (integer divided by 10)

  458409
  45840 - 18 == 45822
  4582 - 4 == 4578
  457 - 16 == 441
  44 - 2 == 42
  4 - 4 == 0
  

• 8 - last 3 digits are divisble by 8
• 9 - sum of digits is 9
• 10 - last digit is a 0
• 11 - alternate subtracting and adding digits

  121: 1 - 2 + 1 == 0, so yes
  913: 9 - 1 + 3 == 11, so yes
  3729: 3 - 7 + 2 - 9 == -11, so yes
  14641: 1 - 4 + 6 - 4 + 1 == 0, so yes
  12345678906: 1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 0 + 6 == 11, so yes
  12345678905: 1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + 9 - 0 + 5 == 10, so no
  

• 12 - apply both rules for 3 and 4
• 13 - repeat: multiple last digit by4 and add back to number with last digit removed (integer divided by 10)

  2453674
  245367 + 16 == 245383
  24538 + 12 == 24550
  2455 + 0 == 2455
  245 + 20 == 265
  26 + 20 == 46
  4 + 24 == 28 (34 19 37 31 7)
  
  2453672
  245367 + 8 == 245375
  24537 + 20 == 24557
  2455 + 28 == 2483
  248 + 12 == 260
  26 + 0 == 26
  

• 14 - even and rule for 7
• 15 - rule for 3 and rule for 5
• 16 - last 4 digits are divisibile by 16

Modular Arithmetic

Modular arithmetic is sometimes called clock arithmetic. It is the idea that the set of numbers is finite and that you wrap to the begining when you go past the end (like a clock does). Lots of problems rely on these ideas (such as the "every nth person out" problems).

A typical code snippet might be something like:

n = (n + 1) mod MAX

When you think about it, this is how all arithmetic works. 9 + 1 = 10 When you add one to the largest base 10 digit (9) you get zero for an answer with a carry into the next column. You do the same in modular arithmetic except for forget the carry.