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

2020-08-02, 06:38   #12
axn

Jun 2003

4,969 Posts

Quote:
 Originally Posted by Citrix To refine the question I am looking for kb with m small
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?

2020-08-02, 06:40   #13
axn

Jun 2003

136916 Posts

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

2020-08-02, 07:25   #14
Citrix

Jun 2003

1,579 Posts

Quote:
 Originally Posted by axn 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?
N~ 100,000 bits +
m <1000

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

2020-08-02, 16:47   #15
axn

Jun 2003

4,969 Posts

Quote:
 Originally Posted by Citrix To refine the question I am looking for kb with m small
Quote:
 Originally Posted by Citrix N~ 100,000 bits + m <1000 We could also define k and c to be less than 2^64.
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.

 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:21.

Tue May 18 11:21:10 UTC 2021 up 40 days, 6:02, 0 users, load averages: 1.39, 1.62, 1.65
The provided text is a discussion from a forum about a mathematical problem, specifically searching for a number \(N\) that can be expressed in the form \(k \cdot b^n + c\) with certain constraints on the values of \(k\), \(b\), \(n\), and \(c\).
multiple_questions

1. the first question is about the size of \(n\) and the value of \(m\).
2. the second question is about the feasibility of brute-forcing the solution given the constraints on \(n\), \(m\), \(k\), and \(c\).
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
mersenneforum.org Power number
 Register FAQ Search Today's Posts Mark Forums Read

2020-08-02, 06:38   #12
axn

Jun 2003

4,969 Posts

Quote:
 Originally Posted by Citrix To refine the question I am looking for kb with m small
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?

2020-08-02, 06:40   #13
axn

Jun 2003

136916 Posts

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

2020-08-02, 07:25   #14
Citrix

Jun 2003

1,579 Posts

Quote:
 Originally Posted by axn 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?
N~ 100,000 bits +
m <1000

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

2020-08-02, 16:47   #15
axn

Jun 2003

4,969 Posts

Quote:
 Originally Posted by Citrix To refine the question I am looking for kb with m small
Quote:
 Originally Posted by Citrix N~ 100,000 bits + m <1000 We could also define k and c to be less than 2^64.
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.

 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:21.

Tue May 18 11:21:10 UTC 2021 up 40 days, 6:02, 0 users, load averages: 1.39, 1.62, 1.65
user
The provided text is a discussion from a forum about a mathematical problem, specifically searching for a number \(N\) that can be expressed in the form \(k \cdot b^n + c\) with certain constraints on the values of \(k\), \(b\), \(n\), and \(c\).

TYPE: MULTIPLE_QUESTIONS

1. The first question is about the size of \(N\) and the value of \(m\).
2. The second question is about the feasibility of brute-forcing the solution given the constraints on \(N\), \(m\), \(k\), and \(c\).