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

30478 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

17×281 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 online now   Reply With Quote
Old 2020-08-01, 18:35   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

110001001112 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

17×281 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 online now   Reply With Quote
Old 2020-08-02, 02:41   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5,879 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 online now   Reply With Quote
Old 2020-08-02, 05:23   #6
Citrix
 
Citrix's Avatar
 
Jun 2003

110001001112 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

5,879 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 online now   Reply With Quote
Old 2020-08-02, 06:03   #8
axn
 
axn's Avatar
 
Jun 2003

17·281 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
Old 2020-08-02, 06:05   #9
axn
 
axn's Avatar
 
Jun 2003

17×281 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 online now   Reply With Quote
Old 2020-08-02, 06:11   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

157510 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

5,879 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 online now   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 10:39.

Thu Nov 26 10:39:11 UTC 2020 up 77 days, 7:50, 4 users, load averages: 2.02, 1.51, 1.47

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.