A series of series

[DanishDynamite]

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.

[DanishDynamite]

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

[DanishDynamite]

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.

[ceptimus]

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 Ctrl-A 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>

[DanishDynamite]

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 Ctrl-A 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>

The reason is because my algorithm (in my head) was to always pick the lowest solution, when there were more than one possible solution.

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).

[ceptimus]

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.

[xouper]

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

Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.

Example, for N=3, one such non-prime sequence is

{ 14, 15, 16 }

But that is not a proof of your conjecture. Can we call it that?

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.

Or have I misunderstood what you meant? I would wager that the conjecture is false, but I have no proof of that either.

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.

[Skeptoid]

Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.

Okay, N=7.6 x 10⁷ +1. :shock: :D

I'll settle for a proof. Number theory is cool. 8)

[xouper]

Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.

Okay, N=7.6 x 10⁷ +1. :shock: :D

I'll settle for a proof. Number theory is cool. 8)

Let M = (N+1)!

Here's a sequence of N consecutive non-primes:

{ 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.

[xouper]

... the Twin Mersenne Prime Conjecture: there is no largest Mersenne prime such that 1#m and 1#(m+1) are both prime.

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.

OK, that proves Ceptimus's Conjecture for base two.

[Skeptoid]

Thanks, xoup. I find it fascinating that there can be an arbitrarily large gap between successive primes while at the same time there are an infinite number of prime pairs where the gap = 1 (if the Twin Prime Conjecture is true).

[ceptimus]

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

Which reminds me, give me any positive integer N and I will give you a sequence of N consecutive non-primes. Guaranteed.

Example, for N=3, one such non-prime sequence is

{ 14, 15, 16 }

But that is not a proof of your conjecture. Can we call it that?

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.

Or have I misunderstood what you meant? I would wager that the conjecture is false, but I have no proof of that either.

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.

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.

For me, a better wording of the 'ceptimus conjecture' (actually it's DanishDynamite's) :D 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]))

[DanishDynamite]

I knew this puzzle could lead to interesting things. :)

I agree with ceptimus, though. The "ceptimus conjecture" as described by xouper is not equivalent to the question I posed and I very much suspect this version to be false.

The version given by ceptimus is the one I had in mind.

[xouper]

OK, that proves Ceptimus's Conjecture for base two.

Errrmm, not so fast, binary-breath. 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.

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

Well, dang, that'll teach me to poste in haste. :D

[xouper]

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)

Yes, that is different from what I proposed.

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.

[DanishDynamite]

Interesting stuff, xouper.

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.

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.

[statisticool]

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.