[QUOTE=philmoore;206782]I am extremely skeptical. You are saying that for for any positive q, it is possible to write q as k*b^n-1 for some k and b such that pfgw can then run a deterministic primality test. This requires a factorization of q+1 as k*b^n, and most people believe factoring q+1 is in general a MUCH more difficult problem than proving whether q is prime. Recall that even proving numbers of the form k*2^n-1 prime requires k < 2^n, which rules out most possible numbers q. So even if we don't need to factor k itself, finding a base b seems most unlikely.

If you still think you are on to something, try presenting a small example to show us how your method works.[/QUOTE]

Well I don't have an example, but I know, that for a fact running a 10000 digit test and prove if composit or prime can be done for the form k*b^n-1 in most cases (unless you have a several million digit base) in less than 10 seconds, while today you are using several months maybe even years on proving a q=2^n+p, which gives a lot of time to find the exact log(q)=log(k*b^n-1) solution.

Finding a solution with the proper software, should be done rather quickly, since it can be done this way:

using 2^28978+34429=q

q=8724 digits and log(q)=8723,2472143508470749037256913264

Now we have to find a k*b^n-1 solution where log(k*b^n-1)-log(q)=0

Since we are interested in finding the smallest k and the lowest base, our starting base should be 2. Now we have to do as follows:

log(q)/log(b)=log(8723,2472143508)/log(0,3010299956)=28978
Our starting n is then n=28978
Since we know that we can not exceed or go below log(q), then we now have to find the first k, for which k*2^28978-1 equals log(q). In my case I found using my spread sheet a strong candidate, which of course didn't match the full log(q), but for 1*2^28978-1 only the last 5 decimal digits in the decimal expansion varied from 2^28978+34429 (most likely the difference is 34430 since my strong solution is 2^28978-1).

It is obvious that non of your numbers can be transformed into a k*2^n-1 number, but the system is the same, no matter what base is used. I have manually checked up to n=24 and all prime bases <100, but no solutions was found. But the system is that one keep shooting for the lowest possible k and starts out with the lowest possible base. According to my experiences, it should also be enough to only test for solutions looking like this: k*primebase^n-1, since it should cover all positive numbers possible to write in the world.

I hope you got the idea, but to sum up, it is faster to prove a k*b^n-1 number and it is possible to write all q as k*b^n-1. And according to my system, it comes down to searching for a log(q)-log(k*b^n-1)=0 solution, starting out with the lowest possible base and searching the highest possible n, simply to get the lowest possible k in the solution.

Regards

KEP

[QUOTE=ET_;206784]What do you mean with [COLOR="Red"]k*(prime)b^n-1[/COLOR] ?

Luigi[/QUOTE]

Short and easy answered: k*primebase^n-1

I mean by that, that all numbers in the world should be possible to write in the form of k*primebase^n-1. Actually it appears to be much the same as factoring is only nescessary to do for p=prime, since all other p's is factoring the same numbers as p=prime. So in this case all k*primebase^n-1 covers the same numbers as k*b^n-1 would do.

Hope this covers your question.

Regards

KEP

You mean, some (every) number q , we can transform into q=k*p^n +/-1 ?

I think , that is not possible.

"using 2^28978+34429=q"

The factors of 2^28978+34428 or 2^28978+34430 are very rare. So it is not
sure to find (all of thinks) another relevant p^n what divided q-1 or q+1. Not in numbers with more than 10000 digits.

Maybe "pfgw" look for such forms.

both

"34201516571902560263*6^ 458 +1"
and the full length
"84589808111699289076243980310211398247526850801960339840075034~
984937005024785098788429830885818943087114229827966521865223571~
519264113061169061153911278676167484505717761550245627075220022~
027484879544154295256581059294887566388370992159484228535984032~
144355515243922299730621242005526658978769754968619183432465407~
98095726043089650831743692750635100484349589165217838171947009
"

we get with -tc option "is prime!"

Yes every number q is possible to transform into the form of:

q=k*b^n-1 or q=k*(p)b^n-1

If we are searching for only odd q, which any prime q above 2 is, then we will be covered by searching only the primebases. But regarding the transformation of q into k*b^n-1, then it is all a matter of having the right software, which does a search for a solution according to my previous post. If the numbers are very small, then it can be done manually, however with big numbers, it is nescessary with some sort of software to do the search among the primebases for a k*primebase^n-1 solution wich meets the demand of having log(q)-log(k*b^n-1)=0! With huge numbers, there is too many k/n solutions to search, before the right one is found, to even making it remotely possible to do by hand.

I'm not sure if I quite understood everything you wrote mr. Cybertronic, however in short terms, all q=k*b^n-1 it is just a matter of finding the right base and the right k.

However, I'll try to build a list, showing all q<=1M and wich k*primebase^n-1 they transform to. I'll construct the list such as k<b^n

Hope I got it right and got it all.

Regards

KEP

[QUOTE=KEP;206828]
I'll try to build a list, showing all q<=1M and wich k*primebase^n-1 they transform to. I'll construct the list such as k<b^n

Hope I got it right and got it all.

Regards

KEP[/QUOTE]

Mind that pfgw has another limitation, IIRC: k<2[sup]63[/sup].

Luigi

[QUOTE=ET_;206831]Mind that pfgw has another limitation, IIRC: k<2[sup]63[/sup].

Luigi[/QUOTE]

Okay I didn't know that, but that could potentially cause a problem since some of the PRPs here, might convert to a solution where k>2^63 even though the k's will start out low. Do you happen to know about any limitations in the base?

If I recall correctly, the limitation in n is maybe 12 million digits or maybe n=12M, this may however have changed since it was in a 2 year old version of PFGW that I read that.

However no matter what limitations there is to the software currently, it doesn't change anything regarding the fact that all q=k*b^n-1 :smile: (and maybe it is enough to search only k*(p)b^n-1 even though a further study should clear up that theory).

On another note, the limit in k, will eventually cause a problem for CRUS, unless another solution is found in the future once they eventually exceed the k limit on the really big conjectures :smile:

Regards

KEP

[QUOTE=philmoore;206782]I am extremely skeptical. You are saying that for for any positive q, it is possible to write q as k*b^n-1 for some k and b such that pfgw can then run a deterministic primality test. This requires a factorization of q+1 as k*b^n, and most people believe factoring q+1 is in general a MUCH more difficult problem than proving whether q is prime. Recall that even proving numbers of the form k*2^n-1 prime requires k < 2^n, which rules out most possible numbers q. So even if we don't need to factor k itself, finding a base b seems most unlikely.[/QUOTE]

Phil was being polite. Let me be blunt. Your idea can NOT, does NOT, will NOT work. Please stop extrapolating from tiny examples.

You are factoring q-1 or q+1 into k*b^n.
[U][COLOR=#810081][URL="http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic"]Fundamental_theorem_of_arithmetic[/URL].[/COLOR][/U]
n can only be as high as the highest degree of the consituent prime factors which will be very small (single digits), and k will be the rest.
No use.

Axn and Batalov, its obvious none of you are getting what I'm saying, so please talk nice to me. But since you don't care, then I really will not spend any more time on this very productive idea. Just remember for future references, that just because there is something one doesn't get, it doesn't mean that it is impossible or that you can allow yourself to blunt. But it's all up to yourself, but a fact is that if your project isn't open to new ideas, then nothing usefull is ever going to be produced.

Apparently this project is just a waiste of time, so I'm just glad that nothing much of resources has been waisted on trying to figure a way to help you.

TAKE CARE!

KEP

EDIT: Just took a look at the wiki link, it just emphasize that none of you are getting what I'm stating or trying to explain. But as previously mentioned it's your waist of resources and gladly not mine!

Hey KEP, keep cool !

I'm sure it is easy to show that one of our numbers we can't transform into k*p^n+1 (or -1). Is there generally an example then it is a huge of luck.
My opinion.

"EDIT: Just took a look at the wiki link, it just emphasize that none of you are getting what I'm stating or trying to explain. But as previously mentioned it's your waist of resources and gladly not mine!"

This is not fair.

Otherwise you have right. Every prime is of form k*2^n+1 :smile:

23=11*2^1+1
29=14*2^1+1
31=15*2^1+1
...

[quote=KEP;206828]However, I'll try to build a list, showing all q<=1M and wich k*primebase^n-1 they transform to. I'll construct the list such as k<b^n[/quote]
Do that for q=419. Take care. -Serge