A series of series

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
A series of series
Here's a puzzle I thought up today.
How was the following complete series generated?
2, 3, 3, 3, 3
Well, obviously there are many ways it could have been generated but I'll tell you that the series is purely mathematical in nature and depends only on the first number in the series. Here's another one:
7, 1, 9, 3, 3, 3
An infinite number of series could be generated. I suspect all these series will be of finite length but haven't tried to prove it. Perhaps that could be an extra exercise after the nature of the series has been found by you guys.
How was the following complete series generated?
2, 3, 3, 3, 3
Well, obviously there are many ways it could have been generated but I'll tell you that the series is purely mathematical in nature and depends only on the first number in the series. Here's another one:
7, 1, 9, 3, 3, 3
An infinite number of series could be generated. I suspect all these series will be of finite length but haven't tried to prove it. Perhaps that could be an extra exercise after the nature of the series has been found by you guys.

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
I suspect this puzzle is quite difficult. I'll therefore give a major clue by providing a link I used when generating the series:
Don't click here unless you want a major clue
Don't click here unless you want a major clue

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
A few more series:
3, 1, 1, 9, 3
5, 3
11, 3
Some leading questions:
What do the first numbers in the series have in common? What do the subsequent numbers in the series have in common? How important are commas, really?
BTW, I just noticed something interesting in each of the series so far. They all end in a 3. I wonder if that is always the case.
3, 1, 1, 9, 3
5, 3
11, 3
Some leading questions:
What do the first numbers in the series have in common? What do the subsequent numbers in the series have in common? How important are commas, really?
BTW, I just noticed something interesting in each of the series so far. They all end in a 3. I wonder if that is always the case.

 Posts: 1278
 Joined: Wed Jun 02, 2004 11:04 pm
 Location: UK
I can't see why the 2 sequence doesn't go:
2, 9, 3, 9, 9, 9, 9, 9<br><br><table><tr bgcolor="#c0c0e0"><td> Spoiler  'select' text using mouse, or press CtrlA to reveal. </td></tr><tr bgcolor="white"><td><br>Adding a digit to the end of the number each time, the numbers remain prime, so:
2, 29, 293, 2939, 29399, 293999, 2939999 and 29399999 are all prime
but there is no 9 digit prime 29399999x<br><br></td></tr></table><br>
2, 9, 3, 9, 9, 9, 9, 9<br><br><table><tr bgcolor="#c0c0e0"><td> Spoiler  'select' text using mouse, or press CtrlA to reveal. </td></tr><tr bgcolor="white"><td><br>Adding a digit to the end of the number each time, the numbers remain prime, so:
2, 29, 293, 2939, 29399, 293999, 2939999 and 29399999 are all prime
but there is no 9 digit prime 29399999x<br><br></td></tr></table><br>

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
The reason is because my algorithm (in my head) was to always pick the lowest solution, when there were more than one possible solution.ceptimus wrote:I can't see why the 2 sequence doesn't go:
2, 9, 3, 9, 9, 9, 9, 9<br><br><table><tr bgcolor="#c0c0e0"><td> Spoiler  'select' text using mouse, or press CtrlA to reveal. </td></tr><tr bgcolor="white"><td><br>Adding a digit to the end of the number each time, the numbers remain prime, so:
2, 29, 293, 2939, 29399, 293999, 2939999 and 29399999 are all prime
but there is no 9 digit prime 29399999x<br><br></td></tr></table><br>
However, since you got the basic algorithm, can you prove that any series derived from this algorithm will always be finite?
(The stuff I mentioned earlier about how every series always seemed to end on a 3 is not true. I found a counterexample).

 Posts: 1278
 Joined: Wed Jun 02, 2004 11:04 pm
 Location: UK
I picked the longest solution, rather than the lowest. Whenever there is a choice, track all branches, and follow the one that lasts longest.
I think it's pretty clear that the series will always be finite. In base 10, the last digit of a prime (greater than 5) can never be 0, 2, 4, 5, 6, or 8. The sum of the individual digits can't be a multiple of three either. The digits 3 and 9 tend to be favored  adding a 1 or 7 at the end is more likely to make the number divisible by 3. Prime numbers thin out as they get higher, so the chances of forming a new prime number by adding a 1, 3, 7 or 9 to an existing one become increasingly slim as the number gets longer. OK, I know that's not a proof  merely arm waving.
I think it's pretty clear that the series will always be finite. In base 10, the last digit of a prime (greater than 5) can never be 0, 2, 4, 5, 6, or 8. The sum of the individual digits can't be a multiple of three either. The digits 3 and 9 tend to be favored  adding a 1 or 7 at the end is more likely to make the number divisible by 3. Prime numbers thin out as they get higher, so the chances of forming a new prime number by adding a 1, 3, 7 or 9 to an existing one become increasingly slim as the number gets longer. OK, I know that's not a proof  merely arm waving.

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive nonprimes. Guaranteed.ceptimus wrote:... Prime numbers thin out as they get higher, so the chances of forming a new prime number by adding a 1, 3, 7 or 9 to an existing one become increasingly slim as the number gets longer. OK, I know that's not a proof  merely arm waving.
Example, for N=3, one such nonprime sequence is
{ 14, 15, 16 }
But that is not a proof of your conjecture. Can we call it that?
Or have I misunderstood what you meant? I would wager that the conjecture is false, but I have no proof of that either.Ceptimus's Conjecture: For any integer base b>1, there is a largest prime P such that P*b+m is also prime, for any 0<m<b.
In base two, perhaps a negation of that could be called the Twin Mersenne Prime Conjecture: there is no largest Mersenne prime such that 1#m and 1#(m+1) are both prime.

 Posts: 1294
 Joined: Fri Jun 04, 2004 5:28 am
 Location: Wisconsin

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
Let M = (N+1)!Skeptoid wrote:Okay, N=7.6 x 10<sup>7</sup> +1.xouper wrote:Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive nonprimes. Guaranteed.
I'll settle for a proof. Number theory is cool.
Here's a sequence of N consecutive nonprimes:
{ M+2, M+3, M+4, M+5, ..., M+N, M+N+1 }
See, for example:
http://en.wikipedia.org/wiki/Prime_number#Prime_gaps
Notice that compared to M, the prime gap specified by N is relatively small.

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
Now that I think about it for a minute, that can't possibly be true for m>2, since 1#m can be prime only if m is prime, and if m is prime, then m+1 cannot be prime, and thus 1#(m+1) cannot be prime.xouper wrote:... the Twin Mersenne Prime Conjecture: there is no largest Mersenne prime such that 1#m and 1#(m+1) are both prime.
OK, that proves Ceptimus's Conjecture for base two.

 Posts: 1294
 Joined: Fri Jun 04, 2004 5:28 am
 Location: Wisconsin

 Posts: 1278
 Joined: Wed Jun 02, 2004 11:04 pm
 Location: UK
I don't think that wording of the 'conjecture' quite sums it up (unless I've misunderstood what you meant ). I would interpret your wording as saying 'there are no primes bigger than a certain limit where another prime can be generated by adding a single digit', which I also suspect is false. However, I'm not very good at math notation, so I may have misunderstood your wording. The wording should indicate that all the numbers in a series of length q, generated from the 'seed prime' by adding digits one at a time, must also be prime, not just the first one.xouper wrote:Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive nonprimes. Guaranteed.ceptimus wrote:... Prime numbers thin out as they get higher, so the chances of forming a new prime number by adding a 1, 3, 7 or 9 to an existing one become increasingly slim as the number gets longer. OK, I know that's not a proof  merely arm waving.
Example, for N=3, one such nonprime sequence is
{ 14, 15, 16 }
But that is not a proof of your conjecture. Can we call it that?
Or have I misunderstood what you meant? I would wager that the conjecture is false, but I have no proof of that either.Ceptimus's Conjecture: For any integer base b>1, there is a largest prime P such that P*b+m is also prime, for any 0<m<b.
In base two, perhaps a negation of that could be called the Twin Mersenne Prime Conjecture: there is no largest Mersenne prime such that 1#m and 1#(m+1) are both prime.
For me, a better wording of the 'ceptimus conjecture' (actually it's DanishDynamite's) would be:
In any base b > 2, there is no prime P[0] that can generate more than q primes by applying the iteration P[n+1] = P[n] * b + m (where 0 < m < b)
I would hazard a guess that q < (b + Log(base b)(P[0]))

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
Well, dang, that'll teach me to poste in haste.xouper wrote:Errrmm, not so fast, binarybreath. You forgot about Sophie Germain primes, wherein both P and 2P+1 are prime, which is the same as tacking a one on the end of the binary representation of a prime.xouper wrote:OK, that proves Ceptimus's Conjecture for base two.
It has not yet been proven that there are only finitely many Sophie Germain primes, so Ceptimus's Conjecture remains unrefuted for base two.
See, for example:
http://en.wikipedia.org/wiki/Sophie_Germain_prime

 Posts: 9473
 Joined: Fri Jun 11, 2004 4:52 am
 Location: has left the building
Yes, that is different from what I proposed.ceptimus wrote:DanishDynamite's Conjecture: In any base b>1, there is no prime P[0] that can generate more than q primes by applying the iteration P[n+1] = P[n] * b + m (where 0<m<b)
I had misunderstood and thought that you were saying that at some value W, q would be zero for all P>W, but I see now that you are not saying that. My error.
We can put the number base back to b>1, since it remains an open question whether there are infinitely many Sophie Germain primes.
See also Cunningham chains:
http://en.wikipedia.org/wiki/Cunningham_chain
Perhaps DD's conjecture becomes: All generalized Cunningham chains are complete.
Actually DD didn't go quite that far, but hey, why not? Generalized Cunningham chains are not restricted to increments less than the number base, only that the increment be relatively prime to the number base.
Also, as I understand it, DanishDynamite chains are slightly different than Cunningham chains in that DD's increment is not fixed for the entire chain.

 Posts: 2608
 Joined: Mon Jun 07, 2004 4:58 pm
 Location: Copenhagen
Interesting stuff, xouper.
Indeed. But it seems to me that if one could prove (and I use your flattering terminology) that all DD chains are complete, one would also have proven that all generalized Cunningham chains, where the increment is less than the number base, are complete.Also, as I understand it, DanishDynamite chains are slightly different than Cunningham chains in that DD's increment is not fixed for the entire chain.

 Posts: 145
 Joined: Sun Apr 03, 2005 6:25 am
Re: A series of series
Re: the primes.
I submitted a question to Math Chat some years ago
http://www.maa.org/features/mathchat/ma ... 16_99.html
and it was answered in the next column
http://www.maa.org/features/mathchat/ma ... 06_00.html
The idea, with different terminology, goes back to at least 1968 (snowball primes), but I'm sure people considered it earlier.
I submitted a question to Math Chat some years ago
http://www.maa.org/features/mathchat/ma ... 16_99.html
and it was answered in the next column
http://www.maa.org/features/mathchat/ma ... 06_00.html
The idea, with different terminology, goes back to at least 1968 (snowball primes), but I'm sure people considered it earlier.