Brilliant numbers

Brilliant numbers, as defined by Peter Wallrodt, are numbers with two prime factors of the same length (in decimal notation). These numbers are generally used for cryptographic purposes, and for testing the performance of prime factoring programs.

The challenge is to continue the table shown below. This table contains the least brilliant number with an even number of digits and the greatest brilliant number with an odd number of digits.

It is possible to define n-brilliant numbers as the product of n prime numbers of the same length.

Maximal and minimal 2-brilliant numbers

The next table contains the maximal and minimal numbers with given number of figures whose two prime factors have the same length when expressed in decimal notation.

Maximal and minimal 3-brilliant numbers

The next table contains the maximal and minimal numbers with given number of figures whose three prime factors have the same length when expressed in decimal notation.

Maximal and minimal 4-brilliant numbers

The next table contains the maximal and minimal numbers with given number of figures whose four prime factors have the same length when expressed in decimal notation.

Instead of deriving density results using other people's work I decided to think about the problem myself for a change and I'm quite pleased with the results.

With brilliant numbers we're trying to represent a number in the region of b^n (where n is odd) as the product of two primes where the larger of the two primes ranges from b^(n/2) to b^((n+1)/2). First we work out the average number of factors that a number b^n+-x has in this range. If we say that the factor in the range b^((n-1)/2) to b^ (n/2) is p and the larger factor is q. It's easy to see that they have the same number of digits base b. If we plot p against q then the number of ways is the number of lattice points on the curve p= (b^n+x)/q in the relevant region. We can estimate this by looking at the area between the curves p=b^n/q and p=(b^n+1)/q between the specified limits. I make this to be roughly ln b /2 which, for base 10 is about 1.15.

I initially found it surprising that a number would be representable as the product of two numbers in the relevant ranges in on average more than one way. After all, some of these numbers are prime or are the product of a tiny prime and a large prime so I looked a bit closer.

• 1000=10*100=20*50=25*40
• 1001=11*91=13*77
• 1002=...
• 1003=17*59
• 1004=...
• 1005=15*67
• 1006=...
• 1007=19*53
• 1008=12*84=14*72=16*63=18*56=21*48=24*42=28*36
• 1009=...
• 1010=101*10
• 1011=...
• 1012=11*92=22*46=23*44
• 1013=...
• 1014=13*78=26*39
• 1015=39*35
• 1016=...
• 1017=...
• 1018=...

So that's 19 numbers representable in a total of 22 ways which works out to an average of 1.158 which is reasonable agreement. We then have to make sure that both p and q are prime. I can make a handwaving argument for the probabilities being independent based on the lack of usable modularity constraints. Anyway, when p and q are similar magnitude roughly one in n^2/4 ln^2 b will both be prime this goes down(up?) to one in (n^2-1) ln^2 b when they are at the other extremes of their ranges. The difference of (ln b)^2 can be usefully neglected when n is large enough to be interesting.

This means that we have ln b /2 ways of which only one in n^2/4 ln^2 b are acceptable. This cancels nicely to yield a density of 2- brilliants of one in n^2/2 ln b.

This gives excellent agreement with computed densities for instance the density of the first 1000 base 3 2-brilliants greater than 3^57 is one in 1765.118 and 57^2/2 ln 3 =1784.7

We can therefore expect that the density of 2-brilliants near 10^95 will be about one in 10390. The factor of ln b in the formula completely explains the density's base dependence left unexplained by the previous analysis.

From a handwavey point of view you can try and explain the base dependence by observing that 2^95+x is smaller than 10^95+x but then one has to mumble incoherently about being more likely to split into similar sized factors and I can't really justify it.

I have done a theoretical analysis of the density of 3-brilliants.
For numbers b^n±x the proportion of 3-brilliants is 1 in (n^3 * ln b)/9 for n=2 mod 3 and 1 in 4*(n^3* ln b)/9 for n=1 mod 3.

Last updated on May 28th, 2013.