Blanket disclaimer: "if my calculations are correct, then ..."
The largest 3-smooth number that is less than 10^(10^100) is (2^i *
3^j) with exponents:
i =
5240457667536011553835317450277728970934205468247636517564762249075461811464263633070239562599567131
j =
17652672078113695646780517281391322686756289658776623674452938609239119167653573777408804025286004169
The next larger 3-smooth number, the smallest greater than 10^(10^100)
is (2^i * 3^j) with exponents:
i =
27911468858263353241606509519002899665982732517683148866824387638854242548327309121999804414370453492
j =
3348856574332340113860690779192481010573144504681280790577562072532814236920588073281466383293377609
The count of 3-smooth numbers below 10^(10^100) is:
348121998551416012668317959038480349279883545263691567113007477174736072507536976909539413592707867929651180140491194903602707766209055905884337013518535303190734936825129889519635109995577520171302547
Incredibly, Ramnujan's approximation is a mere 18 below this.
My counting function computes (n = indx(i, j)) as the index in
A003586(n) for entry (2^i * 3^j).
The first key to making this computation quickly is to use a result by
Donald J. Mintz, from "2,3 Sequence as Binary Mixture", The Fibonacci
Quaterly Volume 19, 351-360, 1981.
Mintz calls his counting function Ord(a, b), which is indexed starting
from 0 rather than from 1. His Theorem 9 states:
Ord(a,b) = a*b + Ord(a,0) + Ord(0,b)
My equivalent relationship is:
indx(i,j) = i*j + indx(i,0) + indx(0,j) - 1
where the -1 is a consequence of starting the index at 1. I use two
auxillary functions which happen to correspond directly to OEIS entries:
indx(i,j) = i*j + i_indx(i) + j_indx(j) - 1
where
i_indx(i) is A022331
j_indx(j) is A022330
This is a pretty good start, because it reduces the evaluation of any
point in the I-J plane to a single multiplication plus one evaluation
on each of the I-J axes. The trick to making i_indx() and j_indx()
efficient is to exploit Pick's Theorem.
Pick's Theorem is used to count vertices in and on a triangle with
vertices {(0,0), (i,0), (j,0)}. However, there are constraints for
using Pick's Theorem to count 3-smooth numbers. The simplest case
where Pick's Theorem applies is when (i,0) and (j,0) are at opposite
ends of a single hop. An example of this is shown below:
2295: (84 0) [-84 53]15 19342813113834066795298816
2296: (0 53) [65 -41]10 19383245667680019896796723
The first time that hop [-85 53]15 appears in the hop sequence is at
index 2295, where (84,0) is followed immediately by (0,53), so that
the diagonal of the triangle is covered by a single hop. I use
alpha(h) to refer to the first appears of hop(h) in the hop sequence
that generates 3-smooth numbers. In simple cases where the diagonal
corresponds to a single hop, Pick's Theorem can be formulated as:
pick(i,j) = 1 + ((i + 1) * (j + 1) / 2)
Since the hop corresponds to a convergent of the CF of log_2(3), the
numerator and denominator are relatively prime, so they cannot both be
even. Thus at least one of (i+1), (j+1) is even, and dividing the
product by 2 leaves a whole number.
Pick's Theorem is applied after the hop so that all of the vertices
are included in the count. So in this case:
j_indx(53) = pick(84,53) = 1 + (85 * 54 / 2) = 2296
i_indx(84) = j_indx(53) - 1
When Pick's Theorem applies, the computations are very fast, since the
only operations involved are three increments, one multiplication, and
a division which can be implemented as an integer right shift. All
the calculations are integers, so no expensive floating point
operations are needed.
There are slightly more complicated cases where Pick's Theorem can be
used. Triangles of the form {(0,0), (t*i,0), (0,t*j)} can sometimes
be counted using Pick's Theorem, as shown in the example below:
9041* (168 0) [-84 53]15
374144419156711147060143317175368453031918731001856
9042* (84 53) [-84 53]15
374926498489468450744392093558119645344593994579968
9043* (0 106) [149 -94]11
375710212613636260325580163599137907799836383538729
In this case, the sequence starts at (168,0) and two identical hops
[-84 53]15 are used to "skip" to (0,106). In cases with (t > 1),
Pick's Theorem can be cast in the form:
pick(i,j,t) = 1 + ((t * (i*(t*j + 1) + j + 1) / 2)
so that
j_indx(j) = pick(i,j,t) = 1 + (2 * (84*(2*53 + 1) + 53 + 1) / 2) = 9043
i_indx(i) = j_indx(j) - t = 9041
There are very few cases where Pick's Theorem can be applied to
counting vertices in a true right triangle in the I-J plane. These
rare case happen to be related to the "hop rectangles" that I
described in post #1. In total, only about 2150 of these cases exist
below the googolplex upper bound. Half correspond the hops that start
from the I axis and land on the J axis, and half correspond to hops
that start from the J axis and land on the I axis.
The final step to optimizing i_indx() and j_indx() exploits the
Pick-able cases by decomposing the set of vertices into a small number
of rectangles combined with Pick-able triangles. I'll try to describe
that process in post #3.
