mersenneforum.org Power number
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-01, 16:08 #1 Citrix     Jun 2003 62716 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
2020-08-01, 17:51   #2
axn

Jun 2003

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

2020-08-01, 18:35   #3
Citrix

Jun 2003

32×52×7 Posts

Quote:
 Originally Posted by axn 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?

2020-08-02, 02:23   #4
axn

Jun 2003

478110 Posts

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

2020-08-02, 02:41   #5
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

10110111101112 Posts

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

2020-08-02, 05:23   #6
Citrix

Jun 2003

62716 Posts

Quote:
 Originally Posted by axn 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

2020-08-02, 05:28   #7
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

587910 Posts

Quote:
 Originally Posted by Citrix eg. 7*6^100+11
Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%

2020-08-02, 06:03   #8
axn

Jun 2003

7×683 Posts

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

2020-08-02, 06:05   #9
axn

Jun 2003

7·683 Posts

Quote:
 Originally Posted by retina 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))

2020-08-02, 06:11   #10
Citrix

Jun 2003

157510 Posts

Quote:
 Originally Posted by axn 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

2020-08-02, 06:38   #11
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

587910 Posts

Quote:
 Originally Posted by axn "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

 Similar Threads Thread Thread Starter Forum Replies Last Post petrw1 Teams 10 2019-10-15 17:36 CRGreathouse Hardware 9 2016-02-06 18:46 JohnFullspeed Miscellaneous Math 45 2011-07-10 20:13 bitblit Math 8 2009-04-24 02:48 Unregistered Information & Answers 7 2008-08-30 14:36

All times are UTC. The time now is 11:34.

Sun Nov 29 11:34:36 UTC 2020 up 80 days, 8:45, 3 users, load averages: 1.40, 1.30, 1.21