You are viewing a single comment's thread from:
RE: Smartass answers to number theory programming problems
I'm guessing a big part of the estimate being high is that any non-zero number that contains a zero can't be an SPN, and you didn't check for that except in the last digit. That's going to apply to the vast majority of the numbers.
That rules a lot of numbers out "early", but my code would still start checking them.
The estimate I made was
log_2 ( 10^85 ) < 283
log_3 ( 10^85 ) < 179
log_5 ( 10^85 ) < 121
log_7 (10^85 ) < 101
So, 9*84 * ( 283 * 179 * 101 + 179 * 121 * 101 ) = 5.5 billion
But the code avoids trying many of the possibilities 2^a 3^b 7^d, 0 < a < 283, 0 < b < 179, 0 < d < 101, because most of them are bigger than 10^85. Probably there's some smart way to get an estimate closer to 845 million by taking that into account.