Sequence A069354, Low bases with many divisibility tests
In base 10, there are well-known tests for divisibility by the primes 2, 3, and 5, and by the composite numbers 9 and 10. (The tests for 2, 5 and 10 look at the last digit; the tests for 3 and 9 use the repeated digit addition technique, also called 'casting out nines'.)
Are there bases for which there are more numbers that can be easily tested? In base 9, you can test for divisibility by 3 and 9 by looking at the last digit, and by 2, 4, or 8 by using the digit-addition trick. So base 9 has just as many easy tests (5) as base 10. But the number of primes is less (just two: 2 and 3). In base 6, you can test for divisibility by the same three primes (2, 3, 5) as in base 10.
Since division by composites can always be broken down into division by multiple primes, what really matters the most, for convenience and utility, is to have tests for as many primes as possible. So, in base 6 and in base 10 there are three prime numbers for which one can easily test for divisibility: 2, 3 and 5. Base 6 is the smallest base in which you can test for divisibility by 3 distinct primes.
I wondered what was the smallest base that has easy tests for 4 prime numbers? It turns out the answer is base 15, with the primes 2, 3, 5 and 7 being easily testable. What about 5 or more? In general, what is the smallest base in which one can easily test for divisibility by N prime numbers? The question is answered by the terms of Sloane's sequence A69354:
2, 3, 6, 15, 66, 210, 715, 7315, 38571, 254541, 728365, 11243155, 58524466, ...
It is easy to see that for any base B, the primes that have 'easy tests' are the prime factors of B combined with the prime factors of B-1. Since any two positive integers are relatively prime (meaning that they share no factors), there is no overlap, and so the number of primes with 'easy' tests is simply the number of distinct prime factors of B plus the number of distinct prime factors of B-1. (Duplicates don't count, so for example when B is 10, B-1 = 9 = 3×3 which only counts as a single prime factor.)
Closely related to this is sequence A59958, "Smallest number m such that m*(m+1) has n distinct prime factors." :
1, 2, 5, 14, 65, 209, 714, 7314, 38570, 254540, 728364, 11243154, 58524465, ...
in which the terms are just 1 less than the terms of A69354. It is pretty easy to see why: Since m is relatively prime to m+1, the prime factors of m(m+1) are just the prime factors of m combined with the prime factors of m+1. The terms are this sequence are one less because A59958 concerns the prime factors of m and of m+1 whereas A69354 concerns m-1 and m.
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2014 Mar 10.
s.27