mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-08-01, 16:08   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

2·5·157 Posts
Default 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?
Citrix is offline   Reply With Quote
Old 2020-08-01, 17:51   #2
axn
 
axn's Avatar
 
Jun 2003

469310 Posts
Default

Quote:
Originally Posted by Citrix View Post
Brute force could be one way:- calculating N%b, N%b^2 ... and checking if they are all same.
You have to start with b^k > |c| and check both N%b^k and N%b^(k+1) are the same. Of course, without any size limits on b or c, this is going to take forever to rule out all potential b's.

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.
axn is offline   Reply With Quote
Old 2020-08-01, 18:35   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

2·5·157 Posts
Default

Quote:
Originally Posted by axn View Post
You have to start with b^k > |c| and check both N%b^k and N%b^(k+1) are the same. Of course, without any size limits on b or c, this is going to take forever to rule out all potential b's.

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.
Thanks.
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 b-1, 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?
Citrix is offline   Reply With Quote
Old 2020-08-02, 02:23   #4
axn
 
axn's Avatar
 
Jun 2003

10010010101012 Posts
Default

Quote:
Originally Posted by Citrix View Post
Thanks.
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 b-1, 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?
That will not probably work. Due to the presence of k, a large range of b's will be perfectly plausible for any given n.

I think we can slightly optimize the previous b-based approach to only look at prime b's.
axn is offline   Reply With Quote
Old 2020-08-02, 02:41   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

52×229 Posts
Default

Quote:
Originally Posted by Citrix View Post
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.
Yes.

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.
retina is offline   Reply With Quote
Old 2020-08-02, 05:23   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

2·5·157 Posts
Default

Quote:
Originally Posted by axn View Post
I think we can slightly optimize the previous b-based approach to only look at prime b's.
Why? b can be composite.

eg. 7*6^100+11
Citrix is offline   Reply With Quote
Old 2020-08-02, 05:28   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

52×229 Posts
Default

Quote:
Originally Posted by Citrix View Post
eg. 7*6^100+11
Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%
retina is offline   Reply With Quote
Old 2020-08-02, 06:03   #8
axn
 
axn's Avatar
 
Jun 2003

125516 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 offline   Reply With Quote
Old 2020-08-02, 06:05   #9
axn
 
axn's Avatar
 
Jun 2003

13·192 Posts
Default

Quote:
Originally Posted by retina View Post
Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%
"Size of N" is the digit length of N, which is basically O(log(N))
axn is offline   Reply With Quote
Old 2020-08-02, 06:11   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

110001000102 Posts
Default

Quote:
Originally Posted by axn View Post
That will not probably work. Due to the presence of k, a large range of b's will be perfectly plausible for any given n.
Your point for prime b makes sense. Thanks.

For small k values and large n values only 1-2 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
Citrix is offline   Reply With Quote
Old 2020-08-02, 06:38   #11
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

52·229 Posts
Default

Quote:
Originally Posted by axn View Post
"Size of N" is the digit length of N, which is basically O(log(N))
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 2020-08-02 at 06:38
retina is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
More Power!!!! petrw1 Teams 10 2019-10-15 17:36
TDP as power used? CRGreathouse Hardware 9 2016-02-06 18:46
Power 2 JohnFullspeed Miscellaneous Math 45 2011-07-10 20:13
testing, if a number is a power bitblit Math 8 2009-04-24 02:48
IBM Power 6 Unregistered Information & Answers 7 2008-08-30 14:36

All times are UTC. The time now is 01:22.

Sun Sep 20 01:22:52 UTC 2020 up 9 days, 22:33, 0 users, load averages: 1.01, 1.23, 1.24

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.