k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1

jasong · 2016-04-22, 21:18

I don't have the mathematical ability to discuss this, but talking to Xyzzy tickled my brain in a way that made me remember a friend from years ago talking about this.

Basically, and I'll try to be as rigorously technical as possible, the idea is that k*b^n+/-c might be able to be tested with b equaling an integer higher than 2 WITHOUT referring to methods used for a simple string of digits. In other words, if my friend was correct(someone other than Xyzzy, he just managed to remind me of it) than there are mathematical shortcuts to testing k*b^n+/-c with b equaling integers greater than 2 and c equaling integers other than 1, but also occasionally including 1(for the odd-numbered b's)

Following is the idea for the equation my friend talked about. He was way over my head with the concepts, but was involved with jjsieve. I'm intentionally being vague about his identity because he likes his privacy, so please don't openly state his real name on here, but a bit of research and talking to jasonp, if he's still on here, should reveal more information. Jasonp is very bright in his own right but, while he is the public face of jjsieve, is not the only one involved. The math came from elsewhere.

Not sure if the source code for jjsieve is publicly available. If it is, and you have both the programming skills(enough to comprehend the code, if not duplicate it) and the math skills to understand complex sieving code, you might strongly benefit from giving it a look.

Below is simply a copy of what is in the title, since unnecessary scrolling sucks.

k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1

Byes.

chalsall · 2016-04-22, 21:31

Quote:

Originally Posted by jasong

Below is simply a copy of what is in the title, since unnecessary scrolling sucks.

You were given a very valuable gift today.

Someone's time.

Do you have a specificity important point to reciprocate?

axn · 2016-04-23, 11:15

Are you saying that if one studies jjsieve source, one will find a new method to test numbers of the form k*b^n+/-c?

science_man_88 · 2016-04-23, 16:49

maybe I'm missing something why is c limited to 1 to b-1 ? I can figure b^n-1 as the upper limit I can see k semi being limited to 1 to b-1 if you allow c to possibly go over that limit though.

you can sieve out a lot depending on what you do to sieve but most if not all have a thread that talks about them.

Batalov · 2016-04-23, 18:29

I am not sure people usually think about these things but I suppose this place to cast them is as good as any:

Suppose one has a great sieve (note: I am not talking about 10% faster, or even 50%; let's say 10x faster or better 1000000x faster. Hint: significant restriction on factors)
Then one will sieve perhaps much deeper, not just to Ts, or even Ps, but into Es.
That's great! There will be 20-50% less candidates left after such a great sieve compared to "some other form"
...Now, the form has to be searchable at least equally fast as, say, Proths/Riesels. Is this achievable?
- No! Except for very carefully researched forms. b>2 (but not GFN) is slower, |c| $\ne$ 1 is significantly slower.
Ergo: when people search for such primes they (hopefully) know that they are deliberately searching for "slow", hard, but exotic primes.

CRGreathouse · 2016-04-24, 03:40

Quote:

Originally Posted by Batalov

I am not sure people usually think about these things but I suppose this place to cast them is as good as any

Thank you.

2016-04-22, 21:18	#1
jasong "Jason Goatcher" Mar 2005 5×701 Posts	*kb^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1** I don't have the mathematical ability to discuss this, but talking to Xyzzy tickled my brain in a way that made me remember a friend from years ago talking about this. Basically, and I'll try to be as rigorously technical as possible, the idea is that kb^n+/-c might be able to be tested with b equaling an integer higher than 2 WITHOUT referring to methods used for a simple string of digits. In other words, if my friend was correct(someone other than Xyzzy, he just managed to remind me of it) than there are mathematical shortcuts to testing kb^n+/-c with b equaling integers greater than 2 and c equaling integers other than 1, but also occasionally including 1(for the odd-numbered b's) Following is the idea for the equation my friend talked about. He was way over my head with the concepts, but was involved with jjsieve. I'm intentionally being vague about his identity because he likes his privacy, so please don't openly state his real name on here, but a bit of research and talking to jasonp, if he's still on here, should reveal more information. Jasonp is very bright in his own right but, while he is the public face of jjsieve, is not the only one involved. The math came from elsewhere. Not sure if the source code for jjsieve is publicly available. If it is, and you have both the programming skills(enough to comprehend the code, if not duplicate it) and the math skills to understand complex sieving code, you might strongly benefit from giving it a look. Below is simply a copy of what is in the title, since unnecessary scrolling sucks. k*b^n+/-c where b is an integer greater than 2 and c is an integer from 1 to b-1 Byes.

2016-04-23, 18:29	#5
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 10010000101001₂ Posts	I am not sure people usually think about these things but I suppose this place to cast them is as good as any: Suppose one has a great sieve (note: I am not talking about 10% faster, or even 50%; let's say 10x faster or better 1000000x faster. Hint: significant restriction on factors) Then one will sieve perhaps much deeper, not just to Ts, or even Ps, but into Es. That's great! There will be 20-50% less candidates left after such a great sieve compared to "some other form" ...Now, the form has to be searchable at least equally fast as, say, Proths/Riesels. Is this achievable? - No! Except for very carefully researched forms. b>2 (but not GFN) is slower, \|c\| $\ne$ 1 is significantly slower. Ergo: when people search for such primes they (hopefully) know that they are deliberately searching for "slow", hard, but exotic primes.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Integer factorization?	bearnol2	Information & Answers	7	2010-12-09 02:50
Integer Factorization	mgb	Math	16	2007-12-17 10:43
Integer Factorization 2	mgb	Math	5	2007-07-23 12:55
Always an integer.	mfgoode	Puzzles	18	2007-07-13 18:03
Integer FFT	nevarcds	Math	4	2004-07-28 19:14

2016-04-23, 11:15	#3
axn Jun 2003 2×3²×269 Posts	Are you saying that if one studies jjsieve source, one will find a new method to test numbers of the form k*b^n+/-c?

2016-04-23, 16:49	#4
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶·131 Posts	maybe I'm missing something why is c limited to 1 to b-1 ? I can figure b^n-1 as the upper limit I can see k semi being limited to 1 to b-1 if you allow c to possibly go over that limit though. you can sieve out a lot depending on what you do to sieve but most if not all have a thread that talks about them.