20200801, 16:08  #1 
Jun 2003
3^{2}·5^{2}·7 Posts 
Power number
Given a natural number N is there a fast way to test if the number is of the form k*b^n+c where b^n contributes to 99% size of N; c<m*n where m is small.
Brute force could be one way: calculating N%b, N%b^2 ... and checking if they are all same. Anything faster? Would taking log of N help? 
20200801, 17:51  #2  
Jun 2003
1268_{16} Posts 
Quote:
If b & c can be reasonably limited (say both < 1e9), you can use sieving techniques to quickly figure out valid (b,c) combinations that can potentially equal N. 

20200801, 18:35  #3  
Jun 2003
11000100111_{2} Posts 
Quote:
A faster way might be to to : calculate max_n = log(N)/log(2) then for all n from 2 to max_n you calculate corresponding b value (use log to solve) int(N^(1/n))=b Since this is approximate we want to check b1, b and b+1 Then sieve over these values to see if there is a solution. This would still be under brute force. Anything faster than this? 

20200802, 02:23  #4  
Jun 2003
2^{3}·19·31 Posts 
Quote:
I think we can slightly optimize the previous bbased approach to only look at prime b's. 

20200802, 02:41  #5  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{5}·181 Posts 
Quote:
The first number to match the criteria is 100 = 1*99^1+1 Then 200 = 1*198^1+2 Then x*100 = 1*(99x)^1+x etc. So all you have to do is check that the number is divisible by 100. 

20200802, 05:23  #6 
Jun 2003
3^{2}×5^{2}×7 Posts 

20200802, 05:28  #7 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{5}×181 Posts 

20200802, 06:03  #8 
Jun 2003
2^{3}·19·31 Posts 
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 Code:
? N%(3^64) %4 = 11 ? N%(3^65) %5 = 11 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. 
20200802, 06:05  #9 
Jun 2003
4712_{10} Posts 

20200802, 06:11  #10  
Jun 2003
627_{16} Posts 
Quote:
For small k values and large n values only 12 b values will be possible. For small n a large number of b values will be possible. I am more interested in the first case. To refine the question I am looking for k<m*n c<m*n n*m>b with m small 

20200802, 06:38  #11 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{5}·181 Posts 
Okay. But it still doesn't meet the criterion 99%.
log(6¹⁰⁰)/log(7×6¹⁰⁰+11) = 98.92...% Indeed for any integer N I can't see how you ever get 99%. The only way would be something like e×e⁹⁹+0 = 99%. So k=e, b=e, n=99, c=0. And other multiples of those values. Last fiddled with by retina on 20200802 at 06:38 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
More Power!!!!  petrw1  Teams  10  20191015 17:36 
TDP as power used?  CRGreathouse  Hardware  9  20160206 18:46 
Power 2  JohnFullspeed  Miscellaneous Math  45  20110710 20:13 
testing, if a number is a power  bitblit  Math  8  20090424 02:48 
IBM Power 6  Unregistered  Information & Answers  7  20080830 14:36 