mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Power number (https://www.mersenneforum.org/showthread.php?t=25792)

 Citrix 2020-08-01 16:08

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?

 axn 2020-08-01 17:51

[QUOTE=Citrix;552199]Brute force could be one way:- calculating N%b, N%b^2 ... and checking if they are all same.[/QUOTE]
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.

 Citrix 2020-08-01 18:35

[QUOTE=axn;552207]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.[/QUOTE]

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?

 axn 2020-08-02 02:23

[QUOTE=Citrix;552210]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?[/QUOTE]

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.

 retina 2020-08-02 02:41

[QUOTE=Citrix;552199]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.[/QUOTE]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.

 Citrix 2020-08-02 05:23

[QUOTE=axn;552246]
I think we can slightly optimize the previous b-based approach to only look at prime b's.[/QUOTE]

Why? b can be composite.

eg. 7*6^100+11

 retina 2020-08-02 05:28

[QUOTE=Citrix;552262]eg. 7*6^100+11[/QUOTE]Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%

 axn 2020-08-02 06:03

[QUOTE=Citrix;552262]Why? b can be composite.

eg. 7*6^100+11[/QUOTE]

Sure, b can be composite. But a composite b [B]must[/B] also pass a prime b check as a [B]necessary[/B] condition.

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

[CODE]? N=7*6^100+11;
? N%(2^64)
%2 = 11
? N%(2^65)
%3 = 11[/CODE]

I will also pass b=3 check.
[CODE]? N%(3^64)
%4 = 11
? N%(3^65)
%5 = 11
[/CODE]
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 2020-08-02 06:05

[QUOTE=retina;552263]Doesn't meet the criteria: 6¹⁰⁰/(7×6¹⁰⁰+11) = 14.28...%[/QUOTE]

"Size of N" is the digit length of N, which is basically O(log(N))

 Citrix 2020-08-02 06:11

[QUOTE=axn;552246]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.

[/QUOTE]

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

 retina 2020-08-02 06:38

[QUOTE=axn;552269]"Size of N" is the digit length of N, which is basically O(log(N))[/QUOTE]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.

 axn 2020-08-02 06:38

[QUOTE=Citrix;552271]To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small[/QUOTE]

That still leaves surprisingly large search space.

How big is N? Less than 1000 bits? More than million bits?

How small is m? Less than 1000? More than million?

 axn 2020-08-02 06:40

[QUOTE=retina;552272]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.[/QUOTE]

Ah! You're thinking 99% as an exact number, whereas I'm pretty sure OP intended to give the general flavor of the structure of the number. Meaning, b^n part is the dominant term.

 Citrix 2020-08-02 07:25

[QUOTE=axn;552273]That still leaves surprisingly large search space.

How big is N? Less than 1000 bits? More than million bits?

How small is m? Less than 1000? More than million?[/QUOTE]

N~ 100,000 bits +
m <1000

We could also define k and c to be less than 2^64.

 axn 2020-08-02 16:47

[QUOTE=Citrix;552271]To refine the question I am looking for

k<m*n
c<m*n
n*m>b
with m small[/QUOTE]

[QUOTE=Citrix;552281]N~ 100,000 bits +
m <1000

We could also define k and c to be less than 2^64.[/QUOTE]
Let's take m=1000 so we have the largest search space.

When N is about 1e5 bits, the first n that satisfies m*n > b is n_min~=4500, and b_max ~=4.5 million

When N is about 1e6 bits, it is n_min ~= 39600 and b_max ~=39.6 million.

For the above numbers, it should be feasible to brute force all prime b's < b_max. Basic outline of the algorithm would be to do c = N % (b^k), (prime b from 2 to b_max) where b^k is about 256 bits (>> our target c with is < 64 bits).
If |c| < 2^64, we may have a potential solution, so trial factor N-c upto b_max and see if we get a complete factorization.

 All times are UTC. The time now is 10:38.