Thread: Power number
View Single Post
Old 2020-08-02, 06:03   #8
axn
 
axn's Avatar
 
Jun 2003

4,721 Posts
Default

Quote:
Originally Posted by Citrix View Post
Why? b can be composite.

eg. 7*6^100+11
Sure, b can be composite. But a composite b must also pass a prime b check as a necessary condition.

For example, consider N=7*6^100+11. It will pass the b=2 check.

Code:
? N=7*6^100+11;
? N%(2^64)
%2 = 11
? N%(2^65)
%3 = 11
I will also pass b=3 check.
Code:
? N%(3^64)
%4 = 11
? N%(3^65)
%5 = 11
If it didn't pass b=2 check, then no need to check any other even b. If it didn't pass b=3 check, then no need to check any composite base which is multiple of 3, and so on.

So we can limit ourselves to prime bases, as a first pass. In second pass, we subtract the potential c from N (i.e. N - N%(b^k) ) and then trial divide it to see if it factorises into small factors. If so, we get the actual representation as well.
axn is online now   Reply With Quote